Лекции Русакова (1021002), страница 18

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

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

Событие R1 за вычетом содержащегося в немпустого слова представляется также выходными сигналами u и w, а событиеR2 – выходными сигналами v, w. Состоянием 2 или, что то же самое,выходным сигналом w представлено пересечение событий R1 и R2 .Таблица 4.1Таблица 4.2Таблица 4.3166Таблица 4.4Построенные автоматы представляют событие R1 состояниями 1, 2, 3, асобытие R2 – состояниями 2, 4. Событие R1 за вычетом содержащегося в немпустого слова представляется также выходными сигналами u и w, а событиеR2 – выходными сигналами v, w.

Состоянием 2 или, что то же самое,выходным сигналом w представлено пересечение событий R1 и R2 .4.18. Автомат Мили.Широко распространенный на практике класс автоматов Мили получилсвое название по имени американского ученого G. Н. Меаlу, впервыеисследовавшего эту модель.Определение.Автоматом Мили называется автомат, выходные слова которогозависят как от внутренних состояний автомата, так и от значений входныхслов.Оператор автомата Мили (автомата с памятью) полностью описываетсяфункцией переходов q(t +1) и функцией выходов y(t).167Определение.Закон функционирования автомата Мили задается уравнениями:q (t+1) = δ(q(t), x(t)),y (t) = λ(q(t), x(t)), где t = 0,1,2,…Конечный автомат А описывается выражением:А = (Q, X, Y, δ, λ, q0),в котором заданы входной и выходной алфавиты, алфавит состояния, атакже функции переходов и выходов.Выделение в множестве состояний конечного автомата А начальногосостояния q0 объясняется чисто практическими соображениями, связанными,в первую очередь, с необходимостью фиксировать условия начала работыдискретного устройства.

Автомат с выделенным начальным состоянием q0называется инициальным.Многие же задачи можно решать, описывая автомат без начальногосостояния q0:А = (Q, X, Y, δ, λ).Функцию переходов δ и функцию выходов λ определим на ихмножестве пар <состояние – входное слово>.Пусть ξ = xi1 xi2 …xik – входное слово длины k; Е – множество всехконечных входных слов ненулевой длины; ε – входное слово нулевой длины~(пустое слово); δ (qm , ε ) = qm для всех qm ∈ Q .~Тогда функцию заключительного состояния δ (qm , ξ ) определим вмножестве Q × (E ∪ {ε }) следующем образом:168δ (qm , ξ ) = δ (qm , xi1  xik ) =~~()~δ δ (qm , xi1  xik −1 ), xik = δ (qik , xik ), если δ (qij , xij ) определена лл всехqik=j = 1,, k ; qi1 = qm ; не определена в противном случае.4.19.

Автомат Мура.Автомат Мура получил название по имени впервые исследовавшего этумодель американского ученого E. F. Moore.Определение.Автоматом Мура называется автомат, выходные слова которогозависяттолькоотвнутреннихсостоянийавтоматаинезависятнепосредственно от входных слов.Определение.Закон функционирования автомата Мура задается уравнениями:q(t + 1) = δ (q(t ), x(t )),y (t ) = λ (q(t )),t = 0,1,2,...Так как в автомате Мура выходной сигнал зависит только отвнутреннего состояния автомата и не зависит непосредственно от входногосигнала, то он задается одной отмеченной таблицей переходов, в которойкаждому ее столбцу приписан кроме состояния qm еще и выходной сигналyg= λ(qm), соответствующий этому состоянию.169Функциязаключительногосостоянияδ (qm , ξ )~вмножествеQ × (E ∪ {ε }) определяется также, как и для автомата Мили.Функция заключительного выхода λ (qm , o ) модели автомата Мураопределена в множестве Q × (E ∪ {ε }) следующим образом:λ (qm , o ) = λ (qm ) ;~()~~ Л Д (qm , o ) , для всех o ∈ E , если функция Д (qm , o ) - определена;~Л (qm , o ) = ~не определена, если не определена Д (qm , o ).Очевидно, что в модели автомата Мура функция λ (qm , o ) представляетсобой выходной сигнал, который отмечает заключительное состояние.Функция ω (qm , ξ ) – реакция автомата в состоянии qm на входное словоξ = xi ,, xik – не определена, если δ (qm , ξ ) не определена.~~Если δ (qm , ξ ) определена, то:ω (qm , ξ ) = λ (δ (qm , xi1 ))ω (δ (qm , xi1 ), xi 2  xik ) = λ (qi 2 )λ (qi 3 ) λ (qik +1 ) == yi 2 yi 3  yik +1 ,где qi 2 = δ (qm , xi1 ); yij = λ (qij ), j = 2,3,, k + 1.Глава 5.

Теория булевых функций.5.01. Связь булевых функций и схем из функциональных элементов и контактных схем.Определение.170Под функциональным элементом понимается некоторое устройство,внутренняя структура которого нас не интересует и которое обладаетследующими свойствами:1) оно имеет n ≥ 1 упорядоченных отростков сверху – входы и одинотросток снизу – выход (см. рис.

5.1);1 2n…..Рис. 5.1. Функциональный элемент.2)навходыэтогоустройствамогутподаватьсясигналы,принимающие два значения, которые условно обозначают через 0 и 1;3) при каждом наборе сигналов на входах устройство на выходе в тотже момент, в который поступили сигналы на входы, выдает один из сигналов0 или 1;4) набор сигналов на входах однозначно определяет сигнал на выходе,то есть если в различные моменты времени на входы поступили равныенаборы сигналов, то в эти моменты на выходе будет один и тот же сигнал.Заметим, что с каждым функциональным элементом с n выходамисопоставима булева функция от n переменных f (x1, x2,…, xn), определяемая{}следующим образом: входу с номером i i ≤ 1, nставится в соответствиепеременная xi и с каждым набором (а1, а2,…, аn) значений этих переменныхсопоставляется число f (а1, а2,…, аn), равное 0 или 1 в зависимости от того,какой сигнал вырабатывается на выходе при подаче этого набора сигналов навыходы данного функционального элемента.171В этом случае о функции f (x1, x2,…, xn) будем говорить, что данныйфункциональный элемент ее реализует, и такой элемент будем изображатьтак, как показано на рис.5.2.1 2n…..fРис.

5.2. Реализация функционального элемента булевой функцииf (x1, x2,…, xn).Из функциональных элементов определяется схема из функциональныхэлементов (точнее схема из функциональных элементов в соответствующемлогическом базисе), как-то:1) , ∧, ∨;3) , ∨;5) х ∣ у;2) , ∧;4) 1, ∧, ⊕;6) х ↓ уи т.д.Замечания.1.Учитывая,чтосуществуютопределённыеаналитическиепреобразования одного логического базиса в другой, можно изображатьсхемы в любом логическом базисе и преобразовывать их в другие. Базис,состоящий из логических функций , ∧, ∨ называется нормальным; излогических функций , ∨ или , ∧ – неполным нормальным; из стрелкиПирса х ↓ у – базисом Вебба; из штриха Шеффера х ∣ у – базисом Шеффера.Как известно, базис Вебба и базис Шеффера связаны с нормальнымбазисом следующими аналитическими соотношениями:х ∣ у = х ∨ у ; и обратно, х = х ∣ х; х ∨ у = (х ∣ х)∣(у ∣ у);172х ↓ у = х ∧ у ; и обратно, х = х ↓ х; х ∧ у =(х ↓ х) ↓ (у ↓ у).Переход от схемы в нормальном базисе к базисам Шеффера и Веббаи обратно, например, можно отобразить в следующей таблице (таблица 5.1).Таблица 5.1.Нормальный базисБазис ШеффераБазис Веббанеx1xxиx1x2&x2илиx1x21x1y = x1 x2y = x1 ∨ x2x1x2y = x1&x1y = x1 x2&x1&y = x1 x2x2&&y = x1 ∨ x211y = x1 x21x1 ∧ x2x1x2y = x1111y = x1 ∨ x2&2.

Логические функции, кроме их реализации функциональнымисхемами,реализуютсятакжеконтактными,релейно-контактнымииинтегральными схемами.3. Одна и та же схема (функциональная, контактная, релейноконтактная, интегральная) может быть реализована большим или меньшимчислом функциональных базисных элементов (функций), для уменьшения173которых, реализующих одну и ту же булеву функцию, разработана теорияминимизации нормальных форм.5.02. Основные понятия булевых функций.Теорема.n2Число всех различных булевых функций от n аргументов равно 2 .Доказательство:Число различных наборов переменных x1, x2, … , xn, где xi ∈{0,1} равноk=2n.

Так как каждая булева функция принимает только 2 значения: 0 или 1,kk2то число всех булевых функций от n переменных равно 2 = 2 , что итребовалось доказать.Определение.Операцией сложения по модулю два, которая обозначается знаком ⊕,на множестве из двух элементов 0 и 1 называется операция со следующимзаконом композиции:для ∀a имеет местоa ⊕ a ≐ 0 ; a ⊕ 0 ≡ 0 ⊕ a ≡ a .Определение.Элементарнымибулевымифункциямифункции:e1(x) ≡ 0 – нуль-функция;e2(x) ≡ 1 – единица-функция;e3(x) ≡ x – функция x;174называютсяследующиеe4(x) =  x – отрицание x;e5(x, y) ≐ x ∧ y = x & y = x × y = xy – конъюнкция x и y;e6(x, y) ≐ x ∨ y – дизъюнкция x и y;e7(x, y) ≐ x ⇒ y – импликация x и y;e8(x, y) ≐ x ⇔ y – эквиваленция x и y;e9(x, y) ≡ x ⊕ y – сложение по модулю два x и y.Замечания.1. Таблица истинности для элементарных булевых функций имеет вид,представленный в табл.

ниже.Таблица2. Заметим, что1) x ⊕ y =  ( x ⇔ y), то есть e9(x, y) = e4(e8(x, y)), то есть функция x⊕yявляется суперпозицией функций x⇔y и  x.2) x ∨ y ∧ z – суперпозиция функций x ∧ y и x ∨ y , каждая из которыхот двух переменных.3) 0 =  ( x ∨  x); 1= x ∨  x.Приоритеты логических операций.Операция  имеет больший приоритет, чем ∧ ;Операция ∧ имеет больший приоритет, чем ⊕;Операция ⊕ имеет больший приоритет, чем ∨ ;Операция ∨ имеет больший приоритет, чем ⇒;175Операция ⇒ имеет больший приоритет, чем ⇔.Примеры функций, являющихся суперпозициями элементарных функций.g1(x1, x2, x3, x4) ≐ x1 x2 ∨ x3 ⇒  x4g2(x1, x2, x3) ≐ ( x1 ∨ x2 )( x2 ⇒ x3 ⇔ x1 ∨  x2)g3(x1, x2) ≐  ( x1 ⇔ x2 ) ∨ x1 x2 ⇒ x2Определение.Пусть1) u – переменная, при этом пусть u0=  u, а u1=u;2) ai ∈{0,1} , i = 1, n ;3) u1, u2, … , un – переменные, причём не обязательно различные.Тогдаформулаu1a1 ∧ u2a2 ∧ ...

∧ unanназываетсяэлементарнойana1a2конъюнкцией, а u1 ∨ u2 ∨ ... ∨ un – элементарной дизъюнкцией.Примеры.1. Элементарными конъюнкциями будут следующие формулы:x, y,  x, x ∧ y, x1 ∧ x1, x ∧ y ∧ x , x1 ∧ x1 , x1 ∧ x1 ∧ x2 , x1 ∧ x2 ∧ x3 ∧ x4 .2. Элементарными дизъюнкциями будут следующие формулы:x,y, y,x ∨ y,x ∨ x ∨ x, x1 ∨ x1 ∨ x1 , x1 ∨ x1 ∨ x1 ∨ x3 ,x1 ∨ x1 ∨ x2 ∨ y , x1 ∨ x2 ∨ x3 ∨ x4 .Ясно, что каждая элементарная конъюнкция и каждая элементарнаядизъюнкция являются суперпозициями функций  x, x ∧ y и x ∨ y.176Замечание.01Принимая для переменной u , что u = u и u = u , замечаем, чтоua = 1 ⇔ u = a, a∈ {0,1}.В этом случае :1) функцияana1 a2Kn(x1, x2,…, xn) = x1 x2 ...xn(1)такая, что Kn(a1, a2,…, an) = 1 и Kn(b1, b2,…, bn) = 0, если(b1, b2,…, bn) ≠ (a1, a2,…, an);2) функцияana1a2dn(x1, x2,…, xn)= x1 ∨ x2 ∨ ...

∨ xn(2)такая, что dn( a1 , a2 ,..., an ) = 0 и dn(b1, b2,…, bn) = 1, если(b1, b2,…, bn) ≠ ( a1 , a2 ,..., an ).При этом в формулах (1) и (2) все переменные попарно различны.Теорема.Каждая булева функция является суперпозицией следующих функций:отрицания, конъюнкции и дизъюнкции.Доказательство:Первое доказательство.Обозначим множество всех булевых функций через P2. Если даннаяфункция f∈ P2 является константой, равной нулю, то, согласно соотношению0 =  (x ∨ x) или 0 = x ∧ x, утверждение справедливо.

В противном случае,существуют такие наборы (a1, a2,…, an), что f(a1, a2,…, an)=1. Для каждоготакогонабора(a1,a2,…,an)образуемэлементарнуюконъюнкциюx1a1 x2a2 ⋅ ... ⋅ xnan , которая имеет значение 1 только на наборе (a a ,…, a ). Тогда1, 2n177f(x1, x2,…, xn) =∨(a1 ,a2 ,,an )f (a1 ,a2 ,,an )=1x1a1 x2a2 ⋅  ⋅ xnan ,(3)где дизъюнкции берётся по всем таким наборам (a1, a2,…, an), чтоf(a1, a2,…, an) = 1. Так как правая часть равенства (3) является суперпозициейтребуемых функций, то теорема доказана.Второе доказательство.Если функция f∈ P2 является константой равной 1, то, согласно1= x ∨ x или 1= (x ∧ x), утверждение справедливо.

В противном случае,существуют такие наборы (a1, a2,…, an), что f(a1, a2,…, an) ≠ 1, или, что то жесамое, f(a1, a2,…, an) = 0. Таким образом, функция f(x1, x2,…, xn) может бытьпредставлена в виде∧f(x1, x2,…, xn) =( a1 ,a2 ,...,an ),f ( a1 ,a2 ,...,an ) =0( x1a1 ∨ x2a2 ∨ ... ∨ xnan ),(4)где конъюнкция берётся по всем таким наборам (a1, a2,…, an), чтоf(a1, a2,…, an)=0. Правая часть равенства (4) опять, как и в первомдоказательстве, является суперпозицией требуемых функций.

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

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