Русская логика – индикатор интеллекта (стр. 2 )

Автор рекомендует к обязательному изучению главы 1 из части 1 и 1 - 3 из части 2. Если у школьников вызовет затруднение вычисление вероятностей вариантов заключения, то эту процедуру можно опустить: она не имеет отношения к качеству мышления. В главе 10 части 2 могут возникнуть вопросы по 4-значной и 6-значной комплементарным логикам. Школьникам можно не отвлекаться на алгебру этих логик, поскольку для решения логических уравнений автором параллельно предложен метод, основанный на двоичной алгебре. Если не рассматривать вышеперечисленные вопросы, то все разделы вполне можно излагать четвероклассникам. В крайнем случае для них можно использовать [41]. Рекомендуется обратить особое внимание на разделы, выделенные в оглавлении полужирным курсивом: в них излагается совершенно новые методы решения проблем математической логики.

Из всего перечня литературы достаточно проработать сначала брошюру «Русская логика в информатике»[41], а затем – монографию «Русская вероятностная логика» [36]. Автор надеется, что предлагаемое вниманию читателей пособие сможет заменить для наиболее настойчивых любителей математики все предыдущие работы. Студенты техникумов, институтов и академий, старшеклассники школ, гимназий и лицеев легко справлялись с этой немудрёной наукой. Ученики 5-го класса нематематической СШ №3 г. Москвы тоже воспринимали РЛ с интересом и пониманием. Лекции по РЛ в 2007г. были записаны в Современной гуманитарной академии и транслировались по каналу СГУ-ТВ спутникового телевидения на весь бывший Советский Союз. Вполне возможно, что эта трансляция продолжается и сегодня: у автора нет спутниковых телеканалов. Начиная с 1998г., апробация РЛ происходила на конференциях, конгрессах, в том числе и международных, на семинарах и непосредственно в классах и аудиториях. Основные работы автора переведены за рубежом. За державу будет обидно, если РЛ вернётся к нам в зарубежной упаковке. Для преподавателей, собирающихся внедрить РЛ в образование, готов ответить на все вопросы. Мой электронный адрес для них – e-mail: *****@***ru.

Автор родился и вырос в Осташкове, на берегу озера Селигер, на родине Леонтия Филипповича Магницкого, основателя Российской математики. Поэтому он не мог не упомянуть этого города и самого озера хотя бы в названиях алгоритмов. Мне кажется, что не случайно именно осташи продолжили работы и создали Русскую вероятностную логику.

Замысел книги родился благодаря зав. проблемной лаб. ЭВМ МГУ , ознакомившему автора с проблемами современной логики. Путёвку в жизнь новой науке дал научный сотрудник Института проблем управления (ИПУ) Пётр Петрович Вороничев. Русская логика была впервые внедрена в Тушинском вечернем авиационном техникуме (ТВАТ). Автор выражает свою глубокую признательность директору ТВАТ и завучу , оказавших всевозможное содействие в организации учебного процесса. Автор изъявляет сердечную благодарность всем единомышленникам, разместившим материалы РЛ на своих сайтах. Особую признательность необходимо высказать в адрес Евгения Антоновича Капустина, безвозмездно создавшего сайт http://***** и заочно научившего автора методам его наполнения. Признание автора Человеком года-2011 г. не могло бы произойти без рекомендаций , Президента Интеллектуального Международного Фонда «Перестройка Естествознания».

«И может собственных Платонов

И быстрых разумом Невтонов

Российская земля рождать.»

.

ЧАСТЬ 1

Введение.

Под современным определением интеллекта понимается способность к осуществлению процесса познания и к эффективному решению проблем, в частности при овладении новым кругом жизненных задач. Согласно академику Н. Н. Моисееву, интеллект — это, прежде всего, целеполагание, планирование ресурсов и построение стратегии достижения цели. Есть основания полагать, что зачатками интеллекта обладают животные, и уже на этом уровне их интеллект посредством механизмов целеполагания и достижения целей влиял и влияет на эволюцию животных. Изучением интеллекта животных занимается сравнительно молодая область науки, когнитивная этология.

Интеллект — это способность находить алгоритм решения ранее неизвестных задач (путь решения проблем).

Исходя из этого определения данная способность различается для разного рода задач. Например, коэффициент IQ показывает способность выдавать ответы, совпадающие с ответами автора теста IQ.

Интеллект — это способность планировать, организовывать и контролировать свои действия по достижению цели с учетом совпадения истины и блага.

Все эти описания приведены в Википедии. Осюда становится ясно, что никто не в состоянии дать чёткое определение интеллекта. Однако на уровне интуиции все понимают, как можно оценить интеллект. Интеллект – это не начитанность, не натасканность на решение стандартных задач. Шахматист – это не интеллектуал: его обыгрывает безмозглая ЭВМ. Вот что говорит Альфред Барков в своей работе «Интеллект»: «Честно признаюсь, что на чисто интуитивном уровне у меня всегда возникали сомнения относительно "качества" того интеллекта, который проявляется в шахматах. Ведь интеллект — это комплекс свойств иррационального характера, который, включая в себя в том числе врожденные инстинкты и приобретенные условные рефлексы, при создании шедевров искусства подключает к процессу весь накопленный мозгом пласт культуры». Барков задаётся вопросом: «Может ли интеллект чукотского оленевода превосходить суммарный интеллект шестерки "Что? Где? Когда?" и крупье?» И отвечает на него утвердительно. Телеигроки «интеллектуальных» шоу – это мартышки с арифмометром в голове: если в любую ЭВМ загрузить все энциклопедии, то она обыграет всех вместе взятых телеигроков.

Всевозможные тесты по определению IQ (см., например, Ф. Картер « IQ и личностные тесты» - М.: АСТ, 2010») абсолютно непригодны для решения заявленной задачи. Более всего автору симпатизирует определение интеллекта, приведённое в самом начале, а именно:

Интеллект — это способность находить алгоритм решения ранее неизвестных задач (путь решения проблем).

Поэтому, учитывая, что логика является наукой о мышлении, автор предлагает простое интеллектуальное тестирование. Русская логика (РЛ) является прекрасным индикатором бестолковости и измерителем интелекта. Знаний здесь требуется на уровне начальной школы, а всё остальное в освоении РЛ определяется интеллектом читателя. Каждый математик может самостоятельно с помощью РЛ оценить свои способности по 5-балльной системе:

·  не понял брошюру "Русская логика в информтике" – 2,

·  понял брошюру "Русская логика в информтике" - 3,

·  понял работы Порецкого, нашёл его принципиальные ошибки и разработал метод их нейтрализации - 4,

·  нашёл принципиальные ошибки в "Русской вероятностной логике"(а они есть) и создал метод их устранения - 5.

По данной методике интеллект автора РЛ оценивается на уровне «4». Автор сомневается в своей оценке интеллекта выдающихся русских математиков 20-го столетия, но и опровергнуть её не в состоянии. Каждый человек, а тем более учёный, обязан знать математическую логику. Но её не знает никто в мире. Порецкого являются фундаментальными для математической логики, поскольку в них решены все проблемы, поставленные Лейбницем, с которыми не справилось всё человечество за 25 веков. Математики, не знающие работ Порецкого, автоматически попадают в разряд невежд. Бестолочами они являются тоже по определению: ни один математик не возмутился кванторным исчислением, алгеброй множеств и логикой предикатов. Мне известен только один русский математик, знакомый с работой Порецкого. Марков-старший, блестящий учёный с мировым именем. Однако и он не понял результатов гениального русского логика. Маркова нельзя назвать невеждой, но из разряда бестолочей и неучей он, к сожалению, тоже не выпадает. Заглянем в книгу Э. Мендельсона "Введение в математическую логику", которую так нахваливает академик Адян тоже сплошь кванторы и кванторный вычисления. Это безмозглость и попугайство. Мендельсон не ссылается на Порецкого - значит, он невежда. Нет ни одной работы за последние 128 лет, в которой авторы разобрались бы с достижениями и Л. Кэрролла. Следовательно, все логики – невежды, неучи и бестолочи.

Предложенную оценку интеллектуальных способностей можно использовать при подборе кадров, особенно научных. Уже в VI веке в Китае были разрботаны тесты для определения уровня способности чиновников. Логикой должен владеть каждый образованный человек. Поскольку истинной логикой сегодня является только Русская логика, то её обязан изучить каждый чиновник, а тем более учёный. Одновременно по степени освоения РЛ мы получим информацию о интеллекте того или иного чиновника или учёного.

Когда незабвенный Аркаша Райкин, клоун и н. а. СССР, в «своих» интермедиях издевался над отличниками, то все понимали, что интеллект Аркаши ниже плинтуса, а по математике он наверняка был двоечником. . Разумеется, не из каждого круглого отличника вырастает гениальный учёный, но каждый учёный обязан быть отличником хотя бы в математической логике. Строго говоря, математики – это соль земли. Поэтому каждый государственный деятель обязан иметь математическое образование наряду с каким-либо гуманитарным. У автора складывается впечатление, что человечество деградирует: нет больше Ломоносовых, Менделеевых, Порецких. Мы уже опустились до того, что не понимаем достижений своих предшественников. Иногда мне заявляют, опровергая деградацию, что вот Лобанов выше Порецкого. Но это случилось лишь потому, что я стою на его плечах. Эволюционная теория Дарвина предполагает, что человек произошёл от обезьяны. Возможно, Дарвин, Аркашка Райкин и им подобные – потомки обезьян. Современная наука считает, что человек – результат генетических экспериментов высокоразвитых цивилизаций и, вероятнее всего, обезьяны – результат деградации человека. Поэтому, чтобы не превратиться в мартышек, нужно осваивать математику и в частности РЛ.

Основываясь на определении и оценке интеллекта по критериям РЛ, можно дать такое определение термина «интеллигент». Интеллигент – это человек, в котором гармонично сочетаются душевная чуткость, порядочность, культура, интеллект и образованность. Первые три качества не поддаются объективной оценке, интеллект мы уже научились определять. Осталось оценить образованность. Кто-то из классиков заявил, что без математики нет науки. А я добавлю, что без математики нет образования. Становится смешно, когда какого-нибудь полиглота, заядлого театрала, знатока искусств, пустомелю политолога или литературного критика считают образованным человеком. Следовательно, интеллигентами могут быть только инженеры и учёные, т. е. те, кого гуманитарии высокомерно называют технарями. Так называемая «творческая интеллигенция» к интеллигенции никакого отношения не имеет, поскольку не обладает ни интеллектом, ни образованностью. Истинными интеллигентами (этот термин существует только у русского народа) могут быть лишь русские инженеры и учёные.

А теперь попробуем ответить на вопрос, который был задан автору после прочтения доклада о РЛ в Военной Академии РВСН (Ракетных Войск Стратегического Назначения): «Зачем нужна математическая логика?». Ответов может быть много:

1.  Весь мир пытается её создать вот уже 25 веков.

2.  На её основе построена вся вычислительная техника и все электронные системы управления оборонного и народно-хозяйственного назначения.

3.  РЛ – индикатор интеллекта.

4.  РЛ – это и есть теория доказательства, которую невежды и неучи ищут до сих пор.

5.  РЛ – фундамент искусственного интеллекта(ИИ), стратегического направления науки 21-го века.

6.  Русских интеллектуалов много, а интеллектуального инструмента у них нет. РЛ – интеллектуальный инструмент.

7.  «Море» макулатуры по логике за 2011 г.(на полках «Московского дома книги» автор насчитал более 60 наименований учебных пособий и монографий ) говорит о возросшем интересе к указанной науке.

8.  Математика даёт иногда неожиданные плоды и спустя десятилетия.

9.  Логика – это Бог мыслящих (Л. Фейхтвангер).

10. Логика необходима потому, что одолеть её можно только с помощью логики (О. Хевисайд).

Когда прозвучал первый ответ, то тут же последовало возражение одного из офицеров: «Ну и что из того, что весь мир разрабатывает логику 25 веков! Весь мир те же 25 веков демонстрирует глупость и осваивает логику Аристотеля, но нашлись Ф. Бэкон, и , которые утверждают, что это бред сивой кобылы». Да и сам автор РЛ 50 лет обходился без классической логики, не испытывая никаких неудобств. Вполне возможно, что весь мир ошибается, считая необходимым освоение логики. Положа руку на сердце, все остальные мои обоснования необходимости логики тоже выглядят неубедительно. Кстати, именно этим вопросом задавался в учебном пособии «Элементы математической логики»(М.:МГУ,1984), но его обоснование необходимости изучения «науки о хороших способах рассуждения» выглядит ещё беспомощнее. Надеюсь, что читатели познакомятся с работами , считающего, что «логика стоит над математикой», и найдут более весомые аргументы в защиту науки о мышлении. Ну а пока будем верить древним грекам, русскому гению Ломоносову и талантливому немецкому математику Лейбницу, которые считали, что без знания логики не может быть ни образования, ни науки. Поскольку только математическая логика становится наукой(иначе она остаётся просто болтологикой), постарайтесь освоить Русскую логику, единственную на сегодня истинно математическую логику, науку 21-го века. «Не стыдно и не вредно не знать. Всего знать никто не может, а стыдно и вредно не хотеть знать того, что необходимо каждому человеку»(). Русская логика – это общечеловеческая математическая логика(когда РЛ признают во всём мире, тогда она потеряет национальный признак), поэтому ею должны овладеть учащиеся всех национальностей. Тем более её обязаны освоить русские студенты, преподаватели и учёные, что не только повысит их интеллектуальный уровень, но и подтвердит аксиому: «Россия – родина талантов».

Инженерная логика.

Глава первая

КОМБИНАЦИОННЫЕ ЛОГИЧЕСКИЕ ЦЕПИ

1.1 Основные положения алгебры логики

Анализ и синтез логических схем осуществляется на базе аппарата алгебры логики или булевой алгебры. Излагать весь аппарат не имеет смысла, так как в инженерной практике используются два-три закона алгебры логики.

В алгебре логики переменные могут принимать только два значения, 0 или 1. Для двух аргументов существуют 16 логических функций (операций, логических действий). Над переменными в основном производятся три логических действия: сложение, умножение, отрицание (инверсия), что соответствует функциям ИЛИ, И, НЕ. Все функции в булевой алгебре могут быть описаны с помощью таблицы истинности. В нижеследующих таблицах описаны функции И(f1), ИЛИ(f2),НЕ(f3).

Вместо функции И часто используется термин «конъюнкция», вместо функции ИЛИ - термин «дизъюнкция». Вместо функции НЕ употребляется термин «инверсия» или «отрицание». Для двоичной логики понятия «инверсия» и «отрицание» эквивалентны, но для многозначной дело обстоит иначе. По ЕСКД логические элементы, реализующие функции И(f1), ИЛИ(f2), НЕ(f3), изображаются так, как представлено на рисунке.

При написании логических формул для функции И используются следующие знаки: &, Λ, точка или ее отсутствие; для функции ИЛИ - V,+. Функция НЕ обозначается штрихом над аргументом. Мы для обозначения отрицания будем использовать апостроф. Таким образом, можно записать:

f1 = x2&x1 = x2 Λ x1 = x2x1

f2 = x2 V x1 = x2+x1

f3 = x’

Основные законы алгебры Буля.

Прежде, чем приступить к изложению основных законов алгебры логики, зафиксируем некоторые очевидные её положения.

1 + a = 1; 0 + a = a; a & 1 = a; a & 0 = 0; a + a’ = 1.

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

Как уже отмечалось, в булевой алгебре все операции осуществляются с логическими переменными и подчиняются законам алгебры логики. Опишем некоторые из них.

а) Переместительный закон

а + в = в + а ; ав = ва

б) Сочетательный закон

( а + в ) + с = а + ( в + с) ; ( ав )с = а(вс)

в) Распределительный закон

а( в + с ) = ав + ас ; а + вс = (а + в)( а + с )

г) Закон поглощения

а + ав = а( 1 + в ) = а ; а( а + в ) = а + ав = а

д) Закон склеивания

ав + ав’ = а ; ( а + в )(а + в’) = а

е) Идемпотентный закон

a + a = a; a & a = a

ё) Правила де Моргана

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

а + в + с + .... + z = ( а’в’с’...z’ )’

авс... = ( а’ + в’ + с’ + ... + z’ )’

Эти правила можно описать таким алгоритмом.

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

1) проинвертировать все слагаемые в отдельности;

2) заменить знаки дизъюнкции на знаки конъюнкции;

3) проинвертировать получившееся выражение.

Аналогично выполняется переход от логического произведения к логической сумме. В инженерной практике используются лишь правила де Моргана и закон склеивания (в виде карт Карно).

Свойства эквивалентности и неравнозначности.

Кроме основных функций И, ИЛИ, НЕ в алгебре логики часто используются функции равнозначности (эквивалентности) и неравнозначности (сумма по модулю 2).

Для обозначения этих функций используются следующие знаки : равнозначность - ~, сумма по модулю 2 - Å. Содержание этих функций отражено в таблице.

Из таблицы получаем:

f4 = а ~ в = а’в’ + ав

f5 = a Å в = а’в + ав’

Из таблицы видно, что

f4 = f5’ или f5 = f4’

Таким образом,

а’в’ + ав = ( ав’ + а’в )’ , или

а~в = ( а Å в )’ , а Å в = (а~в)’

Кроме того, автор обнаружил некоторые неожиданные свойства функций эквивалентности и неравнозначности:

ab’ Å a’в = ab’(a+b’)+(a’+b)a’b = ab’+a’b = а Å в.

ab Å a’в’ = ab(a+b)+(a’+b’)a’b’ = ав+a’b’ = а~в.

а Å a’ = a+a’ = 1.

(a Å в)(c+d) = (ac+ad) Å (bc+bd).

(a Å в) Å (c Åd) = (a Å c) Å (b Å d).

(a Å в) Å c = (ab+a’b’)c+(ab’+a’b)c’ = abc+a’b’c+ab’c’+a’bc’.

(a ~ b) ~ c = (ab+a’b’)c+(ab’+a’b)c’ = abc+a’b’c+ab’c’+a’bc’.

Т. е. удалось доказать, что

В то же время

Автором предложена гипотеза: сумма по модулю 2 для нечётного количества аргументов равна эквиваленции этих аргументов, а для чётного - инверсии эквиваленции тех же аргументов. Проверка с помощью САПР MAX+PLUS II не опровергла авторской гипотезы(см. нижепредставленные рисунки). Конечно, эту гипотезу можно доказать и аналитически, превратив её тем самым в закон. Или опровергнуть, приведя хотя бы один пример несоответствия. Предоставляю эту возможность наиболее дотошным математикам.

Кроме того, представляет определённый интерес мажоритарная функция 2 из 3.

Мажоритарность часто используется при создании высоконадёжных устройств и систем, в том числе и для построения спутниковых систем навигации, связи и мониторинга Земли и космического пространства.

Особое место в алгебре логики занимает функция импликации: a→b = a’+b. Физический смысл этого соотношения не может объяснить ни один академик. Он будет разъяснен в разделе «Базисы силлогистики».

Необходимо особо отметить свойство элементов И-НЕ и ИЛИ-НЕ. Это так называемый функционально полный базис: с помощью любого из этих элементов можно построить сколь угодно сложный компьютер, любую цифровую электронную схему управления.

1.2 Алгебра множеств.

Обычно множества изображаются в виде окружностей, эллипсов, прямоугольников, квадратов и других фигур. Однако переход от двумерности к одномерности, т. е. к скалярным диаграммам, позволяет существенно расширить возможности анализа и синтеза в алгебре множеств. Попробуем доказать идентичность функций и законов в алгебре логики и алгебре множеств.

Полная система булевских функций(z0 – z15) для двух аргументов(x, y) показана в таблице.

Эти функции для алгебры множеств можно представить с помощью скалярных диаграмм, которые предложены автором в качестве основного инструмента алгебры множеств. Здесь и далее в том случае, если аргумент или функция равны нулю, то они изображается тонкой линией, в противном случае – толстой.

Все вышеперечисленные законы булевой алгебры легко и просто доказываются с помощью алгебры множеств. Приведем, к примеру, графическое доказательство правила де Моргана для двух аргументов x+y = (x’y’)’.

Из скалярных диаграмм видно, что x+y = (x’y’)’. Далее будет показано, что минимизация функций в алгебре множеств не отличается от минимизации логических функций в алгебре логики. Таким образом, мы доказали, что алгебра логики и алгебра множеств идентичны.

В этом доказательстве не было никакой необходимости, поскольку аргументами в логике могут быть как отдельные переменные, так и множества. Следовательно, алгебра логики и алгебра множеств – синонимы. Создатель «алгебры множеств» и его последователи – невежды и бестолочи.

1.3. Синтез комбинационных схем

Синтез комбинационных схем можно проиллюстрировать решением простой задачи.

Задача 1.3.1.

Приёмная комиссия в составе трех членов комиссии и одного председателя решает судьбу абитуриента большинством голосов. В случае равного распределения голосов большинство определяется той группой, в которой оказался председатель приемной комиссии. Построить автомат для тайного голосования, обеспечивающий определение большинства голосов.

Решение.

Пусть f - функция большинства голосов. f = 1, если большинство членов комиссии проголосовало за приём абитуриента, и f = 0 в противном случае.

Обозначим через x4 голос председателя комиссии. Пусть x4 = 1, если председатель комиссии проголосовал за приём абитуриента. Аналогично представляются через x3, x2, x1 - голоса членов приёмной комиссии.

С учётом вышеуказанных допущений условие задачи можно однозначно представить в виде таблицы истинности.

Заполнение таблицы осуществляем с учётом того, что функция f является полностью определённой, т. е. она определена на всех возможных наборах переменных x1 - x4. Для n входных переменных существует N = 2n наборов переменных. В нашем примере N = 24 = 16 наборов.

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

Примечание. Здесь и далее под набором будем понимать конъюнкцию всех входных переменных. Существует множество научных определений для набора (конституента, терм, импликанта, минтерм и т. д.), но они только вносят путаницу.

Все наборы, на которых функция принимает значение 1 , будем называть единичными, или рабочими. Наборы, на которых функция принимает значение 0, будем называть нулевыми, или запрещенными.

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

Таким образом,

f = x4’x3x2x1 + x4x3’x2’x1 + x4x3’x2x1’ + x4x3’x2x1 + x4x3x2’x1’ + x4x3x2’x1 + x4x3x2x1’ + x4x3x2x1

Полученная форма функции называется совершенной дизъюнктивной нормальной формой (СДНФ), так как каждое логическое слагаемое представляет собой конъюнкцию всех аргументов.

Очевидно, применяя основные законы булевой алгебры, мы могли бы аналитически уменьшить сложность полученного выражения. Но это наихудший способ минимизации булевых функций. Покажем это на примере вышеописанного автомата для тайного голосования. Представим полученную функцию в виде логической суммы цифровых рабочих наборов и произведём группировку слагаемых с целью минимизации результата на основе законов склеивания и идемпотентности:

f = 0111+1001+1010+1011+1100+1101+1110+1111 =

= (0111+1111)+(1001+1011)+(1010+1011)+(1100+1101)+(1110+1111) =

= -111+10-1+101-+110-+111- = -111+10-1+(101-+111-)+(110-+111-) =

= -111+10-1+1-1-+11-- = x3x2x1+ x4x3’x1+ x4x2+ x4x3.

Как мы потом увидим, результат минимизации должен быть компактнее. Но при аналитической минимизации придётся ввести неочевидную группировку: (1101+1111).

f = 0111+1001+1010+1011+1100+1101+1110+1111 =

=(0111+1111)+(1001+1011)+(1010+1011)+(1100+1101)+(1110+1111)+(1101+1111).= -111+10-1+101-+110-+111-+11-1 = -111+(10-1+11-1)+(101-+111-)+(110-+111-) = -111+1--1+1-1-+11-- = x3x2x1+ x4x1+ x4x2+ x4x3 = =x3x2x1+ x4 (x1+ x2+ x3).

После длинных и неочевидных группировок удалось, наконец, получить правильное решение в виде минимальной дизъюнктивной нормальной формы (МДНФ). Даже для 4-х аргументов аналитический метод минимизации не рационален.

Однако не всегда исходное условие задано в виде таблицы истинности.

Задача 2.

Найти МДНФ функции, заданной в виде выражения:

M = (ax=bc)(bx=ac).

Решение.

Вначале необходимо выполнить операцию логического умножения, а затем преобразовать полученную ДНФ в СДНФ. Далее по СДНФ заполняется таблица истинности и следует традиционная минимизация с помощью карты Карно. Однако перемножать сложные выражения достаточно утомительно, поэтому заменим эту операцию сложением на основе формулы де Моргана. Получим:

M’ = (ax Å bc) + ( bx Å ac) = ab’x+ac’x+a’bc+bcx’+a’bx+bc’x+acx’+ab’c.

Мы получили ДНФ инверсии логической функции М. Теперь необходимо развернуть её в СДНФ. Выполняется эта процедура достаточно просто добавлением недостающей переменной (в данном случае домножением на (c+c’), (b+b’) или (x+x’)):

ab’x = ab’x(c+c’) = ab’cx+ab’c’x = 1011+1001,

ac’x = ac’x(b+b’) = abc’x+ab’c’x = 1101+1001,

a’bc = a’bc(x+x’) = a’bcx+a’bcx’ = 0111+0110 и т. д.

Против полученых кодов СДНФ в таблице истинности вписываем нули, а для остальных кодов – единицы (см. Рис.1.8).

После занесения M’в карту Карно получим

M = a’b’+abcx+c’x’.

1.4.Минимизация полностью определённых булевых функций.

Существует несколько способов минимизации булевых функций. Прежде всего, это метод Квайна-Мак-Класки, метод Блека-Порецкого и метод минимизации с помощью карт Карно или диаграмм Вейча [26]. Здесь будет подробно излагаться метод карт Карно, как самый удобный метод, позволяющий быстро решать задачи минимизации булевых функций от достаточно большого числа аргументов (6-12). При этом получается минимальная форма в базисе И, ИЛИ, НЕ.

Существуют карты Карно на 2 , 3 , 4 , 5 и 6 переменных[14,26]. Причем последние стали использоваться достаточно недавно. На рисунке представлены карты Карно для 2, 3, 4, 5 и 6 аргументов.

1.5.Карты Карно для 7, 8, 9 и 10 переменных.

Карты Карно позволяют решать задачу минимизации логических функций элегантно и просто. Карно был не только сообразителен (кстати, за 30 лет я так и не нашёл его биографии: узнал только, что это американец 20-го столетия), но и, вероятно, весьма ленив: он считал, что его карты настолько прозрачны, что нет резона описывать алгоритм работы с ними (вполне возможно, что Карно и не представлял себе карт более, чем для 4-х переменных). Поэтому до сих пор неблагодарное человечество не научилось работать с этими картами. Алгоритм работы с картами Карно (этот алгоритм не известен ни одному логику в мире) был разработан автором более 30 лет назад, изложен в «Инженерных методах разработки цифровых устройств»(1977г.), «Русской логике для школьников» и «Русской логике против классической», а также на вышеназванных сайтах.

До сих пор сохранилось мнение, что карты Карно для 7-10 переменных являются труднообозримыми, поэтому ни в какой литературе, кроме [13,14], нельзя найти не только описания метода работы с картами Карно на большое количество переменных, но и самих карт. Этим же обстоятельством объясняется тот факт, что до недавнего времени в литературе редко встречались карты Карно даже для 6 переменных. Прежде, чем приступить к рассмотрению многоаргументных карт Карно, покажем на простых примерах, как осуществляется соседнее кодирование для произвольного числа переменных. Для одной переменной существует только соседнее кодирование, так как она кодируется нулём и единицей. Чтобы перейти к соседнему кодированию для двух переменных x2 и x1 предлагается следующая операция. Напишем в один столбец коды для x1. Между нулём и единицей для столбца x1 проведём ось, которую назовём осью симметрии 1-го ранга.

Проведём под этим столбцом ось симметрии, которую в дальнейшем будем называть осью симметрии 2-го ранга, и продолжим столбец кодов для x1 симметрично относительно этой оси (симметрично относительно оси симметрии 2-го ранга разместятся и оси симметрии 1-го ранга).

Дополним одноразрядный код до двухразрядного, для чего выше оси симметрии впишем для x2 нули, а ниже - единицы.

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

Дополним двухразрядные коды до трёхразрядных, вписав в третьем разряде нули выше оси Карно 3-го ранга и единицы ниже этой оси. Получим соседнее кодирование для трёх переменных.

Следовательно, для того, чтобы осуществить соседнее кодирование для (Р+1) переменных, если известно соседнее кодирование для Р переменных, необходимо выполнить следующий алгоритм:

1) под столбцом известного Р-разрядного соседнего кодирования провести ось симметрии (Р+1)-го ранга ;

2) осуществить симметричное отображение относительно оси симметрии (Р+1) - ранга всех Р-разрядных кодов и осей симметрии всех рангов до ранга Р включительно ;

3) дополнить Р-разрядные коды слева одним разрядом, в котором записать 0 для всех кодов выше оси симметрии (Р+1)-го ранга и 1 для кодов, расположенных ниже оси симметрии (Р+1)-го ранга.

Соседнее кодирование карт Карно по вышеизложенному алгоритму производится как для вертикальных, так и для горизонтальных сторон карт. Примеры кодирования карт Карно приведены на рисунке. На нём стрелками обозначены оси симметрии, ранг которых отмечен цифрами, стоящими рядом со стрелками.

Покрытие всех единичных наборов булевой функции, размещённых в карте Карно, прямоугольниками Карно не вызывает затруднений, если функция зависит не более, чем от 6 переменных. Обозримость карт Карно для большего числа переменных усложняется, так как становится трудно определить, соответствует ли данная фигура покрытия понятию прямоугольника Карно. Определение достоверности прямоугольника Карно основано на принципе симметрии, значительно повышающем обозримость карт Карно, и осуществляется с помощью приводимого ниже алгоритма.

Принцип симметрии Лобанова

(Алгоритм проверки достоверности прямоугольника Карно)

1. Если предполагаемый прямоугольник Карно (ППК) охватывает одну ось симметрии, либо не охватывает ни одной, то перейти к п.4.

2. Если ППК располагается по обе стороны от нескольких осей симметрии, то он должен быть симметричен относительно той из этих осей, которая имеет максимальный ранг, иначе данная фигура не является прямоугольником Карно (ПК).

3. Разбить исходный ППК пополам. Считать любую его половину новым ППК. Перейти к п.1.

4. Конец.

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

Проверим достоверность прямоугольника Карно А на вышеприведённом рисунке. Прямоугольник А размещается по обе стороны от горизонтальной оси 4-го ранга. Симметричность его очевидна. Верхняя половина фигуры А симметрична относительно горизонтальной оси симметрии 1-го ранга. Так как ППК охватывает одну единственную ось симметрии, то проверка фигуры покрытия А на соответствие принципу симметрии относительно горизонтальных осей закончена.

Приступаем к проверке принципа симметрии относительно вертикальных осей симметрии. Фигура покрытия А размещается по обе стороны от вертикальной оси симметрии 4-го ранга и симметрична относительно этой оси. Левая половина фигуры А симметрична относительно оси симметрии 3-го ранга. После повторного деления левая половина фигуры покрытия оказалась симметричной относительно оси симметрии 2-го ранга. После 3-го деления ППК не охватывает ни одной оси симметрии, на этом проверка достоверности прямоугольника Карно заканчивается. Таким образом, фигура покрытия А действительно является прямоугольником Карно. Аналогично доказывается, что фигура покрытия В также является прямоугольником Карно. В результате минимизации прямоугольники А и В будут описаны следующими формулами: