Учебное пособие: Дискретная математика

А«В

АÛВ

1

0

0

1

Эквиваленция, эквивалентность А тогда и только тогда, когда В; А эквивалентно В 1 – (A-B)² 56 АÅВ

А+В

АÚВ

АDВ

0

1

1

0

Сумма по модулю 2, сумма Жегалкина А плюс В; Либо А, либо В 67 А½В

1

1

1

0

Штрих Шеффера, антиконъюнкция Неверно, что А и В; А штрих Шеффера В 78 А¯В

А°В

АÚВ

1

0

0

0

Стрелка Пирса, антидизъюнкция, функция Вебба, функция Даггера Ни А, ни В; А стрелка Пирса В

Несмотря на то, что булевых функций от любого заданного числа m двоичных переменных конечное число, их слишком много, чтобы иметь запас преобразователей для любых встретившихся отображений. Рассмотрим сначала все возможные функции от одной двоичной переменной. Их четыре, две из них – константы (0 и 1), одна – тождественная функция и только одна – функция отрицания (функция НЕ) – является нетривиальной.

p	p
0	1
1	0

Очевидно, что число различных булевых функций от m переменных равно 2 в степени . При m = 2 это число 16, то есть всего функций от двух переменных 16, однако наиболее практически применимых из них меньше.

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

Пример.

Логическая формула задает функцию от трех переменных как суперпозицию функций одной и двух переменных.

Для уменьшения числа скобок вводятся приоритеты операций. Наиболее приоритетна функция отрицания. Затем идет конъюнкция, после нее – дизъюнкция. Все другие функции имеют равный приоритет, меньший, чем у дизъюнкции. Очевидно, что скобками можно установить желаемый порядок операций. Вышеприведенная формула может быть эквивалентно записана так: . Отметим, что используют и другое распределение приоритетов, в частности, полагая импликацию менее приоритетной, чем все другие функции.