![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Конституентой единицы набора называется конъюнкт
.
Конституентой нуля набора называется дизъюнкт
Отметим, что тогда и только тогда, когда
.
Пример: Формула есть конституента единицы К1 (1,0,1) (1 – без отрицания, 0 – отрицание);
Формула есть конституента нуля К0(0,0,1) (1 – отрицание, 0 – без отрицания).
Совершенной ДНФ называется дизъюнкция некоторых конституент единицы;
Совершенной КНФ называется конъюнкция некоторых конституент нуля, среди которых нет одинаковых.
Термин «совершенная» происходит от двух понятий:
1) Все переменные в каждой элементарной конъюнкции;
2) СДНФ (СКНФ) единственна.
[Подсказка: СКНФ – где 0 (скобки обязательны), СДНФ – где 1]
Таким образом, СДНФ (СКНФ) есть ДНФ (КНФ), в которой в каждый конъюнкт (дизъюнкт) каждая переменная xi из набора {xi,..., хл} входит ровно один раз, причем входит либо сама xi,либо ее отрицание |.
Пример: 1) формула – СДНФ,
2) формула – СКНФ,
3) формула не СДНФ, но ДНФ.
x1 | х2 | х3 | f(x1, х2, х3) |
0 | 0 | 0 | 1 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | 1 |
0 | 1 | 1 | 0 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 0 |
1 | 1 | 1 | 1 |
f(x1, х2, х3) = – СДНФ;
f(x1, х2, х3) = – СКНФ.
Дата публикования: 2015-02-03; Прочитано: 965 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!