54
правки
Изменения
ДНФ
,Нет описания правки
Т.к применение данного соотношения к каждой из переменных увеличивает количество дизъюнктивных членов в два раза, то для функции от <tex>n</tex> переменных мы имеем <tex>2^n</tex> дизъюнктивных членов. Каждый из них соответствует значению функции на одном из <tex>2^n</tex> возможных наборов значений n переменных. Если на некотором наборе <tex>f(\vec{x})=0</tex>, то весь соответствующий дизъюнктивный член также равен нулю и из представления данной функции его можно исключить. Если же <tex> f(\vec{x})=1</tex>, то в соответствующем дизъюннктивном члене само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.
}}
== Алгоритм построения СКНФ по таблице истинности ==# В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1.# Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть 1, то в конъюнкцию включаем саму переменную, иначе ее отрицание.# Все полученные конъюнкции связываем операциями дизъюнкции.
== Пример построения СДНФ ==
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1.
|+
|-align="center" bgcolor=#EEEEFF
! x || y || z || <xyztex>med(x,y,z)</tex>
|-align="center" bgcolor=#F0F0F0
| 0 || 0 || 0 || 0
|+
|-align="center" bgcolor=#EEEEFF
|-align="center" bgcolor=#F0F0F0
| 0 || 0 || 0 || 0 ||
== Ссылки ==
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%94%D0%9D%D0%A4 СДНФ — Википедия — свободная энциклопедия]
* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская — Дискретная математика]
