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

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

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

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

Построение СДНФ с помощью таблиц истинности (общий случай)

Легко переформулировать этот метод для общего случая Пусть дана формула F(X1; X2; : : : ; Xn).

1.Строим таблицу истинности для F.

2.Если на всех наборах принимает значение 0, то она невыполнима.

3.Åñëè F выполнима, то каждому набору переменных, на котором F принимает значение 1, сопоставляем элементарную

конъюнкцию Ci по правилу:

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

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

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

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

Построение СДНФ с помощью таблиц истинности (общий случай)

Легко переформулировать этот метод для общего случая Пусть дана формула F(X1; X2; : : : ; Xn).

1.Строим таблицу истинности для F.

2.Если на всех наборах принимает значение 0, то она невыполнима.

3.Åñëè F выполнима, то каждому набору переменных, на котором F принимает значение 1, сопоставляем элементарную

конъюнкцию Ci по правилу: если для данного набора переменная равна 0, то в качестве сомножителя берем отрицание этой переменной,

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

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

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

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

Построение СДНФ с помощью таблиц истинности (общий случай)

Легко переформулировать этот метод для общего случая Пусть дана формула F(X1; X2; : : : ; Xn).

1.Строим таблицу истинности для F.

2.Если на всех наборах принимает значение 0, то она невыполнима.

3.Åñëè F выполнима, то каждому набору переменных, на котором F принимает значение 1, сопоставляем элементарную

конъюнкцию Ci по правилу: если для данного набора переменная равна 0, то в качестве сомножителя берем отрицание этой переменной, иначе берем саму переменную.

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

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

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

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

Построение СДНФ с помощью таблиц истинности (общий случай)

Легко переформулировать этот метод для общего случая Пусть дана формула F(X1; X2; : : : ; Xn).

1.Строим таблицу истинности для F.

2.Если на всех наборах принимает значение 0, то она невыполнима.

3.Åñëè F выполнима, то каждому набору переменных, на котором F принимает значение 1, сопоставляем элементарную

конъюнкцию Ci по правилу: если для данного набора переменная равна 0, то в качестве сомножителя берем отрицание этой переменной, иначе берем саму переменную.

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

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

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

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

Построение СДНФ с помощью таблиц истинности (общий случай)

Пусть C1, C2; : : : ;Ck построенные таким образом элементарные конъюнкции.

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

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

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

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

Построение СДНФ с помощью таблиц истинности (общий случай)

Пусть C1, C2; : : : ;Ck построенные таким образом элементарные конъюнкции. Тогда

G = C1 _ _Ck

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

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

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

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

Построение СДНФ с помощью таблиц истинности (общий случай)

Пусть C1, C2; : : : ;Ck построенные таким образом элементарные конъюнкции. Тогда

G = C1 _ _Ck

является СДНФ для формулы F.

#

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

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

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

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

Определение

Формула называется элементарной дизъюнкцией, если она представляет собой дизъюнкцию логических переменных и их отрицаний

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

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

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

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

Определение

Формула называется элементарной дизъюнкцией, если она представляет собой дизъюнкцию логических переменных и их отрицаний

1 Элементарная дизъюнкция принимает значение 0

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

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

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

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

Определение

Формула называется элементарной дизъюнкцией, если она представляет собой дизъюнкцию логических переменных и их отрицаний

1Элементарная дизъюнкция принимает значение 0 тогда и

только, когда все составляющие ее высказывания принимают значения 0

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