Основные законы булевой алгебры

Законы и правила	Дизъюнкция	Конъюнкция
1. Закон двойного отрицания
2. Закон коммутативности	х1х2=х2х1	х1х2=х2х1
3. Закон ассоциативности	х1(х2х3) = (х1х2)х3	х1(х2х3) = (х1х2)х3
4. Закон дистрибутивности	х1(х2х3) =х1х2х1х3	х1х2х3= (х1х2)(х1х3)
5. Правила де-Моргана
6. Правила операций с константами 0 и 1
	х0 =х;х1 = 1	х0 = 0;х1 =х
7. Правила операций с переменной и ее инверсией
8. Закон поглощения	х1х1х2=х1	х1(х1х2) = х1
9. Закон идемпотентности	хх…х=х	хх…х=х

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

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

Используя закон дистрибутивности и выполняя тождественные преобразования, можно получить

.

3. Синтез комбинационных схем

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

Для синтеза комбинационных схем (цифровых автоматов без памяти) необходимо выполнить следующее:

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

2. сформировать алгебраическое представление реализуемой булевой функции;

3. осуществить минимизацию полученной булевой функции;

4. на основе выбранного набора логических элементов построить схему синтезируемого цифрового автомата.

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

В алгебре логики доказывается, что любую функцию алгебры логики, кроме функции f = 0, можно представить в виде формулы через конъюнкцию, дизъюнкцию и отрицание в виде

(4)

где — общее обозначение для аргументаx_kи его отрицания.

Логическое суммирование в (4) ведется для тех наборов ₁,₂, …,_k, …,_n, для которых.

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

Правило построения СДНФдля булевой функции, заданной таблицей истинности:

1) выписать из таблицы те наборы, для которых функция равна единице;

2) для каждого выписанного набора составить конъюнкцию ;

3) соединить полученные конъюнкции знаком дизъюнкции - получается СДНФ искомой функции.

Пример 1.Составить СДНФ для таблично заданной функции (табл. 5).

Таблица 5

х1	х2	х3	z
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	0

Используя правило построения СДНФ, получим:

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

Для рассмотренного примера 1СКНФ функции будет иметь вид:

.

Переход от СДНФ к СКНФ представления булевых функций осуществляется так:

• выписывается логическая сумма дизъюнктивных членов, не вошедших в СДНФ, т.е. отрицание функции;

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

Пример 2.Построить СКНФ булевой функции по ее СДНФ:. Получим отрицание этой функции:

Взяв отрицание от полученного выражения еще раз и использую правило де-Моргана, получим

Аналогично осуществляется переход от СКНФ к СДНФ представления функции алгебры логики.