Автоматизация решения задач. 
Логический подход

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

По этой тематике может быть рекомендована книга [42].

З.1 Исчисление высказываний

З.1.1 Язык логики высказываний

При задании формального логического языка обычно следуют следующей схеме:

• а) Указывается конечный либо бесконечный набор символов, образующих алфавит языка; при описании алфавита могут вводиться те или иные характеристики его символов, в частности определяться разбиения их на подклассы.
• б) Вводится индуктивное описание множества правильных выражений языка — конечных последовательностей символов алфавита.
• в) Индуктивным образом определяется интерпретация языка (либо множеств допустимых интерпретаций), сопоставляющая каждому выражению языка обозначаемую им функцию, либо объект из некоторой «области интерпретации» .

Пункты а) и 6) задают синтаксис логического языка, пункт в) — его семантику В случае языка логики высказываний эта общая схема реализуется следующим образом:

• а) Алфавит языка логики высказываний состоит из счетного списка переменных хьвд, двух логических констант И, Л; заданного набора логических связок (например, связок V,&, *-?), а также скобок (,).
• б) Правильные выражения языка логики высказываухий, называемые формулами логики высказываухий, вводятся при помощи следующего определения:
  • 1) Однобуквенное слово, состоящее из переменной, есть формула логики высказываний.
  • 2) Если слова А и В суть формулы логики высказываний, то

слова (-'Л), (А V В)₎ (AScB)_} (А —? В)> (А В) суть формулы логики высказываний.

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

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

Таким образом, интерпретацией языка логики высказываний мы называем отображение /, определенное на множестве переменных х_% хг,… и сопоставляющее каждой переменной х, некоторую истинностную константу а,; а* G {И, Л}. Значение (F)r формулы F в интерпретации I определяем индукцией по построению формулы F:

• 1) Если F есть переменная х*, то (F)i есть /(х<);
• 2) Если F имеет вид -«((G)j = 6, то (F)[ есть истинностная константа, отличная от 6;
• 3) Если F имеет вид G V G2 и уже определены (G)i = 61, (G2)/ = 62, то (F)j есть константа И, если хотя бы одно из Ь, 62 равно И, иначе (F)j есть Л;
• 4) Если F имеет вид GkG2 и уже определены (G)j = 61, (^2)/ = 62, то (F)j есть константа И, если 61,62 равны И, иначе (F)j есть Л;
• 5) Если F имеет вид G —? G2 и уже определены (Сч)/ = 61, (С?2)/ = 62, то (F)/ есть константа Л, если 61 равно И, а 62 равно Л; иначе (F)i есть И;
• 6) Если F имеет вид G (7₂ и уже определены (Сч)/ = 6‘_ь (С?г)/ = 6₂, то (F)/ есть константа И, если 61 =62, иначе (F)/ есть Л.

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

Моделью формулы / будем называть произвольную интерпретацию языка логики высказываний в которой / имеет значение И.

Формулу имеющую хотя бы одну модель назовем выполнимой.

Формулу не имеющую ни одной модели назовем невыполнимой.

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

В качестве примеров отметим, что формула ((xi Vx₂) —* х₂) — выполнима, но не общезначима, формула ((xi&x₂) —? х₂) — общезначима, а формула (-'(xi —? (х₂ —? xi))) — невыполнима.

В дальнейшем часто мы будем опускать скобки, подразумевая, что -" — самая приоритетная операция, и в случае, когда порядок расставления скобок не существенен.

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

• 1) Нахождение индуктивного описания класса всех общезначимых формул. Такое описание определяет в базисе индукции некоторое подмножество общезначимых формул (конечное либо бесконечное), называемых аксиомами, и указывает в индуктивном шаге перечень допустимых правил вывода, позволяющих получать новые общезначимые формулы исходя из ранее найденных. Логический язык вместе с индуктивным описанием такого рода образует дедуктивную систему.
• 2) Нахождение алгоритма, перечисляющего все общезначимые формулы — фактически, обеспечивается при построении дедуктивной системы.
• 3) Нахождение алгоритма, распознающего общезначимые формулы в классе всех правильных выражений языка. В отличие от пунктов 1 и 2, описание такого типа удается найти лишь для весьма немногих логических языков, к числу которых относится и язык логики высказываний.