Проверим, является ли выводимой формула ((?
?)
((
?
?)&?)). В этой формуле (будем обозначать ее ?) имеется три высказывания, что приводит к необходимости рассмотрения истинного значения ? на 23=8 комбинациях. Эти комбинации и соответствующие шаги по определению истинностного значения ? на них даны в табл. 3, в которой И и Л означают соответственно значения «истина» и «ложь».
Таблица 3

Появление в пятой строке в столбце ? значения Л свидетельствует о невыводимости исследуемой формулы. На этом шаге процесс вывода можно прекратить. Остальные строки в таблице приведены лишь для полноты картины.
«Логик-теоретик»
Так была названа программа для ЭВМ, созданная в середине шестидесятых годов американским кибернетиком А. Ньюэллом в содружестве с психологом Г. Саймоном. Она была предназначена для доказательства теорем в исчислении высказываний, т.е. для поиска обоснования тождественной истинности некоторых утверждений. Для того чтобы перейти к описанию программы «Логик-теоретик», введем предварительно понятие о равенстве двух выражений исчисления высказываний. Будем говорить, что выражения ?1 и ?2 равны между собой, и записывать этот факт обычным образом ?1=?2, если на всех возможных наборах интерпретации истинности входящих в них элементарных высказываний истинность ?1 и ?2 одинакова.
Появление знака равенства, которого не было в исчислении высказываний, не должно нас смущать. Его легко можно исключить из рассмотрения, введя формулу ((?1&?2)
(
?1&
?2)). Читатели могут проверить, что эта формула будет истинной только в том случае, когда оценки истинности ?1 и ?2 одинаковы. Тогда утверждение, что ?1=?2, становится эквивалентным утверждению, что формула ((?1&?2)
(
?1&
?2)) является истинной.
«Логик-теоретик» должен был доказывать справедливость утверждений вида ?1=?2 для различных ?1 и ?2. Однако авторы «Логика-теоретика» не пошли по прямому пути. Не стали строить таблицы для ?1 и ?2 и проверять совпадение истинности ?1 и ?2 на всех возможных интерпретациях истинности их аргументов. Ведь с ростом числа аргументов n число строк в этих таблицах растет как 2n . А. Ньюэлл и Г. Саймон пошли по пути приближения процедуры доказательства к тому, как это делают люди.
В основу процесса доказательства они положили идею ликвидации различий в формульной записи ?1 и ?2. Авторы программы составили перечень из шести различий.
1. В ?1 и ?2 различное число членов в формулах. Например, ?1=?
?, а ?2=?
?.
2. В ?1 и ?2 имеется различие в основной связке (т.е. в связке, которая выполняется последней). Например, ?1=(??)
(
), а ?2=(?
)
?.
3. Перед всем выражением для ?1(?2) стоит знак отрицания, а перед ?2(?1) его нет. Например, ?1=
(?
?), а ?2=??.
4. Аналогичное различие, но оно касается не всего выражения для ?i (i =1,2), а некоторого его подвыражения.
5. Скобки в ?1 расставлены не так, как в ?2. Например, ?1=?
(?
?), а ?2=(?
?)
?.
6. Записи для ?1 и ?2 отличаются порядком следования подвыражений. Например, ?1=(??)
?, а ?2=?
(??).
Для того чтобы иметь возможность ликвидировать подобные различия, используются 12 преобразований формул исчисления высказываний. Первые семь преобразований носят тождественный характер, т.е. не меняют истинного значения преобразуемых формул. Последние пять верны только при условии, что левая часть их является тождественно истинной (T -выражением).

В преобразованиях использованы большие латинские буквы, которые могут соответствовать любым подвыражениям формул ?1 и ?2. Стрелки
и
показывают направление преобразований. (Знак
есть по сути знак
.)
С помощью этих преобразований можно устранять различия между ?1 и ?2, которые мы перечислили выше. Укажем в специальной табл. 4 классы преобразований F 1, которые можно использовать для устранения различий. Первое различие разделено на два: различие 1’ требует добавления выражений в формулу, а различие 1’’ – вычеркивания из формулы лишних выражений.
Таблица 4

Крестики поставлены там, где можно устранить различие с помощью соответствующего преобразования.
Покажем работу программы «Логик-теоретик» на несложном примере. Пусть требуется доказать равенство ?1=?2, имеющее вид

Применим к ?1 первое преобразование из F 7 справа налево. Выбор F 7 определяется различием ?1 и ?2. Из ?1 необходимо убрать лишнее подвыражение С , которого нет в ?2. После этого получим

Поскольку в ?1 осталось еще выражение С , которого нет справа, то снова фиксируется различие 1’’ и ищется подходящее преобразование. Таким преобразованием является четвертое из F 7. Но для его применения надо сначала использовать преобразование F 1 для устранения различия 6. После этого, применяя четвертое преобразование из F 7, получаем

Теперь можно применить второе преобразование из F 7:

Четвертое преобразование из F 7 приводит к окончательному результату

Пример, конечно, не отражает всех особенностей работы программы «Логик-теоретик». Мы несколько упростили задачу. Как видно из таблицы различий, выбор преобразования на каждом шаге далеко не однозначен. В формулах могут существовать одновременно несколько различий, а для ликвидации различия можно использовать несколько преобразований. Всякий вывод, как бы он не был организован, носит переборный характер. И успешность того или иного выбора преобразования не может быть оценена локально, в момент выбора. Поэтому программа вынуждена перебирать варианты, заходить в тупики, проходить циклы прежде, чем она сможет найти правильный путь решения. Повышение эффективности процесса вывода – центральная проблема всех автоматизированных систем дедуктивного вывода.
Исчисление предикатов
Исчисление высказываний не позволяет описывать дедуктивные рассуждения всех типов, в частности силлогистические умозаключения.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64