Блог о математике, программировании, алгоритмах. И немного о работе операционной системы Linux.

среда, 11 мая 2011 г.

Булевы функции. Хозяйке на заметку.

Бинарных булевых функций существует 16.










0 0 0 1 0 1 0 1 0 1
0 1 0 0 1 1 0 0 1 1
1 0 0 0 0 0 1 1 1 1
1 1 0 0 0 0 0 0 0 0










0 0 0 1 0 1 0 1 0 1
0 1 0 0 1 1 0 0 1 1
1 0 0 0 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1
Причем только 10 из них являются по настоящему бинарными. 0 и 1 — нульарные функции. Скролько бы переменных мы в них не предполагали, они все будут не существенными. Функции , , а также их отрицания являются функциями одной переменной.
Перечислим те из приведенных выше операций, которые являются ассоциативными. То есть:
  1. Конъюнкция (логическое И):
  2. Дизъюнкиця (логическое ИЛИ):
  3. Исключающее ИЛИ:
  4. Эквивалентность:
Перечислим те из них, которые являются коммутативными: Заметим, что для того, чтобы операция была коммутативной, достаточно, чтобы значения для этой операции во второй и третьей строках совпадали. Таких операций будет 6.
  1. Стрелка Пирса:
  2. Исключающее ИЛИ (сложение по модулю 2):
  3. Штрих Шеффера:
  4. Конъюнкция (логическое И):
  5. Эквивалентность:
  6. Дизъюнкиця (логическое ИЛИ):