==Канонические формы логических формул==
Любая логическая формула задает некоторую [[Определение булевой функции|булеву функцию]]. Но для всякой булевой функции можно привести бесконечно много формул ее представляющих. Одной из задач алгебры логики является построение '''канонических форм''' (т.е формул построенных по определенному правилу).
{{Определение
|definition =
Если логическая формула выражена через отрицаниеДНФ (Дизъюнктивная Нормальная Форма) — нормальная форма, конъюнкцию и дизъюнкцию переменных, то такая форма представления называется '''нормальной'''в которой [[Определение булевой функции|булева функция]] имеет вид дизъюнкции нескольких конъюнктов.
}}
Пример ДНФ:
<tex>f(x,y) = (x \land y) \lor (y \land \overline{z})</tex>
{{Определение
|definition =
Формулу называют '''элементарной конъюнкцией''', если она является конъюнкцией одного или нескольких термов.}} {{Определение|definition = Формула называется '''дизъюктивной нормальной формой СДНФ (ДНФСовершенная Дизъюнктивная Нормальная Форма) '''— это такая ДНФ, если она является дизъюнкцией неповторяемых которая удовлетворяет условиям:* в ней нет одинаковых элементарных конъюнкций* в каждой конъюнкции нет одинаковых переменных* каждая элементарная конъюнкция содержит каждый из аргументов функции.
}}
Пример СДНФ:{{Определение|definition = Формула <tex>f(x,y,z) = (x \vecland \overline{xy}\land z)</tex> от n переменных называется '''совершенно дизъюктивной нормальной формой (СДНФ) ''', если <tex>f\lor (x \land y \land \vec xoverline{z})</tex> является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция <tex>n</tex> переменных <tex>x_1</tex>, <tex>x_2</tex>,...,<tex>x_n</tex>, причем на <tex>i</tex>-ом месте этой конъюнкции стоит <tex>i</tex>-ый терм.}} ==Теорема об СДНФ==
{{Теорема
}}
==Алгоритм построения СДНФ по таблице истинности==
# * В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1.# * Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу : если значение некоторой переменной есть 1, то в конъюнкцию включаем саму переменную, иначе ее отрицание.# * Все полученные конъюнкции связываем операциями дизъюнкции. ==Примеры СДНФ для некоторых функций==Стрелка Пирса: <tex> x \downarrow y = (\overline{x} \land \overline{y})</tex> Медиана трёх: <tex>f(x,y,z) = (x \land y \land z) \lor (\overline{x} \land y \land z) \lor (x \land \overline{y} \land z) \lor (x \land y \land \overline{z})</tex> == Ссылки ==* [http://ru.wikipedia.org/wiki/%D0%A1%D0%94%D0%9D%D0%A4 Википедия — свободная энциклопедия]
