Нормальные формы. Приведение формул к СДНФ и СКНФ. Построение таблиц истинности

Сентябрь 13, 2022

Главная
Математика
Нормальные формы. Приведение формул к СДНФ и СКНФ. Построение таблиц истинности

Содержание

2. Нормальная форма логической формулы - это формула, которая не содержит знаков импликации, эквиваленции и отрицания неэлементарных
3. Совершенная конъюнктивная нормальная форма (СКНФ) – такая конъюнкция дизъюнкций, в которой: 1) Различны все члены дизъюнкции
4. Совершенная дизъюнктивная нормальная форма (СДНФ) – такая дизъюнкция конъюнкций, в которой: 1) Различны все члены конъюнкции
5. Приведение формулы к СДНФ с помощью равносильных преобразований: 1) Привести формулу к нормальному виду (т.е. избавиться
6. Приведение формулы к СКНФ с помощью равносильных преобразований: 1) Привести формулу к нормальному виду (т.е. избавиться
7. Пример: (¬(XY)→¬X)∧¬((XY→(¬Y))) ≡ (XY∨(¬X))∧¬(¬X∨(¬Y)) ≡ (¬X∨Y)XY - нормальная форма (¬X∨Y)XY ≡ (¬X∨Y)(X∨Y¬Y)(Y∨X¬X) ≡ (¬X∨Y)(X∨Y)(X∨¬Y)(X∨Y)(¬X∨Y) ≡ (¬X∨Y)(X∨Y)(X∨¬Y)
8. Построение СДНФ и СКНФ по таблице истинности: СДНФ: 1) Выбрать из таблицы истинности те строки, в
9. СКНФ: 1) Выбрать из таблицы истинности те строки, в которых значение формулы - "Ложь". 2) Для
11. Скачать презентацию

Слайд 2

Нормальная форма логической формулы - это формула, которая не содержит знаков

импликации, эквиваленции и отрицания неэлементарных формул. Существует два вида нормальных форм: конъюнктивная нормальная форма, т. е. конъюнкция нескольких дизъюнкций (КНФ) и дизъюнктивная нормальная форма, т. е. дизъюнкция нескольких конъюнкций (ДНФ). КНФ: (X∨Y)(¬X∨Z)(X∨¬Y) ДНФ: (¬XY)∨(XZ)∨(¬Y¬Z)∨(X¬Z)

Слайд 3

Совершенная конъюнктивная нормальная форма (СКНФ) – такая конъюнкция дизъюнкций, в которой: 1)

Различны все члены дизъюнкции ("слагаемые"); 2) Различны все члены каждой конъюнкции ("множители"); 3) В каждой конъюнкции нет одновременно переменной и ее отрицания; 4) Каждая конъюнкция содержит все переменные, входящие в данную формулу или их отрицания. СКНФ: (X∨Y∨Z)(¬X∨¬Y∨Z)(X∨¬Y∨Z)

Слайд 4

Совершенная дизъюнктивная нормальная форма (СДНФ) – такая дизъюнкция конъюнкций, в которой: 1)

Различны все члены конъюнкции ("множители"); 2) Различны все члены каждой дизъюнкции ("слагаемые"); 3) В каждой дизъюнкции нет одновременно переменной и ее отрицания; 4) Каждая дизъюнкция содержит все переменные, входящие в данную формулу или их отрицания. CДНФ: (¬XYZ)∨(X¬YZ)∨(¬XY¬Z)∨(XY¬Z)

Слайд 5

Приведение формулы к СДНФ с помощью равносильных преобразований: 1) Привести формулу к

нормальному виду (т.е. избавиться от импликации, эквиваленции и отрицания неэлементарных формул). 2) Из всех одинаковых членов дизъюнкции ("слагаемых") оставить только один. 3) Если в каком-то члене дизъюнкции ("слагаемом") не хватает переменной Xi, то "домножаем" его на (Xi∨¬Xi), т.е. на 1 . 4) Раскрыть скобки и из всех одинаковых членов дизъюнкции ("слагаемых") оставить только один.

Слайд 6

Приведение формулы к СКНФ с помощью равносильных преобразований: 1) Привести формулу к

нормальному виду (т.е. избавиться от импликации, эквиваленции и отрицания неэлементарных формул). 2) Из всех одинаковых членов конъюнкции ("множителей") оставить только один. 3) Если в каком-то члене конъюнкции ("множителе") не хватает переменной Xi, то "прибавить" к нему (Xi∧¬Xi), т.е. 0 . 4) Раскрыть скобки и из всех одинаковых членов конъюнкции ("множителей") оставить только один.

Слайд 7

Пример: (¬(XY)→¬X)∧¬((XY→(¬Y))) ≡ (XY∨(¬X))∧¬(¬X∨(¬Y)) ≡ (¬X∨Y)XY - нормальная форма (¬X∨Y)XY ≡ (¬X∨Y)(X∨Y¬Y)(Y∨X¬X) ≡ (¬X∨Y)(X∨Y)(X∨¬Y)(X∨Y)(¬X∨Y) ≡ (¬X∨Y)(X∨Y)(X∨¬Y)

- СКНФ (¬X∨Y)XY ≡ XY - СДНФ

Слайд 8

Построение СДНФ и СКНФ по таблице истинности:
СДНФ: 1) Выбрать из таблицы истинности

те строки, в которых значение формулы - "Истина". 2) Для каждой выбранной строки составить конъюнкцию переменных или их отрицаний так, чтобы эта конъюнкция была истинной (для этого переменные, которые в соответствующей строке имеют значение "Ложь" нужно взять с отрицанием, а переменные, имеющие значение "Истина" - без отрицания). 3) Составить дизъюнкцию полученных конъюнкций.

Слайд 9

СКНФ: 1) Выбрать из таблицы истинности те строки, в которых значение формулы

- "Ложь". 2) Для каждой выбранной строки составить дизъюнкцию переменных или их отрицаний так, чтобы эта дизъюнкция была ложной (для этого переменные, которые в соответствующей строке имеют значение "Истина" нужно взять с отрицанием, а переменные, имеющие значение "Ложь" - без отрицания). 3) Составить конъюнкцию полученных дизъюнкций.