11:27
скнф и сднф

скнф и сднф - что это?  

СКНФ - совершенно конъюнктивная нормальная форма
СДНФ - совершенная дизъюнктивная нормальная форма

Что значит нормальна форма:
Нормальная форма логической формулы не содержит знаков импликации, эквиваленции и отрицания неэлементарных формул.

Существует два вида нормальной формы: конъюнктивная нормальная форма, т. е. конъюнкция нескольких дизъюнкций (КНФ) и дизъюнктивная нормальная форма, т. е. дизъюнкция нескольких конъюнкций (ДНФ), пример: 

КНФ:  \(\left (x\vee \bar{y}\vee z \right )\wedge \left (y\vee z \right )\)

ДНФ: \( \left (x\wedge \bar{y}\wedge z \right )\vee \left (y\wedge z \right )\)

Совершенно конъюнктивная НФ - конъюнкция дизъюнкций, причём в каждой дизъюнкции (в каждой скобке) присутствуют все переменные, входящие в формулу, либо их отрицание, нет одинаковых дизъюнкций, в каждой дизъюнкции нет одинаковых слагаемых, пример:

СКНФ:  \( (x\vee y\vee \bar{z})\wedge ( x\vee \bar{y}\vee z )\)

 

Совершенно дизьюнктивная НФ - дизьюнкция коньюнкций , причём в каждой коньюнкции (в каждой скобке) присутствуют все переменные, входящие в формулу, либо их отрицание, нет одинаковых коньюнкций, в каждой коньюнкции нет одинаковых слагаемых, пример:

СДНФ: \( ( x\wedge y\wedge \bar{z}) \vee ( x\wedge \bar{y} \wedge z ) \)

Взаимозаменяемые обозначения:

логика

булева алгебра

+

 

Правила построения СДНФ и СКНФ по таблице истинности

Пример:  Восстановите логическую функцию по ее таблице истинности:

x

y

z

F

0

0

0

1

0

0

1

1

0

1

0

0

0

1

1

0

1

0

0

1

1

0

1

1

1

1

0

0

1

1

1

1

 

 

РЕШЕНИЕ

СДНФ составляется на основе таблицы истинности по следующему правилу:

для каждого набора переменных, при котором функция равна 1, записывается произведение, в котором с отрицанием берутся переменные, имеющие значение «0».

x

y

z

F

0

0

0

1

0

0

1

1

1

0

0

1

1

0

1

1

1

1

1

1

 

Получаем СДНФ:

\(F(x,y,z)=\bar{x}\bar{y}\bar{z}+\bar{x}\bar{y} z+x\bar{y} \bar{z}+x\bar{y}z+xyz\)

СКНФ составляется на основе таблицы истинности по правилу:

для каждого набора переменных, при котором функция равна 0, записывается сумма, в которой с отрицанием берутся переменные, имеющие значение 1.

x

y

z

F

0

1

0

0

0

1

1

0

1

1

0

0

Получаем СКНФ:

\(F(x,y,z)=(x+\bar{y}+z)\cdot (x+\bar{y}+\bar{z })\cdot (\bar{x} +\bar{y}+z)\)

 

Категория: Таблица истинности | Просмотров: 145054 | Добавил: Admin | Теги: нормальные формы | Рейтинг: 4.5/38
Всего комментариев: 111 2 3 4 »
avatar
0
11 nikshadkov • 15:34, 23.12.2018
Благодаря этой статье всё понял! ;3
avatar
0
10 javoronkovdenis • 18:58, 08.03.2017
Сократить как? Есть литература толковая на эту тему?
avatar
0
9 Maximum • 19:22, 09.01.2017
Спасибо все понятно, а как сократить)
1-3 4-6 7-9 10-10
avatar
close