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

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

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

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

Пример Приведем к ДНФ формулу F = :(X $ Y ) ^X. 1. (избавление от импликаций и эквиваленций)

(12)

:(X $ Y ) ^X eq :[(X ! Y ) ^(Y ! X)] ^X eq

(11)

eq :[(:X _Y ) ^(:Y _X)] ^X = F1

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

(100)

:[(:X _Y ) ^(:Y _X)] ^X eq [:(:X _Y ) _:(:Y _X)] ^X eq

(10)

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

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

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

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

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

Пример Приведем к ДНФ формулу F = :(X $ Y ) ^X. 1. (избавление от импликаций и эквиваленций)

(12)

:(X $ Y ) ^X eq :[(X ! Y ) ^(Y ! X)] ^X eq

(11)

eq :[(:X _Y ) ^(:Y _X)] ^X = F1

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

(100)

:[(:X _Y ) ^(:Y _X)] ^X eq [:(:X _Y ) _:(:Y _X)] ^X eq

(10)

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

(6)

eq [(X ^:Y ) _(Y ^:X)] ^X = F

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

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

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

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

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

[(X ^:Y ) _(Y ^:X)]^X

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

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

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

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

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

(30)

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

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

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

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

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

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

(30)

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

Фактически действие алгоритма завершено, но мы можем легко упростить последнюю формулу.

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

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

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

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

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

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

(30)

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

Фактически действие алгоритма завершено, но мы можем легко упростить последнюю формулу.

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

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

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

Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма

Конъюнктивные нормальные форма

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

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

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

Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма

Конъюнктивные нормальные форма

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

Определение

ÄÍÔ G(X1; : : : ; Xn) называется совершенной дизъюнктивной нормальной формой (сокращенно СДНФ), если выполняются следующие условия:

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

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

Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма

Конъюнктивные нормальные форма

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

Определение

ÄÍÔ G(X1; : : : ; Xn) называется совершенной дизъюнктивной нормальной формой (сокращенно СДНФ), если выполняются следующие условия:

1Любая элементарная конъюнкция в G для каждой переменной Xi, i = 1; : : : ; n

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

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

Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма

Конъюнктивные нормальные форма

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

Определение

ÄÍÔ G(X1; : : : ; Xn) называется совершенной дизъюнктивной нормальной формой (сокращенно СДНФ), если выполняются следующие условия:

1Любая элементарная конъюнкция в G для каждой

переменной Xi, i = 1; : : : ; n содержит либо Xi, ëèáî åå отрицание :Xi.

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