Элементы алгебры логики — Информатика, 7 класс

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

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

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

Высказывание — утверждение, о котором можно сказать, истинно оно или ложно. Истину обозначают $1$ , ложь — $0$ . Переменные $A$ , $B$ , $C$ — это высказывания, которые принимают значения $0$ или $1$ .

«Москва — столица России» — истинное высказывание ( $1$ ); « $2 + 2 = 5$ » — ложное ( $0$ ); «Который час?» — не высказывание.

Три основные операции

НЕ (инверсия), $\neg A$ Меняет значение на противоположное:

\neg0 = 1

\neg1 = 0

И (конъюнкция), $A \land B$ Равно

1

, только когда оба равны

1

. Похоже на умножение:

A \cdot B

ИЛИ (дизъюнкция), $A \lor B$ Равно

0

, только когда оба равны

0

. Хотя бы одна единица — уже

1

$A$	$B$	$\neg A$	$A \land B$ (И)	$A \lor B$ (ИЛИ)
0	0	1	0	0
0	1	1	0	1
1	0	0	0	1
1	1	0	1	1

Ключ замкнут —

1

, лампа горит —

1

Как вычислить выражение

1) скобки; 2) $\neg$ (НЕ); 3) $\land$ (И); 4) $\lor$ (ИЛИ). Так же, как в арифметике умножение раньше сложения: И — «умножение», ИЛИ — «сложение».

Найти $A \lor \neg B$ при $A = 0$ , $B = 1$ .

Подставим: $0 \lor \neg1$ .
Сначала НЕ: $\neg1 = 0$ .
Затем ИЛИ: $0 \lor 0 = 0$ . Ответ: $0$ .

Найти $A \lor (\neg B \land C)$ при $A = 0$ , $B = 1$ , $C = 1$ .

Скобка: $\neg B = \neg1 = 0$ , затем $0 \land 1 = 0$ .
Остаётся $A \lor 0 = 0 \lor 0 = 0$ . Ответ: $0$ .

$\neg A \land B$ — это $(\neg A) \land B$ , а не $\neg (A \land B)$ . НЕ относится только к ближайшей переменной (или к скобке сразу за ним). При $A = 1$ , $B = 1$ : $\neg A \land B = 0 \land 1 = 0$ .

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

Законы позволяют упрощать выражения. Каждый проверяется подстановкой $A = 0$ и $A = 1$ .

Закон	Для И	Для ИЛИ
с константой	$A \land 1 = A$ , $A \land 0 = 0$	$A \lor 0 = A$ , $A \lor 1 = 1$
повторения	$A \land A = A$	$A \lor A = A$
противоречия / исключённого третьего	$A \land \neg A = 0$	$A \lor \neg A = 1$
двойного отрицания	$\neg\neg A = A$
переместительный	$A \land B = B \land A$	$A \lor B = B \lor A$
де Моргана	$\neg (A \land B) = \neg A \lor \neg B$	$\neg (A \lor B) = \neg A \land \neg B$

$A \land \neg A$ : высказывание и его отрицание не могут быть истинны одновременно, поэтому выражение всегда равно $0$ . А $A \lor 0$ равно самому $A$ : «ноль» в ИЛИ ничего не меняет.

Сравнивайте с числами: $A \cdot 1 = A$ , $A \cdot 0 = 0$ , $A + 0 = A$ . Отличие одно: в логике $1 \lor 1 = 1$ , а не $2$ .

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

A \land (A \lor B) = A, A \lor (A \land B) = A

законы поглощения

Проверка подстановкой: если $A = 1$ , то $A \lor B = 1$ и $1 \land 1 = 1 = A$ ; если $A = 0$ , то $0 \land (\dots) = 0 = A$ . Второй закон проверяется так же: при $A = 1$ получаем $1$ , при $A = 0$ — $0 \lor 0 = 0$ .

Ещё равносильности из заданий: $A \land 0 = 0$ , $A \lor 0 = A$ , $A \land A = A$ , $A \lor B = B \lor A$ , $\neg\neg A = A$ .

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

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

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

A ∨ ¬B, при A=0, B=1

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

Ответ: 0
Решение. ¬B = 0; 0 ∨ 0 = 0.

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

A ∨ (¬B ∧ C), при A=0, B=1, C=1

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

Ответ: 0
Решение. ¬B = 0; ¬B∧C = 0∧1 = 0; результат: 0 ∨ 0 = 0.

A ∨ 0 равносильно

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

Ответ: A
Решение. Свойство константы: A∨0 = A.

A ∧ ¬A равносильно

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

Ответ: 0
Решение. Закон противоречия: A∧¬A всегда ложно (0).

A ∧ 0 равносильно

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

Ответ: 0
Решение. Свойство константы: A∧0 = 0.

A ∨ (A ∧ B) равносильно

B
A ∧ B
A
1

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

Ответ: A
Решение. Закон поглощения: A ∨ (A ∧ B) = A.

¬(A ∨ B) равносильно

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

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

Ответ: ¬A ∧ ¬B
Решение. Закон де Моргана: отрицание дизъюнкции равно конъюнкции отрицаний.

A ∧ A равносильно

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

Ответ: A
Решение. Закон идемпотентности: A∧A = A.