1 | S t r ona
Podstawy logiczne układów cyfrowych
Andrzej Handkiewicz
Politechnika Poznańska
Katedra Inżynierii Komputerowej
Poznań, 2008
2 | S t r ona
Rys historyczny
Logika w starożytności była dyscypliną filozoficzną (sylogistyka). Rozwój sylogistyki
związany jest z nazwiskami najsłynniejszych filozofów greckich: Sokratesem (469-399),
Platonem (427-347), Arystotelesem (384-322). Pod wpływem sylogistyki stoicy rozwinęli
rachunek zdań mieszczący się obecnie pod pojęciem logiki.
W średniowieczu logika, jako element scholastyki, była podstawowym narzędziem
dla teologii. Najsłynniejszym reprezentantem tego podejścia był Tomasz z Akwinu
(1225-1274), który w swych pracach nawiązywał do Arystotelesa.
W czasach nowożytnych, impulsem do rozwoju logiki było pojawienie się nowej
dyscypliny matematycznej: analizy. Twórcami analizy matematycznej byli Newton
(1643-1727) i Leibniz (1646-1716). Logika stała się dziedziną matematyczną. Wynikało
to z konieczności precyzyjnego formułowania i dowodzenia twierdzeń
matematycznych. Nastąpił szybki rozwój w trzech dziedzinach:
o Rachunek zbiorów. Szczególny wkład wnieśli: Leibniz, Euler (1707-1783),
Hamilton (1788-1856), De Morgan (1806-1878), Boole (1815-1864).
o Rachunek kwantyfikatorów. Szczególny wkład wnieśli: Cauchy (1789-1857),
Bolzano (1781-1848), Weierstrass (1815-1897), Whitehead (1871-1947), Russell
(1872-1970).
o Teoria mnogości, ze szczególnym wkładem m.in. Cantora (1845-1918),
Zermelo (1871-1954) i Chwistka (1884-1944).
Podsumowaniem tego okresu w matematyce jest monografia Whiteheada i Russella
 Principia Mathematica z 1925 r. (II wydanie). Efektem rozkwitu nie tylko logiki ale
matematyki jako całości był tzw. program Hilberta (1862-1943), w którym został
sformułowany postulat o możliwości uzyskania odpowiedzi na każde matematyczne
zagadnienie. Takie podejście można przyrównać do mechanistycznego obrazu
świata, jakie reprezentowali fizycy w okresie rozkwitu mechaniki, po sformułowaniu
przez Newtona swoich zasad. Program Hilberta zostaÅ‚ podważony przez Gödla (1906-
1978), który wykazał, że mogą istnieć twierdzenia prawdziwe ale nie dające się
udowodnić. Ograniczoność poznawcza metody logiczno-aksjomatycznej
spowodowała pojawienie się nowego nurtu w matematyce: metamatematyki, czyli
teorii badajÄ…cej teorie matematyczne, m.in. Tarski (1901-1983).
Obecny rozwój narzędzi (komputery) wspomagających człowieka w pracy
intelektualnej jest powodem powstawania nowych nurtów w myśleniu: maszyna
Turinga i architektury zaproponowane przez von Neumana: Princetown i harwardzka.
Myślenie człowieka ma coraz bardziej charakter algorytmiczny. Ważne pojęcia
związane nowymi narzędziami to złożoność, programowanie, operowanie obiektami.
3 | S t r ona
Rachunek zdań
Rachunek zdań wiąże się z badaniem prawdziwości zdań złożonych, przy
założeniu dotyczącym prawdziwości zdań prostych. Zdaniom
przyporządkowujemy dwie wartości:  1 (zdanie prawdziwe) i  0 (zdanie
fałszywe). Mówimy wówczas o logice dwuwartościowej. Zdania złożone
budujemy używając spójników:  lub ,  i , zaprzeczenia  nie a także formuł
typu  jeżeli ... to ... . W rachunku zdań są one zastępowane operatorami:
o  lub  v (vel) a także znakiem dodawania algebraicznego +
o  i - '" a także znakiem mnożenia algebraicznego *
o  nie  tylda (~) przed negowanym symbolem, prim ( ) za i kreska (--)
nad symbolem
o  jeżeli ... to ...  implikacja (=>)
Przykład:
a   niebo jest zachmurzone
b   świeci słońce
Gdy jedno z tych zdań jest prawdziwe to drugie jest fałszywe, więc: a+b=1,
a*b=0, a*b =1
Możliwe kombinacje dla operacji dodawania, mnożenia oraz implikacji
zawiera poniższa tabela. Obok tabeli pokazane są możliwe zapisy operacji.
Ä… ² Ä…("² Ä…'"² Ä…=>²
Ä…("² Ä…+²
0 0 0 0 1
Ä…'"² Ä…*²
0 1 1 0 1
~Ä… Ä…` Ä… -NEGACJE
1 0 1 0 0
Ä…("²=²("Ä…
1 1 1 1 1
Ä…=>² a" (Ä…`("²)
Zwróćmy uwagę na równoważność zapisu implikacji, która mówi że z fałszu
może wynikać zarówno fałsz jak i prawda, natomiast z prawdy jedynie
prawda (Ä…`("²).
4 | S t r ona
Rachunek zbiorów
Zbiór, element i jego przynależność do zbioru są w teorii mnogości pojęciami
pierwotnymi. Relację przynależności elementu do zbioru będziemy zapisywać
symbolem  " . Zdania proste
o element x należy do zbioru A,
o element x nie należy do zbioru A,
zapisujemy wówczas symbolicznie: x"A, x "A. Działania na zbiorach:
sumowanie, mnożenie, dopełnienie opisuje się za pomocą zdań prostych.
Poniżej zapisane są wymienione operacje na zbiorach, odpowiadający im
zapis przy użyciu rachunku zdań oraz przedstawienia graficzne działań na
zbiorach.
A*"B=C
x"C<=>(x"A)("(x"B)
A)"B=C
x"C<=>(x"A)'"(x"B)
x"A`<=>x "A
Związek między działaniami na zbiorach a rachunkiem zdań pozwala na
dowodzenie zależności rachunku zdań przy użyciu tzw. diagramów Venn a.
5 | S t r ona
Diagramy Venn a
Diagram Venn a dla wyrażeń logicznych trzech zmiennych: x, y, z.
Diagram składa się z trzech zbiorów, odpowiadającym każdej ze zmiennych,
przedstawionych jako okręgi umieszczone w przestrzeni tak aby każdy miał z
każdym z pozostałych wspólną część. Przestrzeń jest zobrazowana
prostokątem, tak jak jest to pokazane na pierwszym z poniższych pięciu
rysunków.
Wykorzystanie diagramu w dowodzeniu tożsamości logicznych przedstawione
jest dla przykładowego wyrażenia na czterech kolejnych rysunkach. A
atwo
wówczas zauważyć, że zbiór odpowiadający wyrażeniu y*z jest zawarty w
sumie zbiorów odpowiadających wyrażeniom x*y i x *z, co dowodzi
równoważności.
X*Y+X`*Z+Y*Z=X*Y+X`*Z
6 | S t r ona
Diagram Venn a dla wyrażeń logicznych czterech zmiennych:
w, x, y, z.
Na diagramie Venn a dla wyrażenia logicznego czterech zmiennych w, x, y,
z, trzy z pośród tych zmiennych x, y, z mają przedstawienie takie jak na
diagramie dla trzech zmiennych, a wypadkowy zbiór umieszczony jest
zarówno w obszarze odpowiadającym zbiorowi w jak i w jego dopełnieniu do
całej przestrzeni. Diagram jest przedstawiony na poniższym rysunku.
W
Y
X
Y
X
Z
Z
Przykład.
Posługując się diagramem dla czterech zmiennych można zauważyć, że zbiór
odpowiadający wyrażeniu (w*z+w*z ) jest tożsamy z w, a suma zbiorów
odpowiadających x*y oraz x*w jest tożsama ze wspólną częścią zbiorów
odpowiadających wyrażeniom x oraz (w+y).
X*Y+X*(WZ+WZ`)=X*(W+Y)
7 | S t r ona
Algebra Boole a
Rachunek zdań i rachunek zbiorów są przykładami algebry różnej od znanych
dobrze algebr: liczb rzeczywistych, zespolonych, macierzy, itp. Aksjomatyczna
podstawa rachunku zdań lub zbiorów to algebra Boole a. Algebra ta bazuje na
zbiorze elementów, który oznaczymy jako B i na dwóch działaniach możliwych do
wykonania na elementach zbioru, oznaczanych symbolami: +, i nazywanych
odpowiednio dodawaniem i mnożeniem. Jak każda teoria aksjomatyczna, algebra
Boole a zawiera zbiór aksjomatów, czyli twierdzeń oczywistych (nie dowodzonych), a
następnie rozwijana przez definiowanie nowych pojęć oraz formułowanie i
dowodzenie twierdzeń. Poniżej podany jest zbiór postulatów algebry Boole a (w
sformułowaniu podanym przez Huntingtona), a następnie dowody kilku
podstawowych twierdzeń. Trzy pierwsze z podanych twierdzeń to tzw. twierdzenia
trywialne, czyli możliwe do udowodnienia wyłącznie z użyciem postulatów. Przy
zapisie postulatów i twierdzeń używamy konwencji dotyczącej kolejności
wykonywania działań: mnożenie jest wykonywane przed dodawaniem. Jeśli więc
dodawanie ma być wykonane przed mnożeniem, konieczne jest użycie nawiasów.
Pojęcia pierwotne: zbiór B z elementami, na których możliwe są dwa działania: +, *.
POSTULATY
1. Zamkniętość:
a) (x"B)'"(y"B)=>(x+y)"B
b) (x"B)'"(y"B)=>x*y"B
2. Element identycznościowy:
a) x+0=0+x=x
b) x*1=1*x=x
3. Przemienność:
a) x+y=y+x
b) x*y=y*x
4. Rozdzielczość:
a) x*(y+z)=(x*y)+(x*z)=x*y+x*z
b) x+y*z=(x+y)*(x+z)
5. Element dopełniający:
a) x+x`=1
b) x*x`=0
6. Zbiór B zawiera przynajmniej dwa różne elementy:
x"B, y"B takie, że x`"y
8 | S t r ona
TWIERDZENIA:
1.
a) x+x=x
Dowód:
x+x=(x+x)*1 P2b
(x+x)*(x+x`) P5a
x+x*x` P4b
x+0 P5b
x P2a
b) x*x=x
Dowód:
x*x=x*x+0 P2a
x*x+x*x` P5b
x*(x+x`) P4a
x*1 P5a
x P2b
2.
a) x+1=1
Dowód:
x+1=1*(x+1) P2b
(x+x`)*(x+1) P5a
x+x`*1 P4b
x+x` P2b
1 P5a
b) x*0=0
3. (x`)`=x P5
4.
a) x+x*y=x
Dowód:
x+x*y = x*1+x*y P2b
x*(1+y) P4a
x*(y+1) P3a
x*1 T2a
x P2b
b) x*(x+y)=x
Twierdzenia De Morgana
a) (x+y)`=x`*y` b) (x*y)`=x`+y`
Zauważmy, że każdy postulat algebry Boole a ma swoje dualne (komplementarne)
sformułowanie. Stąd wynika również dualizm twierdzeń: z prawdziwości twierdzenia
pierwotnego wynika słuszność twierdzenia dualnego. Dualizm jest zilustrowany
powyżej dowodami twierdzeń 1a oraz 1b.
9 | S t r ona
Funkcje Boolowskie:
Funkcjami Boolowskimi będziemy nazywać funkcje, których dziedzina i zbiór wartości
są zbiorami spełniającymi postulaty algebry Boole a.
Proste przykłady funkcji jednej zmiennej to funkcje stałe (F(x)=0, F(x)=1), przeniesienie
(F(x)=x), inwersja (F(x)=x ).
W układach elektronicznych funkcje stałe odpowiadają dołączeniu odpowiednich
węzłów do masy lub szyny zasilającej, przeniesienie odpowiada połączeniu dwóch
węzłów bezpośredniemu lub za pomocą bufora, natomiast inwersja oznacza użycie
bramki nazywanej inwerterem oznaczanej symbolem bufora z kółkiem
odpowiadajÄ…cym negacji.
Poniżej przedstawiono symbole bramek jednowejściowych (inverter, bufor) oraz
tabelę prawdziwości dla operacji logicznego dodawania i mnożenia z symbolami
odpowiadajÄ…cych im bramek OR i AND.
x y x+y x*y przeniesienie
0 0 0 0
0 1 1 0
inwerter
1 0 1 0
1 1 1 1
bufor
Symbole bramek wykorzystywane są w schematach logicznych będących
graficznym przedstawieniem odpowiadających im wyrażeń logicznych, jak jest to
zilustrowane poniższym przykładem.
F(x,y)=x*(x`+y)=x*y
10 | S t r ona
Wszystkie możliwe funkcje logiczne dwóch zmiennych, F ,...,F przedstawia poniższa
0 15
tabela. Następna tabela zawiera symbole i nazwy operacji oraz komentarze
dotyczące każdej z tych funkcji.
x y F F F F F F F F F F F F F F F F
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Funkcja B Symbol Nazwa komentarz
operatora
zero
F0 Stała binarna 0
x*y AND x i (and) y
F1
x/y inhibicja x*y` , x lecz nie y
F2
F3 przeniesienie x
y/x inhibicja x`*y, y lecz nie x
F4
przeniesienie y
F5
ExOR x`*y+x*y`, x lub y ale nie oba
F6
xży
F7 x+y OR x lub (or) y
x“!y NOR (x+y)`, nie (x lub y)
F8
równoważność x`*y`+x*y
F9
(xży)`
y` inwersja Nie y
F10
F11 y=>x implikacja Jeżeli y to x
x` inwersja Nie x
F12
x=>y implikacja Jeżeli x to y
F13
xÄ™!y NAND (x*y)` nie (x i y)
F14
jeden Stała binarna 1
F15
Ze względu na zastosowania ważne są bramki, dotąd jeszcze nie wprowadzone,
odpowiadajÄ…ce funkcjom F , F , F : ExOR, NOR, NAND. Bramka ExOR wykonuje,
6 8 14
oprócz operacji logicznej, również operację arytmetyczną jaką jest suma modulo
dwa. Suma modulo dwa jest podstawowÄ… operacjÄ… potrzebnÄ… przy dodawaniu liczb
w systemie dwójkowym. Bramki NAND i NOR są z kolei najprostszymi ze względu na
liczbę tranzystorów wymaganych do ich budowy. Poniżej przedstawione są symbole
tych bramek.
11 | S t r ona
Działania logicznego sumowania, mnożenia oraz suma modulo dwa są działaniami
łącznymi: x+y+z=(x+y)+z=x+(y+z), x*y*z=(x*y)*z=x*(y*z), xżyżz=(xży) żz=xż (yżz).
WÅ‚aÅ›ciwoÅ›ci tej nie posiadajÄ… operacje NAND i NOR: xÄ™!yÄ™!zô ( xÄ™!y)Ä™!zôxÄ™!(yÄ™!z).
Z powyższych właściwości wynika możliwość realizacji bramek trójwejściowych AND,
OR, ExOR za pomocą bramek dwuwejściowych. Nie dotyczy to bramek NAND, NOR,
które jednak mogą być realizowane jako wielowejściowe bezpośrednio w układach
tranzystorowych. Poniższe rysunki ilustrują przedstawione rozważania.
OR 3-wejściowa
F(x,y,z)=x+y+z=(x+y)+z=x+(y+z)
AND 3-wejściowa
ExOR 3-wejściowa
12 | S t r ona
NOR 3-wejściowa
((x+y)`+z)`=(x+y)*z`=x*z`+y*z``"(x+y+z)`=x`y`z`
NAND 3-wejściowa
((x*y)`*z)`=x*y+z``"(x*y*z)`=x`+y`+z`
13 | S t r ona
Postacie funkcji logicznych
Standardowa Niestandardowa
sumacyjna iloczynowa F=(A*B`+C)*D`+E=
Każdy składnik jest Każdy czynnik jest sumą
=(A*B`+C+E)*(D`+E)
iloczynem dowolnej dowolnej liczby
liczby zmiennych zmiennych niezależnych
niezależnych (zanegowanych lub nie
(zanegowanych lub zanegowanych)
nie zanegowanych) F=(A+C+E)*
F=AB`D`+CD`+E *(B`+C+E)*(D+E)
(A+C+E)=A+C+E+B*B`=(A+B+C+E)(A+B`+C+E)
Postać kanoniczna- taka postać standardowa w której każdym składniku
(czynniku) występują wszystkie zmienne niezależne funkcji logicznej.
F=AB`D`+CD`+E=AB`CD`+AB`C`D`+ACD`+A`CD`+AE+A`E=AB`CD`E+AB`CD`E`
+AB`C`D`E+AB`C`D`E`+&
minterny (składniki) makstermy (czynniki)
konstytnenty jedynki konstytnenty zera
Składniki postaci kanonicznej sumacyjnej noszą nazwę mintermów (konstytuent
jedynki) natomiast czynniki postaci kanonicznej iloczynowej nazwę makstermów
(konstytuent zera). Poniższa tabela przedstawia postacie symboliczne i oznaczenia
mintermów i makstermów funkcji trzech zmiennych. Postacie symboliczne tworzone
sÄ… na podstawie kombinacji zero-jedynkowych odpowiadajÄ…cym trzem zmiennym
niezależnym. Minterm jest iloczynem tych zmiennych, zanegowanych jeśli zmiennej
odpowiada w kombinacji  0 , a nie zanegowanych jeśli  1 . Maksterm tworzony jest
w sposób dualny.
Funkcja 3-zmiennych F(x,y,z)
Minterny Maksterny
x y z F=x*y+z`
p. symb. oznaczenie p. symb. oznaczenie
0 0 0 x`y`z` m x+y+z M 1
0 0
0 0 1 x`y`z m x+y+z` M 0
1 1
0 1 0 x`yz` m x+y`+z M 1
2 2
0 1 1 x`yz m x+y`+z` M 0
3 3
1 0 0 xy`z` m x`+y+z M 1
4 4
1 0 1 xy`z m x`+y+z` M 0
5 5
1 1 0 xyz` m x`+y`+z M 1
6 6
1 1 1 xyz m x`+y`+z` M 1
7 7
14 | S t r ona
Zauważmy, że minterm ma wartość logiczną  1 jedynie dla tej kombinacji zero-
jedynkowej, dla której został utworzony (konstytuenta jedynki). Maksterm przeciwnie:
dla kombinacji na podstawie której został utworzony ma wartość  0 , dla wszystkich
pozostałych kombinacji wartość  1 (knstytuenta zera). W postaci kanonicznej
sumacyjnej funkcji występują więc te mintermy, którym odpowiadają jedynki w tabeli
prawdziwości funkcji, natomiast w postaci kanonicznej iloczynowej te makstermy,
którym w tabeli prawdziwości odpowiadają zera.
Indeksy w oznaczeniach mintermów i makstermów są postaciami dziesiętnymi liczb
dwójkowych dla odpowiedniej kombinacji zero-jedynkowej. Taka umowa pozwala
na skrócone zapisy postaci kanonicznych funkcji z użyciem symboli sumy oraz
iloczynu: " oraz .
Przykładowe sposoby zapisu postaci kanonicznych funkcji trzech zmiennych z
wykorzystaniem postaci symbolicznych i oznaczeń mintermów lub makstermów oraz
symboli sumy lub iloczynu:
F=x`y`z`+x`yz`+xy`z`+xyz`+xyz=m +m +m +m +m ="(0,2,4,6,7)
0 2 4 6 7
F(x,y,z)=(x+y+z`)*(x+y`+z`)*(x`+y+z`)=M M M = (1,3,5)
1 3 5
Tabelą prawdziwości przykładowej funkcji jest ostatnia kolumna w powyższej tabeli
mintermów i makstermów funcji 3-ch zmiennych.
Poniższe przykłady ilustrują sposób przekształcania funkcji z postaci standardowych
do postaci kanonicznych
Przykład przekształcenia funkcji z postaci standardowej sumacyjnej do kanonicznej
sumacyjnej:
F=A+B`*C A=AB+AB`=ABC+ABC`+AB`C+AB`C`
m m m m
7 6 5 4
F(A,B,C)="(1,4,5,6,7)= (0,2,3) B`C=AB`C+A`B`C
m m
5 1
Przykład przekształcenia funkcji z postaci standardowej sumacyjnej do kanonicznej
iloczynowej:
F=xy+x`z=(xy+x`)(xy+z)=(x`+y)(x+z)(y+z)
x`+y=x`+y+z*z`=(x`+y+z)(x`+y+z`)
M M
4 5
x+z=(x+y+z)(x+y`+z)
M M
0 2
y+z=(x+y+z)(x`+y+z)
M M
0 2
y+z=(x+y+z)(x+y`+z)
M M
0 4
F(x,y,z)= (0,2,4,5)="(1,3,6,7)
15 | S t r ona
Przedstawienie funkcji logicznych na mapie
Karnaugha
Mapa Karnaugha - macierz, której elementami są mintermy (makstermy)
funkcji logicznej
1o funkcja 2-ch zmiennych F(x,y)="(1,2)
x\y 0 1
x\y 0 1
0 m m
0 1 0 0 1
1 m m
2 3 1 1 0
2o funkcja 3-ch zmiennych F(x,y,z)=yz+xz`
x\yz 00 01 11 10
x\yz 00 01 11 10
0 m m m m
0 1 3 2
0 0 0 1 0
1 m m m m
4 5 7 6
1 1 0 1 1
F(x,y,z)="(3,4,6,7)= (0,1,2,5)
F=(A`+C)(B+C)=C+A`B
A\BC 00 01 11 10
0 0 1 1 1
1 0 1 1 0
3o funkcja 4-ch zmiennych F(a,b,c,d)
ab\cd 00 01 11 10
00 0 1 3 2
01 4 5 7 6
11 12 13 15 14
10 8 9 11 10
4o funkcja 5-ciu zmiennych F(u,w,x,y,z)
u=0 u=1
wx\yz 00 01 11 10
wx\yz 00 01 11 10
00 0 1 3 2
00 16 17 19 18
01 4 5 7 6
01 20 21 23 22
11 12 13 15 14
11 28 29 31 30
10 8 9 11 10
10 24 25 27 26
16 | S t r ona
Zauważmy, że kombinacje zero-jedynkowe, w przedstawionych powyżej mapach, są
przypisane wierszom i kolumnom według kolejności zgodnej z tzw. kodem Graya. W
tak utworzonych mapach mintermy (makstermy) różniące się tylko na jednej pozycji
sąsiadują ze sobą. Krawędziami sąsiedztwa są również krawędzie lewa i prawa oraz
górna i dolna. Umożliwia to wykorzystanie map Karnaugha do minimalizacji funkcji.
Umieszczenie mintermów (makstermów) różniących się na jednej pozycji w
bezpośrednim sąsiedztwie oznacza, że mapa dla funkcji 5-ciu zmiennych składa się z
dwóch warstw umieszczonych w przestrzeni trójwymiarowej jedna nad drugą.
Szczególnym rodzajem funkcji boolowskich są te, które dla pewnych kombinacji
zero-jedynkowych zmiennych niezależnych mają nieokreślone wartości logiczne.
Takimi funkcjami są np. opisywane układy cyfrowe, na których wejściach nie
pojawiają się pewne kombinacje zero-jedynkowe zmiennych niezależnych. W
postaciach kanonicznych  F takich funkcji będą więc wskazane mintermy
(makstermy), dla których wartości funkcji są określone (przyjmują odpowiednio
wartości 1 lub 0). W dodatkowej funkcji  d , również w postaci kanonicznej, będą
wymienione te mintermy (makstermy) dla których wartości funkcji  F są
nieokreslone. Przykładowa funkcja o wartościach nieokreślonych w postaci
kanonicznej sumacyjnej jest podana poniżej. Na mapie Karnaugha mintermy
(makstermy) dla których wartości funkcji są nieokreślone oznaczać będziemy
symbolem  x . Minterm (maksterm) oznaczony takim symbolem może przyjmować w
procesie minimalizacji wartość 0 lub 1. Możemy wówczas powiedzieć, że funkcja z
wartościami nieokreślonymi jest  aproksymowana jedną z kilku możliwych funkcji
boolowskich o wartościach określonych.
Funkcje z wartościami nieokreślonymi
i m
i
F(w,x,y,z)="(1,3,7,11,15)
0 0000 x
d="(0,2,5)
1 0001 1
2 0010 x
3 0011 1
wx\yz 00 01 11 10
4 0100 0
00 x 1 1 x
5 0101 x
6 0110 0 01 0 x 1 0
7 0111 1
11 0 0 1 0
8 1000 0
10 0 0 1 0
9 1001 0
m =wxyz m =wx`yz
10 1010 0 15 11
11 1011 1 m +m =wx`yz+wxyz=wyz
11 15
12 1100 0
yz
13 1101 0
m +m =w`x`yz+w`xyz=w`yz w x + yz
3 7
14 1110 0
w x
15 1111 1
2,4,8,& ,2j
17 | S t r ona
Proces minimalizacji z użyciem mapy Karnaugha polega na wykorzystaniu
sąsiedztwa mintermów (makstermów) różniących się jedynie jedną zmienną, która
jest w jednym przypadku nie zanegowana a w drugim zanegowana. Przykładami
takich obszarów są mintermy m i m oraz m i m oznaczone na mapie powyżej
11 15 3 7
kolorem odpowiednio czarnym i brÄ…zowym. Postaciami symbolicznymi utworzonych
obszarów są odpowiednio wyz oraz w yz i różnią się z kolei zmienną w. Wyłączenie
wspólnego czynnika yz odpowiada na mapie obszarowi zaznaczonemu na zielono.
Przykład ten wskazuje, że procedura minimalizacyjna z użyciem mapy Karnaugha
polega na znajdywaniu maksymalnych obszarów zawierających 2, 4, 8, ... , 2j
elementarnych kwadratów, gdzie j jest dowolną liczbą naturalną. Poza otrzymanym
obszarem pozostaje minterm m z przypisaną mu wartością 1. Maksymalny obszar
1
obejmujący ten minterm ma postać symboliczną w x i odpowiada pierwszemu
wierszowi na mapie, przy założeniu że wartości obu mintermów w górnych
narożnikach przyjmują wartość 1. Otrzymana w powyższym przykładzie tzw. postać
minimalna sumacyjna jest więc następująca: F=w x +yz. Procedura ta, zastosowana
w sposób dualny do elementów mapy z zerami prowadzi do tzw. postaci minimalnej
iloczynowej funkcji: F=z*(w +y). Zauważmy, że w tym przypadku wartości w górnych
narożnikach przyjmują wartość 0. Różne są również wartości mintermu m w obu
5
postaciach minimalnych: w postaci sumacyjnej ma on wartość 0, a w postaci
iloczynowej 1.
Minimalizacja funkcji boolowskich na mapie Karnaugha
Powyższy przykład ilustruje procedurę otrzymywania dwóch postaci
minimalnych funkcji boolowskich:
1o postać minimalna sumacyjna  łączenie kwadratów na mapie Karnaugha
zawierających jedynki w maksymalne obszary po 2j kwadratów
2o postać minimalna iloczynowa - łączenie kwadratów na mapie Karnaugha
zawierających zera w maksymalne obszary po 2j kwadratów
Przykłady
F(x,y,z)="(0,1,4,5,6) = (2,3,7)
x\yz 00 01 11 10
0 1 1 0 0
1 1 1 0 1
Dla obszarów zaznaczonych kolorami czerwonym i zielonym otrzymujemy
postać minimalną sumacyjną F=y +xz , natomiast dla obszarów zaznaczonych
na niebiesko postać minimalną iloczynową F=(y +z )(x+y ):
F=y`+xz`=(y`+z`)(x+y`)
18 | S t r ona
Schematy logiczne odpowiadajÄ…ce funkcjom w postaci standardowej majÄ…
szczególną cechę: są dwuwarstwowe (dwustopniowe). Dla postaci standardowej
sumacyjnej schemat zawiera w pierwszej warstwie bramki AND w liczbie równej
liczbie składników postaci sumacyjnej, a w drugiej warstwie bramkę OR o liczbie
wejść równej liczbie składników. Schemat dla postaci standardowej iloczynowej jest
dualny: w pierwszej warstwie zawiera bramki OR a w drugiej bramkÄ™ NAND.
DodatkowÄ… cechÄ… postaci minimalnych jest minimalna liczba bramek w obu
warstwach. Z postaci minimalnej sumacyjnej w powyższym przykładzie wynika
schemat logiczny zawierający w pierwszej warstwie jedną bramkę dwuwejściową
AND a w drugiej warstwie dwuwejściową OR. Jest to układ pokazany poniżej na
lewym rysunku w jego górnej części.
Schemat otrzymany na podstawie postaci minimalnej sumacyjnej składa się z kolei z
dwóch bramek OR dwuwejściowych w pierwszej warstwie i z bramki AND
dwuwejściowej w drugiej warstwie. Jest on przedstawiony w postaci równoważnej, z
podwójnie zanegowanymi sygnałami na wyjściach bramek OR, na lewym rysunku w
jego części dolnej. Równoważność ta wynika z Tw.3 algebry Boole a. Bramka
występująca wówczas w drugiej warstwie układu jest, zgodnie z twierdzeniem
Moora, równoważna bramce NOR. Schemat równoważny, zbudowany wyłącznie z
użyciem bramek NOR jest pokazany w dolnej części prawego rysunku powyżej. W
górnej części tego samego rysunku jest pokazany schemat logiczny układu
zbudowanego wyłącznie z bramek NAND, równoważnego układowi otrzymanemu
na podstawie postaci minimalnej sumacyjnej.
Na podstawie obu postaci minimalnych możemy więc otrzymać co najmniej cztery
schematy logiczne: dwa zbudowane z bramek AND i OR, na zmianÄ™ w jednej lub
drugiej warstwie i dwa równoważne im schematy zbudowane wyłącznie z bramek
NAND lub wyłącznie z NOR.
19 | S t r ona
Poniższe przykłady ilustrują metodę minimalizacji z użyciem map Karnaugha i
otrzymane na podstawie tych postaci minimalnych różne schematy logiczne.
Przykład minimalizacji funkcji danej w postaci kanonicznej sumacyjnej
F(a,b,c,d)="(5,7,12,13,14,15)=bd+ab=b(a+d)
ab\cd 00 01 11 10
00 0 0 0 0
01 0 1 1 0
11 1 1 1 1
10 0 0 0 0
ab\cd 00 01 11 10
00 0 0 0 0
01 0 1 1 0
11 1 1 1 1
10 0 0 0 0
Przykład minimalizacji funkcji danej w postaci standardowej sumacyjnej
F=A`B`C`+B`CD`+A`BCD`+AB`C`=B`C`+B`D`+A`C`D`=(B`+C)(C`+D`)(A`+B`)
AB\CD 00 01 11 10
00 1 1 0 1
01 0 0 0 1
11 0 0 0 0
10 1 1 0 1
wykorzystanie:
- tw.1: x  =x, y  =y, z  =z
- tw. De Morgana:
x`+y`+z`=(xyz)`
20 | S t r ona
Schemat na bramkach NOR
F=(B`+C)(C`+D`)(A`+B`)
Przykład funkcji, która ma kilka różnych postaci minimalnych sumacyjnych
F(A,B,C,D)="(0,2,3,5,7,8,9,10,11,13,15)
=BD+B`D`+AD+CD
AB\CD 00 01 11 10
=BD+B`D`+AB`+B`C implikanty
00 1 0 1 1
=BD+B`D`+AD+B`C proste
01 0 1 1 0
=BD+B`D`+AB`+CD
11 0 1 1 0
10 1 1 1 1
Istotne implikanty proste
 są to takie implikanty proste, które
zawierajÄ… przynajmniej jednÄ…
komórkę nie należącą do żadnego
innego implikantu prostego
Ten przykład pokazuje, że zagadnienie syntezy jest niejednoznaczne. Można
znalez
ć kilka równoważnych rozwiązań. Aby je znalez
ć należy wśród
wszystkich implikantów prostych wyszukać istotne, które występują we
wszystkich rozwiązaniach. Odpowiednie kombinacje pozostałych implikantów
dają różne postacie minimalne funkcji.
21 | S t r ona
Algorytm QM
Prosta metoda minimalizacji wykorzystująca mapę Karnaugha może mieć
zastosowanie jedynie dla funkcji niewielu zmiennych. Już przy pięciu
zmiennych użycie mapy jest utrudnione. Do minimalizacji funkcji pięciu i
większej liczby zmiennych używane są odpowiednie algorytmy, bazujące na
pojęciach implikantu prostego i istotnego. Pierwszy taki algorytm Quine a-
McCluskeya pojawił się w latach 60-tych.
Przykład funkcji z wartościami nieokreślonymi
F(w,x,y,z)="(1,3,7,11,15) d(w,r,y,z)="(0,2,5)
=yz+w`z=yz+w`x`=z(w`+y)
wx\yz 00 01 11 10
00 x 1 1 x
01 0 x 1 0
11 0 0 1 0
10 0 0 1 0
Przykłady minimalizacji funkcji z rozwiązaniami
a) F(x,y,z)="(1,3,5,6,7)=z+xy=(x+z)(y+z)
b) F(w,x,y,z)="(1,4,5,6,7,9,14,15)=xy+w`x+x`y`z=(x+y`)(w`+x`+y)(x+z)
c) F(w,x,y)=  (0,1,3,4,5)=xy`+wx=x(y`+w)
d) F(w,x,y,z)="(0,2,5,7,8,10,13,15) =xz+x`z`=(x+z`)(x`+z)
e) F(A,B,C,D)= (1,7,9,13,15)=D`+B`C+A`BC`=(B`+C`+D`)(B+C+D`)(A`+B`+D`)
(A`+C+D`)
f) F(A,B,C,D)="(1,4,5,7,12,14,15)=BC`D`+A`C`D+BCD+ABC
=BC`D`+A`C`D+BCD+ABD`
=BC`D`+A`C`D+A`BD+ABC
=(B+C`)(A+C`+D)(A`+C+D`)(B+D)
a) w`z+xz+x`y+wx`z
b) B`D+A`BC`+AB`C+ABC`
c) AB`C+B`C`D+BCD+ACD`+A`B`C+A`BC`D
d) wxy+yz+xy`z+x`y
Przykład minimalizacji funkcji 5-ciu zmiennych:
F(A,B,C,D,E)="(0,1,4,5,16,17,21,25,29)
postać minimalna sumacyjna:
F=A`B`CE`+A`B`C`D`+B`D`E`+B`CD`+CDE`+BDE`
22 | S t r ona
Pytania kontrolne (punkty za odpowiedzi i oceny)
1O F(w,x,y,z)=w`xy`z+w`xyz+wxyz
a) metodą przekształceń symbolicznych zredukować do minimalnej liczby
literałów 1
b) narysować schemat logiczny dla postaci zredukowanych (AND, OR,
inwertery) 1
2O w`z(x+y`)
a) przekształcić do post standardowej i kanonicznej (obie sumacyjne) 1
b) schemat log (AND, OR) 1
3O F(A,B,C,D)="(0,2,3,5,7,8,10,11,14,15)
a) znalez
ć postać minimalną sumacyjną za pomocą mapy Karnaugha 1
b) schemat log z bramkami NAND 1
2 3 4 5 6
3 3,5 4 4,5 5
1o F=w`x`y`z+w`xy`z+w`xyz
a) postać zredukować do minimalnej liczby literałów (przekształcenia
symboliczne) 1
b) schemat logiczny dla postaci zredukowanej (AND, OR) 1
2o F=(w`+y)xz: schemat logiczny 1
a) postać standardowa sumacyjna: schemat (AND,OR) 1
przekształcić do postaci kanonicznej sumacyjnej: "-1 schemqt 1
3o F(A,B,C,D)="(0,2,4,5,6,7,8,10,13,15)
a) znajdz
postacie minimalne (mapa Karnagha) 2
b) dwa schematy (NAND, NOR) 2
0-
5 6 7 8 9
4
2 3 3,5 4 4,5 5
Przykłady zastosowania metod syntezy układów logicznych kombinacyjnych
Na dwóch kolejnych stronach podane są realizacje:
1. konwertera kodu BCD (Binary Coded Decimal) na Ex-3 (Excess  3)
2. dekodera: zamiana adresu z szyny adresowej na logicznÄ… jedynkÄ™ na linii
wybranego słowa pamięci
23 | S t r ona
Konwerter Kodów
kod  BCD kod  Ex-3 w=A+BD+BC=
AB\CD 00 01 11 10
A B C D w x y Z =(A+B)(B`+C+D)
00 0 0 0 0
0 0 0 0 0 0 1 1
01 0 1 1 1
0 0 0 1 0 1 0 0
11 x x x x
0 0 1 0 0 1 0 1
10 1 1 x x
0 0 1 1 0 1 1 0
0 1 0 0 0 1 1 1
AB\CD 00 01 11 10
0 1 0 1 1 0 0 0 x=B`D+B`C+BC`D`=
00 0 1 1 1
=(B`+D`)(B`+C`)(B+C+D)
0 1 1 0 1 0 0 1
01 1 0 0 0
0 1 1 1 1 0 1 0
1 0 0 0 1 0 1 1 11 x x x x
1 0 0 1 1 1 0 0
10 0 1 x x
AB\CD 00 01 11 10
00 01 11 10
00 1 0 1 0 AB\CD
01 1 0 1 0 00 1 0 0 1
11 x x x x 01 1 0 0 1
10 1 0 x x 11 x x x x
10 1 0 x X
y=C`D`+CD=(C+D`)(C`+D) z=D`
24 | S t r ona
Dekoder
x y z w w w w w w w w
0 1 2 3 4 5 6 7
0 0 0 1 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0 0 0 0
0 1 0 0 0 1 0 0 0 0 0
0 1 1 0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 1 0 0 0
1 0 1 0 0 0 0 0 1 0 0
1 1 0 0 0 0 0 0 0 1 0
1 1 1 0 0 0 0 0 0 0 1
25 | S t r ona
Logika Sekwencyjna
Rozważane dotychczas układy logiczne opisywane były funkcjami logicznymi y=f(x).
Taki opis, nazywany logiką kombinacyjną, oznacza że sygnał logiczny na wyjściu
zależy jedynie od kombinacji zero-jedynkowej zmiennych niezależnych x
występującej na wejściu. Bramki: inwerter, AND, OR, NAND, NOR, EXOR itp., z których
te układy są budowane noszą nazwę bramek kombinacyjnych. Tak jak w przypadku
złożonego układu kombinacyjnego, sygnał na wyjściu bramki kombinacyjnej zależy
jedynie od kombinacji zero-jedynkowej występującej w danej chwili czasu na jej
wejściach. Jeśli sygnał na wyjściu bramki zależy również od wartości sygnałów w
poprzednich chwilach czasu, czyli od ciÄ…gu (sekwencji) zer i jedynek, to bramkÄ™
nazywamy pamiętającą a układ zawierający takie bramki sekwencyjnym.
Działanie układów sekwencyjnych zależy od czasu, zegar jest więc podstawowym
elementem koniecznym do sterowania jego działaniem. Zegarem będziemy
nazywać urządzenie generujące sygnał okresowy, w idealnym przypadku
prostokątny. Taki właśnie przypadek sygnału zegara (clk  clock) jest pokazany na
rysunku poniżej. Odcinki T, których wielokrotności są odłożone na poziomej osi czasu,
nazywamy okresem zegara. Okresy są podzielone na pół (wypełnienie 50%). Na
przedstawionym wykresie przypisujemy sygnałowi zegara logiczne 0 w połówkach
nieparzystych a logiczną 1 w połówkach parzystych.
clk- zmienna logiczna przyjmujÄ…ca na przemian,
w okresie T, wartości 0 lub 1
t
Układ sekwencyjny można rozważać w ogólnym przypadku jako zbudowany z
dwóch bloków: układu kombinacyjnego i układu pamiętającego. Blok
kombinacyjny posiada dodatkowe wejście połączone z wyjściem bloku
pamiętającego i dodatkowe wyjście połączone z wejściem tego bloku. Najprostsze
elementy, z których zbudowany może być układ pamiętający to przerzutniki DFF.
26 | S t r ona
Symbol przerzutnika DFF i wykresy ilustrujące jego działanie są przedstawione poniżej.
FF  flip-flop
D- data, delay
t
t
Działanie DFF polega na przeniesieniu danej (data) z wejścia na wyjście z
opóz
nieniem (delay) jednego okresu T na wyjście.
Analiza układów sekwencyjnych
Poniższy schemat przedstawia przykład układu sekwencyjnego, którego część
kombinacyjna składa się z kilku bramek AND i OR oraz z jednego inwertera. Część
pamiętająca składa się z dwóch przerzutników DFF.
27 | S t r ona
Pierwszy krok w analizie tego układu polega na sporządzeniu tzw. tabeli przejść
będącej odpowiednikiem tabeli prawdziwości układów kombinacyjnych. Zmiennymi
niezależnymi są nie tylko sygnały wejściowe (w podanym przykładzie x) ale także
stany bieżące przerzutników (w przykładzie Q i Q ) będące zmiennymi stanu.
1 2
Sygnałami wyjściowymi są sygnały wyjściowe (w przykładzie y) oraz stany następne
przerzutników (w przykładzie Q i Q ). Sporządzenie tabeli podanej poniżej ułatwia
1+ 2+
obliczenie, dla części kombinacyjnej układu, funkcji Q =D =x(Q +Q )= xQ +xQ
1+ 1 1 2 1 2
Q =D =xQ ` oraz y=x`(Q +Q ).
2+ 2 1 1 2
TABELA PRZEJŚĆ
x Q Q y Q Q
1 2 1+ 2+
0 0 0 0 0 0
0 0 1 1 0 0
0 1 0 1 0 0
0 1 1 1 0 0
1 0 0 0 0 1
1 0 1 0 1 1
1 1 0 0 1 0
1 1 1 0 1 0
Graficzną ilustracją tabeli przejść jest diagram stanów przedstawiony, dla
przykładowej tabeli, w dolnej części rysunku analizowanego układu. Wierzchołkami
grafu są kombinacje stanów bieżących, a krawędziami są oznaczone przejścia do
stanów następnych. Ze względu na skończoną liczbę wierzchołków układu, czyli
jego stanów, nazywamy go maszyną stanów skończonych (FSM  finite state
machine) lub automatem skończonym. Krawędziom są przypisane sygnały
wejściowe i jest tych krawędzi tyle ile wierszy w tabeli przejść. W naszym przykładzie
sygnały wyjściowe są przypisane również krawędziom. Taki automat nazywamy
automatem Mealy go. Jeżeli sygnały wyjściowe są przypisane wierzchołkom, to
układ nazywamy automatem Moora. Można wykazać równoważność obu rodzajów
automatów. Przykłady obu rodzajów są pokazane poniżej.
Przykład równoważności automatów Mealy go i Moora
Poniżej przedstawiony jest prosty automat i jego tabela przejść.
x Q Q y Q Q
1 2 1t 2t
0 0 0 0 0 0
0 0 1 0 0 0
0 1 0 0 0 0
0 1 1 1 0 0
1 0 0 0 0 1
1 0 1 0 1 1
1 1 0 0 0 1
1 1 1 1 1 1
28 | S t r ona
Otrzymaną tabelę przejść można przedstawić w postaci dwóch poniższych
diagramów stanów, jeden będący automatem Mealy go a drugi Moora.
Synteza układów sekwencyjnych
Zagadnienie syntezy jest odwrotnym do zadania analizy. Przyjmijmy, że syntezowany
automat opisany jest diagramem stanów. Liczba stanów określa liczbę przerzutników
potrzemnych do zrealizowania części pamiętającej automatu. Na podstawie tabeli
przejść automatu możemy otrzymać różne postacie funkcji opisujących część
kombinacyjnÄ…: np. zredukowane, minimalne itp. Ostatnim zadaniem jest realizacja
części kombinacyjnej z użyciem bramek, np. AND i OR, wyłącznie NAND, wyłącznie
NOR, itp.
29 | S t r ona
Przykład syntezy automatu Moora
Automat jest opisany poniższym diagramem stanów.
Odpowiadająca mu tabela przejść jest następująca:
x q q q q y
1 1 1t 2t
0 0 0 0 0 0
1 0 0 0 1 0
0 0 1 0 0 0
1 0 1 1 0 0
0 1 0 0 0 0
1 1 0 1 1 0
1 1 1 1 1 1
0 1 1 0 0 1
Otrzymane na podstawie tabeli przejść funkcje opisujące część kombinacyjną są
następujące:
y=xq q +x`q q =q q
1 2 1 2 1 2
D =xq `q +xq q `+xq q =xq +xq =x(q +q )
1 1 2 1 2 1 2 2 1 1 2
D =xq `q `+xq q `+xq q =xq `+xq =x(q +q `)
2 1 2 1 2 1 2 2 1 1 2
Postacie minimalne sumacyjne tych funkcji pozwalają zrealizować automat z
użyciem czterech bramek AND i dwóch OR, jak to jest przedstawione na poniższym
rysunku.
30 | S t r ona
Postacie minimalne iloczynowe
y=q q
1 2
D =x(q +q )
1 1 2
D = x(q +q `)
2 1 2
dają przedstawiony poniżej schemat automatu zrealizowanego na trzech bramkach
AND i dwóch OR
31 | S t r ona
Przykład syntezy zegara czterofazowego
Zegarem 4-ro fazowym nazywamy układ cyfrowy z czterema wyjściami, taki że w
kolejnych okresach zegara sygnał odpowiadający logicznej jedynce pojawia się
tylko na jednym z kolejnych wyjść, na pozostałych wyjściach jego wartość jest
zerowa. Poniższy rysunek przedstawia przebiegi tych sygnałów oraz diagram stanów
zegara.
Zauważmy, że do kodowania stanów został użyty kod Greya. Gwarantuje to
przejścia między żądanymi stanami, nawet przy założeniu różnic w szybkości
działania rzeczywistych przerzutników. Tabela przejść otrzymana na podstawie
diagramu stanów jest następująca:
q q q q y y y y
1 2 1t 2t 1 2 3 4
0 0 0 1 1 0 0 0
0 1 1 1 0 1 0 0
1 1 1 0 0 0 1 0
1 0 0 0 0 0 0 1
Funkcje logiczne opisujące część kombinacyjną automatu są następujące:
y =q `q ` D =q `q +q q =q
1 1 2 1 1 2 1 2 2
y =q `q D =q `
2 1 2 2 1
y =q q
3 1 2
y =q q `
4 1 2
Z tych funkcji wynika, że wejścia przerzutników są połączone bezpośrednio do
odpowiedniego wyjścia drugiego przerzutnika i oprócz tych dwóch przerzutników
potrzebne są jedynie cztery bramki AND do realizacji automatu skończonego
pokazanego na poniższym rysunku.
32 | S t r ona
Przykład syntezy układu migającego
Działanie automatu opisane jest przedstawionym poniżej diagramem stanów.
Wartość sygnału wejściowego b przyjmuje 1 lub 0 w zależności od tego czy przycisk
(button) jest lub nie jest wciśnięty. Sygnał wyjściowy l jest obserwowany na
fotodiodzie (light).
Jeżeli przycisk jest wciśnięty, to zgodnie z diagramem stanów, automat w pierwszym
okresie zegara przechodzi ze stanu poczÄ…tkowego 00 do stanu 01 a w drugim
powraca do stanu początkowego. W pierwszym okresie fotodioda nie świeci, a w
drugim świeci. Jeżeli przycisk nie jest wciśnięty to cały cykl pracy automatu wymaga
czterech okresów zegara, w którym następuje przejście przez wszystkie cztery stany.
Fotodioda nie świeci przez dwa pierwsze cykle zegara, a świeci przez dwa następne.
Tabela przejść przedstawiona jest poniżej.
33 | S t r ona
b q q q q L
1 2 1t 2t
0 0 0 0 1 0
0 0 1 1 1 0
0 1 0 0 0 1
0 1 1 1 0 1
1 0 0 0 1 0
1 0 1 0 0 1
1 1 0 0 0 1
1 1 1 0 0 1
Postacie zredukowane funkcji D i D otrzymane na podstawie tabeli są następujące:
1 2
D =bq `q +b`q q =b`q
1 1 2 1 2 2
D =b`q `q `+b`q `q +bq `q `=
2 1 2 1 2 1 2
=q `q `+bq =q (b+q `)
1 2 1 1 2
Postacie minimalne sumacyjna i iloczynowa, funkcji opisującej sygnał wyjściowy l,
uzyskane z pomocą mapy Karnaugh są następujące:
L=q +bq =(q +q )(b+q )
1 2 1 2 1
b\q 0 0 1 1
1
q 0 1 1 0
2
0 0 0 1 1
1 0 1 1 1
Poniższy schemat przedstawia zrealizowany automat.
34 | S t r ona
Literatura
1. Józef Kalisz,  Podstawy elektroniki cyfrowej , WKA
, W-wa 2002
2. Kenneth A. Ross, Charles R.B. Wright,  Matematyka dyskretna , PWN W-wa
2008
3. Kazimierz Kuratowski,  Wstęp do teorii mnogości i toplogii , PWN W-wa 1965
4. Andrzej Grzegorczyk,  Zarys logiki matematycznej , PWN, W-wa 1975