FINISH (675729), страница 6

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

Текст из файла (страница 6)

К функциям не 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х₂

у=х₁Åх₂

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

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

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

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

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

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

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

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

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

Пример :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

1)Элементы 1,2,3 образуют булев базис.

2)Элементы 1 и 2 или 1 и 3 образует сокращенный(неполный)

булев базис.

3)Элементы 4 или 5 образуют универсальный базис.

4)Элементы 3 и 7 образуют базис Жегалкина.

Функции элементов 6 и 7 совпадают при наличии только двух входов.

Понятие двоичного сигнала.

Способы его кодирования.

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

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

1)Позитивное кодирование (положительное)

высший уровень сигнала - 1 ,низший - 0

2)Негативное кодирование (отрицательное)

высший уровень сигнала - 0 ,низший - 1

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

Понятие логической системы.

Типы логических систем.

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

Соединения логических элементов в рамках единой логической системы должны удовлетворять следующим правилам:

1)К любому входу логического элемента могут быть подключены:

a) выход любого другого логического элемента( в частном случае ,того же самого)

б) входной сигнал (входная переменная)

в) логическая константа(0 или 1)

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

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

Логические схемы разделяются на два типа :

1)Комбинационные

2)Последовательносные

В комбинационных схемах значение выходного сигнала в любой момент времени зависит только от комбинации входных сигналов (в этот же момент времени с учетом задержки распространения сигнала по элементам схемы)

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

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

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

Пример комбинационной схемы на элементах булева базиса :

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

Характеристики

Список файлов реферата