Практикум по решению соритов и полисиллогизмов

Алгоритм аналитического отыскания исходных посылок

Алгоритм графического нахождения исходных посылок

1. Найти СДНФ полной единицы системы М и построить сокращённую таблицу истинности для неё.
2. По сокращённой таблице истинности построить скалярные диаграммы, разбив интервал универсума на части, количество которых равно числу наборов в таблице истинности для М. Каждая часть универсума изображается соответствующим набором из таблицы истинности для М.
3. Из скалярных диаграмм выбрать (N - 1) логических функций от двух переменных, где N - число аргументов.

1. По заданной полной единице системы построить N-1 посылок сорита как функций от двух переменных, заменяя на 1 все "лишние" переменные. Здесь N - число аргументов.
2. Проверить полученные результаты логическим перемножением посылок и сравнением с заданной полной единицей системы.

Задача 1

Рассмотрим в качестве примера одну из задач Льюиса Кэрролла. Пусть у нас имеются 5 посылок:

1. Не бывает котёнка, который любит рыбу и которого нельзя научить всяким забавным штукам.

Не бывает котёнка без хвоста, который будет играть с гориллой.

Котята с усами всегда любят рыбу.

Не бывает котёнка с зелёными глазами, которого можно научить забавным штукам.

Не бывает котят с хвостами, но без усов.

После длительных преобразований ("Энциклопедия-Россия-Он-Лайн") получается единственное заключение Eef, т.е. "Не бывает котёнка с зелёными глазами, который будет играть с гориллой. При этом утверждается, что заключение не очевидно.

Решим этот сорит в соответствии с алгоритмом "Осташков". В качестве универсума U) примем множество всех котят. Введём следующие обозначения:

a - котята, любящие рыбу;b - котята, обучаемые забавным штукам;d - котята с хвостом;e - котята, которые будут играть с гориллой;f - котята с зелёными глазами;g - котята с усами.

Тогда наши посылки будут описаны с помощью силлогистических функторов следующим образом:

Aab.Aed.Aga.Ebf.Adg.

Для перевода мнемонических записей на язык математики воспользуемся Руской логикой: Axy = x'+y; Exy = x'+y'; Ixy(8) = 1. Здесь и далее во всех аналитических выражениях апостроф представляет инверсию аргумента или функции. Переходим к выполнению алгоритма "Осташков". Вначале находим полную единицу системы М как логическое произведение всех исходных посылок.

M = AabAedAgaEbfAdg = (a'+b)(e'+d)(g'+a)(b'+f')(d'+g).

Поскольку перемножать 5 двучленов утомительно, то переходим к M' с помощью правила Де Моргана: M' = ab'+d'e+a'g+bf+dg'

2 и 3. После заполнения карты Карно и проведения минимизации[3] получим: M = a'b'd'e'g'+bd'e'f'g'+abd'e'f'+abdf'g

4. Перебирая все комбинации из шести переменных по 2 получим 15 заключений:

f1(a,b) = a'b'+b+ab+ab = a'+b = Aab;(Все котята-"рыболюбы" обучаются забавным штукам)f2(a,d) = a'd'+d'+ad'+ad = a+d' = Ada;(Все котята с хвостами любят рыбу)f3(a,e) = a'e'+e'+ae'+a = a+e' = Aea;(Все играющие с гориллой любят рыбу)f4(a,f) = a'+f'+af'+af' = a'+f' = Eaf;(Все зеленоглазые не любят рыбу)f5(a,g) = a'g'+g'+a+ag = a+g' = Aga;(Все усатые любят рыбу)f6(b,d) = b+d' = Adb;(Все хвостатые обучаются забавным штукам)f7(b,e) = b+e' = Aeb;(Все играющие с гориллой обучаются забавным штукам)f8(b,f) = b'+f' = Ebf;(Зеленоглазые не обучаются забавным штукам)f9(b,g) = b+g' = Agb;(Все усатые обучаются забавным штукам)f10(d,e) = e'+d = Aed;(Все играющие с гориллой имеют хвосты)f11(d,f) = d'+f' = Edf;(Все зеленоглазые - бесхвостые)f12(d,g) = d'+g = Adg;(Все хвостатые - с усами)f13(e,f) = e'+f' = Eef;(Зеленоглазые не будут играть с гориллой)f14(e,g) = e'+g = Aeg;(Все играющие с гориллой имеют усы)f15(f,g) = g'+f' = Efg.(Зеленоглазые - без усов).

Поскольку универсум - котята, то во всех заключениях речь идёт только о них.

5.Отобразим полученные заключения на скалярных диаграммах. Для этого выстроим полученные заключения по "ранжиру":f10f12f5f1f8 = AedAdgAgaAbEbf.

a =====================---------------- b =========================------------ d ================--------------------- e =============------------------------ f -----------------------------======== g ===================------------------

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

f16(a,b,d) = a'b'd'+bd'+abd'+abd = a'd'+ab =(a+d)'+ab = A(a+d)(ab),

т.е. "Все (a+d) суть ab". Такое заключение подтверждается и скалярными диаграммами. Однако информационность полученной функции сомнительна.

Из анализа результатов можно сделать следующие выводы:

Полученные функции f1(a, b),f5(a, g),f8(b, f),f10(d, e),f12(d, g) соответствуют исходным посылкам 1,3,4,2,5, что подтверждает правильность результатов синтеза.

Даже все синтезированные заключения не дают наглядного представления о взаимном соотношении множеств a, b, d, e, f, g. С этой задачей могут справиться лишь скалярные диаграммы.

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

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

Задача 2.

Пусть заданы 4 суждения: Aa'c, Aa'd, Ab'c, Ab'd. Если исходные посылки из предыдущего примера можно было сразу представить в виде скалярных диаграмм и тем самым получить готовое решение сорита, то в данном примере так не получится. Решение по алгоритму "Осташков" выглядит следующим образом.

M = Aa'c Aa'd Ab'c Ab'd = (a+c)(a+d)(b+c)(b+d).M' = a'c'+a'd'+b'c'+b'd'.

После занесения в карту Карно и минимизации получим:

M = ab+cd.f1(a,b) = ab+1 = 1 = Iab(8);f2(a,c) = a+c = Aa'c;f3(a,d) = a+d = Aa'd;f4(b,c) = b+c = Ab'c;f5(b,d) = b+d = Ab'd;f6(c,d) = 1+cd = 1 = Icd(8).

Полученные функции f2 - f5 совпали с исходными посылками, что подтвердило корректность синтеза, но впредь лишнюю работу делать не обязательно: можно было построить лишь f1, f6. Пример 2 впервые показывает, что заключение сорита может быть частно-утвердительным. По результатам синтеза построим скалярные диаграммы. Поскольку процесс эвристического построения несколько затруднителен, то предлагается использовать с этой целью сокращённую таблицу истинности для М и формализовать синтез скалярных диаграмм.

dcba	_m_

a =====================------=====----- b =====================-----------===== c ----=====------====================== d ---------============================

Как несложно догадаться, скалярные диаграммы представляют собой двоичные коды рабочих наборов полной единицы системы М.

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

Задача 3

В задаче Порецкого о птицах получена полная единица системы:

M = sy+gx'.

Найти минимальное количество возможных посылок.

Построим сокращённую таблицу истинности для М.

gsxy	_m_

По полученной таблице истинности нарисуем скалярные диаграммы.

g -----------========================== s ======================----------===== x ----=======-----======--------------- y ======================-----=====----- 0101 0111 1101 1111 1000 1001 1100

По скалярным диаграммам выберем наиболее простые логические функции от двух переменных. Причём должен соблюдаться такой порядок: f1(g,s), f2(g,x), f3(g,y). Однако f2(g,x) = Igx, а такую функцию не всегда просто представить в виде скалярной диаграммы. Поэтому мы заменим её на f2(s,x) и f4(x,y). Строго говоря, для получения корректной М, обеспечивающей получение однозначного решения полисиллогизма, необходимо перемножить все двуместные функции от заданных аргументов. Это решение проблемы "в лоб", не лучшее, но надёжное.

1(g,s) = g+s = Ag's;f2(s,x) = s+x' = Axs;f3(g,y) = g+y = Ag'y;f4(x,y) = x'+y = Axy.

После перемножения полученных посылок определим M:

M = (g+s)(s+x')(g+y)(x'+y) = (g+sy)(x'+sy) = sy+gx',

что совпадает с исходными данными. Кстати, у Порецкого вместо 4-х посылок использованы 5.

Задача 4

Пусть задано M = m'+xy. Найти исходные посылки.

f1(m, x) = m'+x = Amx;f2(m, y) = m'+y = Amy.M = (m'+x)(m'+y) = m'+xy,

что и требовалось доказать. Однако данный пример не так прост, как кажется на первый взгляд. Здесь кроется подвох, связанный с отысканием f3(x,y).

Дата добавления: 2015-05-08