![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Тема: Отрицание формул
Продолжительность 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 с.
Дата публикования: 2015-03-26; Прочитано: 153 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!