Алгебра логики — Информатика, 9 класс

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

Простыми словами

«Если пойдёт дождь, то я возьму зонт». Обещание нарушено только в одном случае: дождь пошёл, а зонта нет. Алгебра логики точно описывает, когда сложное утверждение истинно, если известна истинность его частей.

$A$	$B$	$\neg A$	$A \land B$	$A \lor B$	$A \to B$	$A \equiv B$
0	0	1	0	0	1	1
0	1	1	0	1	1	0
1	0	0	0	1	0	0
1	1	0	1	1	1	1

И ( $\land$ )1, когда оба равны 1

ИЛИ ( $\lor$ )0, когда оба равны 0

Импликация ( $\to$ )«если…, то…»: ложна ровно в одном случае —

1 \to 0

Эквиваленция ( $\equiv$ )1, когда значения одинаковы

скобки → $\neg$ → $\land$ → $\lor$ → $\to$ → $\equiv$

Значение выражения

$\neg (A \to C) \lor B$ при $A = 1$ , $B = 1$ , $C = 0$ .

Скобка: $1 \to 0 = 0$ .
НЕ: $\neg0 = 1$ .
ИЛИ: $1 \lor 1 = 1$ .

Для какого $X$ из чисел 75, 30, 12 истинно $\neg (X < 40) \land (X кратно 3)$ ?

$\neg (X < 40)$ значит $X \geq 40$ — подходит только 75.
75 кратно 3 ✓. Ответ: 75.

Отрицание меняет знак сравнения: $\neg (X < 40) \Leftrightarrow X \geq 40$ , а не $X > 40$ . Граничное число 40 тоже подходит.

Таблица истинности и подсчёт наборов

Для $n$ переменных — $2^{n}$ наборов: для трёх — 8. Наборы выписывают по порядку двоичных чисел от 000 до 111.

Сколько наборов $(A, B, C)$ , при которых $\neg C \lor (A \to B)$ истинно?

Удобнее найти, когда выражение ложно: ИЛИ ложно, если обе части ложны.
$\neg C = 0$ ⇒ $C = 1$ ; $A \to B = 0$ ⇒ $A = 1$ , $B = 0$ . Такой набор один.
Истинных наборов: $8 - 1 = 7$ .

Для И ищите, когда выражение истинно (все части равны 1), для ИЛИ и импликации — когда ложно. Так перебора почти нет.

$F = (x \to y) \land z$ ; выписаны все наборы с $F = 1$ , заголовки столбцов перепутаны.

$F = 1$ ⇒ $z = 1$ и $x \to y = 1$ : $(x, y) \in {(0, 0), (0, 1), (1, 1)}$ — три строки.
В столбце $z$ — все единицы; у $y$ — две единицы; у $x$ — одна.
Сравниваем с таблицей по числу единиц и находим, где какая переменная.

Подставьте каждую строку фрагмента во все варианты ответа и отбрасывайте те, где значение не совпало с $F$ . Оставшийся вариант — ответ.

Законы алгебры логики

Закон	Запись
де Моргана	$\neg (A \land B) = \neg A \lor \neg B$ ; $\neg (A \lor B) = \neg A \land \neg B$
замена импликации	$A \to B = \neg A \lor B$
двойного отрицания	$\neg\neg A = A$
поглощения	$A \land (A \lor B) = A$ ; $A \lor (A \land B) = A$
дистрибутивности	$A \land (B \lor C) = (A \land B) \lor (A \land C)$
противоречия и исключённого третьего	$A \land \neg A = 0$ ; $A \lor \neg A = 1$

Де Морган: «отрицание проходит внутрь скобки и переворачивает знак» — И становится ИЛИ, ИЛИ становится И.

Импликация не перестановочна: $A \to B \neq = B \to A$ . При $A = 1$ , $B = 0$ : $A \to B = 0$ , а $B \to A = 1$ .

Примеры заданий

Это несколько заданий из тренажёра, остальные — в тренажёре в начале страницы.

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

(A ∧ C) ∧ ¬B

A	B	C
1	1	1

Показать ответ

Ответ: 0
Решение. При A=1, B=1, C=1 выражение (A ∧ C) ∧ ¬B принимает значение 0.

Сколько существует наборов значений переменных A, B и C, при которых выражение истинно?

¬C ∨ (A → B)

A	B	C	F
0	0	0	?
0	0	1	?
0	1	0	?
0	1	1	?
1	0	0	?
1	0	1	?
1	1	0	?
1	1	1	?

Показать ответ

Ответ: 7
Решение. Истинно при наборах: (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,1,0), (1,1,1) — всего 7 из 8.

В таблице приведён фрагмент таблицы истинности некоторого логического выражения F. Какое из выражений соответствует этому фрагменту?

A	B	C	F
1	1	1	1
1	0	1	1
1	0	0	1
1	1	0	1

C ∨ (¬B ∧ A)
(A → B) ∨ C
(C → B) ∧ A
A ∨ (¬B ∧ C)

Показать ответ

Ответ: A ∨ (¬B ∧ C)
Решение. Только выражение A ∨ (¬B ∧ C) даёт указанные значения F во всех строках фрагмента.

Для какого из приведённых чисел X истинно высказывание?

(X < 10) И (X не кратно 6)

Показать ответ

Ответ: 7
Решение. Проверка: X=15 → ложь; X=30 → ложь; X=13 → ложь; X=7 → истина. Подходит только X = 7.

выражение ¬(A ∧ B) по закону де Моргана равносильно

A ∧ ¬B
A ∨ B
¬A ∧ ¬B
¬A ∨ ¬B

Показать ответ

Ответ: ¬A ∨ ¬B
Решение. Первый закон де Моргана: отрицание конъюнкции равно дизъюнкции отрицаний, ¬(A∧B) = ¬A ∨ ¬B.

выражение ¬(A ∨ B) по закону де Моргана равносильно

¬A ∨ B
¬A ∧ ¬B
A ∧ B
¬A ∨ ¬B

Показать ответ

Ответ: ¬A ∧ ¬B
Решение. Второй закон де Моргана: отрицание дизъюнкции равно конъюнкции отрицаний, ¬(A∨B) = ¬A ∧ ¬B.

импликация A → B равносильна выражению

A ∧ ¬B
¬A ∨ B
¬A ∧ B
A ∨ ¬B

Показать ответ

Ответ: ¬A ∨ B
Решение. Замена импликации: A → B = ¬A ∨ B. Это одно из главных тождеств алгебры логики.

Дан фрагмент таблицы истинности выражения F: выписаны все наборы, при которых F = 1, но заголовки столбцов переменных перепутаны. Какая переменная стоит в столбце «Перем. 1»?

(x → y) ∧ z

Перем. 1	Перем. 2	Перем. 3	F
1	0	0	1
1	0	1	1
1	1	1	1

Показать ответ

Ответ: z
Решение. Выражение (x → y) ∧ z истинно на наборах [(0, 0, 1), (0, 1, 1), (1, 1, 1)] (порядок переменных x, y, z). Сопоставление столбцов даёт: «Перем. 1» — это z.