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

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

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

Дизъюнктивная нормальная форма (ДНФ)

Замечание 1

Согласно предложению 2.1 для ДНФ можно определить все наборы переменных, на которых она равна 1, не строя таблицу

истинности.

Пример Рассмотрим ДНФ

G(X;Y; Z) = (X ^:Y ) _(Y ^:Z) _(:X ^Z)

Она состоит из трех элементарных конъюнкций. Самая левая из них H1(X;Y; Z) равна 1

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

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

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

Дизъюнктивная нормальная форма (ДНФ)

Замечание 1

Согласно предложению 2.1 для ДНФ можно определить все наборы переменных, на которых она равна 1, не строя таблицу

истинности.

Пример Рассмотрим ДНФ

G(X;Y; Z) = (X ^:Y ) _(Y ^:Z) _(:X ^Z)

Она состоит из трех элементарных конъюнкций. Самая левая из них H1(X;Y; Z) равна 1 ïðè X = 1 è Y = 0

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

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

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

Дизъюнктивная нормальная форма (ДНФ)

Замечание 1

Согласно предложению 2.1 для ДНФ можно определить все наборы переменных, на которых она равна 1, не строя таблицу

истинности.

Пример Рассмотрим ДНФ

G(X;Y; Z) = (X ^:Y ) _(Y ^:Z) _(:X ^Z)

Она состоит из трех элементарных конъюнкций. Самая левая из них H1(X;Y; Z) равна 1 ïðè X = 1 è Y = 0

Учитывая, что H1 не зависит от Z, òî H1 соответствует сразу два набора значений (X;Y; Z): (1; 0; 0) è (1; 0; 1)

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

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

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

Дизъюнктивная нормальная форма (ДНФ)

Замечание 1

Согласно предложению 2.1 для ДНФ можно определить все наборы переменных, на которых она равна 1, не строя таблицу

истинности.

Пример Рассмотрим ДНФ

G(X;Y; Z) = (X ^:Y ) _(Y ^:Z) _(:X ^Z)

Она состоит из трех элементарных конъюнкций. Самая левая из них H1(X;Y; Z) равна 1 ïðè X = 1 è Y = 0

Учитывая, что H1 не зависит от Z, òî H1 соответствует сразу два набора значений (X;Y; Z): (1; 0; 0) è (1; 0; 1)

Аналогично для второй конъюнкции H2 (не зависит X ) получаем еще два набора:

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

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

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

Дизъюнктивная нормальная форма (ДНФ)

Замечание 1

Согласно предложению 2.1 для ДНФ можно определить все наборы переменных, на которых она равна 1, не строя таблицу

истинности.

Пример Рассмотрим ДНФ

G(X;Y; Z) = (X ^:Y ) _(Y ^:Z) _(:X ^Z)

Она состоит из трех элементарных конъюнкций. Самая левая из них H1(X;Y; Z) равна 1 ïðè X = 1 è Y = 0

Учитывая, что H1 не зависит от Z, òî H1 соответствует сразу два набора значений (X;Y; Z): (1; 0; 0) è (1; 0; 1)

Аналогично для второй конъюнкции H2 (не зависит X ) получаем еще два набора:(0; 1; 0) è (1; 1; 0)

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

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

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

Дизъюнктивная нормальная форма (ДНФ)

Замечание 1

Согласно предложению 2.1 для ДНФ можно определить все наборы переменных, на которых она равна 1, не строя таблицу

истинности.

Пример Рассмотрим ДНФ

G(X;Y; Z) = (X ^:Y ) _(Y ^:Z) _(:X ^Z)

Она состоит из трех элементарных конъюнкций. Самая левая из них H1(X;Y; Z) равна 1 ïðè X = 1 è Y = 0

Учитывая, что H1 не зависит от Z, òî H1 соответствует сразу два набора значений (X;Y; Z): (1; 0; 0) è (1; 0; 1)

Аналогично для второй конъюнкции H2 (не зависит X ) получаем еще два набора:(0; 1; 0) è (1; 1; 0)

И для последней H3 åùå äâà: (0; 0; 1) è (0; 1; 1) #

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

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

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

Приведение формулы к ДНФ

Определение

Формула F может быть приведена к дизъюнктивной нормальной форме, если существует равносильная ей формула G, которая является ДНФ.

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

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

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

Приведение формулы к ДНФ

Определение

Формула F может быть приведена к дизъюнктивной нормальной форме, если существует равносильная ей формула G, которая является ДНФ.

Пример

1. Пусть F = :(X ^Y )

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

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

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

Приведение формулы к ДНФ

Определение

Формула F может быть приведена к дизъюнктивной нормальной форме, если существует равносильная ей формула G, которая является ДНФ.

Пример

1. Пусть F = :(X ^Y )

Применяя закон де Моргана (10') получаем ДНФ

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

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

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

Приведение формулы к ДНФ

Определение

Формула F может быть приведена к дизъюнктивной нормальной форме, если существует равносильная ей формула G, которая является ДНФ.

Пример

1. Пусть F = :(X ^Y )

Применяя закон де Моргана (10') получаем ДНФ

:(X ^Y ) eq :X _:Y

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