logo
Все готово(Шпоры)

Булевы функции двух переменных

Табл.3. Булевы функции двух переменных

X1

X2

0 0 1 1

0 1 0 1

Наименование функции

Y0

0 0 0 0

const 0

Y1

0 0 0 1

конъюнкция x1&x2, x1|x2, x1x2, "И"

Y2

0 0 1 0

запрет по х2, х1*/х2

Y3

0 0 1 1

переменная х1

Y4

0 1 0 0

запрет по х1, /х1*х2

Y5

0 1 0 1

переменная х2

Y6

0 1 1 0

сумма по mod2

Y7

0 1 1 1

Дизъюнкция х1 V х2, x1+x2

Y8

1 0 0 0

стрелка Пирса x1x2

Y9

1 0 0 1

равнозначность x1~x2

Y10

1 0 1 0

инверсия х2, /х2

Y11

1 0 1 1

импликация х2х1

Y12

1 1 0 0

инверсия х1 /х1

Y13

1 1 0 1

импликация х1х2

Y14

1 1 1 0

штрих Шеффера х1/х2

Y15

1 1 1 1

const 1

Для каждой функции можно сформулировать логические правила формирования ее значений. Например: функция запрета по х1 повторяет единичные значения аргумента х2 всегда, когда х1 не равно 1; функция импликации (следования) х1х2 равна единице, если при переходе от х1 к х2 значения не убывают.

Из таблицы видно, что между БФ двух переменных имеет место соотношение:

yi=/y15-i, (i=0,1,..15) (1.3)

На основании этого можно записать:

0=/1, 1=/0 (0-15);

x=//x (3-12, 5-10);

x1/x2=/(x1x2) (1-14);

x1x2=/(x1+x2) (7-8); (1.4)

x1x2=/(x1~x2) (6-9);

x1/x2=/(x1x2) (2-13);

/x1x2=/(x2x1) (4-11);

Из 1.3 следует, что любая функция двух переменных выражается в аналитической форме через отрицание /x и любую из каждой пары {y0,y15}, {y1,y14}, {y2,y13}, {y6,y9}, {y7,y8}. Например, можно выбрать такой набор БФ: y0, /x, y1(&), y7(+), y9(~), y13(). Можно показать, что такой набор является избыточным, т.к. y9 и y13 можно выразить через остальные функции набора:

y9 = x1~x2 = x1x2+/x1/x2, y13=/x1+x2 (1.5)

Набор из оставшихся 4-х функций широко применяется на практике, но и он может быть сокращен за счет удаления y1 и y7.

Выражения, построенные из конечного числа логических переменных и знаков логических операций - называются булевыми выражениями. Введение каждой новой операции должно сопровождаться введением пары операторных скобок. Для упрощения формы записи выражений, как и в обычной алгебре, вводится понятие старшинства операций, например: отрицание, логическое умножение, логическое сложение (в порядке убывания).

Два выражения, дающие одинаковые значения на одних и тех же наборах переменных - называются тождественными.

В алгебре логики тождественность может быть проверена методом подстановки и вычисления значения выражения на всех наборах переменных.

Наглядным способом представления логических функций являются диаграммы Эйлера-Венна. Эти диаграммы приведены ниже для функций НЕ, И, ИЛИ.

а) б) в)

Рис.1.1. Диаграммы Эйлера-Венна для логических

функций НЕ (а), И (в), ИЛИ (б).

Ранее было показано, что одни БФ могут быть выражены через другие. Последние именуют базисными функциями или базисом.