Нормальные формы в логике высказываний
.pdf
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Построение СДНФ с помощью таблиц истинности
Существует еще один способ построения СДНФ, который мы рассмотрим на примере
Пример Построим ДНФ формулы F = X ^(Y ! Z).
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Построение СДНФ с помощью таблиц истинности
Существует еще один способ построения СДНФ, который мы рассмотрим на примере
Пример Построим ДНФ формулы F = X ^(Y ! Z). Ниже приведена таблица истинности формулы F:
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Построение СДНФ с помощью таблиц истинности
Существует еще один способ построения СДНФ, который мы рассмотрим на примере
Пример Построим ДНФ формулы F = X ^(Y ! Z). Ниже приведена таблица истинности формулы F:
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Построение СДНФ с помощью таблиц истинности (пример)
X |
Y |
Z |
Y ! Z |
X ^(Y ! Z) |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Построение СДНФ с помощью таблиц истинности (пример)
X |
Y |
Z |
Y ! Z |
X ^(Y ! Z) |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
F равна 1 на трех наборах
переменных. Каждому из них ставим в соответствие элементарную конъюнкцию
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Построение СДНФ с помощью таблиц истинности (пример)
X |
Y |
Z |
Y ! Z |
X ^(Y ! Z) |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
F равна 1 на трех наборах
переменных. Каждому из них ставим в соответствие элементарную конъюнкцию
C1 = X ^:Y ^:Z
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Построение СДНФ с помощью таблиц истинности (пример)
X |
Y |
Z |
Y ! Z |
X ^(Y ! Z) |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
F равна 1 на трех наборах
переменных. Каждому из них ставим в соответствие элементарную конъюнкцию
C1 = X ^:Y ^:Z
C2 = X ^:Y ^Z
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Построение СДНФ с помощью таблиц истинности (пример)
X |
Y |
Z |
Y ! Z |
X ^(Y ! Z) |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
F равна 1 на трех наборах
переменных. Каждому из них ставим в соответствие элементарную конъюнкцию
C1 = X ^:Y ^:Z
C2 = X ^:Y ^Z
C3 = X ^Y ^Z
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Построение СДНФ с помощью таблиц истинности (пример)
X |
Y |
Z |
Y ! Z |
X ^(Y ! Z) |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
F равна 1 на трех наборах
переменных. Каждому из них ставим в соответствие элементарную конъюнкцию
C1 = X ^:Y ^:Z
C2 = X ^:Y ^Z
C3 = X ^Y ^Z
согласно следующему правилу
Нормальные формы в логике высказываний
Определения Дизъюнктивная нормульная форма
Приведение формулы к ДНФ Построение СДНФ с помощью таблиц истинности Совершенная дизъюнктивная нормальная форма
Конъюнктивные нормальные форма
Построение СДНФ с помощью таблиц истинности (пример)
X |
Y |
Z |
Y ! Z |
X ^(Y ! Z) |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
F равна 1 на трех наборах
переменных. Каждому из них ставим в соответствие элементарную конъюнкцию
C1 = X ^:Y ^:Z
C2 = X ^:Y ^Z
C3 = X ^Y ^Z
согласно следующему правилу
Если для данного набора переменная равна 0, то в ка- честве сомножителя берем отрицание этой переменной,
Нормальные формы в логике высказываний