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

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

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

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

Первоначально замкнутую формулировку задачи можно многократно улучшать, если с учётом выполнения ограничений уменьшать объём множества X{x₁,x₂,…,x_n}, т.е. сокращать множество вариантов которые могут быть рассмотрены в качестве альтернативных решений.

Существует 2 способа формулировки задачи в замкнутой форме:

1. Характеризуется априорно-известными правилами перехода. Например, формулировка игры «пятнашки». Есть исходное состояние, определяемой на некоторой матрице, на которой произвольно расставлены фишки. Необходимо последовательно начальное состояние системы, добиться конечного состояния, в котором все фишки должны быть расставлены по порядку. Необходимо найти путь перехода из начального состояния S_нач в конечное S_кон, а оператор перехода P_AB из состояния A в состояние B имеет смысл при перемещении на пустую клетку любой фишкой из смежной клетки. Одним из ограничений является необходимость предупреждения «патовой» ситуации, когда следующие друг за другом переходы приводят к возврату в уже известного состояния ( ). Некоторое i-ое состояние не должно соответствовать из ранее рассмотренных состояний, для чего придётся создавать трассу переходов из некоторого начального состояния в i-ое состояние, то есть запоминать все промежутки.

2. Не содержит априорно-определённых правил перехода. Например, классическая формулировка задачи на доказательство теорем. Например, следует доказать, что из C(x) можно путём математических преобразований получить H(x). Доказать, что для любого n сумма кубов элементов арифметической прогрессии равна квадрату суммы этих элементов. .
Можно использовать законы коммутативности, ассоциативности, дистрибутивности, преобразования математических выражений. Правила, которые необходимо применить для перехода из одного состояния в другое, требуется отыскать среди некоторого набора возможных. В некоторых случаях задача формулируется, когда не задано конечное состояние, и требуется упростить некоторое математическое выражение. Окончание определяется субъективно, например, когда к полученному состоянию невозможно применить ни один из известных законов преобразования.

Выбор стратегии переходов из одного состояния в другое рассмотрим на следующем примере:

«На одном берегу реки находится волк, коза и капуста. Лодочнику требуется перевезти их на другой берег, но в лодку можно взять что-то одно».

Ограничения: волк может съесть козу, коза может съесть капусту.

Состояние этой системы может быть описано с помощью 2^х множеств: множество на левом и правом берегу

X,Y={W,G,C,B}

Правило переходаможно задать путём указания предмета, который должен быть переправлен и направлением движения - R(U,r).

Перевозимый предметU={Æ, W, G, C}.

Направление движенияr={L,R} – курсируя необходимо обеспечить перевоз всех предметов.

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

Не должно быть - если лодочник находится на другом берегу, если элемент B принадлежит другому множеству.

Возможны 4 направления стратегии решения задачи:

Можно произвести выбор стратегии, развивая решение задачи в глубину путем применения правил перехода к вновь полученному состоянию. Такой способ поможет быстро отыскать путь из начального состояния в конечное. Другая стратегия – определить все возможные переходы и допустимые - стратегии поиска пути, которая носит название «горизонтальная». Хотя нахождение конечного состояния займёт больше времени, не будет пропущено ни одного решения, если их несколько. В конце концов мы неизбежно придем к конечному состоянию: S_k (-; W,G,C,B).

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

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