lec07_1

2 = { , }

докажем, что любую БФ можно так представить. Воспользуемся теоремой 7.1:

даны и полная 1, если из 1 может быть выражена через , то и полная. 1 – система сравнения.

В качестве системы сравнения 1 выберем α, = 2:

1 = { , &, } – функционально полная.

Выразим & через { , } (закон двойственности де Моргана):

1 & 2 = 1 2

2 полная.

11

3 = {&, }

Следует из полноты 2 = { , } согласно теореме ?

согласно теореме 7.2 о функциональной полноте системы двойственных функций, здесь ( * = &).

Доказательство (формально):

1 2 = 1 & 2

12

4 = {|} – штрих Шеффера.

1| 2 = 1 2

Возьмем в качестве системы сравнения: 1 = {&, }

= x | x = & = ;

1 & 2 = 1 | 2 = (x1|x2) | x1 | x2

Таким образом, 4 - функционально полная.

13

5 = { } – стрелка Пирса.

Следует из полноты 4 = {|} согласно теореме	?
согласно теореме 7.2, здесь (|* = ).

Доказательство (формально относительно 3):

1 2 = 1 2 = 1 2= x x = = ;

14

6 = { , &, 1} – система Жегалкина.

Доказательство (формально).

относительно 3 = {&, }:

= x 1 = 1 1 = 0 =1 2 = 1 2 & 1 2

относительно 2 = { , }:

= x 1

1 2 = 1 & 2 = (x1 1)(x2 1) 1 = x1 x2 x1x2

15

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

С использованием ФПС логических элементов можно построить комбинационную схему, реализующую любую, сколь угодно сложную, булеву функцию.

!!! Сверхзадача: возможно любые арифметические операции

проводить с помощью булевых функций	?

Т.к. БФ представима в 4, то если устройство, реализующее (|), то можно сделать ВУ, которое будет выполнять любую операцию.

16

Часть 3.

Алгебра Жегалкина.

Алгебра Жегалкина - совокупность всех булевых функций, на которых введены операции: , &, 1.

Свойства алгебры Жегалкина.

1) Коммутативность:

1 2 = 2 1.

2)Ассоциативность: ( 1 2) 3 = 1 ( 2 3).

3)Дистрибутивность:

	1( 2 3) = 1 2 1 3.
4)	x x = 0.
5)	x 1 = .

6) 1 2 = 1 & 2 = (1 1)&(2 1) = ( 1 1)(2 1) 1 = = 1 2 1 2 1 1 = 1 2 1 2.

18

Одночленом называется произведение переменных		… , в котором нет
	1

повторяющихся сомножителей ( элементарной конъюнкции).

Многочленом Жегалкина называется двоичная сумма одночленов, в которой нет одинаковых слагаемых.

Многочлен Жегалкина (МЖ) – самый общий, разумный вид многочлена.

В общем случае МЖ имеет вид:

(x1, x2, … xn) = a0 a1 x1 … an xn an x1 x2 an+1 x1 x3 … = … an+k xn-1 xn … an+m x1x2 … xn,

где a0, a1, ..., an+m – коэффициенты полинома и представляют собой логические константы (0 или 1). Количество ai при одночлене с k сомножителями - число сочетаний из n по k: Cnk.

19

Теорема о единственности МЖ представления БФ.

Теорема 7.3.

Любая булева функция от n переменных (x1,x2, … xn) может быть представлена в виде МЖ и притом единственным образом.

Доказательство:

Докажем, что БФ (x1,x2, … xn) МЖ. Представим в виде какойнибудь ДНФ (СДНФ нельзя, т.к. «0» непредставим в виде СДНФ). В этой ДНФ заменим все , на операции Жегалкина, что возможно в силу полноты системы Жегалкина. Раскрываем все скобки и приводим подобие. Получаем МЖ.

20