Разложение функции алгебры логики по переменным. СДНФ, СКНФ. Полином Жегалкина.1. Метод равносильных преобразований. Используется для функций, заданных формулой. Метод состоит в выполнении следующих действий. 1) В формуле все функции, кроме суммы Жегалкина и эквиваленции, выражаются через отрицание, конъюнкцию и дизъюнкцию. Эквиваленция заменяется отрицанием операции 2) Дизъюнкция исключается с помощью закона Моргана: 3) Отрицание исключается с помощью свойства суммы Жегалкина: 4) Раскрываются скобки, приводятся подобные с помощью законов:
Пример. 2. Метод неопределенных коэффициентов. Используется для функций, заданных таблицей. Метод состоит в том, что сначала записывается полином Жегалкина для заданной функции в общем виде с неопределенными коэффициентами, затем эти коэффициенты определяются на основе таблицы значений функции от конъюнкции наименьшего ранга к конъюнкциям больших рангов. Пример. Пусть функция задана таблицей 2.14. Запишем полином Жегалкина для f: f (
f (0,0) = f(1,0) = Аналогично, f(0,1) = f(1,1) =
Теперь можно записать выражение (2.5) с определенными коэффициентами: f ( Теорема.Любая функция алгебры логики представима в виде полинома Жегалкина единственным образом с точностью до порядка следования слагаемых. Разложение функции алгебры логики по переменным. СДНФ, СКНФ. Полином Жегалкина.
Логической степенью переменной х называется выражение Другими словами, логическая степень – выражение, которое обозначает переменную или ее отрицание.
Из определения логической степени следует, что На основании этого можно определить следующее общее свойство логической степени: xs=1 тогда и только тогда, когда x=s (соответственно xs=0Û x≠s). Рассмотрим набор переменных {x1,..,xn}. Конъюнкцией (дизъюнкцией) над множеством переменных {x1,..,xn} называетсялюбое выражение вида Рангом конъюнкции (дизъюнкции) над множеством переменных {x1,..,xn} называетсяколичество попарно различных переменных в конъюнкции (дизъюнкции). Пример. Рассмотрим набор переменных {x1,x2,x3,x4}. Тогда Конъюнкция (дизъюнкция) над множеством переменных {x1,..,xn} называется элементарной, если все переменные в ней попарно различны. Элементарную конъюнкцию (дизъюнкцию) над множеством переменных {x1,..,xn}, называют совершенной , если она имеет ранг n. Иными словами, совершенная конъюнкция (дизъюнкция) – это такая, в которой присутствуют все переменные из рассматриваемой совокупности, причем по 1 разу. Пример.
Конъюнкцию (дизъюнкцию) над множеством переменных {x1,..,xm} можно обозначать K(D) или Ki(Di). Дизъюнктивной (конъюнктивной) нормальной формой называется формула вида K1ÚK2Ú…ÚKl или Пример.
Дизъюнктивная (конъюнктивная) нормальная форма называется совершенной дизъюнктивной(конъюнктивной) нормальной формой или СДНФ(СКНФ),если каждая конъюнкция (дизъюнкция) в ней является совершенной. Пример. Для набора переменных {x1,x2,x3} Теорема(о разложении функции алгебры логики по m переменным). Каждую функцию алгебры логики f(x1,..,xn) для любого m≤n следующее можно представить в следующей форме :
Это представление называется разложением функции по m переменным x1,..,xn . Доказательство. Подставим вместо переменных x1,..,xn любые конкретные значения a1,..,anÎE2. Тогда в левой части равенства (2.1) получим f(a1,..,an), в правой Тогда рассматриваемое выражение можно преобразовать к виду
Тем самым равенство доказано. Следствие ( разложение функции алгебры логики по всем переменным). Для любой функции алгебры логики, не тождественно равной 0, справедливо разложение:
Это разложение называется совершенной дизъюнктивной нормальной формой (СДНФ) функции f(x1,..,xn). Доказательство. В равенстве (2.1) положим m=n, получим :
Теорема позволяет функции с большим числом переменных выразить с помощью формул над функциями с меньшим числом переменных.
Пример.
Рассмотрим функцию эквиваленции (табл.2.12). Найдем ее разложение по переменной x1 и по всем переменным. Согласно (2.1), получим
По табл.2.12 функции f(x1,x2) определяем, что f принимает значение 1 на двух наборах (s1,s2) значений переменных – на наборах (0,0) и (1,1). Отсюда, согласно (2.2),
Теорема.Для любой функции алгебры логики, не тождественно равной 1, справедливо следующее разложение:
Это разложение назовем совершенной конъюнктивной нормальной формой (СКНФ) функции f(x1,..,xn). Доказательство. Докажем теорему, используя принцип двойственности.
Рекомендуемые страницы: |