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

Тема: Отрицание формул

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

Цель: научиться решать задачи на построение отрицания формул.

Задачи. 1. Постройте отрицание формулы $ x $ yA Þ" x " yA (знак Ø должна располагаться только перед буквой A).

Докажите, что ни сама формула, ни ее отрицание не являются общезначимыми.

2. Упражнение 9.51 (а)-(д) на стр. 195 книги [2].

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

1. Решение. 1) Отрицание формулы преобразуем при помощи известных эквивалентностей:

эквивалентные формулы	используемые формулы
Ø($ x $ yA Þ" x " yA)
отрицание импликации Ø(A Þ A)º A ÙØ A
$ x $ yA ÙØ" x " yA
отрицание квантора общности Ø" xP º$ x Ø P
$ x $ yA Ù$ x Ø" yA
отрицание квантора общности Ø" xP º$ x Ø P
$ x $ yA Ù$ x $ y Ø A

Ответ: $ x $ yA Ù$ x $ y Ø A.

2) Пусть A есть x = y, I – любое множество, содержащее не менее двух элементов, i,j – различные элементы из I. Тогда:

(i = i) _I ºИ по смыслу отношения равенства,

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

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

(i = j) _I ºЛ по смыслу отношения равенства,

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

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

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

Следовательно, данная формула не общезначима.

3) Пусть A есть x = y Ù x ≠ y, I – любое непустое множество. Тогда:

(i = j Ù i ≠ j) _I ºЛ –противоречие (по таблице истинности) для всех i,j Î I,

($ y (i = y Ù i ≠ y)) _I ºЛ по смыслу квантора существования,

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

($ x $ yA Ù$ x $ y Ø A) _I ºЛ по определению конъюнкции.

Следовательно, отрицание данной формулы не является общезначимой формулой.

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

Постройте отрицание формулы (знак Ø должна располагаться только перед буквой A). Докажите, что ни сама формула, ни ее отрицание не являются общезначимыми:

вариант	формула
	" x $ yA Þ$ x " yA
	$ x " yA Þ" x $ yA
	" x $ yA Þ" y $ xA
	$ x " yA Þ$ y " xA
	" x $ yA Ù" y $ x Ø A
	$ x " yA Ù$ y " x Ø A
	" x $ yA Ú" y $ x Ø A
	$ x " yA Ú$ y " x Ø A
	" x " yA Ù" x " y Ø A
	$ x $ yA Ú$ x $ y Ø A

Используемая литература для практических занятий

1. Мендельсон Э. Введение в математическую логику. – М.: Наука, 1976. – 320 с.

2. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов. - М.: Академия, 2007. – 304 с.