Элементы математической логики — Информатика, 10 класс

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

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

Высказывание — утверждение, про которое можно сказать «истинно» (1) или «ложно» (0). «Идёт дождь» и «есть зонт» — высказывания; «идёт дождь и нет зонта» — сложное высказывание, и его истинность вычисляется по правилам, как пример по арифметике.

Конъюнкция — общая часть, дизъюнкция — всё, что внутри хотя бы одного круга

Логические операции

$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

$\neg$ инверсия, «не»меняет значение на противоположное

$\land$ конъюнкция, «и»1, только если оба 1

$\lor$ дизъюнкция, «или»0, только если оба 0

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

A = 1

B = 0

$\equiv$ эквивалентностьистинна, когда значения совпадают

Сначала скобки, затем $\neg$ , затем $\land$ , затем $\lor$ , последними — $\to$ и $\equiv$ .

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

$B \to A = 1 \to 0 = 0$ .
$\neg0 = 1$ .
$1 \land C = 1 \land 1 = 1$ .

Таблица истинности

Для $n$ переменных в таблице $2^{n}$ строк: для двух — 4, для трёх — 8, для четырёх — 16. Наборы выписывают в порядке возрастания двоичной записи: 000, 001, 010, 011, 100, 101, 110, 111.

$B \to (C \lor \neg A)$ .

Импликация ложна только при $B = 1$ и $C \lor \neg A = 0$ .
$C \lor \neg A = 0$ лишь при $C = 0$ , $A = 1$ . Итак, ложный набор один: $A = 1, B = 1, C = 0$ .
Истинных наборов $8 - 1 = 7$ .

Часто проще посчитать, когда выражение ложно (для $\to$ и $\lor$ ) или истинно (для $\land$ ), и вычесть из $2^{n}$ .

Стёртую ячейку не угадывают, а вычисляют: берут из её строки значения переменных и подставляют в выражение. Для $(B \lor C) \to A$ при $A = 1$ ответ сразу 1: импликация с истинным следствием истинна.

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

Закон	Запись
де Моргана	$\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$
поглощение	$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$
двойное отрицание	$\neg\neg A = A$

При отрицании скобки знак меняется: $\neg (A \land B)$ — это не $\neg A \land \neg B$ , а $\neg A \lor \neg B$ .

Посмотреть и посчитать

Модели

События и множества: круги Эйлера

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

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

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

¬(B → A) ∧ C

A	B	C
0	1	1

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

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

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

B → (C ∨ ¬A)

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, 0, 1), (1, 1, 1) — всего 7 из 8.

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

(B ∨ C) → A

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

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

Ответ: 1
Решение. В стёртой строке A = 1, B = 0, C = 1; выражение (B ∨ C) → A на этом наборе равно 1.