Практическое занятие №6

Тема: Дизъюнктивные и конъюнктивные нормальные формы

Продолжительность 2 часа

Цель: научиться строить СДНФ и СКНФ пропозициональных формул, научиться решать задачи на применение СДНФ и СКНФ.

Задачи. 1. Используя таблицу истинности, найдите СДНФ и СКНФ (от переменных p, q, r) формулы A º((p Ù q)ÞØ r)Û(Ø q Ù r).

2. Докажите, что все следствия СКНФ f ₁Ù…Ù f_m, где f ₁, …, f_m - совершенные дизъюнкции пропозициональных переменных, содержатся среди формул f ₁, …, f_m их всевозможных конъюнкций.

3. Упражнение 2.34 (а) – (д) на стр. 58 по книге [2].

Указания к решению задач.

1. Решение. Построим таблицу истинности формулы A:

p	q	r	p Ù q	Ø r	(p Ù q)ÞØ r	Ø q	Ø q Ù r	A
			л
			л
			л
			л
			л
			л

Выделим строки, в которых A º1, и применим рассуждение, проведенное в ходе доказательства теоремы 1.

.

Следовательно, (p Ù q Ù r)Ú(p ÙØ q Ù r)Ú(Ø p ÙØ q Ù r) – СДНФ A.

Выделим строки, в которых A º0, и аналогично находим СДНФ Ø A:

(p Ù q ÙØ r)Ú(p ÙØ q ÙØ r)Ú(Ø p Ù q Ù r)Ú(Ø p Ù q ÙØ r)Ú(Ø p ÙØ q ÙØ r).

Далее, находим СКНФ A, используя законы де Моргана:

A ºØ((p Ù q ÙØ r)Ú(p ÙØ q ÙØ r)Ú(Ø p Ù q Ù r)Ú(Ø p Ù q ÙØ r)Ú(Ø p ÙØ q ÙØ r))º

ºØ((p Ù q ÙØ r)ÙØ(p ÙØ q ÙØ r)ÙØ(Ø p Ù q Ù r)ÙØ(Ø p Ù q ÙØ r)ÙØ(Ø p ÙØ q ÙØ r))º

º(Ø p ÚØ q Ú r)Ù(Ø p Ú q Ú r)Ù(p ÚØ q ÚØ r)Ù(p ÚØ q Ú r)Ù(p Ú q Ú r).

2. Решение упражнения 2.33 на стр. 58 по книге [2].

Задачи для самостоятельной работы (по вариантам).

Используя таблицу истинности, найдите СДНФ и СКНФ (от переменных p, q, r) формулы A