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

Если \alpha, \beta и \gamma являются выражениями пропозиционального исчисления, то можно вывести следующие техники дедукции из основ:

Правило Предположения (Pre)

Самое простое правило дедукции из всех — это правило предположения. Оно получается непосредственно при применении обратного теоремы дедукции к теореме \vdash(\alpha\rightarrow\alpha). Если это звучит для вас как загадочный язык, все, что вам нужно знать, находится здесь.

\{\alpha\}\vdash \alpha

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

Гипотетический Силлогизм (SH)

Гипотетический силлогизм, или транзитивность импликации, является своего рода эволюцией модус поненс. Его формулировка следующая:

\{(\alpha\rightarrow\beta), (\beta\rightarrow\gamma)\}\vdash (\alpha\rightarrow\gamma)

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

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

Следовательно \{\alpha,(\alpha\rightarrow\beta),(\beta\rightarrow\gamma)\}\vdash\gamma

Наконец, применяя теорему дедукции к этому последнему выражению, мы получаем:

\{(\alpha\rightarrow\beta),(\beta\rightarrow\gamma)\}\vdash(\alpha\rightarrow \gamma)

Еще один способ получить доказательство этого правила — рассуждать исходя из дедукций, строя через предположение и монотонность. Рассмотрите следующее рассуждение исходя из дедукций:

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

Эквивалентности Двойного Отрицания (DN)

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

\alpha\dashv\vdash\neg\neg\alpha

Теперь посмотрим доказательство:

Следовательно \{\neg\neg \alpha \} \vdash \alpha

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

\{\neg\neg \neg \alpha \} \vdash \neg \alpha

И на основе этого составим доказательство в другом направлении:

Следовательно \{\alpha \} \vdash \neg\neg \alpha

Наконец, из этих двух доказательств следует, что \alpha \dashv\vdash \neg\neg \alpha .

Эквивалентность Контрапозиции Импликации (CpI)

Это соответствует следующим эквивалентностям

(\alpha \rightarrow \beta) \dashv\vdash (\neg\beta \rightarrow \neg\alpha)

(\neg\alpha\rightarrow\beta)\dashv\vdash (\neg\beta\rightarrow\alpha)

(\alpha\rightarrow\neg\beta) \dashv\vdash (\beta\rightarrow\neg\alpha)

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

С одной стороны, оно непосредственно следует из третьей аксиомы

Таким образом, \{(\neg\beta\rightarrow \neg\alpha)\}\vdash (\alpha \rightarrow \beta)

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

Таким образом, \{(\alpha \rightarrow \beta)\}\vdash (\neg \beta \rightarrow \neg \alpha )

Таким образом, из двух предыдущих рассуждений следует

(\alpha \rightarrow \beta) \dashv\vdash (\neg \beta \rightarrow \neg \alpha )

Чтобы доказать второе, можно сделать следующие два рассуждения:

Таким образом, \{(\neg\alpha \rightarrow \beta)\} \vdash(\neg\beta \rightarrow \alpha)

Теперь нужно сделать доказательство в обратном направлении. Мы можем сделать это через следующее рассуждение:

Таким образом, \{(\neg\beta\rightarrow\alpha)\}\vdash (\neg\alpha \rightarrow \beta)

Наконец, из этих двух рассуждений следует, что (\neg\beta\rightarrow\alpha) \dashv \vdash (\neg\alpha \rightarrow \beta) , что и требовалось доказать.

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