Доказать тождественную истинность или тождественную ложностьформулы: Привести формулу к виду КНФили ДНФ. Найти СДНФ. Построить логическую сеть.
Доказать тождественную истинность или тождественную ложность
формулы: Привести формулу к виду КНФ
или ДНФ. Найти СДНФ. Построить логическую сеть.
Формула не является ни тождественно ложной, ни тождественно
истинной. — фиктивные переменные.
Что-то не так с работой?
Сводка по ответу
- Загружено студентом
- Проверено экспертом
- Использовано для обучения ИИ
- Доступно по подписке Кампус+
Купи подписку Кампус+ и изучай ответы
Миллион решенных задач от 299 руб
Купить подписку
Похожие работы
Найти предел функции, не пользуясь правилом Лопиталя.
Найдите значение выражения: двадцать семь в степени одна третья.
Кампус Библиотека
Материалы со всех ВУЗов страны
1 000 000+ полезных материалов
Это примеры на которых можно разобраться
Учись на отлично с библиотекой
Экосистема Кампус
Набор самых полезных инструментов, работающих на искусственном интеллекте для студентов всего мира.
Экосистема сервисов для учебы в удовольствие
Твой второй пилот в учебе, быстрые ответы на основе ИИ-шки
ТОП-эксперты помогут решить и объяснят тебе любой вопрос по учебе онлайн
Сообщество, где ты найдешь знакомства и получишь помощь
Мультифункциональный умный бот, который всегда под рукой
База знаний из 1 000 000+ материалов для учебы
VI. Система натурального вывода
Считается, что в логике высказывание существует так называемая «разрешающая процедура», т.е. автоматизированная процедура (алгоритм), которая позволяет определить, является ли формула тождественно-ложной, тождественно-истинной или выполнимой. Такой процедурой является построение таблиц истинности (хотя этот способ и не является единственным для логики высказываний).
В логике предикатов (в логике, где мы анализируем отношения внутри высказывания) такой процедуры не существует. Поэтому решение о том, является ли та или иная формула в логике предикатов тождественно-истинной или тождественно-ложной зависит от творческих способностей исследователя.
Тем не менее, существует несколько механизмов, позволяющих исследователю облегчить этот процесс. Одним из самых распространённых является натуральное исчисление предикатов. Здесь мы будем опираться на систему, построенную Уиллардом Куайном — знаменитым американским философом, логиком и математиком.
Смысл этого метода заключается в том, что исследователю предлагается несколько правил вывода первого порядка (прямых правил) и несколько правил вывода второго порядка (непрямых правил). Правила первого порядка – это правила, в которых из одной формулы следует другая. Правила второго порядка (непрямые правила), это правила, которые возникают в результате некой «цепочки» выводов.
Поясним на примере математики. Из формула «2х2» непосредственно следует «4». В логике бы это правило «2х2→4» называлось бы правилом первого порядка или прямым правилом. А вот формула «2+2х2» требует нескольких действий. Сначала мы должны 2 умножить на 2 и получать 4, а затем прибавить к четырем два. В результате мы получим 6. В логике такое правило «2+2х2→6» называлось бы правилом второго рода или непрямым правилом.
Иными словами. Если мы вынуждены, чтобы доказать некую формулу «а» пройти ряд процедур (a→b→c→d→e) чтобы получить в результате «e», вывод «a→e» назывался бы непрямым (выводом второго порядка).
Понятно, что правил второго рода (непрямых правил) может быть сколько угодно, в зависимости от предпочтений исследователя. А вот правила первого рода (прямые правила) весьма ограничены.
Сначала перечислим их, а затем разъясним:
Правила вывода первого рода:
- а,b ⊧ a˄b –введение ˄ — конъюнкции — (кратко: В˄)
Поясняем. Знак «╞» означает логическое следование и читается «следовательно». Название правила «введение конъюнкции» кратко обозначается, как «В˄». Далее, по аналогии:
- a˄b ⊧ а – удаление (исключение) конъюнкции ˄ (кратко У˄)
- ¬(a˄b) ⊧ ¬a∨¬b — отрицание ˄ (кратко О˄)
- а ⊧ а˅b – введение ˅ (В˅)
- а˅b, ¬a ⊧ b — удаление ˅ (У˅)
- ¬(а˅b) ⊧¬a∧¬b — отрицание ˅ (О˅)
- а⊃b, a ⊧ b – удаление ⊃ (У⊃)¹
- а⊃b, ¬b ⊧ ¬a– удаление ⊃ (У⊃)²
- a, b ⊧ (а⊃b), (b⊃a) — введение ⊃ (В⊃)
- ¬(а⊃b) ⊧ a˄¬b — отрицание ⊃ (О⊃)
- а⊃b, b⊃a ⊧ a≡b — введение ≡ (В≡)
- a≡b ⊧ а⊃b, b⊃a — удаление ≡ (У≡)
- а⊧ ¬¬а — введение двойного отрицания (В¬¬)
- ¬¬а⊧ а — удаление двойного отрицания (У¬¬)
Дополнительная информация
Правила вывода второго рода (которые нужны в любом случае):
(а⊃с)˄(b⊃с)⊧ (а˅b) →с – рассуждение разбором случаев (РРС)
(b˄¬b)⊃а⊧¬а – сведение к абсурду (СА)
¬а⊃(b˄¬b)⊧а – доказательство от противного (ДОП)
(Г, a⊧ b) ⊧ (Г⊧ a→b) — правило дедукции. Читается: если из множества гипотез Г и посылки а логически следует b, то из множества гипотез Г логически следует a⊃b.
Дополнительная информация
Правило введения импликации можно прочитать так: Если в системе вывода мы имеем «a» и «b», то мы вправе сделать вывод «а⊃b» или «b⊃a».
В другом написании эти правила выглядят так:
В˄ | а, b | У˄ | a˄b | О˄ | ¬(a˄b) | В˅ | а | У˅ | а˅b, ¬a | О˅ | ¬(а˅b) |
a˄b | а | ¬a∨¬b | а˅b | b | ¬a∧¬b |
У⊃ | а⊃b, a | У⊃ | а⊃b, ¬b | В⊃ | a, b | О⊃ | ¬(а⊃b) |
b | ¬a | (а⊃b), (b⊃a) | a˄¬b |
В≡ | а⊃b, b⊃a | У≡ | a≡b | В¬¬ | а | У¬¬ | ¬¬а |
a≡b | а⊃b, b⊃a | ¬¬а | a |
РРС | (а⊃с)˄(b⊃с) | СА | (b˄¬b)⊃а | ДОП | ¬а⊃(b˄¬b) |
(а˅b)→с | ¬а | а |
ПД | Г, a ⊧b |
Г⊧ a⊃b |
Что значит доказать формулу? Это означает, что мы её сначала разбиваем на части (согласно правилам вывода) а затем собираем по частям (согласно тем же правилам). Простой пример: Надо доказать элементарную формулу вида a˄b. Записываем ее первым действием:
- a˄b
- а – получаем из действия 1 путем применения правила исключения конъюнкции.
- b — получаем из действия 1 путем применения правила исключения конъюнкции.
- a˄b — получаем из действий 2 и 3 путем применения правила введения конъюнкции. ■
Формула считается доказанной. Это значит, что она выполнима и не является тождественно-ложной.
Важно
Чтобы доказать, что формула является тождественно-истинной, мы должны строить доказательство «от противного», т.е. должны предположить, что формула ложна. Если мы найдем в формуле противоречие (предположив, что она ложная), значит изначальная формула – тождественно-истинная. |
Предположим, дается формула a⊃(b⊃a) — закон ввода истинного антецедента.
Пытаемся понять смысл формулы.
Дано некое «a». Из этого мы делаем вывод, что «а» истинно при условии «b» (по-научному – может ли произвольное «b» имплицировать «а»?)
Постараемся все это перевести на естественный язык.
а — Москва – столица России.
b – Париж столица Франции.
Если верно, что «Москва столица России», следует ли из этого, что «Москва столица России при условии, что Париж столица Франции»?
Пытаемся разобраться. Дана формула a⊃(b⊃a). Доказательство от противного:
Предположим, что формула не верна. Записываем допущение, где эту формулу отрицаем.
Чтобы отрицать формулу, берём её всю в скобки и ставим перед ней знак отрицания «¬». Получаем + ¬(a⊃(b⊃a)).
Действие второе. Вспоминаем, как отрицается импликация. Схема такая: ¬(a⊃b)→a˄¬b. Следовательно, записываем:
- a˄¬(b⊃a) из 1 по О⊃.
Читаем второе действие так: a˄¬(b⊃a) из первого действия по закону отрицания импликации.
- a из 2 по У˄.
- ¬(b→a) из 2 по У˄.
В 3 и 4 действии мы разделили формулу a˄¬(b⊃a) пополам по закону удаления конъюнкции.
- b˄¬a – из 4 по О⊃.
- ¬a – из 5 по У˄.
Теперь обратите внимание: у нас есть «¬a» в шестом действии и «а» в третьем действии. Мы создаем противоречие по закону введения конъюнкции:
- a˄¬a – из 6 и 3 по В˄.
Теперь мы по закону введения импликации соединяем формулы из седьмого и первого действий. Из противоречия выводим отрицание основной формулы:
- (a˄¬a)⊃¬(a⊃ (b⊃a)) из 7 и 1 по В⊃.
Поскольку из противоречия мы получили отрицание основной формулы, следовательно, мы делаем вывод о том, что верна основная формула. Это – закон доказательства от противного. Записываем последнее действие:
- a⊃(b⊃a) из 8 по ДОП.■
Значит, рассуждение «Если верно, что «Москва столица России», следовательно «Москва столица России при условии, что Париж столица Фран-ции» — рассуждение верное.
То же самое мы можем проделать, не прибегая к методу доказательства от противного (доказательство более простое, но менее изящное):
Т.е., мы берем в качестве посылок антецедент всей формулы (a) и антецедент из консеквента (b⊃a) – «b». Пытаемся составить формулу по правилам натурального вывода.
- b⊃a – из 1 и 2 по В⊃.
Понятно, что мы можем из двух посылок получить и «a⊃b», и «a⊃а», и «b⊃b», и «a˄b», и «a˅b»… Но для доказательства исходной формулы нам нужно именно «b⊃a». Важно, что это действие мы выполняем строго по законам натурального вывода.
- a⊃(b⊃a) из 3 и 1 по В⊃. ■
Теперь давайте попробуем решить более сложную теорему. Предположим, что дано (a˄b)⊃c))⊃(a⊃(b⊃c)) – закон экспортации. В качестве допущения принимаем антецеденты формулы:
Для удобства, допущения мы обозначаем знаком «+».
- a˄b – из 2 и 3 по В˄
- с – из 1 и 4 по У⊃
Последний пункт надо пояснить. Имея в первом действии (a˄b)⊃c и в четвертом a˄b, легко получаем «с» по правилу (а⊃b), a╞ b. Правило называется «Удаление импликации» (У⊃).
- b⊃c из 5 и 3 по В⊃
- a⊃(b⊃c) из 6 и 2 по В⊃
- (a˄b)⊃c))⊃(a⊃(b⊃c)) – из 7 и 1 по В⊃■
Попробуем эту же формулу решить методом «от противного». В качестве допущения предположим, что она ложна:
- + ¬((a˄b)⊃c))⊃(a⊃(b⊃c)))
- (a˄b)⊃c))˄¬(a⊃(b⊃c)) из 1 по О⊃
- (a˄b)⊃c) из 2 по У˄
- ¬(a⊃(b⊃c)) из 2 по У˄
- a˄¬(b⊃c) из 4 по О⊃
- a из 5 по У˄
- ¬(b⊃c) из 5 по У˄
- b˄¬c из 7 по О⊃
- b из 8 по У˄
- ¬c из 8 по У˄
- ¬(a˄b) из 10 и 3 по У⊃
- ¬a˅¬b из 11 по О˄
- ¬a из 12 и 9 по У˅
- ¬a˄a из 13 и 6 по В˄
- ¬((a˄b)⊃c))⊃(a⊃(b⊃c)))⊃(¬a˄a) из 1 и 14 по В⊃
- (a˄b)⊃c))⊃(a⊃(b⊃c)) из 15 по ДОП■
Некоторые действия требуют пояснений.
Действие 11. В выводе мы имеем две формулы «¬c» и «(a˄b)⊃c)». По правилу удаления импликации «а⊃b, ¬b) ╞ ¬a» получаем формулу «¬(a˄b)».
Действие 13. В выводе мы имеем две формулы «¬a˅¬b» и «b». По правилу удаления дизъюнкции «а˅b, ¬a ╞ b» получаем формулу «¬(a˄b)».
Действие 14. В этом действии мы достигли главного результата — противоречия.
Действие 15. По правилу введения импликации, мы привели формулу к противоречию. Мы могли бы свести формулу к абсурду, если бы поменяли местами условие и следствие: «(¬a˄a)⊃¬((a˄b)⊃c))⊃(a⊃(b⊃c)))». Правило сведения к абсурду и правило доказательства от противного – идентичны.
Действие 16. Поскольку мы доказали ложность нашего предположения (что формула ложна), значит изначальная формула истинна.
Важно
Совет
Если это невозможно, то воспользуйтесь другими советами.
Если формула представляет собой тождество «A≡B», то решая её «от противного», предположите, что либо антецедент, либо консеквент — ложные. То есть, либо «¬(¬A⊃B)», либо «¬(A⊃¬B)».
Если формула представляет собой сложную импликацию вида «A⊃B⊃C⊃D⊃E», то в качестве допущений можно взять все формулы, кроме последнего члена импликации.
Для закрепления навыков, попробуем решить еще одну аксиому:
Сложность в том, что специального правила для отрицания тождества нет.
Мы можем предположить, что эта формула не верна, если отрицаем одну из частей тождества:
Предположим, мы выбираем второй вариант. Записываем наши предположения в посылках:
- + a⊃b
- + a˄¬b
- a – из 2 по У˄
- ¬b– из 2 по У˄
- b– из 1 и 3 по У⊃
- b˄¬b– из 5 и 4 по В˄
- (b˄¬b)⊃(a˄¬b) – из 2 и 6 по В⊃
- ¬(a˄¬b) – из 7 по СА.
Итак, получили промежуточный вывод — ¬(a˄¬b). Вводим новое допущение:
- + a
- ¬a˅¬¬b – из 8 по О˄
- ¬¬b– из 9 и 10 по У⊃
- b – из 11 по У¬¬
- a⊃b – из 9 и 12 по В⊃
- (a⊃b)⊃¬(a˄¬b) – из 13 и 8 по В⊃
15.¬(a˄¬b)⊃(a⊃b) – из 13 и 8 по В⊃
- (a⊃b)≡¬(a˄¬b) – из 14 и 15 по В≡ ■
Только что мы строили натуральные выводы для логики высказываний. Но для логики высказываний существует разрешающая процедура – построение таблиц истинности. Для логики предикатов такой процедуры нет. Поэтому натуральные исчисления логики предикатов значительно актуальнее.
Для дальнейшей работы нам необходимо ввести несколько определений.
Терм (t) — предметная (индивидная) переменная или предметная (индивидная) константа в формуле. От простой переменной терм отличается тем, что фиксирует не абстрактную переменную в формуле, а конкретную константу (конкретный объект), либо предметную переменную (множество объектов определённого класса).
Свободное и связанное вхождение переменной в формулу. Свободной называется переменная, не находящаяся под действием кванторов (P(x) — «х» свободна, «х» имеет свободное вхождение в формулу). Связанной называется переменная под действием любого квантора (ƎxP(x) или ∀xP(x) — «х» связана, «х» имеет связанное вхождение в формулу).
Правила кванторов можно сформулировать на основе системы Уилларда Куайна KQ2 (системы Куайна — KQ1, KQ2 и KQ3 отличаются лишь формулировкой правил кванторов, главным образом В∀ и УƎ):
- ∀xP(x)⊃P(t) – схема удаления ∀(У∀)
- P(t)⊃ ƎхP(x) – схема введения Ǝ (ВƎ)
- P(t)⊃∀xP(x) — схема введения ∀ (В∀)
- ƎxP(x)⊃P(t) – схема удаления Ǝ (УƎ)
В другом написании:
У∀ | ∀xP(x) | ВƎ | P(t) | В∀ | P(t) | УƎ | ƎxP(x) |
P(t) | ƎхP(x) | ∀xP(x) | P(t) |
Для двух последних правил — В∀ и УƎ необходима оговорка. Переменные (термы), возникающие в результате применения этих правил, должны быть «ограниченными» (или «отмеченными») . Это означает, что для данных переменных повторное применение этих правил недопустимо. Иными словами, переменная не может быть отмечена (ограничена) более одного раза.
Поясним сказанное на примере. Предположим, надо решить теорему ƎxP(x)⊃∀xP(x).
- + ƎxP(x)
- P(x) из 1 по УƎ, х — ограничена
Иными словами, используя правила В∀ и УƎ мы ограничиваем переменную (в данном случае «х») и фиксируем это, написав «х — ограничена»
- ∀xP(x) из 2 по В∀, х — ограничен
Как видим, «х» ограничена два раза, что недопустимо. Следовательно, вывод неправильный.
К четырем правилам натурального вывода предикатов можно добавить еще два. Они не являются необходимыми, но в некоторых случаях могут оказаться весьма полезными:
- ¬∀xP(x)→Ǝx¬P(x) — правило отрицания ∀ (О∀)
- ¬ƎxP(x)→∀x¬P(x) — правило отрицания Ǝ (ОƎ)
О∀ | ¬∀xP(x) | ОƎ | ¬ƎxP(x) |
Ǝx¬P(x) | ∀x¬P(x) |
Попробуем использовать эти правила для решения всё той же задачи — ƎxP(x)⊃∀xP(x). Попробуем теперь решить эту задачу «от противного», чтобы создать противоречие. Предположим, что формула ƎxP(x)⊃∀xP(x) неверна.
- + ¬(ƎxP(x)⊃∀xP(x))
- ƎxP(x)∧¬∀xP(x) — из 1 по О⊃
- ƎxP(x) — из 2 по У∧
- ¬∀xP(x) — из 2 по У∧
- Ǝx¬P(x) — из 4 по О∀
- P(x) — из 3 по УƎ, х — ограничена
- ¬P(x) — из 5 по УƎ, х — ограничена
Мы опять пришли к повторному ограничению «х». Формула не доказана. Впрочем, она и не может быть доказана, поскольку неверна.
Чтобы закрепить навыки, попробуем решить задачу посложнее:
- + ¬(∀x(S(x)⊃P(x))∧∀x(P(x)⊃Q(x))⊃∀x(S(x)⊃Q(x)))
- (∀x(S(x)⊃P(x))∧∀x(P(x)⊃Q(x)))∧¬∀x(S(x)⊃Q(x)) — из 1 по О⊃
- ∀x(S(x)⊃P(x))∧∀x(P(x)⊃Q(x)) — из 2 по О∧
- ¬∀x(S(x)⊃Q(x)) — из 2 по О∧
- ∀x(S(x)⊃P(x)) — из 3 по О∧
- ∀x(P(x)⊃Q(x)) — из 3 по О∧
- S(x)⊃P(x) — из 5 по У∀
- P(x)⊃Q(x) — из 6 по У∀
- Ǝx¬(S(x)⊃Q(x)) — из 4 по О∀
Здесь необходимы пояснения, поскольку у студентов зачастую возникает непонимание: как в системе натурального вывода отрицаются простые суждения.
Дело в том, что до сих пор мы с вами отрицали простые суждения по очень простой формуле:
суждение | ↔ | его отрицание |
∀xS(x) | ↔ | ∃x¬S(x) |
∃xS(x) | ↔ | ∀x¬S(x) |
∃x¬S(x) | ↔ | ∀xS(x) |
∀x¬S(x) | ↔ | ∃xS(x) |
Однако теперь, в логике предикатов, мы стали использовать более подробную запись простых суждений. Если выражение «∀xS(x)» до сих пор означало для нас «Все x суть S», то теперь оно означает «Для всех x, если он S, то он и P».
Поясним. Выражение «Все люди млекопитающие» ранее мы записывали как «∀xS(x)». Теперь же мы то же выражение записываем как «∀x(S(x)⊃P(x))». Читаем: «Для всех x правомерно, что, если он человек, то он млекопитающее». Соответственно, выражение «Некоторые люди млекопитающие», которое мы обозначали как «∃xS(x)», теперь обозначается «∃x(S(x)∧P(x))» и читается соответственно – «Для некоторых x верно, что он человек и млекопитающее».
Последний абзац рекомендуем студентам перечитать несколько раз.
Мы с вами прекрасно знаем, как отрицаются простые суждения. Необходимо изменить квантор на противоположный и изменить качество суждения также на противоположное. С кванторами всё понятно: было Ǝ, стало — ∀; было ∀ — стало Ǝ. Но как поменять качество суждения? Как грамотно превратить утвердительное суждение в отрицательное и наоборот?
Предположим, мы отрицаем суждение «∀x(S(x)⊃P(x))». Первое, что приходит в голову, записать его отрицание так: «∃x¬(S(x)⊃P(x))». Но, с другой стороны, в частном суждении должна быть не импликация, а конъюнкция: «∃x(S(x)˄¬P(x))». Эквивалентны ли эти записи? Т.е. верно ли, что «∃x¬(S(x)⊃P(x))≡∃x(S(x)˄¬P(x))»?
На самом деле данные записи являются эквивалентными (основные эквивалентности вы можете посмотреть в приложении к данному учебному пособию). Поэтому,
- ¬(S(x)⊃Q(x)) — из 9 по УƎ — х ограничен
- S(x)∧¬Q(x) — из 10 по О⊃
- S(x) — из 11 по У∧
- ¬Q(x) — из 11 по У∧
- P(x) — из 7 и 12 по У⊃
- Q(x) — из 8 и 14 по У⊃
- Q(x)∧¬Q(x) из 15 и 13 по В∧
- ¬(∀x(S(x)⊃P(x))∧∀x(P(x)⊃Q(x))⊃∀x(S(x)⊃Q(x)))⊃(Q(x)∧
∧¬Q(x)) — из 1 и 16 по В⊃
- ∀x(S(x)⊃P(x))∧∀x(P(x)⊃Q(x))→∀x(S(x)⊃Q(x)) — из 17 по СА (сведение к абсурду). ■
Пункты 17 и 18 мы могли бы записать по-другому:
- (Q(x)∧¬Q(x))⊃¬(∀x(S(x)⊃P(x))∧∀x(P(x)⊃Q(x))→∀x(S(x)⊃Q(x))) — из 16 и 1 по В⊃
- ∀x(S(x)⊃P(x))∧∀x(P(x)⊃Q(x))⊃∀x(S(x)⊃Q(x)) — из 17 по ДОП (доказательство от противного). ■
Важно
Для частных суждений (с квантором ∃) свойства объекта выражаются через конъюнкцию «∧», например, ∃x(S(x)∧P(x)).
Соответственно, мы имеем запись суждений:
Проверим на истинность силлогизма:
Никто из студентов + не получает пенсию + |
Некоторые пенсионеры — — ворчливые старики — |
Некоторые ворчливые старики — не учатся в вузах + |
Переведем его на формальный язык логики:
∀x(S(x)⊃¬P(x)) |
∃x(P(x)∧Q(x)) |
∃x(Q(x)∧¬S(x)) |
Объединим посылки знаком конъюнкции, а заключение знаком импликации:
- + ¬(∀x(S(x)⊃¬P(x))∧∃x(P(x)∧Q(x))⊃∃x(Q(x)∧¬S(x)))
- ∀x(S(x)⊃¬P(x))∧∃x(P(x)∧Q(x))∧¬∃x(Q(x)∧¬S(x)) – из 1 по О⊃
- ∀x(S(x)⊃¬P(x)) – из 2 по У∧
- ∃x(P(x)∧Q(x)) – из 2 по У∧
- ¬∃x(Q(x)∧¬S(x)) – из 2 по У∧
- S(x)⊃¬P(x) – из 3 по У∀
- P(x)∧Q(x) – из 4 по У∃ х — ограничен
- ∀x(Q(x)⊃S(x)) – из 5 по О∃
- Q(x)⊃S(x) – из 8 по У∀
- P(x) – из 7 по У∧
- Q(x) — – из 7 по У∧
- S(x) – из 11 и 9 по У⊃
- ¬P(x) – из 6 и 12 по У⊃
- P(x)∧¬P(x) – из 13 и 10 по В∧
- (P(x)∧¬P(x))⊃¬(∀x(S(x)⊃¬P(x))∧∃x(P(x)∧Q(x))⊃∃x(Q(x)∧¬S(x))) – из 14 и 1 по В⊃
- ∀x(S(x)⊃¬P(x))∧∃x(P(x)∧Q(x))⊃∃x(Q(x)∧¬S(x)) – из 15 по ДОП. ■
Пробуем решить эту же формулу с помощью гипотез.
- + ∀x(S(x)⊃¬P(x))
- + ∃x(P(x)∧Q(x))
- S(x)⊃¬P(x) – из 1 по У∀
- P(x)∧Q(x) – из 2 по У∃ х — ограничен
- P(x) – из 4 по У∧
- Q(x) – из 4 по У∧
- ¬S(x) – из 3 и 5 по У⊃
- Q(x)∧¬S(x) – из 6 и 7 по В∧
- ∃x(Q(x)∧¬S(x)) — из 8 по В∃
- ∀x(S(x)⊃¬P(x))∧∃x(P(x)∧Q(x)) — из 1 и 2 по В∧
- ∀x(S(x)⊃¬P(x))∧∃x(P(x)∧Q(x))⊃∃x(Q(x)∧¬S(x)) — из 9 и 10 по В⊃. ■
Совет
В ряде случаев, когда в общей формуле мы встречаем выражение вида «a⊃b», мы можем предположить (ввести допущение), что существует «a». Из этого допущения по правилу удаления импликации, мы получаем «b» (a⊃b, a ⊧ b). Для подобных частных случаев мы вправе сформулировать своё собственное правило второго порядка: «a⊃b ⊧ a, b). |
Дополнительная информация
Вообще, схемой аксиом, может служить любая доказанная тождественно-истинная формула. При этом, аксиома служит «прототипом» бесконечного множества истинных формул, построенных по форме (схеме) этой аксиомы.
Возьмем, к примеру, закон утверждения консеквента – «B⊃(A⊃B)». Это тождественно-истинная формула (при желании, студент может её доказать). А это значит, что любая формула такого вида (такой схемы) также является тождественно-истинной. Поэтому, встретив в выводе формулу подобной схемы, доказывать её уже не имеет смысла. Можно просто сослаться на данную схему и принять истинность формулы данный схемы по аналогии.
Когда мы говорим, что аксиома служит «прототипом» бесконечного количества истинных формул, мы имеем ввиду, что схема «B⊃(A⊃B)» может быть выражена как «с⊃(a⊃с)», «d⊃(c⊃d)», «с˅b⊃(a⊃(с˅b))», «(d⊃(c⊃d))⊃(¬z⊃(d⊃(c⊃d))) и т.д.
Студент может самостоятельно добавлять схемы аксиом в свою систему исчислений. Для этого достаточно убедиться, что добавленная аксиома действительно является аксиомой (тождественно-истинной формулой). Кроме того, поскольку правила натурального вывода и правила аксиоматической системы исчислений не противоречат друг другу, читатель может смело использовать все известные ему правила одновременно.
Основными правилами аксиоматической системы исчисления предикатов остаются те же, что мы использовали в системе натурального вывода. Однако, меняются правила кванторов:
1. ∀xP(x) ⊧P(t) – схема удаления ∀ (У∀)
Пояснение: если каждый «х» имеет признак P, то признак P имеет и константа «t» (из множества «х»).
«Если все в группе ЮРДб хорошо знают логику, то и г-н Агафонов (из группы ЮРДб) тоже хорошо знает логику»
2. P(t) ⊧ƎхP(x) – схема введения Ǝ (ВƎ)
Пояснение: Если мы имеем константу «t», обладающую признаком P, то верно, что некоторые «x» (из множества, в которое входит «t») тоже обладают признаком P.
«Если г-н Агафонов из группы ЮРДб хорошо знает логику, следовательно, некоторые студенты ЮРДб хорошо знают логику» (если быть более точным, то «Если г-н Агафонов из группы ЮРДб хорошо знает логику, следовательно, существует хотя бы один студент из группы ЮРДб хорошо знающий логику»
3. ∀x(А⊃P(x))⊧(А⊃∀xP(х)) – схема введения ∀ в консеквент (В∀вК).
Пояснение: Если для всех «х» верно, что он имеет признак P при условии А, то при условии A признак P будет свойственен всем «х».
«Если все студенты хорошо успевают, то они получают стипендию → Если студенты хорошо успевают, то все они получают стипендию».
4. ∀x(P(x)⊃А)⊧(ƎхP(х)⊃А) – схема введения Ǝ в антецедент (ВƎвА).
Пояснение: если для всех «х» верно, что некий признак P ведет к результату A, то это верно и для некоторых «x».
«Если все студенты, хорошо учась, получают стипендию, следовательно, это верно и для некоторых студентов».
5. P(t)⊧∀xP(x) — правило обобщения (В∀), при условии, что терм «t» не был ранее связан квантором Ǝ и не является константой.
Формулы логики предикатов
В алгебре высказываний мы подробно изучили одно из важнейших ее понятий и инструментов — понятие формулы алгебры высказываний. Теперь наша задача состоит в том, чтобы определить и изучить соответствующее понятие в логике предикатов, а затем на его основе продемонстрировать, насколько тоньше и точнее язык и логика предикатов отражают процессы человеческого мышления, нежели это делают язык и логика высказываний.
Понятие формулы логики предикатов
Это понятие вводится аналогично понятию формулы алгебры высказываний. Сначала задается алфавит символов, из которых будут составляться формулы:
– предметные переменные: ;
– нульместные предикатные переменные: ;
– n-местные предикатные переменные с указанием числа свободных мест в них:
– символы логических операций: ;
– кванторы: ;
– вспомогательные символы: — скобки; — запятая.
Теперь дадим определение формулы логики предикатов, которое также носит индуктивный характер.
Определение 21.1 (формулы логики предикатов).
1) Каждая нульместная предикатная переменная есть формула;
2) если — n-местная предикатная переменная, то есть формула, в которой все предметные переменные свободны;
3) если — также формула. Свободные (связанные) предметные переменные в формуле те и только те, которые являются свободными (связанными) в — формулы и если предметные переменные, входящие одновременно в обе эти формулы, свободны в каждой из них, то выражения
также являются формулами. При этом предметные переменные, свободные (связанные) хотя бы в одной из формул , называются свободными (связанными) и в новых формулах;
5) если и также являются формулами, в которых переменная — элементарные формулы, а
являются составными формулами. При этом в первой составной формуле предметная переменная связана, а переменные — свободные. Во второй составной формуле свободна лишь переменная
Как и в алгебре высказываний, договоримся внешние скобки у формулы не писать, если только она не является частью более сложной формулы. Отметим кстати, что на основании пунктов 1, 3 и 4 сформулированного определения всякая формула алгебры высказываний будет также и формулой логики предикатов.
В формулах вида и формула областью действия квантора или , соответственно. Тогда ясно, что вхождение предметной переменной в формулу будет связанным, если эта переменная находится в области действия квантора по этой переменной.
Формулы, в которых нет свободных предметных переменных, называются замкнутыми, а формулы, содержащие свободные предметные переменные, — открытыми. Так, все приведенные выше формулы логики предикатов, кроме формулы , являются открытыми.
Примеры замкнутых формул:
Классификация формул логики предикатов
Если в формулу логики предикатов вместо каждой предикатной переменной подставить конкретный предикат, определенный на некотором выбранном множестве
Пример 21.2. Дадим интерпретацию формуле . В качестве множества подставим конкретный предикат, определенный на «». Тогда исходная формула превратится в следующее (очевидно, ложное) высказывание () — «у каждого мужчины есть сын». Этой же формуле можно дать и другую интерпретацию. Возьмем в качестве подставим предикат «», определенный на . Тогда исходная формула превратится в (очевидно, истинное) высказывание — «Для каждого натурального числа существует большее по сравнению с ним натуральное число».
Пример 21.3. В предыдущем примере была рассмотрена интерпретация замкнутой формулы. Дадим интерпретацию открытой формуле . В качестве множества и подставим трехместные предикаты «» и «» соответственно, а вместо нульместного предиката «. Тогда данная формула превратится в двухместный предикат (от предметных переменных ):
Посмотрим, в какие высказывания может превращаться данный предикат при подстановке вместо его переменных конкретных предметов (чисел) из превращается в истинное высказывание при любой подстановке вместо его предметных переменных натуральных чисел. В самом деле, для натуральных тип получаем высказывание
Одноместный предикат (зависит от , выполним, потому что всегда можно найти такое натуральное число , что и , т. е. высказывания будут ложны, а значит, высказывание истинно. Поэтому высказывание
в которое превращается данный предикат, ложно. Итак, исходная открытая формула логики предикатов превращена в тождественно ложный предикат. Нетрудно понять, что если вместо предикатных переменных и подставить только что рассмотренные предикаты, а вместо нульместной предикатной переменной
Сформулируем классификационные определения для формул логики предикатов.
Пример 21.7. Покажем, что формула является противоречием, т.е. тождественно ложной. В самом деле, допустим противное: на некотором множестве , такой, что данная формула превращается в выполнимый предикат (от . Последнее означает: найдется предмет истинно. Истинность конъюнкции дает истинность высказываний и . Из истинности первого следует, что высказывание ложно, а из истинности второго — что предикат тождественно истинный и, значит, для любого предмета из истинно. Получаем противоречие, исключающее предположение о непротиворечивости исходной формулы. Следовательно, она тождественно ложна.
1.6. Тождественно-истинные и тождественно-ложные формулы. Проблема разрешимости
Определение 1.3. Формула называется тождественно-истинной (тавтологией), если для любых наборов переменных она принимает значение И.
Определение 1.4. Формула называется тождественно-ложной, если для любых наборов переменных она принимает значение Л.
Определение 1.5. Формула называется выполнимой, если для некоторых наборов переменных она принимает значение И.
Проблема разрешимости для логики высказываний заключается в том, чтобы установить, является ли произвольная формула тождественно-истинной.
Теорема 1.1. Формула является тождественно-истинной тогда и только тогда, когда в ее КНФ в любую из элементарных дизъюнкций одновременно входят какая-либо переменная и ее отрицание.
Теорема 1.2. Формула является тождественно-ложной тогда и только тогда, когда в ее ДНФ в любую из элементарных конъюнкций одновременно входят какая-либо переменная и ее отрицание.
Следовательно, приведя формулу равносильными преобразованиями к КНФ, можно установить, является ли она тождественно-истинной, а приведя ее к ДНФ, можно установить, является ли она тождественно-ложной.
Доказать, что формула F = (АB) ((C Ú А) (C Ú B)) является тождественно-истинной.
Последовательно применяя равносильные преобразования, приведем нашу формулу к КНФ:
(АB) ((CÚА) (CÚB)) (АB)Ú ((CА) (CÚB)) (А&B) Ú (CÚА) Ú (C Ú B)(А&B) Ú (C&А) Ú (CÚB) (А ÚC)& (АÚ А) &(BÚC) &(BÚА) Ú (CÚB) (АÚC)&(BÚC)&(BÚА)Ú (CÚB) (АÚCÚCÚB)&(BÚCÚCÚB)&(BÚАÚCÚB).
В первую дизъюнкцию входят C и C. Во вторую – B и B, C и C. в третью – B и B. Следовательно, на основании теоремы 1.1 можно утверждать, что исходная формула является тождественно-истинной.
Так как всякой формуле соответствует таблица истинности, то тождественная истинность или тождественная ложность формулы может быть установлена двумя путями:
1) приведением с помощью равносильных преобразований к КНФ или ДНФ;
2) составлением таблицы истинности.
Установить, является ли тождественно-истинной данная формула логики высказываний: F(A, B) = (А&(АB)) B.
1) Последовательно применяя равносильные преобразования, приведем нашу формулу к КНФ:
(А&(АB)) B (А&(АÚB) B (А&(АÚB) B АÚ(АÚB)ÚB АÚ(А&B)ÚB (АÚB)ÚА&B (АÚBÚА)&(АÚBÚB).
В первую дизъюнкцию входят A и A. Во вторую – B и B, поэтому формула является тождественно истинной, F(A, B) И.
2) Составим таблицу истинности F(A, B) (таблица 1.7):