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

Лекция №1

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

§1.1 Табличный способ задания

Определение 1.1.1 Двоичной функцией от n (n ³ 1) переменных называется функция f(x1, ..., xn), аргументы и значения которой выбираются из множества F2={0;1}, т. е. f:
® F2, где = {a=(a1, ... ,an) | aiÎF2, iÎ(1,... ,n)}

Замечание 1.1.2 Двоичные функции от n переменных также называют булевыми (булевскими) функциями от n переменных или n –местными булевыми функциями.

На множестве определим так называемый лексикографический порядок, т. е. для любого двоичного набора

определим его номер

N(a) = a1×2n-1 + a2×2n-2 +...+ an-1×21 + an×20

Тогда двоичная функция однозначно может быть задана следующей таблицей

таблица 1.1.3

Номер набора	x1 ... xn-1 xn	f(x1, ..., xn)
0	0...0 0	f(0, ..., 0,0)
1	0...0 1	f(0, ..., 0,1)
. . .	. . .	. . .
2n-2	1...1 0	f(1, ..., 1,0)
2n-1	1...1 1	f(1, ..., 1,1)

При указанной договоренности о расположении наборов из функция однозначно определяется набором - столбцом значений. Отсюда непосредственно вытекает справедливость следующего утверждения.

Утверждение 1.1.4 Число двоичных функций от n переменных

равно

Перечислим все двоичные функции от одной и двух переменных. Имеется четыре функции от одной переменной

Таблица 1.1.5

x1 \ f	f0	f1	f2	f3
0	0	0	1	1
1	0	1	0	1
Условное обозначение	0	x1		1

Функции f0 и f3 не зависят от значения переменной x1 и называются константными ( f0(x1) º 0, f3(x1) º 1). Функция f1(x1) = x1 называется тождественной функцией, а функция f2(x1) =
называется отрицанием.

Функций от двух переменных – шестнадцать.

Таблица 1.1.6

x1, x2\ f	f0	f1	f2	f3	f4	f5	f6	f7
0 0	0	0	0	0	0	0	0	0
0 1	0	0	0	0	1	1	1	1
1 0	0	0	1	1	0	0	1	1
1 1	0	1	0	1	0	1	0	1
Обозначение	0	x1 x2		x1		x2	x1 x2	x1 x2

x1, x2\ f	f8	f9	f10	f11	f12	f13	f14	f15
0 0	1	1	1	1	1	1	1	1
0 1	0	0	0	0	1	1	1	1
1 0	0	0	1	1	0	0	1	1
1 1	0	1	0	1	0	1	0	1
Обозначение	x1x2	x1~x2				x1 x2	x1| x2	1

Важнейшими из них являются:

f1 - конъюнкция (x1 x2, x1 & x2, x1x2)

f6 - сложение по модулю 2 (x1 x2 )

f7 - дизъюнкция(x1 x2)

f8 - функция Пирса (x1x2)

f13 - импликация (x1 x2)

f14 - функция Шеффера (x1| x2)

Определение 1.1.7 Переменная xi , или i-ая переменная двоичной функции f(x1,... , xn) называется существенной переменной функции f(т. е. функция f существенно зависит от xi), если существует набор

(a1,..., ai-1, ai+1,..., an) Î такой, что

f (a1,..., ai-1,0, ai+1,..., an)¹ f (a1,..., ai-1,1, ai+1,..., an)

В противном случае переменная xi называется несущественной (фиктивной) переменной функции f.

Так, среди функций от двух переменных имеется ровно десять функций, существенно зависящих от всех своих переменных.

Число двоичных функций от n переменных растет с увеличением n чрезвычайно быстро, например, при n £ 8 оно равно

Таблица 1.1.8

n	число функций от n переменных
1	2
2	16
3	256
4	65536
5
6	> 1.8 ×1019
7	> 3.4 ×1038
8	> 1.1 ×1077

С табличным заданием функции непосредственно связан такой ее параметр, как вес.

Определение 1.1.9 Множество двоичных наборов

{(a1, ... ,an) Î| f(a1, ... ,an) = 1}, на которых функция f принимает значение 1, называется областью истинности функции f.

Мощность области истинности функции f называется весом функции f и обозначается ||f||.

Очевидно, что 0£ ||f|| £ 2n, причем равенства достигаются лишь для функций-констант 0 и 1. Если ||f|| = 2n-1, то функция f называется равновероятной.

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

§1.2 Геометрический способ задания

Под геометрическим способом задания двоичной функции f(x1, ... ,xn) понимается выделение тех вершин n –мерного двоичного куба, на наборах координат которых функция принимает единичное значение. На рис. 1.2.1 приведены двоичные кубы размерностей n = 0, 1, 2, 3.

Рис. 1.2.1

Выделим среди множества вершин n-мерного куба те, на наборе координат которых функция принимает единичное значение. Например, функции, заданной таблицей 1.2.2 соответствует геометрическое задание, изображенное на рис. 1.2.3

Таблица 1.2.2

x1	x2	x3	f	Рис. 1.2.3
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

Часто по геометрическому заданию функции строят граф связности вершин n-мерного куба, соответствующий данной функции. Для этого сначала отмечают те ребра, у которых оба конца выделены, т. е. соответствующие вершины лежат в области истинности. Затем все остальные ребра и вершины, не лежащие в области истинности, отбрасывают. Так функции, изображенной на рис. 1.2.3, соответствует граф связанности вида

Рис 1.2.4

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

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

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

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

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

Установим теперь связь между формулами и двоичными функциями. Сначала заметим, что для произвольного набора значений переменных, входящих в формулу, можно, используя индуктивных характер определения, вычислять ее значение на этом наборе. Действительно, если значение формул Ф1, ..., Фm, входящих в формулу Ф = f(Ф1, ... , Фm), уже подсчитаны и равны соответственно b1, ..., bm, biÎF2, то значение формулы Ф равно значению функции f(b1, ..., bm). Поставим в соответствие каждой формуле Ф(x1, ... ,xn) функцию fФ(x1, ... ,xn), зависящую от тех же переменных, значения которой при всех значениях переменных совпадают со значениями формулы Ф(x1, ... ,xn).

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

x1	f1
0	0
1	1

x1	x2	f
0	0	0
0	1	0
1	0	1
1	1	1

x1	x2	x3	f
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

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

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

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

x1, x1 ×(x1 x2), x1 (x1× x2), x1 (x2× ), ...

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

формул.

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

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

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

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

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

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

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

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

§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	0 1 0 1 0 0 1 1

Таблица 2.1.17

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

Поэтому:

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

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

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

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

==.

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

Поэтому

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

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

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

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

, где .

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