ДМ 2012 / Инд. задание к самостоятельной работе 2012 (ДМ РБ) / (Л4) Якимов_ДискретнаяМатематика_МУ

11

Пример – Пусть логическая функция задана выражением

f = x1x4 (x1 x3 x4 )(x2 x3 ) .

Привести логическую функцию в базис И-НЕ, ИЛИ-НЕ: а) приводим функцию к базису И-НЕ:

f = f1 f2 f3 = f1 f2 f3 = f1 ( f2 | f3 ) = f1 ( f2 | f3 ) = f1 ( f2 | f3 ) = f 1 | ( f2 | f3 );

f1 = x1x4 = x1 | x4 ;

f2 = x1 x3 x4 = x1x3x4 = x1x3x4 = x1 | x3 | x4 ;

f3 = x2 x3 = x2 x3 = x2 x3 = x2 | x3 ;

f = (x1 | x4 ) | ((x1 | x3 | x4 ) | (x2 | x3 )) ;

б) приводим функцию к базису ИЛИ-НЕ:

f = f1 f2 f3 = f1 f2 f3 = f1 ( f2 f3 ) = f1 ( f2 f3 ) = f1 ↓( f2 ↓ f3 ) ;

f1 = x1x4 = x1x4 = x1 x4 = x1 ↓ x4 ;

f2 = x1 x3 x4 = x1 x3 x4 = x1 ↓ x3 ↓ x4 ;

f3 = x2 x3 = x2 x3 = x2 ↓ x3 f3 = x2 ↓ x3 ;

f= (x1 ↓ x4 ) ↓ ((x1 ↓ x3 ↓ x4 ) ↓ (x2 ↓ x3 )) .

2.3Задача анализа логической схемы

По заданной схеме требуется определить функцию f, реализуемую данной схемой.

При решении задачи анализа следует придерживаться следующей последовательности действий:

1)заданная схема разбивается по ярусам;

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

12

3)записываются выходные функции каждого элемента в виде формул в соответствии с введенными обозначениями;

4)производится подстановка одних выходных функций через другие, используя входные переменные;

5)записывается получившаяся булева функция через входные переменные.

Пример – По заданной логической схеме (рисунок 3) составить булеву функцию.

Рисунок 3 – Пример логической схемы устройства

Согласно приведенной выше последовательности действий произведем разбиение схемы на ярусы. Пронумеровав получившиеся ярусы, введем обозначения для каждой выходной функции (см. рисунок 3). Запишем все функции, начиная с 1-го яруса:

1) f1 = f21 f22 x4 ;

2) a)	f21 = f31 x2 ; b) f22 = f32 x1 ;
3) a)	f31 =		; b) f32 =		.
		x1		x2 x3
Теперь запишем все	функции, подставляя входные переменные
x1, ..., x4 :

a) f21 = x1 x2 ;

b) f 22 = x1 ( x 2 x 3 ) .

В итоге получим выходную функцию

f = f1 = x1 (x1 x2 ) (x2 x3 ) x4 .

13

2.4 Практические задания

1 Дешифратор управляет семисегментным (сегменты a, b, c, d, e, f, g) индикатором, отображающим символы от 0 до 9, a, b, c, d, E, F (рисунки 4–5).

a

f g b

e c

d

Рисунок 4 – Стандартное обозначение сегментов индикатора

Рисунок 5 – Символы, отображаемые индикатором

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

Таблица 1 – Варианты синтеза логической схемы управления

Базис				Сегмент индикатора
	a	b	c		d		e	f	g
И-НЕ	1	3	5		7		9	11	13
ИЛИ-НЕ	2	4	6		8		10	12	14

2 Синтезировать в базисе И-НЕ (ИЛИ-НЕ) схему для поразрядного сравнения двух двоичных четырехразрядных чисел и выдачи результатов этого сравнения. Для каждой пары сравниваемых разрядов a[n] и b[n] вычисляется сумма по модулю 2 (таблица 2).

Если значения соответствующих разрядов не совпадают, то на выходе устройства появляется высокий потенциал.

14

Таблица 2 – Поразрядное вычисление суммы по модулю 2

a[n]	b[n]	a[n] b[n]	a[n]	b[n]	a[n] b[n]
0	0	0	1	0	1
0	1	1	1	1	0

3 Синтезировать в базисе И-НЕ (ИЛИ-НЕ) дешифратор, представляющий собой устройство, в котором при любой комбинации входных двоичных трехразрядных чисел появляется сигнал единица только на одном из его восьми выходов.

4 Синтезировать преобразователь двоичного четырехразрядного кода в код Грея. При этом коде в процессе счета с приходом следующего импульса меняется сигнал только на одном выходе (таблица 3).

Таблица 3 – Преобразование двоичного кода в код Грея

	Двоичный код (входы)					Код Грея (выходы)
C(22)		B(21)		A(20)	P1		P2		P3
0		0		0	0		0		0
0		0		1	0		0		1
0		1		0	0		1		1
0		1		1	0		1		0
1		0		0	1		1		0
1		0		1	1		1		1
1		1		0	1		0		1
1		1		1	1		0		0

5 Синтезировать в базисе И-НЕ (ИЛИ-НЕ) сумматор для выполнения операции сложения четырехразрядных чисел в двоичном коде. Сложение двух двоичных чисел производится в соответствии с таблицей истинности (таблица 4), где Ai и Bi – значения складываемых двоичных чисел в данном разряде; Si – результат суммирования в данном разряде; Pi, Pi–1 – значения сигналов переноса соответственно в данном и предыдущем разряде.

Таблица 4 – Выполнение операции сложения двоичных чисел

	Вход			Выход
Ai	Bi	Pi–1	Pi		Si
0	0	0	0		0
0	0	1	0		1
0	1	0	0		1
0	1	1	1		0
1	0	0	0		1
1	0	1	1		0
1	1	0	1		0
1	1	1	1		1

6 Синтезировать в базисе И-НЕ (ИЛИ-НЕ) преобразователь двухразрядного двоичного кода в трехразрядный (таблица 5).

15

Таблица 5 – Преобразование двухразрядного кода в трехразрядный

Вход				Выход
a1		a0	b2	b1	b0
0		0	0	0	0
0		1	1	0	1
1		0	0	0	1
1		1	1	1	0

7 Реализовать функции И, ИЛИ и НЕ на логических элементах в базисе И-НЕ (ИЛИ-НЕ).

8 Синтезировать в базисе И-НЕ (ИЛИ-НЕ) устройства, заданные логической функцией:

1)f(x1, x2 , x3, x4) = x1x2 x3 x1x3x4 (x1x2 )(x3x4 ) ;

2)f(x1, x2 , x3, x4) =(x1 x2 )x3x4 ;

3)f(x1, x2 , x3, x4) =(x1x2 ) x3 x4 ;

4)f(x1, x2 , x3, x4) = x1 x2 x3 x4 ;

5)f(x1, x2 , x3, x4) = x1x2 x3x4 ;

6)f(x1, x2 , x3, x4) = x1 x2 x3 x4 x1x2 ;

7)f(x1, x2 , x3, x4) =(x1 x2 )(x3 x4 ) ;

8)f(x1, x2 , x3, x4) = x1x2 x3 x1x2 x4 (x1 x2 )(x3 x4 ) ;

9)f(x1, x2 , x3, x4) = x1x2 x3 x1x2 x3 x4 ;

10)f(x1, x2 , x3, x4) =(x1 x2)x3 x1x2 x3x4 ;

11)f(x1, x2 , x3, x4) =(x1 x2 x3 )(x1 x2 x3x4 ) ;

12)f(x1, x2 , x3, x4) = x1x2 x3x4 ;

13)f(x1, x2 , x3, x4) = x1 x2 x3x4 x1 x2 x3x4 x1x3 ;

14)f(x1, x2 , x3, x4) = x1 (x2 x3 (x1 x4 ) ;

15)f(x1, x2 , x3, x4) = x1(x2 x3 ) x3x4 ;

16)f(x1, x2 , x3, x4) = x1x3x4 x1x2 x2 x4 ;

17)f (x1, x2 , x3, x4 ) = x1x2 x3x4 x1x3x4 ;

18)f (x1, x2 , x3, x4 ) = x1x2 x3x4 x2 x3 x1x2 ;

19)f (x1, x2 , x3, x4 ) = x3x4 x1x2 x4 ;

20)f (x1, x2 , x3, x4 ) = x1x2 x3 x1 x2 x4 ;

21)f (x1, x2 , x3, x4 ) = x1 x1x2 x2 x3 x1x4 ;

22)f (x1, x2 , x3, x4 ) = x1(x2 (x3 x1x4 ) x1x3 ) ;

23)f (x1, x2 , x3, x4 ) = x1x2 (x3 x4 ) x2 x4 ;

24)f (x1, x2 , x3, x4 ) =(x1 x3)x2 x4 (x2 x4 )x1x3 ;

25)f (x1, x2 , x3, x4 ) = x1 x2 x3x4 x2 x3 (x2 x1) .

16

3 Способы задания абстрактного конечного автомата

3.1 Понятие конечного автомата

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

По входному каналу в каждый момент времени t = 1, 2,... в устройство М поступают входные сигналы (из некоторого конечного множества сигналов). Задается закон изменения состояния к следующему моменту времени в зависимости от входного сигнала и состояния устройства в текущий момент времени. Выходной сигнал зависит от состояния и входного сигнала в текущий момент времени (рисунок 6).

Рисунок 6 – Абстрактный конечный автомат

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

Конечным автоматом называется структура A = X; Q; Y; δ; λ , где X,

Q, Y – произвольные непустые конечные множества.

Множество X ={a1, ..., am} называется входным алфавитом, а его

элементы – входными символами, их последовательности – входными словами. Множество Q ={q1, ..., qn} называется множеством состояний, а его

элементы – состояниями. Множество Y ={b1, ..., bp} называется выходным

алфавитом, а его элементы – выходными символами, их последовательности – выходными словами.

Функция δ: X ×Q →Q	называется	функцией	переходов. Функ-
ция λ: X ×Q →Y называется	функцией	выходов,	т. е. δ(a, q) Q;
λ(a,q ) Y | a X ; q Q .

Если в момент времени t = 1, 2,... на вход автомата А = (X; Q;Y; δ; λ)

17

последовательно подаются входные символы x(t) X и при этом автомат находится в состоянии q(t) Q , то под воздействием символа x(t) автомат перейдет в новое состояние q(t +1) Q и выдаст выходной сигнал y(t).

Величины x(t), y(t), q(t), q(t+1) связаны между собой следующими уравнениями:

q(t +1)	=δ(x(t), q(t));	t =1, 2, ..., n, ...
y(t) =λ(x(t), q(t)),

Эти уравнения называются каноническими уравнениями автомата А. С конечным автоматом ассоциируется воображаемое устройство, которое работает следующим образом. Оно может находиться в состоянии из множества Q, воспринимать символы из множества X и выдавать символы

из множества Y.

3.2 Способы задания конечного автомата

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

Табличное задание автомата. Из определения автомата следует, что его всегда можно задать таблицей с двумя входами, содержащей m строк и n столбцов, где на пересечении столбца q и строки a стоят значения функций δ(a, q) , λ(a, q) (таблица 6).

Таблица 6 – Табличное задание автомата

	a			q
		q1	…	qj	…	qn

a1	δ(a , q ) ; λ(a , q )	…	δ(a1, q j) ; λ(a1, q j)	…	δ(a , q	) ; λ(a , q	)
	1 1 1 1				1 n	1 n
…	…	…	…	…		…
ai	δ(ai, q1) ; λ(ai, q1)	…	δ(ai, q j) ; λ(ai, q j)	…	δ(ai, qn) ; λ(ai, qn)
…	…	…	…	…		…
am	δ(am, q1) ; λ(am, q1)	…	δ(am, q j) ; λ(am, q j)	…	δ(am, qn) ; λ(am, qn)

Задание автомата диаграммой Мура. Другой способ задания ко-

нечного автомата – графический. При этом способе состояния автомата изображают кружками, в которые вписывают символы состояний qj (j = 1, ..., n). Из каждого кружка проводится т стрелок (ориентированных ребер), взаимно-однозначно соответствующих символам входного алфавита X ={a1, ..., am}. Стрелке, соответствующей символу ai X и выхо-

дящей из кружка q j Q , приписывается пара ( ai , λ(ai , q j ) ), причем эта

18

стрелка ведет в кружок, соответствующий δ(ai, q j) .

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

Матричный способ задания автомата. Кроме рассмотренных выше способов, произвольный абстрактный автомат может быть описан матрицей соединений. Такое описание – один из способов матричного задания абстрактных автоматов. Матрица соединений автомата является квадратной и содержит столько столбцов (строк), сколько различных состояний имеет рассматриваемый автомат. Каждый столбец (строка) матрицы соединений помечается символом состояния автомата. Если автомат инициальный, то первый слева столбец и первая сверху строка матрицы помечаются символом начального состояния автомата. В клетке матрицы соединений, находящейся на пересечении столбца j и строки i, ставится входной символ a (или дизъюнкция входных символов), под воздействием которого осуществляется переход из состояния i в состояние j. Рядом с входным символом в скобках ставится выходной символ, который выдает автомат, выполняя переход из i-го состояния в j-ое состояние.

Задание конечного автомата системой булевых функций. Сле-

дующий способ задания конечного автомата А = (X; Q; Y; δ; λ), заданного таблицей или диаграммой Мура, состоит в определении системы булевых функций.

Изложим алгоритм этого способа задания.

Шаг 1. Находим числа k, r, s, удовлетворяющие условиям

2k−1 < m < 2k , 2r−1 < n < 2r , 2s−1 < p < 2s ,

где m =| X |, n =|Q |, p =|Y |.

Очевидно, что k, r, s соответственно равны числу разрядов в двоичном представлении чисел m, n, p. Например, если m = 5, n = 17, p = 3, то k = 3, r = 5, s = 2.

Шаг 2. Кодирование состояний, входных и выходных символов автомата.

Каждому q j Q взаимно-однозначно ставим в соответствие двоич-

ную последовательность длины r – двоичный код α(q) = z1z2…zr. Аналогично каждому ai X и каждому bk Y ставим взаимно-однозначно в со-

ответствие двоичные последовательности β(a) = x1x2…xk, γ(b) = y1y2…ys. Отметим, что кодирование состояний, входных и выходных симво-

лов можно провести многими способами. При этом некоторые последовательности (коды) могут оказаться неиспользованными.

Шаг 3. Составляем таблицу 7.

19

Таблица 7 – Кодирование входных, выходных символов и состояний

Код входного

Код текущего

Код следующего

Код выходного

символа β(a)

состояния α(q)

состояния α'(q)

символа γ(b)

x1

x2

…

xk

z1

z2

…

zr

δ1

δ2

…

δr

λ1

λ2

…

λs

0

0

…

0

0

0

…

0

α'2

β1

β2

…

βk

α1

α2

…

αr

α'1

…

α'r

γ1

γ2

…

γs

1

1

…

1

1

1

…

1

Эта таблица содержит k + r + r + s столбцов и 2k+r строк. В первых k + r столбцах выписаны все наборы длины k + r. Каждый такой набор соответствует паре (β, α), где β – код входного символа; α – возможный код некоторого состояния.

Шаг4. Заполнениепоследнихстолбцоввтаблице(таблица7 нашаге3). Для каждой пары (ai, qj), где ai X ; q j Q , находим код β(a) и α(q).

По таблице автомата (или диаграмме Мура) определяем, что

δ(a, q) = q', λ(a, q) = b.

Затем находим код α(q') = α'1 α'2… α'r и код γ(b) = γ1γ2...γs. В строку таблицы, соответствующую набору

β1, β2, …, βk, α1, α2, …, αr,

дописываем набор

α'1, α'2, …, α'r, γ1, γ2, ..., γs.

Шаг 5. Определение системы булевых функций.

После выполнения предыдущего шага может оказаться, что не все строки в таблице заполнены. Это произойдет в том случае, если хотя бы одно из чисел m, n не является степенью 2. Таким образом, функции δ1, δ2, …, δr, λ1, λ2, …, λs окажутся не полностью определенными – на некоторых наборах их значения не определены. Тогда их доопределяют произвольным образом, но, как правило, так, чтобы получившиеся полностью определенные функции удовлетворяли тем или иным условиям оптимальности, например, представлялись минимальными ДНФ.

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

{δ1, δ2, …, δr, λ1, λ2, …, λs}.

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

20

уравнения записываются в координатной форме:

z1(t +1) =δ1(x1(t), ..., xk (t), z1(t), ..., zr (t)) ;

…

zr (t +1) =δr (x1(t), ..., xk (t), z1(t), ..., zr (t)) ; y1(t) =λ1(x1(t), ..., xk (t), z1(t), ..., zr (t)) ;

…

ys (t) =λs (x1(t), ..., xk (t), z1(t), ..., zr (t)) , t = 1, 2, …

Для построения канонических уравнений автомата А необходимо для данной булевой функции найти минимальную ДНФ (дизъюнктивную нормальную форму), которая, вообще говоря, определяется неоднозначно. Аналитический алгоритм построения этой ДНФ следующий.

Шаг 1. Для данной функции f(x1, …, xn) строим совершенную конъюнктивную нормальную форму (СКНФ).

Шаг 2. В построенной СКНФ раскрываем скобки, используя правило:

( A B) (C D) = A C B C A D B D .

Шаг 3. Полученное выражение упрощаем, применяя тождества следующего вида:

K1 K2 K1 = K1 ; K K = K ; K 0 = K ;

K K = 0 ; K 1 =1; K 1 = K ;

K K = K ; K K =1.

В результате получим сокращенную ДНФ, являющуюся дизъюнкцией всех простых импликант данной функции f(x1, …, xn).

3.3 Примеры конечных автоматов

Приведем несколько примеров конечных автоматов. Пример 1. Элемент задержки (элемент памяти).

Элементы задержки представляют собой устройство, имеющее один вход и один выход. Причем значение выходного сигнала в момент времени t совпадает со значением сигнала в предыдущий момент. Схематично элемент задержки можно изобразить следующим образом (рисунок 7).