- •1.Совершенные нормальные формы.Правила приведения к сднф и скнф. Минимизация логических функций.
- •§8. Нормальные формы функций.
- •8.2 Нормальные формы.
- •8.3 Совершенные нормальные формы.
- •8.4 Правила приведения произвольной формулы алгебры логики к совершенной нормальной форме.
- •8.6 Способ составления снф для произвольной формулы алгебры логики по таблице истинности.
- •§ 1. Понятие формулы исчисления высказываний.
- •§ 2. Определение доказуемой (выводимой) формулы.
- •Правила вывода.
- •Определение выводимой (доказуемой ) формулы.
- •Правило сложной (одновременной) подстановки (спп).
- •Правило сложного заключения.
- •Правило силлогизма.
- •Правило контр позиции.
- •Правило снятия двойного отрицания.
- •§4.Понятие выводимости формул из совокупности формул.
- •§5. Понятие вывода.
- •§6. Правила выводимости.
- •H,w├a из совокупности формул : “Если а выводима из н, то она вы- водима из ”.
- •5. Теорема дедукции: h, c├ a .
- •§9.Проблемы аксиоматического исчисления высказываний.
- •2. Проблема непротиворечивости исчисления высказываний.
- •3.Проблема полноты исчисление высказываний.
- •4.Проблема независимости аксиом исчисления высказываний.
- •§1. Недостаточность логики высказываний. Понятие предиката.
- •§2. Логические операции над предикатами.
- •§3. Кванторные операции.
- •Квантор всеобщности.
- •Квантор существования.
- •Отрицание предложений с кванторами.
- •§4.Понятие формулы логики предикатов.
- •§5. Значение формулы логики предикатов.
- •§6. Равносильные формулы логики предикатов.
- •§7. Нормальные формы формул логики предикатов.
- •§8. Общезначимость и выполнимость формул. Проблема разрешимости.
- •§9. Применение языка логики предикатов для записи математических предложений, определений, построения отрицания предложений.
- •9.1 Запись математических предложений и определений в виде формул логики предикатов.
- •9.2. Построение противоположный утверждений.
- •9.3 Прямая, обратная и противоположная теоремы.
- •9.4 Необходимые и достаточные условия.
- •9.5. Доказательство теорем методом от противного.
- •Утверждения о свойствах объектов и отношениях между ними
- •Язык логики предикатов
- •Синтаксис: формулы логики предикатов
- •Семантика: системы и значения формул на их состояниях
- •Реляционные базы данных
- •Реляционная алгебра
- •Теоретико-множественные операции
- •Специальные реляционные операторы
- •Запросы
- •Ограничения целостности
- •Основные определения
- •Тьюрингово программирование
- •Стандартная заключительная конфигурация
- •Односторонние машины Тьюринга
- •Последовательная и параллельная композиции машин Тьюринга
- •Ветвление (условный оператор)
- •Повторение (цикл)
1.Совершенные нормальные формы.Правила приведения к сднф и скнф. Минимизация логических функций.
§8. Нормальные формы функций.
При решении ряда задач, связанных с использованием формул алгебры высказываний, важную роль играют формулы, построенные особым образом из высказывательных переменных с помощью только операций дизъюнкции, конъюнкции и отрицания и называемые ДИЗЪЮНКТИВНЫМИ и КОНЪЮНКТИВНЫМИ НОРМАЛЬНЫМИ ФОРМАМИ (ДНФ и КНФ).
8.1 Элементарные дизъюнкции и конъюнкции.
Пусть задана система высказывательных переменных
(x1,x2,…,xn). (1)
Элементарной дизъюнкцией высказывательных переменных из системы (1) называется дизъюнкция некоторых высказывательных переменных этой системы или их отрицаний.
ЭЛЕМЕНТАРНОЙ КОНЪЮНКЦИЕЙ называется конъюнкция некоторых высказывательных переменных этой системы или их отрицаний.
Если в элементарную дизъюнкцию (конъюнкцию) входит каждое высказывательное переменное из системы (1) (с отрицанием или без него) и притом только один раз, то она называется ПОЛНОЙ ЭЛЕМЕНТАРНОЙ ДИЗЪЮНКЦИЕЙ (КОНЪЮНКЦИЕЙ).
Из “n” высказывательных переменных можно образовать 2n всевозможных неэквивалентных полных элементарных дизъюнкций и столько же полных элементарных конъюнкций. Каждая полная элементарная дизъюнкция только для одного варианта значений высказывательных переменных системы (1) принимает значение, равное нулю, а именно – когда каждое высказывательное переменное xi, не находящееся в под знаком отрицания, равно нулю, а каждое отрицательное – единице.
Систему значений высказывательных переменных, для которой данная полная элементарная дизъюнкция принимает значение, равное нулю, назовем нулем этой полной элементарной дизъюнкции.
Так, нулями элементарных дизъюнкций (2) являются: (0,0,0), (0,0,1), (0,1,0), (1,0,0), (0,1,1), (1,0,1), (1,1,0), (1,1,1).
Если обратиться к полным элементарным конъюнкциям, то можно обнаружить, что каждая из них только один раз принимает значение, равное единице – когда неотрицаемое переменное равно единице, а отрицаемое – нулю. Такую систему значений высказывательных переменных назовем ЕДИНИЦЕЙ соответствующей ПОЛНОЙ ЭЛЕМЕНТАРНОЙ КОНЪЮНКЦИИ.
8.2 Нормальные формы.
Определение 8.1.
Формула F называется КОНЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМОЙ (КНФ) от высказывательных переменных системы (1), если она является конъюнкцией элементарных дизъюнкций, образованных из высказывательных переменных этой системы.
Формула F называется ДИЗЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМОЙ (ДНФ) от высказывательных переменных системы (1), если она является дизъюнкцией элементарных конъюнкций, образованных из этих переменных.
Это определение, учитывая закон двойственности, можно сформулировать иначе: формула F называется ДНФ от высказывательных переменных системы (1), если двойственная ей формула F* является КНФ, образованной из этих переменных.
Утверждение 3.
Для всякой формулы F существуют эквивалентные ей КНФ и ДНФ.
8.3 Совершенные нормальные формы.
Определение 8.3
Формула F называется СОВЕРШЕННОЙ КОНЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМОЙ (СКНФ) от высказывательных переменных системы (1) x1,…,xn, если она является конъюнкцией различных полных элементарных дизъюнкций от этих переменных (при этом равенство дизъюнкций понимается с точностью до порядка членов).
Определение 8.4
Формула F называется СОВЕРШЕННОЙ ДИЗЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМОЙ (СДНФ) от высказывательных переменных системы (1) x1,…,xn, если она является дизъюнкцией различных полных элементарных конъюнкций от этих переменных.
Или иначе: если двойственная ей формула F* является СКНФ. Из замечания 2 следует, что СДНФ не может быть тождественно ложным высказыванием.