1. Основные понятия
- Нормальная форма — стандартная запись логических выражений
- Литерал — переменная (A) или её отрицание (¬A)
- Конъюнкция — соединение через И (A ∧ ¬B ∧ C)
- Дизъюнкция — соединение через ИЛИ (A ∨ ¬B ∨ C)
2. Совершенная дизъюнктивная форма (СДНФ)
Алгоритм построения:
- Выбрать строки таблицы истинности, где f=1
- Для каждой строки создать конъюнкцию:
- Если переменная=1 → A
- Если переменная=0 → ¬A
- Объединить все конъюнкции через ∨
Пример для A → B:
| A | B | f | Конъюнкция |
|---|---|---|---|
| 0 | 0 | 1 | ¬A ∧ ¬B |
| 0 | 1 | 1 | ¬A ∧ B |
| 1 | 0 | 0 | — |
| 1 | 1 | 1 | A ∧ B |
СДНФ: (¬A ∧ ¬B) ∨ (¬A ∧ B) ∨ (A ∧ B)
3. Совершенная конъюнктивная форма (СКНФ)
Алгоритм построения:
- Выбрать строки таблицы истинности, где f=0
- Для каждой строки создать дизъюнкцию:
- Если переменная=1 → ¬A
- Если переменная=0 → A
- Объединить все дизъюнкции через ∧
Пример для A → B:
| A | B | f | Дизъюнкция |
|---|---|---|---|
| 0 | 0 | 1 | — |
| 0 | 1 | 1 | — |
| 1 | 0 | 0 | ¬A ∨ B |
| 1 | 1 | 1 | — |
СКНФ: ¬A ∨ B
4. Визуализация алгоритмов
Схема построения СДНФ:
graph TD
A[Таблица истинности] --> B{Выбрать строки f=1}
B --> C[Для каждой строки]
C --> D[Создать конъюнкцию]
D --> E[Объединить через ИЛИ]
E --> F[СДНФ]
Схема построения СКНФ:
graph TD
A[Таблица истинности] --> B{Выбрать строки f=0}
B --> C[Для каждой строки]
C --> D[Создать дизъюнкцию]
D --> E[Объединить через И]
E --> F[СКНФ]
5. Пример с тремя переменными
Функция: f(A,B,C) = A ∨ (B ∧ C)
Фрагмент таблицы истинности:
| A | B | C | f | Конъюнкция (СДНФ) | Дизъюнкция (СКНФ) |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | — | A∨B∨C |
| 0 | 0 | 1 | 0 | — | A∨B∨¬C |
| 0 | 1 | 0 | 0 | — | A∨¬B∨C |
| 0 | 1 | 1 | 1 | ¬A ∧ B ∧ C | — |
| 1 | 0 | 0 | 1 | A ∧ ¬B ∧ ¬C | — |
СДНФ: (¬A ∧ B ∧ C) ∨ (A ∧ ¬B ∧ ¬C) ∨ …
СКНФ: (A∨B∨C) ∧ (A∨B∨¬C) ∧ (A∨¬B∨C) ∧ …
6. Особенности и применение
| Параметр | СДНФ | СКНФ |
|---|---|---|
| Когда использовать | Много 0 в таблице | Много 1 в таблице |
| Сложность | Высокая при многих 1 | Высокая при многих 0 |
| Применение | Минимизация схем | Проверка выполнимости |
| Пример | ¬A ∧ B ∨ A ∧ ¬B | (A∨B) ∧ (¬A∨¬B) |