close

Вход

Забыли?

вход по аккаунту

?

MishuraPopov1

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное
образовательное учреждение высшего образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
О. В. Мишура, В. П. Попов
ДИСКРЕТНАЯ МАТЕМАТИКА.
ТЕОРИЯ МНОЖЕСТВ. МИНИМИЗАЦИЯ
ЛОГИЧЕСКИХ ФУНКЦИЙ ПРИ ПОМОЩИ
ДИАГРАММ ВЕЙЧА
Учебно-методическое пособие
Санкт-Петербург
2016
УДК 519.7
ББК 22.176
М71
Рецензент –
киндидат технических наук, доцент Н. В. Соловьев
Утверждено
редакционно-издательским советом университета
в качестве учебно-методического пособия
Мишура, О. В.
М71 Дискретная математика. Теория множеств. Минимизация логических функций при помощи диаграмм Вейча.:
учеб.-метод. пособие / О. В. Мишура, В. П. Попов. – СПб.:
ГУАП, 2016. – 55 с.
Предназначено для студентов дневной и заочной формы обучения
по направлению 09.03.02 «Информационные системы и технологии»,
квалификация – бакалавр.
Подготовлены кафедрой информационно-сетевых технологий
(№53) и рекомендованы к изданию редакционно-издательским советом Санкт-Петербургского государственного университета аэрокосмического приборостроения.
Учебно-методическое пособие может быть полезно для студентов
других направлений, изучающих дисциплину «Дискретная математика».
УДК 519.7
ББК 22.176
©
©
Мишура О. В., Попов В. П., 2016
Санкт-Петербургский государственный
университет аэрокосмического
приборостроения, 2016
ПРЕДИСЛОВИЕ
Разделы дискретной математики – теория множеств и комбинаторика тесно связаны друг с другом. Первый раздел учебно-методического издания посвящен представлениям в области классической
теории множеств, которая является основой таких областей математики как комбинаторика, теория групп, отображения, перестановки, преобразования, топология, общая алгебра и др. Определённые представления в области теории множеств позволяют лучше
усвоить второй раздел пособия – комбинаторику. Комбинаторика
ориентирована на решение задач выбора и расположения элементов
некоторых множеств. Во втором разделе рассмотрены задачи традиционной комбинаторики – размещения, перестановки, сочетания,
раскладки, разбиения. Отдельные (весьма немногочисленные) примеры могут вызвать некоторые затруднения, но они будут преодолены если не при первом, то при повторном чтении данного учебнометодического издания. Учебно-методическое издание подготовлено в соответствии с требованиями ФГОС и программой дисциплины
«Дискретная математика», разработанной в ГУАП.
3
1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
1.1. Понятие множества
В математике часто интересуются не отдельными объектами,
а целыми классами объектов, например:
− совокупность всех целых чисел;
− совокупность всех натуральных чисел;
− совокупность всех простых чисел;
− совокупность всех треугольников;
− совокупность всех букв и т.д.
Иногда, такие совокупности состоят из бесконечного
(беcчисленного) множества отдельных элементов. Математики всегда интересовались понятием бесконечности. Но первые попытки изучения бесконечности привели к многочисленным парадоксам. Например, парадоксы Зенона (греческий философ). Первый парадокс –
парадокс летящей стрелы (невозможность движения): чтобы стрела
пролетела какой-то путь, сначала она должна преодолеть половину
пути. Но прежде чем преодолеть полпути, надо преодолеть четверть
пути, восьмую часть пути, шестнадцатую часть и т.д. Так как процесс деления пополам никогда не кончится (вот она бесконечность),
то стрела никогда не сможет сдвинуться с места. Второй парадокс –
сможет ли Ахиллес догнать Черепаху?
Прежде чем знакомиться со свойствами множеств, надо определить:
а) что такое множество;
б) какие действия можно выполнить над ними.
К сожалению, основному понятию теории множеств – понятию
«множества» – дать точное, строгое определение не возможно.
Понятия «элементы» и «множество» считаются общеизвестными и не определяются. Разумеется, можно было бы сказать, что
«множество» это:
а) – «совокупность» элементов (тогда надо дать определение «совокупности»). Например, «совокупность» – это набор элементов, что
в свою очередь потребует определения термина «набор» и т.д. Такие
вложенные определения будут повторяться до бесконечности.
б) – «собрание» элементов – те же проблемы.
в) – «система», «класс» – те же проблемы.
Это всё не математические определения, а использование словарного богатства русского языка (его избыточности). Чтобы определить
какое–либо понятие, надо указать, частным случаем какого, более
4
широкого понятия является определяемое понятие. Для понятия
множества это не возможно, т.к. оно само является наиболее широким и не в каких других понятиях не содержится. Точно таким
же неопределяемым понятием является термин «элемент«. Часто,
некоторые объекты объединены некоторым общим признаком, например:
– множество стульев в комнате,
– множество всех клеток человеческого тела,
– множество картофелин в данном мешке,
– множество студентов конкретной группы.
Для того ,что бы указать ,что данное множество M состоит из элементов а обычно пишут :
M = {а}.
Здесь фигурные скобки { } обозначают, что элементы а объединены в одно целое – множество M. Например, а – каждый студент
конкретной группы, M – множество студентов конкретной группы.
Факт принадлежности элемента а множеству M записывают
с помощью символа ∈, т.е. а∈M.
Читается эта запись т.о. «элемент а принадлежит множеству M».
Если же элемент b не принадлежит множеству M ,то пишут либо
b Ï M, либо b Î M.
Например, M – множество четных чисел, тогда 4∈M, а 3 Ï M.
Основатель теории множеств – немецкий математик Георг Кантор, создал её приблизительно в 1870 г.
Если множество содержит конечное число элементов, его именуют конечным, а если в нем бесконечно много элементов, то именуют бесконечным. Например, множество деревьев парка – конечное,
а множество точек на окружности – бесконечно.
Мощность множества M – это число его элементов. Обозначается
мощность |M|.
1.2. Способы задания множества
Как задают множества? Существуют различные способы задания множеств.
Один из них – дать полный список элементов, входящих в множество. Но этот способ применим только к конечным множествам
(да и то не ко всем).
Примеры задания множеств:
1) Первый способ – задать множество перечислением его элементов (самый простейший способ). Например, множество студен5
тов данной группы определяется их списком в групповом журнале:
а,b,с,d,е∈M, множество стран на земном шаре определяется их списком в географическом атласе мира, множество элементов таблицы
Менделеева.
Перечислительный, или явный способ задания множеств, неудобен в случае, когда элементов множества очень много, и совсем
непригоден для задания бесконечных множеств. Кроме того, даже
в тех случаях, когда явное задание множества является возможным и легким, но оно затуманивает сам смысл рассматриваемого множества, и скрывает причины, побудившие нас объединить
в одно множество именно эти, а не другие элементы. Гораздо более
распространен иной, неявный или описательный способ задания
множеств.
2) Второй способ задания множеств, когда множество нельзя
задать списком, – указать некоторое характеристическое свойство, которым обладают элементы множества, т.е. сформулировать правило определения принадлежности элемента множеству.
Например:
– множество синтаксических ошибок в тексте программы;
– множество натуральных чисел (числа целые, положительные и 0) Z + ;
– множество целых чисел Z;
– множество всех действительных чисел R.
По второму способу, в приведённых примерах, мы задали все
множества общими свойствами их элементов. Другие примеры задания множеств по второму способу:
а) множество M – это решения тригонометрического уравнения
вида
π
sin x = 1 ® x = + 2πn,
2
где n – произвольный элемент множества Z (множества целых чисел);
б) множество групп первого курса какого либо факультета MГ.
Каждый элемент множества MГ является множеством конкретных
студентов, т. е. MГ является множеством множеств.
Бесконечные множества можно задавать только описательным
способом.
Любая совокупность элементов некоторого множества M
именуется подмножеством. Это же понятие возникает каждый раз,
когда приходится рассматривать множество не как самостоятельное,
а как часть другого, более широкого множества. Если множество
6
В является подмножеством другого множества А, т.е. каждый
элемент х из множества В является и элементом множества А, то
в этом случае пишут B Ì A или A É B.
Эти два соотношения имеют один и тот же смысл: множество А
содержит множество В в качестве своей части. Чисто внешне, эти
соотношения близки к записям и В < А и А > В.
1.3. Основные операции над множествами
В приложениях дискретной математики часто приходится из нескольких множеств образовывать новое множество. Операции, выполняемые над множествами, следующие:
1) объединение (сумма) множеств – это образование единого (целого) множества из нескольких множеств. Объединением (суммой)
нескольких множеств А, В, … называют новое множество, состоящие из тех и только тех элементов, которые входят хотя бы в одно
из слагаемых множеств. Символ объединения множеств  или + ,
соответственно объединение (сумму) множеств А и В, обозначают
A  B или А + В.
Следует отметить, что отдельные элементы могут входить не
только в одно, а в несколько объединяемых (слагаемых) множеств.
В этом случае всё равно они входят в сумму только один раз. Поэтому, для конечных множеств число элементов суммы может оказаться меньше, чем сумма числа элементов слагаемых множеств.
Это можно представить геометрически (рис. 1). Пусть множество А
состоит из точек фигуры, заштрихованной горизонтальными линиями, а множество В состоит из точек фигуры
заштрихованной наклонными линиями,
тогда множество А + В или A  B, т.е. их
объединение, составляет вся заштрихованA
ная фигура.
B
Очевидно, что операция объединения
(сложения) множеств обладает многими
свойствами сложения чисел. Так, выполняются:
Рис. 1
а) переместительный закон (коммутативный)
А + В = В + А;
б) сочетательный закон (ассоциативный)
А + (В + С) = (А + В) + С.
7
Множества А + (В + С) или (А + В) + С можно обозначить и без
скобок:
А + В + С,
т.к. сумма их представляет объединение всех трёх множеств А,B
и С. Геометрически это выглядит т.о. (рис. 2),т.е. объединение множеств А,В и С – это вся заштрихованная область.
В алгебре множеств есть особые множества:
– пустое множество;
– множество – единица.
Пустое множество обозначается буквой Æ , похожей по написанию на число ноль 0 (именуется оно иногда нуль-множеством). Пустое множество
такое, сложение (объединение) с которым не должно изменять ни одного мноA
жества. Это означает, что множество Æ
не содержит ни одного элемента, т.е. явB
ляется пустым.
Иногда появляется мысль вовсе исC
ключить из рассмотрения подобное пустое множество: ведь если оно не содержит элементов, то это вообще не множество (и нечего о нём говорить). Однако,
Рис. 2
поступать так, было бы подобным исключению числа 0 из совокупности чисел: ведь набор из нуля предметов так же является пустым набором
и говорить о числе предметов, содержащихся в этом наборе, как
будто бессмысленно. Но на самом деле это совсем не бессмысленно,
а очень даже осмысленно. Если бы мы не имели числа 0 ,то не могли
бы вычесть одно из другого любую пару чисел, например 3-3. При
отсутствии числа 0 эта разность вообще бы ничему не равнялась.
Нам было бы трудно записывать в позиционной десятичной системе
счисления, скажем, число 10810 – одна сотня, восемь единиц и совсем никаких десятков.
И ещё многое мы не смогли бы сделать, поэтому идея возникновения
нуля считается одним из выдающихся (замечательных) событий во
всей истории арифметики. Поэтому, если множество Æ – пустое
множество, то для любого множества А: А + Æ = А.
Несколько сложнее обстоит дело с «множеством-единицей». Это
множество будем обозначать буквой I, похожей по написанию на число 1. Множество-единица – это универсальное множество, его смысл
8
аналогичен роли единицы. Значение этого множества мы оценим после того, как рассмотрим операцию пересечения (произведения) множеств. Рассмотрим несколько примеров объединения множеств. Пусть
два множества имеют элементы M1 = {a,b,c,d}, M2 = {b,c,e,p}.
Их объединение будет множество M3, элементы которого: M3 =
= M1 + M2 или M3 = M1  M2 = {a b,c,d,e,p}.
Пусть – M1, множество студентов (юношей) группы, – M2 множество студеток (девушек) группы.
Тогда M1  M2 будет множество всех обучающихся в этой
группе.
2) Вторая операция над множествами – пересечение (произведение, умножение) множеств. Пересечением множеств А и В называют новое множество, содержащее те и только те элементы, которые
входят в каждое из множеств А и В. т.е. пересечение множеств – это
общая часть этих множеств. Обозначение пересечения множеств –
символ  или A∙B (как в алгебре).
Геометрический смысл этой операции (рис. 3) следующий: если
множество А состоит из точек фигуры заштрихованной горизонтальными линиями, а множество В – состоит из точек фигуры ,заштрихованной наклонными линиями ,то пересечением этих множеств А∙В или А  В будет фигура из горизонтальных и наклонных
линий (т.е. покрытая решеткой).
Кстати, название операции «пересечение» происходит от того,
что при пересечении двух геометрических фигур, получают множество точек пересечения обоих фигур в самом обычном смысле
этого слова. Т.к. пересечением множеств является новое множество, элементами которого будут элементы, принадлежащие одновременно как одному, так и другому множеству, то для множеств
M1 и M2 предидущего примера M4 = M1  M2, или M4 = M1∙M2,
или M4 = {b,c}.
Если имеются два множества M1 = {a,b,c,d,e} и В = {1,2,3}, то их
пересечение не содержит ни одного общего элемента, точнее содержит
пустое множество элементов, и это будет
записываться так: M1  B = Æ .
Например, пусть А – множество
умеющих играть в шахматы в студенÀ
ческой группе, а В – множество пловB
цов (умеющих плавать) в этой же группе, тогда А∙В или А  В есть множество
тех шахматистов, которые умеют плаРис. 3
вать.
9
Для пересечения (умножения) множеств выполняются:
а) переместительный (коммутативный) закон А∙В = В∙А или А  В=
= В  А,
т.е. понятно ,что «множество А∙В это множество шахматистов,
которые умеют плавать», и «множество плавцов, которые умеют
играть в шахматы» – это одно и тоже множество.
б) столь же очевидно, что для пересечения (умножения) множеств справедлив сочетательный (ассоциативный) закон, т.е. для
любых трёх множеств А, В, и С: (А∙В)∙С = А∙(В∙С), любое из этих множеств можно обозначить просто А∙В∙С.
Геометрически (рис. 4) это означает, что при пересечении трёх
множеств А,В,С, множество А∙В∙С покрыто тройной штриховкой.
в) для любых трёх множеств А,В и С выполняется также распределительный (первый дистрибутивный) закон: (А + В)∙С = А∙С + В∙С.
Вернёмся к особым множествам – пустое множество и множество-единица. Если бы не причислять к числу множеств пустое
множество Æ , то мы не смогли бы указать пересечения любых двух
множеств, например таких, как представлено на рис. 5.
Пересечение множеств А и В пустое, как например множество
студентов в группе и множество слонов. Вот почему мы писали
А + Æ = А.
Вернёмся к множеству-единице I. Это множество такое ,что
пересечение (произведение) его и любого множества А совпадает с А. Это
множество I должно содержать вообще все элементы всех множеств.
В таком случае под I будем понимать «самое большое множество»,
содержащее все рассматриваемые нами элементы (предметы)
в предыдущих множествах (множество студентов в группе, множество
всех элементов в таблице Менделеева, множество всех точек квадрата).
A
B
C
Рис. 4
10
À
B
Рис. 5
Это особое множество I (рис. 6) в алгебре
множеств называется единичным или
универсальным множеством.
Очевидно ,что для любого множества из «меньших множеств», например
А (даже если А совпадает с I), мы будем
иметь: А∙I = А и А + I = I.
Рис. 6
В этом глубокое отличие единичного множества от числа 1. Какое бы множество А мы не сложили
(объединили) с единичным, получим тоже множество I, т.к. по
определению множество I является «самым большим» и поэтому
увеличить ещё его уже невозможно. В заключение отметим ещё
два закона алгебры множеств, противоречащих представлениям,
полученным при изучении элементарной алгебры. Очевидно ,что
каким бы ни было множество А, объединение его со вторым таким же множеством, совпадает с исходным множеством А. Точно
также, пересечение множества А с самим собой, тоже совпадает
с исходным множеством А, т.е. А + А= = А. Эти два последних равенства называют идемпотентным законом (законом идемпотентности).
Как мы видим, в алгебре множеств действуют законы во многом
похожие на знакомые нам из курса школьной математики законы
алгебры, относящиеся к числам, но они не дублируют полностью
числовые законы. т.е. в алгебре множеств, как мы увидим, имеют
место почти все основные законы, справедливые для чисел, но вместе с ними в ней выполняются и другие законы, которые вероятно
могут показаться необычными. Например, в алгебре чисел а + 1≠1,
а в алгебре множеств всегда А + I = I, А∙I = А.
Совершенно новыми для нас являются законы идемпотенции,
т.е. А + А = А, А∙А = А. Эти законы иногда выражают в виде утверждения о том, что в алгебре множеств нет ни показателей степени, ни
коэффициентов:
À × À ×
À
× À ×¼.×
À = À,
À + À + À + À +¼. + À = À, 

I
n ðàç
n ðàç
каким бы не было множество А и число n. Поэтому, например, если
В – подмножество в А, т.е. В Ì А, то справедливы равенства В∙А = В
и В + А = А.
Весьма своеобразно «раскрытие скобок» в алгебре множеств –
об этом говорит второй дистрибутивный закон – в алгебре мно11
жеств, всегда (т.е. при любых множествах А,В, и С) имеет место
равенство
А∙В + С = (А + С)∙(В + С),
хотя с точки зрения чисел это равенство неправильное («неполное»).
Приведем графическую иллюстрацию второго дистрибутивного закона. На рис. 7 штриховкой с правым наклоном покрыто пересечение
А∙В множеств А и В, а штриховкой с левым наклоном множество С. Вся
заштрихованная фигура (с левыми и правыми наклоном) изображает множество А∙В + С.
На рис. 8 горизонтальными линиями заштриховано объединение
двух множеств А и С, т.е. А + С, а вертикальными линиями заштриховано объединение двух множеств В и С, т.е. В + С.
«Cеткой» покрыто на рис. 8 пересечение (А + С)∙(В + С) этих двух
объединений. Легко увидеть, что фигура покрытая на рис. 8 сеткой
(из горизонтальных и вертикальных линий) в точности совпадает
с заштрихованной на рис. 7 ,что и доказывает второй дистрибутивный закон. Примеры действия этих двух законов.
Пример 1.
À + Ñ )× ( Â + Ñ )
(


À×
= À × ( À × Â + Ñ) =
âòîðîé äèñòðèáóòèâíûé çàêîí
=
À× À

× Â + À × Ñ = À × Â + À × Ñ. èäåìïîòåíòíîñòü
Пример 2. А∙(А + В) = А∙А + А∙В = А + А∙В = А∙I + A∙B = A∙(I + B) = A∙I = A.
Пример 3. А∙В + А = А∙В + А∙I = А∙(В + I) = А∙I = А.
Именно это отличие законов алгебры множеств от законов алгебры чисел, во многих учебниках по дискретной математике стало
B
B
А
А
С
С
Рис. 7
12
Рис. 8
причиной того, что объединение (сложение) множеств и пересечение
(умножение) множеств обозначаются не обычными алгебраическими знаками «+» и «∙», а совершенно иначе (т.е. другой символикой):
– объединение множеств А и В обозначают A  B,
– пересечение множеств А и В – через A  B.
1.4. Разбиение множеств
Часто некоторое множество является суммой своих подмножеств, но никакие два из этих подмножеств не имеют общих элементов (т.е. эти подмножества не пересекаются). В этом случае
говорят, что множество А разбито на непересекающиеся подмножества. Разбиение на такие подмножества часто полезно для классификации объектов. Например, составляют каталог книг (множество книг) в библиотеке. Сначала книги разбиваются на подмножества:
– художественная литература;
– книги по общественно политическим наукам;
– книги по естественным наукам;
– книги по техническим наукам и т.д.
После этого подмножества разбиваются на более мелкие подмножества:
– художественную литературу разбивают на прозу и поэзию;
– книги по общественным наукам – на книги по философии, политической экономии, культурологии и т.д.;
– книги по естественным наукам – на книги по физике, математике и т.д.
Такое разбиение позволяет быстро найти нужную книгу. Очевидно, что одно и то же множество можно разбивать на подмножества разными способами. Например, для одного и того же множества книг в библиотеке составляется алфавитный каталог, т.е. множество книг разбивается на подмножество книг, авторы которых
имеют фамилии начинающиеся на букву А, на подмножество книг,
фамилии авторов которых начинаются на букву Б и т.д. После этого
каждое полученное подмножество разбивают в соответствии со второй буквой фамилии и т.д.
При разбиении множества на подмножества часто используют
понятие эквивалентности элементов. Для этого определяют, что
значит «элемент х эквивалентен элементу у», после чего объединяют эквивалентные элементы в одно подмножество. Для понятия эквивалентности должны выполняться три следующих условия:
а) каждый элемент сам себе эквивалентен;
13
б) если элемент х эквивалентен элементу у, то элемент у эквивалентен элементу х;
в) если х эквивалентен у и у эквивалентен z, то элемент х эквивалентен z.
1.5. Вычитание множеств
Там где есть сложение (объединение), обычно существует
и вычитание. Не являются в этом смысле исключением и множества. Разностью множеств А и В называют новое множество
А–В, в которое входят все элементы множества А, не принадлежащие множеству В. На рис. 9 разность А–В это множество
точек заштрихованной области (серповидной фигуры) без дуги
MN, А–В = А–А∙В.
При этом совсем не обязательно, чтобы множество В было частью множества А. Если В не является частью А, то вычитание В из
А сводится к удалению из А общей части А и В. Например:
А – множество всех обучающихся в группе,
В – множество студенток в этой группе,
А–В – множество студентов (юношей) в группе.
В том случае, если множество В является частью множества А,
то А–В называют дополнением к множеству В в А. Условно обозначается это таким образом BA′.
Например:
– дополнением множества четных чисел в множество всех целых
чисел является множество нечетных чисел;
– дополнением множества студенток В в группе в множество А
всех обучающихся в этой же группе, является BA, т.е. число студентов – юношей.
Дополнение множества В в универсальное единичное множество I
(рис. 10), вместо BI′ пишут просто B′.
Следует обратить внимание на то,
что некоторые формулы алгебры чисел
M
.
перестают быть верными для вычитания множеств. Так, например, в алгеB
бре множеств (A + B) – – C≠A + (B – C)
A
Почему? В самом деле, если все три
.
множества совпадают, т.е. А = В = С,
то левая часть является пустым мноN
жеством, а правая часть – множество
А, и Æ ≠А.
Рис. 9
14
1.6. Прямое произведение множеств
Bʹ
Прямым произведением множеств А и В
(обозначается произведение AxB) являются
AB
множество всех пар a∙b, где a ∈ A, b ∈ B.
Например,
A = {a,b,c} и B = {1,2}.
Элементами прямого произведения этих
Рис. 10
множеств будут
AxB = {a∙1,a∙2,b∙1,b∙2,c∙1,c∙2}
Пусть А – конечное множество, элементами которого являются
символы (буквы, цифры, знаки препинания, знаки операций). Такое множество символов называется алфавитом. Элементы множества An именуются словами длиной n в алфавите А (т.е. число
символов n в слове – длина слова). Всё множество слов в алфавите
А может быть односимвольными словами – A1, двухсимвольными
словами – A2 и т.д. Поэтому, множество всех слов в алфавите А – это
множество, являющееся объединением A1  A2  A3  … An.
Рассмотрим две полезные теоремы:
1) пусть A1,A2,A3,A4…,An – конечные множества, каждое из которых имеет свою мощность |Ai| = Mi.
Тогда мощность прямого произведения A1∙A2 ∙A3∙∙ … ∙ An равна
произведению мощностей этих множеств M1∙M2∙M3∙…∙Mn, для n =
1 это утверждение очевидно.
2) если для конечного множества А, его мощность |A| = n, то число
всех подмножеств множества А равно 2n. Например, для множества
A = {a,b,c} его мощность |A| = 3. Подмножества, т.е. слова в этом алфавите, будут следующие:
– {Æ }
– {a}
– {b}
– {c}
– {a∙b}
– {a∙c}
– {b∙c}
– {a∙b∙c}
т.е. 23 = 8.
Слова единичной длины отождествляются с буквами алфавита.
Все подмножества включают слова положительной длины (т.е. состоящие не менее чем из одной буквы) а так же и пустое слово – не
содержащее ни одной буквы.
15
2. АЛГЕБРА МНОЖЕСТВ
2.1. Основные законы алгебры множеств
Мы познакомились с действиями над множествами и некоторыми свойствами (иногда необычными) этих действий. Приведём
в виде таблицы (табл. 1) список всех основных свойств действий над
множествами, и в этом списке, как и ранее, обозначим через Æ – пустое множество, I – единичное (универсальное) множество, А′ – дополнение множества А в универсальное множество I.
Таблица 1
Номер
свойства
Свойства действий над множествами
Примечания
1
A⊂A
А содержит множество А
2
3
4
если A ⊂ B и B ⊂ A, то A = B
если A ⊂ B и B ⊂ C, то А ⊂ С
5
6
A⊂I
A+B=B+A
7
A∙B = B∙A
Коммутативный закон для
умножения (пересечения)
множеств
8
A + (B + C) = (A + B) + C
Ассоциативный закон для
сложения (объединения) множеств
9
A∙(B∙C) = (A∙B)∙C = (A∙C)∙B
Ассоциативный закон для
умножения (пересечения)
множеств
10
A+A=A
11
A∙A = A
Идемпотентный закон для
сложения (объединения) множеств
Идемпотентный закон для
умножения (пересечения)
множеств
12
A∙ (B + C) = A∙B + A∙C
13
A + B∙C = (A + B) (A + C)
14
A+ Æ =A
16
Æ⊂A
Коммутативный закон для
сложения (объединения) множеств
Первый дистрибутивный закон для множеств
Второй дистрибутивный закон
для множеств
Свойство пустого множества
Окончание табл. 1
Номер
свойства
Свойства действий над множествами
Примечания
15
A∙I = A
16
A+I=I
17
A∙ Æ = Æ
Если А ⊂ B (A подмножество
в B), то A + B = B и A∙B = A
Свойство единичного множества
Свойство единичного множества
Свойство пустого множества
18
19
20
A + A′ = I
21
Æ′=I
22
I′= Æ
(A′)′ = A
Соотношение A ⊂ B (множество A содержится в B)
эквивалентно B ′⊂ A′
(A + B) ′ = A ′∙ B′
(A∙B)′ = A ′ + B ′
Смотри рис. 11
A∙A′ = Æ
23
24
25
26
Смотри рис. 12
С помощью свойств 1…26 (табл. 1) можно выполнять действия
над множествами аналогично тому, как в алгебре выполняют действия над числами.
Полезно знать:
1) А∙В = (A′ + B′)′, по свойству 26.
2) (A′ + B′)′ + (A′ + B)′ = A, т.к. (A′ + B′)′ = A∙B и (A′ + B)′ = (A′)′∙B′,
тогда A∙B + A∙B′ = A∙(B + B′) = A∙I = А. Все эти свойства (табл. 1) мож-
Bʹ
B
A
Aʹ
B
A
Рис. 11
Рис. 12
17
но легко доказать через две операции над множествами – сложение
(объединение) и образование дополнения.
2.2. Упражнения
Доказать следующие равенства, в которых большими буквами
обозначены множества (буква Æ всегда обозначает пустое множество, а буква I – единичное множество):
1. (A + B)∙(A + C) (B + D)∙(C + D) = A∙D + B∙C
2. A∙(A + B) = A
3. A∙B + A = A
4. A∙(A + C)∙(B + C) = A∙B + A∙C
5. A∙(A + I)∙(B + Æ ) = A∙B
6. (A + B)∙(B + C)∙(C + A) = A∙B + B∙C + C∙A
7. (A + D)∙(B + D) ∙ (C + D) = A∙B∙C + D
8. (A + B)∙(B + C)∙(C + D) = A∙C + B∙C + B∙D
9. (A + B)∙(A + I) + (A + B)∙(B + Æ ) = A + B
10. (A + B)∙(B + I)∙(A + Æ ) = A
11. (A + B + C)∙(B + C + D)∙(C + D + A) = A∙B + A∙D + B∙D + C
18
3. ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ ЛОГИКИ
3.1. Логическая переменная. Логическая функция
Логической переменной называется такая переменная х, которая может принимать только одно из двух значений: 0 или 1.
Высказывание – это такое предположение, о котором можно говорить, что оно истинно или ложно.
Любое высказывание можно обозначить величиной х и говорить,
что высказывание истинно, если соответствующая ему величина
х = 1, и ложно, если х = 0.
Логическая функция – это функция f ( x1, x2 ,…, xn ), которая
принимает значения 0 или 1 на наборе логических переменных
x1, x2 ,…, xn .
3.2. Логическая функция от одной переменной f(x)
Функцию f ( x ) можно представить в виде таблицы истинности.
Таблица истинности содержит следующую информацию. Левый
столбец задает все наборы переменных, на которых существует заданная функция, таким образом определяется количество строк
в таблице. Это количество определяется величиной 2n , где n – количество переменных, от которых зависит логическая функция.
Для функции от одной переменной наборов, на которых существует эта функция, т. е. количество строк в таблице истинности, равно
n
1
2=
2=
2.
Полное количество логических функций, зависящих от n пере2n
менных, равно 2 .
Для функции,
зависящей от одной переменной, это количество
21
равно = 2 = 4.
Объединим в одной таблице истинности четыре таблицы (табл. 1)
и представим в ней все четыре функции, зависящие от одной переменной:
f1(x) – функция «константа 0»; абсолютно ложная функция; функция, принимающая значения 0 при любых значениях переменной;
f2(x) – функция «константа 1»; абсолютно истинная функция;
функция, принимающая значения 1 при любых значениях переменных;
f3(x) – тождественная функция; f3(x) ≡ х; функция, принимающая значения переменной;
f4(x) – функция логического отрицания; функция инверсии;
функция НЕ; f4 ( x ) = x = ¬x .
19
Таблица 1
X
f1(x)
f2(x)
f3(x)
f4(x)
0
1
0
0
1
1
0
1
1
0
3.3. Логическая функция от двух переменных
Определим размеры таблицы истинности для представления любых функций, зависящих от двух переменных.
Количество наборов, на которых определена данная функция,
равно
2n2 = 22 = 4. Всего функций, зависящих от двух переменных:
2n
2
2=
2=
16.
Таблица 2
x1x2
f1 ( x1, x2 )
f2 ( x1, x2 )
f3 ( x1, x2 )
f4 ( x1, x2 )
00
01
10
11
0
1
1
1
1
0
0
0
0
0
0
1
1
1
1
0
Представим в таблице истинности четыре основные функции, зависящие от двух переменных, которые наиболее часто используются на практике (табл. 2):
f1 ( x1, x2=
) x1 ∨ x2 – функция дизъюнкции, логического сложения, функция ИЛИ;
f2 ( x1, x2=
) x1 ∨ x2 – функция инверсии логического сложения,
функция Пирса, функция ИЛИ-НЕ;
f3 ( x1, x2=
) x1 * x=
2 x1 ∨ x2 – функция конъюнкции, функция логического умножения, функция И;
f4 ( x1, x2 ) = x1x2 – функция инверсии конъюнкции, функция
Шеффера, функция И-НЕ.
1.4. Свойства логических переменных и логических функций
Логическая переменная х обладает следующими свойствами:
1) x = x – двойное отрицание переменной равно исходной переменой;
x ∨ x ∨ ... ∨ x =
x
 – правила, позволяющие сократить длину
2)
x * x *...* x = x 
логического выражения;
3) x ∨ 0 =
x,
20
x * 0 = 0 ;
4) x ∨ 1
=
1
,
x * 1 = x;
5) x ∨ x =
1,
x * x = 0 .
Справедливость представленных свойств можно проверить путем простого подставления значений 0 или 1 для переменной х.
Дизъюнкция и конъюнкция обладают рядом свойств, аналогичных свойствам арифметических операций сложения и умножения.
1. Свойство ассоциативности (сочетательный) закон:
x1 ∨ ( x2 ∨ x3 ) = ( x1 ∨ x2 ) ∨ x3 , (1)
x1 ( x2 x3 ) = ( x1x2 ) x3 . (2)
2. Свойство коммутативности (переместительный) закон:
x1 ∨ x2 = x2 ∨ x1, (3)
x1x2 = x2 x1. (4)
3. Свойство дистрибутивности (распределительный) закон:
x1 ( x2 ∨ x3 ) = x1x2 ∨ x1x3 , (5)
x1 ∨ x2 x3 =
( x1 ∨ x2 )( x1 ∨ x3 ). (5а)
4. Свойства, позволяющие перейти от операции дизъюнкции
к операции конъюнкции и наоборот (законы де Моргана):
x1 ∨ x2 =
x1 x2 , (6)
x1 x2= x1 ∨ x2 . 5. Законы поглощения:
x1 ( x1 ∨ x2 )
= x1, x1 ∨ x1x2 =
x1. (7)
(8)
(9)
6. Законы склеивания:
x1x2 ∨ x1 x2 =
x1, (10)
(x1 ∨ x2 )(x1 ∨ x2 ) =
x1. (11)
21
4. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ ФУНКЦИЙ
АЛГЕБРЫ ЛОГИКИ
Любую логическую функцию можно представить при помощи
таблицы истинности. Но эта довольно громоздкий способ, так как
чем больше переменных, от которых зависит функция, тем больше
наборов, на которых определена эта функция, т. е. больше строчек
в таблице. Поэтому при большом количестве переменных предпочтительнее аналитический способ задания функций, который дает
более компактную запись.
4.1. Представление логических функций
в дизъюнктивной нормальной (ДНФ) и совершенной
дизъюнктивной нормальной формах (СДНФ)
Конъюнкция нескольких переменных, каждая из которых входит
в нее не больше одного раза с инверсией или без нее, называется элементарной конъюнкцией, элементарным произведением, минтермом, конституэнтой единицы.
Дизъюнкция нескольких элементарных конъюнкций называется дизъюнктивной нормальной формой представления логической
функции. Например:
f ( x1, x2 , x3 )= x1x2 x3 ∨ x1 x3 ∨ x2 x3 . (12)
Дизъюнктивная нормальная форма представления функции называется совершенной дизъюнктивной нормальной формой, т. е.
ДНФ называемой СДНФ, если каждая переменная, от которых зависит функция, входит в каждую элементарную конъюнкцию только один раз с инверсией или без нее. Например:
f ( x1, x2 , x3 ) = x1x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 (13)
т. е. в выражении (12) во вторую конъюнкцию должна войти переменная х2, а в третью конъюнкцию – переменная х1.
Любая логическая функция может быть представлена в СДНФ.
4.2. Представление логических функций
в конъюнктивной нормальной (КНФ) СДНФ
Дизъюнкция нескольких логических переменных, в которую
каждая переменная входит не более одного раза с инверсией или
без нее, называется элементарной дизъюнкцией, макстермом, конституэнтой нуля.
22
Конъюнкция нескольких элементарных дизъюнкций называется конъюнктивной нормальной формой представления функции
КНФ. Например:
(
)(
)
f ( x1, x2 , x3 ) = x1 ∨ x3 x1 ∨ x2 ∨ x3 ( x2 ∨ x3 ). (14)
Конъюнктивная нормальная форма представления логической функции называется совершенной конъюнктивной нормальной формой, т. е. КНФ называется СКНФ, если каждая переменная, от которых зависит функция, входит в каждую элементарную дизъюнкцию не более одного раза с инверсией или без
нее. Например:
(
)(
)
f ( x1, x2 , x3 ) = x1 ∨ x2 ∨ x3 x1 ∨ x2 ∨ x3 ( x1 ∨ x2 ∨ x3 ), (15)
т. е. в выражении (14) в первую дизъюнкцию должна войти переменная х2, а в третью дизъюнкцию – переменная х1.
4.3. Ранги термов и суммы рангов ДНФ, СДНФ, КНФ и СКНФ
представления функций
Элементарные дизъюнкция и конъюнкция называются термами. Количество переменных, составляющих терм, образует ранг
терма. Например, для конъюнкции x1 x2 x3 ранг терма r = 3, для
дизъюнкции x1 ∨ x2 ранг терма r = 2.
Для выражения (12) сумма рангов R = r1 + r2 + r3 = 3 + 2 + 2 = 7.
Для выражения (15) сумма рангов R = r1 + r2 + r3 = 3 + 3 + 3 = 9.
Совершенные формы представления функций отличаются от
нормальных форм суммой рангов. В совершенных формах сумма
рангов больше, так как ранг каждого терма в представлении функции максимален. Максимум ранга определяется количеством переменных, от которых зависит логическая функция.
4.4. Способ представления логической функции
в СДНФ и СКНФ
Представим таблицу истинности, например, для так называемой мажоритарной функции, которая зависит от трех переменных
(табл. 3). Для этой функции значения на каждом наборе переменных определяются значением большинства логических переменных. Определим размеры таблицы истинности в этом случае. Так
как функция зависит от трех переменных, то количество наборов,
на которых определена функция, равно 23, т. е. 8. Таким образом,
в таблице истинности будет 8 строк.
23
Таблица 3
x1,x2,x3
f1(x1,x2,x3)
000
0
x1 ∨ x2 ∨ x3
001
0
x1 ∨ x2 ∨ x3
010
0
x1 x2 x3
011
1
100
0
101
1
x1 x2 x3
110
1
x1x2 x3
111
1
x1x2 x3
СДНФ
СКНФ
x1x2 x3
x1 ∨ x2 ∨ x3
Получим представление функции в СДНФ. В этой форме элементарные конъюнкции объединяются знаками дизъюнкции. Поэтому в столбце СДНФ в таблице истинности нужно представить конъюнкции. Поскольку конъюнкция – это конституэнта единицы, то
нужно для единичных значений функции представить конъюнкции, в которых единичные переменные для соответствующего набора берутся без инверсии, а нулевые – с инверсией. Теперь нужно
объединить полученные конъюнкции знаком дизъюнкции:
f ( x1, x2 , x3 ) = x1x2 x3 ∨ x1 x2 x3 ∨ x1x2 x3 ∨ x1x2 x3 . (16)
Получим представление функции в СКНФ. В этой форме элементарные дизъюнкции объединяются знаком конъюнкции. Поэтому
в столбце СКНФ в таблице истинности нужно представить дизъюнкции. Поскольку дизъюнкция – это конституэнта 0, то нужно
для нулевых значений функции записать дизъюнкции, причем единичные переменные соответствующего набора переменных берутся
с инверсиями, а нулевые – прямыми. Теперь нужно объединить полученные дизъюнкции знаками конъюнкции:
(x1, x2 , x3 ) =
(17)
= (x1 ∨ x2 ∨ x3 )(x1 ∨ x2 ∨ x3 )(x1 ∨ x2 ∨ x3 )(x1 ∨ x2 ∨ x3 ).
24
5. РЕАЛИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ
ПРИ ПОМОЩИ ЛОГИЧЕСКИХ ЭЛЕМЕНТОВ
5.1. Логические элементы
Информация в ЦВМ представляется в двоичном коде. Физическими аналогами 0 и 1 являются сигналы, принимающие два хорошо различимых значения. Например, потенциалы высокого и низкого уровней – потенциальный код, отсутствие или наличие электрического импульса – импульсный код.
Преобразование информации в ЦВМ сводится к согласованному
изменению значений сигналов и описывается в термах алгебры логики. Для реализации операций над двоичными сигналами используются логические элементы.
Логическим элементом называется электрическая схема, реализующая элементарную логическую функцию и имеющая количество входов, равное числу аргументов функции, и только один
выход. Входные сигналы, поступающие на входы логического элемента, определяют значения входных переменных. Значение выходного сигнала является функцией значений входных сигналов.
Для выполнения операций отрицания, дизъюнкции и конъюнкции
используются логические элементы НЕ, ИЛИ, И.
Система из элементов ИЛИ и НЕ, а также И и НЕ являются функционально полными, т. е. из подобных элементов можно построить
схемы, реализующие любые заданные логические функции. На
рис. 1 представлены условные обозначения логических элементов:
НЕ, ИЛИ, И, ИЛИ-НЕ, И-НЕ:
а – нвертор – инвертирует только потенциальные сигналы. Для
инвертирования импульсных сигналов используются элементы
И-НЕ, ИЛИ-НЕ;
ИЛИ
НЕ
x
x
x1 1
x1∨x2
x2
а
И
x1 &
x1x2
1
x1∨x2
x2
x2
б
ИЛИ-НЕ
x1
в
г
И-НЕ
x1
&
x2
x1x2
д
Рис. 1. Условные обозначения логических элементов
25
x
1
x
x∨x =x
x
1
x∨0=x
x
Рис. 2
б – элемент ИЛИ – реализует операцию дизъюнкции, называется дизъюнктором;
в – элемент И – реализует операцию конъюнкции, называется
конъюнктором;
г – элемент ИЛИ-НЕ – является комбинацией дизъюнктора и инвертора, называется элементом Пирса (Р). Может использоваться
в качестве инвертора для импульсных сигналов (рис. 2). В этом случае на оба входа двухвходового элемента Пирса необходимо подать
переменную, которую нужно проинвертировать, или же подать на
один вход переменную, а на второй вход 0.
д – элемент И-НЕ – является комбинацией конъюнктора и инвертора, называется элементом Шеффера (S). Аналогично элементу
Пирса может использоваться в качестве инвертора для импульсных
сигналов (рис. 3). В этом случае на оба входа двухвходового элемента Шеффера необходимо подать переменную, которую нужно проинвертировать или же подать на один вход переменную, а на второй
вход 1.
5.2. Логические и комбинационные схемы
Последовательное соединение логических элементов, при котором выход одного элемента соединен с входом другого элемента, соответствует подстановке в логические функции в качестве аргументов других логических функций.
Совокупность логических элементов, организованная для выполнения операций над двоичными переменными (сигналами), называется логической схемой.
В зависимости от класса реализуемых функций логические схемы подразделяются на комбинационные и последовательностные.
Логическая схема, реализующая систему логических функций,
называется комбинационной схемой.
x
1
x
x* x = x
x
1
Рис. 3
26
1
x *1 = x
Выходные сигналы комбинационных логических схем в отличие от последовательностных схем, имеющих память, определяются только значениями входных сигналов в любой данный момент
времени.
5.3. Примеры построения логических схем
для реализации логических функций
Для реализации мажоритарной функции из п. 2.4 повторим аналитическое выражение этой функции в СДНФ (16):
f ( x1, x2 , x3 ) = x1x2 x3 ∨ x1 x2 x3 ∨ x1x2 x3 ∨ x1x2 x3 . Поскольку это выражение состоит из четырех элементарных
конъюнкций, то потребуется для построения логической схемы
четыре конъюнктора, а поскольку ранг каждой конъюнкции равен 3, то конъюнкторы должны иметь по 3 входа. Выходы конъюнкторов нужно подать на дизъюнктор, так как конъюнкции в СДНФ
объединяются знаком дизъюнкции. Дизъюнктор будет четырехвходовым.
При построении схемы нужно учесть, что значения переменных
будут подаваться на входы конъюнкторов с генератора. Код подачи
может быть монофазным. В этом случае значения переменных будут только прямыми. Если нужны и инверсные значения, то потребуется парафазный код подачи переменных. В выражении (16) имеются как прямые, так и инверсные значения переменных, поэтому
будем использовать парафазный код подачи переменных. На рис. 4
приведена логическая схема реализации мажоритарной функции,
представленной в СДНФ.
Представим логическую схему мажоритарной функции в СКНФ.
Для этого повторим выражение этой функции в СКНФ (17):
(
f ( x1, x2 , x3 ) =
)(
)(
)
= ( x1 ∨ x2 ∨ x3 ) x1 ∨ x2 ∨ x3 x1 ∨ x2 ∨ x3 x1 ∨ x2 ∨ x3 .
Для построения схемы нужны четыре дизъюнктора, так как
в выражении имеются четыре дизъюнкции. Дизъюнкторы будут трехвходовыми, поскольку ранг дизъюнкции равен 3. Выходы дизъюнкторов подаются на конъюнктор, который должен
иметь четыре входа. Для схемы будет использоваться парафазный код подачи переменных с генератора на входы дизъюнкторов. На рис. 5 представлена схема, реализующая мажоритарную
функцию в СКНФ.
27
x1 x1 x2 x2 x3 x3
&
x1,x2,x3
&
x1,x2,x3
1
f(x1,x2,x3)
&
x1,x2,x3
&
x1,x2,x3
Рис. 4
x1 x1 x2 x2 x3 x3
&
x1∨x2∨x3
&
x1∨x2∨x3
1
f(x1,x2,x3)
&
x1∨x2∨x3
&
x1∨x2∨x3
Рис. 5
3.4. Функционально полные системы логических функций
Операция, в результате которой в качестве аргументов одной
логической функции используются значения других логических
функций, называется суперпозицией.
Одни логические функции можно выражать через другие.
Система функций алгебры логики называется функционально
полной, или базисом, если она позволяет через суперпозицию доста28
точного количества повторений этой системы выразить любую логическую функцию.
К базису относится система функций И-ИЛИ-НЕ. Базисами также являются системы, содержащие функции Шеффера и Пирса.
Базисы могут быть избыточными и минимальными.
Базис является минимальным, если удаление хотя бы одной
функции превращает систему в неполную.
Базис И-ИЛИ-НЕ является избыточным, так как из него возможно удаление некоторых функций по законам де Моргана.
4. Использование законов де Моргана для построения логических схем, реализующих функции алгебры логики
29
4. ИСПОЛЬЗОВАНИЕ ЗАКОНОВ ДЕ МОРГАНА
ДЛЯ ПОСТРОЕНИЯ ЛОГИЧЕСКИХ СХЕМ, РЕАЛИЗУЮЩИХ
ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ
4.1. Перевод логической функции, представленной
в СДНФ, в СКНФ
Для того чтобы поменять знак одной логической операции на
другой, в данной задаче знак дизъюнкции на знак конъюнкции
между термами, т. е. перейти от СДНФ к СКНФ, необходимо воспользоваться законами де Моргана (см. выражения (6) и (7)).
Повторим логическую функцию в СДНФ (16):
f ( x1, x2 , x3 ) = x1x2 x3 ∨ x1 x2 x3 ∨ x1x2 x3 ∨ x1x2 x3 . По законам де Моргана (6), т. е. используя отрицание дизъюнкции, перейдем к знаку конъюнкции, но переменные возьме с отрицаниями.
Таким образом, в выражении (16) необходимо отрицание над
знаками дизъюнкции. Одно отрицание проинвертирует значение
функции, поэтому воспользуемся двойным отрицанием, т. е.
f ( x1, x2 , x3 ) = x1x2 x3 ∨ x1 x2 x3 ∨ x1x2 x3 ∨ x1x2 x3 , = (18)
Верхняя инверсия остается без изменений, а нижняя по выражению (6) разрывается и меняет знак дизъюнкции на знак конъюнкции, т. е.
= x1x2 x3 * x1 x2 x3 * x1x2 x3 * x1x2 x3 , = (19)
В выражении (19) над элементарными конъюнкциями появились инверсии. По законам де Моргана (7) отрицание конъюнкции
дает дизъюнкцию отрицаний: xy= x ∨ y , поэтому
(
) (
) (
)
= (x1 ∨ x2 ∨ x3 ) * x1 ∨ x2 ∨ x3 * x1 ∨ x2 ∨ x3 * x1 ∨ x2 ∨ x3 . (20)
Таким образом, логическая функция в СДНФ (16), после использования законов де Моргана записывается как выражение (20), а
это – инверсия СКНФ.
Поэтому можно сделать вывод, что
30
ÑÄÍÔ = ÑÊÍÔ. (21)
4.2. Перевод логической функции,
представленной в СКНФ, в СДНФ
Повторим логическую функцию в СКНФ (17):
(
)(
)(
)
f ( x1, x2 , x3 ) = ( x1 ∨ x2 ∨ x3 ) x1 ∨ x2 ∨ x3 x1 ∨ x2 ∨ x3 x1 ∨ x2 ∨ x3 .
Для перевода этой функции в СДНФ проведем преобразования
из п. 4.1.
f ( x1, x2 , x3 ) =
(
)(
)(
)
= ( x1 ∨ x2 ∨ x3 ) ∨ ( x1 ∨ x2 ∨ x3 ) ∨ ( x1 ∨ x2 ∨ x3 ) ∨ ( x1 ∨ x2 ∨ x3 ) =
= ( x1 ∨ x2 ∨ x3 ) x1 ∨ x2 ∨ x3 x1 ∨ x2 ∨ x3 x1 ∨ x2 ∨ x3 =
= x1 x2 x3 ∨ x1 x2 x3 ∨ x1x2 x3 ∨ x1 x2 x3
(22)
Выражение (22) – это инверсия от СДНФ.
Таким образом, ÑÄÍÔ = ÑÊÍÔ. (23)
4.3. Построение логических схем в базисе Шеффера
для логической функции, заданной в СДНФ
Повторим функцию в СДНФ (16):
f ( x1, x2 , x3 ) = x1x2 x3 ∨ x1 x2 x3 ∨ x1x2 x3 ∨ x1x2 x3 .
x1 x1 x2
x2 x3 x3
&
&
&
f(x1,x2,x3)
&
&
Рис. 6
31
x1 x2 x3
&
&
&
&
&
f(x1,x2,x3)
&
&
&
Рис. 7
Чтобы реализовать эту функцию в базисе Шеффера, нужно
вспомнить, что базис Шеффера – это операции И-НЕ. Здесь отсутствует операция дизъюнкции, которая присутствует в СДНФ (16).
Воспользуемся законами де Моргана, т. е. возьмем двойное отрицание от выражения (16), т. е.
f ( x1, x2 , x3 ) = x1x2 x3 ∨ x1 x2 x3 ∨ x1x2 x3 ∨ x1x2 x3 , = , (24)
Верхнее отрицание останется без изменения, а нижнее, разрываясь, поменяет знак дизъюнкции на знак конъюнкции по законам де
Моргана (6), т. е.
= x1x2 x3 ∨ x1 x2 x3 ∨ x1x2 x3 ∨ x1x2 x3 , = (25)
Выражение (25) записано в базисе Шеффера, т. е. присутствуют
только операции И-НЕ. Поэтому можно записать:
( (
) (
) (
)
)
= S S x1, x2 , x3 , S x1, x2 , x3 S x1, x2 , x3 S ( x1, x2 , x3 ) . (26)
В выражении (26) под символом S понимается логический элемент Шеффера. В скобках представлены переменные, которые являются входными сигналами соответствующих элементов Шеф32
фера. Поскольку переменные имеют инверсии, то выражение (26)
записано для парафазного хода подачи переменных. На рис. 6 приведена логическая схема для функции (16) в базисе Шеффера для
парафазного кода подачи переменных.
Чтобы представить схему на рис. 6 для монофазного кода подачи
переменных, нужно в выражении (26) для каждой переменой с отрицанием использовать элемент Шеффера (см. п. 3.1, рис. 3). Выражение (26) перепишем для монофазного кода подачи переменных:
f (x1, x2 , x3 ) =
 S ( x1 ), x2 , x3 ), S ( x1, S ( x2 ), x3 ), 
. = (S 
 S ( x1, x2 , S ( x3 ) ), S ( x1, x2 , x3 )  

(27)
На рис. 7 приведена схема для функции (16) в базисе Шеффера
для монофазного кода подачи переменных.
4.4. Построение логических схем в базисе Пирса
для логической функции, заданной в СДНФ
Повторим функцию в СДНФ (16):
f ( x1, x2 , x3 ) = x1x2 x3 ∨ x1 x2 x3 ∨ x1x2 x3 ∨ x1x2 x3 . Чтобы реализовать эту функцию в базисе Пирса, нужно вспомнить, что базис Пирса – это операции ИЛИ-НЕ. Здесь отсутствует операция конъюнкции, которая присутствует в элементарных
x1 x1 x3 x2 x3 x3
1
1
1
1
f(x1,x2,x3)
1
1
Рис. 8
33
x1 x1 x3
1
1
1
1
1
1
1
1
1
1
f(x1,x2,x3)
1
1
1
1
1
Рис. 9
конъюнкциях в СДНФ (16). Воспользуемся законами де Моргана,
т. е. возьмем двойное отрицание для каждой элементарной конъюнкции в выражении (16), т. е.
f ( x1, x2 , x3 ) = x1x2 x3 ∨ x1 x2 x3 ∨ x1x2 x3 ∨ x1x2 x3 = (28)
Все верхние отрицания останутся без изменения, а нижние, разрываясь, поменяют знак конъюнкции в каждом терме в (16) на знак
дизъюнкции по законам де Моргана (7), т. е.
(
) (
) (
)
= (x1 ∨ x2 ∨ x3 ) ∨ x1 ∨ x2 ∨ x3 ∨ x1 ∨ x2 ∨ x3 ∨ x1 ∨ x2 ∨ x3 = (29)
Чтобы выражение (29) можно было представить в базисе Пирса,
нужно взять двойное отрицание от всего выражения, т. е.
(
) (
) (
)
= (x1 ∨ x2 ∨ x3 ) ∨ x1 ∨ x2 ∨ x3 ∨ x1 ∨ x2 ∨ x3 ∨ x1 ∨ x2 ∨ x3 = (30)
34
Выражение (30) записано в базисе Пирса, так как присутствуют только операции ИЛИ-НЕ. Его можно представить в символах
Р, где под каждым символом Р понимается логический элемент
Пирса, т. е.
(
) (
) (
)
= ÐÐ (Ð õ1, õ2 , õ3 , Ð õ1, õ2 , õ3 , Ð õ1, õ2 , õ3 , Ð (õ1, õ2 , õ3 )). (31)
В скобках представлены переменные, которые являются входными сигналами для соответствующих элементов Пирса. Поскольку переменные имеют инверсии, то выражение (31) записано для парафазного кода подачи переменных.
На рис. 8 приведена логическая схема для функции (16) в базисе
Пирса для парафазного кода подачи переменных.
Чтобы представить схему на рис. 8 для монофазного кода подачи переменных, нужно в выражении (31) для каждой переменной с отрицанием использовать элемент Пирса (см. п. 3.1,
рис. 2). Выражение (31) перепишем для монофазного кода подачи
переменных,т. е.
f ( x1, x2 , x3 ) = Ð
Ð ( Ð ( õ1 ), Ð(õ2 ), Ð(õ3 ) ), Ð ( Ð ( õ1 ), õ2 , Ð ( õ3 ) ), Ð ( Ð ( õ1 ), Ð ( õ2 ), õ3 ),
Ð ( Ð ( õ1 ), Ð ( õ2 ), Ð ( õ3 ) ).
(32)
На рис. 9 показана логическая схема для функции (16) в базисе
Пирса для монофазного кода подачи переменных.
4.5. Построение логических схем в базисе Шеффера
для логической функции, заданной в СКНФ
Повторим функцию в СКНФ (17):
(
)(
)(
)
f ( x1, x2 , x3 ) = ( x1 ∨ x2 ∨ x3 ) x1 ∨ x2 ∨ x3 x1 ∨ x2 ∨ x3 x1 ∨ x2 ∨ x3 .
Чтобы реализовать эту функцию в базисе Шеффера, нужно
вспомнить, что базис Шеффера – это операции И-НЕ. Здесь отсутствует операция дизъюнкции, которая присутствует в элементарных дизъюнкциях в СКНФ (17). Воспользуемся законами де Моргана, т. е. возьмем двойное отрицание от каждой элементарной дизъюнкции в выражении (17), т. е.
f ( x1, x2 , x3 ) =
(
)(
)
= ( x1 ∨ x2 ∨ x3 ) x1 ∨ x2 ∨ x3 x1 ∨ x2 ∨ x3 (x1 ∨ x2 ∨ x3 ), = (33)
35
x1 x1 x2 x2 x3 x3
&
&
&
f(x1,x2,x3)
&
&
&
Рис. 10
x1 x2 x3
&
&
&
&
&
&
&
&
&
f(x1,x2,x3)
&
&
&
&
&
&
Рис. 11
36
Все верхние отрицания останутся без изменения, а нижние, разрываясь, поменяют знак дизъюнкции в каждом терме в (17) на знак
конъюнкции по законам де Моргана, т. е.
x x x )( x x x )( x x x )( x x x )
(=
(34)
Чтобы выражение (34) можно было записать в базисе Шеффера,
нужно взять двойное отрицание от всего выражения, т. е.
1 2 3
1 2 3
1 2 3
1 2 3
x x x )( x x x )( x x x )( x x x )
(=
1 2 3
1 2 3
1 2 3
1 2 3
Выражение (35) записано в базисе Шеффера, так как присутствуют
только операции И-НЕ. Его можно представить в символах S, где под
каждым символом S понимается логический элемент Шеффера, т. е.
( (
) (
) (
))
) (
= SS S x1, x2 , x3 S x1, x2 , x3 S x1, x2 , x3 S x1, x2 , x3 . (36)
В скобках представлены переменные, которые являются входными сигналами для соответствующих элементов Шеффера. Поскольку переменные имеют инверсии, то выражение (36) записано
для парафазного кода подачи переменных.
На рис. 10 приведена логическая схема для функции (17) в базисе
Шеффера для парафазного кода подачи переменных.
Чтобы представить схему на рис. 10 для монофазного кода подачи
переменных, нужно в выражении (36) для каждой переменной с отрицанием использовать элемент Шеффера (см. п. 3,1, рис. 3). Выражение
(36) перепишем для монофазного кода подачи переменных, т. е.
f ( x1, x2 , x3 ) = SS ( S ( Sx1 ), S ( x2 ), S ( x3 ) ), S ( S ( x1 ), S ( x2 ), x3 ),
(
)
S ( S ( x1 ), x2 , S ( x3 ) ), S x1,S ( x2 ), S ( x3 ) ).
(37)
На рис. 11 показана логическая схема для функции (17) в базисе
Шеффера для монофазного кода подачи переменных.
4.6. Построение логических схем в базисе Пирса
для логической функции, заданной в СКНФ
Запишем функцию в СКНФ (17):
f ( x1, x2 , x3 ) =
(
)(
)(
)
= ( x1 ∨ x2 ∨ x3 ) x1 ∨ x2 ∨ x3 x1 ∨ x2 ∨ x3 x1 ∨ x2 ∨ x3 .
Чтобы реализовать эту функцию в базисе Пирса, нужно вспомнить, что базис Пирса – это операции ИЛИ-НЕ. Здесь отсутствует
37
операция конъюнкции, которая присутствует в СКНФ (17). Воспользуемся законами де Моргана, т. е. возьмем двойное отрицание
от выражения (17):
f ( x1, x2 , x3 ) =
(
)(
)(
)
= ( x1 ∨ x2 ∨ x3 ) x1 ∨ x2 ∨ x3 x1 ∨ x2 ∨ x3 x1 ∨ x2 ∨ x3 = (38)
Верхнее отрицание останется без изменения, а нижнее, разрываясь, поменяет знак конъюнкции на знак дизъюнкции по законам де
Моргана (7):
(
)(
)(
)
= ( x1 ∨ x2 ∨ x3 ) x1 ∨ x2 ∨ x3 x1 ∨ x2 ∨ x3 x1 ∨ x2 ∨ x3 , = (39)
Выражение (36) записано в базисе Пирса, т. е. присутствуют только
операции ИЛИ-НЕ. Его можно представить в символах Р, где под каждым символом Р понимается логический элемент Пирса, т. е.
= P(P(x1, x2 , x3 ),P(x1, x2 , x3 ), P(x1, x2 , x3 ), P(x1, x2 , x3 )) (40)
В скобках представлены переменные, которые являются входными сигналами для соответствующих элементов Пирса. Поскольку переменные имеют инверсии, то выражение (40) записано для парафазного кода подачи переменных.
На рис. 12 приведена логическая схема для функции (17) в базисе
Пирса для парафазного кода подачи переменных.
x1 x1 x2 x2 x3 x3
1
1
1
1
1
Рис. 12
38
f(x1,x2,x3)
x1 x1 x2
1
1
1
1
1
1
f(x1,x2,x3)
1
1
Рис. 13
Чтобы представить схему на рис. 12 для монофазного кода подачи переменных, нужно в выражении (40) для каждой переменной с отрицанием использовать элемент Пирса (см. п. 3.1, рис. 2).
Выражение (40) перепишем для монофазного кода подачи переменных:
f ( x1, x2 , x3 ) = P(P(x1, x2 , x3 ), P(x1, x2 , P(x3 )),
P(x1, P ( x2 ), x3 ), P(P(x1 ), x2 , x3 )).
(41)
На рис. 13 представим логическую схему для функции (17) в базисе Пирса для монофазного кода подачи переменных.
39
5. МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ
5.1. Понятие диаграммы Вейча
Минимизация – это процесс преобразования логических функций к такому виду, который допускает наиболее простую, с наименьшим числом логических элементов, имеющих наименьшее число
входов, физическую реализацию функции. Частная задача минимизации логических функций сводится к такому представлению заданной функции, которое содержит наименьшее возможное число переменных и наименьшее возможное число операций над ними.
ДНФ и КНФ представления логических функций имеют меньшую сумму рангов, чем СДНФ и СКНФ для этих же функций. Поэтому возникает задача нахождения для логических функций представления их в ДНФ и КНФ с минимальной суммой рангов.
Для небольшого количества переменных (n = 2, 3, 4) приемлемым способом минимизации являются диаграммы Вейча, которые
представляют собой разновидность карт Карно.
Известно, что любую логическую функцию можно задать при помощи таблицы истинности. Диаграмма Вейча – это та же таблица
истинности, только другим образом организованная, так как содержит ту же самую информацию, что и таблица истинности.
Диаграмма Вейча представляет собой квадрат или прямоугольник, разделенные на 2n клеток, где n – количество переменных, от
которых зависит функция.
Если n – четное, то диаграмма Вейча – квадрат, сторона которого
n
разделена на 2 2 клеток.
Ели n – нечетное, то диаграмма Вейча – это прямоугольник,
у которого одна сторона разделена на 2
n −1
2 2
n +1
2
клеток, а вторая – на
клеток.
Но в любом случае общее количество клеток в диаграмме Вейча
2n. Такое же количество строк в таблице истинности, так как 2n –
это количество наборов переменных, на которых существует заданная логическая функция.
В таблице истинности каждому набору переменных ставится в соответствие значение функции, которое она принимает на этом наборе.
В диаграмме Вейча каждая клетка соответствует определенному набору переменных, поэтому в эту клетку проставляется соответствующее значение функции.
40
Чтобы каждая клетка диаграммы Вейча соответствовала определенному набору переменных, проводят разметку диаграммы,
причем таким образом, чтобы для соседних клеток диаграммы был
справедлив закон склеивания.
Рассмотрим диаграмму Вейча для двух переменных. В качестве
примера приведем функцию дизъюнкции (см. п. 1.3, табл. 2).
Таблица истинности функции дизъюнкции, зависящей от двух
переменных, имеет следующий вид (табл. 4).
На рис. 14 представлена диаграмма Вейча для этой функции. Она
является квадратом и содержит 4 клетки.
x1
Проведена правосторонняя разметка. Под
чертой разметки значения переменной –
00
10
единичные, при отсутствии в нулевых
клетках согласно разметке проставлен на0
1
бор переменных, который соответствует
01
11
данной клетке. В самой клетке проставлено значение функции, которое она приниx2
мает на этом наборе.
1
1
Рассмотрим применение закона склеивания (10) для соседских клеток.
Рис. 14
На наборе х1 = 1, х2 = 0 значение функции равно 1. На наборе х1 = 1, х2 = 1 значение функции также равно 1.
Запишем дизъюнкцию элементарных конъюнкций наборов этих
клеток
(
)
x1 x2 ∨ x1x2= x1 x2 ∨ x2 = x1. (42)
Выражение (42) показывает применение закона склеивания для
соседних клеток диаграммы Вейча, что позволяет уменьшить сумму
рангов выражения. В этом и заключается процесс минимизации при
помощи диаграмм Вейча.
Таким образом, разметка диаграммы Вейча должна производиться так, чтобы для соседних клеток был применим закон склеивания,
который позволяет уменьшать сумму рангов выражения.
Таблица 4
х1 х2
f
00
01
10
11
0
1
1
1
41
x2
x1
x3
000
100
110
100
0
0
1
0
001
011
111
101
0
1
1
1
Рис. 15
Рассмотрим диаграмму Вейча для трех переменных и ее разметку.
В данном случае она представляет собой прямоугольник, содержащий 8 клеток, так как функция в этом случае существует на 8
наборах переменных: 23 = 8. На рис. 15 представлена диаграмма
Вейча для мажоритарной функции (см. табл. 3).
В углу каждой клетки проставлен набор переменных в соответствии с приведенной разметкой, а внутри клетки проставлено значение функции, которое она приобретает на этом наборе.
5.2. Соседние клетки и соседние области в диаграмме Вейча
Диаграмма Вейча заполняется так же, как и таблица истинности.
В клетку, которая соответствует набору, где функция принимает
единичное значение, проставляется 1. В клетку, которая соответствует набору, где функция принимает значение «0», может проставляться нуль, но чаще эту клетку оставляют пустой, чтобы не
загромождать диаграмму. Если функция не определена на каком-то
наборе, то в этой клетке ставится прочерк.
Две клетки диаграммы Вейча называются соседними, если они
имеют общее ребро и к конъюнкциям, соответствующим их набором переменных, применим закон склеивания.
В любой диаграмме соседними клетками являются не только
смежные, но и клетки, находящиеся на противоположных концах
любой строки или столбца. Эти клетки становятся смежными (имеющими общее ребро), если диаграмму свернуть по горизонтали или
вертикали в цилиндр, а затем концы полученного цилиндра замкнуть в кольцо.
Соседние клетки объединяются в соседние области. Областями
соседних клеток являются прямоугольники с количеством клеток,
42
кратным 2m. Чем больше клеток входит в соседнюю область, тем
по большему количеству переменных происходит склеивание, тем
меньше будет сумма рангов конечного выражения.
5.3. Пример минимизации мажоритарной
функции по единицам
При записи аналитического выражения для функции по таблице
истинности для использования единичных значений функции каждому значению ставится в соответствие конъюнкция из переменных данного набора как конституэнта «1». Эти конъюнкции соединяют знаками дизъюнкции и получается выражение функции в СДНФ (16).
При минимизации функции по диаграмме Вейча по единицам
выражение функции будет в ДНФ, причем сумма рангов выражения
должна быть минимальной.
В процессе минимизации нужно покрыть клетки с единичными значениями прямоугольниками – соседними областями максимально возможных размеров (количество клеток в области кратно
2m). Каждой соседней области ставится в соответствие конъюнкция,
в которой будут отсутствовать те же переменные, которые изменяют
в этой области свои значе-ния – по ним происходит склеивание. Эти
конъюнкции объединяют зна-ками дизъюнкции и получается выражение для логической функции в ДНФ.
Следует иметь в виду, что одна и та же клетка может входить в несколько соседних областей, но в каждой соседней области должна быть
хотя бы одна клетка, принадлежащая только этой соседней области.
Если клетка с прочерком увеличивает соседнюю область, то ее
нужно использовать, считая прочерк единичным значением функции, если же такая клетка не входит в соседние области, то ее не
учитывают при минимизации.
На рис. 16 в качестве примера приведена диаграмма Вейча для
мажоритарной функции (см. рис. 15) по единицам.
В диаграмме на рис. 16 пустые клетки соответствуют нулевым
значениям функции.
В диаграмме найдены три соседние области, каждая из которых
содержит по две клетки. Одна «1» входит во все соседние области,
но в каждой области есть одна клетка, принадлежащая только этой
области.
Запишем выражение для данной диаграммы:
– первой соседней области соответствует конъюнкция: х1х3 (единичные переменные в конъюнкцию входят без инверсии);
43
x2
x1
1
1
1
3
1
1
x3
2
Рис. 16
– второй соседней области соответствует конъюнкция: х2х3;
– третьей соседней области соответствует конъюнкция: х1х2.
Представим выражение в ДНФ:
f ( x1, x2 , x3 ) = x1x3 ∨ x2 x3 ∨ x1x2
Сумма рангов этого выражения равна: 2 + 2 + 2 = 6.
Если сравнить полученную сумму рангов с суммой рангов для
выражения этой функции в СДНФ (16), которая равна 12, то выигрыш очевиден.
5.4. Пример минимизации мажоритарной
функции по нулям
При записи аналитического выражения для функции по таблице истинности при использовании нулевых значений функции
каждому значению ставится в соответствие дизъюнкция из переменных данного набора как конституэнта «0». Эти дизъюнкции соединяют знаками конъюнкции и получается выражение функции
в СКНФ (17).
При минимизации функции по диаграмме Вейча по нулям выражение функции будет в КНФ, причем сумма рангов выражения
должна быть минимальной.
В процессе минимизации нужно покрыть клетки с нулевыми
значениями прямоугольниками – соседними областями максимально возможных размеров (количество клеток в области кратно
2m). Каждой соседней области ставится в соответствие дизъюнкция,
в которой будут отсутствовать те переменные, которые изменяют
в этой области свои значения (по ним происходит склеивание). Эти
дизъюнкции объединяют знаками конъюнкции и получается выражение для логической функции в КНФ.
44
3
x2
x1
3
1
1
x3
1
1
2
1
Рис. 17
Следует иметь в виду, что одна и та же клетка может входить
в несколько соседних областей, но в каждой области должна быть
хотя бы одна клетка, принадлежащая только этой соседней области.
Если клетка с прочерком увеличивает размеры соседней области, то ее нужно использовать, считая прочерк нулевым значением
функции, если же такая клетка не входит в соседнюю область, то ее
не учитывают при минимизации.
На рис. 17 в качестве примера приведена диаграмма Вейча для
мажоритарной функции (см. рис. 15) по нулям.
В диаграмме на рис. 17 пустые клетки соответствуют нулевым
значениям функции.
В диаграмме найдены три соседние области, каждая из которых
содержит по две клетки. Область три получается при сворачивании
диаграммы Вейча в цилиндр по вертикальной оси. Один «0» входит
во все соседние области, но в каждой области есть одна клетка, принадлежащая только этой области.
Запишем выражение для данной диаграммы:
– первой соседней области соответствует дизъюнкция: х1 v х3
(нулевые переменные в дизъюнкцию входят без инверсии);
– второй соседней области соответствует дизъюнкция: х1 v х2;
– третьей соседней области соответствует дизъюнкция: х2 v х3.
Представим выражение в КНФ
f ( x1, x2 , x3 ) =
(x1 ∨ x3 )(x1 ∨ x2 )(x2 ∨ x3 ).
(43)
Сумма рангов этого выражения равно: 2 + 2 = 2 = 6.
Если сравнить полученную сумму рангов с суммой рангов для
выражения этой функции в СКНФ (17), которая равна 12, то выигрыш очевиден.
45
5.5. Построение логической схемы в базисе Шеффера
для логической функции, представленной в ДНФ (43)
Для реализации схемы в базисе Шеффера нужно вспомнить, что
базис Шеффера, это операции И-НЕ (см. п. 4.5). Воспользуемся законами де Моргана и выполним некоторые преобразования:
f ( x1, x2 , x3 ) = x1x3 ∨ x2 x3 ∨ x1x2 =
= x1x3 ∨ x2 x3 ∨ x1x2 = x1x3 * x2 x3 * x1x2 =
= S(S(x1, x3 ), S(x2 , x3 ), S(x1, x2 )).
(44)
Выражение (44) представлено для построения логической схемы
в базисе Шеффера. Поскольку в (44) отсутствуют переменные с инверсиями будем использовать монофазный код подачи переменных.
На рис. 18 приведена логическая схема в базисе Шеффера для логической функции в ДНФ (42).
5.6. Построение логической схемы в базисе Пирса
для логической функции, представленной в КНФ (43)
Для реализации схемы в базисе Пирса необходимо вспомнить,
что базис Пирса – это операции ИЛИ-НЕ (см. п. 4.6). Воспользуемся
законами де Моргана и выполним некоторые преобразования:
f (x1, x2 , x3 ) = (x1 ∨ x3 )(x1 ∨ x2 )(x2 ∨ x3 ) =
= (x1 ∨ x3 )(x1 ∨ x2 )(x2 ∨ x3 ) =
= (x1 ∨ x3 ) ∨ (x1 ∨ x2 ) ∨ (x2 ∨ x3 ) =
= P ( P ( x1, x3 ), P ( x1, x2 ), P ( x2 , x3 ) ).
x1 x2 x3
&
&
&
Рис. 18
46
&
f(x1,x2,x3)
(45)
x1 x2 x3
&
&
&
f(x1,x2,x3)
&
Рис. 19
Выражение (45) является основой для построения логической
схемы в базисе Пирса. Поскольку в (45) отсутствуют переменные
с инверсиями, будем использовать монофазный код подачи переменных. На рис. 19 приведена логическая схема в базисе Пирса для логической функции в КНФ (43).
47
6. МАЖОРИТАРНАЯ ЛОГИЧЕСКАЯ ФУНКЦИЯ,
ЗАВИСЯЩАЯ ОТ ЧЕТЫРЕХ ПЕРЕМЕННЫХ
6.1.Таблица истинности для мажоритарной функции,
зависящей от четырех переменных.
Представление функции в СДНФ, СКНФ
Поскольку функция зависит от четырех переменных, то количество строк в таблице, т. е. количество наборов, на которых
функция определена, равняется 2n = 24 = 16. Значения функции
определяются значениями большинства переменных набора. Если
в наборе две переменных равны 1 и две другие переменные равны
0, то значение функции неопределенно и проставляется прочерк
(табл. 5).
Представим функцию в СДНФ. Для этого нужно объединить
элементарные конъюнкции, соответствующие наборам переменных, где функция принимает единичные значения, знаками дизъюнкции.
f (x1, x2 , x3 , õ4 ) =
õ1õ2 õ3 õ4 ∨ õ1 õ2 õ3 õ4 ∨ õ1õ2 õ3 õ4 ∨ õ1õ2 õ3 õ4 ∨ õ1õ2 õ3 õ4 . (46)
Сумма рангов функции равна R = 20.
Представим функцию в СКНФ. Для этого нужно объединить
элементарные дизъюнкции, соответствующие набором переменных, где функция принимает нулевые значения, знаками конъюнкции.
Таблица 5
х1 х2 х3 х4
f
0000
0
0001
0010
0
0011
–
0100
48
0
0
0101
–
0110
–
СДНФ
СКНФ
õ1 ∨ õ2 ∨ õ3 ∨ õ4
õ1 ∨ õ2 ∨ õ3 ∨ õ4
õ1 ∨ õ2 ∨ õ3 ∨ õ4
õ1 ∨ õ2 ∨ õ3 ∨ õ4
0111
1
1000
0
1001
–
1010
–
1011
1
1100
–
1101
1
õ1 õ2 õ3 õ4
1110
1
õ1 õ2 õ3 õ4
1111
1
õ1 õ2 õ3 õ4
õ1 õ2 õ3 õ4
õ1 ∨ õ2 ∨ õ3 ∨ õ4
õ1 õ2 õ3 õ4
f (x1, x2 , x3 , õ=
4 ) (õ1 ∨ õ2 ∨ õ3 ∨ õ4 )(õ1 ∨ õ2 ∨ õ3 ∨ õ4 )
(õ1 ∨ õ2 ∨ õ3 ∨ õ4 )(õ1 ∨ õ2 ∨ õ3 ∨ õ4 )(õ1 ∨ õ2 ∨ õ3 ∨ õ4 ). (47)
Сумма рангов функции равна R = 20.
6.2. Минимизация мажоритарной функции
при помощи диаграммы Вейча
Диаграмма Вейча в данном случае будет квадратом, разделенным на 16 клеток, каждая из которых соответствует своему набору
переменных (рис. 20).
В диаграмме на рис. 20 в клетках проставлены значения наборов переменных и соответствующие им значения функций. Пустые
клетки соответствуют нулевым значениям функции.
Для диаграммы на рис. 20 найдены две соседние области для
единичных значений функции: области 1 и 2. Области содержат по
четыре клетки, клетки с прочерками в данном случае увеличивают
размеры областей, поэтому используются.
Запишем выражение функции в ДНФ:
f ( x1, x2 , x3 ,=
x4 ) x2 x4 ∨ x1x3 . (48)
Сумма рангов выражения (48) R = 4.
Для нулевых значений функции найдены две соседние области
по четыре клетки: 3 и 4. Эти соседние области также имеют в своем
составе клетки с прочерками.
49
x2
x1
0000
0100
1100
0001
0101
1101
0011
0111
–
1
1
1
0010
0101
1110
1010
1000
3
–
x4
–
x3
1
1111
1001
–
1011
–
–
1
2
4
Рис. 20
Запишем выражение в КНФ:
f ( x1, x2 , x3 , x4 ) =
( x3 ∨ x4 )( x1 ∨ x2 ).
(49)
Сумма рангов выражения (49) R = 4.
Таким образом, можно сделать вывод, что использование диаграммы Вейча для минимизации логических функций является
достаточно простыми эффективным способом уменьшения суммы рангов выражений, т. е. упрощения функций для реализации
этих функций при помощи логических схем. Необходимо помнить,
что выражение в ДНФ или КНФ должно быть минимальным ДНФ
или КНФ, т. е. не подлежащие дальнейшему упрощению и должны
иметь минимальные суммы рангов.
50
7. КОНТРОЛЬНЫЕ ВОПРОСЫ
7.1. Найти сумму рангов выражения функции, которая задана диаграммой Вейча на рис. 21. Проминимизировать по единицам и нулям.
Для единичных значений найдены три соседних области (1, 2 и
3). Запишем выражение в ДНФ:
f ( x1, x2 , x3 , x4 ) = x1x2 ∨ x2 x4 ∨ x1x3 x4 .
(50)
Сумма рангов R = 7.
Для нулевых значений найдены четыре соседние области, содержащие по четыре клетки: 4, 5, 6, 7. Запишем выражение в КНФ:
f ( x1, x2 , x3 , õ4 ) =
( x1 ∨ x2 )( x1 ∨ x4 )( x2 ∨ x3 )( x2 ∨ x4 ). (51)
Сумма рангов полученного выражения (51) равна R = 8.
7.2. Сколько клеток в диаграмме Вейча нужно отметить единицами, если функция в ДНФ имеет вид:
f ( x1, x2 , x3 , õ4=
) x2 x3 x4 ∨ x1x3 ∨ x2 x4 .
(52)
Необходимо представить диаграмму Вейча для четырех переменных. Далее для каждой конъюнкции из ДНФ нужно поставить
в соответствие соседнюю область (рис. 22).
На рис. 21 показаны соседние области для конъюнкций в (52): 1,
2, 3.
Количество клеток, отмеченных 1, равно 9.
x2
5
7
x1
6
7
1
x4
4
–
–
1
1
6
1
3
1
x3
7
5
7
2
1
Рис. 21
51
x2
3
1
3
1
1
x4
1
x3
x1
1
1
1
1
1
1
2
3
3
Рис. 21
7.3. Какое выражение соответствует приведенной на рис. 22 схеме?
Для ответа на данный вопрос нужно после каждого логического
элемента, учитывая переменные на входах, записать результат операции на выходе и последовательно записать полученное выражение. А далее, используя законы де Моргана, привести выражение
x1 x1 x2 x2 x3 x3 x4 x4
1
x1∨x3
1
(x1∨x3)∨(x2∨x3)
1
1
x2∨x3
&
f
x 1x 3
&
(x1∨x3)∨(x2∨x3)
&
x2x3
Рис. 22
52
к ДНФ, т. е. к элементарным конъюнкциям объединенным знаками
дизъюнкции (53):
f ( x1, x2 , x3 , õ4 ) =  x1 ∨ x3 ∨ x2 ∨ x3  ∨  x1 x3 x1 x3  = (53)


 
) (
(
) (
)(
)

 

=  x1x3 ∨ x2 x3  ∨  x1 x3  ∨  x2 x3   =

 
 

= x1x3 ∨ x2 x3 ∨ x1 x3 ∨ x2 x3 .
(
) (
)
(54)
Выражение (54) представлено в ДНФ.
7.4. Сколько нужно элементов типа И-НЕ – элементов Шеффера,
с числом входов не более двух для построения логической схемы по
выражению в ДНФ:
f ( x1, x2 , x3 , õ4 )= x1 x2 x3 ∨ x2 x4 ∨ x2 x3 x4 . (55)
Вначале это выражение нужно привести к базису Шеффера.
Воспользуемся законами де Моргана^
f ( x1, x2 , x3 , õ4 ) = = x1 x2 x3 ∨ x2 x4 ∨ x2 x3 x4= x1 x2 x3 * x2 x4 * x2 x3 x4= (56)
= S(S(x1, x2 , x3 ), S(x2 , x4 ), S(x2 , x3 , x4 )).
Выражение (56) представлено в базисе Шеффера, но первый и
третий элементы Шеффера, а также выходной элемент Шеффера
в схеме имеют по три входа. Воспользуемся следующим преобразованием:
x1 x2 x3 = x1 x2 x3 ,
(57)
S(x1, x2 , x3 ) = S(SS(x1, x2 ), S(x3 )). (58)
Т. е. Проведем следующие преобразования:
x1=
x2 x3 * x2 x4 * x2 x3 x4 x=
1 x2 x3 * x2 x4 * x2 x3 x4
( (
(
) )
 S S S S S x ,x ,x S ( x ,x )
 2 3 4 7 8 1 2 3 5 2 4
= S1 
 S6 S9 S10 x2 , x3 , x4

(
(
) )
),.



(60)
53
x1 x1 x2 x2 x3 x3 x4 x4
&
&
&
&
&
&
f(x1,x2,x3,x4)
&
&
&
&
Рис. 23
В выражении (59) пронумерованы все инверсии, эти номера совпадают с номерами логических элементов Шеффера, имеющих не более
двух входов в выражении (60), для которого построим логическую схему, используя парафазный код подачи переменных (рис. 23).
54
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Мишура О. В. Цифровые автоматы. Основы алгебры логики.
Минимизация логических функций при помощи диаграмм Вейча: метод. указ. для студентов 2-го курса заочной формы обучения.
СПб.: ГУАП, 2012.
2. Пятибратов А. П., Кирпиченко А. А., Гудьно Л. П. Вычислительные системы, сети и телекоммуникации. М.: Финансы и статистика, 2002.
3. Фрикс К. Вводный курс цифровой электроники. М.: Техносфера, 2004.
СОДЕРЖАНИЕ
Предисловие............................................................... 1. Элементы теории множеств........................................ 2. Алгебра множеств.................................................... 3. Основные понятия алгебры логики.............................. 4. Аналитическое представление функций
алгебры логики ........................................................... 5. Реализация логических функций
при помощи логических элементов................................. 4. Использование законов де Моргана
для построения логических схем, реализующих
функции алгебры логики .................................................. 5. Минимизация логических функций................................ 6. Мажоритарная логическая функция,
зависящая от четырех переменных................................. 7. Контрольные вопросы............................................... Библиографический список............................................... 3
4
16
19
22
25
30
40
48
51
55
55
Учебное издание
Мишура Ольга Владимировна,
Попов Валерий Павлович
ДИСКРЕТНАЯ МАТЕМАТИКА.
ТЕОРИЯ МНОЖЕСТВ. МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ
ФУНКЦИЙ ПРИ ПОМОЩИ ДИАГРАММ ВЕЙЧА
Учебно-методическое пособие
В авторской редакции
Компьютерная верстка М. И. Дударевой
Подписано к печати 14.06.2016. Формат 60 × 84 1/16.
Бумага офсетная. Усл. печ. л. 3,25. Уч.-изд. л. 3,50.
Тираж 50 экз. Заказ № 262.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
Документ
Категория
Без категории
Просмотров
0
Размер файла
2 844 Кб
Теги
mishurapopov1
1/--страниц
Пожаловаться на содержимое документа