& & V y
&
x --- &
---
__ &
&
З
З
6д)
S\X | 00 | 01 | 10 | 11 |
S0 | S0/0 | S0/1 | S0/1 | S0/0 |
s(t) |
|
| y(t) | s(t+1) |
0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 | 0 |
0 | 1 | 0 | 1 | 0 |
0 | 1 | 1 | 0 | 0 |
1 | 0 | 0 | -- (0) | -- (0) |
1 | 0 | 1 | -- (0) | -- (0) |
1 | 1 | 0 | -- (0) | -- (0) |
1 | 1 | 1 | -- (0) | -- (0) |
Автомат без памяти s(t)
0,
&
&
s(t) |
|
|
|
| s(t+1) |
0 | 0 | 0 | 0 | 1 | 0 |
0 | 0 | 1 | 0 | 0 | 0 |
0 | 1 | 0 | 0 | 1 | 0 |
0 | 1 | 1 | 1 | 0 | 0 |
1 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 1 | 0 | 0 |
1 | 1 | 0 | 0 | 1 | 1 |
1 | 1 | 1 | 1 | 0 | 1 |
S\X | 00 | 01 | 10 | 11 |
S0 | S0/01 | S0/00 | S0/01 | S0/10 |
S1 | S0/00 | S0/10 | S1/01 | S1/10 |
7а) 
S0 S1
Контрольные задания.
1 Доказать справедливость соотношений. Проиллюстрировать их при помощи диаграмм Эйлера-Венна.
1.1 a) 
b) 
1.2 a) 
b) 
1.3 a) 
b) 
1.4 a) 
b) 
1.5 a) 
b) 
1.6 a) 
b) 
1.7 a) 
b) 
1.8 a) 
b) 
1.9 a) 
b) 
1.10 a) 
b) 
1.11 a) 
b) 
1.12 a) 
b) 
1.13 a) 
b) 
1.14 a) 
b) 
1.15 a) 
b) 
1.16 a) 
b) 
1.17 a) 
,
b)
1.18 a) 
b) 
1.19 a)
b) 
1.20 a) 
b) 
1.21 a) 
b) 
1.22 a) 
b)
1.23 a) 
b) 
1.24 a) 
b) 
1.25 a) 
b) 
1.26 a) 
b) 
1.27 a) 
b) 
1.28 a) 
b) 
1.29 a) 
b) 
1.30 a) 
b) 
2 Для отношения R, заданного на множестве М={1,2,3,4,5,6,7}, построить матрицу отношения, найти область определения Dom(R), область значений Im(R), дополнение 
, обратное отношение 
. Определить, выполняется ли для данного отношения свойства рефлексивности, антирефлексивности, симметричности, антисимметричности, транзитивности:
2.1 
;
2.2 
четно 
;
2.3 
;
2.4 
,
имеют один и тот же остаток от деления
на 2;
2.5 
;
2.6 
четно ;
2.7 делится на 3;
2.8 
;
2.9 
;
2.10 и взаимно просты ;
2.11 
;
2.12 делитель 
;
2.13 
;
2.14 
;
2.15 делится на ;
2.16 нечетно ;
2.17 
;
2.18 
;
2.19 
;
2.20 
четно ;
2.21 , имеют один и тот же остаток от деления
на 3;
2.22 делится на 3;
2.23 
;
2.24 , имеют общий делитель, отличный от 1;
2.25 
;
2.26 
;
2.27 
делится на 4 ;
2.28 
;
2.29 делится на 4;
2.30 
.
3 Для булевой функции 
найти методом преобразования минимальную ДНФ и многочлен Жегалкина. Используя таблицу истинности, построить СКНФ. Построить минимальную релейно-контактную схему. Выяснить принадлежность функции 
классам 
.
3.1 | 3.2 |
3.3 | 3.4 |
3.5 | 3.6 |
3.7 | 3.8 |
3.9 | 3.10 |
3.11 | 3.12 |
3.13 | 3.14 |
3.15 | 3.16 |
3.17 | 3.18 |
3.19 | 3.20 |
3.21 | 3.22 |
3.23 | 3.24 |
3.25 | 3.26 |
3.27 | 3.28 |
3.29 | 3.30 |
4 Орграф задан матрицей смежности 
. Требуется:
а) нарисовать граф; б) выделить компоненты сильной связности;
в) в ассоциированном графе найти эйлерову цепь (или цикл).
4.1 
; 4. 2 
; 4.3 
;
4.4 
; 4.5 
; 4.6 
;
4.7 
; 4. 8 
; 4. 9 
;
4.10 
; 4.11 
; 4.12 
;
4.13 
; 4.14 
; 4.15 
;
4.16 
; 4.17 
; 4.18 
;
4.19 
; 4.20
;
;
4.22
; 4.23
; 4.24
;
4.25
; 4.26
; 4.27
;
4.28
; 4.29
; 4.30
.
5 Нагруженный граф задан матрицей длин дуг 
. Найти:
а) остовное дерево минимального веса;
б) кратчайшее расстояние от вершины 
до остальных вершин графа (используя алгоритм Дейкстры).
5.1 
, 
; 5.2 , 
; 5.3 , 
;
5.4 , 
; 5.5 , 
; 5.6 , 
;
5.7 
, ; 5.8 , ; 5.9 , ;
5.10 , ; 5.11 , ; 5.12 , ;
5.13 
, ; 5.14 , ; 5.15 , ;
5.16 , ; 5.17 , ; 5.18 , ;
5.19 
, ; 5.20 , ; 5.21 , ;
5.22 , ; 5.23 , ; 5.24 , ;
5.25 
, ; 5.26 , ; 5.27 , ;
5.28 , ; 5.29 , ; 5.30 , .
=
; =
;
=
; =
;
=
.
6 Построить конечный детерминированный автомат (определить множества 
, построить таблицу и диаграмму Мура), построить каноническую таблицу, канонические уравнения. Нарисовать схему устройства, используя логические элементы «И», «ИЛИ», «НЕ».
Во всех задачах 
6.1 
6.2 
6.3 
6.4 
6.5 
6.6 
6.7 
6.8 
6.9 
6.10 
6.11 
6.12 
6.13 
6.14 
6.15 
6.16 
6.17 
6.18 
6.19 
6.20 
6.21 
6.22 
6.23 
6.24 
6.25 
6.26 
6.27 
6.28 
6.29 
6.30 
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 |
