Элементы булевой алгебры

Булева алгебра, или алгебра высказываний - это самостоя­тель­ный раздел дискретной математики, который формализует правила формальной логики и находит самые разнообразные применения. Изложим некоторые практические сведения из булевой алгебры, которые нам понадобятся в даль­нейшем.

Булева алгебра оперирует с высказываниями. Каждому высказы­ва­нию можно сопоставить одно из логических значений - "истина" или "ложь". На практике для обозначения значения "истина" часто исполь­зуют цифру 1, а значения "ложь" - 0. В нашем случае понятие "вы­ска­зы­ва­ние" заменяется понятием "связь" или "отношение".

В булевой алгебре над высказываниями определен ряд операций. Каж­дая операция представ­ляет новое высказывание, истинность кото­ро­го определяется по особым для каждой операции правилам.

Пусть даны два высказывания A и B. Тогда

1. Конъюнкция - соответствует связке " и ", обозначается , или , или . истинно тогда и только тогда, когда истинно и A, и B, и ложно в остальных случаях (аналог умножения)

1∙1=1; 1∙0=0; 0∙1=0; 0∙0=0.

2. Дизъюнкция - соответствует связке " или "; обозначается A+B, или AÚB; истинно, если истинно хотя бы одно из высказываний (аналог сложения)

1+0=1; 1+1=1; 0+1=1; 0+0=0.

3. Отрицание - соответствует связке " не ", обозначается ⌐А; лож­но, если A истинно, и истинно, если A ложно

⌐1=0; ⌐0=1.

4. Импликация (следование) - A→B (A - посылка, B - следствие) - соответствует связке " если - то ", "из A следует B); ложно тогда и только тогда, когда A истинно, а B ложно.

5. Эквивалентность A = B - истинно, если A и B оба истинны или оба ложны.

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

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

A + B = B + A; AB = BA; (A + B) + C = A + (B + C);

(AB)C = A(BC); A(B + C) = AB + AC; A + BC = (A+B)(A+C);

A + A = A; AA = A; A + (AB) = A; A(A + B) = A; A⌐A = 0;

A + 0 = A; A + 1 = 1; A + ⌐A = 1; A1 = A; A0 = 0; ⌐⌐A = A;

A + B = ⌐ (⌐A⌐B); ⌐ (A + B) =⌐A⌐B; AB =⌐ (⌐A + ⌐B);

⌐(AB) = ⌐A + ⌐B; AB + A⌐B = A; (A + B)(A + ⌐B) = A;

A = B эквивалентно соотношению ⌐AB + A⌐B = 0, либо

A + B = AB, либо AB + ⌐A⌐B = 1 и т.д.

Более подробный набор формул можно найти в специальной лите­ратуре.

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

Приложение 2

Дата добавления: 2015-06-04