1. Основные понятия
Высказывание — утверждение, которое истинно (1) или ложно (0).
Предикат — утверждение с переменными.
Кванторы:
| Квантор | Обозначение | Пример | Значение |
|---|---|---|---|
| Всеобщности | ∀ | ∀x (x > 0) | 0 (не все x положительны) |
| Существования | ∃ | ∃x (x < 0) | 1 (существует x<0) |
2. Логические операции
Таблица базовых операций:
| Операция | Обозначение | Таблица истинности |
|---|---|---|
| НЕ (NOT) | ¬A | A: 0→1, 1→0 |
| И (AND) | A ∧ B | 00→0, 01→0, 10→0, 11→1 |
| ИЛИ (OR) | A ∨ B | 00→0, 01→1, 10→1, 11→1 |
| Искл. ИЛИ (XOR) | A ⊕ B | 00→0, 01→1, 10→1, 11→0 |
| Импликация | A → B | 00→1, 01→1, 10→0, 11→1 |
| Эквивалентность | A ↔ B | 00→1, 01→0, 10→0, 11→1 |
Схема импликации:
graph LR A[0] --> B[0] --> C[1] A --> D[1] --> E[1]
3. Законы алгебры логики
Основные тождества:
| Закон | Формула |
|---|---|
| Коммутативный | A ∧ B = B ∧ A; A ∨ B = B ∨ A |
| Ассоциативный | (A∧B)∧C = A∧(B∧C) |
| Дистрибутивный | A ∧ (B ∨ C) = (A∧B) ∨ (A∧C) |
| Де Моргана | ¬(A ∧ B) = ¬A ∨ ¬B |
| Двойного отрицания | ¬(¬A) = A |
Связь с множествами:
graph TD A[Логика] -->|¬A| B[Дополнение] A -->|A ∧ B| C[Пересечение] A -->|A ∨ B| D[Объединение]
4. Логические выражения
Порядок операций: Скобки → НЕ → И → ИЛИ → →, ↔
Пример упрощения:
Упростить: ¬(A ∨ B) ∧ ¬A
- ¬(A ∨ B) = ¬A ∧ ¬B (де Морган)
- (¬A ∧ ¬B) ∧ ¬A = ¬A ∧ ¬B (идемпотентность)
5. Логические уравнения
Методы решения:
- Табличный (построить таблицу истинности)
- Аналитический (упростить выражение)
- Перебор значений
Пример: A → B = 0
Решение: A=1, B=0
6. Логические функции
Количество функций: Для n переменных → \( 2^{2^n} \) функций
Примеры:
| n | Количество | Примеры |
|---|---|---|
| 0 | 2 | 0, 1 |
| 1 | 4 | ¬A, A, 0, 1 |
| 2 | 16 | AND, OR, XOR |
7. Канонические формы
СДНФ (Совершенная ДНФ):
Дизъюнкция минтермов (для f=1)
Пример f(A,B) = A ⊕ B: (¬A ∧ B) ∨ (A ∧ ¬B)
СКНФ (Совершенная КНФ):
Конъюнкция макстермов (для f=0)
Пример f(A,B) = A ⊕ B: (A ∨ B) ∧ (¬A ∨ ¬B)
Алгоритм построения:
graph TD
A[Таблица истинности] --> B{Значение f}
B -->|1| C[Минтерм для СДНФ]
B -->|0| D[Макстерм для СКНФ]
C --> E[Объединить через ∨]
D --> F[Объединить через ∧]