6.3 Вычисление выражений.

При вычислении значения сложного логического высказывания необходимо учитывать приоритет булевых операций and, or, not. Самый высокий приоритет имеет операция отрицания not, затем and и только потом or.

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

Если в выражении встречаются две или более операций с одинаковым приоритетом, то они выполняются слева направо в данном выражении.

Пример:

Пусть A = "истина", B = "ложь", C ="ложь", D="истина"

Указать порядок выполнения операций и найти значение логического выражения при заданных переменных :

A and B or not C and D

Решение:

Сначала выполняется операция not C, затем not C and D, где в качестве одного из высказываний используется выражение not C. Затем - операция A and B. Самой последней выполняется операция логического сложения or, т.е. (A and B) or (not C and D), где скобки поставлены для наглядности.

Вычислим данное выражение, соблюдая порядок выполнения логических операций и используя таблицы истинности для данных операций ("истина" равносильна 1, "ложь" - 0):

Результатом операции not C является значение C="истина", not C and D = "истина", т.к. обе переменные имеют значение "истина". Результат A and B будет "ложь", а значением исходного выражения является "истина" потому, что при выполнении операции or, слева от нее находится истинное выражение, получаем "истину" на основании определения логического сложения.

Во многих языках программирования истинность логического выражения обозначают - true ("истина"), а ложность - false ("ложь").

6.4 Законы булевой алгебры.

Таблицы истинности могут применяться для анализа и сопоставления любых сложных высказываний. Такие проблемы возникают при анализе отрицаний. Например, отрицание "неверно, что 0<x<1" означает, что "x<=0" или "x>=1".

Приведенный выше пример является частным случаем закона отрицания логического умножения.

Существует два основных закона булевой алгебры, законы де Моргана:

1-ый закон де Моргана: (отрицание конъюнкции)

Отрицание логического умножения равносильно логическому сложению отрицаний, т.е.

not (A and B) = (not A) or (not B)

2-ый закон де Моргана: (отрицание дизъюнкции)

Отрицание логического сложения равносильно логическому умножению отрицаний, т.е.

not (A or B) = (not A) and (not B)

Кроме этого, в булевой алгебре существует следующие законы, позволяющие делать эквивалентные преобразования:

Ассоциативность сложения и умножения:

X1 or (X2 or X3) = (X1 or X2) or X3 = X1 or X2 or X3

X1 and (X2 and X3) = (X1 and X2) and X3 = X1 and X2 and X3

Коммутативность сложения и умножения:

X1 or X2 = X2 or X1

X1 and X2 = X2 and X1

Дистрибутивность умножения относительно сложения:

X1 and (X2 or X3) = X1 and X2 or X1 and X3

Дистрибутивность сложения относительно умножения:

X1 or (X2 and X3) = (X1 or X2) and (X1 or X3)

Идемпотентность (отсутствие степеней и коэффициентов):

X and X = X

X or X = X

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

not not X = X

Свойства констант 0("ложь") и 1("истина"):

X and 1 = X	X and 0 = 0
X or 1 = 1	X or 0 = X
not 0 = 1	not 1 = 0

Закон противоречия:

X and not X = 0

X or not X = 1

На основании приведенных выше законов можно получить наиболее распространенные соотношения исключения третьего:

X or X and Y = X and 1 or X and Y = X and (1 or Y) = X (поглощение)

X and Y or X and not Y = X and (Y or not Y) = X and 1 = X (склеивание)

X or not X and Y = (X or not X) and (X or Y) = 1 and (X or Y) = X or Y