Элементы алгебры логики

Для описания логики функционирования аппаратных и программных средств компьютера используется алгебра логики или булева алгебра.

Дж. Буль – английский математик 19 века. Булева алгебра оперирует с логическими переменными, которые могут принимать только 2 значения: истина и ложь, обозначаемые соответственно 1 и 0.

· Совокупность значений логических переменных , ,…, называется набором переменных. Набор логических переменных удобно изображать в виде n-разрядного двоичного числа, каждый разряд которого равен значению одной из переменных. Количество наборов логических переменных в n двоичных разрядах равно 2 ⁿ.

· Логической функцией от набора логических переменных f(, ,…, ) называется функция, которая может также принимать только 2 значения: истина или ложь.

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

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

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

Наиболее часто используемая система логических функций: инверсия (Ø, отрицание, NOT), конъюнкция (), логическое умножение, AND, &), дизъюнкция (Ú, логическое сложение, OR).

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

f(x1, x2, x3) = (x1)x2 * x2*x3))x1*`x3;

f(0, 1, 1) = (0)1*1*1))0*`1= 0;

f(1, 0, 1) = (1)0*0)1))1*`1 =1.

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

1. Коммуникативный закон (переместительный):

x1*x2=x2*x1

x1)x2=x2)x1

2. Ассоциативный закон (сочетательный):

x1*(x2*x3) = (x1*x2)*x3

x1)(x2)x3) = (x1)x2))x3

3. Дистрибутивный закон (распределительный):

x1)(x2*x3) = (x1)x2)*(x1)x3)

x1*(x2)x3) = (x1*x2))(x1*x3)

4. Правила де Моргана:

x1*x2 = `x1)`x2

x1)x2 = `x1*`x2

5. Правила операций с константами:

`0 = 1; `1 = 0; x)1 = x; x)0 = 0; x*0 = x; x*1 = 1.

6. Правила операций переменной с ее инверсией:

x*`x = 1;

x)`x = 0;

7. Закон поглощения:

x1*(x1)x2) = x1;

x1)(x1*x2) = x1.

8. Закон идемпотентности:

x*x = x;

x)x = x;

9. Закон двойного отрицания:

x = x.

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

Поиск по сайту: