Облако знаний. Логические функции. Полные системы логических функций. Информатика. 10 класс

Логические функции – это функции, аргументы и значения которых принимают значения из множества {0, 1}. Каждая такая функция описывает зависимость между двоичными переменными.
Количество возможных логических функций от n аргументов составляет 2²ⁿ. Эта формула показывает экспоненциальный рост разнообразия функций с увеличением числа аргументов:
- при n = 0: 2¹ = 2 функции (константы 0 и 1);
- при n = 1: 2² = 4 функции;
- при n = 2: 2⁴ = 16 функций;
- при n = 3: 2⁸ = 256 функций.
Стремительный рост количества логических функций показывает, что изучать их по отдельности практически невозможно. Однако эту проблему решает концепция полных систем – наборов из нескольких базовых функций, через которые можно выразить любую логическую функцию.
Основные полные системы:
1. {И, ИЛИ, НЕ} – классическая система булевых операций;
2. {И, НЕ} – конъюнкция с отрицанием;
3. {ИЛИ, НЕ} – дизъюнкция с отрицанием;
4. {И–НЕ} (штрих Шеффера) – одна функция, достаточная для построения любой другой;
5. {ИЛИ–НЕ} (стрелка Пирса) – также образует полную систему.
Полные системы логических функций находят практическое применение через нормальные формы – стандартизированные способы записи логических выражений. На основе полной системы {И, ИЛИ, НЕ} строятся две основные нормальные формы:
- дизъюнктивная нормальная форма (ДНФ) – это дизъюнкция конъюнкций. Например: (A ∧ ¬B) ∨ (¬A ∧ C) ∨ (B ∧ C);
- конъюнктивная нормальная форма (КНФ) – это конъюнкция дизъюнкций. Например: (A ∨ ¬B) ∧ (¬A ∨ C) ∧ (B ∨ C).