/>Федеральноеагенство по образованию РФ Саратовский государственный университет
имени Н.Г. Чернышевского
Кафедра геометрии
курсовая работа
Минимальныеформы булевых многочленов
г. Саратов2009 г.
содержание
Введение
Основные понятия булевой алгебры
1.1 Основные этапы развития булевой алгебры
1.2 Основные определения булевой алгебры
1.3 Минимальные формы булевых многочленов
II.Решение минимальных форм булевых многочленов с
помощью метода Куайна – Мак-Класки
Заключение
Список используемых источников.
ВВЕДЕНИЕ
Булевы алгебры – эторешетки особого типа, которые применяются при исследовании логики (причем каклогики человеческого мышления, так и цифровой компьютерной логики), а такжепереключательных схем. Это последнее приложение было инициировано К. Шенноном,показавшим, что фундаментальные свойства электрических сетей, состоящих избистабильных элементов, могут быть выражены с помощью булевых алгебр. Наряду сшенноном пионерами в применении теории булевых алгебр для решения задачрелейной техники в 1936-1938 гг. были русский математик В.И. Шестаков и японцыА.Накасима и М. Ханзава. Отметим также, что ещё в 1910 г. известный физик П.Эренфест в рецензии на русский перевод книги Л. Кутюра «Алгебра логики» указална потенциальную применимость булевой логики к проектированию автоматическихтелефонных станций, сформулировав вопросы о реализуемости булевых функций иминимизации схем.
Целью данной курсовойработы является изучение булевой алгебры и применение минимальных форм булевыхмногочленов к решению задач.
Курсовая работа состоитиз введения, трех глав, заключения и списка используемых источников.
Во введении описанаактуальность темы, сформулирована цель, дана структура курсовой работы.
В первой главе даныосновные определения и основные понятия булевой алгебры.
Во второй главе даетсяопределение минимальных форм булевых многочленов и намечен курс дальнейшегоисследования.
Третья глава посвященаприменению минимальных форм булевых многочленов к решению задач.
В заключениисформулированы основные выводы к работе.
I. ОСНОВНЫЕ ПОНЯТИЯ БУЛЕВОЙ АЛГЕБРЫ
1.1Основные этапыразвития булевой алгебры.
В 1847 году Дж. Бульнаписал маленькую, но эпохальную книгу «математический анализ логики», вкоторой логика трактовалась как чисто формальная система; интерпретация вобычном языке пришла позже. Буль писал, что математика характеризуется своейформой, но не содержанием. В своей последующей книге «Исследование законовмышления» (1854) он ввел понятие булевой алгебры.
Булевское исчислениелогики сосредоточено на формальной трактовке логики посредством математических(особенно алгебраических) методов и на описании логических тождеств. СледуяБулю, школа английских математиков, а также Шрёдер, Уайтхед разработали аксиоматикуопераций конъюнкции, дизъюнкции, отрицания; с другой стороны, Пирс и Шрёдерсоздали аксиоматику порядка, используя отношение включения в качествефундаментального понятия. В 1904 году Хантингтон исследовал две системы аксиоми начал трактовать булевы алгебры как самостоятельные математические структуры,не обязательно связанные с логикой.
Буль использовалдистрибутивность пересечения относительно объединения, которую еще до негоотметил Ламберт. Буль работал с множествами. Обозначая пересечение х и учерез ху, а объединение – через х + у, если х и удизъюнкты. Подобно Лейбницу, он интерпретировал отношение включения х Íу как ху = х, что легко давало возможностьполучить классические правила силлогизма. Затем Джевонс распространил операциюобъединения на произвольные х и у; Де Морган и, позже, Пирсдоказали соотношение двойственности, называемые законами де Моргана.
Большинство логиковдевятнадцатого века не высказывало большого интереса к применению в математикесвоих находок. Одной из причин этого было отсутствие кванторов, введенных позжеФреге и Пирсом. Пеана, среди прочих, ввел символы È, Ç, — для объединения, пересечения и вычитания множеств.После книги ван дер Вардена по современной алгебре понятие универсальнойалгебры было уже не за горами. Биркгоф развил концепцию «алгебры», отправляясьот подходов ван дер Вардена, и взял название «универсальная алгебра» из книгиУайтхеда. в 1934 году, будучи в Геттингене, Маклейн также высказывал некоторыемысли об универсальной алгебре, но не опубликовал их. Одна из фундаментальнейшийстатей по теории решеток была напечатана Оре в 1935 году. Последующие годыознаменовались целым рядом исследований в области, как теории, так и приложенийрешеток, например, в теории групп, проектированной геометрии, квантовоймеханике, функциональном анализе, теории меры и интегрирования.
В 1933 – 1937 гг. М.Стоун получил важные результаты о булевых алгебрах, которые он интерпретировалкак специальные кольца, а именно как булевы кольца, где была применима теорияидеалов. Другие фундаментальные вопросы, рассматривавшиеся Стоуном, — этовопросы о представлении булевых алгебр и приложения булевых алгебр в топологии.С тех пор теория решеток превратилась во вполне жизнеспособную, сильную исамостоятельную дисциплину.
1.2 Основные определенияи понятия булевой алгебры
Определение: Булевой алгеброй (обозначим В) называетсянепустое множество элементов с двумя бинарными операциями «+», «*»и одной унарной операцией «`», а так же специальными элементами и 1, если выполняются следующие свойства:
1. a+ b = b + a ,"a ,b B
2. a* b = b * a ,"a, b B
3. a+ (b*c) = (a + b)*(a + c)
4. a*(b + c) = (a*b) + (a*c)
5. a+ 0 = a, a* 1 = a. (Тождественность)
6. a+ a` = 1, a* a`= 0. (Дополнительность)
Эта система аксиомявляется полной и независимой.
Пример 1: Пусть множество В– этомножество В= {1,0} на котором заданы две бинарные операции:
+
1
*
1
1
1
1
1
1
1
И унарнаяоперация: 0`= 1, 1`=0.
Пример 2: Множество делителей числа 70:,7,10,14,35,70>
1. a+ b = НОД (a,b)
2. a*b =НОК (a,b)
3. a`=70/a
Определение: Пусть С — непустое подмножествомножества В. Говорят, что С -подалгебра алгебры В, еслиона сама является алгеброй с теми же операциями.
Подмножество С — есть подалгебра алгебры В ÛС замкнуто относительно трех операций.
Пример 3: Если С=замкнуто относительно операций «+», «*», «`», тогда Сявляется подалгеброй алгебры В.
Определение: Две булевы алгебры В и В`изоморфны: В ~В`, если существует взаимно-однозначная функция f: B®B`, такая, что:
1. f(a+b) = f (a) + f (b)
2. f(a*b) = f (a)*f (b)
3. f(a`) = (f (a))`
Для булевой алгебрысправедливы принципы дуальности.
Основные теоремыабстрактной булевой алгебры.
1. Идемпотентныйзакон: a + a = a, a * a = a.
2. Граничный закон: a+ 1 = 1, a+ 0 = a.
3. Абсорбционныйзакон: a + (a * b) = a, a * (a + b) = a.
4. Ассоциативныйзакон: a + (b + c) = (a + b) + c, a * (b * c) = (a * b) * c.
5. Единственностьдополнения: если $x: a+ x= 1, a* x= 0, то x= a`.
6. Инволютивныйзакон: ((a`))` =a Þ0`=1, 1`=0.
7. Законде Моргана: (a + b)`=a` * b`, (a * b)` = a` + b`.
Булева алгебра какрешетка.
Поскольку для булевойалгебры справедливы ассоциативный, коммутативный и абсорбционный законы, тосогласно определению булева алгебра есть решетка. В этой решетке
"а, а + 1 = 1 Þ а £1, а * 0 = 0 Þ0 £а.
Таким образом В естьограниченная решетка, кроме того аксиомы (2) и (4) указывают на то, чторешетка дистрибутивна и дополнена. И наоборот, любая ограниченная,дистрибутивная и дополненная решетка есть булева алгебра.
Определение: Булева алгебра – это ограниченная, дистрибутивная идополненная решетка.
Мы можем ввести набулевой алгебре отношение частичного порядка. Полагаем, что a£b Û
aÚb= b, aÙb= a.
Теорема. В булевой алгебре следующиевыражения эквивалентны:
1) a+ b= b
2) a* b= a
3) a` + b= 1
4) a* b` = 0.
Доказательство.
1. Докажемэквивалентность (1) и (3)
а) Пусть (1) верно, тогда
a`+b=a`+(a+b)=(a`+a)+b=1+b=1;
b) Пусть (3) верно, тогда
a + b = (a`+ b) * (a + b) = b * (a + a`) = b * 1 = b;
2. Докажемэквивалентность (3) и (4)
a) Пусть (3) верно, тогда
=1`=(a`+b)`=(a`)`*b`=a*b`;
b) Пусть (1) верно, тогда
1=0`=(a+b`)`=a`+(b`)`=a`+b;
3. Докажемэквивалентность (2) и (4)
a) Пусть (2) верно, тогда
a*b`=(a*b)*b`=a*(b*b`)=a*=;
b) Пусть (4) верно, тогда
a * b = a *b + 0 = a * b + a * b` = a * (b + b`) = a * 1 = a;
Тогда выражения (1), (2), (3), (4)эквивалентны.Пример 1. Рассмотрималгебру множеств – модель булевой алгебры.
А £В если А ÌВ.
1. АÚВ=В
2. АÙВ=А
3. АÚВ=U
4. АÙВ`=Æ
Любая конечная булеваалгебра может содержать лишь 2 в степени nэлементов, где n– натуральное число.
Пример 2. 1)Множество делителей 70-ти D=. Множество A= -множество атомов решетки D.
10=2Ú5
14=2Ú7
35 =5Ú7
70=(2Ú5) Ú7
70
/>
10 />/>/>/>/>/> 14 35
/>/>/>2 5 7
1
2) Множество А={2,5,7}
Отношение вложенности.
{2,5,7}
/>
{2,5} {2,7} {5,7}
/>
/> {2} {5} {7}/> /> /> /> /> /> />
Æ
Эта решетка изоморфнапредыдущей.
Алгебра множеств иалгебра высказываний являются моделями абстрактной булевой алгебры. Всеабстрактные булевы алгебры (которые состоят из одинакового числа элементов)изоморфны.
1.3Минимальныеформы булевых многочленов
Определение. Понятие булева многочленаопределяется рекурсивно. Пусть Хn= {x1,…, xn} – множество из n символов (называемых неизвестными или переменными),которое не содержит символов и 1. Булевы многочлены над Хn суть объекты, которые могут бытьполучены последовательным применением следующих правил:
(I) х1,х2, …, хn, 0,1 – булевы многочлены;
(II) если p и q – булевы многочлены, то таковыми являются и
(p) Ù(q), (p) Ú(q), (p)¢.
Обозначим множество всехбулевых многочленов над Хnчерез Рn.
Пример. Вот несколько примеров булевыхмногочленов над {х1, х2}: 0,1, х1, х2,х1 Ùх2, х1 Úх2, х1¢,х1¢Ùх2.
Так как любой булевмногочлен над x1,…, xnмодно рассматривать как булевмногочлен над x1,…, xn, xn+1, мы имеем
Р1ÌР2Ì… ÌРnÌРn+1 Ì…
Булев многочлен можноупростить с помощью аксиом булевой алгебры. В процессе упрощения часто труднорешить, какие аксиомы и в каком порядке должны быть использованы. Но существуютнекоторые систематические методы упрощения булевых многочленов. Недостаткомбольшинства этих методов является возможность их практического внедрения, когдачисло переменных слишком велико. Соответствующая проблематика в теории булевыхалгебр носит общее название проблема оптимизации или минимизации булевыхмногочленов; она важна для таких приложений, как упрощение переключательныхсхем.
Определение. Назовем литералом любую переменную хi и ее дополнение хi¢, а также и 1. Подпроизведением понимается произведение нескольких литералов, т.е. булевмногочлен, в котором нет знака +. Дизъюнктивным выражением или простовыражением назовем буле многочлен, являющийся суммой произведений. Слагаемые втаком выражении назовем дизъюнктами.
Обсуждая упрощениебулевых многочленов, мы ограничимся важным случаем сведения дизъюнктивныхвыражений к «минимальным выражениям» относительно специального условияминимальности. Обозначим через df общее число литералов в выражении f, а через ef – число дизъюнктов. Мы говорим, чтовыражение f проще выражения j, если df£dg, ef£eg и хотя бы одно из этих неравенствстрогое. Выражение fназывается минимальным, если не существует выражения, которое было быэквивалентно f и проще f. Таким образом, мы будем искать«кратчайшее» выражение с наименьшим возможным числом литералов, которое было быэквивалентно f. Такоеминимальное выражение не всегда определено однозначно. Я опишу один изнескольких существующих методов упрощения. Он основан на работе Куайна и былулучшен Мак-Класки, поэтому называется методом Куайна — Мак-Класки.
Определение. многочлен p влечет многочлен q, если для любых b1,….,bnÎВ
рв (b1, …, bn) = 1 влечет qв(b1, …, bn) = 1;
в этом случае рназывается импликантом для q.Простым импликантом многочлена р называется произведение />, которое влечетр, но если в />вычеркнуть хотябы один сомножитель, то результат уже не влечет р. Произведение,сомножители-литералы которого образуют подмножество сомножителей-литераловдругого произведения, называется подпроизведением последнего.
Пример. Произведение х1х3является подпроизведением как х1х2х3,так и х1х2¢х3, и влечет выражение
/>/>р = х1х2х3+ х1х2¢х3 + х1¢х2¢х3¢,
/>/>поскольку (х1х3)(1,i2, 1) = 1 и р(1, i2, 1) = 1, а для других значений аргументов х1х3дает 0. Ни х1, ни х3 невлекутр; например, х1(1, 1, 0) = 1, но р(1, 1, 0)= 0, поэтому х1х3– простойимпликант для р.
Теорема. Любой многочлен р ÎPnэквивалентен сумме всех своих простыхимпликантов.
Выражение, являющеесясуммой простых импликантов для р, называется неприводимым, если оноэквивалентно р, но пересекает быть таковым, если удалить хотя бы однослагаемое. Минимальное выражение должно быть неприводимым. Поэтому, чтобыопределить минимальное выражение, мы находим все неприводимые выражения, асреди них ищем выражение с наименьшим числом литералов. Изложим теперьпринадлежащий Куайну метод определения простых импликантов.
Простые импликантыполучаются из дизъюнктивной нормальной формы d булева многочлена р применением (слеванаправо) правила
yz+ yz¢~y,
когда это возможно. Болееобщо, мы используем правило
/> (*)
где />и /> — произведения.следующий пример поможет понять смысл описываемой процедуры.
Пример. Пусть р – булев многочлен,имеющий следующую дизъюнктивную нормальную форму:
d= wxyz’ + wxy’z’ + wx’yz+ wx’yz’ + w’x’yz+ w’x’yz’ + w’x’y’z
Мы используем правило />изаконы идемпотентности для тех (из общего числа (/>) = 21)пар дизъюнктов в d, для которыхэто возможно, тем самым «укорачивая» произведения. например, превый и второйдизъюнкты при использовании (*) дают wxz’. Если в процессе упрощения слагаемые используютсяхотя бы один раз, то оно помечается. Так как знак + стоит вместо Ú, выражение может быть использованолюбое число раз, но помечается не более одного раза. Таким образом, всепомеченные произведения содержат более короткие произведения и поэтому не могутбыть простыми импликантами. В целом в первом раунде этого процесса мы переходим
от wxyz’ и wxy’z’ к wxz’
от wx’yz и wx’yz’ к wx’y
от wxyz’ и wx’yz’ к wyz’
от w’x’yz и w’x’yz’ к w’x’y
от w’x’yz и w’x’y’z к w’x’z
от wx’yz и w’x’yz к x’yz
от wx’yz’ и w’x’yz’ к x’yz’
Здесь использованы, ипотому должны быть помечены, все семь слагаемых.
В общем, эта процедураповторяется снова и снова с использованием только помеченных выражений (которыестановятся короче). Прочие произведения суть простые импликанты и остаютсянеизменными.
В нашем примере второйраунд упрощения осуществляет переход
от wx’y и w’x’y к x’y
от x’yz и x’yz’ к x’y
Четыре выражения — wx’y, w’x’y, x’yz, x’yz’ – помечены. Остальные произведения, а именно wxz’, wyz’, w’x’z не могут быть упрощен. следовательно, рэквивалентно такой сумме простых импликантов:
р ~wxz’ + wyz’ + w’x’z+ x’y.
Как уже было сказано,Мак-Класки улучшил это метод. Чтобы описать улучшенный алгоритм, используеммногочлен
d= wxyz’ + wxy’z’ + wx’yz+ wx’yz’ + w’x’yz+ w’x’yz’ + w’x’y’z
Шаг 1. Считая переменные упорядоченными по алфавиту (или пономерам), поставим в соответствие каждому произведению последовательностьсимволов из {0, 1, -}: вместо xi’ и xiзапишем и 1 соответственно, а вместоопущенных переменных запишем черточку. Например, вместо w’x’y’z запишем 0001, а вместо w’x’z – 00-1.
Шаг 2. Произведения, рассматриваемые кактроичные n-ки, разбиваются на классыэквивалентности в соответствии с числом единиц. Упорядочим классы повозрастанию этого числа. В нашем примере:
w’x’y’z0 0 0 1
w’x’yz’0 0 1 0
w’x’yz0 0 1 1
wx’yz’1 0 1 0
wx’yz1 0 1 1
wxyz’1 1 1 0
wxy’z’1 1 0 0
Шаг 3.Используя правило (*), нужно складывать толькопроизведения из соседних классов, т.е. когда числа единиц в соответствующихпоследовательностях отличаются лишь на 1. При этом мы должны сравниватьвыражения из соседних классов, имеющих черточки в одних и тех же позициях. Еслидва таких выражения отличаются точно в одной позиции, то они имеют вид р = i1i2…ir…in и q= i1i2…ir’…in, где все ik лежат в {0, 1, -}, а ir лежит в {0, 1}. Тогда (*)сводит p, q к i1i2…ir-1 — ir+1 …in, причем p и qдолжны быть помечены. В рассматриваемом примере это дает такие четверки (меткиотносятся к следующему раунду, тогда как в предыдущем списке все произведенияследовало пометить):
0 0 — 1
0 0 1 -ü
— 0 1 0ü
— 0 1 1ü
1 0 1 -ü
1 — 1 0
1 1 — 0
Помеченные выражения неявляются простыми импликантами и во втором раунде этого шага дают единственноевыражение
— 0 1 -
Итак, мы нашли всепростые импликанты, а именно
0 0 1 — w’x’z
— 0 1 0 wyz’
— 0 1 1 wxz’
1 0 1 — x’y
Так как сумма всехпростых импликантов необязательно является минимальным выражением, алгоритмтребует выполнения ещё одного шага.
Шаг 4. В силу теоремы сумма всех простыхимпликантов для р эквивалентна р. поэтому для каждого слагаемого дизъюнктивнойнормальной формы d многочленар должен существовать простой импликант, являющийся произведением этогослагаемого. для выявления возникшего соответствия удобно использовать таблицупростых импликантов. столбцы этой таблицы индексируются дизъюнктами из d, а строки – простыми импликантами,вычисленными в шаге 3. на пересечении i-й строки и j-го столбца ставится крестик û, если простой импликант из i-й строки является подпроизведением произведения из j-го столбца. Говорят, что однопроизведение покрывает, если первое является подпроизведением второго. Длятого, чтобы найти сумму простых импликантов, которая будет эквивалентна d, мы из множества всех простыхимпликантов выбираем подмножество таким образом, чтобы каждое слагаемое в d покрывалось по крайней мере однимимпликантом из подмножества. Тогда минимальной формой будет сумма простыхимпликантов с наименьшим числом членов и наименьшим числом букв. Простойимпликант называется главным членом, если он покрывает произведение, непокрываемое никаким другим простым импликантом; сумма всех главных членовназывается ядром. сначала мы находим ядро, затем обозначаем через q1,…,qk произведения, не покрываемыепростыми импликантами из ядра; простые импликанты, не входящие в ядро,обозначим через р1,…, рm. Далее формируем таблицу, столбцыкоторой индексируются элементами qi, а строки – элементами рi. Крестик û на месте (i, j) указывает, что рi покрывает qj.
Теперь образуемпроизведение сумм. Каждый сомножитель соответствует одному из qj и является суммой тех рi, который покрывают этот qj. Используя законы булевой алгебры,мы преобразуем это выражение в простейшую возможную сумму произведений. Каждоеиз этих произведений представляет подмножество элементов рi, которые покрывают все qj. Далее рассматриваем произведения снаименьшим числом сомножителей. Из этих кратчайших произведений выбираем те,что содержат наименьшее общее число литералов. Теперь каждое из полученныхпроизведений переписываем в виде суммы составляющих его простых импликантов,складываем с ядром, получая минимальную сумму произведений, эквивалентнуюр.
II.РЕШЕНИЕ МИНИМАЛЬНЫХ ФОРМ БУЛЕВЫХМНОГОЧЛЕНОВ С ПОМОЩЬЮ МЕТОДА КУАЙНА – МАК-КЛАСКИ
Задача.Определимформу булева многочлена р, заданного в дизъюнктивной нормальной форме
d= v’w’x’y’z’+ v’w’x’yz’+ v’w’xy’z’+ v’w’xyz’+ v’wx’y’z+ v’wx’yz’+ v’wxy’z+ v’wxyz’+ v’wxyz+ vw’x’y’z’+ vw’x’y’z+ vw’xy’z+ vwx’yz’+ vwxy’z’+ vwxyz’+ vwxyz
Решение:
Шаги1 и 2
0 единиц
0 0 0 0 0
ü
(1)
1 единица
0 0 0 1 0
0 0 1 0 0
1 0 0 0 0
ü
ü
ü
(2)
(3)
(4)
2 единицы
0 0 1 1 0
0 1 0 0 1
0 1 0 1 0
1 0 0 0 1
ü
ü
ü
ü
(5)
(6)
(7)
(8)
3 единицы
0 1 1 0 1
0 1 1 1 0
1 0 1 0 1
1 1 0 1 0
1 1 1 0 0
ü
ü
ü
ü
ü
(9)
(10)
(11)
(12)
(13)
4 единицы
0 1 1 1 1
1 1 1 1 0
ü
ü
(14)
(15)
5 единиц
1 1 1 1 1
ü
(16)
Шаг 3. Комбинация строк (i) и (j) дает сокращение, указанное в строке (i)(j):
(1)(2)
(1)(3)
(1)(4)
0 0 0 — 0
0 0 — 0 0
— 0 0 0 0
ü
ü
J
(2)(5)
(2)(7)
(3)(5)
(4)(8)
0 0 -1 0
0 -0 1 0
0 0 1 — 0
1 0 0 0 -
ü
ü
ü
I
(5)(10)
(6)(9)
(7)(10)
(7)(12)
(8)(11)
0 -1 1 0
0 1 -0 1
0 1 — 1 0
- 1 0 1 0
1 0 -0 1
ü
H
ü
ü
G
(9)(14)
(10)(14)
(10)(15)
(12)(15)
(13)(15)
0 1 1 — 1
0 1 1 1 -
— 1 1 1 0
1 1 -1 0
1 1 1 — 0
F
ü
ü
ü
Е
(14)(16)
(15)(16)
— 1 1 1 1
1 1 1 1 -
ü
ü
Повторениеэтого шага с новыми строками дает нам
(1)(2)(3)(5)
0 0 — -
D
(2)(5)(7)(10)
0 — — 1 0
C
(7)(10)(12)(15)
— 1 — 1 0
B
(10)(15)(14)(16)
— 1 1 1 -
A
Пометки «птичкой»ü и буквами сделаны после процессаупрощения. найденные простые импликанты обозначены буквами А, В, …J.
Шаг 4. Формируем таблицу простыхимпликантов, где индексы столбцов – слагаемые из d – представлены в виде двоичных столбцов.
(1)
(2)
1
(3)
1
(4)
1
(5)
1
1
(6)
1
1
(7)
1
1
(8)
1
1
(9)
1
1
1
(10)
1
1
1
(11)
1
1
1
(12)
1
1
1
(13)
1
1
1
(14)
1
1
1
1
(15)
1
1
1
1
(16)
1
1
1
1
1
-111- А
û
û
û
û
-1-10 В
û
û
û
û
0--10 С
û
û
û
û
00--0 D
û
û
û
û
111-0 E
û
û
011-1 F
û
û
10-01 G
û
û
01-01 H
û
û
1000- I
û
û
-0000 J
û
û
В наших краткихобозначениях ядро, т.е. сумма главных членов, есть D+ H+ G+ B+ E+ A. Единственным произведение, не покрываемым ядро,является (4); это и есть q1.Простыми импликантами pi, не входящими в ядро, являются С, F, I, J. Новая таблица имеет вид
(4) 1 0 0 0 0
0 — — 1 0 С
0 1 1 — 1 F
1 0 0 0 — I
û
— 0 0 0 0 J
û
Это обозначает, что мыполучаем две минимальные форы:
(i) D+ H+ G+ B+ E+ A+ I, если использоватьI, и
(ii) D+ H+ G+ B+ E+ A+ J, если выбрать J.
В обычных обозначенияхминимальная форма (i) такова:
v’w’z’ + v’wy’z+ vw’y’z+ wyz’ + vwxz’ + wxy+ vw’x’y’.
ЗАКЛЮЧЕНИЕ
По результатампроведённого курсового исследования по теме «Минимальные формы булевыхмногочленов» можно сделать следующие выводы.
При всейпростоте своей аксиоматики теория булевых алгебр весьма содержательна. Мынаходим в ней немало трудных и глубоких проблем, многие из которых ещё нерешены. Эти проблемы весьма разнообразны, они соприкасаются с логикой и теориеймножеств, с теорией вероятностей и анализом. Такое обилие точек соприкосновениясо смежными математическими дисциплинами роднит теорию булевых алгебр сфункциональным анализом, к которому она близка и по своему общемуматематическому стилю.
Существуютразличные методы нахождения минимальных форм булевых многочленов. В своейкурсовой работе я исследовала один из методов — метод Куайна — Мак-Класки. Онпредназначен для нахождения множества простых импликант для функций, заданныхсовокупностью наборов, на которых функция равна единице, или дизъюнктивнойсовершенной нормальной формой. Умение минимизировать логические функции имеетогромное значение при проектировании устройств цифровой электроники.
СПИСОК ИСПОЛЬЗУЕМЫХИСТОЧНИКОВ
1. ВладимировД.А., Булевы алгебры – М., Издательство «Наука» 1969.
2. Дискретнаяматематика и математические вопросы кибернетики – под общей редакцией С.В.Яблонского и О.Б. Лупанова – М., «Наука», 1974.
3. ЛидлР., Пильц Г., «Прикладная абстрактная алгебра» — Екатеринбург, «Издательствоуральского университета» 1996.
4. www.exponenta.ru/educat/systemat/1006/2_tutorials/bin_log.asp
5. www.intuit.ru/department/hardware/archsys/keywords.2.html