Многочлен Жегалкина и действительный

Задание двоичных функций формулами

Пусть имеется некоторый класс (т.е. множество) двоичных функций K. Он может быть как конечным, так и бесконечным. Обозначим через f₁, f₂,..., входящие в него функции, и пусть X = {x₁, x₂,...} множество двоичных переменных. Дадим индуктивное определение формулы над классом K.

1. Символ переменной x_i, x_iÎX есть формула над K.

2. Если f –обозначение некоторой функции от m переменных из класса K и Ф₁,..., Ф_m - формулы над K то запись Ф = f(Ф₁,..., Ф_m) есть формула над K

Таким образом, формулы – это записи, в которых используются символы переменных и функций из K. Если необходимо подчеркнуть, от каких переменных зависит формула Ф, то используют обозначение Ф(x₁,...,x_n), где x₁,...,x_n - это все переменные, участвующие в задании формулы Ф.

Установим теперь связь между формулами и двоичными функциями. Сначала заметим, что для произвольного набора значений переменных, входящих в формулу, можно, используя индуктивных характер определения, вычислять ее значение на этом наборе. Действительно, если значение формул Ф₁,..., Ф_m, входящих в формулу Ф = f(Ф₁,..., Ф_m), уже подсчитаны и равны соответственно b₁,..., b_m, b_iÎF₂,то значение формулы Ф равно значению функции f(b₁,..., b_m). Поставим в соответствие каждой формуле Ф(x₁,...,x_n) функцию f_Ф(x₁,...,x_n), зависящую от тех же переменных, значения которой при всех значениях переменных совпадают со значениями формулы Ф(x₁,...,x_n).

Легко видеть, что одна и та же формула может быть использована для записи целого ряда функций. Например, формула x₁ соответствует функциям

x₁	f₁

x₁	x₂	f

x₁	x₂	x₃	f

и.т.д. Поэтому естественным оказывается следующее определение.

Определение 1.3.1 Под функциями, реализуемыми формулой Ф понимается функция f_Ф, а также все функции, которые получаются из f_Ф удалением или добавлением несущественных переменных.

С другой стороны, одной функции может соответствовать множество различных формул. Например, рассматриваемые выше функции могут быть заданы любой из следующих формул:

x₁, x₁ ×(x₁x₂), x₁(x₁× x₂), x₁(x₂× ),...

Чтобы учесть эту неоднозначность введем понятие равносильности

формул.

Определение 1.3.2. Две формулы Ф₁ и Ф₂ называются равносильными (обозначается Ф₁= Ф₂), если они реализуют одинаковые множества функций.

Замечание 1.3.3. Заметим, что для проверки равносильности формул Ф₁ и Ф₂ достаточно добавить к функции те переменные, которые входят в Ф₂, но не входят в формулу Ф₁, а к функции добавить переменные из Ф₁, которые не входят в формулу Ф₂, а затем сравнить таблицы полученных функций.

Приведем два свойства, облегчающих проверку равносильности формул. Для их формулировки нам потребуется понятие подформулы.

Определение 1.3.4. Подформулой формулы Ф называется сама формула Ф; подформулой формулы f(Ф₁,..., Ф_m) называется она сама, а также все подформулы формул Ф₁,..., Ф_m.

Свойство 1.3.5. Если Ф₁ - подформула формулы Ф, и Ф₁ равносильна Ф₂, то подформула Ф’, полученная из Ф путем замены Ф₁ на Ф₂ будет равносильна формуле Ф.

Свойство 1.3.6. Если формулы Ф₁ и Ф₂ равносильны, то, подставив одновременно в них вместо некоторых переменных любые формулы, получим в результате также равносильные формулы.

Основные способы задания двоичных функций.

(продолжение)

§2.1 нормальные формы двоичных функций.

Всюду в этом параграфе рассматриваются формулы над классом . Обозначим через функцию

Очевидно, что тогда и только тогда, когда ,

Определение 2.1.1 Элементарной конъюнкцией называются формулы вида , где все переменные различны. Рангом элементарной конъюнкции называется число входящих в неё переменных.

Непосредственно из определения 2.1.1 получаем, что элементарная конъюнкция принимает единичное значение в том и только том случае, когда , . Этот факт запомним как свойство элементарных конъюнкций.

Определение 2.1.2. Дизъюнктивной нормальной формой (ДНФ) называется формула вида , где дизъюнкция берется по некоторым наборам , и , .

Обозначим через функцию, полученную из функции фиксацией первых переменных значениями . Из следующей теоремы вытекает, что любую двоичную функцию можно задать с помощью ДНФ.

Теорема 2.1.3 (о разложении функции). При любом , , двоичную функцию можно представить в виде:

(2.1.4)

Доказательство. Покажем, что функция, стоящая в левой и правой части равенства 2.1.4, принимает одинаковое значение при одинаковых значениях переменной. Пусть. Тогда в силу свойств элементарных конъюнкций значение функции из правой части равно = . Теорема доказана.

Следствие 2.1.5

(2.1.6)

Доказательство. Следует из теоремы 2.1.3, если положить

Следствие 2.1.7

(2.1.8)

Доказательство. Вытекает из следствия 2.1.5 при перенумерации переменных.

Замечание 2.1.9. Разложение (2.1.6) называется разложением Шеннона.

Следствие 2.1.10

(2.1.11)

Доказательство. Следует из теоремы 2.1.3, если положить .

Замечание 2.1.12. В разложении 2.1.11 можно опустить все элементарные конъюнкции, которым соответствуют нулевые значения функций. Полученная в результате формула имеет вид:

(2.1.13)

Определение 2.1.14. Равенство (2.1.13) называется совершенной ДНФ (СДНФ) функции .

Как построить СДНФ функции ?

СДНФ двоичной функции легко построить по ее табличному заданию. С этой целью для каждого набора аргументов , на котором функция принимает единичное значение, строится элементарная конъюнкция ранга по правилу:

(2.1.15)

Затем берется дизъюнкция всех построенных элементарных конъюнкций. Приведём пример:

Пример 2.1.16. Пусть функция задана следующей таблицей:


0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

Таблица 2.1.17

Построим для неё СДНФ:

Поэтому:

Заметим, что СДНФ является частным случаем ДНФ. В ней все элементарные конъюнкции имеют ранг .

Отличительной особенностью СДНФ является то, что она однозначно определяется по функции . Действительно, все элементарные конъюнкции в ней находятся во взаимно-однозначном соответствии с векторами из области истинности функции: .

В отличие от СДНФ, ДНФ не однозначно соответствует функции. Так функция из предыдущего примера может быть записана в виде следующих ДНФ:

Аналогично ДНФ вводятся конъюктивные нормальные формы (КНФ). Они являются конъюнкциями элементарных дизъюнкций и имеют вид , где конъюнкция берется по некоторым наборам , , . Как и в случае СДНФ можно показать, что функции соответствует однозначно определенная КНФ(называемая совершенная КНФ), в которой все элементарные дизъюнкции имеют ранг . Её можно получить из СДНФ функции : с помощью соотношений: , . Из свойств 1.3.5 и 1.3.6 равносильных формул имеем:

==.

СКНФ функции легко строится по её табличному зданию. Для функции , заданной таблицей 2.1.17, получаем:

Поэтому

многочлен двоичной функции.

Будем рассматривать формулы над классом

Определение 2.2.1. Многочленом Жегалкина (приведенным многочленом) называется представление двоичной функции формулой вида:

, где .

Теорема 2.2.2. Для каждой двоичной функции существует единственный многочлен Жегалкина.

Доказательство. Покажем, что по таблице функции однозначно определяются коэффициенты её многочлена Жегалкина. Воспользуемся методом неопределенных коэффициентов. Будем последовательно вычислять значения искомого многочлена на наборе из одних нулей, затем на наборе с одной единицей, затем – с двумя, и т.д. В результате получим систему:

Из первого уравнения находим , из второго ,…, из - ,

из - ,…, из последнего . Теорема доказана.

Определение 2.2.3. Конъюнкции , входящие в многочлен Жегалкина, называются одночленами. Степенью одночлена называется число входящих в него переменных (ранг конъюнкции). Степенью нелинейности (порядком) многочлена Жегалкина функции (обозначается ) называют максимальную из степеней входящих в него многочленов.