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

К основным законам (тождествам, правилам) булевой алгебры относятся:

1. Коммутативные (переместительные) законы:

2. Ассоциативные (сочетательные) законы:

3. Дистрибутивные (распределительные) законы:

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

5. Законы тавтологии (идемпотентности):

6. Законы нулевого элемента:

7. Законы единичного элемента:

8. Законы дополнительного элемента. В булевой алгебре дополнительным элементом по отношению к а является отрицание

9. Законы двойственности (де Моргана):

Следствия:

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

11. Правила сокращения:

Следствия:

12. Правила склеивания:

Комментарии к законам булевой алгебры

1.  Для доказательства законов можно использовать:

а) метод совершенной индукции,

б) одни законы для доказательства других законов.

Метод совершенной индукции состоит в доказательстве эквивалентности левой и правой частей на всем множестве наборов аргументов. Для этого составляются таблицы истинности левой и правой частей с последующим их сравнением.

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

3. Некоторые законы можно распространять на произвольное число элементов.

4. В любом законе любую букву можно заменить на произвольное логическое выражение.

5. Законы применяются для упрощения булевых функций.

 

Разнообразие булевых функций

Булевы функции от одной переменной приведены в табл.2.1.

 

Обозначение аргумента и функции	Значения аргумента и функции		Наименование функции
x	0	1
	0	0	Логический ноль
	0	1	Повторение x
	1	0	Инверсия x
	1	1	Логическая единица

 

Таблица 2.1. Булевы функции от одной переменной

Булева функция от n аргументов f ⁿ(Х) называется вырожденной по аргументу x_i, если ее значение не зависит от этого аргумента, то есть для всех наборов аргументов имеет место равенство:

f ( x ₁, x ₂, ..., x_{i -1}, 0, x_{i +1}, ..., x_n ) = f ( x ₁, x ₂, x_{i -1}, 1, x_{i +1}, ..., x_n ).

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

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

Булевы функций от двух переменных приведены в табл.2.2.

Среди функций от двух переменных шесть вырожденных функций, к которым относятся:

· логический ноль;

· логическая единица;

· функция повторения аргументов x₁ и x₂;

· отрицание аргументов x₁ и x₂.

 

Некоторые функции от трех переменных представлены в табл. 2.3.

 

Замечание. Функции сумма по модулю 2 и исключающее ИЛИ для трех аргументов являются неэквивалентными.

 

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

Аргументы и функции (в символической форме)	Значения аргументов и функций				Обозначение функций	Наименование	Вырожденность	Представление функции в булевом базисе
x1	0	0	1	1
x2	0	1	0	1
	0	0	0	0	0	Логический ноль	+	-
	0	0	0	1	x1 & x2	Конъюнкция	-
	0	0	1	0	x1 D x2	Запрет x1 по x2	-
	0	0	1	1	x1	Повторение x1	+	-
	0	1	0	0	x2 D x1	Запрет x2 по x1	-
	0	1	0	1	x2	Повторение x2	+	-
	0	1	1	0	x1 Å x2	Сумма по модулю 2, неравнозначность, исключительное ИЛИ	-
	0	1	1	1	x1 Ú x2	Дизъюнкция	-
	1	0	0	0	x1 ¯ x2	Функция Вебба, стрелка Пирса	-
	1	0	0	1	x1 ~ x2 ( x1 º x2 )	Равнозначность, эквивалентность	-
	1	0	1	0		Отрицание x2	+
	1	0	1	1	x2 ® x1	Импликация от x2 к x1	-
	1	1	0	0		Отрицание x1	+
	1	1	0	1	x1 ® x2	Импликация от x1 к x2	-
	1	1	1	0	x1 ï x2	Штрих Шеффера	-
	1	1	1	1	1	Логическая единица	+	-

Таблица 2.2. Булевы функции от двух переменных

Значение аргументов			Значение функций
			Сумма по  модулю 2	Исключающее ИЛИ	Функция мажоритарности
x1	x2	x3	x1Å x2Å x3	XOR (x1, x2, x3)	x1#x2#x3
0	0	0	0	0	0
0	0	1	1	1	0
0	1	0	1	1	0
0	1	1	0	0	1
1	0	0	1	1	0
1	0	1	0	0	1
1	1	0	0	0	1
1	1	1	1	0	1

 

Таблица 2.3. Некоторые функции от трех переменных

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: