7. Аксиомы и законы булевой алгебры

Булева алгебра базируется на нескольких аксиомах, из которых выводят основные законы для преобразований с двоичными переменными. Обоснованность выбора этих аксиом подтверждается таблицами истинности для рассмотренных операций. Каждая аксиома представлена в двух видах, что вытекает из принципа дуальности (двойственности) логических операций, согласно которому операции конъюнкции и дизъюнкции допускают взаимную замену, если одновременно поменять логическую 1 на 0, 0 на 1, знак на ∙, а ∙ на.

Аксиомы операции отрицания: ,.

Аксиомы операций конъюнкции и дизъюнкции:

1. ;; (2.1)

2. ;; (2.2)

3. ;. (2.3)

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

1. Переместительный закон

; . (2.4)

2. Сочетательный закон

; . (2.5)

3. Закон повторения (тавтологии)

; . (2.6)

4. Закон обращения: если , то. (2.7)

5. Закон двойной инверсии . (2.8)

6. Закон нулевого множества

; . (2.9)

7. Закон универсального множества

; . (2.10)

8. Закон дополнительности

; . (2.11)

9. Распределительный закон

; . (2.12)

10. Закон поглощения

; . (2.13)

11. Закон склеивания

; . (2.14)

12. Закон инверсии (закон Де Моргана)

; (2.15)

или после инвертирования левых и правых частей

; . (2.16)

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

Логическая функция может быть задана словесно, алгебраическим выражением и таблицей, которая называется таблицей истинности. Словесное представление, отражающее словесную взаимосвязь ее аргументов со значениями функции (например, функция трех аргументов принимает значения единицы, если два или более ее аргументов равные единице, во всех других случаях функция равна нулю). Словесное представление логической функции предшествует любому другому способу представления, поскольку оно отражает неформальную взаимосвязь между аргументами и функцией. Табличный способ, когда логическая функция задается в виде таблицы соответствия (таблицы истинности, состояния). При этом функция представляется в виде таблицы, в которой выписываются все возможные наборы аргументов в порядке возрастания их номеров, и для каждого набора устанавливается значение функции. Число наборов аргументов, а значит, и число значений функции равно , где– число переменных. В таблице 2.4 представлена функция, словесно заданная в предыдущем примере.

№ набора	Аргументы				Функция
0	0	0	0	0
1	0	0	1	0
2	0	1	0	0
3	0	1	1	1
4	1	0	0	0
5	1	0	1	1
6	1	1	0	1
7	1	1	1	1

Аналитический способ задания функции заключается в том, что логическая функция задается в виде алгебраического уравнения, в котором переменныесвязаны между собой знаками логических операций (таблица 2.3). Существуют две основные формы записи логических функций в алгебраическом виде, называемые нормальными. Первая –дизъюнктивная нормальная форма (ДНФ) – представляет собой логическую сумму элементарных логических произведений (или дизъюнкцию элементарных конъюнкций), в каждое из которых аргумент или его отрицание входит не более одного раза. Например,

. (2.17)

Вторая форма, или конъюнктивная нормальная форма (КНФ), есть логическое произведение элементарных логических сумм (или конъюнкция элементарных дизъюнкций). Например,

. (2.18) Элементарными называются такие дизъюнкции или конъюнкции, число переменных в которых меньше полного числа переменных, от которых зависит функция. Например, функции (2.17) и (2.18) зависят от трех переменных, а две из трех составляющих их дизъюнкций и конъюнкций соответственно включают только две переменные. Третьи дизъюнкция и конъюнкция включают полное число переменных, поэтому они являются неэлементарными. Рассмотрим функцию, представленную таблицей 2.4. Она равна единице на наборах переменных с номерами 3, 5, 6, 7, а на остальных наборах равна нулю. Отсюда формулировка записи этой функции по единичным значениям может быть представлена так:

. (2.19)

Такая конъюнкция, включающая в себя полный набор переменных, на котором функция равна единице, называется конституентой единицы (минтермом), а запись функции в виде суммы конституент единицы (т.е. дизъюнкция конституент единицы) называется совершенной дизъюнктивной нормальной формой (СДНФ). Аналогично конъюнкция, включающая полный набор переменных, на котором функция равна нулю, называется конституентой нуля (макстермом), а запись функции в виде суммы конституент нуля называется совершенной конъюнктивной нормальной формой (СКНФ а запись функции в виде суммы конституент нуля называется совершенной конъюктивной нормальной формой ()итуентой нуля ()которых).

. (2.20)

Используя закон Де Моргана (2.15), выражение (2.20) можно переписать в виде

;

. (2.21)

Таким образом, любая функция из табличной формы записи может быть преобразована в аналитическую с использованием элементарных функций И, ИЛИ, НЕ. Числовой способ задания функции используется для сокращения ее записи, при этом логическая функция записывается в виде логической суммы десятичных номеров двоичных наборов, на которых функция равна единице, например, для функции, заданной таблицей 2.4.

. (2.22)