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

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

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

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

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

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

1 - 3 Алгоритм приведения к ДНФ. Пусть G(X1; X2; : : : ; Xn) полученная ДНФ, т. е.

G = C1 _C2 _Ck, ãäå Ci, i = 1; : : : ; k элементарные конъюнкции

4 (преобразование элементарных конъюнкций )

Для каждой конъюнкции Ci

4a åñëè Ci содержит некоторую переменной Xj вместе с отрицанием :Xj, то она невыполнима и исключается из G;

(Если все конъюнкции будут отброшены, то G eq 0

(формула невыполнима) и алгоритм заканчивает работу)

4b åñëè Ci содержит более одного вхождения Xi ( èëè :Xi) , то оставляем только одно из этих вхождений ( закон (70).

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

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

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

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

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

Пусть G0 = C10 _ _Ct0 ДНФ, полученная после действий в 4.

5(добавление недостающих переменных в конъюнкции) Если конъюнкция Ci0 не содержит ни переменной Xj, ни ее отрицания :Xj,

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

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

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

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

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

Пусть G0 = C10 _ _Ct0 ДНФ, полученная после действий в 4.

5(добавление недостающих переменных в конъюнкции) Если конъюнкция Ci0 не содержит ни переменной Xj, ни ее отрицания :Xj, разбиваем Ci0 íà äâå (Ci0 ^Xj) _(Ci0 ^:Xj), что приводит к равносильной формуле

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

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

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

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

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

Пусть G0 = C10 _ _Ct0 ДНФ, полученная после действий в 4.

5(добавление недостающих переменных в конъюнкции) Если конъюнкция Ci0 не содержит ни переменной Xj, ни ее отрицания :Xj, разбиваем Ci0 íà äâå (Ci0 ^Xj) _(Ci0 ^:Xj), что приводит к равносильной формуле т. к.

((Ci0 ^Xj) _(Ci0 ^:Xj)

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

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

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

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

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

Пусть G0 = C10 _ _Ct0 ДНФ, полученная после действий в 4.

5(добавление недостающих переменных в конъюнкции) Если конъюнкция Ci0 не содержит ни переменной Xj, ни ее отрицания :Xj, разбиваем Ci0 íà äâå (Ci0 ^Xj) _(Ci0 ^:Xj),

что приводит к равносильной формуле т. к.

(30)

((Ci0 ^Xj) _(Ci0 ^:Xj) eq Ci0 ^(Xi _:Xi)

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

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

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

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

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

Пусть G0 = C10 _ _Ct0 ДНФ, полученная после действий в 4.

5(добавление недостающих переменных в конъюнкции) Если конъюнкция Ci0 не содержит ни переменной Xj, ни ее отрицания :Xj, разбиваем Ci0 íà äâå (Ci0 ^Xj) _(Ci0 ^:Xj),

что приводит к равносильной формуле т. к.

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

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

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

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

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

Пусть G0 = C10 _ _Ct0 ДНФ, полученная после действий в 4.

5(добавление недостающих переменных в конъюнкции) Если конъюнкция Ci0 не содержит ни переменной Xj, ни ее отрицания :Xj, разбиваем Ci0 íà äâå (Ci0 ^Xj) _(Ci0 ^:Xj),

что приводит к равносильной формуле т. к.

Последовательно, применяя аналогичные действия ко всем конъюкциям и недостающим переменным,

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

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

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

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

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

Пусть G0 = C10 _ _Ct0 ДНФ, полученная после действий в 4.

5(добавление недостающих переменных в конъюнкции) Если конъюнкция Ci0 не содержит ни переменной Xj, ни ее отрицания :Xj, разбиваем Ci0 íà äâå (Ci0 ^Xj) _(Ci0 ^:Xj),

что приводит к равносильной формуле т. к.

Последовательно, применяя аналогичные действия ко всем конъюкциям и недостающим переменным, получаем ДНФ, удовлетворяющую свойству (1) из определения СДНФ

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

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

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

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

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

Пусть G0 = C10 _ _Ct0 ДНФ, полученная после действий в 4.

5(добавление недостающих переменных в конъюнкции) Если конъюнкция Ci0 не содержит ни переменной Xj, ни ее отрицания :Xj, разбиваем Ci0 íà äâå (Ci0 ^Xj) _(Ci0 ^:Xj),

что приводит к равносильной формуле т. к.

Последовательно, применяя аналогичные действия ко всем конъюкциям и недостающим переменным, получаем ДНФ, удовлетворяющую свойству (1) из определения СДНФ

6 (отбрасываем одинаковые элементарные конъюнкции)

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

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

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

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

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

Пусть G0 = C10 _ _Ct0 ДНФ, полученная после действий в 4.

5(добавление недостающих переменных в конъюнкции) Если конъюнкция Ci0 не содержит ни переменной Xj, ни ее отрицания :Xj, разбиваем Ci0 íà äâå (Ci0 ^Xj) _(Ci0 ^:Xj),

что приводит к равносильной формуле т. к.

Последовательно, применяя аналогичные действия ко всем конъюкциям и недостающим переменным, получаем ДНФ, удовлетворяющую свойству (1) из определения СДНФ

6(отбрасываем одинаковые элементарные конъюнкции) Если есть более одной одинаковых конъюнкций,

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