Презентация на тему "СКНФ и СДНФ"

Тема: Совершенная конъюнктивная нормальная форма и совершенная

дизъюнктивная нормальная форма

(СКНФ и СДНФ)

Основные понятия

Определение

Дизъюнктивная нормальная форма – это выражение

Основные понятия

Определение

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

Основные понятия

Определение

Совершенная дизъюнктивная

нормальная форма (СДНФ)

– это выражение вида

Основные понятия

Определение

Совершенная конъюнктивная

нормальная форма (СКНФ)

– это выражение вида

Основные понятия

Характерные черты СДНФ:

• Все члены дизъюнкции различные.
• Все члены конъюнкции различные.
• Ни одна конъюнкция не содержит одновременно переменную и её отрицание.
• Всякая конъюнкция содержит переменную, входящую в формулу.

Основные понятия

Характерные черты СКНФ:

• Все члены конъюнкции различные.
• Все члены дизъюнкции различные.
• Ни одна дизъюнкция не содержит одновременно переменную и её отрицание.
• Всякая дизъюнкция содержит переменную, входящую в формулу.

Основные понятия

Замечание 1:

Каждая формула не тождественно ложная имеет СДНФ

Замечание 2:

Каждая формула не тавтология имеет СКНФ

Задача

,

1. Привести формулу к СДНФ

X

Y

1

1

Z

1

1

1

1

0

0

0

1

1

1

0

0

1

0

1

0

0

0

0

1

0

0

Задача

,

2. Привести формулу к СДНФ и СКНФ

X

Y

1

1

Z

1

1

1

1

0

0

0

1

1

1

0

0

1

0

1

0

0

0

0

1

0

0

Задача

,

3. Привести формулу к СДНФ и СКНФ

X

Y

1

1

Z

1

1

1

1

0

0

0

1

1

1

0

0

1

0

1

0

0

0

0

1

0

0

Задача

,

4. Привести формулу к СДНФ и СКНФ

X

Y

1

1

Z

1

1

1

1

0

0

0

1

1

1

0

0

1

0

1

0

0

0

0

1

0

0

Задача

,

5. Привести формулу к СДНФ и СКНФ

x

y

1

1

1

0

0

1

0

0

Домашнее задание

,

Привести формулы к СДНФ и СКНФ