Сориты. Полисиллогизмы
Краткая справка
Сорит - это умозаключение из нескольких посылок, в котором каждая последующая посылка является заключением для двух предыдущих. В классической силлогистике для сорита выводится лишь одно заключение. Посылки в сорите являются общеутвердительными или общеотрицательными суждениями. На самом деле реально посылки могут быть как общего, так и частного характера. Полисиллогизм - это умозаключение с произвольным соотношением посылок и терминов. Таким образом сорит - частный и наиболее примитивный вид полисиллогизма. Заключений в сорите, как и в полисиллогизме, может быть огромное количество. Для двухаргументных(двуместных) заключений оно определяется как число сочетаний из числа посылок по 2, т.е.
K = С(n,2) = n(n-1)/2,
где К - число залючений от двух аргументов, n - число терминов в посылках. Количество абсолютно новых заключений меньше К на число исходных посылок. Если же рассматривать искомые заключения, как функции от трёх и более переменных, то К значительно возрастает. Однако при этом теряется прозрачность полученных результатов. Алгоритм "Осташков" для решения соритов и полисиллогизмов достаточно прост. Он является следствием из алгоритмов "ИЭИ" (синтез силлогизмов) и "Селигер"(решение логических уравнений).
Аббревиатуры СДНФ (совершенная дизъюнктивная нормальная форма) и МДНФ (минимальная дизъюнктивная нормальная форма) являются традиционными в классической логике, поэтому не требуют пояснений.
Алгоритм "Осташков" (синтез заключений полисиллогизма)
Алгоритм "Суздаль" (графический синтез заключений сорита)
Алгоритм графического нахождения исходных посылок
Алгоритм аналитического отыскания исходных посылок
Практикум по решению соритов и полисиллогизмов
Задача 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_ |
| 0011 | 1 |
| 0111 | 1 |
| 1011 | 1 |
| 1111 | 1 |
| 1100 | 1 |
| 1101 | 1 |
| 1110 | 1 |
a =====================------=====----- b =====================-----------===== c ----=====------====================== d ---------============================
Как несложно догадаться, скалярные диаграммы представляют собой двоичные коды рабочих наборов полной единицы системы М.
Иногда возникает задача восстановить по известной полной единице системы М исходные посылки. Алгоритм разложения логического уравнения на исходные посылки прост.
Задача 3
В задаче Порецкого о птицах получена полная единица системы:
M = sy+gx'.
Найти минимальное количество возможных посылок.
Построим сокращённую таблицу истинности для М.
| gsxy | _m_ |
| 0101 | 1 |
| 0111 | 1 |
| 1101 | 1 |
| 1111 | 1 |
| 1000 | 1 |
| 1001 | 1 |
| 1100 | 1 |
По полученной таблице истинности нарисуем скалярные диаграммы.
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).