Суббота, 10.12.2016, 02:09
Главная Регистрация RSS
Вы вошли как Гость | Группа "Гости"Приветствую Вас, Гость
Поделиться
Статистика
Яндекс.Метрика
Flag Counter
Онлайн всего: 5
Гостей: 5
Пользователей: 0
» »
11:27
скнф и сднф

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

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

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

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

КНФ: 

ДНФ:

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

СКНФ: 

 

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

СДНФ:  

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

логика

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

+

 

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

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

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

 

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

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

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

x

y

z

F

0

1

0

0

0

1

1

0

1

1

0

0

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

 

Категория: Таблица истинности | Просмотров: 55469 | Добавил: Admin | Теги: нормальные формы | Рейтинг: 4.5/16



Всего комментариев: 81 2 3 »
avatar
0
8 evgenivelichkoj • 00:37, 14.10.2016
Красавчик!СПасибо большое))
avatar
0
7 danis199696 • 17:51, 07.06.2016
Админ, спасибо, все оооочень ясно) на пальцах прям))
avatar
0
6 saturday22 • 20:44, 14.04.2016
Всё понятно yes
1-3 4-6 7-7
avatar
  .