2. Особенности построения доказательств в логике высказываний

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

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

В логике высказываний все доказательства строятся на отношении поряд­ка, то есть на отношении, которое существует между причиной и следствием. Здесь уже отдельные звенья цепи доказательства связаны символом импликации, который при логическом выводе заменяется на символ « ». Введем еще два метасимвола: вместо объектной конъюнкции « » будем использовать субъек­тивный символ метаконъюнкции - « , », а вместо объектной дизъюнкции « » - субъективную метадизъюнкцию « ; ». Тогда утверждение, которое требуется доказать, в логике высказываний оформляется в виде следующего причинно-следственного отношения:

где P_i - посылка (причина), С - заключение (следствие).

Читается, «Если посылки Р₁, Р₂, ..., Р_п истинны, то заключение С тоже истинно» или, по другому; «Если причины Р₁, Р₂, ..., Р_п имели место, то будет иметь место и следствие С».

Чтобы не путать объектное высказывание (предложение) с субъективным высказыванием, справедливость которого намерены установить, условимся на­зывать предложения типа (10.1.) клаузой (clause), которая представляет собой метапредложение, в котором использовано отношение порядка, оформленное через символ метаимпликации « ». Клауза является формальной записью до­казываемого предложения. Вместо букв в нее можно подставить объектные вы­сказывания, и тогда клауза наполняется конкретным содержанием, которое на­зывается семантикой или легендой.

Клаузу вида (10.1.) называют хорновской. Произвольную клаузу всегда можно свести к хорновскому виду путем эквивалентных преобразований.

Если символ метаимпликации « » сместить в крайнее левое положение. то она превращается в тавтологию:

Тавтология позволяет находить верные заключения при любой истинности по­сылок.

Если символ метаимпликации « » сместить в крайнее правое положение, то она превращается в противоречие:

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

3. Аксиоматический метод доказательства логических клауз

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

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

если А=В, то В=А

всегда можно представить в антисимметричной форме:

если А=В, то ,

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

Дана очевидная сентенция:

«Истину может изречь всякий»

На формальном языке логики высказываний эту сентенцию можно представить следующей клаузой;

(10.2.)

Она означает: «если А истинно, то источником этой истинности может быть что угодно, например B». Если произвести эквивалентное преобразование этой клаузы

(10.3.)

то семантика ее тоже изменится, и станет примерно такой: «если ранее было ус­тановлено, что А истинно, то истинность В не может проявиться так, что А ста­нет ложным». Путем эквивалентных преобразований клаузу (10.2.) всегда можно преобразовать к другим формам:

,

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

(10.4.)

к виду

.

После раскрытия скобок и упрощения сразу же приходим к аксиоме по­рядка (10.3.). Доказанная элементарная клауза (10.4.) известна с времен Аристо­теля и играет исключительно важную роль в логике высказываний. Она имеет даже специальное латинское название - modus ponens - правило отделения. Ес­ли в процессе доказательства справедливости какой-либо сложной клаузы уда­лось свести ее к клаузе (10.4.), считается, что доказательство состоялось.

Закон антисимметричности по существу определяет правила действия по переносу объектных высказываний относительно символа метаимпликации. Что же касается двух других законов отношения порядка, то они, в принципе, сво­дятся к аксиоме порядка. Так закон рефлексивности путем использования закона о единице может быть записан как:

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

а эту клаузу уже можно доказывать путем сведения ее к аксиоме порядка. Про­ведем доказательство в три этапа:

1. Перенесем А влево за знак метаимпликации

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

3. Затем еще раз воспользуемся этим же правилом, но для третьей посыл­ки и вновь полученной, что приводит к аксиоме порядка в форме:

Таким образом, закон транзитивности доказан. Убедимся в истинности тавтологии:

1. Произведем эквивалентные преобразования:

2. Воспользуемся правилом отделения:

3. Воспользовавшись еще раз правилом отделения, приходим к аксиоме порядка в форме предыдущего примера:

Докажем справедливость клаузы, которая построена на основе тождест­венного закона склеивания:

После эквивалентного преобразования:

она сводится к закону рефлексивности, то есть к частному случаю аксиомы по­рядка, рассмотренному ранее,

Исторически первой системой аксиом классической логики была система, предложенная Г. Фреге:

1. 

2. 

3. 

4. 

5. 

Первая из аксиом Фреге является аксиомой порядка. Вторая доказана вы­ше. Остальные аксиомы представляют собой тождества логики Буля, записан­ные в форме клауз.

Позднее Я. Лукасевич уменьшил число аксиом в системе Фреге с пяти до трех:

3. 

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