Кратко

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

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

1. подсчитать \(n\) — число переменных в выражении;
2. подсчитать общее число логических операций в выражении;
3. установить последовательность выполнения логических операций с учётом скобок и приоритетов;
4. определить число столбцов в таблице: число переменных + число операций;
5. заполнить шапку таблицы, включив в неё переменные и операции в соответствии с последовательностью, установленной в п. 3;
6. определить число строк в таблице (не считая шапки таблицы): \(m = 2^n\);
7. выписать наборы входных переменных с учётом того, что они представляют собой ряд целых \(n\)-разрядных двоичных чисел от 0 до \(2^n - 1\);
8. провести заполнение таблицы по столбцам, выполняя логические операции в соответствии с установленной последовательностью.

Построим таблицу истинности для логического выражения \(A \lor A \& B\). В нём две переменные, две операции, причём сначала выполняется конъюнкция, а затем — дизъюнкция. Всего в таблице будет четыре столбца:

| A | B | A&B | A ∨ A&B |

Наборы входных переменных — это целые числа от 0 до 3, представленные в двухразрядном двоичном коде: 00, 01, 10, 11. Заполненная таблица истинности имеет вид:

A	B	A&B	A ∨ A&B
0	0	0	0
0	1	0	0
1	0	0	1
1	1	1	1

Обратите внимание, что последний столбец (результат) совпал со столбцом A. В таком случае говорят, что логическое выражение \(A \lor A \& B\) равносильно логической переменной A.

1.3.4. Свойства логических операций

Рассмотрим основные свойства логических операций, называемые также законами алгебры логики.

1. Переместительный (коммутативный) закон: • для логического умножения: \(A \& B = B \& A\); • для логического сложения: \(A \lor B = B \lor A\).
2. Сочетательный (ассоциативный) закон: • для логического умножения: \((A \& B) \& C = A \& (B \& C)\); • для логического сложения: \((A \lor B) \lor C = A \lor (B \lor C)\). При одинаковых знаках операций скобки можно ставить произвольно или вообще опускать.

3. Распределительный (дистрибутивный) закон: • для логического умножения: \(A \& (B \lor C) = (A \& B) \lor (A \& C)\); • для логического сложения: \(A \lor (B \& C) = (A \lor B) \& (A \lor C)\).
4. Закон двойного отрицания: \(\overline{\overline{A}} = A\). Двойное отрицание исключает отрицание.
5. Закон исключённого третьего: • для логического умножения: \(A \& \overline{A} = 0\); • для логического сложения: \(A \lor \overline{A} = 1\). Из двух противоречивых высказываний об одном и том же предмете одно всегда истинно, а второе — ложно, третьего не дано.
6. Закон повторения: • для логического умножения: \(A \& A = A\); • для логического сложения: \(A \lor A = A\).
7. Законы операций с 0 и 1: • для логического умножения: \(A \& 0 = 0; A \& 1 = A\); • для логического сложения: \(A \lor 0 = A; A \lor 1 = 1\).
8. Законы общей инверсии: • для логического умножения: \(\overline{A \& B} = \overline{A} \lor \overline{B}\); • для логического сложения: \(\overline{A \lor B} = \overline{A} \& \overline{B}\).

Законы алгебры логики могут быть доказаны с помощью таблиц истинности. Докажем распределительный закон для логического сложения: \(A \lor (B \& C) = (A \lor B) \& (A \lor C)\).

A	B	C	B & C	A ∨ (B & C)	A ∨ B	A ∨ C	(A ∨ B) & (A ∨ C)
0	0	0	0	0	0	0	0
0	0	1	0	0	0	1	0
0	1	0	0	0	1	0	0
0	1	1	1	1	1	1	1
1	0	0	0	1	1	1	1
1	0	1	0	1	1	1	1
1	1	0	0	1	1	1	1
1	1	1	1	1	1	1	1

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

Пример 2. Найдём значение логического выражения \((X < 3) \& \overline{(X < 2)}\) для числа \(X = 0\). Решение. При \(X = 0\) получаем следующее логическое выражение: \((0 < 3) \& \overline{(0 < 2)}\). Так как логические выражения \(0 < 3\), \(0 < 2\) истинны, то, подставив их значения в логическое выражение, получаем: \(1 \& \overline{1} = 1 \& 0 = 0\).

1.3.5. Решение логических задач

Рассмотрим несколько способов решения логических задач.

Задача 1. Коля, Вася и Серёжа гостили летом у бабушки. Однажды один из мальчиков нечаянно разбил любимую бабушкину вазу. На вопрос, кто разбил вазу, они дали такие ответы: Серёжа: 1) Я не разбивал. 2) Вася не разбивал. Вася: 3) Серёжа не разбивал. 4) Вазу разбил Коля. Коля: 5) Я не разбивал. 6) Вазу разбил Серёжа. Бабушка знала, что один из её внуков, назовём его правдивым, оба раза сказал правду; второй, назовём его шутником, оба раза сказал неправду; третий, назовём его хитрецом, один раз сказал правду, а другой раз — неправду. Назовите имена правдивого, шутника и хитреца. Кто из внуков разбил вазу? Решение. Пусть \(K = \)«Коля разбил вазу», \(B = \)«Вася разбил вазу», \(C = \)«Серёжа разбил вазу». Для решения задачи можно соста-

вить таблицу истинности, в которой представить высказывания каждого мальчика. Так как ваза разбита одним внуком, то чтобы выяснить, кто именно это сделал, достаточно фрагмента таблицы истинности, содержащего наборы значений входных переменных: 001, 010, 100.

K	B	C	Утверждения Серёжи		Утверждения Васи		Утверждения Коли
			\(\overline{C}\)	\(\overline{B}\)	\(\overline{C}\)	\(K\)	\(\overline{K}\)	\(C\)
0	0	1	0	1	0	0	1	1 ✓
0	1	0	1	0	1	0	1	0
1	0	0	1	1	1	1	0	0

Исходя из того, что знает о внуках бабушка, следует искать в таблице строку, содержащую в каком-либо порядке три комбинации значений: 00 (слова шутника), 11 (слова правдивого внука), 01 или 10 (слова хитреца). Такая строка отмечена галочкой. Согласно этой строке, вазу разбил Серёжа, он же оказался хитрецом. Шутником оказался Вася. Имя правдивого внука — Коля.

Задача 2. В соревнованиях по гимнастике участвуют Алла, Валя, Сима и Даша. Болельщики высказали предположения о возможных победителях:

1. Сима будет первой, Валя — второй;
2. Сима будет второй, Даша — третьей;
3. Алла будет второй, Даша — четвёртой. По окончании соревнований оказалось, что в каждом из предположений только одно из высказываний истинно, другое ложно. Какое место на соревнованиях заняла каждая из девушек, если все они оказались на разных местах? Решение. Рассмотрим простые высказывания: \(C_1 = \)«Сима заняла первое место»; \(B_2 = \)«Валя заняла второе место»; \(C_2 = \)«Сима заняла второе место»; \(Д_3 = \)«Даша заняла третье место»; \(A_2 = \)«Алла заняла второе место»; \(Д_4 = \)«Даша заняла четвёртое место». Так как в каждом из трёх предположений одно из высказываний истинно, а другое ложно, то можно заключить следующее: