Piotr Kawalec

Wykład III - 1

Wykład III

Logika układów cyfrowych

Synteza układów

kombinacyjnych

Technika cyfrowa

Piotr Kawalec

Wykład III - 2

Technika cyfrowa

LOGIKA UKŁADÓW CYFROWYCH

Algebra Boole’a

Aksjomatyczna definicja algebry Boole’a

Algebrą Boole’a nazywamy system algebraiczny

< B, +,

,

–,

o

,

i

>

w którym:

B

-

jest zbiorem;

+, 

-

operacje dwuargumentowe określone w

zbiorze

B

;

–

-

operacja jednoargumentowa określona w zbiorze

B

;

o

oraz

i

-

wyróżnione elementy zbioru

B

Piotr Kawalec

Wykład III - 3

Technika cyfrowa

Aksjomaty algebry Boole’a



a,b,c



B

a

+

b 

B

a

+

b = b

+

a

a

•

(b

+

c) = a

•

b

+

a

•

c

a

+

o

= a

1

a

•

b 

B

a

•

b

= b

•

a

a

+

b

•

c = (a

+

b)

•

(a

+

c)

a

•

i

= a

2

3

4



a 

B



a 

B

a

+

a =

i

a

•

a =

o

5

Piotr Kawalec

Wykład III - 4

Technika cyfrowa

Twierdzenia algebry Boole’a

a

+

(b

+

c) = (a

+

b)

+

c

a

+

a

•

b = a

a

•

(b

+

c) = a

•

b

+

a

•

c

a

+

a = a

a

+

i

=

i

a

+

b = a

•

b

o

=

i

1

a

•

(b

•

c) = (a

•

b)

•

c

a

•

(a

+

b)

= a

a

+

b

•

c = (a

+

b)

•

(a

+

c)

a

•

a

= a

a

•

o

=

o

a

•

b = a

+

b

i

=

o

2

3

4

5

6

7

8

a = a

Piotr Kawalec

Wykład III - 5

Technika cyfrowa

Dwuelementowa algebra Boole’a

Zbiór

B

{

0

,

1

} ; elementy wyróżnione

o

=

0

;

i

=

1

Operacje

+, 

,

–,

definiujemy

następująco:

a b a

+

b a



b a

0 0 0 0 1
0 1 1 0 1
1 0 1 0 0
1 1 1 1 0

+

- suma logiczna;



- iloczyn logiczny;

–

- negacja

Piotr Kawalec

Wykład III - 6

Technika cyfrowa

Dowodzenie twierdzeń w algebrze
Boole’a

W dwuelementowej algebrze Boole’a
twierdzenia mogą być dowodzone



na podstawie aksjomatów

;



metodą zero - jedynkową L = P

Przykład

Udowodnić twierdzenie

a

•

a

= a



wykorzystując aksjomaty

a

•

a = a

•

a

+

0

= a

•

a

+

a

•

a =a

•

(a

+

a ) = a

• 1

= a



metodą zero - jedynkową

a aa

0 0

1 1

4

4

5

3

5

4

Piotr Kawalec

Wykład III - 7

Technika cyfrowa

Funkcje i formuły boolowskie

Def.

Funkcją boolowską f

n

zmiennych

binarnych
x

1

, . . . x

n

nazywamy odwzorowanie zbioru

{0,1}x

. . .

x{0,1}

= {0,1}

n

w zbiór {0,1}



Można udowodnić że istnieje

2

różnych funkcji logicznych

n

zmiennych

dla n=1 istnieją 4 rożne funkcje, dla n=2 jest 16
funkcji

n

2

Piotr Kawalec

Wykład III - 8

Technika cyfrowa

Funkcje logiczne dwóch zmiennych

x

1

x

2

0 0 1 1

0 1 0 1

Nazwa funkcji

Zapis funkcji

+,  –

Uwagi

f

0

0 0 0 0

stała 0

0

f. zdegenerowana

f

1

0 0 0 1

iloczyn log. (AND)

x

1

 x

2

f

2

0 0 1 0

iloczyn z zakazem dla x

2

x

1

– x

2

= x

1

 x

2

f

3

0 0 1 1

zmienna x

1

x

1

f. częściowo zdegen.

f

4

0 1 0 0

iloczyn z zakazem dla x

1

x

2

– x

1

= x

1

 x

2

f

5

0 1 0 1

zmienna x

2

x

2

f. częściowo zdegen.

f

6

0 1 1 0

albo, (ExOR)

x

1

+ x

2

= x

1

x

2

+ x

1

x

2

f

7

0 1 1 1

suma log. (lub, OR)

x

1

+ x

2

f

8

1 0 0 0

negacja sumy (NOR)

x

1

 x

2

= x

1

+ x

2

f

9

1 0 0 1

równoważność

x

1



x

2

= x

1

x

2

+ x

1

x

2

f

10

1 0 1 0

negacja x

2

(NOT)

x

2

f. częściowo zdegen.

f

11

1 0 1 1

implikacja x

1

przez x

2

x

2

 x

1

= x

1

+ x

2

f

12

1 1 0 0

negacja x

1

(NOT)

x

1

f. częściowo zdegen.

f

13

1 1 0 1

implikacja x

2

przez x

1

x

1



x

2

=

x

1

+ x

2

f

14

1 1 1 0

negacja iloczynu (NAND)

x

1

/ x

2

= x

1

 x

2

f

15

1 1 1 1

stała 1

1

f. zdegenerowana

Piotr Kawalec

Wykład III - 9

Technika cyfrowa

Systemy funkcjonalnie pełne

Def.

Zbiór operacji takich, że każda funkcja

logiczna
może być przedstawiona przy pomocy
argumentów
stałych 0 i 1 oraz tych operacji nazywamy

systemem funkcjonalnie pełnym

(SFP)



Funkcje logiczne sumy, iloczynu i negacji

tworzą
podstawowy system funkcjonalnie pełny



Sprawdzenie czy jakiś system jest SFP polega

na
próbie wyrażenia przy pomocy badanych
operatorów
operacji negacji, sumy i iloczynu

Piotr Kawalec

Wykład III -
10

Technika cyfrowa

Systemy funkcjonalnie pełne



Spośród 16 funkcji dwóch zmiennych tylko

dwie,

każda niezależnie tworzą system funkcjonalnie

pełny.

Są to funkcje:



NAND



NOR

Wykazać że funkcja

NAND

oraz

NOR

tworzy

SFP

Piotr Kawalec

Wykład III -
11

Technika cyfrowa

SYNTEZA UKŁADÓW
KOMBINACYJNYCH

Def.

Syntezą układów kombinacyjnych

nazywamy

zespół czynności, które na podstawie

założeń

dotyczących działania układów

doprowadzają

do schematu logicznego układu, przy czym

schemat ten powinien zawierać tylko

elementy

przewidzianego typu i spełniać pewne

wymagania optymalności.

Piotr Kawalec

Wykład III -
12

Technika cyfrowa

SYNTEZA UKŁADÓW
KOMBINACYJNYCH

Układ

kombinacyjny

x

1

x

n

.
.
.

.
.
.

y

1

y

m

y

i

= f

i

(x

1

, . . . X

n

)

Piotr Kawalec

Wykład III -
13

Technika cyfrowa

Sposoby opisu działania układów



opis słowny

Zaprojektować układ o 3 wejściach i jednym
wyjściu wykrywający gdy na wejściu pojawi się
nieparzysta liczba jedynek



tablica wartości funkcji -

podstawowy

sposób
opisu układów kombinacyjnych



wykresy czasowe

Piotr Kawalec

Wykład III -
14

Technika cyfrowa

Kanoniczne postacie funkcji
logicznych



kanoniczna postać sumy

y

i

= f

i

(x

1

, . . . X

n

) =



f(a) K

a



kanoniczna postać iloczynu

y

i

= f

i

(x

1

, . . . X

n

) =

 (

f(b) + D

b

)

2

n

-1

a= 0

2

n

-1

b= 0

Piotr Kawalec

Wykład III -
15

Technika cyfrowa

Kanoniczne postacie funkcji logicznych


kanoniczną

postać sumy można otrzymać

bezpośrednio z tablicy wartości funkcji
rozpatrując
tylko te wiersze dla których y=1, przy
czym
zmienna o wartości 1 wchodzi do iloczynu
w
postaci afirmacji, a zmienna o wartości 0 -
w
postaci negacji



kanoniczną postać iloczynu można

otrzymać
bezpośrednio z tablicy wartości funkcji
rozpatrując
tylko te wiersze dla których y=0, przy
czym
zmienna o wartości 1 wchodzi do sumy w
postaci
negacji, a zmienna o wartości 0 - w
postaci
afirmacji

Piotr Kawalec

Wykład III -
16

Technika cyfrowa

Kanoniczne postacie funkcji logicznych



Postaci kanoniczne funkcji zwykle zapisuje

się jako zbiór dziesiętnych indeksów

poprzedzonych odpowiednim symbolem

Np.

kanoniczne postacie funkcji zadanych

słownie
będą następujące

y=(1,2,4,7)

y=(0,3,5,6)

Jeśli dla pewnych ciągów argumentów
funkcja jest
nieokreślona, to odpowiadające im indeksy
zapisuje się w nawiasie w obu postaciach
kanonicznych funkcji