logo
Конспект лекций Комп схем и АК 2011

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

Булева алгебра состоит из следующих элементов:

  1. числа,

  2. переменные,

  3. операции,

  4. выражения,

  5. функции,

  6. законы.

Рассмотрим каждый из представленных элементов:

    1. Числа – два числа: логический ноль (лог. «0») и логическая единица (лог. «1») в Булевой алгебре отождествляются с понятиями «истина» и «ложь»;

    2. Переменные – булевы (логические, двоичные) переменные называются переменными, принимающими значения из множества ноль и единица {0;1};

    3. Операции – простейшие логические функции Булевой алгебры, в состав которых входят:

                  1. Отрицание (инверсия):

Только операция отрицания является унарной (операция с одной переменной). К примеру: операция означает отрицание переменной, т.е., прии наоборот – при. Отрицание может быть применено и к выражению –, т.к. выражениеможно представить в виде функции, то инверсия функциибудет иметь следующий вид.

Операция отрицания (НЕ) f=читается, как f есть (эквивалентна)НЕ . Элемент, реализующий функциюНЕ, называется элементом НЕ (инвертором).

                  1. Конъюнкция (логическое умножение):

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

Для написания операции конъюнкции применяются следующие символы (знакооперации): , а так же, как и при записи арифметического умножения, допускается опускание символа операции умножения. К примеру, записи:,,иозначают операцию конъюнкции над переменнымии.

Операция конъюнкции (логического умножения) записывается в виде f=X1·X2. Функция конъюнкции читается так: f есть (эквивалентна) Х1 и Х2, поскольку функция истинна тогда, когда истинны 1-й и 2-й аргументы (переменные). Конъюнкцию называют функцией И, а элемент, реализующий эту функцию, элементом И.

В общем случае функцию логического умножения от n переменных записывают так:

Количество переменных (аргументов), участвующих в одной конъюнкции, соответствует количеству входов элемента И.

                  1. Дизъюнкция (логическое сложение):

Для написания операции дизъюнкции применяются следующие символы: . К примеру, записи: иозначают операцию дизъюнкции над переменнымии.

Дизъюнкция (логическое сложение) записывается в виде

f=X1 + X2, и читается так: f есть Х1 или Х2, поскольку функция истинна, когда истинна одна или другая переменная (хотя бы одна). Поэтому функцию дизъюнкции часто называют функцией ИЛИ.

В общем случае функцию логического сложения от n переменных записывают так:

3.4. Исключающее ИЛИ ( сложение по модулю 2)

Для написания операции исключающего ИЛИ используют знак .

Операция исключающего ИЛИ записывается как f=X1X2 , и читается как f есть исключающее ИЛИ от X1 и X2, или f равно сумме по модулю 2 X1 и X2.

    1. Выражения – переменные и знакооперации, соединенные вместе при возможном наличии скобок для задания порядка выполнения операций. Приоритет задается порядком операции. У операции конъюнкции порядок выше, чем у операции дизъюнкции.

    2. Функции – Булевой (логической) функцией называется такая функция, аргументами которой являются булевы переменные, и сама функция принимает значение из множества {0;1}.

Областью определения Булевой функции является совокупность 2m двоичных наборов ее аргументов. Набор аргументов можно рассматривать как m-компонентный двоичный вектор.