Аксиоматический метод. 
Исчисление высказываний

В школьном курсе геометрии упоминаются имя древнегреческого математика Евклида, его трактат «Начала» и часто встречаются слова аксиома и теорема. Геометрия Евклида является классическим примером построения научной теории аксиоматическим методом.

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

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

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

Основные правила логического вывода

Правило отделения

Если истинно высказывание А и истинно, что из А следует Б, то истинно и высказывание Б (если А = 1, А => Б, то Б = 1).

Правило силлогизма

Если истинно высказывание, что из А следует Б, и истинно высказывание, что из Б следует С, то истинно и высказывание, что из А следует С (если А => Б, В => С, то Л => С).

Правило равносильной замены

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

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

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

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

Имея законы логики высказываний 1—24 и правило равносильной замены, получим способ построения различных формул, равносильных данной, а заодно еще один способ доказательства равносильности двух формул, кроме построения их совместной таблицы истинности.

Правило равносильной замены перепишем в более удобном для этих целей виде: если в некоторой формуле F заменить подформулу G равносильной ей формулой G', то получим формулу F равносильную исходной формуле F.

Пример 2.9.

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

Решение. В силу закона 9 (двойного отрицания) имеет место равносильность формул.

К подформуле А л В, стоящей справа формулы, применим закон 12 (де Моргана).

Затем используем правило равносильной замены и получим в итоге требуемую формулу:

Закон 23 показывает, что для операции импликации также существует равносильная ей формула, в которой встречаются только операции отрицания и дизъюнкции:

Для логической операции эквивалентности равносильную ей формулу, содержащую только операции отрицания и дизъюнкции, можно построить, пользуясь правилом равносильной замены, законом 24, формулой для конъюнкции из предыдущего примера и законом двойного отрицания 9:

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

В 1928 г. немецкий математик Д. Гильберт сформулировал аксиоматическую теорию высказываний, названную в его честь гильбертовым исчислением высказываний.

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

Замечание. Вместо отрицания и дизъюнкции в качестве «основных» операций логики высказываний можно использовать отрицание и конъюнкцию. Это следует из законов де Моргана, связывающих между собой дизъюнкцию, конъюнкцию и отрицание.

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