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

Логическим исчислением, или просто исчислением, называют совокупность, которая включает в себя: алфавит (совокупность используемых символов); синтаксические правила построения формул в алфавите; аксиомы (общезначимые формулы); правила вывода по аксиомам производных формул или теорем.

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

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

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

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

Модус поненс. Из истинности условия импликации и истинности самой импликации следует истинность следствия импликации

Правило подстановки. Из формулы выводима формула которая получается подстановкой в формулу вместо каждого вхождения переменной формулы

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

Исключение конъюнкта. Из истинности конъюнкции следует истинность любого её конъюнкта

Введение конъюнкции. Из списка истинных формул следует истинность их конъюнкции

Введение дизъюнкции. Из истинности формулы следует истинность её дизъюнкции с любыми другими формулами

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

Простая резолюция (удаление дизъюнкта). Из истинности дизъюнкции и отрицания одного из её дизъюнктов следует истинность формулы, которая получается из дизъюнкции удалением этого дизъюнкта

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

или эквивалентно

Формализация вывода средствами логики высказываний. Вернемся к нашему примеру - среде кота. Введем три логические переменные истинное значение первой из которых означает, что кот находится у левой комнаты, а ложное, что он находится у правой комнаты; истинное значение переменной означает, что кусочек сыра лежит около левой комнаты, а ложное, что его там нет; истинное значение означает, что кусочек сыра лежит около правой комнаты, а ложное, что его там нет. В результате таких обозначений табл. 1 можно заменить на табл. 4.Каждое состояние среды можно рассматривать как комбинацию (отношение) простейших свойств объектов, задаваемых значениями отдельных логических переменных. Так, состояние соответствует комбинации свойств кота и кусочков сыра, состоящей в том, что кот находится у левой комнаты, и в то же самое время около левой и правой комнат находится по кусочку сыра. На русском языке эту комбинацию можно выразить предложением "Кот находится около левой комнаты, кусочек сыра лежит около левой комнаты и кусочек сыра лежит у правой комнаты". В соответствии с уже приведенной выше интерпретацией логических переменных это предложение можно представить формулой которая истинна в единственном случае - все логические переменные, входящие в нее, истинны, т.е. среда находится в состоянии . Формулы такого типа, которые являются конъюнкцией переменных с отрицанием или без него, называют элементарными конъюнкциями. Если среда находится в состоянии , то истинна формула и т.д.

Таблица 4

Состояние	Переменные			Формула, описывающая состояние
	xк	xл	xп
b1	И	И	И	xкxлxп
b2	Л	И	И	 xкxлxп
b3	И	И	Л	xкxл xп
b4	Л	И	Л	 xкxл xп
b5	И	Л	И	xк xл xп
b6	Л	Л	И	 xк xл xп
b7	И	Л	Л	xк xл xп
b8	Л	Л	Л	 xк xл xп

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

Рассмотрим теперь, как могут быть выражены в виде формул переходы среды из одного состояния в другое при совершении котом того или иного действия. Так если кот находился в состоянии и выполнил действие Идти направо, то среда перейдет в состояние Факт нахождения кота в состоянии и выполнение им в это время действия Идти направо означает истинность а факт перехода состояния при выполнении действия Идти направо в состояние будем интерпретировать как истинность формулы

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

Таблица 5

Переход			Импликация, соответствующая переходу
Исходное состояние	Действие	Результирующее состояние

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

Имеем таким образом постановку задачи:

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

* множество формул представляют все состояния среды в последнем столбце таблицы 4;

* множество допустимых переходов представлено импликациями в последнем столбце таблицы 5;

* множество допустимых действий описывается формулами

* множество целевых состояний представлено формулами и .

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

1. Выбираем начальное состояние Это означает истинность соответствующей ему формулы, которую будем обозначать В нашем случае

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

3. Полагаем, что формула истинна (среда находится в состоянии и совершает действие ).

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

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

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

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

Таблица 6

Исключение конъюнкта
Введение конъюнкта
Модус поненс
Исключение конъюнкта
Введение конъюнкта
Модус поненс
Модус поненс

Таким образом, для примера со средой кота был осуществлен вывод формулы из исходных истинных формул

, , , ,

,

что можно записать в виде выражения

, , , , .

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