Практическое занятие №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

№№	А
	(R Þ(Ø S ÚØ T))Û ((R Ù S)Þ T)
	R ÞØ(S Þ((R Ú T)ÞØ(S Ù T)))
	(R ÙØ(S Ú T))Þ((R Ù S)ÛØ T)
	(Ø(R Þ(R Ú S))Þ(Ø T Ù S))Ù T
	(R ÛØ(S Ú T))Þ(Ø(R Þ S)Ù T)
	(R ÞØ(S Ù T))Û((Ø R Ú S)Þ T)
	R ÞØ(S Þ(Ø(R Ú T)Þ(S Ù T)))
	(Ø(R Ù S)Ú T)Þ((R Ú S)ÛØ T)
	(Ø(R Þ(R Ù S))Þ(T Ú S))ÚØ T
	(R ÛØ(S Ù T))ÞØ((R Þ S)Ú T)