Высказывания и логические операции
Высказывание — утверждение, про которое можно сказать, истинно оно (1) или ложно (0). Из простых высказываний операции строят сложные.
| Операция | Обозначение | Python | Истинна, когда |
|---|---|---|---|
| Отрицание (НЕ) | ¬A | not A | A ложно |
| Конъюнкция (И) | A ∧ B | A and B | оба истинны |
| Дизъюнкция (ИЛИ) | A ∨ B | A or B | хотя бы одно истинно |
| Импликация | A → B | A <= B | всегда, кроме 1 → 0 |
| Эквивалентность | A ≡ B | A == B | значения совпадают |
Импликация: A → B = ¬A ∨ B. Законы де Моргана: ¬(A ∧ B) = ¬A ∨ ¬B; ¬(A ∨ B) = ¬A ∧ ¬B.
Таблицы истинности
Таблица истинности перечисляет все наборы значений переменных. Для $n$ переменных наборов $2^n$: для двух — 4, для трёх — 8, для четырёх — 16.
Пример. Таблица для F = A → B:
| A | B | F |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Постройте таблицу для любой формулы в тренажёре:
Интерактив «Таблицы истинности» — открыть в тренажёре →
Проверь себя. Сколько строк в таблице истинности функции от 5 переменных?
Ответ: 32
ОГЭ-3: при каком x высказывание истинно
В задании 3 ОГЭ нужно найти наибольшее или наименьшее число (или имя, слово), при котором составное высказывание истинно или ложно.
Пример. Найдите наименьшее натуральное x, для которого истинно: НЕ (x < 5) И (x нечётное).
НЕ (x < 5) означает x ≥ 5. Наименьшее нечётное число, не меньшее 5, — это 5.
ЕГЭ-2: фрагмент таблицы истинности
Дана функция F от x, y, z, w и фрагмент её таблицы, где столбцы переменных перепутаны, а часть клеток пуста. Нужно понять, какой переменной соответствует каждый столбец.
from itertools import product, permutations
def F(x, y, z, w):
return (x or y) <= (z == w)
for a in product([0, 1], repeat=5): # 5 пустых клеток
t = [(1, a[0], 0, a[1]), (a[2], 1, a[3], 0), (1, 1, a[4], 1)]
if len(set(t)) == len(t): # строки должны быть различны
for p in permutations('xyzw'):
if all(F(**dict(zip(p, r))) == 0 for r in t):
print(''.join(p))ЕГЭ-15: ДЕЛ, отрезки и поразрядные операции
В задании 15 формула содержит параметр A, и нужно найти A, при котором формула тождественно истинна (истинна при любом x). Встречаются три вида:
- ДЕЛ(n, m) — «n делится на m без остатка» — в Python n % m == 0;
- отрезки на числовой прямой: x ∈ P — в Python P[0] <= x <= P[1];
- поразрядная конъюнкция m & n — в Python тот же оператор &.
Пример. Для какого наименьшего натурального A формула (ДЕЛ(x, A) ∧ ДЕЛ(x, 36)) → ДЕЛ(x, 24) тождественно истинна?
def ok(A):
for x in range(1, 10000):
if not ((x % A == 0 and x % 36 == 0) <= (x % 24 == 0)):
return False
return True
print(min(A for A in range(1, 1000) if ok(A))) # 8Логика: число, кратное и A, и 36, должно делиться на 24 = 8·3. В 36 = 4·9 тройка есть, а двойка входит только во второй степени — недостающую восьмёрку должен дать A. Ответ 8.
Проверь себя. При каком наибольшем натуральном A формула ДЕЛ(x, 12) → ДЕЛ(x, A) тождественно истинна?
Ответ: 12