Wyk ECiUL#1 2013

background image

Dr Galina

Cariowa

background image

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

:

background image

George Boole.

(1815 -1864)

W

1854

r.

opublikował

książkę

wprowadzając

ą

matematyczn

ą teorię logiki.

background image

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.

background image

Algebra Boole’a

Układy cyfrowe

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.

background image

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.

background image

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

background image

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

background image

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

background image

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

.

background image

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

.

background image

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.

background image

Bramki logiczne

background image

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

.

background image

Rodzaje

bramek

background image

Bramka AND

background image

Bramka OR

y=x

1

+

x

2

(dysjunkcj

a)

background image

Bramka NOT

(negacja,

dopełnienie)

Kółeczko na wyjściu

symbolu wskazuje na

inwersję

background image

Bramka

NAND

background image

Bramka NOR

background image

Bramka XOR (ExOR,

Albo)

nierównoważność

)

)(

(

2

1

2

1

2

1

x

x

x

x

x

x

2

)

background image

Bramka ExNOR

)

)(

(

2

1

2

1

2

1

x

x

x

x

x

x

y

background image

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

.

background image

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:

background image

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

background image

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

)

,

,

(

background image

• 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.

background image

Prawa Algebry Boole’a

background image

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) .

background image

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.

background image

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.

background image

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

.

background image

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

background image

Weryfikacja twierdzenia

De Morgana

background image

Prawa idempotentności

x

xx

x

x

x

Prawa

sprzeczności

1

0

x

x

x

x

Prawa Algebry

Boole’a

background image

Prawa Algebry Boole’a

Prawo podwójnej negacji

x

x

Dwukrotne dopełnienie przywraca

zmienną do jej pierwotnej wartości.

background image

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

background image

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

background image

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

.

background image

Zastosowanie algebry Boole’a.

Przekształcenie wyrażeń

boolowskich

background image

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

background image

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

background image

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

.

background image

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

background image

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ł

background image

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

.

background image

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.

background image

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

background image

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

background image

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.

background image

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.

background image

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

background image

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.

background image

Sposoby zapisu funkcji

logicznych

• Zapis

algebraiczny

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

background image

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.

.

background image

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.

background image

Tablica prawdy bramki

AND

background image

Wektor

prawdy

background image

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

background image

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

background image

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

background image

Uzyskiwanie postaci FDCF i

FCCF

background image

1. Przekształcenia

algebraiczne

background image

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

background image

1.Przekształcenia

algebraiczne

background image

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

background image

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.

background image

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.

background image

Tworzenie funkcji w postaci

FDCF na podstawie tablicy

prawdy

Przykład

.

background image

Tworzenie funkcji w postaci

FCCF na podstawie tablicy

prawdy

Maksterm

background image

Tworzenie funkcji w postaci

FDCF i FCCF na podstawie

tablicy prawdy

)

)(

)(

(

z

y

x

z

y

x

z

y

x

background image

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

background image

Dziękuję za uwagę

Dziękuję za uwagę

background image

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


Document Outline


Wyszukiwarka

Podobne podstrony:
Wyk ECiUL#6 2013
Wyk ECiUL#5 2013
Wyk ECiUL#3 2013
Wyk ECiUL#9S 2013
Wyk ECiUL#9S 2013
TEMATY NA ZAL WYK Z MASZYN 2013, Mazynoznastwo
de Rosset, wyk inauguracyjny 2013 14
4 Wyk PNOP 2013 14 innowacje dz Nieznany (2)
TEMATY NA ZAL WYK MASZYNOZN 2013 14, STUDIA PŁ, TECHNOLOGIA ŻYWNOŚCI I ŻYWIENIA CZŁOWIEKA, ROK II, S
TEMATY NA ZAL WYK Z MASZYN 2013, Mazynoznastwo
fizjo - wyk+éady, Leśnictwo UP POZNAŃ 2013, Fizjologia roślin drzewiastych
Genetyka wyk éad 2( 02 2013
genetyka wyk éad 1 ! 02 2013 MAM
MiBM Reg. i wyk. ćw. Lab 2013 stacjonarne
Wyk. syllabus 2010 analiza ekonomiczna SSE I, Ekonomia UWr WPAIE 2010-2013, Semestr II, Analiza Ekon
materia éy z wyk é VIII ch fiz 2013

więcej podobnych podstron