Основные сведения

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

Цель работы: изучить основные понятия, определения и законы булевой алгебры.

Основные сведения

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

Двоичными (булевыми ) переменными х1, х2, ... хn называются переменные, которые могут принимать только два значения: 0 или 1. Совокупность таких значений называют набором.

Двоичной (булевой) функцией от двоичных переменных называется функция, у которой аргументы являются булевыми переменными и которая на любом наборе значений аргументов принимает значения из того же множества { 0, 1}. Область определения булевой функции конечна, общее число наборов двоичных аргументов, на которых определяется булева функция, равно 2ⁿ.

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

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

Таблица 8

x	f1= отрицание переменной х или ее инверсия	f2=0 константа нуль	f3=1 константа единица	f4=x переменная х

Элементарные логические функции двух переменных (Табл. 9):

f5 = x1 & x2 - конъюнкция, логическое умножение, логическое “и”;

f6 = x1 V x2 - дизъюнкция, логическое сложение, логическое “или” ;

f7 = x1 x2 = x2 V x1 - сложение по модулю два, разделительное “или”;

f8 = x1 x2 = & функция Пирса, антидизъюнкция, функция Вебба;

f9 = x1 | x2 = V - функция Шеффера, антиконъюнкция;

f10 = x1~ x2 - эквивалентность, тождественность;

f11 = x1 x2 = V x2- импликация, логическое следование.

Таблица 9

x1 x2	f5 = =x1& x2	f6 = =x1 Vx2	f7 = =x1 x2	f8 = =x1 x2	f9 = =x1 | x2	f10= = x1~x2	f11 = =x1 x2

Булева функция F, зависящая от трех аргументов, называется мажоритарной,если имеет место равенство F= x1x2 V x1x3 V x2x3

Основные законы булевой алгебры

В булевой алгебре для представления любой функции в виде формулы кроме символов основных операций используются следующие символы: малые буквы типа x, y, z ... ( включая буквы с индексами) для обозначения переменных, константы 0 и 1, скобки.

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

В булевой алгебре при отсутствии в выражении скобок вводится следующий порядок действий: первыми выполняются операции отрицания, далее- конъюнкции, а затем - дизъюнкции. Скобки меняют порядок действий - в первую очередь должны выполняться операции внутри скобок.

1. Закон двойного отрицания = х

2. Закон коммутативности х1 V х2 = х2 V х1
х1 & x2 = x2 & x1 или ( x1 x2 = x2 x1)

3. Закон ассоциативности x1 V (x2 V x3) = (x1 V x2) V x3
x1 & (x2 & x3) = (x1 & x2) & x3 или
x1 (x2 x3) = (x1 x2) x3

4. Законы дистрибутивности x1 (x2 V x3) = x1 x2 V x1 x3
x1 V x2 x3 = (x1 V x2) (x1 V x3)

5. Правила Де-Моргана =
= V

6. Правила операций с константами 0 и 1
x V 0 = x x V 1 = 1
x & 0 = 0 x & 1 = x
= 1 = 0

7. Правила операций с переменной и ее инверсией
х V =1 х & =0

Из основных законов легко получаются следующие соотношения

- Законы поглощения x1 V x1x2 =x1
x1 (x1V x2) =x1

- Закон идемпотентности дизъюнкции и конъюнкции
x V x V x V x . . . = x
х х х . . . = х

- Закон склеивания
x1 V x1 x2 =x1

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

- Используя второй закон дистрибутивности и выполняя тождественные преобразования, можно получить

х1 V x2 = х1 V х2