Основы логики · Блок 3§8
SilverTests.ru · Подготовка к ИТМОТеория + паттерны + задания
Основы логики
Операции, законы, упрощение, подсчёт решений, побитовые операции
1Операции и таблицы истинности
| A |
B |
¬A |
A∧B |
A∨B |
A⊕B |
A→B |
A↔B |
| 0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
| 0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
| 1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
| 1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
Мнемоники
запоминалки∧ (AND) — 1 только когда оба = 1 // «строгий» ∨ (OR) — 0 только когда оба = 0 // «добрый» ⊕ (XOR) — 1 когда различаются // «отличник» → (IMP) — 0 только при 1→0 // «из истины ложь не следует» ↔ (EQV) — 1 когда совпадают // «одинаковые»
Приоритет операций (от высшего к низшему): ¬ → ∧ → ∨ → ⊕ → → → ↔.
На ИТМО скобки обычно расставлены явно, но если нет — считайте НЕ первым, И вторым, ИЛИ третьим.
Полезные эквивалентности
формулыA → B ≡ ¬A ∨ B A ↔ B ≡ (A→B) ∧ (B→A) ≡ (A∧B) ∨ (¬A∧¬B) A ⊕ B ≡ ¬(A↔B) ≡ (A∧¬B) ∨ (¬A∧B)
2Законы булевой алгебры
| Закон |
Формула |
| Де Моргана |
¬(A∧B) = ¬A∨¬B ¬(A∨B) = ¬A∧¬B |
| Дистрибутивность |
A∧(B∨C) = A∧B ∨ A∧C A∨(B∧C) = (A∨B)∧(A∨C) |
| Поглощение |
A ∨ A∧B = A A∧(A∨B) = A |
| Склеивание |
A∧B ∨ A∧¬B = A |
| Идемпотентность |
A∧A = A A∨A = A |
| Константы |
A∧0=0, A∧1=A, A∨0=A, A∨1=1 |
| Дополнение |
A∧¬A=0 A∨¬A=1 |
| Двойное отрицание |
¬¬A = A |
Самые ходовые на ИТМО: Де Моргана, склеивание, поглощение. Остальные — для полноты.
3Упрощение выражений
пример// Упростить: ¬(A∨B) ∨ A 1. Де Моргана: ¬(A∨B) = ¬A ∧ ¬B 2. Подставим: (¬A ∧ ¬B) ∨ A 3. Дистрибутивность: (¬A ∨ A) ∧ (¬B ∨ A) 4. Дополнение: 1 ∧ (A ∨ ¬B) 5. Константа: A ∨ ¬B // Проверка таблицей: // A=0,B=0: ¬(0)∨0 = 1∨0 = 1. A∨¬B = 0∨1 = 1 ✓ // A=0,B=1: ¬(1)∨0 = 0∨0 = 0. A∨¬B = 0∨0 = 0 ✓ // A=1,B=0: ¬(1)∨1 = 0∨1 = 1. A∨¬B = 1∨1 = 1 ✓ // A=1,B=1: ¬(1)∨1 = 0∨1 = 1. A∨¬B = 1∨0 = 1 ✓
На ИТМО упрощение — не самоцель, а инструмент. Чаще нужно анализировать выражение для подсчёта решений или понимания логического преобразователя.
4Подсчёт решений
Типичная задача ИТМО: сколько наборов переменных делают выражение истинным?
Метод 1: полная таблица (для n ≤ 5)
пример// (x&sub1;→x&sub2;) ∧ (x&sub2;→x&sub3;) = 1. Сколько решений? // x&sub1;→x&sub2; ложно только при x&sub1;=1, x&sub2;=0 // x&sub2;→x&sub3; ложно только при x&sub2;=1, x&sub3;=0 // Обе должны быть 1. x&sub1;=0: x&sub1;→x&sub2;=1 всегда. Нужно x&sub2;→x&sub3;=1: x&sub2;=0: x&sub3; любое → 2 решения x&sub2;=1: x&sub3;=1 → 1 решение x&sub1;=1: нужно x&sub2;=1. Тогда x&sub3;=1. → 1 решение Итого: 2 + 1 + 1 = 4 решения
Метод 2: цепочка импликаций (для длинных цепей)
паттерн// (x&sub1;→x&sub2;) ∧ (x&sub2;→x&sub3;) ∧ ... ∧ (xₙ&sub1;→xₙ) = 1 // Это значит: в цепочке x&sub1;,x&sub2;,...,xₙ // после первой единицы не может быть нуля. // Допустимые наборы: 000...0, 000...01, 000...011, ..., 111...1 // Количество: n + 1
Ключевое наблюдение: импликация x⊂i → x⊂i+1 запрещает «падение» 1→0. Допустимы только монотонные последовательности: сначала нули, потом единицы. Таких — ровно n+1 (переключение может произойти перед любой позицией, включая «нигде»).
5Побитовые операции на числах
На ИТМО задача 3 часто работает с числами, переведёнными в двоичную запись, к которым применяются побитовые операции.
пример// 13 AND 6 = ? 13 = 1101 6 = 0110 AND = 0100 = 4 // 13 OR 6 = ? OR = 1111 = 15 // 13 XOR 6 = ? XOR = 1011 = 11 // NOT 13 (в 8-битной арифметике) = ? NOT 00001101 = 11110010 = 242
Побитовые свойства
| Свойство |
Формула |
| Обнуление битов (маска) |
x AND mask — оставляет только биты, где mask=1 |
| Установка битов |
x OR mask — ставит 1 там, где mask=1 |
| Переключение |
x XOR mask — инвертирует биты, где mask=1 |
| Самоуничтожение XOR |
x XOR x = 0 x XOR 0 = x |
| Проверка чётности |
x AND 1 = 0 ⇒ x чётное |
На финале ИТМО 2022 задача «Много чисел» требовала разбить hex-число на тетрады, применить к каждой тетраде логическую функцию и собрать результат. Без навыка побитовых операций — не решить.
6Чек-лист
| № |
Что помнить |
| 1 |
Импликация A→B = 0 только при A=1, B=0 |
| 2 |
Де Моргана: «НЕ И» = «ИЛИ НЕ», «НЕ ИЛИ» = «И НЕ» |
| 3 |
Цепочка импликаций (x&sub1;→x&sub2;→...→xₙ) = 1 ⇒ n+1 решение |
| 4 |
XOR: самоуничтожение x⊕x=0, нейтральный элемент x⊕0=x |
| 5 |
Маски AND/OR/XOR — основа побитовых манипуляций |
| 6 |
Для n≤5 переменных — таблица истинности (2ⁿ строк); для n>5 — аналитический подход |
Проверь себя8 заданий