Zadania do ćwiczeń z TC (OKNO)

Zadanie 1.

Zminimalizować metodą tablic następujące funkcje boolowskie:

a) f = (0,1,2,9,11,12,13, ,27, 28,29),

b) f = [4,5,10,11,15,18,20,24,26,30,31, (9,12,14,16,19,21,25)].

Rozwiązania:

1. f = (0,1,2,9,11,12,13, ,27, 28,29)

ponieważ najwyższa liczba dziesiętna w zbiorze to 29 (w zapisie binarnym 11101) wiemy stąd, że nasza funkcja ma 5 argumentów wejściowych. Tworzymy np. tablicę Karnaugha 3/2 i wpisujemy w odpowiednie współrzędne (liczby dziesiętne ze zbioru w zapisie dwójkowym) wartości funkcji 1, w pozostałe 0.

x4x5 x1x2x3	00	01	11	10
000	1	1	0	1
001	0	0	0	0
011	1	1	0	0
010	0	1	1	0
110	0	0	1	0
111	1	1	0	0
101	0	0	0	0
100	0	0	0	0

Po zakreśleniu „pętelek” uzyskujemy następujące wyrażenie boolowskie, wypisując kolejno poziome, następnie pionowe owale:

2. f = [4,5,10,11,15,18,20,24,26,30,31, (9,12,14,16,19,21,25)]

x4x5 x1x2x3	00	01	11	10
000	0	0	0	0
001	1	1	0	0
011	-	0	1	-
010	0	-	1	1
110	1	-	0	1
111	0	0	1	1
101	1	-	0	0
100	-	0	-	1




Zadanie 2.

Uprościć następujące wyrażenie:




Rozwiązanie:

Nanosimy Y na tablicę Karnaugha 2/2 (liczba zmiennych 4 - ABCD) i upraszczamy tworząc pętelki obejmujące 0.

Następnie wypisujemy rozwiązanie, dla kanonicznego iloczynu sumy argumenty z 0 są proste, argumenty z 1 są zanegowane.

CD AB	00	01	11	10
00	1	0	0	1
01	0	0	0	0
11	0	1	1	1
10	0	0	0	0

Po minimalizacji uzyskaliśmy następująca funkcję:




Zadanie 3.

Funkcję boolowską opisaną zbiorami F i R zminimalizować metodą ekspansji.

F:		R:
00000 11000 11010 01110 11100 01011		11101 00010 00110 10001 01100

Rozwiązanie:

	k
F:	1 2 3 4 5 6	00000 11000 11010 01110 11100 01011	R:	11101 00010 00110 10001 01100

Liczymy ekspansję K_1.

Ponieważ k₁=(00000), to macierz blokująca B₁jest identyczna z macierzą R.

		1 2 3 4 5
B1:		11101 00010 00110 10001 01100		1,2,3,5 4 3,4 1,5 2,3

⇒ Do pokrycia wybieramy

L={3,4,5} (x₃ x₄ x₅)

wypisujemy w każdym wierszu numery kolumn z

1. Następnie wybieramy taki zbiór, który zapewni pokrycie kolumnowe.




K₁⁺ dla k₁=00000 będzie --000: K₁⁺ ≥ K₂ Pokryta została także kostka K₂

k3	11010				1 2 3 4 5
R:	11101 00010 00110 10001 01100		B3:		00111 11000 11100 01011 10110		3,4,5 1,2 1,2,3 2,4,5 1,3,4

Minimalne pokrycie zapewnia ⇒ L={1,5} (x₁ x₅)


K₃⁺ = 1---0 = K₃⁺ ≥ K₅

Kostka K₃⁺ pokrywa także K₅, do dalszych obliczeń zostają kostki K₄, K₆

k4	01110				1 2 3 4 5
R:	11101 00010 00110 10001 01100		B4:		10011 01100 01000 11111 00010		1,4,5 2,3 2 1,2,3,4,5 4

Minimalne pokrycie zapewnia ⇒ L={2,4} (x₂ x₄)





K₄⁺ = -1-1- = K₄⁺ ≥ K₆

Zbierając wszystkie kostki pokrycia otrzymujemy funkcję minimalną:

Zadanie 4.


Dla funkcji F opisanej tablicą zmienne niezbędne są x₅ oaz x₇. Należy wyznaczyć wszystkie (!!!) minimalne zbiory argumentów, od których zależy ta funkcja oraz jej minimalne wyrażenie boolowskie z najmniejszą liczbą argumentów.

Rozwiązanie:



















Stąd wszystkie rozwiązania minimalno-argumentowe:

x₃, x₄, x₅, x₇

x₂, x₃, x₅, x₇

x₁, x₄, x₅, x₆, x₇

x₂, x₄, x₅, x₆, x₇





F =


IT PW 4 / 4







x5 x7 x3 x4	00	01	11	10
00	1	1	0	-
01	0	-	0	1
11	0	0	-	-
10	-	0	-	0













Tablica porównań

2,10	x1x2x3x4x6
8,10	x2x4
4,6	x3x4
3,7	x2x3x6
5,7	x3x6
7,11	x1x2x3x4
7,12	x1x2x3

	x3 x4 x5 x7	F
1	0 0 1 1	0
2	1 1 0 0	0
3	1 0 0 1	0
4	0 1 1 0	1
5	1 0 0 1	0
6	1 0 1 0	0
7	0 0 0 1	1
8	0 1 0 0	0
9	0 1 1 1	0
10	0 0 0 0	1
11	1 1 0 1	0
12	1 0 0 1	0

	x1	x2	x3	x4	x5	x6	x7	F
1	1	0	0	0	1	0	1	0
2	0	1	1	1	0	0	0	0
3	1	1	1	0	0	1	1	0
4	1	1	0	1	1	0	0	1
5	1	0	1	0	0	1	1	0
6	1	1	1	0	1	0	0	0
7	1	0	0	0	0	0	1	1
8	1	1	0	1	0	1	0	0
9	1	1	0	1	1	0	1	0
10	1	0	0	0	0	1	0	1
11	0	1	1	1	0	0	1	0
12	0	1	1	0	0	0	1	0

(x₄ + x₂)(x₄ + x₃)(x₃ + x₆)( x₃ + x₁ + x₂) = (x₄ + x₂x₃)( x₃ + x₁x₆ + x₂x₆) =

= x₃x₄ + x₁x₄x₆ + x₂x₄x₆ + x₂x₃ + x₁x₂x₃x₆ + x₂x₃x₆

---