Формулы равносильности.

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

АVВ  ВVА А&В  В&А

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

АV(ВVС)  (АVВ)VС А&(В&С)  (А&В) &С

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

АV(В&С)  (АVВ)&(АVС) А&(ВVС)  (А&В)V(А&С)

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

АVА  А А&А  А

5. Поглощение

АV(А&В)  А А&(АVВ)  А

6. Закон де Моргана

 &  V

7. Закон исключающий третьего

АV1  1 А&1  A

8. Закон противоречия

AV  A A&  

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

 A

10.  1 ,  0

11. AB  VB

12. AB  (AB)&(BA)

13. AB  A& V &B

14. A | B   V

15. AB   &

Дизъюнктивной нормальной формой (ДНФ) формулы называется выражение вида:

, (2.4)

где  элементарная конъюнкция.

Конъюнктивной нормальной формой (КНФ) формулы называется выражение вида:

, (2.5)

где  элементарная дизъюнкция.

Любую формулу можно представить в виде ДНФ или КНФ.

ПРИМЕР

Пусть дана формула

Требуется получить ДНФ и КНФ данной формулы.

Применяя формулы равносильности, получаем КНФ :

Применяя формулы равносильности, получаем ДНФ :

Совершенной дизъюнктивной нормальной формой (СДНФ) формулы называется такая ДНФ, для которой выполняются следующие условия:

1. Все элементарные конъюнкции, входящие в ДНФ , различны.

2. Все элементарные конъюнкции, входящие в ДНФ , содержат литеры, соответствующие всем переменным.

3. Каждая элементарная конъюнкция, входящая в ДНФ , не содержит двух одинаковых литер.

4. Каждая элементарная конъюнкция, входящая в ДНФ , не содержит переменную и ее отрицание.

СДНФ можно получить двумя способами:

1. по таблице истинности;

2. с помощью равносильных преобразований.

Совершенной конъюнктивной нормальной формой (СКНФ) формулы называется такая КНФ, для которой выполняются следующие условия:

1. Все элементарные дизъюнкции, входящие в КНФ , различны.

2. Все элементарные дизъюнкции, входящие в КНФ , содержат литеры, соответствующие всем переменным.

3. Каждая элементарная дизъюнкция, входящая в КНФ , не содержит двух одинаковых литер.

4. Каждая элементарная дизъюнкция, входящая в КНФ , не содержит переменную и ее отрицание.

Метод минимизации с помощью карт Вейча.

Алгоритм метода карт Вейча включает в себя следующие этапы:

1. Любая формула приводится к СДНФ.

2. Составляется карта Вейча. Карта Вейча – это таблица всех возможных комбинаций значений переменных. В соответствующие ячейки заносятся единицы, соответствующие конституентам СДНФ.

3. Единицы, стоящие по вертикали и горизонтали, объединяются (по 2 , по 4 . по 8 и т.д.). Объединение единиц соответствует операциям склеивания и поглощения. Иначе говоря, формируются максимальные подкубы.

4. Для каждого объединения выписываются конъюнкции из элементов, общих для каждой единицы, входящих в объединение..

5. Выше полученные конъюнкции составляют МДНФ.

Карты Вейча удобны при поиске МДНФ функций двух, трех и четырех переменных.

n=2

СДНФ=

1
1	1

МДНФ=

n=3

СДНФ=

1	1
	1		1

МДНФ=

n=4

СДНФ=

	1	1	1	1
		1
	1
			1	1

МДНФ=

Задание на практическую работу: