10. Що таке Булева алгебра? Які операції булевої алгебри Ви знаєте?

Одним из первых, кто заинтересовался двоичной системой, стал немецкий ученый Готфрид Вильгельм Лейбниц, В своей работе "Искусство составления комбинаций" (1666 г.) он заложил основы формальной двоичной логики. Но основной вклад в исследование двоичной системы счисления внес английский математик-самоучка Джордж Буль. В своей работе под названием «Исследование законов мышления» (1854 г.) он изобрел своеобразную алгебру – систему обозначений и правил, применимую к всевозможным объектам, от чисел и букв до предложений (эта алгебра затем была названа в его честь булевой алгеброй). Пользуясь этой системой Буль мог закодировать высказывания – утверждения, истинность или ложность которых требовалось доказать, – с помощью символов своего языка, а затем манипулировать как двоичными числами.

В 1936 г. выпускник американского университета Клод Шеннон показал, что если построить электрические цепи в соответствии с принципами булевой алгебры, то они могли бы выражать логические отношения, определять истинность утверждений, а также выполнять сложные вычисления и вплотную приблизился к теоретическим основам построения компьютера.

Как уже говорилось при рассмотрении истории вычислительной техники, основу работы схем и устройств компьютера составляет специальный математический аппарат, называемый булевой алгеброй, алгеброй логики или исчислением высказываний. При этом под высказыванием понимается любое утверждение, о котором можно сказать, что оно истинно или ложно.

Если высказывание истинно, то считают, что его значение равно единице; если высказывание ложно, то считают, что его значение равно нулю. Таким образом, значения высказываний можно рассматривать как переменную величину, принимающую только два дискретных значения: 0 или 1. Это приводит к полному соответствию между логическими высказываниями в математической логике и двоичными цифрами в двоичной системе счисления, что позволяет описывать работу логических схем компьютера, проводить их анализ и синтез с помощью математического аппарата алгебры логики.

Всякое устройство компьютера, выполняющее арифметические или логические операции, можно рассматривать как функциональный преобразователь, входными переменными (аргументами) которого являются исходные двоичные числа x_i (i=1,n), а выходными функциями – yj (j=1,m) (рис. 2.6).

В этом случае функциями

y_j = f(x₁,x₂,…x_n),

где:

x_i – i-й вход;

n – число входов;

y_j – j-й выход;

m – число выходов,

можно описывать алгоритм работы любого устройства компьютера.

Входные переменные, так и выходные функции могут принимать лишь одно из двух возможных значений: 0 или 1, иначе говоря, аргументы и функции определены на множестве из двух чисел: 0 и 1 (это записывается как x_i,y_i{0,1}).

Алгебра логики устанав­ливает основные законы формирования и преобразования логических функций. Она позволяет представить любую сложную функцию в виде композиции простейших функций. Рассмотрим наиболее употребительные логические функции.

Так как каждая переменная x_i при этом равна 0 или 1, то для n переменных образуется множество разнообразных сочетаний или наборов входных переменных. Количество функций N от n аргументов выражается следующей зависимостью:

. (1.2)

Для n=0 определены две основные функции, не зависящие от каких-либо переменных: y₀, тождественно равную нулю (y₀0), и y₁, тождественно равную единице (y₁1). Технической интер­претацией функции y₁1 может быть генератор импульсов. При от­сутствии входных сигналов на выходе этого устройства всегда име­ются импульсы (единицы). Функция y₀0 может быть интерпретиро­вана отключенной схемой, сигналы от которой не поступают ни к каким устройствам.

При n=1 зависимость (1.2) дает N=4. Представим зависимость зна­чений этих функций от значения аргумента x в виде специальной таб­лицы истинности, определяющей значение функции в зависимости от комбинации вход­ных сигналов:

x1	yj
	y0	y1	y2	y3
0	0	0	1	1
1	0	1	0	1

Функции y₀ и y₄ имеют тот же смысл, что и функции y₀ и y₁ для n=0. Функция y₁=x повторяет значение x, а функция y₂ выдает значение, обратное значению x, и называется инверсией, или отрицанием x (отрицание обозначается , т. е.=0, если х = 1 , и =1 , если x = 0). Этим функциям соответствуют определенные технические анало­ги. Схема, реализующая зависимость у=х, называется повторите­лем, а схема y= – инвертором.

При n=2, значение N равно 16, т.е. от двух переменных можно построить шестнадцать различных логических функций y₁, y₂,..., y₁₆. Эти функции приведены в следующей таблице:

xi			yj
x1	x2	y1		y2	y3	y4	y5	y6	y7	y8	y9	y10	y11	y12	y13	y14	y15	y16
0	0	0		1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
0	1	0		0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	0	0		0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	1	0		0	0	0	0	0	0	0	1	1	1	1	1	1	1	1

Такими таблицами удобно описывать функционирование различных логических элементов и узлов компьютера.

Рассмотрим различные логические функции y_j двух переменных, представленные в таблице не в порядке их нумерации, а в той последовательности, которая позволит выявить их общие и наиболее характерные свойства.

1. Функции y₁ и y₁₆ являются, как и функции y₀ и y₄ для одной переменной, соответственно тождественно равными 0 и 1: y₀  0; y₁₆  1.

2. Функции y₁₁ и y₁₃, как и функция y₁ для одной переменной, повторяют соответственно переменные x₂ и x₁: y₁₁  x₂; y₁₃  x₁.

3. Функции y₄ и y₆, как и функция y₂ для одной переменной, являются соответственно отрицаниями переменных x₁ и x₂: y₄ = ;y₆ = .

4. Функция y₉ – конъюнкция (логическое умножение, или операция И) переменных x₁, х₂, которая обращается в единицу только в том случае, если аргументы x₁ и х₂ одновременно равны единице, и в нуль – во всех остальных случаях, т. е. если хотя бы один аргумент равен нулю. Иными словами, функция конъюнкции равна min(x₁,х₂). Обозначается конъюнкция знаком “Ù”, который читается как И. Значение конъюнкции для заданных аргументов находится по правилам логического умножения:

В общем случае, функцию конъюнкции можно определить для любого числа аргументов, т.е. x₁ Ù x₂ Ù x₃ Ù... . Знак “Ù” может быть опущен или заменен точкой, т.е.