Множество простых правильно построенных формул«п.п.ф.», а также множество комбинированных правильно построенных формул «п.п.ф.» является бесконечным.

Формула, правильно составленная из пропозициональных переменных и нескольких символов логических связок называется комбинированной:

((((А→ D)→ (В→ C))& (AVB))→ ( DVC)).

Простые и сложные формулы логики высказываний называются пропозициональными функциями, поскольку только после подстановки в них объектов предметной области языка логики высказываний они преобразуются в конкретные высказывания.

Правило подстановки.

1) Пропозициональные переменные разрешается переименовывать в простых и сложных формулах:

например, А можно заменить на В (А/В).

Сложную формулу, например, формулу (А → ( В → А)), можно

переименовать на формулу - (p → ( q → p)).

Можно также делать подстановку вместо простых формул типа(p, q) сложных формул типа (rvt) и (lvm)..

Пример. Если р/(rvt), иq/(lvm ), то получаем формулу вида( rvt → ( lvm → rvt ).

2) При интерпретации формул логики высказываний вместо символов пропозициональных переменных и символов логических связок разрешается подстановка языковых выражений естественного языка или языка дисциплины.

Пример. Формула « А& В» в результате подстановки вместо «А» предложения «Светит солнце». И подстановки вместо «В» предложения - «Идет дождь». И замены «^» на «и» получается предложение «Солнце светит и идет дождь».

Правила вывода. Они делятся на основные и производные.

1) Основные правила вывода при аксиоматическом построении логики высказываний предназначены,

Во-первых, для вывода

Из аксиом логики высказываний логических формул (теорем) языка этой логики.

И, во-вторых, для вывода или доказательства других формул из аксиом и ранее выведенных, доказанных теорем.

В логики высказываний правила вывода отождествляются с понятием доказательства и представлены в двух видах.

В виде схем вывода и логических формул.

Многие из этих правил вывода были известны уже стоикам четвертого века до нашей эры:

Например, им было, известно, правило отделения, как схема вывода: «Если из А следует В. И имеет место быть - А, то следует признать, что имеет место быть – В».

Другое название этого правила, идущее от средневековой логики, - модус ронес. Правило это позволяет от утверждения условного суждения. И утверждения его основания (антецедента, в данном случае-А) перейти к утверждению его следствия (консеквента, в данном случае - В).

Это правило гарантирует вывод истинного следствия из истинных посылок.

В логике высказываний правило отделения является основным правилом, как схемой вывода и одновременно как логической формулой ((А → В) & А) → В),, представляющей закон логики.

Производные правила. Эти правила расширяют и упрощают доказательства с помощью основных правил.

Что, собственно, новое внесла логика высказываний классической логики в понимание доказательства и вывода?

Во-первых, с созданием аксиоматического построения классической логики высказываний произошел крутой поворот в понимания доказательства в аксиоматических дедуктивных языках логики, математики и программирования.

Во-вторых, появилась символическая или математическая логика, основанная на таком важном логическом методе дедуктивного доказательства, как теорема дедукции.

В- третьих, аксиоматическое построение классической логики высказываний способствовало развитию методов формализации и методологии развития исследования неклассической логики.

Остановимся на теореме дедукции. Термин принадлежит выдающемуся математику Д.Гильберту, а ее использование методологии доказательства формализованных языках было представлено рядом логиков 30-ых годов прошлого века.

Теорема дедукции. С.82.

Содержание теоремы дедукции в качестве метода допущений доказательствах в аксиоматических дедуктивных языках (теориях) сводится к следующему:

Для доказательства сложной формулы вида (если А, то В), где А-антецедент, основание, а В – консеквент, вывести из А его следствие В по правилам вывода данного языка (теории).

2)В символической записи теорема дедукции для аксиоматических дедуктивных языков логики с правилом отделения имеет вид:

«Если из множества (Г) и формулы ( а), доказанной в данном языке, можно доказать, что формула (в) есть следствием формулы (а), то формула ( а→ в ) также принадлежит множеству (Г)». Здесь (Г)- множество аксиом, а также формул (теорем), доказанных в данном языке с применением его правил вывода.

В случае, когда в языке логике высказываний нет аксиом, множество (Г) будет состоять из формул (теорем), доказанных с применением основных и производных правил вывода языка логики высказываний.

Производные правила вывода существенно сокращают длину доказательства, но без них можно обойтись, используя только основные правила вывода.

Пример дедуктивного доказательства на основе теоремы дедукции.

Доказать - ((( а→ в)→ ( в→ с )) → ( а→ с)). Используя пункт (1) теоремы дедукции, выделим последовательность антецедентов и консеквентов в этой формуле ((( а→ в)→ ( в→ с ))

- антецедент для формулы ( а→ с); ( а→ в) );

- антецедент для формулы ( в→ с);

а)- антецедент для формулы (с).

Получаем последовательность формул для доказательства формулы (с) из формулы (а) по правилу отделения.

1(а→ в).

2. (в→ с).

3.(а).

4. (в) - правило отделения (1, 3)= ((а→ в), а)→ в.

5.(с) - правило отделения (3, 4) = ((в→ с), в)→ с.

Применяя теорему дедукции к этой последовательности снизу верх, можно восстановить структуру доказываемой формулы.

А что такое прямое и косвенное доказательства в классической логике высказываний?

Приведенное выше доказательство называется прямым. В косвенном доказательстве доказывается не сама формула, которую надо доказать, а ее отрицание. В этом случае доказательство сводиться к выводу противоречия в виде формулы (Р& не-Р).

За логическую основу косвенного доказательства берется закон Клавия, логика 16 века, который выявил его применение в доказательстве Евклидом одной из теорем, предполагая, что она изначально является ложной.

Два вида формулы этого закона:

1. ( 7Р→ Р) → Р).

2. ((Р→ 7Р) → 7Р).

3. (7Р→ (Q& 7Q) → Р).

4. (( Р→ (Q& 7Q) → 7Р).

Основной смысл этого закона: Если изначально признаваемого истинным какого-то утверждения по правилам логики выводится противоречие или отрицание этого утверждения, то следует считать, что истинным является не оно само, а его отрицание.

Косвенные доказательства эффективно используются в натуральном исчислении высказываний классической логики.

Чем отличается натуральное исчисление высказываний от аксиоматически-дедуктивного исчисления высказываний?

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

Структура языка натурального исчисления высказываний совпадает со структурой аксиоматически-дедуктивного исчисления высказываний, единственным различием является: отсутствие изначально заданного списка аксиом без предварительного доказательства. Но зато в нем есть множество правил ввода и исключения всех логических связок и правил замены равнообъемных формул, установленных по таблицам истинности.

Пример правил ввода и исключения в доказательствах: Если А-истинно и В- истинно, то в доказательство разрешатся включить истинную формулу А& В.

Правило исключения этой логической связки: если в доказательстве выведена формулу А& В, то в доказательстве можно. использовать А и В по отдельности.

Другой пример, исключение дизъюнкции в доказательстве. Е

Сли доказана формула (АvВ) и доказано, что имеет место (7В), то тогда следует признать доказанной формулу (А).

Пример косвенного доказательства в натуральном исчислении высказываний.

Нужно доказать закон исключенного третьего (Аv7А).

Предположим, что он ложен, тогда он преобразуется в формулу с отрицанием:

Неверно, (Аv7А).

2. Применим к этой формуле закон де Моргана для логической дизъюнкции и закон двойного отрицания:

Получаем формулу (7А& А)

Исключая конъюнкцию из этой формулы,

Получаем доказанную формулу(А) и доказанную формулу (7А) т.е. противоречие.

4. Следовательно. Из формулы ((неверно, что (Аv7А )) следует( → )формула-(7А& А).

Значит, по закону Клавия, наше косвенное допущение об истинности формулы (неверно, что (Аv7А)) является ложным.

Законы де Моргана (англ. логика 19 века А. де Моргана были известны средние века, но за символической их записью закрепилась имя этого логика):

Отрицание дизъюнкции

«7(А vВ)»= «(7А & 7В)».

2) отрицание конъюнкции «7(А & В)»= «(7А v7В)».

Закон двойного отрицания был известен античным логикам:

« 77Р→ Р».

Пример языка исчисления предикатов классической логики.

По своему логическому существу исчислениях предикатов - это достаточно глубокий и эффективный формализованный язык ( языки) логики, позволяющий исследовать широкий класс рассуждений, используемый в различных сферах деятельности человека.

В точном смысле исчислении предикатов – это логический аппарат, с помощью которого сформулированы логические законы и правила, используемые в рассуждениях в разнообразных видах рациональной деятельности человека.

⇐ Предыдущая891011121314151617Следующая ⇒

Поделиться: