Нормальные формы в логике высказываний
.pdf
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Алгоритм приведения к CДНФ
Пусть G0 = C10 _ _Ct0 ДНФ, полученная после действий в 4.
5(добавление недостающих переменных в конъюнкции) Если конъюнкция Ci0 не содержит ни переменной Xj, ни ее отрицания :Xj, разбиваем Ci0 íà äâå (Ci0 ^Xj) _(Ci0 ^:Xj),
что приводит к равносильной формуле т. к.
((C0 |
|
X |
) |
|
(C0 |
|
X |
(30) |
|
|
(5) |
^ |
_ |
^: |
) eq C0 |
^ |
(X X ) eq C0) |
||||||
i |
j |
|
i |
j |
i |
i _: i |
i |
||||
Последовательно, применяя аналогичные действия ко всем конъюкциям и недостающим переменным, получаем ДНФ, удовлетворяющую свойству (1) из определения СДНФ
6(отбрасываем одинаковые элементарные конъюнкции) Если есть более одной одинаковых конъюнкций, то оставляем только одну
# 
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Алгоритм приведения к CДНФ (пример)
Пример Приведем к СДНФ формулу G = (X ^Y ) _(X ^:Z)
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Алгоритм приведения к CДНФ (пример)
Пример Приведем к СДНФ формулу G = (X ^Y ) _(X ^:Z)
Данная формула является ДНФ, и поэтому шаги 1 3 не нужны.
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Алгоритм приведения к CДНФ (пример)
Пример Приведем к СДНФ формулу G = (X ^Y ) _(X ^:Z)
Данная формула является ДНФ, и поэтому шаги 1 3 не нужны.Шаг 4 тоже не требуется, так как в обеих конъюнкциях нет лишних вхождений переменных
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Алгоритм приведения к CДНФ (пример)
Пример Приведем к СДНФ формулу G = (X ^Y ) _(X ^:Z)
Данная формула является ДНФ, и поэтому шаги 1 3 не нужны.Шаг 4 тоже не требуется, так как в обеих конъюнкциях нет лишних вхождений переменных
5. К конъюнкции X ^Y добавляем Z
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Алгоритм приведения к CДНФ (пример)
Пример Приведем к СДНФ формулу G = (X ^Y ) _(X ^:Z)
Данная формула является ДНФ, и поэтому шаги 1 3 не нужны.Шаг 4 тоже не требуется, так как в обеих конъюнкциях нет лишних вхождений переменных
5. К конъюнкции X ^Y добавляем Z , т. е. заменяем на
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Алгоритм приведения к CДНФ (пример)
Пример Приведем к СДНФ формулу G = (X ^Y ) _(X ^:Z)
Данная формула является ДНФ, и поэтому шаги 1 3 не нужны.Шаг 4 тоже не требуется, так как в обеих конъюнкциях нет лишних вхождений переменных
5. К конъюнкции X ^Y добавляем Z , т. е. заменяем на
(X ^Y ^Z) _(X ^Y ^:Z)
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Алгоритм приведения к CДНФ (пример)
Пример Приведем к СДНФ формулу G = (X ^Y ) _(X ^:Z)
Данная формула является ДНФ, и поэтому шаги 1 3 не нужны.Шаг 4 тоже не требуется, так как в обеих конъюнкциях нет лишних вхождений переменных
5. К конъюнкции X ^Y добавляем Z , т. е. заменяем на
(X ^Y ^Z) _(X ^Y ^:Z)
К конъюнкции (X ^:Z) добавляем Y , т. е. заменяем на
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Алгоритм приведения к CДНФ (пример)
Пример Приведем к СДНФ формулу G = (X ^Y ) _(X ^:Z)
Данная формула является ДНФ, и поэтому шаги 1 3 не нужны.Шаг 4 тоже не требуется, так как в обеих конъюнкциях нет лишних вхождений переменных
5. К конъюнкции X ^Y добавляем Z , т. е. заменяем на
(X ^Y ^Z) _(X ^Y ^:Z)
К конъюнкции (X ^:Z) добавляем Y , т. е. заменяем на
(X ^:Z ^Y ) _(X ^:Z ^:Y )
Получаем
G eq (X ^Y ^Z) _(X ^Y ^:Z) _(X ^:Z ^Y ) _(X ^:Z ^:Y )
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Таким образом
Geq (X ^Y ^Z) _(X ^Y ^:Z) _(X ^:Z ^Y ) _(X ^:Z ^:Y )
6.Переставляя переменные в элементарных конъюнкциях и выбрасывая лишние вхождения, получаем СДНФ
(X ^Y ^Z) _(X ^Y ^:Z) _(X ^:Y ^:Z):
#
Нормальные формы в логике высказываний