Нормальные формы в логике высказываний

Определения Дизъюнктивная нормульная форма Приведение формулы к ДНФ

Совершенная дизъюнктивная нормальная форма Конъюнктивные нормальные форма

Алгоритм приведения к ДНФ

Пусть дана формула F(X1; : : : ; Xn)

1(избавление от импликаций и эквиваленций)

Применяя законы 12 и 11 получаем формулу F1, равносильную исходной и содержащую только операции

отрицания, конъюнкции и дизъюнкции.

2(все отрицания заносятся к переменным)

Последовательно применяя законы де Моргана и закон двойного отрицания (6) получаем из формулы F1 равносильную формулу F2, в которой отрицания находятся только перед переменными.

Нормальные формы в логике высказываний

Определения Дизъюнктивная нормульная форма Приведение формулы к ДНФ

Совершенная дизъюнктивная нормальная форма Конъюнктивные нормальные форма

Алгоритм приведения к ДНФ

Пусть дана формула F(X1; : : : ; Xn)

1(избавление от импликаций и эквиваленций)

Применяя законы 12 и 11 получаем формулу F1, равносильную исходной и содержащую только операции

отрицания, конъюнкции и дизъюнкции.

2(все отрицания заносятся к переменным)

Последовательно применяя законы де Моргана и закон двойного отрицания (6) получаем из формулы F1 равносильную формулу F2, в которой отрицания находятся

только перед переменными.

3 (раскрываем все скобки, содержащие дизъюнкции)

Нормальные формы в логике высказываний

Определения Дизъюнктивная нормульная форма Приведение формулы к ДНФ

Совершенная дизъюнктивная нормальная форма Конъюнктивные нормальные форма

Алгоритм приведения к ДНФ

Пусть дана формула F(X1; : : : ; Xn)

1(избавление от импликаций и эквиваленций)

Применяя законы 12 и 11 получаем формулу F1, равносильную исходной и содержащую только операции

отрицания, конъюнкции и дизъюнкции.

2(все отрицания заносятся к переменным)

Последовательно применяя законы де Моргана и закон двойного отрицания (6) получаем из формулы F1 равносильную формулу F2, в которой отрицания находятся

только перед переменными.

3 (раскрываем все скобки, содержащие дизъюнкции)

Последовательно применяя к формуле F2 закон дистрибутивности 30 получаем равносильную формулу G,

Нормальные формы в логике высказываний

Определения Дизъюнктивная нормульная форма Приведение формулы к ДНФ

Совершенная дизъюнктивная нормальная форма Конъюнктивные нормальные форма

Алгоритм приведения к ДНФ

Пусть дана формула F(X1; : : : ; Xn)

1(избавление от импликаций и эквиваленций)

Применяя законы 12 и 11 получаем формулу F1, равносильную исходной и содержащую только операции

отрицания, конъюнкции и дизъюнкции.

2(все отрицания заносятся к переменным)

Последовательно применяя законы де Моргана и закон двойного отрицания (6) получаем из формулы F1 равносильную формулу F2, в которой отрицания находятся

только перед переменными.

3 (раскрываем все скобки, содержащие дизъюнкции)

Последовательно применяя к формуле F2 закон дистрибутивности 30 получаем равносильную формулу G,

которая является ДНФ	Нормальные формы в логике высказываний

Определения Дизъюнктивная нормульная форма Приведение формулы к ДНФ

Совершенная дизъюнктивная нормальная форма Конъюнктивные нормальные форма

Алгоритм приведения к ДНФ

Пусть дана формула F(X1; : : : ; Xn)

1(избавление от импликаций и эквиваленций)

Применяя законы 12 и 11 получаем формулу F1, равносильную исходной и содержащую только операции

отрицания, конъюнкции и дизъюнкции.

2(все отрицания заносятся к переменным)

Последовательно применяя законы де Моргана и закон двойного отрицания (6) получаем из формулы F1 равносильную формулу F2, в которой отрицания находятся

только перед переменными.

3 (раскрываем все скобки, содержащие дизъюнкции)

Последовательно применяя к формуле F2 закон дистрибутивности 30 получаем равносильную формулу G,

которая является ДНФ	Нормальные формы в логике высказываний

Определения Дизъюнктивная нормульная форма Приведение формулы к ДНФ

Совершенная дизъюнктивная нормальная форма Конъюнктивные нормальные форма

Алгоритм приведения к ДНФ (пояснения)

Прокомментируем шаг 3

Нормальные формы в логике высказываний

Определения Дизъюнктивная нормульная форма Приведение формулы к ДНФ

Совершенная дизъюнктивная нормальная форма Конъюнктивные нормальные форма

Алгоритм приведения к ДНФ (пояснения)

Прокомментируем шаг 3

раскрывая скобки, мы последовательно заменяем каждое вхождение вида

Y ^(Z1 _ _Zk)

Нормальные формы в логике высказываний

Определения Дизъюнктивная нормульная форма Приведение формулы к ДНФ

Совершенная дизъюнктивная нормальная форма Конъюнктивные нормальные форма

Алгоритм приведения к ДНФ (пояснения)

Прокомментируем шаг 3

раскрывая скобки, мы последовательно заменяем каждое вхождение вида

Y ^(Z1 _ _Zk)

на дизъюнкцию элементарных конъюнкций

(Y ^Z1) _ _(Y ^Zk)

или более общо

Нормальные формы в логике высказываний

Определения Дизъюнктивная нормульная форма Приведение формулы к ДНФ

Совершенная дизъюнктивная нормальная форма Конъюнктивные нормальные форма

Алгоритм приведения к ДНФ (пояснения)

Прокомментируем шаг 3

раскрывая скобки, мы последовательно заменяем каждое вхождение вида

Y ^(Z1 _ _Zk)

на дизъюнкцию элементарных конъюнкций

(Y ^Z1) _ _(Y ^Zk)

или более общо

(Y1 _ _Ym) ^(Z1 _ _Zk)

Нормальные формы в логике высказываний

Определения Дизъюнктивная нормульная форма Приведение формулы к ДНФ

Совершенная дизъюнктивная нормальная форма Конъюнктивные нормальные форма

Алгоритм приведения к ДНФ (пояснения)

Прокомментируем шаг 3

раскрывая скобки, мы последовательно заменяем каждое вхождение вида

Y ^(Z1 _ _Zk)

на дизъюнкцию элементарных конъюнкций

(Y ^Z1) _ _(Y ^Zk)

или более общо

(Y1 _ _Ym) ^(Z1 _ _Zk)

заменяется на

(Y1 ^Z1) _ _(Y1 ^Zk) _ _(Ym ^Z1) _ _(Ym ^Zk)

Нормальные формы в логике высказываний