Тема 5. Формализация доказательств в исчислении высказываний

Изучив материалы темы, Вы сможете:

- сформулировать теорему дедукции для логики высказываний;

- понять разницу между прямым и непрямым способом аргументации;

- дать определение понятию «истинностная функция»;

- привести доказательство логической корректности теоремы дедукции;

- указать функционально полные наборы функций;

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

Логика высказываний – это логическая теория, язык которой содержит один тип нелогических символов – пропозициональные переменные (замещают простые высказывания естественного языка), а также один тип логических символов – пропозициональные связки (~‚→‚v‚ &‚↔‚ ↮).

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

Зная значения А и В, можно однозначно установить значения выражений: Α&B‚ ΑvB‚ A→Β‚ A↔Β‚ ~Α‚ Α↮Β. Это позволяет рассматривать данные символы как знаки функций особого типа: возможными аргументами и значениями этих функций являются объекты «истина» и «ложь». Такие функции называют функциями истинности, а пропозициональные связки, которые служат знаками этих функций, – истинностно-функциональными.

Существует бесконечное число функций истинности, хотя для каждого n число n-местных функций истинности (функций от n аргументов) конечно и равно . Например, количество одноместных функций – 4, двухместных – 16, трёхместных – 256.

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

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

Примером такой функционально полной системы является множество функций, представленных связками ~‚→‚v‚ &‚↔‚ ↮. Например, логический смысл высказывания вида (A↔Β) равносилен смыслу выражения (A→Β)&(A→Β). Данные выражения принимают значение «истина» в одних и тех же случаях: 1) когда А и В истинны, 2) когда А и В ложны. Таким образом, функция эквиваленции выразима посредством функций конъюнкции и импликации.

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

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

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

A→(BvA)

Вместо А можно подставить (ΑvB) и получить следующую формулу

(ΑvΒ)→(Βv(AvΒ))

Если формула, в которую производится подстановка, является истинной, то и формула, получающаяся в результате произведённой подстановки, также будет истинной.

Большое значение в формализации доказательств в исчислении высказываний имеют тождественно-истинные формулы или законы логики. Законом классической логики высказываний является формула, принимающая значение «истина» при любых наборах значений входящих в неё пропозициональных переменных. Определить является ли произвольное высказывание естественного языка логическим истинным можно следующим образом: выразить логическую форму данного высказывания в языке логики высказываний и построить таблицу истинности для полученной формулы. Если во всех строках таблицы истинности формула примет значение «истина», то исходное высказывание является логически истинным относительно данной теории. Подробнее о таблицах истинности и других способах определить является ли формула логики высказываний тождественно-истинной можно узнать из темы 8.

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

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

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

Предположим, что целью основного рассуждения является обоснование некоторого тезиса А из некоторого множества аргументовГ. В ряде случаев решение данной задачи сводят к решению подзадач – к построению одного или нескольких вспомогательных рассуждений: к выведению высказывания из множества высказываний ,к выведению из ,…, к выведению из . Если указанные подзадачи решены, то заключают о достижении основной цели рассуждения – о получении А из Г. При этом переходе и используют непрямой способ аргументации.

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

Из выведено

Из выведено

…………………….

…………………….

Из выведено

Из Г выведено А

Непрямой способ аргументации является корректным, если и только если он гарантирует «сохранение» логического следования при переходе от вспомогательных рассуждений к основному, то есть обеспечивает наличие логического следования А из Г в том случае, когда следует из , следует из ,…, следует из .

Одним из видов непрямых способов аргументации является рассуждение по правилу дедукции. Данный способ аргументации применяется в том случае, когда целью основного рассуждения является обоснование посредством некоторого множества аргументов Г такого тезиса, который представляет собой импликативное высказывание A→B. В этом случае можно осуществить следующее вспомогательное рассуждение: принять в качестве допущения антецедент А данного импликативного высказывания, а затем вывести из Г и А его консеквент В. При решении указанной подзадачи заключают, что основной тезис A→B обоснован посредством Г.

Пример содержательного рассуждения по правилу дедукции.

«Докажем, что если число оканчивается на 0 и сумма его цифр кратна 3, то это число кратно 15. Допустим, что данное число оканчивается на 0 и сумма его цифр кратна 3. Известно, что если число оканчивается на 0, то оно кратно 5. Поэтому наше число кратно 5, ведь, согласно допущению, оно оканчивается на 0. Известно также, что если сумма цифр числа кратна 3, то и само это число кратно 3. Поэтому наше число кратно 3, ведь, согласно допущению, сумма его цифр кратна 3. Итак, наше число кратно 5 и 3. Но если число кратно 5 и 3, то оно кратно 15. Следовательно, наше число кратно 15. Таким образом, если число оканчивается на 0 и сумма его цифр кратна 3, то это число кратно 15».

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

«Если число оканчивается на 0 и сумма его цифр кратна 3, то это число кратно 15».

В процессе рассуждения использованы следующие аргументы:

(а) «если число оканчивается на 0, то это число кратно 5»,

(б) «если сумма цифр числа кратна 3, то и само это число кратно 3»,

(в) «если число кратно 5 и 3, то оно кратно 15».

В качестве допущения в рассуждении принимается антецедент обосновываемого тезиса:

(г) «число оканчивается на 0 и сумма его цифр кратна 3».

Далее из допущения (г) и аргументов (а) – (в) посредством цепочки умозаключений выводится консеквент тезиса:

(д) «данное число кратно 15».

Затем, применяя метод рассуждения по правилу дедукции, заключаем, что наш импликативный тезис обоснован посредством аргументов (а) – (в).

Рассуждение по правилу дедукции зафиксировано в теореме дедукции.

Теорема дедукции – теорема, которая гласит: если из посылок Г, А выводима формула В, то только лишь из посылки Г будет выводима формула A→B. Символически это можно записать так:

Г , А├ В

Г ├ (A→B)

Где греческая буква Г («гамма») обозначает произвольную конечную последовательность формул, А и В – какие-то высказывания, ├ – знак выводимости, знак → – союз «если…, то…», запятая в верхней формуле – содержательное «и».

Можно привести доказательство логической корректности этой теоремы, то есть показать, что в случае наличия логического следования вида Г, А├ В имеет место логическое следование вида Г ├ (A→B).

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

(1) Пусть Г, А├ В.

Согласно определению логического следования, это означает:

(2) не существует такой интерпретации пропозициональных переменных, при которой все формулы из Г истинны, А – истинна, а В – ложна.

Согласно условиям ложности импликативных формул :

(3) выражение «А истинно, а В ложно» равносильно выражению «A→B ложно».

Осуществим замену выражения «А истинно, а В ложно» в составе (2) на равносильное ему «A→B ложно».

(4) Не существует интерпретации, при которой все формулы из Г истинны, а A→B ложна.

Снова используем определение логического следования:

(5) Г ├ (A→B).

Доказательство завершено.

Контрольные вопросы:

1. Что такое пропозициональные переменные?

2. Какие виды пропозициональных связок Вы знаете?

3. Сформулируйте теорему дедукции для исчисления высказываний.

4. Какие наборы истинностных функций называются функционально полными?

5. Что такое непрямой способ аргументации?

6. Дайте определение закона классической логики высказываний.

7. Сформулируйте правило подстановки для исчисления высказываний.