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

Пусть даны формулы F₁, F₂,…F_n и формула G.

Тогда формула G является логическим следствием формул F₁, F₂,…F_n,

если и только если формула вида ( F₁ & F₂ … & F_n  G ) является общезначимой

и наоборот.

Доказательство:

I.

Предположим, что G является логическим следствием формул F₁, F₂,…F_n.

Пусть I – произвольная интерпретация для F₁, F₂,…F_n.

Если все F₁, F₂,…F_n истинны в I, то по определению логического следствия G тоже истинна в I.

Тогда формула ( F₁ & F₂ … & F_n  G ) истинна в I по определению операции импликации ( t  t = t ).

С другой стороны, если не все F₁, F₂,…F_n истинны в I, то есть хотя бы одна из них ложна в I,

тогда формула ( F₁ & F₂ … & F_n  G ) истинна в I по определению операции импликации ( f  f = t или f  t = t ).

Таким образом, формула ( F₁ & F₂ … & F_n  G ) истинна для всякой интерпретации, то есть она является общезначимой.

II.

Пусть ( F₁ & F₂ … & F_n  G ) – общезначимая формула.

Тогда для всякой интерпретации I, если формула F₁ & F₂ … & F_n истинна в I, то G должна быть истинна в I по определению операции импликации. То есть формула G является логическим следствием формул F₁, F₂,…F_n, что и требовалось доказать.

7. Следствие

Формула G является логическим следствием формул F₁, F₂,…F_n, если и только если формула вида ( F₁ & F₂ … & F_n &  G ) противоречива.

Доказательство:

По теореме о дедукции G является логическим следствием формул F₁, F₂,…F_n, если и только если формула ( F₁ & F₂ … & F_n  G ) общезначима, то есть её отрицание противоречиво:

 ( F₁ & F₂ … & F_n  G ) 

 (  ( F₁ & F₂ … & F_n )  G ) 

 (  ( F₁ & F₂ … & F_n ) ) & G 

F₁ & F₂ … & F_n  G

Что и требовалось доказать.

8. Выводимость

Если существует правило вывода R, то говорят, что G непосредственно выводима из формул F₁, F₂, …F_n по правилу вывода R. Обычно этот факт записывают следующим образом:

F₁, F₂, …F_n

 R

G

Если формула G является логическим следствием формул F₁, F₂, …F_n,

то формула вида ( F₁ & F₂ … & F_n  G ) называется теоремой,

формулы F₁, F₂, …F_n – посылками теоремы,

G – заключением теоремы.

9. Выводы

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

Атомарная формула в логике высказываний рассматривается как единое целое, её структура никак не анализируется.

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

2. Логика предикатов

Рассмотрим следующее рассуждение:

Все люди смертны

Сократ – человек

Следовательно, Сократ смертен

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

P: Все люди смертны

Q: Сократ – человек

R: Сократ – смертен

Используя соответствующие связки, можно написать формулу

( P & Q )  R

Эта формула необщезначима, следовательно, невозможно установить, что R является логическим следствием P и Q. Таким образом, логика высказываний не позволяет корректно выразить рассуждение. Однако ясно, что высказывание имеет внутреннюю структуру, то есть значение высказывания является функцией значений его компонент.

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

Все люди смертны

содержит внутреннюю импликацию. Его можно переписать следующим образом:

Быть человеком –

значит быть смертным.

Эта переформулировка не вполне удовлетворительна: такое впечатление, что ей соответствует формула типа ( A  B ). Это не так: слово «быть» устанавливает связь между посылкой A и следствием B условного наклонения. Заметим, что слово Сократ устанавливает аналогичную связь между строками

Сократ – человек

Сократ – смертен

Между тем эти случаи различны:

• слово «быть» означает какой-то, пока не определённый, объект некоторой предметной области,

• (тогда как) Сократ означает конкретный объект этой области.

По аналогии с языками программирования математики говорят, что «быть» – это переменная ( обозначим её через X ), тогда как Сократ – константа.

Для того чтобы увидеть реальную структуру предложенного текста перепишем его следующим образом:

Для всех X, если X является человеком, % импликация

то X является смертным, % неявная конъюнкция

Сократ является человеком,

(следовательно) Сократ является смертным. % импликация

В дополнение к высказываниям и связкам (неявной конъюнкции, импликации «если …, то», импликации «следовательно») появились новые компоненты:

Для всех,

X,

Сократ,

является человеком,

является смертным.

Выделение слова является могло бы показаться интересным, но в данном контексте это не подтверждается, так как оно может слишком легко исчезнуть. Оборот речи «является альтруистом» можно заменить на «заботится о других», тогда как «является смертным» приблизительно означает «умрёт». Такие обороты речи служат примерами предикатных констант (имён предикатов). Предикатная константа не меняет своего значения истинности. Она лишь связана с подходящим числом аргументов или параметров, называемых термами. Это число (арность) зависит только от рассматриваемой предикатной константы. Предикатная константа вместе с подходящим числом термов называется предикатом.

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

Следет заметить, что отрицанием выражения Для всех X, А будет выражение Существует ( хотя бы один ) X,  А. Областью действия каждого квантора является формула, перед которой он стоит.

Теперь можно формализовать рассуждения.