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

курсовая работа

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

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

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

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

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

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

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

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

a + b = b + a , a , b B

a * b = b * a , a, b B

a + (b * c) = (a + b) * (a + c)

a* (b + c) = (a * b) + (a * c)

a + 0 = a, a * 1 = a. (Тождественность)

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: BB`, такая, что:

f (a + b) = f (a) + f (b)

f (a * b) = f (a) * f (b)

f (a`) = (f (a))`

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

Основные теоремы абстрактной булевой алгебры.

Идемпотентный закон: a + a = a, a * a = a.

Граничный закон: a + 1 = 1, a + 0 = a.

Абсорбционный закон: a + (a * b) = a, a * (a + b) = a.

Ассоциативный закон: a + (b + c) = (a + b) + c, a * (b * c) =

(a * b) * c.

Единственность дополнения: если x: a + x = 1 , a * x = 0,

то x = a`.

Инволютивный закон: ((a`))` = a 0` = 1 , 1` = 0.

Закон де Моргана: (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) и (3)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тогда выражения (1), (2), (3), (4) эквивалентны.

Пример 1. Рассмотрим алгебру множеств - модель булевой алгебры.

А В если А В.

АВ=В

АВ=А

АВ=U

АВ`=

Любая конечная булева алгебра может содержать лишь 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

14 35

2 5 7

1

2) Множество А = {2,5,7}

Отношение вложенности.

{2,5,7}

{2,5} {2,7} {5,7}

{2} {5} {7}

Эта решетка изоморфна предыдущей.

Алгебра множеств и алгебра высказываний являются моделями абстрактной булевой алгебры. Все абстрактные булевы алгебры (которые состоят из одинакового числа элементов) изоморфны.

Делись добром ;)