Основы логики и логические операции
Алгебра логики: высказывания, операции НЕ, И, ИЛИ, исключающее ИЛИ. Законы де Моргана. Построение таблиц истинности.
Основы логики и логические операции
1. Алгебра логики
Алгебра логики (булева алгебра) — раздел математики, изучающий высказывания и логические операции над ними. Названа в честь Джорджа Буля (1815–1864).
Высказывание — это повествовательное предложение, про которое можно однозначно сказать, истинно оно или ложно. Например:
- «Москва — столица России» — истинное высказывание (1, True).
- «2 + 2 = 5» — ложное высказывание (0, False).
- «Который час?» — не высказывание (вопрос).
- «x > 5» — не высказывание (зависит от x).
2. Базовые логические операции
Отрицание (НЕ, NOT, ¬)
Инверсия — унарная операция, меняющая значение высказывания на противоположное.
| A | ¬A |
|---|---|
| 0 | 1 |
| 1 | 0 |
В Python: not A
Конъюнкция (И, AND, ∧)
Логическое умножение — бинарная операция, истинная только когда оба операнда истинны.
| A | B | A ∧ B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
В Python: A and B
Дизъюнкция (ИЛИ, OR, ∨)
Логическое сложение — бинарная операция, ложная только когда оба операнда ложны.
| A | B | A ∨ B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
В Python: A or B
Исключающее ИЛИ (XOR, ⊕)
Истинно, когда значения операндов различны. Сложение по модулю 2.
| A | B | A ⊕ B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
В Python: A != B или A ^ B (побитовое)
3. Законы алгебры логики
Законы де Моргана
¬(A ∧ B) = ¬A ∨ ¬B
¬(A ∨ B) = ¬A ∧ ¬B
Словами: отрицание конъюнкции равно дизъюнкции отрицаний; отрицание дизъюнкции равно конъюнкции отрицаний.
Другие важные законы
| Закон | Формула |
|---|---|
| Коммутативности | A ∧ B = B ∧ A; A ∨ B = B ∨ A |
| Ассоциативности | (A ∧ B) ∧ C = A ∧ (B ∧ C) |
| Дистрибутивности | A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C) |
| Двойного отрицания | ¬(¬A) = A |
| Исключённого третьего | A ∨ ¬A = 1 |
| Противоречия | A ∧ ¬A = 0 |
| Идемпотентности | A ∧ A = A; A ∨ A = A |
| Поглощения | A ∨ (A ∧ B) = A |
4. Импликация и эквивалентность
Импликация (если...то, →)
| A | B | A → B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Импликация ложна только когда из истины следует ложь. Эквивалентные формулы: A → B = ¬A ∨ B.
Эквивалентность (тогда и только тогда, ↔, ≡)
| A | B | A ↔ B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Истинна когда оба операнда совпадают. A ↔ B = (A → B) ∧ (B → A).
5. Логические элементы компьютера
Базовые логические операции реализованы аппаратно с помощью логических вентилей (гейтов). Каждый вентиль — микроэлектронная схема на транзисторах:
- Инвертор (NOT) — один вход, выход — инверсия входа
- Конъюнктор (AND) — выход 1 только при всех входах 1
- Дизъюнктор (OR) — выход 1 при любом входе 1
Комбинации вентилей образуют более сложные схемы: сумматоры, триггеры, регистры — основу процессора.
Примеры вопросов из тренажёра
-
Q: Какое высказывание является истинным для операции И (AND)?
A: верный ответ — Только 1 И 1 = 1
Объяснение: Конъюнкция (И) истинна только когда оба операнда истинны: 1∧1 = 1, во всех остальных случаях 0.
-
Q: Какое высказывание является истинным для операции ИЛИ (OR)?
A: верный ответ — Ложна только когда оба операнда ложны
Объяснение: Дизъюнкция (ИЛИ) ложна только при 0∨0 = 0. Во всех остальных случаях — истина.
-
Q: Когда выражение A ⊕ B (исключающее ИЛИ, XOR) истинно?
A: верный ответ — Когда значения A и B различны
Объяснение: XOR = 1 когда операнды разные: 0⊕1=1, 1⊕0=1. Когда одинаковые: 0⊕0=0, 1⊕1=0.
-
Q: Что гласит закон де Моргана для конъюнкции?
A: верный ответ — ¬(A ∧ B) = ¬A ∨ ¬B
Объяснение: Отрицание конъюнкции равно дизъюнкции отрицаний: ¬(A∧B) = ¬A∨¬B. «Не (A и B)» = «Не A или не B».
-
Q: Что такое высказывание в алгебре логики?
A: верный ответ — Предложение с однозначным значением истинности
Объяснение: Высказывание — повествовательное предложение, о котором можно однозначно сказать: истинно оно или ложно.