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

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_
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).

 

Логические уравнения

Краткая справка

Теоретический материал в полном объёме можно найти в работах [18,24,26].

Таблица базисных функций 4-значной комплементарной логики

XY	X'	X&Y	X+Y	XY	X'	X&Y	X+Y
00	1	0	0	i0	j	0	1
0j	1	0	j	ij	j	0	1
0i	1	0	i	ii	j	i	i
01	1	0	1	i1	j	i	1
j0	i	0	j	10	0	0	1
jj	i	j	j	1j	0	j	1
ji	i	0	1	1i	0	i	1
j1	i	j	1	11	0	1	1

Алгоритм "Селигер" решения логических уравнений

1. Привести систему уравнений к нулевому виду (исходная система).

2. Заполнить карту Карно нулями в соответствии с термами левых частей исходной системы уравнений, а в оставшиеся клетки вписать единицы. Эти единичные термы представляют собой СДНФ полной единицы системы.

3. Произвести минимизацию совокупности единичных термов. Полученное соотношение представляет МДНФ уравнения полной единицы системы.

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

5. Произвести минимизацию искомых функций.