§ 8. Совершенные конъюнктивные и дизъюнктивные нормальные формы формул алгебры высказываний.
Определение 1, 2. Дизъюнктивный (конъюнктивный) одночлен от n переменных высказываний x1, x2, ..., xn называется совершенным, если каждая переменная входит в него ровно один раз: либо сама, либо своим отрицанием.
Из этих определений следует, что совершенный одночлен от n переменных высказываний состоит точно из n членов.
Примеры.
1) СКО от двух переменных:
2) CДО от трех переменных: , .
Определение 3. Совершенной дизъюнктивной нормальной формой формулы алгебры высказываний называется такая ДН форма этой формулы, в которой каждый ее конъюнктивный одночлен является совершенным.
Пример. СДНФ формулы от двух переменных .
Определение 4. Совершенной конъюнктивной нормальной формой формулы алгебры высказываний называется такая КН форма этой формулы, в которой каждый ее ДО является совершенным.
Пример. СКНФ формулы от трех переменных .
Из этих определений и доказанных выше теорем вытекают следующие принципиально важные следствия.
Следствия 1, 2. Для всякой формулы алгебры высказываний, не являющейся ТИ (ТЛ) существует равносильная ей СКН форма (СДН форма) и притом единственная.
Из всего выше изложенного вытекает следующий алгоритм приведения формул алгебры высказываний к совершенным нормальным формам.
1. Приводим данную формулу F алгебры высказываний к равносильной ей формуле F1 относительно первых трех логических операций.
2. Приводим полученную формулу F1 к равносильной ей нормальной форме: конъюнктивной или дизъюнктивной.
3. Если в полученной нормальной форме имеются одинаковые одночлены, то из них оставляют только один, остальные отбрасывают.
4. Если в одночлене нормальной формы имеются одинаковые переменных xk, то из них оставляют только одну, остальные отбрасывают.
5. Если в полученной нормальной форме имеется одночлен, содержащий переменную xi с ее отрицанием , то все такие одночлены отбрасывают.
6. Если какой-либо одночлен Fj от n переменных не содержит некоторой переменной xi, то он заменяется двумя одночленами вида для случая ДН форм и двумя одночленами вида для случая КН форм.
- Пособие по дисциплине
- Пособие по дисциплине
- Оглавление
- Глава I. Алгебра высказываний.
- Предисловие
- Введение
- Глава I. Алгебра высказываний.
- § 1. Высказывания и логические операции над ними.
- § 2. Формулы алгебры высказываний и их истинностное значение.
- § 3. Основные виды формул алгебры высказываний. Законы формул алгебры высказываний.
- § 4. Равносильность формул алгебры высказываний и ее свойства.
- § 5. Основные равносильности формул алгебры высказываний.
- § 6. Конъюнктивные и дизъюнктивные нормальные формы формул алгебры высказываний.
- § 7. Проблема установления вида формул алгебры высказываний.
- § 8. Совершенные конъюнктивные и дизъюнктивные нормальные формы формул алгебры высказываний.
- § 9. Применение алгебры высказываний к анализу и синтезу электрических схем.
- Алгоритм упрощения электрических схем
- § 10. Приложение алгебры высказываний к вопросам школьной математики.
- Глава II. Алгебра предикатов
- § 1. Определение n-местного предиката и его основных видов.
- § 2. Логические операции над предикатами и их свойства.
- § 3. Связанные и свободные переменные. Свойства операций навешивания кванторов.
- § 4. Формулы алгебры предикатов и их основные виды.
- § 5. Равносильность формул алгебры предикатов. Основные равносильности алгебры предикатов.
- § 6. Приведенные и предваренные формы предикатных формул.
- Рекомендуемая литература