3.2 Алгебра высказываний. Основные логические операции и их таблицы истинности.

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

Для образования новых высказываний наиболее часто используют логические операции, выражаемые с помощью логических связок "И", "ИЛИ", "НЕ",.

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

НЕ Операция, выражаемая словом "не", называется отрицанием (инверсией) и обозначается чертой над высказыванием (или знаком ¬). Высказывание Ā истинно, когда А ложно, и ложно, когда А истинно.

Пример. "Луна - спутник Земли" (А); "Луна - не спутник Земли" (Ā).

А	Ā
0	1
1	0

И Операция, выражаемая связкой "и", называется конъюнкцией (лат. conjunctio - соединение) или логическим умножением и обозначается точкой "·" (может также обозначаться знаками ٨ или &).

Высказывание А·В истинно тогда и только тогда, когда оба высказывания А и В истинны.

Например, высказывание "10 делится на 2 и 5 больше 3" истинно, а высказывания "10 делится на 2 и 5 не больше 3", "10 не делится на 2 и 5 больше 3", "10 не делится на 2 и 5 не больше 3" - ложны.

А	В	А&В
0	0	0
0	1	0
1	0	0
1	1	1

ИЛИ Операция, выражаемая связкой "или" (в не исключающем смысле этого слова), называется дизъюнкцией (лат. disjuncito - разделение) или логическим сложением и обозначается знаком v (или +).

Высказывание АvВ ложно тогда и только тогда, когда оба высказывания А и В ложны.

Например, высказывание "10 не делится на 2 или 5 не больше 3" ложно, а высказывания "10 делится на 2 или 5 больше 3", "10 делится на 2 или 5 не больше 3", "10 не делится на 2 или 5 больше 3" - истинны.

А	В	А+В
0	0	0
0	1	1
1	0	1
1	1	1

3.3 Построение таблиц истинности для сложных логических выражений.

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

При построении таблиц истинности надо руководствоваться определенной последовательностью действий:

Алгоритм построения таблицы истинности:

1. подсчитать количество переменных n в логическом выражении;

2. определить число строк в таблице, которое равно m = 2ⁿ;

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

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

5. заполнить столбцы входных переменных наборами значений;

6. провести заполнение таблицы значениями (0 и 1) истинности по столбцам, выполняя логические операции.

Порядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок договорились считать, что сначала выполняется операция отрицания ("не"), затем конъюнкция ("и"), после конъюнкции - дизъюнкция ("или") .

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

a) Z = (A + B · C) + (¬A · C)

А	В	С	В · С	А + В · С	¬А	¬А · С	(А + В · С) + (¬А · С)
0	0	0	0	0	1	0	0
0	0	1	0	0	1	1	1
0	1	0	0	0	1	0	0
0	1	1	1	1	1	1	1
1	0	0	0	1	0	0	1
1	0	1	0	1	0	0	1
1	1	0	0	1	0	0	1
1	1	1	1	1	0	0	1

b) F = (A + B)&(¬A + ¬B)

A	B	A + B	¬A	¬B	¬A + ¬B	(A + B) · (¬A + ¬B)
0	0	0	1	1	1	0
0	1	1	1	0	1	1
1	0	1	0	1	1	1
1	1	1	0	0	0	0