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

Тема: Логически общезначимые формулы

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

Цель: закрепить умение работать с формулами с кванторами, решать задачи логически общезначимые и выполнимые формулы.

Задачи. 1. Докажите, что формула ($ xA Þ" xB)Þ" x (A Þ B) общезначима (для краткости предполажим, что A есть предикат P (x) и B есть предикат Q (x)).

2. Упражнения 1-2 на стр. 63 по книге [1].

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

1. Решение. Докажем методом от противного. Допустим, что (($ xA Þ" xB)Þ" x (A Þ B)) _I ºЛ в некоторой интерпретации I. Тогда:

($ xA Þ" xB) _I ºИ и (" x (A Þ B)) _I ºЛ по определению импликации,

(P (i)Þ Q (i)) _I ºЛ для некоторого i Î I по смыслу квантора общности,

(P (i)) _I ºИ и (Q (i)) _I ºЛ по определению импликации,

($ xA) _I ºИ по смыслу квантора существования,

(" xB) _I ºЛ по смыслу квантора общности,

($ xA Þ" xB) _I ºЛ по определению импликации.

Получается противоречие: ($ xA Þ" xB) _I ºИ и ($ xA Þ" xB) _I ºЛ.

Значит, данная формула не может быть ложной в произвольной интерпретации I. Она истинна в любой интерпретации I, т.е. общезначима.

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

Докажите, что формула общезначима (для простоты предполагаем, что A есть предикат P (x) и B есть предикат Q (x)):

вариант	формула
	(" xA Þ" xB)Þ$ x (A Þ B)
	($ xA Þ$ xB)Þ$ x (A Þ B)
	(" xA Þ$ xB)Þ$ x (A Þ B)
	" x (A Ú B)Þ(" xA Ú$ xB)
	" x (A Ú B)Þ($ xA Ú" xB)
	(" xA Ù$ xB)Þ$ x (A Ù B)
	" x (A Þ B)Þ(" xA Þ" xB)
	" x (A Þ B)Þ(" xA Þ$ xB)
	" x (A Þ B)Þ($ xA Þ$ xB)
	$ x (A Þ B)Þ(" xA Þ$ xB)