Дополнительные равносильности

БУЛЕВЫ ФУНКЦИИ

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

Переменная х, принимающая значения 0 или 1, называется булевой (или логической, двоичной). Функция F, зависящая от булевых переменных  и принимающая также значения 0 или 1, называется булевой (или логической, двоичной) и обозначается .

Булевы функции F от n переменных  могут быть заданы посредством таблицы истинности, содержащей  строк и  столбцов. В левой части таблицы содержатся наборы значений n переменных, расположенные в порядке возрастания их десятичного эквивалента, а в правой ее части - значения функции F  на соответствующих наборах значений переменных.

В качестве примера рассмотрим таблицу истинности некоторой булевой функции F, зависящей от переменных ,  и .

			F
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Булева функция n переменных F  однозначно определяется  - разрядным булевым вектором ее значений w(F) (т.е. w(F) - таблица истинности функции F). Например, в этом примере имеем w(F)=(00100111).

Рассматриваемая булева функция F  принимает значения 0 на наборах 000, 001, 011 и 100, а значение 1 - на наборах 010, 101, 110 и 111.

Множество наборов, на которых функция F принимает значение 1, называется характеристическим и обозначается через   N_F. В настоящем примере имеет место N_F = (010, 101, 110, 111).

Общее число различных булевых функций F от n переменных равно . Т.е. число булевых функций от двух переменных равно , от трех переменных .

Элементарные булевы функции. Равносильности

Булевых (или логических) функций от одной переменной . Они приведены в следующей таблице:

	0		отрицание	1
0	0	0	1	1
1	0	1	0	1

Основные элементарные булевы функции от двух переменных приведены в следующей таблице:

		конъюнк- ция	дизъюнк- ция	имплика- ция	эквивален-тность	сложение по модулю два	стрелка Пирса	штрих Шеффера
0	0	0	0	1	1	0	1	1
0	1	0	1	1	0	1	0	1
1	0	0	1	0	0	1	0	1
1	1	1	1	1	1	0	0	0

Функция  называется конъюнкцией, ее обозначают также  , но чаще всего знак конъюнкции аналогично знаку умножения опускают и пишут . Конъюнкция  равна единице, только если =1 и =1 одновременно, поэтому ее часто называют функцией И. Еще одно название конъюнкции ― логическое умножение, поскольку ее таблица истинности действительно совпадает с таблицей обычного умножения для чисел 0 и 1.

Функция  называется дизъюнкцией. Дизъюнкция  равна единице, только если =1 или =1 (т.е. хотя бы одна переменная равна единице), поэтому ее часто называют функцией ИЛИ.

Кроме таблицы истинности, булевы функции могут быть заданы аналитически с помощью формул. Например, .

Если формула a реализует булеву функцию F,которая тождественно равна единице, то она называется тождественно истинной. Если формула a реализует булеву функцию F, которая тождественно равна нулю, то она называется тождественно ложной.

Если формулы a и b зависят от одних и тех же переменных и реализуют одну и ту же булеву функцию F,то формулы a и b называются равносильными.

 Основные равносильности

Закон двойного отрицания

.

Идемпотентность

, .

Коммутативность

, .

Ассоциативность

, .

Дистрибутивность

, .

Законы де Моргана

, .

Формулы с константами

, , ,

, ,   .

Дополнительные равносильности

,

,

,

,

,

,

,

,

,  (законы склеивания),

 (закон поглощения).

 (закон обобщенного склеивания).

Переменная  булевой функции F называется несущественной (или фиктивной), если , то есть если изменение значения  в каждом наборе значений  не меняет значения функции. При этом существует такая формула, реализующая эту булеву функцию, в которой отсутствует .

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

Решение.Применяя закон поглощения и закон склеивания, получим

F = .

Так как существует такая формула, реализующая эту булеву функцию, в которой отсутствует , то эта переменная является фиктивной.

Пример. С помощью таблицы истинности убедиться в справедливости законов де Моргана .

Решение. Построим таблицу истинности для  и .

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

Так как в таблице истинности булевым функциям  и  соответствуют одинаковые столбцы, то формулы  и  равносильны.

Пример. С помощью основных равносильностей доказать закон обобщенного склеивания .

Решение. Применяя закон склеивания (в обратном порядке, то есть ) и дистрибутивность (то есть вынесем за скобки  и ), получим

.

Пример. С помощью основных равносильностей доказать, что .

Решение. Применяя основные равносильности, получим

.