5.4. Решение логических задач методом характеристического уравнения

Алгоритм решения:

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

2. Запись условия задачи в виде логических уравнений

(*)

где логическая функция

3. Сведение системы уравнений к характеристическому уравнению

(**)

множество корней, которого совпадает с множеством корней системы (*)

4. Приведение левой части характеристического уравнения к ДНФ и решение его:

• Приравнивание каждого слагаемого ДНФ (СДНФ), независимо от других, к единице извлечение из уравнения значений переменных. Каждый их набор является решением задачи.

• Если после упрощения в ДНФ осталось только одно слагаемое, задача имеет единственное решение. В случае, когда в левой части уравнения все слагаемые уничтожены, задача не имеет решения.

Рассмотрим применение этого алгоритма на примере одной из логических задач.

Задача Р.М. Смаллиана «Принцесс и тигр».

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

На табличках, прикрепленных к двери каждой из комнат, было написано:

1.	2.
В этой комнате находится принцесса, а в другой комнате сидит тигр.	В одной из этих комнат находится принцесса, кроме того, в одной из этих комнат сидит тигр.

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

Решение:

1. Формулируем простые высказывания:

• «принцесса находится в комнате i»: i=1,2;

• - «тигр сидит в комнате i»: i=1,2;

2. формулируем сложные высказывания, соответствующие условию задачи:

Получаем систему уравнений:

3. Составляем характеристическое уравнение:

4. Приведение левой части характеристического уравнения к ДНФ. Реализуем с помощью матричного представления логических функции:

Из последней матрицы видно, что ДНФ содержит только одно слагаемое.

Решением уравнения является набор 0110, т.е. принцесса находится в комнате 2, а тигр в комнате 1.

5.5. Алгебра предикатов

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

Предикат - повествовательное предложение, содержащее предметные переменные, определенные на соответствующих множествах. При замене переменных конкретными значе­ниями (элементами) этих множеств предложение обращает­ся в высказывание, т.е. принимает значение "истинно" или "ложно".

n-местный предикат - это функция Р(х₁,х₂,...,х_n) от n переменных, принимающих значения из некоторых задан­ных предметных областей, так что х₁М₁, х₂М₂,..., х_nМ_n, а функция Р принимает два логических значения - "истинно" или "ложно" ({И, Л}, {1, 0}). Таким образом, предикат Р(х₁,х₂,...,х_n) является функцией типа Р: М₁×М₂×...×М_n → В, где множества М₁,М₂,...,М_n назы­ваются предметными областями предиката; х₁,х₂,...,х_n - предметными переменными предиката; В - двоичное (би­нарное) множество {И, Л} или {1,0}.

В качестве примера рассмотрим три высказывания:

А - "Рубль - валюта России";

В - "Доллар - валюта России";

С - "Доллар - валюта США".

Высказывания А и С - истинны, а В - ложно. Если вместо конкретных наименований валюты в выражениях А, В (и, может быть, аналогичных им) подставить предметную пере­менную х и определить ее на множестве наименований де­нежных единиц {рубль, доллар, фунт стерлингов,..., мар­ка}, то получим одноместный предикат Р(х) - "х - валюта России".

Если в выражениях А, В, С (или аналогичных им) вместо конкретных наименований валюты и государства подставить соответственно переменные x и у, где у {Россия, США, Англия,...,Германия}, получим двухместный предикат P(x, у) – «x - валюта у». Общим для этих предикатов является то, что, приписав значения входящим в них переменным из со­ответствующих областей определения, получим высказыва­ния, обладающие свойством "истинно" или "ложно".

С помощью логических связок (и скобок) предикаты мо­гут объединяться в разнообразные логические формулы - предикатные формулы. Исследование предикатных формул и способов установления их истинности является основным предметом логики предикатов. Логика предикатов вместе с входящей в нее логикой высказываний является основой ло­гического языка математики. С ее помощью удается форма­лизовать и точно исследовать основные методы построения математических теорий. Логика предикатов является важным средством построения развитых логических языков и фор­мальных систем (формальных теорий).

Логика предикатов, как и логика высказываний, может быть построена в виде алгебры логики предикатов и исчис­ления предикатов. Здесь, как и в случае логики высказыва­ний, для знакомства с основными понятиями логики преди­катов воспользуемся языком алгебры, а не исчислений.

Соответствия между предикатами, отноше­ниями и функциями:

1. Для любых М и n существует взаимно однозначное соответствие между n-местными отношениями RМⁿ и n-местными предикатами Р(х₁,х₂,...,х_n), Р: Мⁿ → В:

• каждому n-местному отношению R соответствует пре­дикат Р(х₁,х₂,...,х_n) такой, что Р(a₁,a₂,...,a_n) = 1, если и только если (a₁,a₂,...,a_n) R;

• всякий предикат Р(х₁,х₂,...,х_n) определяет отношение R такое, что (a₁,a₂,...,a_n) R, если и только если Р(a₁,a₂,...,a_n) = 1.

При этом R задает область истинности предиката Р.

2. Всякой функции f(х₁,х₂,...,х_n), f: Мⁿ → М, соответ­ствует предикат Р(х₁,х₂,...,х_n,х_n+1), P: M^n+l →B, такой, что Р(a₁,a₂,...,a_n,a_n+1) = 1, если и только если f(a₁,a₂,..., a_n) = a_n+1

Рис. 5.1

Аналогичное соответ­ствие (взаимно однозначное) имеется между подмноже­ством отношений {R'}{R} и множеством функций {f}. Для этого класса отношений выполняется аналогичное условие:

если (a₁,a₂,...,a_n,a_n+1)R', то для любого a`_n+1a_n+1 (a₁,a₂,...,a_n,a_n+1)R'. (5.2)

Выражение Р(a₁,a₂,...,a_n) будем понимать как высказы­вание «Р(a₁,a₂,...,a_n) =1» или «Р(a₁,a₂,...,a_n) истинно», а выражение Р(х₁,х₂,...,х_n) - как переменное высказывание, истинность которого определяется подстановкой элементов множества М вместо переменных х₁,х₂,...,х_n. При этом бу­дем также называть Р(х₁,х₂,...,х_n) логической (двоичной) переменной, в отличие от х₁,х₂,...,х_n - предметных (нелоги­ческих) переменных.

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