Булева алгебра и булевы многочлены | Конова Виктория Владимировна. Работа №354772

ВВЕДЕНИЕ

Обычная в школьной алгебре мы имеет дело с натуральными, целыми, а также рациональными и действительными числами. Но если взять какое-либо определенное количество чисел и проделать с ними различные операции, например сложение(вычитание)и умножение, то мы вполне можем получить новую разновидность алгебры. И таких разновидностей будет огромное количество. Одной из таких разновидностей является дискретная алгебра, которая включает в себя булеву алгебру.

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

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

Задачи работы:

изучить

основные

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

;

рассмотреть виды построения нормальных форм булевых многочленов;

рассмотреть

методы

примеры

минимизации булевых многочленов

к

ПОНЯТИЕ БУЛЕВОЙ АЛГЕБРЫ И БУЛЕВА КОЛЬЦА.

Еще в 1847г. Джордж Буль написал книгу, именуемая: «Математический анализ логики». Джордж утверждал, что математика в основном характеризуется не содержательностью, а формой. Затем, в книге «Исследование законов мышления» в 1854 г. впервые было введено такое понятие, как булева алгебра.

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

Для того, чтобы булева алгебра развивалась было вложено немало сил: Буль ввел дистрибутивность пересечения относительно объединения; Джевонс ввел операцию объединения; Де Морган, а также чуть позднее Пирс ввел Законы Де Моргана.

Теория булевой алгебры представляет собой огромный раздел в дискретной математике. Операции булевой алгебры применяются в логических рассуждениях. Здесь две переменные (0 и 1) интерпретируются как Истинное (1) и Ложное (0).

Для введения булевых операций будем использовать следующие обозначения:1 и 0-булевы константы:

ᴧ-конъюнкция(пересечение);

ᴠ-дизъюнкция(объединение);

Ᾱ-инверсия(отрицание);

~-эквивалентность;

↔-неравнозначность;

Для начала изучения булевы алгебры, рассмотрим ее основные понятия и определения.

Определение. Булевой алгеброй ℬ называется множество(непустое) В с заданными на нем двумя бинарными операциями ᴠ(дизъюнкция), ᴧ(конъюнкцией) и одной унарной операцией Ᾱ(отрицания) и двумя выделенными элементами:0(Ложь) и 1(Истина) такими, что для любых х, у и z из множества В выполняются следующие аксиомы:

1.Коммутативность

x ᴠ y=y ᴠ x; (х ᴧ у =у ᴧ х);

2.Ассоциативность

x ᴠ (y ᴠ z) = (x ᴠ y) ᴠ z; x ᴧ (y ᴧ z) = (x ᴧ y) ᴧ z;

3.Поглощение:

x ᴠ (x ᴧ y) =x; x ᴧ (x ᴠ y) =x;

4.Дистрибутивность

(x ᴠ y) ᴧ z = (x ᴧ z) ᴠ (y ᴧ z); (x ᴠ y) ᴧ z = (x ᴧ z) ᴠ (y ᴧ z);

Множество В называется постоянным носителем булевой алгебры ℬ, а 0 и 1 -выделенными элементами или универсальными гранями.

Таким образом, в булевой алгебре для объединения и пересечения выполняются законы коммутативности, дистрибутивности, поглощения ассоциативности и идемпотентности. Очевидно, что в булевой алгебре операции объединения и пересечения определены для любой совокупности элементов.

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

Итак, другими словами, булеву алгебру можно определить как систему А(В,ᴪ1,ᴪ2,…,ᴪn), в которой несущим множеством является двухэлементное множество В={0,1}, а Ω={ᴪ1, ᴪ2, …, ᴪn }-заданные на этом множестве логические операции.

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

Что же такое булево кольцо?

Определение. Булево кольцо-кольцо с идемпотентным умножением, то есть кольцо (R, +, •), в котором х2 =х для всех хϵR.

Теорема: Булево кольцо (R, +, •, ¯, 0), где ¯ -унарная операция взятия противоположного элемента, коммутативно и х + х =0 для всех хϵR.

Доказательство: докажем, что х +х = (х +х)2= х2+х2+ х2+х2= х + х+ х +х=> х +х =0 (т.е. х = -х).

Ч.т.д.

Теорема: пусть ℬ= {В, ᴠ, ᴧ, ¯, 0 ,1}-булева алгебра. Для любых х, у ϵ В положим х +у = (х ᴧ ¯у) ᴠ (¯хᴧ у), х • у=х ᴧ у.

Тогда ℬ*= {В, +, •, 0, 1} есть булево кольцо с единицей.

Теорема: пусть ℛ = {R, +, •, 0, 1}-булево кольцо с единицей. Для любых х, у ϵ R положим: х ᴠ у=х +у +х• у, х ᴧ у= х• у, x¯=х+1

Тогда ℛ*= {R, ᴠ, ᴧ, ¯, 0, 1}-булева алгебра.

1.1.Основные свойства и их доказательства.

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

1.Законы де Моргана:

¯(х ᴠ у)=¯x ᴧ ¯y; ¯(х ᴧ у)=¯x ᴠ ¯y;

Доказательство: для доказательства построим таблицу истинности:

Таблица 1.1.1

X

Y

¯X

¯Y

X ᴠ Y

¯(X ᴠ Y)

¯X ᴧ ¯Y

X ᴧ Y

¯(X ᴧ Y)

¯X ᴠ ¯Y

0

0

1

1

0

1

1

0

1

1

0

1

1

0

1

0

0

0

1

1

1

0

0

1

1

0

0

0

1

1

1

1

0

0

1

0

0

1

0

0

2.Закон Блейка-Порецкого

х ᴠ (¯х ᴧ у) =х ᴠ у; х ᴧ (¯х ᴠ у) =х ᴧ у;

3.Идемпотентность

х ᴧ х=х; х ᴠ х=х;

4.Двойное отрицание

¯ ¯х=х; x ᴠ 0=x; x ᴧ 0=0; ¯1=0; x ᴧ 1=x; x ᴠ 1=1; ¯0=1

5.Склеивание

(х ᴧ у) ᴠ (¯х ᴧ у) =у; (х ᴠ у) ᴧ (¯х ᴠ у) =у;

Все остальные доказательства также доказываются с помощью таблицы истинности.

Наряду с этим рассмотрим свойства булева кольца:

Одним из основных свойств булева кольца является удовлетворение условию, что х +х=0 для всех хϵR.

Всякое булево кольцо (R, +, •) коммутативно, что также является следствием идемпотентности умножения: х +у= (х +у)2

Доказательство: х2+ху+ух+у2=х+у+ху+ух. Отсюда х + у = (х + у)2= х2+ху+ух+у2=х+ху+ух+у => Видим, что ху+ух=0, далее выполняя действия получаем ху=ху+(ух+ху)=(ху+ух)+ух=0+ух=ух. Из этого делаем вывод, что ху=ух.

Ч.т.д.

Учитывая, что свойство х +х=0 показывает, что любое булево кольцо является ассоциативной алгеброй над полем F2 с двумя элементами только одним способом, мы видим, что в булевом кольце выполняется свойство ассоциативности: (х +у) +z=x+(y+z).