2.3 Понятие базиса и функционально-полного базиса

Исследование логических функций двух переменных показало, что возможно выделение некоторого подмножества Y' множества Y={y0,y1,..y15}, с помощью которого можно выразить любую БФ от произвольного числа аргументов. Такие подмножества называют функционально полным базисом. Построить функции большего числа переменных, используя только функции двух переменных, можно с помощью операций композиции, под которыми понимается подстановка одних функций вместо переменных в другие функции. Такая подстановка возможна в силу того, что области значений функций и переменных совпадают (0 и 1).

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

4. Основные аксиомы и тождества алгебры логики

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

//x=x		Ассоциативный закон:	xvyvz=(xvy)vz	x&y&z=(x&y)&z
x&0=0	xv0=x	Коммутативный закон:	xvy=yvx	x&y=y&x
x&1=x	xv1=1	Дистрибутивный закон:	(xvy) & z=x&z v y&z	x&y v z=(xvz)&(yvz)
x&x=x	xvx=x	Законы поглощения:	xvx&y=x	(xvy)&x=x
x&/x=0	xv/x=1	Законы дуальности (теоремы д-Моргана):	___ _ _ xvy = x&y	___ _ _ x&y=xvy

Клод Шенон предложил обобщение теорем дуальности, позволяющее отыскивать инверсию любой функции f(X), где X=(xn,..x1):

________ _

f(X/v,&)=f(X/&,v). (1.7)

В соответствии с 1.7 инверсию любой функции можно получить взаимной заменой переменных и их инверсий и операций дизъюнкции и конъюнкции.

2. Способы задания Булевых функций

3.1 Описательный способ:

Пример 1: функция E(x) — целая часть числа x. Вообще через E(x) = [x] обозначают наибольшее из целых чисел, которое не превышает x. Иными словами, если x = r + q, где r — целое число (может быть и отрицательным) и q принадлежит интервалу [0; 1), то [x] = r. Функция E(x) = [x] постоянна на промежутке [r; r+1) и на нем [x] = r.

Пример 2: функция y = {x} — дробная часть числа. Точнее y ={x} = x - [x], где [x] — целая часть числа x. Эта функция определена для всех x. Если x — произвольное число, то представив его в виде x = r + q ( r = [x]), где r — целое число и q лежит в интервале [0; 1), получим {x} = r + q - r=q

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

3.2 Аналитический метод:

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

N	x2 x1 x0	y
0	0 0 0	0
1	0 0 1	1
2	0 1 0	1
3	0 1 1	0
4	1 0 0	1
5	1 0 1	0
6	1 1 0	1
7	1 1 1	0

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

Логическая функция записывается в виде математического выражения. Предпочтительно использование канонических форм записи в виде дизъюнктивной или конъюнктивной форм. Рассмотрим эти формы записи.

Минтермом или конституентой единицы называется функция n переменных:

~ ~ ~

mi (x_n,x_n-1 ..x₁)=x1&x2&..&xn,

~ __

где xp - т.н. первичный терм, принимающий значение xp или xp, а i - номер терма соответствующий двоичному коду, построенному на значениях первичных термов входящих в выражение xp ставится в соответствие 1, а /xp - 0.

Видно, что имеется 2ⁿ различных минтермов для n переменных. Минтермы обладают следующими свойствами:

Минтерм принимает единичное значение лишь на наборе соответствующем его номеру;

Минтермы взаимно ортогональны, т.е. произведение любых минтермов с разными номерами равно 0;

Сумма всех минтермов функции n переменных равна 1.

Макстермом или конституентой 0 называют функцию n переменных:

~ ~ ~

Mi(x_n,x_n-1,..x₁)=x_n v x_n-1 v..v x₁.

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