Существует три обязательных правила вывода, входящих вмножество B в исчислении высказываний:
1. Все аксиомы выводимы.
2. Правило одновременной подстановки: если некоторая тавтология U содержит атом P, то одновременная замена всех вхождений атома P в U на любую формулу Q приводит к порождению тавтологии.
3. Modus Ponens (заключение): если P – тавтология, и P® Q, то Q – тавтология.
Часто необходимо преобразовывать формулы из одной формы в другую. Поэтому, кроме аксиом и правил вывода необходимо иметь набор эквивалентных формул (законов), которые позволяют производить преобразования формул:
1. P « Q = P ® Q Щ Q ® P;
2. P ® Q = Ш P Ъ Q;
3. Коммуникативные законы: P Ъ Q = Q Ъ P; P Щ Q = Q Щ P;
Можно доказать следующие дополнительные правила вывода:
Утверждение 1.
Если P - тавтология, то Q ® P – тавтология.
Доказательство.
Доказательство следует из аксиомы 1 классической системы аксиом и правила вывода 3.
По аксиоме 1 P ®( Q ® P), тогда, если P – тавтология, то по правилу Modus Ponens Q ® P – тоже тавтология.
Утверждение 2.
Свойство транзитивности отношения следования: если P® Q, Q® R – тавтологии, то P® R – тавтология.
Доказательство.
Эквивалентная формулировка утверждения 2 заключается в том, что формула (((P® Q) Щ (Q® R)) ®(P® R)) является тавтологией. Воспользуемся законами эквивалентных преобразований исчисления высказываний:
(((P® Q) Щ (Q® R)) ®(P® R)) «
Ш ((ШPЪ Q) Щ (ШQЪ R)) Ъ (ШPЪ R) «
((PЩ ШQ) Ъ (Q Щ ШR)) Ъ (ШP Ъ R) «
((PЪ Ш P) Щ (ШQ Ъ Ш P)) Ъ ((Q Ъ R) Щ (ШR Ъ R)) «
((И Щ (ШQ Ъ Ш P)) Ъ ((Q Ъ R) Щ И)) «
ШQ Ъ Ш P Ъ Q Ъ R «
И Ъ Ш P Ъ Q « И.
Утверждение 3.
Теорема дедукции: необходимым и достаточным условием выводимости Q из гипотез R, P является выводимость P® Q из R. Данную теорему можно записать следующим образом: R, P ъ-- Q « R ъ-- (P® Q).
Термин «первого порядка» означает, что в этой теории кванторы допускаются только по переменным и не допускаются по функциональным и предикатным символам. Кроме того, запрещены предикаты, которые в качестве своих аргументов имеют другие предикаты.
В логике высказываний атом рассматривается как единое целое, его структура и состав не анализируется. Однако, есть много умозаключений, которые не могут быть представлены таким простым способом. Например, рассмотрим следующее умозаключение:
Каждый человек смертен.
Так как Конфуций человек, то он смертен.
Приведенное рассуждение интуитивно корректно, однако, если мы введем обозначения:
P: Каждый человек смертен,
Q: Конфуций – человек,
R: Конфуций смертен,
то R не есть логическое следствие P и Q в рамках логики высказываний.
В логике предикатов первого порядка по сравнению с логикой высказываний имеет еще три логических понятия: термы, предикаты и кванторы.
Множество T базовых элементов исчисления предикатов включает в себя следующие символы:
1. Константы – это обычно строчные буквы a, b, c… или осмысленные имена объектов;
2. Переменные – это обычно строчные буквы x, y, z, …, возможно с индексами;
3. Функции – это обычно строчные буквы f, g, h,… или осмысленные слова из строчных букв;
4. Предикаты – это обычно прописные буквы P, Q, R … или осмысленные слова из прописных букв;
Всякая функция или предикатный символ имеет определенное число аргументов. Если функция f имеет n аргументов, то f называется n- местной функцией. Аналогично, если предикат P имеет n аргументов, то P называется n- местным предикатом.
Определение 6. Термы определяются рекурсивно следующим образом:
· Константа есть терм;
· Переменная есть терм;
· Если f есть n- местная функция и t1, t2,…,tn – термы, то f (t1, t2,…,tn) – терм;
· Никаких термов, кроме порожденных применением указанных выше правил, нет.
Определение 7. Предикат P(t1, t2,…,tn) есть логическая функция, определенная на множестве термов t1, t2,…,tn, при фиксированных значениях которых она превращается в высказывания со значением истина (И) или ложь(Л).
Определение 8. Если P – n- местный предикат и t1, t2,…,tn – термы, то P(t1, t2,…,tn) – атом.
Для построения формул в исчислении предикатов используются пять логических связок и два квантора: " - всеобщности и $- существования. Если x – переменная, то ("x) читается как «для всех x», «для каждого x», «для любого x», тогда как ($x) читается как « существует x», «для некоторых x», «по крайней мере, для одного x».
Пример 1: запишем следующие утверждения:
1. Каждое рациональное число есть вещественное число.
2. Существует число, которое является простым.
3. Для каждого числа x существует такое число y , что x<y.
Обозначим «x есть простое число» через P(x), «x есть рациональное число» через Q(x), «x есть вещественное число» через R(x) и «x меньше y» через МЕНЬШЕ (x, y).
Тогда указанные выше утверждения могут быть записаны соответственно выражениями:
1. ("x) (Q(x)® R(x)),
2. ($x) P(x),
3. ("x) ($y) МЕНЬШЕ (x, y).
Каждое из выражений 1, 2, 3 называется формулой. Прежде чем дать формальное определение формулы в логике предикатов, следует установить различие между связанными переменными и свободными переменными и определить область действия квантора, входящего в формулу, как ту формулу, к которой этот квантор применяется. Так, область действия квантора существования в выражении 3 есть МЕНЬШЕ (x, y), а область действия квантора всеобщности в выражении 3 есть ($y) МЕНЬШЕ (x, y).
Определение 9. Вхождение переменной x в формулу F называется связанным тогда и только тогда, когда оно совпадает с вхождением в квантор ("xF) или ($yF). Формула, к которой применяется квантор по данной переменной, называется областью действия этого квантора. Вхождение переменной в формулу свободно тогда и только тогда, когда оно не находится в области действия какого-либо квантора. Формула, не содержащая свободных переменных, называется замкнутой и представляет собой высказывание.
Пример2.
P(x, y) Щ R(z)® ("x)(R(x) Щ Q(y)). В этом примере первое вхождение переменной x является свободным, второе – связанным, первое вхождение переменной y является свободным, второе – связанным, единственное вхождение переменной z является свободным.
Отметим, что переменная в формуле может быть свободной и связанной одновременно.
