Пример построения модели предметной области в исчислении высказываний

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

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

А — «Обезьяна находится в точке а»;

В — «Ящик находится в точке Ь»

С — «Бананы находятся в точке с»;

D — «Обезьяна находится на Ящике»;

Е — «Обезьяна держит Бананы»;

F — «Обезьяна, Ящик, Бананы находятся в разных точках»;

G — «Обезьяна находится рядом с Ящиком».

Используя логические связки —i, д, v, —", =, мы можем строить более сложные умозаключения, например такие.

1. Если «Обезьяна, Ящик, Бананы находятся на своих исходных позициях, т. е. в точках а, b и с соответственно», то справедливо сказать: «Обезьяна, Ящик, Бананы находятся в разных точках»:

2. Если «Обезьяна, Ящик, Бананы находятся в разных точках», то «Обезьяна находится не рядом с Ящиком»:

3. Если «Обезьяна, Ящик, Бананы находятся в разных точках», то «Обезьяна не находится на Ящике»:

4. Если «Обезьяна, Ящик, Бананы находятся в разных точках», то «Обезьяна не держит Бананы»:

Высказывания (2), (3) и (4) можно объединить в одно с помощью логической связки «И»: ^[1]

6. Если «Обезьяна, Ящик и Бананы находятся не в разных точках» (т.е. в одной), то «Обезьяна стоит на Ящике» И «Обезьяна держит Бананы»:

7. Если «Обезьяна не на Ящике», то «Обезьяна не держит Бананы»:

Таким образом, фрагмент предметной области на языке ИВ представляет собой следующий набор формул БЗ:

Для простоты введем обозначение S = А л В л С.

Теперь, используя механизм логического вывода ИВ, мы можем доказать выводимость любой другой формулы, структура которой соответствует синтаксису ИВ (в рамках данной модели). Докажем, например, что формула выводима. Ее смысл: если «Обезьяна, Ящик и Бананы не в исходных точках» И «Обезьяна на Ящике», то «Бананы в руках у Обезьяны».

Логический вывод можно выполнить несколькими способами.

1. Можно, например, использовать таблицу истинности, которая дает исчерпывающую картину значений переменных. При этом формулы (3.14) и (3.15) образуют выражение логического вывода в виде:

Далее следует вычислить значения выражений слева и справа от знака I—>. Если окажется, что формула справа принимает значение И как только все формулы (3.14), образующие левую часть, одновременно примут значение И, то логическая выводимость (3.15) из (3.14) доказана.

Учтем, однако, следующее: формула (3.16) имеет семь переменных. Это значит, что таблица будет содержать 2⁷, т. е. 128 строк! Есть и другие методы.

2. Можно попытаться использовать метод вывода, основанный на системе аксиом исчисления высказываний. Но это тоже — очень трудоемкий процесс.

3. Лучше всего попробовать метод опровержения, основанный на принципе дедукции и реализуемый посредством резолюций. Согласно этому методу следует доказать противоречивость системы:

где под номером (5) как раз и стоит отрицание формулы (3.15). Далее применим метод резолюций. Для начала все пять предложений следует представить в виде конъюнкции элементарных дизъюнктов (КЭД). Для простоты дизъюнкцию будем обозначать «+».

Для первого предложения имеем: Г. S + F.

Для второго: 2'. F + (G л D л Е).

Для третьего: 3'. F+(Z) л ?).

Для четвертого: 4'. D + Е.

Для пятого приведем цепочку преобразований:

5 '.SaD^E = SaD^E = S + D + E = SaDaE.

Пользуясь правилом раскрытия конъюнкции по дизъюнкции, имеем для 2': (F + G) л (F + D) л (F + ?); для 3': (F + D) л (F + Е).

Конъюнкция 5' распадается на три одночленных дизъюнкта: S, D, E.

Теперь у нас имеется система элементарных дизъюнктов, на основе которой делаем вывод методом резолюции (табл. 3.4).

Таблица 3.4

Вывод методом резолюции.

Мы получили «пустой» (ложный) дизъюнкт. Это значит, что выводимость формулы (3.2) из системы (3.14) доказана, т. е. утверждение (3.14) истинное.

Отметим, что приведенная резолюция не является единственно возможной.

Упражнения к параграфу 3.2

• 3.6. Определите, какие из нижеприведенных формул общезначимы, а какие невыполнимы:
  • а) VxP (jх) л ЗуР (у);
  • б) ЗхР (х)->_VyP (.y);
  • в) fxP{x) л ЗуР (у);
  • г) V.vP (.t) л ЗхР (х);
  • д) ЗхР (х) -« ЗуР (у) с) V. vP (.v) v ЗуР (у).
• 3.7. Приведите к предваренной форме, сделайте преобразования и докажите следующие тождества:
  • а) V.rP (.r) —> (ЗуР (у) —> (V.vP (.v) л VzP (z)));
  • б) (ЗхР (х) л V. tP (.v)) —> МуР (у)
  • в) 3xQ{x) —> (УуР (у) —> VzQ (z));
  • г) Э.т (2(.г) -» (V.vQ (.v) v VyP (y));
  • д) (3.tP (.r) ^yyQ (y)) ->((VxP (.r) -" 3zQ (z))^VwP (m)): с) (VxP (x) v 3yQ (y)) ->(З.гР (л) -> 3zQ (z));
  • ж) V. r (P (.r) —> Q (.r)) —"(3.rP (.r) —" аг (2(л-));
  • з) (VxP (.х) VyQ (y)) -" Vz (P (z) v Q (z)).
• 3.8. Докажите тождества методом опровержения:
  • а) Эх (Р (х) л Q (x)) (ЗуР (у) л 3zQ (z));
  • б) V.х (Р (х) —> Q (x)) —" (ЭхР (х) —> 3zQ (z));
  • в) Зу/хР (х, у) -> fx3yP (x, у);
  • г) НгР (г) -> УуР (уУ,
  • д) VxP (x) -> ((Зг/Р (у) -> VyQ (y)) -> 3zQ (z)).
• 3.9. Докажите нижеследующие силлогизмы:
• 1а) Кто мяукает, тот кошка;
• 16) Собаки — нс кошки;
• 1в) Следовательно: собаки не мяукают.
• 2а) Без свободы нет счастья;
• 26) Без счастья нет любви;
• 2в) Следовательно: где нет свободы, не может быть любви.

• [1] F —" (G л D л Е).