План Литература. W145 В. И. Лобанов. Инженерные методы разработки цифровых уст- 4/231(цптб) ройств М.: 1977. Информационный листок N% 54-87 В. И. Лобанов Метод бу
| Вид материала | Литература |
- Тезисы докладов Всесоюзного совещания ?Повышение качества брэа на основе широкого внедрения, 100.73kb.
- Политехнический музей, 19.55kb.
- К. т н. И. Н. Бычков, С. В. Егоров, И. Н. Лобанов, Г. М. Расулов, 148.52kb.
- Рабочая программа дисциплины мерительные устройства систем управления, 448.87kb.
- Лобанов Владимир Иванович, вед научн сотрудник фгуп «цнии «Комета», к т. н., e mail, 1199.47kb.
- М. П. Лобанов «бессильная красота», 296.13kb.
- -, 1113.42kb.
- Урока литературы в 9 классе на тему: «Древнерусская литература и современность. Золотое, 43.48kb.
- 1. Политология как система знаний о политике, 244.32kb.
- Программа дисциплины логика для направления 080100. 62 Экономика Утверждена, 404.05kb.
Лобанов Владимир Иванович (e-mail: lobanov-v-i@mail.ru),
к.т.н., член РФО РАН, главный специалист НПП 'Редан', Москва.
Основы логики
Употребляйте с пользой время.
Учиться надо по системе.
Сперва хочу вам в долг вменить
На курсы логики ходить.
Ваш ум,не тронутый доныне,
На них приучат к дисциплине,
Чтоб взял он направленья ось,
Не разбредаясь вкривь и вкось.
Что вы привыкли делать дома
Единым махом наугад,
Как люди пьют или едят,
Вам расчленят на три приема
И на субъект и предикат.
В мозгах как и в мануфактуре,
Есть ниточки и узелки.
Посылка не по той фигуре
Грозит запутать челноки.
(Гете "Фауст")
План
1.Литература.
W145 1.В.И.Лобанов.Инженерные методы разработки цифровых уст-
4/231(ЦПТБ) ройств - М.:1977.
2. Информационный листок N% 54-87 В.И.Лобанов "Метод бу-
левых функций от большого числа переменных с помощью
карт Карно".Московской областной территориальный центр
научно-технической информации и пропаганды. 1987 (ТД 87-18-15).
3.В.И.Кириллов,А.А.Старченко.Логика - М.:1995.
4.В.А.Светлов.Практическая логика - СПб.:1997.
5.Б.В.Григорьев.Классическая логика - М.:1996.
6.Г.Л.Бузук.Логика и компьютер - М.:1995.
7.Л.Кэрролл.Логическая игра - М.:1991.
8.К.К.Жоль.Логика в лицах и символах - М.:1993.
9.А.Гжегорчик.Популярная логика - М.:1979.
10.О.В.Суворов.Основы логики для средней школы. - М.:Ак-
вариум,1997.
2.Предмет логики.История становления логики как науки.
3.Основные законы логики.
4.16 функций логики.
5.Старосте подготовить список группы на ПК в Lexicon.
6.Дом.задание на листах(лучше в тонкой тетрадке) в клеточ-
ку.Конспект в клетч.тетради(48 листов).
1.Логика как наука.Основные законы алгебры логики.
Введение.
Логика - наука о мышлении,точнее о закономерностях в связях и
развитии мыслей.
Первое упоминание логики встречается в китайской "Книге пере-
мен"(VIII в до н.э.).В Древней Греции она начала разрабатываться в VI
в до н.э.Немного позже логика возникла в Индии.Первоначально логика
служила юриспруденции(воровство-двигатель прогресса) и ораторскому ис-
кусству.Еще одним стимулом создания науки логики стали запросы матема-
тики,где требовались строгие доказательства.В Древней Греции логику
разрабатывали Парменид (VIв. до н.э.),Демокрит,Сократ,Платон(V в до
н.э.) и Аристотель(IV в до н.э.).
Аристотель,внук легендарного врача Асклепия,родился в г.Стаги-
ра(второе имя - Стагирит) в 384 г. до н.э.Обучался в академии Плато-
на,был дружен с царем Филиппом,обучал логике его сына Александра Маке-
донского.Впервые ввел в логику законы и правила,основал силлогисти-
ку,т.е.создал логику.Смерть Аристотеля датируется 322 г до н.э.(яд?).
Принципы современной математической логики предвосхитил в своей
работе "Об искусстве комбинаторики"(1666) великий немецкий философ,ма-
тематик,физик и языковед Готфрид Вильгельм Лейбниц(1646-1716).
Великий русский и швейцарский ученый Леонард Эйлер(1707-1783) с
1727г. по 1741г. работал в России.С 1766г. был избран академиком Пе-
тербургской АН.Ученый необычайной широты интересов.Автор свыше 800 ра-
бот по математике,физике,небесной механике,оптике,баллистике,кораб-
лестроению,теории музыки.Предложил так называемые круги Эйлера,ставшие
основой формальной силлогистики.
Однако основоположником математической логики считается Джордж
Буль(1815-1864),английский математик,отец всемирно известной писатель-
ницы Этель Лилиан Войнич(роман "Овод").
Лекции не научат вас логически мыслить,поскольку каждый человек
обладает этим даром от природы.Человечество достигло современных вер-
шин цивилизации не благодаря,а скорее вопреки формальной логике.Но
формальная логика поможет вам справиться с обработкой большого объема
информации при анализе и синтезе силлогизмов,при решении логических
уравнений,при синтезе микропрограммных автоматов.В настоящее время
значение математической логики сильно возросло в связи с насущной не-
обходимостью создания искусственного интеллекта.Пока не будут решены
проблемы силлогистики,искусственный интеллект останется пустым звуком.
Силлогистика - фундамент искусственного интеллекта.
Предлагая свои методы решения многих проблем логики,в том числе в
области силлогистики,решения логических уравнений и минимизации логи-
ческих функций, автор не претендует на истину в последней инстан-
ции,тем более,что к решению этих проблем вплотную подошли русские ло-
гики Кулик Б.А.[9],Светлов В.А.[18],Брусенцов Н.П.[5].
1.1.Основные законы алгебры логики.
В алгебре логики переменные могут принимать только 2 значения:
0 или 1.
Табл.1.1 Табл.1.2
------------T------------¬ -----------T---------¬
¦Аргументы ¦ Функции ¦ ¦Аргументы ¦ Функция¦
+-----------+------T-----+ +----------+---------+
¦ ¦ И ¦ ИЛИ¦ ¦ ¦ НЕ ¦
¦ х1 х2 +------+-----+ ¦ х +---------+
¦ ¦ у1¦ у2¦ ¦ ¦ у3 ¦
+-----------+------+-----+ +----------+---------+
¦ 0 0 ¦ 0 ¦ 0 ¦ ¦ 0 ¦ 1 ¦
¦ 0 1 ¦ 0 ¦ 1 ¦ +----------+---------+
¦ 1 0 ¦ 0 ¦ 1 ¦ ¦ 1 ¦ 0 ¦
¦ 1 1 ¦ 1 ¦ 1 ¦ L----------+---------+
+-----------+------+------
И -логическое умножение,конъюкция.
ИЛИ -логическое сложение,дизъюнкция.
НЕ -отрицание,инверсия.
Графическое и аналитическое представление основных логических
функций приведено на рисунке 1.1.
------¬ ------¬ __
X1--+ & ¦ X1--+ 1 о--У3=Х1
Х2--+ +--У1=Х1*Х2 L------
L------
------¬
X1--+ 1 ¦
X2--+ +--Y2=X1+X2 Рис.1.1
L------
У1=Х1*Х2=Х1&X2=Х1Х2=X1 X2
У2=Х1+Х2=Х1VХ2
_
У3=Х
Далее в качестве знака отрицания вместо "крышки" будет использо-
ваться апостроф.
Для n переменных в двоичной логике имеется 22n функций.Полный
набор логических функций от 2-х переменных представлен в табл.1.3.
Табл.1.3
-----T---T---T---T---T---T---T---T---T---T---T---T---T---T---T---T---¬
¦ xy ¦z0 ¦z1 ¦z2 ¦z3 ¦z4 ¦z5 ¦z6 ¦z7 ¦z8 ¦z9 ¦z10¦z11¦z12¦z13¦z14¦z15¦
+----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
¦ 00 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦
¦ 01 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦
¦ 10 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦
¦ 11 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦
L----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+----
Некоторые из этих функций получили специальные названия:
z0 = 0 - тождественный нуль;
z1 = xy - конъюнкция;
z6 = xy'+x'y - неравнозначность,сумма по модулю 2;
z7 = x+y - дизъюнкция;
z8 = x'y' = (x+y)' - функция Вебба(стрелка Пирса);
z9 = x'y'+xy - равнозначность;
z13= x'+y= x -> y - импликация,а также Axy;
z14= x'+y' = (xy)' - функция Шеффера,а также Exy;
z15= 1 - тождественная 1,а также Ixy(8).
1.2.Основные законы алгебры Буля.
1. Комплементарность.
a*a'=0; a+a'=1
2. Идемпотентный закон.
а*а=а; а+а=а
3. Переместительный закон.
а+в=в+а; ав=ва
4. Сочетательный закон.
(а+в)+с=а+(в+с); (ав)*с=а*(вс)
5. Закон поглощения.
а+ав=а(1+в)=а; а(а+в)=а+ав=а
6. Распределительный закон.
а(в+с)=ав+ас; (а+в)(а+с)=а+вс
/* (а+в)(а+с)=а*а+ав+ас+вс=(а+ав+ас)+вс=
=а(1+в+с)+вс=а+вс */
7. Закон склеивания
ав+ав'=а(в+в')=а;
(а+в)(а+в')=а+ав+ав'+вв'=а+а(в+в)+0=
=а+а*1=а+а=а
8.Правила де Mоргана.
____ ____
_ _ _ _
а+в = а*в; а*в = а*в
_________ __________
_ _ _ _ _ _
/*а+в+...+z = а*в...*z; а*в*...*z = а+в+...+z */
Заучивать все логические законы и запоминать их названия нет ни-
какого смысла,тем более,что на практике используются 2-3 из них(законы
поглощения и склеивания,правила Де Моргана).Значительно важнее осмыс-
лить эти законы и научиться применять.
С помощью правил де Моргана легко реализуются логические схемы на
базе интегральных схем(ИС) так называемого функционально полного бази-
са(ФПБ).ФПБ характерен тем,что на его основе можно построить любую
сколь угодно сложную схему,в том числе и самую сложную вычислительную
машину без применения других ИС.К ФПБ относятся ИС типа И-НЕ,а также
ИЛИ-НЕ.Таким образом,на очень простом элементе типа И-НЕ может быть
построена,например,сложная система управления ракетой.Только в этой
системе управления простые элементы И-НЕ сгруппированы в большие ин-
тегральне схемы(БИС),которые выполняют функции процессора,памяти и то-
му подобных сложных устройств.
Пусть нам необходимо построить схему,реализующую функцию
y = x1x2 + x3x4.Используя формулу де Моргана,получим следующее соотно-
шение:
y = x1x2 + x3x4 = ((x1x2)'(x3x4)')'.
Таким образом,мы выразили исходную функцию с помощью одних только
элементов И-НЕ.Схема реализации заданной функции представлена на ри-
сунке.
------¬
X1--+ & ¦ (x1x2)'
Х2--+ о-------¬ ------¬
L------ L-------+ & ¦ y=((x1x2)'(x3x4)')'=x1x2+x3x4
--------+ о--
------¬ ¦ L------
X3--+ & ¦ ¦
Х4--+ о--------
L------ (x3x4)'
Синтез релейных схем выполняется также на основе алгебры логики.
3.Задача.
Задержаны подозреваемые в преступлении Браун,Джон и Смит.Один из
них говорит правду,другой - полуправду,третий - ложь.Приведем их пока-
зания.
Браун:"Я совершил это,Джон не виноват."
Джон:"Браун не виноват,преступник - Смит."
Смит:"Я не виноват,виноват Браун."
Найти преступника,если известно,что он один.
Решение.
Введем обозначения:
B - виноват Браун;
C - виноват Смит;
D - виноват Джон.
Тогда условие задачи будет выражено двумя уравнениями:
1)BD'+B'C+BC' = 1(показания подозреваемых,одно из них истинно);
2)B'C'+B'D'+C'D' = 1(преступник единственный).
M = (BD'+B'C+BC')(B'C'+B'D'+C'D') = B'CD'+BC'D' = 1.
BC'D' отпадает,т.к. иначе Браун и Смит оба говорят правду.Следо-
вательно,истинно B'CD',т.е. преступник - Смит,он еще и лжец.Джон гово-
рит правду,Браун - полуправду.Кстати,отсеять BC'D' можно было на пер-
вом этапе,поскольку из условий задачи следует BD'+BC' = 0,поэтому
M = B'C(B'C'+B'D'+C'D') = B'CD'.
4.Задача.
Если в экспедицию поедет Арбузов,то поедут и Брюквин с Вишневс-
ким.Если поедут Арбузов с Вишневским,то поедет и Брюквин.Кто отправит-
ся в экспедицию?
Решение.
A - поедет Арбузов.
B - поедет Брюквин.
W - поедет Вишневский.
1)A -> (B+W);
2)AW -> B.
M = (A'+B+W)(A'+W'+B) = A'+B = A -> B,т.е. если поедет Арбузов,то
поедет и Брюквин.
| |  К оглавлению |  ссылка скрыта |
Кінець форми
Формы задания и синтез логических функций
ЛЕКЦИЯ 2
--------
План
1.Формы задания лог. ф-ций.
2.Синтез ПОЛФ.
3.Дать доп.примеры синтеза ПОЛФ(с пом. ПК).
4.Минимизация с пом.осн.з-нов логики.
2.Формы задания и синтез логических функций
Традиционно логические функции задаются с помощью таблиц истин-
ности,где в левой ее части вписаны входные наборы,а в правой - значе-
ние функции на этих наборах.Однако входные наборы можно представлять в
виде 8-ичных или 16-ичных кодов,которые легко разворачиваются в двоич-
ные коды,являющиеся по сути входными наборами.
Таблица перевода 8-ичных кодов в
2-ичную систему счисления.
---------T--------¬
¦ 8-ая ¦ 2-ая ¦
+--------+--------+
¦ 0 ¦ 000 ¦
¦ 1 ¦ 001 ¦
¦ 2 ¦ 010 ¦
¦ 3 ¦ 011 ¦
¦ 4 ¦ 100 ¦
¦ 5 ¦ 101 ¦
¦ 6 ¦ 110 ¦
¦ 7 ¦ 111 ¦
L--------+---------
Для перевода целого 8-ичного числа в 2-ичную систему счисления
достаточно представить каждую 8-ичную цифру данного числа в виде 2-ич-
ной триады.
Пример 1.
73(8) = 111011(2)
54321(8) = 101100011010001(2)
Пример 2.
Логическая функция от 6 переменных задана следующими 8-ичными ра-
бочими наборами:
РН(6) = 31,51,71.
Этим РН(6) соответствуют следующие 2-ичные коды:
011001,101001,111001.
2.1. Синтез полностью определенных логических функций
-----------------------------------------------------
Полностью определенной логической функцией(ПОЛФ) от N переменных
называется такая функция,которая задана на всех 2N наборах.Синтез
ПОЛФ можно проиллюстрировать решением простой задачи.
Задача 2.1.
-----------
Приемная комиссия в составе трех членов комиссии и одного предсе-
дателя решает судьбу абитуриента большинством голосов . В случае рав-
ного распределения голосов большинство определяется голосом председа-
теля. Построить автомат для тайного голосования.
Решение.
-------
Выразим условие задачи в виде таблицы истинности (табл.2.1). Здесь
х4-председатель,х3...х1 - члены комиссии,у-полностью определенная
выходная функция; у=1,если абитуриент успешно прошел собеседова-
ние.
Таблица 2.1.
------------------T-----¬
¦х4 х3 х2 х1 ¦ у ¦
+-----------------+-----+
¦ 0 0 0 0 ¦ 0 ¦
¦ 0 0 0 1 ¦ 0 ¦
¦ 0 0 1 0 ¦ 0 ¦
¦ 0 0 1 1 ¦ 0 ¦
¦ 0 1 0 0 ¦ 0 ¦
¦ 0 1 0 1 ¦ 0 ¦
¦ 0 1 1 0 ¦ 0 ¦
¦ 0 1 1 1 ¦ 1 ¦
¦ 1 0 0 0 ¦ 0 ¦
¦ 1 0 0 1 ¦ 1 ¦
¦ 1 0 1 0 ¦ 1 ¦
¦ 1 0 1 1 ¦ 1 ¦
¦ 1 1 0 0 ¦ 1 ¦
¦ 1 1 0 1 ¦ 1 ¦
¦ 1 1 1 0 ¦ 1 ¦
¦ 1 1 1 1 ¦ 1 ¦
L-----------------+------
Конъюнкции входных переменных, на которых функция принимает зна-
чение 1, будем называть единичными , или рабочими наборами(РН) . Набо-
ры, на которых функция принимает значение 0, будем называть нулевыми,
или запрещенными наборами(ЗН).
Кстати,данная таблица истинности может быть представлена следую-
щими 8-ичными кодами единичных наборов:7,11,12,13,14,15,16.17.Нулевые
наборы для ПОЛФ не задаются:они получаются автоматически.
Для того,чтобы по таблице истинности найти функцию, достаточно
выписать все рабочие наборы и соединить их знаком логического сложе-
ния.Если переменная входит в РН единицей,то она записывается в прямом
виде,иначе - в инверсном. Из табл.2.1 получаем
__ _ _ __ __ __ _ _ __
у=х4х3х2х1 + х4х3х2х1 + х4х3х2х1 + х4х3х2х1 + х4х3х2х1+ х4х3х2х1 +
__
+ х4х3х2х1 + х4х3х2х1
Данное выражение представляет собой совершенную дизъюнктивную нор-
мальную форму (СДНФ) булевой функции
ДОМАШНЕЕ ЗАДАНИЕ 1
1.Выполнить синтез 16 табличных функций от 2-х переменных(лекция
1,табл.1.3).
2.Выполнить ситез функций,заданных 8-ичными рабочими наборами:
- РН(3) = 0,2,5,7;
- РН(4) = 14,15,10,11.
3.Отминимизировать полученные в п.2 ДЗ1 функции,используя основ-
ные законы логики.
4.Отминимизиpовать функции от 3-х пеpеменных под 8-ичными номеpами:
267,173,370,111,123,146,230,345,356,234.
5.Отминимизировать функцию автомата для тайного голосования.
Минимизация булевых функций
ЛЕКЦИЯ 3
--------
План
1.Методы минимизации.
2.Карты Карно.
3.Алгоритм графич.минимизации.
4.Сущность алгоритма.
3.Минимизация булевых функций
Существуют несколько способов минимизации булевых функций.Прежде всего,это аналитический символьный и аналитический кодовый методы,метод Квайна - Мак-Класки,метод Блека - Порецкого,метод обобщенных кодов[11] и графическая минимизация с помощью карт Карно[12].
Пример для демонстрации аналитических методов:
z = x_y+xy_+xy = (x_y+xy)+(xy_+xy) = y(x_+x) + x(y_+y) = x+y.
z = 01+10+11 = (01+11)+(10+11) = -1+1- = x+y.
Первые четыре метода чрезвычайно громоздки и малоэффективны уже при количестве аргументов более четырёх. Метод обобщенных кодов ориентирован на использование ЭВМ,однако может использоваться и при ручном синтезе для функций от большого числа переменных.
3.1.Минимизация полностью определенных булевых функций
Наиболее эффективна минимизация булевых функций с помощью карт
Карно.До сих пор существует ошибочное мнение,что этим методом можно
решать задачи для функций от не более, чем 6 аргументов. На самом деле
карты Карно могут применяться для функций даже от 8-12 переменных
[12]. На рис.3.1. представлены карты Карно для 2-6 переменных и приме-
ры минимизации с их помощью логических функций.
\ x1 \x2x1 \x2x1
x2 \ 0 1 x3\ 00 01 11 10 x4x3\ 00 01 11 10
\ ----T----- -----T----T----T----- ------T-----T-----T------
0 | а | а | 0 | а | | | а | 00 | 1 | 0 | 1 | 1 |
+----+----+ +----+----+----+----+ +-----+-----+-----+-----+
1 | | | 1 | | | | | 01 | 0 | 0 | 1 | 0 |
L----+----- L----+----+----+----- +-----+-----+-----+-----+
-- -- -- 11 | 0 | 0 | 1 | 0 |
а = X2 а = X3*X1 +-----+-----+-----+-----+
10 | 1 | 0 | 1 | 1 |
L-----+-----+-----+------
-- --
y = X2X1 + X3*X1
а) б) в)
\
\ X2X1
X5X4X3 \ 00 01 11 10
------T-----T-----T------
000 | а | а | b | b |
+-----+-----+-----+-----+ -- --
001 | | | b | b | а = X3*X2
+-----+-----+-----+-----+ --
011 | | | b | b | b = X5*X2
+-----+-----+-----+-----+
010 | а | а | b | b | c = X5*X3*X2
+-----+-----+-----+-----+
110 | а | а | | |
+-----+-----+-----+-----+
111 | | | с | с |
+-----+-----+-----+-----+
101 | | | с | с |
+-----+-----+-----+-----+
100 | а | а | | |
L-----+-----+-----+------
г)
\ Х3Х2Х1
Х6Х5Х4 \
000 001 011 010 110 111 101 100
----T---T---T---T---T---T---T----
000| a | в | c | | | c | в | a |
+---+---+---+---+---+---+---+---+
001| e | | | e | | | | | f=X6*X5*X4
+---+---+---+---+---+---+---+---+ __
011| m | k | k | m | m | k | k | m | n=X6*X4*X2
+---+---+---+---+---+---+---+---+
010| d | d | | | | | d | d |
+---+---+---+---+---+---+---+---+
110| n | n | | | | | n | n |
+---+---+---+---+---+---+---+---+
111| f | f | f | f | f | f | f | f |
+---+---+---+---+---+---+---+---+
101| | | | | | | | |
+---+---+---+---+---+---+---+---+
100| n | n | | | | | n | n |
L---+---+---+---+---+---+---+----
д)
Рис.3.1. Карты Карно для 2-6 переменных
Метод Карно основан на законе склеивания.Склеиваются наборы,
отличающиеся друг от друга лишь значением одного разряда.
Такие наборы называются соседними, и они соответствуют соседним
клеткам карты Карно.Формируются такие наборы(коды Грея) по принципу
симметрии[11,12].
Введем определение прямоугольника Карно, под которым будем пони-
мать некоторую, зачастую разрозненную, фигуру покрытия,удовлетворяющую
принципу симметрии,т.е. сплошь состоящую из элементарных прямоугольни-
ков Карно,закодированных только соседними наборами.
Алгоритм "НИИРТА"
графической минимизации логических функций
1.Заполнить карту Карно нулями и единицами в соответствии с таб-
лицей истинности.
2.Покрыть все единичные наборы минимальным количеством прямоу-
гольников Карно, каждый из которых имеет максимальную площадь.
3.Каждому прямоугольнику Карно соответствует одна импликанта,
причем, если в границах прямоугольника Карно какая-либо переменная
принимает значение как 0, так и 1, то она склеивается.
На рис. 3.2 представлены фигуры покрытия,не являющиеся прямоу-
гольника Карно
\ x3x2x1
x5x4 \ 000 001 011 010 110 111 101 100
----T---T---T---T---T---T---T----
00 | К | К | | К | К | | К | К |
| | | | | | | | |
+---+---+---+---+---+---+---+---+
01 | П |П | | | | | | |
| | | | | | | | |
+---+---+---+---+---+---+---+---+
11 | | | | М |М |М |М | |
| | | | | | | | |
+---+---+---+---+---+---+---+---+
10 | П |П | | М |М |М |М | |
| | | | | | | | |
L---+---+---+---+---+---+---+----
Рис. 3.2 Фигуры покрытия,не являющиеся прямоугольниками Карно
Применим карту Карно для решения задачи 2.1 о синтезе автомата
для тайного голосования.Это решение представлено на рис. 3.3
\ x2x1
x4x3 \ 00 01 11 10
----T----T----T-----
00 | 0 | 0 | 0 | 0 | y= x4x1 + x4x2 + x4x3 + x3x2x1
+----+----+----+----+
01 | 0 | 0 | 1 | 0 | Это выражение представляет собой пример
+----+----+----+----| минимальной дизъюнктивной нормальной
11 | 1 | 1 | 1 | 1 | формы (МДНФ).
+----+----+----+----+
10 | 0 | 1 | 1 | 1 |
L---------+----------
Рис. 3.3. Решение задачи 2.1.
В некоторых случаях приведение результата минимизации к скобочной
форме позволяет уменьшить сложность булевой функции. Скобочная форма
для (3.3) имеет вид
y= x4(x1 + x2 + x3) + x3x2x1.
Реализация скобочной формы логической функции автомата для тайно-
го голосования в виде релейной схемы изображена на рисунке.
| x3 x2 x1 |
+----------------L-----L------L-------------- |
| | ------- |
| x4 x3 | | | |
+------L---T-----L-----T--------------------+---+ УИ +----+
| | x2 | | | |
| +-----L-----+ L------ |
| | x1 | |
| L-----L------ |
| |
|+Еп |-Еп
Релейная схема автомата к задаче 2.1
На схеме представлены контакты реле x4,x3,x2,x1.При включении
тумблера срабатывает соответствующее реле и замыкает свои контак-
ты.Например,если за прием абитуриента проголосовали председатель(x4) и
3-й член комиссии(х3),то замкнутся контакты х4 и х3 и сработает уст-
ройство индикации(УИ),запитанное от источника с напряжением Еп.
Домашнее задание.
1.Найти z5,z7,z11,z13,z14,z15 для функций от трех переменных.
------T---T---T---T---T---T---T---T---T---T---T---T---T---T---T---T----
| uxy |z0 |z1 |z2 |z3 |z4 |z5 |z6 |z7 |z8 |z9 |z10|z11|z12|z13|z14|z15|
+-----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 000 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 001 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 010 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 011 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 100 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 101 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 110 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 111 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
L-----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+----
2.Найти общее количество функций от 3-х переменных.