Teoria Automatów
Wykład 1
Halina Kamionka-
Mikuła
pokój 316
http://www.zmitac.iinf.polsl.gliwice.pl/HKM
/
Teoria Automatów
Wykład 1
Halina Kamionka-
Mikuła
pokój 316
http://www.zmitac.iinf.polsl.gliwice.pl/HKM
/
•
informacje,
•
program przedmiotu,
•
ogłoszenia,
•
wykaz literatury,
•
terminy konsultacji,
są dostępne na stronie:
http://www.zmitac.iinf.polsl.gliwice.pl/HKM
/
Warunki
zaliczenia przedmiotu TA - sem 2
pozytywne zaliczenie dwóch sprawdzianów.
http://www.zmitac.iinf.polsl.gliwice.pl/HKM
/
Jest możliwe zwolnienie z egzaminu TA w sem. 3.
Warunki zwolnienia z egzaminu są podane do
adresem internetowym:
http://www.zmitac.iinf.polsl.gliwice.pl/HKM/
Możliwość przepisania oceny z poprzednich lat
studiów
należy wyjaśnić na początku semestru, którego ocena
dotyczy.
http://www.zmitac.iinf.polsl.gliwice.pl/HKM
/
Wykaz literatury
[1] Kamionka-Mikuła H. Małysiak H., Pochopień B.:
Synteza i analiza układów cyfrowych, WPKJS,
2006.
[2] Kamionka-Mikuła H. Małysiak H., Pochopień B.: Układy cyfrowe -
Teoria i przykłady, Wydanie VII uzupełnione. WPKJS, Gliwice 2004.
[3] Praca zb. pod red. H. Małysiaka: Teoria automatów cyfrowych –
Laboratorium. WPŚl., Gliwice 2004.
[4] Praca zb. pod redakcją H. Małysiaka, B. Pochopienia: Układy
cyfrowe – Zadania. WPŚl., Gliwice 2002.
[5] Praca zb. pod red. H. Małysiaka i J. Siwińskiego: Zbiór zadań
z układów przełączających. WPŚl., Gliwice 2003.
[6] Praca zbiorowa pod kierunkiem H. Małysiaka: Układy
przełączające w automatyce przemysłowej – Zadania. WNT,
Warszawa 1981.
[7] Pochopień B.: Arytmetyka systemów cyfrowych. WPŚl.,
Gliwice 2002.
[8] Siwiński J.: Układy przełączające w automatyce, WNT
Warszawa 1980.
[9] Pieńkos J., Turczyński J.: Układy scalone TTL
w systemach cyfrowych. WKiŁ, Warszawa 1986
[10] Programy dydaktyczne na stronie internetowej:
http://www.zmitac.iinf.polsl.gliwice.pl/HKM/
Wykaz literatury
http://www.zmitac.iinf.polsl.gliwice.pl/HKM
/
Co to jest UKŁAD CYFROWY
?
Układ cyfrowy
(logiczny, przełączający)
wykonuje operacje na zbiorach sygnałów
dyskretnych,
najczęściej
dwuwartościowych.
...
Urządzeni
a
rejestrują
ce
Przykład układu sterowania pracą mieszalnika
Czujniki poziomu:
górny: x
1
.
środkowy: x
2
,
dolny x
3
,
Czujniki temperatury:
x
4
– reagujący na niższą
temperaturę,
x
5
– reagujący na wyższą.
temperaturę.
UKŁAD
CYFROWY
UKŁAD
CYFROWY
x
5
x
4
x
3
X2
x
1
Z
5
Z
4
Z
3
Z
2
Z
1
Jak projektuje
się
układy cyfrowe
?
Teoria Automatów
zajmuje się: analizą i syntezą układów
cyfrowych
x
1
Z
1
x
2
Z
2
x
3
Z
3
x
4
Z
4
x
5
Z
5
Jak opisuje się układ
cyfrowy
?
Rachunek logiczny
zdań
Przykład układu sterowania pracą mieszalnika
Warunki sterowania napełnianiem
zbiornika
poniżej x3:
przez zawór Z4 i dodatkowo:
zaworem Z1 (gdy temperatura jest za
wysoka),
zaworem Z2 (gdy temperatura jest za
niska),
zaworem Z1 i Z2 (gdy temp. jest
pośrednia),
pomiędzy x3 i x2:
jak wyżej tylko bez zaworu Z4,
pomiędzy x2 i x1: jednym lub żadnym
zaworem zależnie od temp:
zaworem Z1 (gdy temperatura jest za
wysoka),
zaworem Z2 (gdy temperatura jest za
niska),
żadnym zaworem (gdy temp. jest
pośrednia),
powyżej x1:
brak napełniania.
Opróżnianie zaworem Z3
wtedy i tylko wtedy, kiedy poziom jest
powyżej x3
i temperatura jest pośrednia.
Opróżnianie zaworem Z5
wtedy i tylko wtedy, kiedy poziom jest
powyżej x1
i temperatura jest różna od pośredniej.
Czujniki poziomu:
górny: x
1
.
środkowy: x
2
,
dolny x
3
,
Czujniki temperatury:
x
4
– reagujący na niższą
temperaturę,
x
5
– reagujący na wyższą.
temperaturę.
Przykład układu sterowania pracą
mieszalnika
Czujniki poziomu:
górny: x
1
.
środkowy: x
2
,
dolny x
3
,
Czujniki temperatury:
x
4
– reagujący na niższą
temperaturę,
x
5
– reagujący na wyższą.
temperaturę.
poziom wody jest powyżej x3
i
temperatura jest
pośrednia
.
Przykład zdań
logicznych
Zawór Z
3
jest otwarty
Przykład iloczynu logicznego zdań
Poziom wody jest powyżej
poziomu zamontowania czujnika
x
3
Temperatura wody jest pośrednia
rachunek log. zdań
algebra Boole’a
prawda
1
fałsz
0
zdanie logiczne A
A
zdanie przeciwne do A
A
iloczyn logiczny zdań: A,B
A B
suma logiczna zdań: A,B
A + B
Albebra Boole’a
Co to jest
Funkcja
przełączająca
?
Funkcja przełączająca (funkcja
logiczna)
F
(
x
1
, ... , x
n
)
F
{
0, 1
}
x
i
{
0, 1
}
i
{
0, 1, .. , n
}
Przykład
Zawór Z
3
jest otwarty
poziom jest powyżej x
3
i
temperatura jest pośrednia
Z
3
=
x
3
•
tp
Z
3
(
x
3
,
tp
)
Zawór Z
3
jest otwarty
wtedy i tylko wtedy,
kiedy
poziom jest powyżej x
3
i temperatura jest
pośrednia.
Zawór Z
3
jest otwarty
poziom jest powyżej x
3
i
temperatura jest pośrednia
Z
3
=
x
3
•
tp
Z
3
(
x
3
,
tp
)
Zawór Z
3
jest otwarty
poziom jest powyżej x
3
i
temperatura jest pośrednia
Z
3
=
x
3
•
tp
Z
3
(
x
3
,
tp
)
Z
3
{0,
1}
x
3
{0,
1}
tp
{0,
1}
Z
3
jest otwarty
Z
3
jest zamknięty
poziom jest powyżej
x
3
poziom jest poniżej x
3
temperatura jest
pośrednia
temperatura jest różna
od pośredniej
temperatura jest pośrednia
temtp. jest wyższa lub równa od t
4
i
jest niższa od t
5
tp
=
x
4
• x
5
x
4
{0,
1}
x
5
{0,
1}
temp. jest niższa od
t
4
temp. jest wyższa
od t
4
temp. jest niższa od t
5
temp. jest wyższa od
t
5
tp
{0,
1}
temp. jest pośrednia
temp. jest różna od
pośredniej
Z
3
=
x
3
•
tp
Z
3
=
x
3
•
x
4
•
x
5
tp
(
t
4
,
t
5
)
Podstawowe funkcje algebry
Boole’a
N
a
z
w
a
f
u
n
k
c
j
i
:
I
l
o
c
z
y
n
l
o
g
i
c
z
n
y
(
k
o
n
i
u
n
k
c
j
a
)
S
u
m
a
l
o
g
i
c
z
n
a
(
d
y
s
j
u
n
k
c
j
a
)
N
e
g
a
c
j
a
l
o
g
i
c
z
n
a
(
i
n
w
e
r
s
j
a
)
W
y
r
a
ż
e
n
i
e
l
o
g
i
c
z
n
e
a
b
(
c
z
y
l
i
a
b
)
a
+
b
(
c
z
y
l
i
a
b
)
a
T
a
b
l
i
c
a
z
a
l
e
ż
n
o
ś
c
i
a
b
a
b
0
0
0
0
1
0
1
0
0
1
1
1
a
b
a
+
b
0
0
0
0
1
1
1
0
1
1
1
1
a
a
0
1
1
0
Podstawowe prawa algebry
Boole’a
1. Prawo
dla mnożenia ( ):
A B = B A
przemienności
dla dodawania ( ):
A + B = B + A
2. Prawo
dla :
(A B) C = A (B C)
łączności
dla :
(A + B)+C = A+ (B + C)
3. Prawo
dla względem :
A (B + C) = AB + AC
rozdzielności
dla względem :
A + (B C) = (A+B) (A+C)
4. Prawo negacji
dla :
A B = A + B
(de Morgana)
dla :
A + B = A B
Zależności algebry Boole’a
Jakie są pojęcia
stosowane w zapisie funkcji
logicznych
?
Przykład 1
opis układu cyfrowego
a
b
Z
3
c
Tablica
zależności
Jak w oparciu o dane tablicy
zależności
?
funkcji logicznej dla
wyjścia Z
3
podać zapis
literałowy
Składniki ”1”, czyli elementarne
implikanty (ek)
Czynniki „0”, czyli elementarne
implicenty (ec)
(0 1 0, 0 1 1, 1 0 1, 1 1
1)
abc
(0 0 0, 0 0 1, 1 0 0, 1
1 0)
abc
Składniki ”1”, czyli elementarne
implikanty (ek)
(0 0 0, 0 0 1, 1 0 0, 1
1 0)
abc
( 0 , 1 , 4 ,
6)
abc
a b c
wagi: 2
2
2
1
2
0
(1 1 0)
abc
= 1·
2
2
+ 1·
2
1
+0·
2
0
= (6)
abc
Składniki ”1”, w zapisie dziesiętnym:
Składniki ”1”, czyli elementarne
implikanty (ek)
(0 0 0, 0 0 1, 1 0 0, 1
1 0)
abc
Składniki ”1”, w zapisie literałowym:
c
b
a
c
b
c
b
a
c
b
a
,
,
,
a
Składniki ”1”, czyli elementarne
implikanty (ek)
c
b
a
c
b
a
c
b
a
c
b
a
,
,
,
(0 0 0, 0 0 1, 1 0 0, 1
1 0)
abc
( 0 , 1 , 4 ,
6)
abc
c
b
a
c
b
a
c
b
a
c
b
a
,
,
,
Czynniki „0”, czyli elementarne
implicenty (ec)
(0 1 0, 0 1 1, 1 0 1, 1 1
1)
abc
(2, 3, 5, 7)
abc
Składniki ”1”, czyli elementarne
implikanty (ek)
c
b
a
c
b
c
b
a
c
b
a
,
,
,
a
(0 0 0, 0 0 1, 1 0 0, 1
1 0)
abc
( 0 , 1 , 4 ,
6)
abc
c
b
a
c
b
a
c
b
a
c
b
a
,
,
,
Czynniki „0”, czyli elementarne
implicenty (ec)
(0 1 0, 0 1 1, 1 0 1, 1 1
1)
abc
(2, 3, 5, 7)
abc
Kanoniczna postać funkcji logicznej
Z
3
=
c
b
a
c
b
a
c
b
a
c
b
a
Kanoniczna postać sumy
(alternatywna)
(
0 0 0, 0 0 1, 1 0 0, 1 1
0
)
abc
(
0 , 1 , 4 ,
6
)
abc
Z
3
=
Z
3
=
Kanoniczna postać funkcji logicznej
Z
3
=
Kanoniczna postać iloczynu
(koniunkcyjna)
c
b
a
c
b
a
c
b
a
c
b
a
(
0 1 0, 0 1 1, 1 0 1, 1 1
1
)
abc
(
2 , 3 , 5 ,
7
)
abc
Z
3
=
Z
3
=
Czy można uprościć zapis literałowy
funkcji
?
Kanoniczna postać sumy
(kps)
Po zastosowaniu prawa rozdzielności
mnożenia względem dodawania:
Z
3
=
c
b
a
c
b
a
c
b
a
c
b
a
b
b
c
a
c
c
b
a
Z
3
=
minimalna postać
sumy:
Z
3
= a b + a c
A (B + C)
= A B + A
C
A B + A
C
= A (B + C)
czyli
A + A
= 1
A · 1
= A
Kanoniczna postać iloczynu
(kpi)
Po zastosowaniu prawa rozdzielności
dodawania względem mnożenia:
Z
3
=
minimalna postać iloczynu:
A + B C = (A+B)
(A+C)
(A+B)
(A+C)
= A + B C
czyli
c
b
a
c
b
a
c
b
a
c
b
a
Z
3
=
b
b
c
a
c
c
b
a
c
a
b
a
Z
3
=
A · A
= 0
A + 0
= A
Przykład 2
opisu układu cyfrowego
Z
1
(a, b, c )
Z
2
(a, b, c )
a
Z
1
b
c
Z
2
Przykład 2
opisu układu cyfrowego
wagi
argumentów:
a b c
2
2
2
1
2
0
0
1
2
3
4
5
6
7
Przykład 2
opisu układu cyfrowego
0
1
2
3
4
5
6
7
Przykład 2
opisu układu cyfrowego
wagi
argumentów:
a b c
2
2
2
1
2
0
Kanoniczna postać sumy
0
1
2
3
4
5
6
7
Z
1
=
c
b
a
c
b
a
c
b
a
c
b
a
Skrócona postać
sumy:
Minimalna postać
sumy :
Kanoniczna postać
sumy
Z
1
=
c
b
a
c
b
a
c
b
a
c
b
a
Minimalna postaci
sumy
Z
1
=
b
b
c
a
c
c
b
a
Przekształcenie
wyrażenia
A B + A
C
= A (B + C)
Kanoniczna postać iloczynu
0
1
2
3
4
5
6
7
Skrócona postać
iloczynu
Minimalna postać
iloczynu
Z
1
=
c
b
a
c
b
a
c
b
a
c
b
a
Z
1
=
c
a
b
a
c
b
c
a
b
a
Z
1
=
Przekształcenie
wyrażenia
Minimalna postać
iloczynu
Z
1
=
c
b
a
c
b
a
c
b
a
c
b
a
Z
1
=
c
a
b
a
b
b
c
a
c
c
b
a
Z
1
=
Kanoniczna postać
iloczynu
(A+B)
(A+C)
= A + B C
Co to jest funkcja
nie w pełni
określona
?
Sposoby przedstawienia funkcji
nie w pełni określonej
0
1
2
3
4
5
6
7
stan
nieokreślony
Jakie elementy używane są
do budowy układów
cyfrowych
?
ELEMENTY PRZEŁĄCZAJĄCE
(logiczne,
cyfrowe)
•
stykowe
wykorzystują różne zjawiska fizyczne.
•
bezstykowe
Najbardziej
rozpowszechnione:
•
elektromagnetyc
zne,
• elektroniczne,
• hydrauliczne,
• pneumatyczne,
• magnetyczne,
• światłowodowe.
układy
stykowe
układy
bezstykowe
algebr
a
Boole’
a
Symbole i
oznaczenia
układy
stykowe
układy
bezstykowe
algebr
a
Boole’
a
Symbole i
oznaczenia
układy
stykowe
układy
bezstykowe
algebr
a
Boole’
a
Symbole i
oznaczenia
Co to jest
element stykowy
?
Przekaźnik elektromagnetyczny
U
element
stykowy
Przekaźnik elektromagnetyczny
styk normalnie zamknięty (rozwierny), symbol:
styk normalnie otwarty (zwierny), symbol
:
x
x
U
Przekaźnik elektromagnetyczny
styk normalnie zamknięty (rozwierny), symbol:
styk normalnie otwarty (zwierny), symbol
:
x
x
zwora (kotwica)
U
Przekaźnik elektromagnetyczny
styk normalnie zamknięty (rozwierny), symbol:
styk normalnie otwarty (zwierny), symbol
:
x
x
Cewka (uzwojenie na rdzeniu
magnetycznym) o symbolu:
X
zwora (kotwica)
U
Przykład schematu układu stykowego
a
a
b
c
Z
3
+
_
a
a
b
+
_
c
Z
3
Z
3
= a b + a c
c
a
b
a
Z
3
=
Co to jest
element bezstyk
owy
?
• elektroniczne
(półprzewodnikowe),
• hydrauliczne,
• pneumatyczne,
• magnetyczne,
• światłowodowe.
elementy bezsty
kowe:
Najprostsze półprzewodnikowe elementy
logiczne (funktory)
elementy
bezstykowe
a
b
a
b
a
b
a
+
b
a
a
System funkcjonalnie pełny
Jest nim taki zestaw funktorów, który
pozwala zrealizować każdą funkcję logiczną.
a
b
a
b a
b
a
+
b
a
a
Podstawowy system funkcjonalnie pełny
AND
OR
NOT
Przykłady
Minimalnych systemów funkcjonalnie
pełnych
a
b
a
b
a
a
a
b
a
+
b
a
a
a
b
a
b
a
b
a
+
b
AND
NOT
NAND
OR
NOT
NOR
Przykład schematu bezstykowego układu
a b c
Z
3
Z
3
= a b + a c
a b c
Z
3
a b a c
Z
3
=
NAND
AND
OR
AND
NAND
NAND
a b c
Z
3
a b c
Z
3
AND
OR
NOT
NAND
Przekształcenie wyrażenia opisującego
układ
Z
3
= a b + a c
Z
3
= a b + a c
Z
3
= a b · a c
a b c
Z
3
a b
c
Z
3
A = A
A+B = A ·
B
Przekształcenie wyrażenia opisującego
układ
Z
3
= a b + a c
Z
3
= a b + a c
Z
3
= a b · a c
a b c
Z
3
a b
c
Z
3
Przekształcenie wyrażenia opisującego
układ
Z
3
= a b + a c
a b c
Z
3
a b
c
Z
3
Z
3
=
a+b + a+c
NOR
Z
3
= a b + a c
Z
3
= a+ b + a+ c
A = A
A · B = A +
B
A = A
Przekształcenie wyrażenia opisującego
układ
Z
3
= a b + a c
a b c
Z
3
a b
c
Z
3
Z
3
=
a+b + a+c
NOR
Z
3
= a b + a c
Z
3
= a+ b + a+ c
Przekształcenie wyrażenia opisującego
układ
a b c
Z
3
a b
c
Z
3
a b
c
Z
3
Jakimi układami
będziemy się zajmowali
?
Układy kombinacyjne
Układy sekwencyjne
Układy statyczne
Układy dynamiczne
Układy synchroniczne
Układy asynchroniczne
UKŁADY CYFROWE
(
przełączające
)
Przykłady układów
Przykład układów
kombinacyjnych
a b c
Z
W
Przykład układów
kombinacyjnych
Przykład układów
kombinacyjnych
Przykład układu sekwencyjnego
asynchroniczne
go:
x
1
x
2
W
Sygnał taktujący
Y
7
Y
6
Y
5
Y
4
Y
3
Y
2
Y
1
Y
0
„0”
J
Q
C
K Q
s
r
a
2
a
1
a
0
J
Q
C
K Q
s
r
„1”
x
Q
1
Q
2
W
>
>
Przykład układu sekwencyjnego
synchroniczneg
o:
Tablica zawartości pamięci
Stan
licznika
Pole
skoku
Pole
Multipl.
Pole
wyjść
A
1
A
0
Y
1
Y
2
Y
3
Y
4
Y
5
Y
6
1
0 0
0 0
0 0
0 0
2
0 1
0 1
0 1
1 0
3
1 0
1 0
1 0
0 1
4
1 1
1 1
0
„0”
A
1
Y
1
Y
2
A
0
Y
3
Y
4
Y
5
CS Y
6
C
X
1
X
2
LICZNIK
mod. 4
liczący
w kodzie
natur. dw.
L
CE
„0”
Sygnał taktujący
Q
2
Q
1
S
P
S
L
w
a
1
a
0
D
3
D
2
D
1
Y
D
0
CS
p a b „1”
ROM
[2
2
6]
Przykład układu sekwencyjnego
mikroprogramowan
ego:
PLD
y
1
y
2
„0”
x
1
x
2
y
1
y
2
AND
OR
W
PLA
CE
i
1
i
2
i
3
i
4
i
5
i
6
i
7
i
8
PGA
a)
b)
imp. takt. (C)
Q
0
J
Q
Q
>C
SI
K
J
Q
Q
>C
K
Q
1
J
Q
Q
>C
K
Q
2
J
Q
Q
>C
K
Q
3
(SO)
J
Q
Q
>C
K
Q
4
C
X
Q
0
Q
1
Q
2
Q
3
Q
4
wpisana 5-bitowa informacja: 10010 dostępna jest
równolegle na wyjściach: Q
4
Q
3
Q
2
Q
1
Q
0
początek odczytu szeregowego
informacji na wyjściu: Q
4
= SO
zakończenie odczytu szeregowego
informacji na wyjściu: Q
4
= SO
1 2 3 4 5 6 7 8 9 10
Przykład typowych układów
sekwencyjnych
Rejestr
Układ do zamiany informacji równoległej
na szeregową:
Q
0
J
Q
Q
>C
K
Q
1
r
„1”
X
1
informacja wejściowa
W
imp. takt.
„0”
S
Q
J
Q
Q
>C
K
Q
n-2
s
r
X
n-2
Q
Q
J
Q
Q
>C
K
Q
n-1
s
r
X
n-1
J
Q
Q
>C
K
s
r
informacja
wyjściowa
K
. . .
b
. . .
s
LICZNIK
p
1
= 5
„1”
J Q
K Q
C
S
Q
0
J Q
K Q
C
S
Q
1
J Q
K Q
C
S
Q
2
„1”
“1”
Wy
1
„1”
J Q
K Q
C
S
J Q
K Q
C
S
„1”
Q
3
Q
4
p
2
= 3
Wy
2
= Wy
We
dekada szeregowa