Wykłady n.t.

Teoretyczne podstawy informatyki

Algebra Boole'a

Zbiór wartości z określonymi w nich działaniami na dwóch elementach: mnożenia  i dodawania  i działania na jednym elemencie : dopełnienie ~

Dwa wyróżnione elementy 0 i 1 , w których są spełnione aksjomaty dla wszystkich elementów o symbolach x, y, z  {0, 1 }

A1: x  0 = x A2: x  1 = x moduł sumy i mnożenia

A3: x  y = y  x A4: x  y = y  x przemienność działania

A5: x  (y  z) = (x  y)  (x  z) rozdzielność dodawania względem mnożenia

A6: x  (y  z) = (x  y)  (x  z) rozdzielność mnożenia względem dodawania

A7: x  ~x = 1 A8: x  ~x = 0

A9: x  ( y  z ) = ( x  y )  z łączność mnożenia

A10: x  ( y  z ) = ( x y )  z łączność dodawania

dodatkowo dodaje się najczęściej aksjomaty:

x  1 = 1 x  0 = 0 A.11 i A.12

można zamiast tych aksjomatów podać dwa inne

x  1 = ~x x  0 = ~x A.13 i A.14

W przypadku przyjęcia aksjomatów A.11 i A.12 otrzymujemy następujące tabele zależności (czasami nazywamy je tabelami prawdy):

x	y	F(x,y) = x  y		x	y	F(x,y) = x  y
0	0	0		0	0	0
0	1	1		0	1	0
1	0	1		1	0	0
1	1	1		1	1	1

W przypadku przyjęcia aksjomatów A.13 i A.14 otrzymalibyśmy tabele zależności

x	y	F(x,y) = x  y		x	y	F(x,y) = x  y
0	0	0		0	0	1
0	1	1		0	1	0
1	0	1		1	0	0
1	1	0		1	1	1

Funkcja boole'owska

Funkcja boole'owska odwzorowuje zbiory wartości boole'owskich w zbiór wartości boole'owskich:

F(a,b,c,...)  z, gdzie a, b, c, ... , z  {0,1}

Funkcje takie można opisać w trojaki sposób:

• słowny,

• w postaci tabeli zależności,

• w postaci wyrażeń boole'owskich

Implikanty i implicenty

Implikantem funkcji F() nazywamy iloczyn I zmiennych w postaci prostej lub zanegowanej, spełniający następującą zależność:

I=1  F()=1

Implikant zawierający wszystkie zmienne funkcji F nazywamy implikantem pierwotnym.

Implikant funkcji F, z którego usunięcie dowolnej zmiennej powoduje, że przestaje być implikantem nazywamy implikantem prostym.

Implicentem funkcji F() nazywamy sumę J zmiennych w postaci prostej lub zanegowanej, spełniającą następującą zależność:

J=0  F()=0

Implicent zawierający wszystkie zmienne funkcji F nazywamy implicentem pierwotnym.

Implicent funkcji F, z którego usunięcie dowolnej zmiennej powoduje, że przestaje być implicentem nazywamy implicentem prostym.

Przekształcanie i upraszczanie formuł boole'owskich

Prawa d'Morgana

~(x  y) = ~x  ~y oraz ~(x  y) = ~x  ~y

Reguła pochłaniania

A  (A x) = A  (A ~x) = A

oraz

A  (A  x) = A  (A  ~x) = A

Reguła sklejania

(A ~x)  (A x) = A

oraz

(A  ~x)  (A  x) = A

Sąsiedztwo logiczne

Sąsiedztwo słów binarnych:

Dwa słowa binarne o tej samej długości (ta sama liczba bitów) są sąsiednie logicznie jeżeli różnią się tylko na jednej pozycji.

Sąsiedztwo implikantów (implicentów):

Każdy pierwotny implikant (implicent) można zapisać w postaci ciągu zer i jedynek, przypisując zmiennej w postaci prostej jedynkę a zmiennej w postaci zanegowanej zero lub odwrotnie. Zatem analogicznie do sąsiedztwa słów binarnych, dwa pierwotne implikanty (implicenty) są sąsiednie logicznie jeżeli różnią się postacią tylko jednej zmiennej.

Synteza i upraszczanie funkcji boole'owskiej

Sposoby opisu funkcji boole'owskiej:

• opis słowny,

• opis w postaci tablicy zależności,

• opis w postaci wyrażenia algebraicznego.

W dalszej części przyjmuje się następujące oznaczenia:

~x oznaczamy

~(x  y) oznaczamy

~( x  y ) oznaczamy

Tabela 1

waga/ równoważnik	a	b	c	d	F1	F2	F3	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
		2^3	2^2	2^1				2^0
0	0	0	0	0	1	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	1	0	1	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
2	0	0	1	0	1	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0
3	0	0	1	1	0	1	1	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0
4	0	1	0	0	0	1	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0
5	0	1	0	1	1	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
6	0	1	1	0	0	1	1	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0
7	0	1	1	1	0	1	1	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0
8	1	0	0	0	1	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0
9	1	0	0	1	1	0	1	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0
10	1	0	1	0	0	0	1	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0
11	1	0	1	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0
12	1	1	0	0	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0
13	1	1	0	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0
14	1	1	1	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0
15	1	1	1	1	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1

F₁ = f0 + f2 + f5 + f8 + f9 + f11 + f12 + f13 + f15 = ….

F₂ = f0 + f1 + f3 + f4 + f6 + f7 + f11 + f12 + f13 + f14 = …

F₃ = f1 + f3 + f6 + f9 + f10 + f15 = ....

Tabela 1

waga/ równoważnik	a	b	c	d	F1	F2	F3	g	g	g	g	g	g	g	g	g	g	g	g	g	g	g	g
																0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
		2^3	2^2	2^1				2^0
0	0	0	0	0	1	1	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
1	0	0	0	1	0	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1
2	0	0	1	0	1	0	0	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1
3	0	0	1	1	0	1	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1
4	0	1	0	0	0	1	0	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1
5	0	1	0	1	1	0	0	1	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1
6	0	1	1	0	0	1	1	1	1	1	1	1	1	0	1	1	1	1	1	1	1	1	1
7	0	1	1	1	0	1	1	1	1	1	1	1	1	1	0	1	1	1	1	1	1	1	1
8	1	0	0	0	1	0	0	1	1	1	1	1	1	1	1	0	1	1	1	1	1	1	1
9	1	0	0	1	1	0	1	1	1	1	1	1	1	1	1	1	0	1	1	1	1	1	1
10	1	0	1	0	0	0	1	1	1	1	1	1	1	1	1	1	1	0	1	1	1	1	1
11	1	0	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	0	1	1	1	1
12	1	1	0	0	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	0	1	1	1
13	1	1	0	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	0	1	1
14	1	1	1	0	0	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	0	1
15	1	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	0

F₁ = g1 * g3 * g4 * g6 * g7 * g10 * g14 = ...

F₂ = g2 * g5 * g8 * g9 * g10 * g15 = ...

F₃ = g0 * g2 * g4 * g5 * g8 * g11 * g12 * g13 * g14 = ...

Przykład przekształcania funkcji boole'owskiej do postaci kanonicznej

Przekształćmy do postaci kanonicznych: sumy iloczynów i iloczynu sum funkcję:

Wykorzystując prawa de Morgana otrzymamy:

W celu otrzymania postaci sumy iloczynów wykorzystamy prawo rozdzielności mnożenia względem dodawania. Otrzymamy wówczas:

W celu otrzymania postaci iloczynu sum wykorzystamy prawo rozdzielności dodawania względem mnożenia. Otrzymamy wówczas:

Siatki Karnaugh'a - upraszczanie funkcji logicznej

Na podstawie lewej tablicy możemy napisać:

Na podstawie prawej tablicy możemy napisać

Zapis informacji - kodowanie liczb

• kodowanie znaków np. ASCII

• kodowanie liczb

• liczby stałopozycyjne

• znak - moduł (0 - liczba dodatnia, 1 - ujemna)

Przykład 0 001011 odpowiada +11

1 010101 odpowiada - 21

moduł

znak

• uzupełnienie do 1

Przykład 0 001011 odpowiada +11

negacja wszystkich bitów

1 110100 odpowiada -11

0 010101 odpowiada +21

1 101010 odpowiada - 21

pozostała część zapisu

znak

• uzupełnienie do 2

Przykład 0 001011 odpowiada +11

negacja wszystkich bitów - uzupełnienie do 1

1 110100 odpowiada -11

+1

1 110101 uzupełnienie do 2

pozostała część zapisu

znak

0 011100 odpowiada +28

1 100011 uzupełnienie do 1

1 100100 odpowiada - 28 uzupełnienie do 2

pozostała część zapisu

znak

! W zapisie uzupełnienia do 1 wartość 0 reprezentują dwie postaci 0 000000 (+0) i 1 111111 (-0)

! Liczby dodatnie w zapisie uzupełnienie do 1 i do 2 są zgodne z zapisem znak moduł

! Najstarszy bit zapisu U1 i U2 wskazuje na znak liczby

• kodowanie ósemkowe {0,1,2,3,4,5,6,7} odpowiada {000,001,010,011,100,101,110,111}

• kodowanie szesnastkowe {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}

• kodowanie dwójkowo - dziesiętne (BCD, kody refleksyjne, kod Exess 3)

• liczby zmiennopozycyjne : zapis znak cecha mantysa

Zamiana liczby kodowanej dziesiętnie na liczbę kodowaną dwójkowo

Poniżej przedstawimy zamianę modułu liczby dziesiętnej na dwójkową.

Liczba całkowita

Wartość dziesiętną liczby B oznaczymy przez D(B). Wówczas: