48
правок
Изменения
КНФ
,Нет описания правки
}}
Простая дизъюнкция
* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно 1 один раз;
* '''монотонная''', если она не содержит отрицаний переменных.
{{Определение
|definition =
'''Конъюнктивная нормальная форма, КНФ ''' (Конъюнктивная Нормальная Формаангл. ''conjunctive normal form, CNF'') — {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид конъюнкции нескольких простых дизъюнктов.
}}
Пример КНФ:
{{Определение
|definition =
'''Совершенная конъюнктивная нормальная форма, СКНФ ''' (Совершенная Конъюнктивная Нормальная Форма)англ. ''perfect conjunctive normal form, PCNF'' ) — это такая КНФ, которая удовлетворяет условиям:
* в ней нет одинаковых простых дизъюнкций
* каждая простая дизъюнкция полная
Пример СКНФ:
<tex>f(x,y,z) = (x \lor \neg{y} \lor z) \land (x\lor y \lor \neg{z})</tex>
== Алгоритм построения СКНФ по таблице истинности ==
# В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex>0</tex>.# Для каждого отмеченного набора записываем дизъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex>0</tex>, то в дизъюнкцию включаем саму переменную, иначе ее отрицание.
# Все полученные дизъюнкции связываем операциями конъюнкции.
== Пример построения СКНФ для медианы==
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex>0</tex>.
{| class="wikitable" style="width:10cm" border=1
|-align="center" bgcolor=#F0F0F0
! 0 || 1 || 0 || 0
|-align="center" bgcolor=#F0F0F0FFF
| 0 || 1 || 1 || 1
|-align="center" bgcolor=#F0F0F0
! 1 || 0 || 0 || 0
|-align="center" bgcolor=#F0F0F0FFF
| 1 || 0 || 1 || 1
|-align="center" bgcolor=#F0F0F0FFF
| 1 || 1 || 0 || 1
|-align="center" bgcolor=#F0F0F0FFF
| 1 || 1 || 1 || 1
|}
2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу : если значение некоторой переменной есть <tex>0</tex>, то в дизъюнкцию включаем саму переменную, иначе ее отрицание.
{| class="wikitable" style="width:16cm" border=1
|-align="center" bgcolor=#F0F0F0
! 0 || 1 || 0 || 0 || <tex>(x \lor \neg{y} \lor z)</tex>
|-align="center" bgcolor=#F0F0F0FFF
| 0 || 1 || 1 || 1 ||
|-align="center" bgcolor=#F0F0F0
! 1 || 0 || 0 || 0 || <tex>(\neg{x} \lor y \lor z)</tex>
|-align="center" bgcolor=#F0F0F0FFF
| 1 || 0 || 1 || 1 ||
|-align="center" bgcolor=#F0F0F0FFF
| 1 || 1 || 0 || 1 ||
|-align="center" bgcolor=#F0F0F0FFF
| 1 || 1 || 1 || 1 ||
|}
Исключающее или: <tex> x \oplus y \oplus z = (\neg {x} \lor \neg {y} \lor z) \land (\neg {x} \lor y \lor \neg {z}) \land (x \lor \neg {y} \lor \neg {z}) \land (x \lor y \lor z)</tex>
== Ссылки Источники информации ==* [http://ru.wikipedia.org/wiki/%D0%A1%D0%9A%D0%9D%D0%A4 Википедия {{---}} СКНФ — Википедия]* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская — {{---}} Дискретная математика]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Булевы функции ]]
