Основные булевы функции.

Основные БФ ДМ играют ту же роль, что и элементарные функции обычной математики.

xy f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16 00 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1- const 0, 2- x₁x₂ 01 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 3- not(x®y), 4- x, 10 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 5- not(y®x), 6-y, 11 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 7- x  y, 8- xy, 9- xy, 10- xy, 11- y, 12- y®x, 13- x, 14- x®y, 15- x/y, 16- const 1. m(x,y,z) – функция согласования (медиант), по количеству 0 и 1 функция m принимает значение исходя из большинства.

Основные булевы тождества. БФ может быть задана формулой. Стройматериалом для функции является: const 0,1 , x,y, ,,,,,,/. Приоритет:  ,, все остальные в порядке следования. Если нужно изменить порядок, то ставят скобки. БФ можно преобразовать, используя основные тождества. Две функции называются тождественными, если они реализуют одну функцию. Пример: ху=ху. Тождеством называется пара тождественных функций, связанных знаком «=».

1. х х=х, х 0=0, х 1=х, х х=0, хх=х, х0=х, х1=1, хх=1, хх=0, х0=х, х1=х, хх=1.

2. х у=у х, хÚу=уÚх, хÅу=уÅх, х(yz)=(xy)z, xÚ(yÚz)= (xÚy) Úz, xÅ(yÅz)=(xÅy) Åz.

3. x(yÚz)=xyÚxz, xÚyz=(xÚy)(xÚz), x(yÅz)=xyÅxz. 4. not(xÚy)= x`y, not(xy)= `xÚ`y.

5. x®y=`xÚy – импликация, xy=xyÚ`x`y – эквивалентность, xÅy=x`yÚ`x y, xy=not(xÚy), x/y=not(xy).

xyÅxÅy=xÚy.

Двойственность. Принцип двойственности.

Функция f^*(x_n) называется двойственной функции f(x_n), если она построена по правилу: f^*(x_n)=not( f(x₁, x₂, …,x_n) )= f(x_n). Чтобы построить f* на нуле, мы должны посмотреть, чему равно значение функции на 1 и инвертировать: f^*(0)= f(1). Столбец функции f^* получается из столбца функции f переписыванием последнего в обратном порядке, одновременно инвертируя двоичные цифры. Очевидно, что (f^*)^*= f. Если функция f= f^*, то она называется самодвойственной функцией. Рассмотрим функции, двойственные к элементарным: (xy)*=xy, 0*=1,1*=0, (xy)*=xy, (x/y)*=xy.

Теорема1: если функция f зависит от переменной xi фиктивно, то и двойственная к функции f зависит от xi фиктивно. Пусть R – система БФ, которые используются для реализации функции f и будем говорить, что f реализована над системой R.

Теорема2(1-й принцип двойственности): если функция f реализована над системой R, то заменой каждого символа операции в f на двойственный получится формула, которая реализует двойственную функцию f*. Заметим, что порядок выполнения действий при замене операций на двойственные сохраняется, поэтому в нужных местах проставление скобок обязательно.

Теорема3: если функция f, то и f **.

Переход от табличного задания функции к аналитическому.

Если мы знаем аналитическое задание функции, то мы всегда может построить ее таблицу значений. Но как наоборот? Поскольку одна и та же функция может быть выражена различной формулой, то прежде всего поставим вопрос: «какие операции мы будем использовать для получения f?» Будем для построения функции f использовать три операции ( ,,). Назовем элементарным произведением(элементарной суммой) конъюнкцию(дизъюнкцию) переменных и их отрицания. Совершенным произведением функции и переменных называется элементарное произведение, удовлетворяющее условиям: а) оно содержит и переменные, и отрицания, б) все переменные различны и в) в произведении не могут содержаться переменные со своим отрицанием.

Аналогично вводится понятие совершенной суммы. Очевидно, что если взять два различных СП(СС), то они отличаются хотя бы одним знаком отрицания, а потому их конъюнкция(дизъюнкция) = 0(1).