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