Реш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)