2.3.3. Нахождение целевого состояния

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

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

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

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

• Множество допустимых переходов представлено импликациями в последнем столбце табл. 2.5;

Таблица 2.5 (см. скан)

Окончание табл. 2.5 (см. скан)

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

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

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

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

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

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

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

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

Таблица 2.6 (см. скан)

истинна. (При т.е. в этом случае среда переходит из состояния снова в состояние в результате действия

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

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

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

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