1.8. Минимизация сложных высказываний методом Квайна

Алгоритм:

1. Получить СДНФ.

2. Получить сокращенную ДНФ (СкДНФ), используя следующие равносильности:

- неполное склеивание;

- поглощение.

3. Построить импликантную матрицу, с помощью которой получить МДНФ.

Пример.

1. - ДНФ

- СДНФ

1 2 3 4 5 6

2. Применяя операции склеивания, получаем СкДНФ.

1-2:
1-5:
2-3:
3-4:
4-6:
5-6:

3. Импликантная матрица

	+	+
	+				+
		+	+
			+	+
				+		+
					+	+

Выбираем импликанты, которые поглощают все конституенты единицы.

1.9. Полные системы функций

1.9.1. Система функций {}

Теорема. Всякая булева функция порождается некоторой формулой, в которой есть только операции .

Доказательство. Пусть некоторая булева функция. Для нее можно поострить таблицу истинности, в которой будет 2ⁿстрок. Каждую строку можно представить в виде конъюнкции переменных х₁,…х_n, куда входит либо, либо. Если значение конъюнкции будет равно 1, то всю функцию можно представить в виде дизъюнкции этих конъюнкций.

Пример.

x	y	f(x,y)
0	0	1
0	1	1
1	0	0
1	1	1

Получим СДНФ, используя таблицу истинности.

Возникает вопрос: Существуют ли другие системы булевых функций, с помощью которых можно выразить все другие функции?

1.9.2. Замкнутые классы

Пусть множество булевых функций отnпеременных.

Замыканием F([F]) называется множество всех булевых функций, реализуемых формулами надF.

Множество функций (класс) называется замкнутым, если [F]=F.

Рассмотрим следующие классы функций.

1. Класс функций, сохраняющих 0:

.

2. Класс функций, сохраняющих 1:

3. Класс самодвойственных функций:

, где .

4. Класс монотонных функций

где.

5. Класс линейных функций

, где + - означает сложение по модулю 2, а знак конъюнкции опущен.

Теорема. Классы Т₀, Т₁, Т_*, Т_М,T_L– замкнуты.

Доказательство. Чтобы доказать, что некоторый класс Fзамкнут достаточно показать, что, если формула реализована в виде формулы надF, то она принадлежитF.

Рассмотрим доказательство для одного класса функций Т₀.

Пусть и. Тогда.

Аналогичные доказательства можно привести для остальных классов.

1.9.3. Функциональная полнота

Класс функций Fназывается полным, если его замыкание совпадает сP_n:

.

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

Теорема.

Пусть заданы две системы функций и.

Тогда, если система F– полная и все функции изFреализуемы формулами надG, то системаGтоже полная.

Доказательство. Пусть h– произвольная функция,. Тогда [F]=P_n, следовательно,hреализуема формулой, базисом которой являетсяF(). Если выполнить замену подформулыfiна подформулув формуле, то мы получим формулу надG.

Следовательно, функция hреализуется формулой.

Примеры:

1. Система {} – полная, т. к. любая логическая операция может быть выражена через дизъюнкцию, конъюнкцию и отрицание;

2. Система {} – полная, т. к.

3. Система {} – полная, т. к.

4. Система {|} – полная, т. к., а{}и{}– полные системы.

5. Система {} – полная, т. к.Представление логической операции системой{}называется полиномом Жегалкина. Таким образом, всякая логическая операция представима в виде

где- сложение по модулю 2, знак · обозначает конъюнкцию,.

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

Пример.

Докажем полноту системы {,,1}.

f	T0	T1	T*	TL	TM	В каждом столбце должен быть хотя бы один «-»
xy	+	-	-	+	-
xy	+	+	-	-	+
1	-	+	-	+	+

Проверка на принадлежность классу T₀.

Проверка на принадлежность классу T₁.

Проверка на принадлежность классу T*.

Проверка на принадлежность классу T_L.

Проверка на принадлежность классу T_M.

f(0,0)=0

f(0,1)=1

f(1,0)=1

f(1,1)=0

f(0,0)=0

f(0,1)=1

f(1,0)=1

f(1,1)=1