Решение минимальных форм булевых многочленов с помощью метода Куайна – Мак-Класки

содержание

Введение

I.Основные понятия булевой алгебры

1.1 Основные этапы развития булевой алгебры

1.2 Основные определения  булевой алгебры

1.3 Минимальные формы булевых многочленов

II.Решение минимальных форм булевых многочленов с

помощью метода Куайна – Мак-Класки

Заключение

Список литературы.

 

 

ВВЕДЕНИЕ

Булевы алгебры –  это решетки особого типа, которые  применяются при исследовании логики (причем как логики человеческого  мышления, так и цифровой компьютерной логики), а также переключательных схем. Это последнее приложение было инициировано К. Шенноном [10], показавшим, что фундаментальные свойства электрических сетей, состоящих из бистабильных элементов, могут быть выражены с помощью булевых алгебр. Наряду с шенноном пионерами в применении теории булевых алгебр для решения задач релейной техники в 1936-1938 гг. были русский математик В.И. Шестаков [11] и японцы А.Накасима и М. Ханзава. Отметим также, что ещё в 1910 г. известный физик П. Эренфест в рецензии на русский перевод книги Л. Кутюра «Алгебра логики» указал на потенциальную применимость булевой логики к проектированию автоматических телефонных станций, сформулировав вопросы о реализуемости булевых функций и минимизации схем.

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

Целью данной курсовой работы является изучение булевой алгебры и применение минимальных форм булевых многочленов к решению задач.

Объект исследования: булевы многочлены и систематические  методы их упрощения.

Предмет исследования: практическое внедрение минимальных булевых многочленов.

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

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

Во введении описана актуальность темы, сформулирована цель, дана структура курсовой работы.

В первой главе даны основные определения и основные понятия  булевой алгебры.

Во второй главе дается определение минимальных форм булевых  многочленов и намечен курс дальнейшего исследования.

Третья глава посвящена  применению минимальных форм булевых  многочленов к решению задач.

В заключении сформулированы основные выводы к работе.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

I. ОСНОВНЫЕ ПОНЯТИЯ БУЛЕВОЙ АЛГЕБРЫ

1.1 ОСНОВНЫЕ ЭТАПЫ РАЗВИТИЯ БУЛЕВОЙ АЛГЕБРЫ

В 1847 году Дж. Буль написал  маленькую, но эпохальную книгу «математический  анализ логики», в которой логика трактовалась как чисто формальная система; интерпретация в обычном  языке пришла позже. Буль писал, что  математика характеризуется своей  формой, но не содержанием. В своей последующей книге «Исследование законов мышления» (1854) он ввел понятие булевой алгебры.

Булевское исчисление логики сосредоточено  на формальной трактовке логики посредством  математических (особенно алгебраических) методов и на описании логических тождеств. Следуя Булю, школа английских математиков, а также Шрёдер, Уайтхед разработали аксиоматику операций конъюнкции, дизъюнкции, отрицания; с другой стороны, Пирс и Шрёдер создали аксиоматику порядка, используя отношение включения в качестве фундаментального понятия. В 1904 году Хантингтон исследовал две системы аксиом и начал трактовать булевы алгебры как самостоятельные математические структуры, не обязательно связанные с логикой.

Буль использовал дистрибутивность пересечения относительно объединения, которую еще до него отметил Ламберт. Буль работал с множествами. Обозначая пересечение х и у через ху, а объединение – через х + у, если х и у дизъюнкты. Подобно Лейбницу, он интерпретировал отношение включения х Í у как ху = х, что легко давало возможность получить классические правила силлогизма. Затем Джевонс распространил операцию объединения на произвольные х и у; Де Морган и, позже, Пирс доказали соотношение двойственности, называемые законами де Моргана.

Большинство логиков девятнадцатого века не высказывало большого интереса к применению в математике своих находок. Одной из причин этого было отсутствие кванторов, введенных позже Фреге и Пирсом. Пеана, среди прочих, ввел символы È, Ç, - для объединения, пересечения и вычитания множеств. После книги ван дер Вардена по современной алгебре понятие универсальной алгебры было уже не за горами. Биркгоф развил концепцию «алгебры», отправляясь от подходов ван дер Вардена, и взял название «универсальная алгебра» из книги Уайтхеда. в 1934 году, будучи в Геттингене, Маклейн также высказывал некоторые мысли об универсальной алгебре, но не опубликовал их. Одна из фундаментальнейших статей по теории решеток была напечатана Оре в 1935 году. Последующие годы ознаменовались целым рядом исследований в области, как теории, так и приложений решеток, например, в теории групп, проектированной геометрии, квантовой механике, функциональном анализе, теории меры и интегрирования.

В 1933 – 1937 гг. М. Стоун получил важные результаты о булевых алгебрах, которые он интерпретировал как специальные кольца, а именно как булевы кольца, где была применима теория идеалов. Другие фундаментальные вопросы, рассматривавшиеся Стоуном, - это вопросы о представлении булевых алгебр и приложения булевых алгебр в топологии. С тех пор теория решеток превратилась во вполне жизнеспособную, сильную и самостоятельную дисциплину.

 

1.2 ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ПОНЯТИЯ БУЛЕВОЙ АЛГЕБРЫ

Определение: Булевой алгеброй (обозначим В) называется непустое множество элементов с двумя бинарными операциями «+», «*» и одной унарной операцией «`», а так же специальными элементами 0 и 1, если выполняются следующие свойства [1, c.38]:

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	0		*	1	0
1	1	1		1	1	0
0	1	0		0	0	0

 

И унарная операция: 0` = 1, 1` = 0.

Пример 2: Множество делителей числа 70:<1,2,5,7,10,14,35,70>

1. a + b = НОД (a, b)
2. a * b = НОК (a, b)
3. a` = 70/a

Определение: Пусть С - непустое подмножество множества В. Говорят, что С - подалгебра  алгебры В, если она сама является алгеброй с теми же операциями.

Подмножество С - есть подалгебра алгебры В Û С замкнуто относительно трех операций.

Пример 3: Если С=<1,2,35,70> замкнуто относительно операций «+», «*», «`», тогда С является подалгеброй алгебры В.

Определение: Две булевы алгебры В и В` изоморфны: В ~ В`, если существует взаимно-однозначная функция f: B®B`, такая, что [1, c.42]:

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) указывают на то, что решетка дистрибутивна и дополнена. И наоборот, любая ограниченная, дистрибутивная и дополненная решетка есть булева алгебра.

Определение: Булева алгебра – это ограниченная, дистрибутивная и дополненная решетка [3, c.108].

Мы можем ввести на булевой алгебре отношение частичного порядка. Полагаем, что 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;

2. Пусть (3) верно, тогда

a + b = (a` + b) * (a + b) = b * (a + a`) = b * 1 = b;

2. Докажем эквивалентность (3) и (4)

1. Пусть (3) верно, тогда

0 = 1` = (a` + b)` = (a`)` * b` = a * b`;

     b)   Пусть (1) верно, тогда

1 = 0` = (a + b`)` = a` + (b`)` = a` + b;

3. Докажем эквивалентность (2) и (4)

1. Пусть (2) верно, тогда

a * b` = (a * b) * b` = a * (b * b`) = a * 0 = 0;

2. Пусть (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=<1,2,5,7,10,14,35,70>. Множество A=<2,5,7> -множество атомов решетки 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 = {x₁,…, x_n} – множество из n символов (называемых неизвестными или переменными), которое не содержит символов 0 и 1. Булевы многочлены над Х_n суть объекты, которые могут быть получены последовательным применением следующих правил [1, c.102]:

1. х₁, х₂, …, х_n, 0,1 – булевы многочлены;
2. если p и q – булевы многочлены, то таковыми являются и

(p) Ù (q), (p) Ú (q), (p)¢.

Обозначим множество всех булевых  многочленов над Х_n через Р_n.

Пример. Вот несколько примеров булевых многочленов над {х₁, х₂}: 0,1, х₁, х_2, х₁ Ù х₂, х₁ Ú х₂, х₁¢, х₁¢ Ù х₂.

Так как любой булев многочлен  над x₁,…, x_n модно рассматривать как булев многочлен над x₁,…, x_n, x_n+1, мы имеем