1. Prawa algebry boolowskiej (które najważniejsze z punktu widzenia inżyniera?)Udowodnij przykłady: xy'+z+(x'+y)z'=1 oraz axy'+ax'y+a'y = (ax) XOR y

1) Algebrą Boole'a nazywamy zbiór B, wyróżnione jego podzbiory O i I oraz operacje dwuargumentowe +; •, które dla dowolnych elementów X, Y, Z zbioru B spełniają następujące aksjomaty:

Aksjomaty

X+Y჎B	X•Y჎B	( domknięcie )
X+Y=Y+X	X • Y=Y • X	( przemienność )
X •(Y+Z)=X •Y+X •Z	X+Y •Z=(X +Y) • (X +Z)	( rozdzielność )
X+O=X	X •I=X	( element neutralny )
X+X'=I	X •X'=O	( element odwrotny )

Dwuelementową realizację algebry Boole'a otrzymujemy dla B={0,1}; O=0; I=1;

+: 1+1=1; •: 1 •1=1; Jeżeli X=1, to X'=0

1+0=1; 1 •0=0; Jeżeli X=0, to X'=1

0+1=1; 0 •1=0;

0+0=0. 0 •0=0.

2) Właściwości algebry Boole'a

a) Zasada dualizmu. Zastępując działanie `•' działaniem `+', a działanie `+' działaniem `•' oraz stałą I stałą 0, a stałą 0 stałą I w dowolnej tożsamości otrzymujemy również tożsamość.

b) Idempotentność

X•X=X X+X=X

c) Łączność

(X • Y) •Z=X • (Y • Z) (X +Y) +Z=X +(Y +Z)

d) Pochłanianie

X• (X+Y)=X X+(X•Y)=X

e) Prawa de Morgana

(X+Y)'=X' • Y' (X•Y)'=X'+Y'

f) Prawo podwójnej negacji

(X')'=X

Uwaga!

W algebrze Boole'a nie obowiązuje zasada skracania !!!

Jeżeli A • B=A • C to nie znaczy że B=C.

Podobnie: Jeżeli A + B=A + C to nie znaczy że B=C

Ale: Jeżeli A • B=A • C i A + B=A + C to B=C

3) Podstawowe funkcje logiczne jednej i dwóch zmiennych

Funkcja NOT f(x)=x'

Funkcja AND f(x,y) = x • y

Funkcja OR f(x,y) = x+y

Funkcja NAND (NOT AND) f(x,y) = (x • y)'

Funkcja NOR (NOT OR) f(x,y) = (x+y)'

Funkcja EXOR (EXCLUSIVE OR) f(x,y)=x' •y+x •y' = xჅy

Na podstawie: http://www.fpga.agh.edu.pl/tc/tc_pliki/algebrab.ppt

Które prawa algebry Boole'a są najbardziej istotne z punktu widzenia hardware-designera?

udowodnić: xy'+z+(x'+y)z'=1

trzeba skorzystać z 2 praw: a + a'b = a + b oraz a + 1 = 1. czyli:
P=1
L=xy' + z + x'z' + yz' = xy' + (z + z'x') + yz' = xy' + z + x' + yz' = xy' + (z + z'y) + x' = xy' + z + y + x' = (y + y'x) + z + x' = y + x + z + x' = (x + x') + y + z = 1 + y + z = 1 + z = 1
L = P

udowodnić: axy'+ax'y+a'y = (ax) XOR y

axy' + ax'y + a'y= a(xy' + x'y) + a'y = a(x XOR y) + a'y = (ax)XOR(ay) + a'y = (ax)XOR(y(a+a')) = (ax)XOR(y)

Ćwiczenie (wykład)

1. Udowodnij X•X=X 2. Udowodnij prawa de Morgana.

Ad2. Dowód:
Y=A+B
Negujemy zmienne i wymieniamy operator na przeciwny.
~Y = ~A*~B
Oczywiście zachodzi:
Y=~(~Y)
Stąd:
A+B = ~(~A*~B) - prawo de'Morgana dla sumy logicznej

---