Минимальные формы булевых многочленов
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}
Эта решетка изоморфна предыдущей.
Алгебра множеств и алгебра высказываний являются моделями абстрактной булевой алгебры. Все абстрактные булевы алгебры (которые состоят из одинакового числа элементов) изоморфны.