Prof. dr hab. Włodzimierz Szmerko

Fellow IEE, Senior Member IEEE

Institute of Computer Science & Information Systems,

Technical University of Szczecin,

January 1999

examin.doc

EXAMINATION`S QUESTIONS ON

Prof. dr hab. Włodzimierz Szmerko

Teoria układów logicznych (Theory of logic design)

Egzaminacyjne pytania testowe (Test questions)

Transformacje ortogonalne funkcji Boolowskich.

1. Dany jest wektor współczynników wielomianu arytmetycznego:

1. Zapisz ten wielomian arytmetyczny.

b) Za pomocą metody macierzowej określ wektor prawdy.

P=[1 0 -1 1 -1 1 2 -3]^T

2. Dany jest wektor współczynników wielomianu arytmetycznego:

1. Zapisz ten wielomian arytmetyczny.

b) Za pomocą metody macierzowej określ wektor prawdy.

P=[0 1 1 -2 0 0 0 1]^T

3. Dany jest wektor współczynników wielomianu arytmetycznego:

1. Zapisz ten wielomian arytmetyczny.

b) Za pomocą metody macierzowej określ wektor prawdy.

P=[1 -1 -1 2 0 0 1 -1]^T

1. Dany jest wektor prawdy funkcji boolowskiej,

1. Za pomocą metody macierzowej zbuduj wielomian Reed-Muller'a.

2. Za pomocą metody macierzowej zbuduj wielomian arytmetyczny.

X=[1 1 0 1 0 1 1 0]^T

2. Dany jest wektor prawdy funkcji boolowskiej,

1. Za pomocą metody macierzowej zbuduj wielomian Reed-Muller'a.

2. Za pomocą metody macierzowej zbuduj wielomian arytmetyczny.

X=[1 0 1 1]^T

3. Dany jest wektor prawdy funkcji boolowskiej,

1. Za pomocą metody macierzowej zbuduj wielomian Reed-Muller'a.

2. Za pomocą metody macierzowej zbuduj wielomian arytmetyczny.

X=[0 1 0 1]^T

1. Dany jest wektor współczynników wielomianu Reed-Muller'a

1. Zapisz wielomian Reed-Muller'a

1. Za pomocą metody macierzowej zbuduj wektor prawdy.

1. Za pomocą metody macierzowej zbuduj wielomian arytmetyczny.

F=[0 1 1 0 0 1 0 0]^T

2. Dany jest wektor współczynników wielomianu Reed-Muller'a

a) Zapisz wielomian Reed-Muller'a

b) Za pomocą metody macierzowej zbuduj wektor prawdy.

c) Za pomocą metody macierzowej zbuduj wielomian arytmetyczny.

F=[1 0 0 1 1 0 1 1]^T

1. Dany jest wektor prawdy funkcji Boolowskiej:

1. Za pomocą metody macierzowej zbuduj wielomian Reed-Muller'a.

2. Narysuj układ na podstawie otrzymanej w punkcie (a) funkcji.

3. Czy za pomocą wielomianów Reed-Muller'a można przedstawić każdą funkcję Boolowską.

X=[1 0 1 0 1 1 1 0]^T

2. Dany jest wektor prawdy funkcji Boolowskiej:

1. Za pomocą metody macierzowej zbuduj wielomian Reed-Muller'a.

2. Narysuj układ na podstawie otrzymanej w punkcie (a) funkcji.

3. Czy za pomocą wielomianów Reed-Muller'a można przedstawić każdą funkcję Boolowską.

X=[1 1 1 0 0 1 1 1]^T

1. Dany jest wektor prawdy funkcji boolowskiej, za pomocą metody macierzowej zbuduj wielomian Reed-Muller'a i wielomian arytmetyczny

X=[1 0 1 1]^T

2. Dany jest wektor prawdy funkcji boolowskiej, za pomocą metody macierzowej zbuduj wielomian Reed-Muller'a i wielomian arytmetyczny

X=[0 1 1 1]^T

Kontrola błędów - Grafy nieskierowane

1. Pokoloruj graf i podaj liczbę chromatyczną.

1. Pokoloruj graf i podaj liczbę chromatyczną.

2. Pokoloruj graf i podaj liczbę chromatyczną.

Algebra Boole'a - twierdzenie Shannona

1. Zastosuj twierdzenie Shannona dla zmiennych x₁x₂ dla funkcji Boolowskiej:

x₁  x₂ (x₁  x₂  x₂ x₃)

1. Zastosuj twierdzenie Shannona dla zmiennych x₂x₃ dla funkcji Boolowskiej:

x₁  x₂ (x₁  x₂  x₂ x₃)

1. Zastosuj twierdzenie Shannona dla zmiennych x₁x₄ dla funkcji Boolowskiej:

x₁  (x₂ (x₃  x₁x₄))

Elementy teorii różniczki logicznej

1. Mając daną funkcję Boolowską: oblicz różniczkę:

∂

∂x₃

1. Metodą symboliczną

2. Metodą macierzową.

3. Jakie własności układu określa różniczka.

2. Mając daną funkcję Boolowską: oblicz różniczkę.

∂

∂x₁

1. Metodą symboliczną

2. Metodą macierzową.

Jakie własności układu określa różniczka.

Minimalizacja

1. Metodą Zakrzewskiego (schodkową- staircase method) zminimalizuj funkcję daną w postaci macierzowej
   i wektora prawdy
   do minimalnej funkcji Reed-Muller'a.

2. Metodą Zakrzewskiego (schodkową- staircase method) zminimalizuj funkcję daną w postaci macierzowej
   i wektora prawdy
   do minimalnej funkcji Reed-Muller'a.

3. Metodą Zakrzewskiego (schodkową- staircase method) zminimalizuj funkcję daną w postaci macierzowej
   i wektora prawdy
   do minimalnej funkcji Reed-Muller'a.

1. Za pomocą metody macierzowej zbadaj czy wielomian arytmetyczny opisuje funkcję boolowską. Jeżeli tak to jaką?

P(X)=1-x₃-x₂+2x₂x₃+x₁x₂-x₁x₂x₃

2. Za pomocą metody macierzowej zbadaj czy wielomian arytmetyczny opisuje funkcję boolowską. Jeżeli tak to jaką?

P(X)=x₂-x₂x₃+x₁-2x₁x₂+x₁x₂x₃

3. Za pomocą metody macierzowej zbadaj czy wielomian arytmetyczny opisuje funkcję boolowską. Jeżeli tak to jaką?

1. Za pomocą metody macierzowej zbadaj czy wielomian arytmetyczny opisuje system funkcji Boolowskich, jeżeli tak to jaki?

P(X)=9-2x₁+4x₁x₂

1. Za pomocą metody macierzowej zbadaj czy wielomian arytmetyczny opisuje system funkcji Boolowskich, jeżeli tak to jaki?

P(X)=2-2x₂+5x₁-3x₁x₂

2. Za pomocą metody macierzowej zbadaj czy wielomian arytmetyczny opisuje system funkcji Boolowskich, jeżeli tak to jaki?

P(X)=2-x₂+3x₁

1. Przekształć funkcję do FCCF (Full Conjunctive Canonical Form), FDCF (Full Disjunctive Canonical Form) i Reed-Muller'a.

f(X)=((x₁~x₂)↑x₃)↑(x₁x₃)

2. Przekształć funkcję do FCCF (Full Conjunctive Canonical Form), FDCF (Full Disjunctive Canonical Form) i Reed-Muller'a.

f(X)=((x₁x₂)→(x₂x₃))(x₁~(x₁x₃))

3. Przekształć funkcję do FCCF (Full Conjunctive Canonical Form), FDCF (Full Disjunctive Canonical Form) i Reed-Muller'a.

f(X)=(x₁x₂x₃↑x₁x₂x₃)(x₁x₂x₃)

1. Narysuj układ wykorzystując bramki NAND

(x₁⊕x₂)~(x₁→x₂)

1. Zbadaj czy funkcja jest:

1. klasy class „0”

2. klasy class „1”

3. klasy class „S”

4. funkcją monotoniczną

5. liniową formą Reed-Muller'a

(x₁x₂x₁x₂)(x₁x₂)

2. Zbadaj czy funkcja jest:

1. klasy class „0”

2. klasy class „1”

3. klasy class „S”

4. funkcją monotoniczną

5. liniową formą Reed-Muller'a

((x₁↑x₂)~x₂)↑(x₁x₂)

3. Zbadaj czy funkcja jest:

1. klasy class „0”

2. klasy class „1”

3. klasy class „S”

4. funkcją monotoniczną

5. liniową formą Reed-Muller'a

((x₁x₂)→(x₁x₂))(x₁~(x₁x₂))

1. Przy pomocy symbolicznych transformacji zbuduj wielomian Reed-Muller'a.

f(X)=x₁x₂x₁+x₂x₃+x₁

1. Przy pomocy symbolicznych transformacji zbuduj wielomian Reed-Muller'a.

f(X)=x₁x₂+x₃x₂x₁x₂x₃

2. Przy pomocy symbolicznych transformacji zbuduj wielomian Reed-Muller'a.

f(X)=x₁x₃+x₂x₁→x₁x₂x₃

1. Przy pomocy symbolicznych transformacji zbuduj wielomian arytmetyczny.

f(X)=x₁x₂~x₃x₂

1. Przy pomocy symbolicznych transformacji zbuduj wielomian arytmetyczny.

f(X)=x₁x₂x₃x₂

2. Przy pomocy symbolicznych transformacji zbuduj wielomian arytmetyczny.

f(X)=(x₁+x₂)↑(x₁+x₂+x₃)

1. Zminimalizuj funkcję i narysuj układ po minimalizacji.

x₁x₂x₃⊕x₁x₂

1. Zminimalizuj funkcję i narysuj układ po minimalizacji.

x₂x₃⊕x₁x₄→(x₁~x₃)(x₁→x₄∪x₁x₂x₃)

2. Zminimalizuj funkcję i narysuj układ po minimalizacji.

(x₁∪x₂)~x₃)→(x₃∪x₁x₃∪x₁(x₃∪x₂x₄))

1. Zapisz wszystkie wielomiany Reed-Muller'a dla funkcji logicznej dwóch zmiennych.

2. Zapisz wszystkie liniowe wielomiany Reed-Muller'a dla funkcji logicznej dwóch zmiennych.

1. Na podstawie mapy Karnaugha (Karnaugh map):

1. Zapisz minimalną funkcję Boolowską f_min(X)

2. 
   Zapisz minimalną funkcję Boolowską f_min(X)

3. Zapisz FDCF (Full Disjunctive Canonical Form)

4. Zapisz FCCF (Full Conjunctive Canonical Form)

2. Na podstawie mapy Karnaugha (Karnaugh map):

1. Zapisz minimalną funkcję Boolowską f_min(X)

2. 
   Zapisz minimalną funkcję Boolowską f_min(X)

3. Zapisz FDCF (Full Disjunctive Canonical Form)

4. Zapisz FCCF (Full Conjunctive Canonical Form)

Logika Arytmetyczna

1. Oblicz za pomocą metody macierzowej:

1. Czy wielomian arytmetyczny opisuje funkcję Boolowską.

2. Jeżeli tak to jaką.

3. Jakiej klasy jest ta funkcja.

P(X)=1-x₃-x₂+2x₂x₃+x₁x₂-x₁x₂x₃

2. Oblicz za pomocą metody macierzowej:

1. Czy wielomian arytmetyczny opisuje funkcję Boolowską.

2. Jeżeli tak to jaką.

3. Jakiej klasy jest ta funkcja.

P (X)=x₂-x₂x₃+x₁-2x₁x₂+x₁x₂x₃

Logika arytmetyczna , systemy funkcji

1. Za pomocą metody macierzowej:

1. zbadaj czy wielomian arytmetyczny opisuje system funkcji Boolowskich,

1. Jeżeli tak to jaki? Jakiej klasy są te funkcje.

1. Wybierz jedną z tych funkcji i przekształć ją do FCCF(Full Conjunctive Canonical Form),FDCF(Full Disjunctive Canonical Form.

D(X)=9-2x₁+4x₁x₂

2. Za pomocą metody macierzowej:

1. zbadaj czy wielomian arytmetyczny opisuje system funkcji Boolowskich,

2. jeżeli tak to jaki? Jakiej klasy są te funkcje.

3. Wybierz jedną z tych funkcji i przekształć ją do FCCF(Full Conjunctive Canonical Form),FDCF(Full Disjunctive Canonical Form.

D(X)=2-2x₂+5x₁-3x₁x₂

3. Za pomocą metody macierzowej:

1. zbadaj czy wielomian arytmetyczny opisuje system funkcji Boolowskich,

1. jeżeli tak to jaki? Jakiej klasy są te funkcje.

1. Wybierz jedną z tych funkcji i przekształć ją do FCCF(Full Conjunctive Canonical Form),FDCF(Full Disjunctive Canonical Form.

D(X)=2-x₂+3x₁

Elementy algebry Boole'a - Formy kanoniczne

1. Przekształć funkcję Boolowską do

1. FCCF (Full Conjunctive Canonical Form)

2. FDCF (Full Disjunctive Canonical Form)

3. Wielomianu Reed-Muller'a.

f(x)=((x₁~x₂)↑x₃)↑(x₁x₃)

2. Przekształć funkcję Boolowską do

1. FCCF (Full Conjunctive Canonical Form)

2. FDCF (Full Disjunctive Canonical Form)

3. Wielomianu Reed-Muller'a.

f(x)=((x₁x₂)→(x₂x₃))(x₁~(x₁x₃))

Algebra Boole'a

1. Zbudować układ na podstawie podanej funkcji Boolowskiej:

1. Wykorzystując bramki logiczne NAND

2. Za pomocą multiplekserów o 2 wejściach i 1 wyjściu

(x₂x₃)~x₁+x₄(x₃→x₁)+x₁x₂x₃

2. Zbudować układ na podstawie podanej funkcji Boolowskiej:

1. Wykorzystując bramki logiczne NAND

2. Za pomocą multiplekserów o 2 wejściach i 1 wyjściu

x₂x₃x₄→x₁+x₃~x₄+x₁⊕x₄

3. Zbudować układ na podstawie podanej funkcji Boolowskiej:

1. Wykorzystując bramki logiczne NAND

2. Za pomocą multipleksera o 2 wejściach i 1 wyjściu

(x₁⊕x₂)~(x₁→x₂)

Algebra Boole'a - Systemy funkcjonalnie pełne

1. Zbadaj czy funkcja Boolowska należy do klasy funkcji:

1. klasy „0”

2. klasy „1”

3. klasy „S”

4. funkcji monotonicznych

5. liniowych form

(x₁x₂x₁x₂)(x₁x₂)

2. Zbadaj czy funkcja Boolowska należy do klasy funkcji:

1. klasy „0”

2. klasy „1”

3. klasy „S”

4. funkcji monotonicznych

5. liniowych form

((x₁↑x₂)~x₂)↑(x₁x₂)

Wielomiany Reed-Muller'a

1. Na podstawie danej funkcji Boolowskiej zbuduj wielomian Reed-Muller'a.

1. Przy pomocy symbolicznych transformacji

2. Metodą macierzową.

3. Za pomocą wektora prawdy

x₁x₂x₁+x₂x₃+x₁

2. Na podstawie danej funkcji Boolowskiej zbuduj wielomian Reed-Muller'a.

1. Przy pomocy symbolicznych transformacji

2. Metodą macierzową.

3. Za pomocą wektora prawdy

x₁x₂+x₃x₂x₁x₂x₃

3. Na podstawie danej funkcji Boolowskiej zbuduj wielomian Reed-Muller'a.

1. Przy pomocy symbolicznych transformacji

2. Metodą macierzową.

3. Za pomocą wektora prawdy

x₁x₃+x₂x₁→x₁x₂x₃

Logika arytmetyczna

1. Mając daną funkcję Boolowską zbudować wielomian arytmetyczny.

a) Przy pomocy symbolicznych transformacji

b) Metodą macierzową

x₁x₂~x₃x₂

2. Mając daną funkcję Boolowską zbudować wielomian arytmetyczny.

a) Przy pomocy symbolicznych transformacji

b) Metodą macierzową

x₁x₂x₃x₂

Minimalizacja

1. Zminimalizować funkcję i narysować układ logiczny realizujący funkcję po minimalizacji.

a) metodą symbolicznych transformacji

b) metodą minimalizacji Karnaugh'a

c) metodą Quine'a McCluskey'a

x₁x₂x₃ ⊕x₁x₂

2. Zminimalizować funkcję i narysować układ logiczny realizujący funkcję po minimalizacji.

a) metodą symbolicznych transformacji

b) metodą minimalizacji Karnaugh'a

c) metodą Quine'a McCluskey'a

x₂x₃⊕x₁x₄→(x₁~x₃)(x₁→x₄∪x₁x₂x₃)

---