План Литература. W145 В. И. Лобанов. Инженерные методы разработки цифровых уст- 4/231(цптб) ройств М.: 1977. Информационный листок N% 54-87 В. И. Лобанов Метод бу

Вид материала

Подобный материал:

1 2 3 4

частью не совпадают с традиционными "правильными" силлогизма-

ми[8].Это и естественно:традиционная логика построена на нес-

колько иных базовых суждениях.

Кстати,для запоминания "правильных" модусов человечество придума-

ло мнемонику,которая облегчает распознавание 19 сильных и 5 слабых

достоверных форм.Первые три гласные в каждом слове представляют модус:

1.BARBARA,CELARENT,DARII,FERIOQUE = AAA,EAE,AII,EIO.

2.CESARE,CAMESTRES,FESTINO,BAROCO = EAE,AEE,EIO,AOO.

3.DARAPTI,DISAMIS,DATISI,FELAPTON,BOCARDO,FERISON =

AAI,IAI,AII,EAO,OAO,EIO.

4.BRAMANTIP,CAMENES,DIMARIS,FESAPO,FRESISON =

AAI,AEE,IAI,EAO,EIO.

Мнемоника современного образца[20] выглядит проще и осмысленнее:

1.Четыре девочки:BARBARA,BERNADETTE,HERMIONE,LAVINIA.

2.Встретили 4-х мальчиков:ALPHONSO,ELIOTT,GERVASE,LAVRENCE.

3.Они посетили 6 мест:ATLANTIC,PACIFIC,EQUATOR,ETHIOPIA,

MIAMI,MONACO.

4.Там они видели пятерых знаменитостей:CLARENCE,

MELCHIOR,ISAIAH,MALACHI,MELANCTHON.

Однако не следует забывать,что большинство этих модусов не имеет

никакого отношения к логике здравого смысла.

Домашнее задание.

1.Проверить все "правильные" Аристотелевы модусы на основе русс-

кого базиса.

2.Найти заключения для AxmImy',EmxIm'y,AmxIm'y',Am'xIxy.

Силлогистика Аристотеля-Жергонна

ЛЕКЦИЯ 9

СИЛЛОГИСТИКА АРИСТОТЕЛЯ-ЖЕРГОННА

Аристотелева силлогистика[1],традиционно излагаемая в учеб-

никах[8,16],давно уже не устраивает логиков[2-6].Особенно возрос поток

публикаций по силлогистике в последнее время[5,8,18].Все это свиде-

тельствует о том,что проблемы анализа и синтеза силлогизмов далеки от

разрешения.Кстати,впервые правильность модусов Аристотеля опроверг

Лейбниц(1646-1716),но авторитет основателя логики был настолько ве-

лик,что Лейбниц посчитал свои выводы ошибочными.

В прекрасной монографии Стяжкина Н.И.[19] приведены так называе-

мые "жергонновы отношения".С помощью этих отношений Ж.Д.Жер-

гонн(1771-1859) представил все классы суждений(силлогистические функ-

торы),выделенные Аристотелем,на языке теории множеств.Переведем "жер-

гонновы отношения" на язык скалярных диаграмм.

x x' x x'

L=========+---------- L=========+----------

y y' y' y

L============+------- L------------+======-

y y'

L=========+----------

Axy. Exy.

x' x x' x

L---------+=========- L---------+=========-

y y' y y'

a)L============+------- a)L============+-------

y' y y' y' y y'

b)L----+========+------ b)L----+========+------

y' y y y'

c)L------+============- c)L======+-------------

y' y y' y

d)L-------------+=====- d)L-------------+=====-

y' y

e)L---------+=========-

Ixy. Oxy.

Скалярные диаграммы обладают хорошей наглядностью и позволяют,как

мы увидим в дальнейшем,даже школьнику легко находить графическое реше-

ние силлогизмов.Скаляры в данной ситуации отображают множества и могут

быть описаны на языке алгебры множеств[9].Скалярным диаграммам,предс-

тавленным на рис.1-4 соответствуют таблицы истинности(табл.1-4).

Табл.1 Табл.2 Табл.3 Табл.4

-----T---¬ -----T---¬ -----T---¬ -----T---¬

¦ xy ¦Axy¦ ¦ xy ¦Exy¦ ¦ xy ¦Ixy¦ ¦ xy ¦Oxy¦

+----+---+ +----+---+ +----+---+ +----+---+

¦ 00 ¦ 1 ¦ ¦ 00 ¦ 1 ¦ ¦ 00 ¦ i ¦ ¦ 00 ¦ i ¦

¦ 01 ¦ i ¦ ¦ 01 ¦ 1 ¦ ¦ 01 ¦ i ¦ ¦ 01 ¦ i ¦

¦ 10 ¦ 0 ¦ ¦ 10 ¦ 1 ¦ ¦ 10 ¦ i ¦ ¦ 10 ¦ 1 ¦

¦ 11 ¦ 1 ¦ ¦ 11 ¦ 0 ¦ ¦ 11 ¦ 1 ¦ ¦ 11 ¦ i ¦

L----+---- L----+---- L----+---- L----+----

Из таблиц истинности(табл.1-4) получаем следующие соотноше-

ния:

"Все X суть Y" : Axy = xy+x'y'+ix'y (1)

"Ни один X не есть Y" : Exy = x'+y'= (xy)' (2)

"Некоторые X суть Y" : Ixy = xy+i(xy)' (3)

"Некоторые X не суть Y": Oxy = xy'+i(xy')' (4)

Кстати из (3) и (4) видно,что Oxy = Ixy',что вовсе не соответс-

твует математическому смыслу функтора Oxy.

В связи с тем,что при проверке силлогизмов потребуются отри-

цания функций (1-4),то на основе формулы де Моргана выведем фор-

мулы (5-8):

(Axy)' = xy'+jx'y (5)

(Exy)' = xy (6)

(Ixy)' = j(xy)' (7)

(Oxy)' = j(xy')' (8)

Такой же результат может быть получен табличным методом,для чего

необходимо проинвертировать значения соответствующих силлогистических

функторов в табл.1-4.Для того,чтобы проверить силлогизм,можно выпол-

нить алгоритмы "Осташ-Т" и "ТВАТ".

Проведем выборочную проверку силлогистики Аристотеля.

Фигура 1.

1.1. AmxAym -> f(x,y) = mx'+jm'x+m'y+jmy'+f(x,y) = 1

-----T------¬ xy

m L=========+---------- ¦ xy ¦f(x,y)¦ \ 00 01 11 10

x1 L==============+----- +----+------+ m \---T---T---T---¬

x2 L=========+---------- ¦ 00 ¦ 1 ¦ 0 ¦ ¦ 1 ¦ 1 ¦ j ¦

y1 L======+------------- ¦ 01 ¦ 0 ¦ +---+---+---+---+

y2 L=========+---------- ¦ 10 ¦ i ¦ 1 ¦ 1 ¦ 1 ¦ ¦ j ¦

¦ 11 ¦ 1 ¦ L---+---+---+----

L----+-------

Скалярные диаграммы и алгоритм "Осташ-С" дали одинаковый ре-

зультат:f(x,y) = xy+x'y'+ixy' = Ayx.

1.2. AmxEym -> f(x,y) = mx'+jm'x+my+f(x,y) = 1(i)

-----T------¬ xy

m L======+------------- ¦ xy ¦f(x,y)¦ \ 00 01 11 10

x1 L==============+----- +----+------+ m \---T---T---T---¬

x2 L======+------------- ¦ 00 ¦ i ¦ 0 ¦ ¦ ¦ j ¦ j ¦

y1 L---------------+===- ¦ 01 ¦ i ¦ +---+---+---+---+

y2 L-------+===========- ¦ 10 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ ¦

y3 L-------+=====+------ ¦ 11 ¦ i ¦ L---+---+---+----

L----+-------

f(x,y) = xy'+i(xy')' = Ixy' = Oxy.

У Аристотеля этот модус считается "неправильным".

1.6. EmxEym -> f(x,y) = mx+my+f(x,y) = 1(i)

-----T------¬ xy

m L--------------+====- ¦ xy ¦f(x,y)¦ \ 00 01 11 10

x L=========+---------- +----+------+ m \---T---T---T---¬

y1 L----------+==+------ ¦ 00 ¦ 1 ¦ 0 ¦ ¦ ¦ ¦ ¦

y2 L=============+------ ¦ 01 ¦ i ¦ +---+---+---+---+

y3 L======+------------- ¦ 10 ¦ i ¦ 1 ¦ ¦ 1 ¦ 1 ¦ 1 ¦

¦ 11 ¦ i ¦ L---+---+---+----

L----+-------

f(x,y) = x'y'+i = Ix'y'(3).

Это тоже "неправильный" по Аристотелю модус.Очередная ошибка ве-

ликого логика.

1.7. EmxIym -> f(x,y) = mx+jm'y'+f(x,y) = 1(i)

m L=========+---------- -----T------¬ xy

x L--------------+====- ¦ xy ¦f(x,y)¦ \ 00 01 11 10

y1 L-----+======+------- +----+------+ m \---T---T---T---¬

y2 L----+==============- ¦ 00 ¦ i ¦ 0 ¦ j ¦ j ¦ j ¦ j ¦

y3 L====+--------------- ¦ 01 ¦ 1 ¦ +---+---+---+---+

y4 L----+===========+--- ¦ 10 ¦ i ¦ 1 ¦ j ¦ ¦ 1 ¦ 1 ¦

y5 L==================+- ¦ 11 ¦ i ¦ L---+---+---+----

L----+-------

f(x,y) = x'y+i(x'y)' = Ix'y.

У Аристотеля получено заключение Оху.

Фигура 2.

2.1. AxmAym -> f(x,y) = m'x+jmx'+m'y+jmy'+f(x,y) = 1(i)

m L=========+---------- -----T------¬ xy

x1 L====+--------------- ¦ xy ¦f(x,y)¦ \ 00 01 11 10

x2 L=========+---------- +----+------+ m \---T---T---T---¬

y1 L=======+------------ ¦ 00 ¦ 1 ¦ 0 ¦ ¦ 1 ¦ 1 ¦ 1 ¦

y2 L===+---------------- ¦ 01 ¦ i ¦ +---+---+---+---+

y3 L=========+---------- ¦ 10 ¦ i ¦ 1 ¦ j ¦ j ¦ j ¦ j ¦

y4 L----+====+---------- ¦ 11 ¦ i ¦ L---+---+---+----

L----+-------

f(x,y) = x'y'+i(x'y')' = Ix'y'.

Этот "неправильный" по Аристотелю модус также оказался правильным.

2.7. ExmIym -> f(x,y) = mx+j(my)'+f(x,y) = 1(i)

-----T------¬ xy

m L=========+---------- ¦ xy ¦f(x,y)¦ \ 00 01 11 10

x L--------------+====- +----+------+ m \---T---T---T---¬

y1 L================+--- ¦ 00 ¦ i ¦ 0 ¦ j ¦ j ¦ j ¦ j ¦

y2 L===========+-------- ¦ 01 ¦ 1 ¦ +---+---+---+---+

y3 L-----+=============- ¦ 10 ¦ i ¦ 1 ¦ j ¦ ¦ 1 ¦ 1 ¦

y4 L===+---------------- ¦ 11 ¦ i ¦ L---+---+---+----

L----+-------

f(x,y) = x'y+i(x'y)' = Ix'y.

У Аристотеля этот модус имеет вид EIO.

Фигура 3.

3.2. AmxEmy -> f(x,y) = mx'+jm'x+my+f(x,y) = 1(i)

-----T------¬ xy

m L=========+---------- ¦ xy ¦f(x,y)¦ \ 00 01 11 10

x1 L============+------- +----+------+ m \---T---T---T---¬

x2 L=========+---------- ¦ 00 ¦ i ¦ 0 ¦ ¦ ¦ j ¦ j ¦

y1 L--------------+====- ¦ 01 ¦ i ¦ +---+---+---+---+

y2 L----------+========- ¦ 10 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ ¦

y3 L---------+=+-------- ¦ 11 ¦ i ¦ L---+---+---+----

L----+-------

f(x,y) = xy'+i(xy')' = Ixy'.

У Аристотеля этот модус - "неправильный".

3.5. EmxAmy -> f(x,y) = mx+my'+f(x,y) = 1(i)

-----T------¬

m L=========+---------- ¦ xy ¦f(x,y)¦ xy

x L------------+======- +----+------+ \ 00 01 11 10

y1L=========+---------- ¦ 00 ¦ i ¦ m \---T---T---T---¬

y2L==============+----- ¦ 01 ¦ 1 ¦ 0 ¦ ¦ j ¦ j ¦ ¦

y3L=========+--+======- ¦ 10 ¦ i ¦ +---+---+---+---+

¦ 11 ¦ i ¦ 1 ¦ 1 ¦ ¦ 1 ¦ 1 ¦

L----+------- L---+---+---+----

f(x,y) = x'y+i(x'y)' = Ix'y.

"Правильный" модус - EAO.

3.13.OmxAmy -> f(x,y) = j(mx')'+my'+jm'y+f(x,y) = 1(i)

m L=========+---------- -----T------¬ xy

x1 L-------------+=====- ¦ xy ¦f(x,y)¦ \ 00 01 11 10

x2 L----+==============- +----+------+ m \---T---T---T---¬

x3 L=====+-------------- ¦ 00 ¦ i ¦ 0 ¦ j ¦ j ¦ j ¦ j ¦

y1 L=============+------ ¦ 01 ¦ 1 ¦ +---+---+---+---+

y2 L=========+---------- ¦ 10 ¦ i ¦ 1 ¦ 1 ¦ ¦ j ¦ 1 ¦

y3 L=========+---+=====- ¦ 11 ¦ i ¦ L---+---+---+----

L----+-------

f(x,y) = Ix'y.

"Правильный" модус - OAO.Очередная ошибка классической логики.

Фигура 4.

4.1. AxmAmy -> f(x,y) = m'x+jmx'+my'+f(x,y) = 1

m L=========+---------- -----T------¬ xy

x1 L====+--------------- ¦ xy ¦f(x,y)¦ \ 00 01 11 10

x2 L=========+---------- +----+------+ m \---T---T---T---¬

y1 L============+------- ¦ 00 ¦ 1 ¦ 0 ¦ ¦ j ¦ 1 ¦ 1 ¦

y2 L=========+---------- ¦ 01 ¦ i ¦ +---+---+---+---+

¦ 10 ¦ 0 ¦ 1 ¦ 1 ¦ j ¦ ¦ 1 ¦

¦ 11 ¦ 1 ¦ L---+---+---+----

L----+-------

f(x,y) = x'y'+xy+ix'y = Axy.

Грубейшая ошибка классической логики,которая настаивает на модусе

AAI.

4.5. ExmAmy -> f(x,y) = mx+my'+jm'y+f(x,y) = 1(i)

-----T------¬ xy

m L=========+---------- ¦ xy ¦f(x,y)¦ \ 00 01 11 10

x L--------------+====- +----+------+ m \---T---T---T---¬

y1L================+--- ¦ 00 ¦ i ¦ 0 ¦ ¦ j ¦ j ¦ ¦

y2L=========+---------- ¦ 01 ¦ 1 ¦ +---+---+---+---+

y3L=========+---+=====- ¦ 10 ¦ i ¦ 1 ¦ 1 ¦ ¦ 1 ¦ 1 ¦

¦ 11 ¦ i ¦ L---+---+---+----

L----+-------

f(x,y) = Ix'y.

"Правильный" модус EAO - очередная ошибка классической логики.

В результате получим следующие правильные модусы:

1-я фигура: AAA,AEO,AII,AOI,EAE,EEI,EII,EOI,IEO,OEI.

2-я фигура: AAI,AEE,AII,AOI,EAE,EEI,EII,IEO,OAO.

3-я фигура: AAI,AEI,AII,AOO,EAI,EEI,EII,EOI,IAI,IEO,OAI,OEI.

4-я фигура: AAA,AEE,EAI,EEI,EII,EOI,IAI,IEI.

Полученные результаты очевидны,однако в большей своей части дан-

ные модусы не совпадают с традиционными "правильными" силлогизмами[8].

Пример.

В замечательной книге известного автора и политического легендар-

ного деятеля России начала 20-го века В.В.Шульгина "Что нам в них не

нравится"(М.:"Хорс",1992) на стр.210 есть интересный пример применения

классической силлогистики для решения спорного вопроса.

"...Карл Маркс плох,говорю я, - большая посылка. Карл Маркс - ев-

рей, - малая посылка. Вывод:еврей - плох,не годится в качестве руково-

дителя."

Прав ли автор? Здравый смысл не согласен с таким выводом. Прове-

рим формально по алгоритму ИЭИ силлогизм В.В.Шульгина.

Карл Маркс - m

плохой - x

еврей - y

M = AmxAmy = (m'+x)(m'+y) = m'+xy

f(x,y) = xy+i = Ixy(3)

Таким образом,мы получили следующее заключение (в Аристотелевом

базисе):"Некоторые евреи - плохие люди". Такой вывод справедлив для

любой нации,хотя с позиции здравого смысла здесь нельзя сделать ника-

кого заключения. Следовательно, В.В.Шульгин ошибся в силлогистике.

Соотношения (1) - (4) описывают аристотелевскую логику,которая не

соответствует требованиям,предъявленным русским ученым Васильевым

Н.А.[6] к частным суждениям с научной точки зрения и с позиции логики

здравого смысла.Поэтому логика Аристотеля-Жергонна представляет инте-

рес с чисто научно-исторической точки зрения.

Некоторые дополнительные аспекты проблем современной силло-

гистики изложены в [13].

Домашнее задание.

1.Проверить все "правильные" Аристотелевы модусы на основе базиса

Аристотеля-Жергонна.

2.Найти заключения для AxmImy',EmxIm'y,AmxIm'y',Am'xIxy.

Общеразговорная силлогистика

ЛЕКЦИЯ 10

Общеразговорная силлогистика.

Общеразговорная силлогистика построена на базисе Васильева Н.А.

Силлогистические функторы Аху и Еху в этом базисе такие же,как и в

русском:

Axy = (xy')' = x'+y

Exy = (xy)' = x'+y'.

Для функтора Ixy в базисе Васильева не удалось найти аналитичес-

кое представление,поэтому изобразим этот функтор при помощи скалярных

диаграмм.

x' x

----------===========

y' y y'

-----==========------

В базисе Васильева справедливо соотношение

Ixy -> Ixy' -> Ix'y' -> Ix'y.

Отыскание заключения в общеразговорной силлогистике возможно лишь

с помощью графического алгоритма "ТВАТ".Рассмотрим некоторые модусы.

1.9.ImxAym -> f(x,y)

m =======-------- -----T---¬

x ----=======---- ¦ xy ¦Ixy¦

y1===------------ +----+---+

y2=====---------- ¦ 00 ¦ 1 ¦

y3----===-------- ¦ 01 ¦ i ¦

¦ 10 ¦ 1 ¦

¦ 11 ¦ i ¦

L----+----

f(x,y) = y'+iy = Ixy'(7).

2.9.IxmEym -> f(x,y)

m =======-------- -----T---¬

x ----=======---- ¦ xy ¦Ixy¦

y1------------=== +----+---+

y2--------======- ¦ 00 ¦ 1 ¦

y3--------===---- ¦ 01 ¦ i ¦

¦ 10 ¦ 1 ¦

¦ 11 ¦ i ¦

L----+----

f(x,y) = y'+iy = Ixy'(7).

Синтез силлогизмов в базисе Васильева более прост по сравнению с

другими базисами.Для модусов,содержащих частноотрицательные посыл-

ки,синтез заключений невозможен,поскольку не существует графического

представления частноотрицательного суждения.В результате графического

синтеза по алгоритму "ТВАТ" были получены следующие модусы.

1-я фигура:

AAA,AEI[3],AII[3],EAE,EEI[3],EII[3],IAI[3],IEI[3].

2-я фигура:

AAI[3],AEE,AII[3],EAE,EEI[3],IAI[3],IEI.

3-я фигура:

AAI,AEI[3],AII[3],EAI[3],EEI[3],EII[3],IAI,IEI[3].

4-я фигура:

AAA,AEE,AII[3],EAI[3],EEI[3],EII[3],IAI[3],IEI[3].

Индекс в скобках указывает номер базиса заключения.Отсутствие ин-

декса указывает на русский базис заключения.

Рассмотрим несколько примеров применения русской логики к анализу

содержательных силлогизмов.

Пример 1.

В книге Дж.Макаллистера "Искусственный ин-

теллект и Пролог на микро-ЭВМ"(М.:1990,стр.33) приводится рассуждение:

Все собаки(m) имеют хвосты(x)

Том(y) - это человек(z).

Автор пытается сделать вывод,что "Том не имеет хвоста".Но эти по-

сылки не имеют среднего термина,поэтому их нельзя считать силлогиз-

мом,т.е. никакого заключения нельзя получить в принципе.Автор соглаша-

ется с таким выводом,но добавляет 3-ю посылку:"Том не является соба-

кой".Из этого тоже нельзя сделать заключения,что Том бесхвостый.Но ав-

тор и теперь пытается получить заключение:"Правда,в соответствии с

внутренней логикой программы такого рода умозаключения могут быть раз-

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

знания об объектах.Тогда,поскольку нет никакой информации о том,что

Том - это собака и известно,что только собаки имеют хвосты,можно сде-

лать вывод

"Том не имеет хвоста".

Здесь автор путает силлогистические функторы "все" и "только".Это

совсем не одно и то же.Такие ляпсусы не к лицу апологету логического

программирования.

Решим эту задачу по алгоритму "ТВАТ".

Все собаки(m) имеют хвосты(x)

Том(y) - это человек(z)

Том(y) не является собакой(m).

m =======-------- -----T---¬

x ===========---- ¦ xy ¦Ixy¦

z1------------=== +----+---+

z2--------======= ¦ 00 ¦ 1 ¦

y1--------=------ ¦ 01 ¦ i ¦

y2-----------=--- ¦ 10 ¦ 1 ¦

y3-------------=- ¦ 11 ¦ i ¦

L----+----

f(x,y) = y'+iy = Ixy'(7).

Т.е. заключение имеет вид:"Некоторые не-Томы имеют хвосты".

Пример 2.

Все люди(m) смертны(x)

Некоторые люди(m) неграмотны(y)

--------------------------

f(x,y) = ?

Решение.

По алгоритму ИЭИ получим:

M = AmxImy(8) = (m'+x)&1 = m'+x

f(x,y) = x+i = Ixy(5)

Казалось бы,все верно.Проверим результат с помощью алгоритма ТВАТ.

Универсумом являются существа,в том числе и бессмертные(боги).Бу-

дем считать богов грамотными.

m =======-------- -----T---¬

x ===========---- ¦ xy ¦Ixy¦

y ---========---- +----+---+

¦ 00 ¦ 1 ¦

¦ 01 ¦ 0 ¦

¦ 10 ¦ 1 ¦

¦ 11 ¦ 1 ¦

L----+----

f(x,y) = y'+x = Ayx

Результат превзошел наши ожидания:впервые нарушено правило:если

хотя бы одна посылка носит частный характер,то и заключение должно

быть частным.

Пример 3.

В предыдущем примере исключим богов из универсума.Тогда получим

следующее решение.

m =======-------- -----T---¬

x =============== ¦ xy ¦Ixy¦

y ---============ +----+---+

¦ 00 ¦ 0 ¦

¦ 01 ¦ 0 ¦

¦ 10 ¦ 1 ¦

¦ 11 ¦ 1 ¦

L----+----

f(x,y) = x = Ayx(4) = Ay'x(4)

Пример 4.

В силлогизме примера 2 будем считать богов неграмотными.Получим

третий вариант решения.

m =======-------- -----T---¬

x =======-------- ¦ xy ¦Ixy¦

y ---============ +----+---+

¦ 00 ¦ 0 ¦

¦ 01 ¦ 1 ¦

¦ 10 ¦ 1 ¦

¦ 11 ¦ 1 ¦

L----+----

f(x,y) = x+y = Ay'x = Ax'y

Заключение.

Правильный синтез силлогизмов предполагает выполнение следующих

условий:

1.Правильная формулировка посылок(силлогизм о сахаре,"Нек.живот-

ные - олени" и т.п. ляпсусы).

2.Строгий выбор базиса("англичане - трусы").

3.Выбор универсума("ромб-квадрат",примеры 2-4)

4.Учет всех необходимых условий("ромб-квадрат-прямоугольник").

5.Правильные модусы не всегда приводят к правильному реше-

нию,т.е. введение аппарата модусов является ошибкой.

6.Закон "частная посылка - частное заключение" не всегда коррек-

тен.

7.Все 4 классических правила посылок некорректны.

Домашнее задание.

1.Проверить все модусы на основе базиса Васильева.

2.Найти заключения для AxmImy',EmxIm'y,AmxIm'y',Am'xIxy для этого

же базиса.

Решeние логических уравнений

ЛЕКЦИЯ 11

Решeние логических уравнений

Под решением логического уравнения понимается преобразование ис-

ходного уравнения к явному виду относительно одной из переменных.Этой

проблемой занимались Дж.Буль и русский ученый Порецкий Платон Сергее-

вич.

Платон Сергеевич Порецкий родился 3 октября 1846 г. в Елизаветг-

раде Херсонской губернии в семье военного врача.В 1870 г.закончил физ-

матфак Харьковского университета.Был оставлен прфессорским стипендиа-

том на кафедре астрономии.С 1876 г. избирается астрономом-наблюдателем

Казанского университета.За 1876-79 гг. Порецкий опубликовал 2 тома

наблюдений на меридианном круге.Несмотря на слабое здоровье участвует

в общественной жизни университета,являясь секретарем секции физмат.

наук,казначеем,а затем и пожизненным членом.Редактирует либеральную

газету "Телеграф".

За астрономические исследования в 1886 г. ему присуждается ученая

степень доктора астрономии и звание приват-доцента.

П.С.Порецкий умер в 9 августа 1907 г. в с.Жоведь Гродненского

уезда Черниговской губернии,куда переехал из Казани в 1889 г.,будучи

уже тяжелобольным.

Принимал заочное участие в ряде международных научных конгрес-

сов,вел активную переписку как с русскими,так и иностранными учены-

ми.Смерть застала его за неоконченной статьей по логике.

Логикой занимается с 1880 г. В 1881 г. выходит его работа "Изло-

жение основных начал мат.логики ...". В 1884 г. издает свой большой

труд "О способах решения логических равенств и об обратном способе ма-

тематической логики",где излагает теорию логических равенств,закон

форм посылок,закон замещения системы посылок одной посылкою,закон раз-

ложения посылок на элементы,закон исключения терминов из посылок,закон

умозаключений(синтез),закон причин.

Работа П.С.Порецкого "Из области математической логики"(1902) яв-

ляется обобщением классической силлогистики.Синтезируется несколько

заключений из заданных посылок.

При решении системы логических уравнений вначале определяется так

называемая полная единица задачи (системы),а потом отыскивается реше-

ние уравнения относительно заданных переменных.Поскольку известные ме-

тоды решения логических уравнений[5,17] сложны для восприятия и черес-

чур громоздки,попробуем найти решение этой проблемы с помощью таблиц

истинности.В приводимом ниже примере считаем полную единицу системы(M)

известной.

Пример 1.

Дано: M = ab + cd = 1

Найти: d = f(a,b,c)

Решение.

На основании исходного логического уравнения полной единицы стро-

им таблицу истинности для разрешенных наборов(табл.2),т.е. тех набо-

ров,на которых исходное уравнение имеет решение.Перенеся столбцы a,b,c

из табл.2 в качестве входных наборов,а столбец d - в качестве значений

искомой функции, получим таблицу истинности (табл.3) для d = f(a,b,c).

Табл.2 Табл.3

----------T---¬ --------T---¬

¦ d c b a ¦ M ¦ ¦ c b a ¦ d ¦

+---------+---+ +-------+---+

¦ 0 0 1 1 ¦ 1 ¦ -----> ¦ 0 1 1 ¦ 0 ¦

¦ 0 1 1 1 ¦ 1 ¦ ¦ 1 1 1 ¦ 0 ¦

¦ 1 0 1 1 ¦ 1 ¦ ¦ 0 1 1 ¦ 1 ¦

¦ 1 1 1 1 ¦ 1 ¦ ¦ 1 1 1 ¦ 1 ¦

¦ 1 1 0 0 ¦ 1 ¦ ¦ 1 0 0 ¦ 1 ¦

¦ 1 1 0 1 ¦ 1 ¦ ¦ 1 0 1 ¦ 1 ¦

¦ 1 1 1 0 ¦ 1 ¦ ¦ 1 1 0 ¦ 1 ¦

L---------+---- L-------+----

По табл.3 заполним карту Карно (рис.1),откуда после минимизации

получим следующие соотношения(3,4).Если на некотором наборе функция

принимает значение как 0,так и 1,то в соответствующую клетку карты

Карно вписываем символ i.Если на каком-либо наборе функция не опреде-

лена,то в сооветствующую клетку карты Карно вносим значение j.

ba

\ 00 01 11 10 Для четырехзначной логики имеем:

c \---T---T---T---¬

0 ¦ j ¦ j ¦ i ¦ j ¦ d=cb'+ca'+iba+j(c'b'+c'a')

+---+---+---+---+

1 ¦ 1 ¦ 1 ¦ i ¦ 1 ¦

L---+---+---+----

Рис.1

Клетки карты Карно с координатами 011 и 111 заполнены значением

i,т.к. на этих наборах d принимает значения как 0,так и 1.Наборы

000,001 и 010 в табл.3 отсутствуют,поскольку при таких значениях аргу-

ментов исходное уравнение не имеет решения,поэтому соответствующие

клетки карты Карно заполнены символом j.

Автор использует менее трудоемкий,но более сложный для восприятия

метод.Пpи этом вначале в КК вписываются значения i,а потом все осталь-

ное.

----------T---¬ --------T---¬

¦ d c b a ¦ M ¦ ¦ c b a ¦ d ¦

+---------+---+ +-------+---+

¦ - - 1 1 ¦ 1 ¦ -----> ¦ - 1 1 ¦ i ¦

¦ 1 1 - - ¦ 1 ¦ ¦ 1 - - ¦ 1 ¦

L---------+---- L-------+----

ba

\ 00 01 11 10 Для четырехзначной логики имеем:

c \---T---T---T---¬

0 ¦ j ¦ j ¦ i ¦ j ¦ d=c(b'+a')+iba+jc'(b'+a')

+---+---+---+---+

1 ¦ 1 ¦ 1 ¦ i ¦ 1 ¦

L---+---+---+----

Пример 2.

Рассмотрим 1-ю задачу Порецкого[17].Между птицами данного зоосада

существуют 5 отношений:

1.Птицы певчие - крупные или обладающие качеством Y.

2.Птицы,не имеющие качества Y - или не крупны,или не имеют ка-

чества X.

3.Птицы певчие в соединении с крупными объединяют всех птиц с ка-

чеством X.

4.Каждая не-крупная птица есть или певчая,или обладающая качест-

вом X.

5.Между птиц с качеством X совсем нет таких птиц с качеством

Y,которые не будучи певчими,были бы крупны.

Определить,были ли птицы качества X певчие или нет.Узнать то же в

отношении птиц качества Y.Найти,были ли среди птиц качества X птицы

качества Y и наоборот.Т.е. требуется найти M(x,s),M(y,s),M(x,y).

Решение.

Пусть X - птицы качества X,

Y - птицы качества Y,

S - певчие птицы,

G - крупные птицы.

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

уравнениями:

1.s=(g+y)s;

2.y'=(g'+x')y';

3.x(s+g)=x;

4.g'=(s+x)g';

5.xys'g=0.

Уравнения Порецкий через эквивалентность приводит к единичной

форме:

1.g+y+s'

2.g'+x'+y

3.s+g+x'

4.s+g+x

5.x'+y'+s+g'

Основываясь на введенном нами русском базисе,можно получить эти

же соотношения более простым путем:

1.As(g+y) = s'+g+y

2.Ay'(g'+x') = y+g'+x'

3.Ax(s+g) = x'+s+g

4.Ag'(s+x) = g+s+x

5.Ex(ys'g) = x'+y'+s+g'

Однако восхищает красота решения задачи П.С.Порецким без привле-

чения силлогистики.Фактически русский ученый,сам того не ведая,впервые

в мире вывел соотношения для силлогистических функторов Аху и Еху.

Современная силлогистика до сих пор не замечает и не использует этих

результатов великого русского логика.Кроме того,данная система уравне-

ний представляет из себя 5 посылок силлогизма,точнее сорита.Таким об-

разом,решив систему уравнений,Порецкий впервые в мире синтезировал

аналитически заключение силлогизма(сорита).

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

конъюнкция всех левых частей системы логических уравнений .Эту рутин-

ную операцию можно заменить на менее утомительную процедуру построения

дизъюнкции нулей.Получим систему:

1.g'y's=0

2.gxy'=0

3.g's'x=0

4.g's'x'=0

5.gs'xy=0

Полный логический нуль системы равен дизъюнкции всех левых частей

системы логических уравнений .Проведем решение задачи Порецкого с ис-

пользованием карты Карно.Заполним карту Карно нулями в соответствии с

нулевыми термами системы ,а в оставшиеся клетки впишем единицы

(рис.2).Тогда минимальная дизъюнктивная нормальная форма (МДНФ) полной

логической единицы всей задачи примет вид:

xy

M=sy+gx' (8) \ 00 01 11 10

gs \----T----T----T----¬

00¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦

+----+----+----+----+

01¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦

+----+----+----+----+

11¦ 1 ¦ 1 ¦ 1 ¦ 0 ¦

+----+----+----+----+

10¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦

L----+----+----+-----

Рис.2

Из полученной формулы для М легковыводятся следующие соотношения:

M(x,s) = s+x' = Axs

M(y,s) = sy+i = Isy(3)

M(x,y) = y+x' = Axy

Для ответа на вопросы Порецкого в заданной им форме поступим нес-

колько иначе.Выпишем из карты Карно (рис.2) все единичные термы в виде

таблицы истинности (табл.4).По табл.4 построим табл.5 для x =

f1(g,s),табл.6 для y = f2(g,s) и табл.7 для y = f3(x).Если на ка-

ком-либо наборе функция принимает значение как 0,так и 1,то в соот-

ветствующую клетку карты Карно вписываем i.Если какой-либо набор от-

сутствует,то для этого набора в карту Карно вносим значение j при че-

тырехзначной логике или произвольное(по аналогии с двузначной логи-

кой)-при трехзначной. Карты Карно для табл.5,6 и 7 представлены на

рис.3,4 и 5 соответственно.

Табл.4 Табл.5 Табл.6 Табл.7

-------T---¬ ----T---¬ ----T---¬ ----T---¬

¦ gsxy ¦ M ¦ ¦ s ¦ x ¦ ¦ s ¦ y ¦ ¦ x ¦ y ¦

+------+---+ +---+---+ +---+---+ +---+---+

¦ 0101 ¦ 1 ¦ ¦ 1 ¦ 0 ¦ ¦ 1 ¦ 1 ¦ ¦ 0 ¦ 1 ¦

¦ 0111 ¦ 1 ¦ ¦ 1 ¦ 1 ¦ ¦ 1 ¦ 1 ¦ ¦ 1 ¦ 1 ¦

¦ 1101 ¦ 1 ¦ ----> ¦ 1 ¦ 0 ¦ ¦ 1 ¦ 1 ¦ ¦ 0 ¦ 1 ¦

¦ 1111 ¦ 1 ¦ ¦ 1 ¦ 1 ¦ ¦ 1 ¦ 1 ¦ ¦ 1 ¦ 1 ¦

¦ 1000 ¦ 1 ¦ ¦ 0 ¦ 0 ¦ ¦ 0 ¦ 0 ¦ ¦ 0 ¦ 0 ¦

¦ 1001 ¦ 1 ¦ ¦ 0 ¦ 0 ¦ ¦ 0 ¦ 1 ¦ ¦ 0 ¦ 1 ¦

¦ 1100 ¦ 1 ¦ ¦ 1 ¦ 0 ¦ ¦ 1 ¦ 0 ¦ ¦ 0 ¦ 0 ¦

L------+---- L---+---- L---+---- L---+----

\s 0 1 \s 0 1 \x 0 1

\---T---¬ \---T---¬ \---T---¬

¦ 0 ¦ i ¦ ¦ i ¦ i ¦ ¦ i ¦ 1 ¦

L---+---- L---+---- L---+----

Рис.3 Рис.4 Рис.5

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

нений :

x = is

y = i

y = x + ix' = (x + ix) + ix' = x + i

Результаты,полученные Порецким :

x = xs

y = g's + gy

y = y + x

Результаты Порецкого менее корректны,поскольку он использует

2-значную(с некоторой натяжкой ее можно считать псевдо-трехзначной:

здесь в качестве i выступает символ функции,встречающийся в правой

части уравнений) логику вместо 4-значной .Метод Порецкого хорошо сра-

ботал на общих посылках,но он абсолютно непригоден для частных посылок

и частных заключений.

Основываясь на примерах 1 и 2 составим алгоритм решения системы

логических уравнений.

Алгоритм "Селигер".

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

2.Заполнить карту Карно нулями в соответствии с термами левых

частей исходной системы уравнений,а в оставшиеся клетки вписать едини-

цы.Эти единичные термы представляют собой СДНФ полной единицы системы.

3.Произвести минимизацию совокупности единичных термов.Полученное

соотношение представляет МДНФ уравнения полной единицы системы.

4.Построить сокращенную (только для единичных термов) таблицу ис-

тинности уравнения полной единицы и выписать из нее все значения вход-

ных и выходных переменных в виде частных таблиц истинности для искомых

фумкций.

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

Используя алгоритм "Селигер",выясним смысл импликации M = x -> y

= x'+y.Решая это уравнение относительно у,получим:y = x+ix'.Откуда

следует физический смысл импликации:"Если х-истинно,то истинно и

у".Или более традиционная формулировка:"Из истинности х следует истин-

ность у".Кроме того,это же уравнение описывает функтор Axy. Таким об-

разом Порецкий в своей 1-й задаче нашел впервые в мире аналитическое

решение для общего сорита,т.е. сорита,имеющего общие посылки и заклю-

чение.

Домашнее задание ДЗ5

Задача Дж.Буля.

Дано: x = y(zw' + z'w)

Найти: y = f(x,z,w),где

x - ответственные существа,

y - разумные существа,

z - обладающие свободой действия,

w - добровольно пожертвовавшие свободой.

Результат,полученный Булем,выражается соотношением .

y = x(zw' + z'w) + vx'z'w'

Решение.

В соответствии с алгоритмом "Селигер" приведем к единичной форме

.сходное уравнение (1) с помощью формулы эквивалентности:

M = xy(zw'+z'w)+x'(y(zw'+z'w))' = xyzw'+xyz'w+x'y'+x'z'w'+x'zw = 1 (2)

На основании логического уравнения (2) строим таблицу истинности

для разрешенных наборов(табл.2),из которой следует таблица истинности

(табл.3) для y = f(x,z,w).Кстати,табл.3 может быть получена непосредс-

твенно из таблицы истинности для уравнения (1).

Табл.2 Табл.3

----------T---¬ --------T---¬

¦ x y z w ¦ M ¦ ¦ x z w ¦ y ¦

+---------+---+ +-------+---+

¦ 1 1 1 0 ¦ 1 ¦ -----> ¦ 1 1 0 ¦ 1 ¦

¦ 1 1 0 1 ¦ 1 ¦ ¦ 1 0 1 ¦ 1 ¦

¦ 0 0 - - ¦ 1 ¦ ¦ 0 - - ¦ 0 ¦

¦ 0 - 0 0 ¦ 1 ¦ ¦ 0 0 0 ¦ i ¦

¦ 0 - 1 1 ¦ 1 ¦ ¦ 0 1 1 ¦ i ¦

L---------+---- L-------+----

На наборах 000 и 011 искомая функция y может принимать любые зна-

чения (состояние i) без нарушения соотношения (2).На наборах 100 и 111

функция не имеет места,т.е. не может быть никогда.По табл.3 заполним

карту Карно (рис.1),откуда после минимизации получим следующие соотно-

шения(3,4).Здесь и далее апостроф означает отрицание аргумента или

функции.

zw

\ 00 01 11 10

x \---T---T---T---¬

0 ¦ i ¦ 0 ¦ i ¦ 0 ¦

+---+---+---+---+

1 ¦ j ¦ 1 ¦ j ¦ 1 ¦

L---+---+---+----

Рис.1

Для четырехзначной логики имеем:

y = x(zw'+z'w) + (ix'+jx)(z'w'+zw) (3)

Для трехзначной логики результат выглядит проще:

y = x + ix'(z'w'+zw) (4)

Blog

План Литература. W145 В. И. Лобанов. Инженерные методы разработки цифровых уст- 4/231(цптб) ройств М.: 1977. Информационный листок N% 54-87 В. И. Лобанов Метод бу