Конспект лекций по дискретной математике (стр. 6 из 14)

_____

x₁ x₂=

₁ v ₂

Функциональная полнота системы булевых функций называется минимальной ,если удаление из нее какой-либо функции приводит к нарушению свойства функциональной полноты.

Системы из одной функции S₄=¯(стрелка Пирса)

S₅=|(штрих Шеффера)

которые принято называть универсальным базисом.

2)Базис Жегалкина S₆= {&, Å, 1}

Понятие функциональной полноты системы булевых функций связано с аналогичным понятием для системы логических элементов.

Эта связь заключается в следующем :

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

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

Доказательство функциональной полноты некоторой системы

булевых функций можно осуществлять одним из двух способов:

1) С использованием теоремы о функциональной полноте .

2) С использованием конструктивного подхода .

Теорема о функциональной полноте (Пост - Яблонского).

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

1) cохраняющую константу ноль

2) cохраняющую константу единица

3) линейную функцию

4) монотонную функцию

5) самодвойственную функцию.

Замечательные классы булевых функций.

1. Булева функция называется сохраняющей константу ноль , если на нулевом наборе аргументов она принимает значение равное нулю, то есть f(0,0,0,...,0) = 0;

В противном случае функция относится к классу не cохраняющих константу ноль.

К функциям ,сохраняющим константу ноль относятся

f(x₁,x₂)= x₁ v x₂

f(x₁,x₂)= x_{1 *} x₂

К функциям не cохраняющим константу ноль относятся

f(x)=

и f(x₁,x₂)=x₁~x₂

2.Булева функция называется сохраняющей константу единица , если на единичном наборе аргументов она принимает значение равное единице, то есть f(1,1,1,...,1)= 1;

В противном случае функция относится к классу не cохраняющих константу единица.

К функциям ,сохраняющим константу единица относятся

f(x₁,x₂)= x₁ v x₂

f(x₁,x₂)= x_{1 *} x₂

К функциям не cохраняющим константу единица относятся

f(x)=

и f(x₁,x₂)=x₁Åx₂

3. Булева функция называется линейной если она представима полиномом Жегалкина первой степени.

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

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

fⁿ (x)= K₀ ÅK₁x₁Å...ÅK_n x_n Å...

...ÅK_n+1x₁x₂ ÅK_n+2x₁x₃ Å...ÅK_n+lx_n-1x_n Å...

...

...ÅK_n+mx₁x₂...x_n

K₀ ,K₁ ,K_n+m -являются коэффициентами и представляют собой логические константы нуля или единицы.

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

Полином Жегалкина является линейным (1-ой степени) если все коэффициенты общего полинома ,начиная с K_n+1=K_n+2 =...=K_n+m=0

В отношении функции от 2-х переменных полином Жегалкина имеет вид (линейный): f²(x)=K₀ÅK₁x₁ÅK₂x₂

Примерами линейных функций являются:

y= x₁Åx₂ (K₀=0,K₁=K₂=1)

_____

y= x₁~x₂=x₁Åx₂=1Åx₁Åx₂ (K₀=K₁=K₂)

y=

=1Åx₁ (K₀=K₁=1 ,K₂=0)

Примеры нелинейных функций:

y= x₁*x₂

____

y= x₁lx₂ =x₁*x₂=1Åx₁*x₂

4.Булева функция называется монотонной если при возрастании наборов аргументов она принимает неубывающие значения.

A=(a₁,a₂,...,a_n)>B=(b₁,b₂,...,b_n)

f(A)³f(B)

Между наборами аргументов А и В имеет место отношение возрастания в том и только том случае , если имеет место отношение не убывания для всех компонент этого набора:

___

a_i³b_i (i=1, n )

и по крайней мере для одной компоненты имеет место отношение возрастания.

Примеры наборов ,для которых имеет место отношение возрастания: (1011)>(0011)

(1011)>(0001)

(0001)>(0000)

Пример несопоставимых наборов (1011)и (0111)

В отношении функции от 2-х переменных несопоставимыми являются наборы (01) и (10)

Пример немонотонных функций: y=

y= x₁Åx₂

5.Две булевы функции fⁿ(x) и gⁿ(x) называются двойственными если для любых наборов аргументов выполняется равенство

____

fⁿ(x) =gⁿ(x) то есть функции f и g на противоположных наборах аргументов х и

принимает противоположные значения .

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

x=(0101)

=(1010)

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

Примером самодвойственной функции является : у=

Примеры не самодвойственных функций: у=х₁*х₂

у=х₁vх₂

у=х₁Åх₂

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

К₀ + сохраняет константу ноль ,- не сохраняет константу ноль

К₁ + сохраняет константу единица ,- не сохраняет константу

К_л + линейная ,- нелинейная

К_м + монотонная , - не монотонная

К_с + самодвойственная ,- не самодвойственная

Функция	К0	К1	Кл	Км	Кс
0	+	-	+	+	-
1	-	+	+	+	-
	-
х1*х2	+	+	-	+	-
х1vх2	+	+	+	-
х1Åх2	+	-	+	-	-
х1~х2	-	+	-
х1Dх2	+	-
х1®х2	-
х1|х2	-	-
х1¯х2	-

Конструктивный подход к доказательству функциональной полноты некоторой системы булевых функций.

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

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

Пример :S₅={|}

_ ____

x =x * x= x|x

====

x₁*x₂ = x₁*x₂ =( x₁|x₂)|( x₁|x₂)

______

x₁vx₂=

₁* ₂ =( x₁|x₁)|( x₂|x₂)

Синтез комбинационных схем.

Понятиелогическогоэлемента.

Типовые логические элементы и их обозначения на функциональных схемах.

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

Любой логический элемент характеризуется :

1) Наличием одного или нескольких входов на которые подаются входные сигналы( входные переменные).

2) Наличием выхода ,на котором формируется выходной сигнал

(выходная переменная).

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

К основным типам логических элементов относятся:

1) Инвертор( НЕ)

2) Дизъюнктор (ИЛИ)

3) Конъюнктор (И)

4) Дизъюнкторс отрицанием (ИЛИ - НЕ)

5) Конъюнкторс отрицанием (И - НЕ)

6) Исключительное ИЛИ

(единичный сигнал на выходе имеет место в том и только том случае если на

одном и только одном входе присутствует единичный сигнал)

7) Сумматор по модулю 2