Логика и логические выражения
Логические операции, таблицы истинности и отрезки
Операции
| Название | Запись | Когда истинно |
|---|---|---|
| Отрицание | ¬A | A ложно |
| Конъюнкция («и») | A ∧ B | оба истинны |
| Дизъюнкция («или») | A ∨ B | хотя бы одно истинно |
| Импликация | A → B | ложна только при A = 1, B = 0 |
| Эквивалентность | A ≡ B | A и B равны |
| Исключающее «или» | A ⊕ B | A и B различны |
Таблица истинности импликации:
| A | B | A → B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Приоритет операций: ¬, затем ∧, затем ∨, затем →, затем ≡. Для надёжности расставляйте скобки.
Законы, которые нужны чаще всего
- Импликация через «или»:
A → B = ¬A ∨ B. - Законы де Моргана:
¬(A ∧ B) = ¬A ∨ ¬Bи¬(A ∨ B) = ¬A ∧ ¬B. - Эквивалентность:
A ≡ B = (A ∧ B) ∨ (¬A ∧ ¬B). - Поглощение:
A ∨ (A ∧ B) = AиA ∧ (A ∨ B) = A. - Двойное отрицание:
¬¬A = A.
Задача № 2: перебор таблицы истинности
Когда в условии даны фрагмент таблицы истинности и формула, надёжнее всего написать перебор.
from itertools import product
print('x y z w')
for x, y, z, w in product([0, 1], repeat=4):
F = ((x <= y) and (not z)) or w # импликация x → y записывается как x <= y
if F == 0: # условие из задачи
print(x, y, z, w)Для чисел 0 и 1 выражение x <= y совпадает с импликацией x → y. Это самый короткий способ записать её в Python.
Так как столбцы в условии обычно перемешаны, проверяйте все перестановки имён переменных: используйте itertools.permutations('xyzw') и сверяйте найденные строки с фрагментом.
Задача № 15: высказывания про отрезки и множества
Пусть P, Q — отрезки на числовой прямой, а A — искомый отрезок. Высказывание «x ∈ A» истинно, когда x лежит на отрезке A. Формула должна быть тождественно истинной, то есть истинной при любом x.
Ключевая идея: импликация X → Y ложна, только если X истинно, а Y ложно. Значит, чтобы формула всегда была истинной, такой ситуации не должно быть.
Пример 1. Формула (x ∈ A) → ((x ∈ P) ∨ (x ∈ Q)) тождественно истинна, где P = [10, 30], Q = [20, 50]. Если x ∈ A, то x обязан попасть в P или в Q. Значит, A целиком лежит в объединении P ∪ Q = [10, 50]. Наибольшая длина A: 50 − 10 = 40.
Пример 2. Формула (x ∈ P) → ((x ∈ Q) → (x ∈ A)) тождественно истинна, P = [10, 30], Q = [20, 50]. Преобразуем: ¬P ∨ ¬Q ∨ A. Формула может быть ложной только там, где P и Q истинны, а A ложно. Значит, A обязан покрывать пересечение P ∩ Q = [20, 30]. Наименьшая длина A: 30 − 20 = 10.
Для условий про делимость (например, «x делится на A») работает тот же приём: определите, какие значения x нельзя оставлять без покрытия, и подберите A по ним. Перебор по x на Python в этом случае тоже работает:
def check(A):
return all(((x % 6 == 0) <= (x % A == 0)) for x in range(1, 1000))
print([A for A in range(1, 100) if check(A)])Типичные ошибки
- Читают импликацию как «и»:
A → Bложна только в одной строке таблицы. - Не раскрывают отрицание перед конъюнкцией и дизъюнкцией: ошибаются в законах де Моргана.
- Считают длину отрезка включительно: для отрезка [a, b] длина равна b − a, а не b − a + 1. Для количества целых точек — наоборот, их b − a + 1.