Dr Galina

Cariowa

•

M. Morris Mano

, Charles R. Kime – Podstawy

projektowania układów logicznych i

komputerów, Wydawnictwa Naukowo-

Techniczne,

•

Giovanni De Micheli

- Synteza i optymalizacja

układów

cyfrowych, Wydawnictwa Naukowo-Techniczne,

•

Majewski Władysław

- Układy logiczne,

Podręczniki

akademickie EiT,

•

Jan Pienkos

, Janusz Turczyński - Układy scalone

TTL w

systemach cyfrowych, Wydawnictwa Komunikacji i

Łączności,

•

Wilkinson Barry

- Układy cyfrowe,

•

Grocki Wojciech

- Układy cyfrowe,

•

Tyszer Jerzy

, Mrugalski Grzegorz-Technika

cyfrowa. Zbiór zadań z

rozwiązaniami, Wydawnictwa BCT.

LITERATURA

:

George Boole.

(1815 -1864)

W

1854

r.

opublikował

książkę

wprowadzając

ą

matematyczn

ą teorię logiki.

Algebra Boole’a

Początkowo algebra Boole’a

służyła do analizy zdań

logicznych i procesów

myślowych.

Obecnie algebra boolowska

jest stosowana do opisu

połączeń bramek cyfrowych

oraz do

analizy i projektowania

binarnych układów cyfrowych.

Algebra Boole’a

Układy cyfrowe

są

elementami sprzętu
elektronicznego, które
przetwarzają informację
binarną.

Układy cyfrowe

są implementowane

przy użyciu tranzystorów połączonych

ze sobą wewnątrz układów scalonych.

Algebra

Boole’a

Algebra Boole’a jest algebrą

związaną ze

zmiennymi binarnymi

, które mogą

przyjmować dwie dyskretne wartości,

0

i

1

, oraz matematycznymi

funkcjami logicznymi,

które

operują na tych zmiennych.

Logika dwuwartościowa

.

Trzy podstawowe operacje logiczne

związane ze zmiennymi binarnymi to

AND

,

OR

oraz

NOT

.

AND

.

Na przykład

, Z=XY lub

.

Ta operacja jest przedstawiana za

pomocą kropki lub brakiem
operatora

.

Alternatywnym symbolem dla symbolu

”kropka” jest symbol .



Y

X

Z





1. Operacja

AND

– mnożenie logiczne,

koniunkcja

Logika dwuwartościowa

Interpretacja

logiczna

AND

:

Z=1 wtedy i

tylko wtedy,

gdy X=1 i Y=1,

w przeciwnym

razie Z=0.

Poniższe

równania

definiują

operację logiczną

AND:

1

1

1

0

0

1

0

1

0

0

0

0

















Logika dwuwartościowa

Ta operacja przedstawiana jest

symbolem dodawania :

Z=X+Y

.

Alternatywnym symbolem dla

symbolu +, oznaczającego

OR

,

jest symbol .



2.

Operacja

OR

– dodawanie logiczne,

dysjunkcja

Logika dwuwartościowa

Interpretacja

logiczna OR

:

Z=1

, jeżeli X=1

lub Y=1, lub

obie

zmienne

X=1 i

Y=1.

Z=0

wtedy i

tylko

wtedy,

gdy

X=0 i

Y=0.

Poniższe

równania

definiują

operację

logiczną

OR

:

0+0=0

0+1=1

1+0=1

1+1=

1

W arytmetyce
binarnej 1+1=

10

.

Logika dwuwartościowa

Tę operację symbolizuje

kreska nad zmienną:

.

X

Z 

Oznacza to, że jeżeli X=1, to

Z=0,

ale jeśli X=0,

to Z=1.

3. Operacja

NOT

–

negacja

,

dopełnienie

.

Logika dwuwartościowa

Tablica prawdy

(ang.truth table)

dla danej operacji jest tablicą

kombinacji wartości binarnych

przedstawiająca zależność

między wartościami

przyjmowanymi przez zmienne a

wartościami stanowiącymi

wynik tej operacji.

Bramki logiczne

Bramki logiczne

Nazwy zakresów napięć

wyjściowych

i

wejściowych

:

WYSOKI STAN LOGICZNY

(

H

) i

NISKI

(

L

)

PRAWDA

(

T

) i

FAŁSZ

(

F

)

1

i

0

Zakładamy, że

PRAWDA

i 1 są związane z

wysokimi napięciami,

H,

a

FAŁSZ i 0

– z

niskimi,

L

.

Rodzaje

bramek

Bramka AND

Bramka OR

y=x

1

+

x

2

(dysjunkcj

a)

Bramka NOT

(negacja,

dopełnienie)

Kółeczko na wyjściu

symbolu wskazuje na

inwersję

Bramka

NAND

Bramka NOR

Bramka XOR (ExOR,

Albo)

nierównoważność

)

)(

(

2

1

2

1

2

1

x

x

x

x

x

x









2

)

Bramka ExNOR

)

)(

(

2

1

2

1

2

1

x

x

x

x

x

x

y











Algebra

Boole’a

Wyrażenie boolowskie

jest to

wyrażenie algebraiczne utworzone z

użyciem zmiennych binarnych, stałych 0 i

1, symboli operacji logicznych i

nawiasów.

Projektowanie układów logicznych jest

oparte na przekształceniu

wyrażeń

boolowskich

.

Algebra Boole’a

1) za pomocą

równania boolowskiego

,

które składa się ze zmiennej binarnej,

poprzedzającej znak równości i wyrażenia

boolowskiego. Na przykład:

F=1, jeśli X=1 lub Y=0 i Z=1.

Dwie części wyrażenia,

X

oraz ,

nazywamy

wyrazami

(ang. term)

wyrażenia F,

a zmienne X, Y, Z -

literalami.

Z

Y

X

Z

Y

X

F





)

,

,

(

Z

Y

Funkcja boolowska

może być opisana na dwa

sposoby:

Algebra Boole’a

2) Funkcja boolowska może być przedstawiona

za pomocą tablicy prawdy.

Tablica prawdy

funkcji zawiera spis

wszystkich kombinacji 0 i 1 , które

mogą być przypisane zmiennym

binarnym, oraz spis wartości funkcji

dla każdej kombinacji binarnej.

Liczba wierszy tablicy prawdy wynosi

, gdzie n jest liczbą zmiennych

funkcji.

n

2

Algebra

Boole’a

X Y Z

F

0 0 0

0

0 0 1

1

0 1 0

0

0 1 1

0

1 0 0

1

1 0 1

1

1 1 0

1

1 1 1

1

Kombinacje

binarne tablicy

prawdy stanowią

n-bitowe liczby

binarne

,

odpowiadające

liczeniu w

systemie

dziesiętnym od 0

do

1

2 

n

Tablica prawdy
funkcji

Z

Y

X

Z

Y

X

F





)

,

,

(

• Istnieje tylko jeden sposób

przedstawienia funkcji boolowskiej za

pomocą tablicy prawdy.

• Gdy funkcja jest przedstawiona w postaci

równania boolowskiego, można ją wyrazić

na wiele sposobów, ponieważ można

przekształcać wyrażenia boolowskie

zgodnie z

prawami algebry Boole’a.

Prawa Algebry Boole’a

Prawo
przemienności

yx

xy

x

y

y

x









Prawa Algebry

Boole’a

Kolejność, w jakiej

zmienne są zapisane, nie

wpływa na wynik

(operacji OR i AND) .

Prawa Algebry Boole’a

z

y

x

z

y

x











)

(

)

(

Prawo

łączności

z

xy

yz

x

)

(

)

(



Wynik operacji stosowanej do trzech

zmiennych nie zależy od kolejności

pobierania zmiennych,

nawiasy mogą

być usunięty.

Prawo rozdzielności

)

)(

(

)

(

)

(

)

(

)

(

z

x

y

x

yz

x

xz

xy

z

y

x















Prawa Algebry

Boole’a

Drugie prawo rozdzielności jest

dualne względem zwykłego

(pierwszego) prawa

rozdzielności.

Prawa Algebry Boole’a

Wyrażenie

dualne

do danego

wyrażenia algebraicznego uzyskamy,

zamieniając ze sobą operacje AND i

OR oraz zastępując jedynki zerami i

zera jedynkami.

Wyrażenie dualne nie jest

równe oryginalnemu

wyrażeniu

.

Prawa Algebry Boole’a

Prawa De Morgana

(dla dwóch

zmiennych)

y

x

y

x







y

x

y

x







Prawa De Morgana

(

dla wielu

zmiennych

)

n

n

x

x

x

x

x

x















...

...

2

1

2

1

n

n

x

x

x

x

x

x















...

...

2

1

2

1

Weryfikacja twierdzenia

De Morgana

Prawa idempotentności

x

xx

x

x

x







Prawa

sprzeczności

1

0









x

x

x

x

Prawa Algebry

Boole’a

Prawa Algebry Boole’a

Prawo podwójnej negacji

x

x 

Dwukrotne dopełnienie przywraca

zmienną do jej pierwotnej wartości.

Pierwsze prawo identyczności

0

0

)

(

1

1









x

ie

pochlanian

x

Drugie

prawo identyczności

x

x

x

x









1

0

Stałe 0

Stała

1

Prawa Algebry

Boole’a

Prawa Algebry Boole’a

Twierdzenie o

zgodności

(

ang.

consensus theorem)

z

x

xy

yz

z

x

xy









Dowód

twierdzenia:











yz

x

xyz

z

x

xy











yz

x

z

x

xyz

xy











)

1

(

)

1

(

y

z

x

z

xy

z

x

xy

















)

(

x

x

yz

z

x

xy

yz

z

x

xy

Prawa Algebry Boole’a

Każdą zmienną w tożsamości

można zastąpić wyrażeniem

boolowskim, a tożsamość dalej

jest spełniona.

Przykład

.

Mamy wyrażenie

(A+B)(A+CD).

Przyjmiemy X=A, Y=B, Z=CD.

Na mocy drugiego prawa

rozdzielności

mamy:

(A+B)

(A+CD)=A+BCD

.

Zastosowanie algebry Boole’a.

Przekształcenie wyrażeń

boolowskich

Udowodnij, że lewa strona jest równa

prawej.

z

y

x

y

x

z

x

y











P

L

P

z

y

x

z

x

y

z

x

y

z

x

x

x

y

z

x

x

y

z

x

x

y

z

x

x

y

z

x

y

y

x

y

z

x

y

x

y

y

x

z

x

y

L



























































































)

(

1

)

)(

(

)

(

1

)

(

)

)(

(

)

(

prawo

przemienności

drugie prawo

rozdzielności

prawo

sprzeczności

prawo

sprzeczności

prawo

przemienności

Zastosowanie algebry

Boole’a

drugie prawo

rozdzielności

Zastosowanie algebry

Boole’a

Udowodnij, że lewa strona jest równa prawej

ab

b

a

a



 )

(

L

=

P

ab

aba

b

ab

aba

b

a

a

a

a

a

b

a

b

a

a

b

a

b

a

a

b

a

b

a

a

b

a

a



















































0

0

0

)

)(

(

)

(

)

(

L=

P

b

a

b

a

b

a







Prawo De

Morgana

Prawo De

Morgana

a

aa

o

a

a





Zastosowanie algebry

Boole’a

Znajdowanie

dopełnień:

- przez zamianę jedynek na zera i zer

na

jedynki w kolumnie tablicy

prawdy

opisującej wartości

funkcji;

-

algebraicznie

, stosując prawa De

Morgana;

- na podstawie

wyrażeń dualnych

.

Zastosowanie algebry

Boole’a

Znaleźć

dopełnienie

funkcji

.z

y

x

z

y

x

F











z

y

x

z

y

x

F







z

y

x

z

y

x

)

)(

(

z

y

x

z

y

x











prawo De

Morgana

prawo De

Morgana

Zastosowanie algebry

Boole’a

Znaleźć

dopełnienie

funkcji

.

z

y

x

z

y

x

F





)

(

)

(

z

y

x

z

y

x

F





Bierzemy w nawiasy

wyrazy pierwotnej

funkcji

)

)(

(

z

y

x

z

y

x









Zapisujemy wyrażenie

dualne do funkcji F

F

z

y

x

z

y

x











)

)(

(

Negujemy każdy

literał

Standardowe

postacie wyrażeń

boolowskich

Formuły standardowe zawierają ;

wyrazy iloczynowe

(np., )

oraz

wyrazy sumacyjne

(np.,

)

z

y

x

z

y

x





Iloczyn

, w którym wszystkie zmienne

występują dokładnie jeden raz,

zarówno w postaci prostej, jak i

zanegowanej, nazywa się

mintermem

.

Standardowe

postacie wyrażeń

boolowskich

Minterm

– przedstawia sobą

dokładnie

jedną

kombinację zmiennych

binarnych w tablicy prawdy;

– ma wartość

1

dla tej

kombinacji i

0 dla wszystkich

pozostałych

kombinacji.

Własności mintermów

1. Dla n zmiennych istnieje

dokładnie różnych

mintermów.

n

2

2. Dowolna funkcja boolowska może

być wyrażona w postaci sumy

logicznej mintermów.

3. Dopełnienie funkcji zawiera te

mintermy, których nie zawiera

pierwotna funkcja.
4. Funkcja, która zawiera wszystkie

mintermów, jest równa

logicznej 1.

n

2

Mintermy trzech

zmiennych

x y z

Wyraz

iloczyno

wy

Symbol

minter

mu

m

0

m

1

m

2

m

3

m

4

m

5

m

6

m

7

0

0

0

m

0

1 0 0 0 0 0 0 0

0

0

1

m

1

0 1 0 0 0 0 0 0

0

1

0

m

2

0 0 1 0 0 0 0 0

0

1

1

m

3

0 0 0 1 0 0 0 0

1

0

0

m

4

0 0 0 0 1 0 0 0

1

0

1

m

5

0 0 0 0 0 1 0 0

1

1

0

m

6

0 0 0 0 0 0 1 0

1 1

1

m

7

0 0 0 0 0 0 0 1

z

y

x

z

y

x

z

y

x

yz

x

z

y

x

z

y

x

z

xy

xyz

Standardowe postacie

wyrażeń boolowskich

Funkcja boolowska może być

przedstawiona algebraicznie na podstawie

tablicy prawdy przez utworzenie

sumy

logicznej wszystkich mintermów

, dla

których funkcja daje wartość 1.

Takie wyrażenie nosi nazwę

sumy

mintermów

.

Suma mintermów stanowi

standardową postać

wyrażenia

logicznego.

Standardowe postacie

wyrażeń boolowskich

Wyraz sumacyjny

, który zawiera

wszystkie zmienne w postaci prostej bądź

zanegowanej nazywany jest

makstermem.

Maksterm

– przedstawia sobą dokładnie

jedną

kombinację zmiennych

binarnych w

tablicy prawdy;

– ma wartość

0

dla tej kombinacji i

1

dla wszystkich

pozostałych kombinacji.

Makstermy trzech

zmiennych

x y z

Wyraz
sumacyj

ny

Symbol
makster

mu

M

0

M

1

M

2

M

3

M

4

M

5

M

6

M

7

0 0 0 x+y+

z

M

0

0 1 1

1

1

1

1

1

0 0 1

M

1

1 0 1

1

1

1

1

1

0 1 0

M

2

1 1 0

1

1

1

1

1

0 1 1

M

3

1 1 1

0

1

1

1

1

1 0 0

M

4

1 1 1

1

0

1

1

1

1 0 1

M

5

1 1 1

1

1

0

1

1

1 1 0

M

6

1 1 1

1

1

1

0

1

1 1 1

M

7

1 1 1

1

1

1

1

0

z

y

x 



z

y

x





z

y

x 



z

y

x 



z

y

x





z

y

x





z

y

x 



Standardowe postacie

wyrażeń boolowskich

Funkcja boolowska może być przedstawiona

algebraicznie na podstawie tablicy prawdy

przez utworzenie

iloczynu logicznego

wszystkich makstermów

, dla których

funkcja daje wartość 0.

Takie wyrażenie nosi nazwę

iloczynu

sum.

Iloczyn makstermów stanowi

standardową postać

wyrażenia

logicznego.

Sposoby zapisu funkcji

logicznych

• Zapis

algebraiczny

• Tablica prawdy
• Wektor prawdy
• Postać DCF
• Postać CCF
• Postać FDCF
• Postać FCCF

Zapis algebraiczny

z

z

y

xy

z

y

x

f









)

(

)

,

,

(

Funkcja boolowska jest opisana za

pomocą

równania boolowskiego

składającego ze zmiennej binarnej,

która poprzedza znak równości i

wyrażenie boolowskie.

Opcjonalnie

, po identyfikatorze

funkcji następuje, ujęta w nawiasy,

lista zmiennych, rozdzielonych

przecinkami.

Przykła

d.

.

Tablica prawdy

Tablica prawdy

(ang.Truth Table) to

zestawienie w kolejnych wierszach

tablicy wszystkich możliwych kombinacji

wartości logicznych argumentów funkcji

zdaniowej i dokładnie należących od

nich wartości logicznych tejże funkcji.

Kombinacje te muszą być

uporządkowane tak, aby tworzyły

kolejne liczby naturalne zapisane w

systemie dwójkowym.

Tablica prawdy bramki

AND

Wektor

prawdy

Standardowe postaci

funkcji boolowskich

1.

Postać DCF

(

postać dysjunkcyjna

normalna

)-

to jest dysjunkcja koniunkcji normalnych, na

przykład:

1

3

2

1

3

2

1

)

,

,

(

x

x

x

x

x

x

x

f





2.

Postać CCF

(

postać koniunkcyjna

normalna

) - to jest koniunkcja dysjunkcji

elementarnych,

na

przykład:

)

)(

)(

(

)

,

,

(

3

2

3

2

1

2

1

3

2

1

x

x

x

x

x

x

x

x

x

x

g











Standardowe postaci

funkcji boolowskich

To postać dysjunkcyjna, której składnikami są mintermy

(ang. minterm – to iloczyn wszystkich zmiennych danej

funkcji, przy czym zmienne te mogą występować jako

proste lub zanegowane) - jest to tzw.

konstytuenta „1”.

3.

Postać FDCF (SOP)

Full Disjunktive

Canonical Form

(Sum of

Products)

)

(

)

(

)

(

)

(

)

111

,

110

,

100

,

010

(

)

7

,

6

,

4

,

2

(

)

(

3

2

1

3

2

1

3

2

1

3

2

1

2

10

x

x

x

x

x

x

x

x

x

x

x

x

X

f



















Standardowe postaci

funkcji boolowskich

To postać koniunkcyjna, której składnikami są makstermy

(ang.

maksterm

– to suma wszystkich zmiennych danej

funkcji, przy czym zmienne te mogą występować jako

proste lub zanegowane) - jest to tzw.

konstytuenta „0”.











2

10

)

101

,

011

,

001

,

000

(

)

5

,

3

,

1

,

0

(

)

(x

f

4.

Postać FCCF (POS)

Full Conjunctive

Canonical Form

(Product of

Sum)

)

)(

)(

)(

(

3

2

1

3

2

1

3

2

1

3

2

1

x

x

x

x

x

x

x

x

x

x

x

x



















Uzyskiwanie postaci FDCF i

FCCF

1. Przekształcenia

algebraiczne

1. Przekształcenia

algebraiczne (c.d.)

Przykład. Przedstawić funkcję

w postaci FDCF.

c

b

a

c

b

a

h





)

,

,

(













c

b

a

a

c

c

b

b

a

c

b

a

h

)

(

)

)(

(

)

,

,

(















c

b

a

c

ab

c

b

a

c

b

a

c

ab

abc

.

c

b

a

c

b

a

c

b

a

c

ab

abc















)

7

,

6

,

5

,

4

,

2

(

)

,

,

(

FDCF

c

b

a

h

1.Przekształcenia

algebraiczne

1. Przekształcenia

algebraiczne

Przykład. Przedstawić funkcję

w postaci FCCF.

c

b

a

c

b

a

h





)

,

,

(









)

)(

(

)

,

,

(

c

a

b

a

c

b

a

h













)

)(

(

c

b

b

a

c

c

b

a





















)

)(

)(

)(

(

c

b

a

c

b

a

c

b

a

c

b

a

)

)(

)(

(

c

b

a

c

b

a

c

b

a



















)

3

,

1

,

0

(

)

,

,

(

FCCF

c

b

a

h

postać

CCF

2

. Algorytm tworzenia

FDCF

na podstawie tablicy

prawdy

• Z tablicy

wybrać zestawy zmiennych, dla

których funkcja równa się

1

;

• Dla tych zestawów stworzyć

konstytuenty

jedynki

, zawierające zmienną z inwersją, jeśli

przybiera ona w zbiorze wartość 0 i bez

inwersji, jeśli przybiera ona postać 1;

• Zbudować

dysjunkcię

uzyskanych

konstytuent 1.

2.

Algorytm tworzenia FCCF

na podstawie tablicy

prawdy

• Z tablicy

wybrać zestawy zmiennych, dla

których funkcja równa się

0

;

• Dla tych zestawów stworzyć

konstytuenty

zera

, zawierające zmienną z inwersją, jeśli

przybiera ona w zbiorze wartość 1 i bez

inwersji, jeśli przybiera ona postać 0;

• Zbudować

koniunkcję

uzyskanych

konstytuent 0.

Tworzenie funkcji w postaci

FDCF na podstawie tablicy

prawdy

Przykład

.

Tworzenie funkcji w postaci

FCCF na podstawie tablicy

prawdy

Maksterm

Tworzenie funkcji w postaci

FDCF i FCCF na podstawie

tablicy prawdy

)

)(

)(

(

z

y

x

z

y

x

z

y

x















Tworzenie funkcji w postaci

FDCF i FCCF na podstawie

tablicy prawdy

3

2

1

3

2

1

3

2

1

3

2

1

3

2

1

)

,

,

(

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

f

FDCF









)

(

)

)(

)(

(

)

,

,

(

3

2

1

3

2

1

3

2

1

3

2

1

3

2

1

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

f

FCCF



















3

2

1

x

x

x





Dziękuję za uwagę

Dziękuję za uwagę

Prawa Algebry Boole’a

Tablice prawdy

do

weryfikacji

twierdzenia

De

Morgana

0

1

1

1

0

1

0

1

0

1

1

0

1

0

0

0

x+
y

x+
y

y

x

0

0

0

1

1

0

1

0

0

1

0

0

1

1

0

1

1

1

0

0

x
y

y

x

y

x