Rotation ofˆ

176

Przykład 3.13 [4]

Należy znaleźć rozwiąanie tablicy implikantów przedstawionej na rys. 3.20.

Proste \.F implikanty\v	a	b	C	d	e
A	V			V
B		V	V		V
C		V		V
D	V		V		V
E	V	V			V
		i

Rys. 3.20. Tablica Quine’a (przykład 3.13)

Tablica ta nie zawiera zasadniczych prostych implikantów, jak również nie można tu zastosować reguÅ‚ dominacji wierszy i kolumn. Analiza Petricka opiera sie na nastÄ™pujÄ…cym rozumowaniu: do nakrycia jedynki a potrzebny jest implikant A lub D lub E. do nakrycia jedynki b -implikant B lub C lub E. do nakrycia c - implikant B lub D. do nakrycia d - implikant A lub C, do nakrycia e - implikant B lub D lub E. Można to zapisać w postaci nastÄ™pujÄ…cego wyrażenia logicznego:

(A+D+E)(B+C+E)(B+D) (A+C) (B+D+E) (3.57)

Wyrażenie to musi przyjąć wartość logicznÄ… "prawda", aby speÅ‚niony byÅ‚ warunek nakrycia wszystkich jedynek. StosujÄ…c kolejne przeksztaÅ‚cenia uzyskuje siÄ™:

(A+D+E)(B+D+E)(B+C+E)(B+D)(A+C)

= (AB+D+E)

B+(C+E)D

= (AB+D+E)(B+CD+DE)

(A+C) A+C) =

(A+C) = (A+C) =

(3.58)

(AB+ABCD+ABDE+BD+CD+DE+BE+CDE+DE) [aB+CD(AB+1)+BD(AB+l)+DE(1+C)+Be1 (AB+CD+BD+DE+BE)(A+C) =

_ AB+ACD+ABD+ADE+ABE+ABC+CD+BCD+CDE+BCE =

„ _AB(1+D+E+C)+CD(A+1+B+E)+ADE+ECE =

= ab+cd+ade+bce.

Iloczyny ostatniego wyrażenia oznaczajÄ…, które zbiory implikantów należy wybrać, żeby otrzymać wartość "prawda" wyrażenia (3.58) a zatem i wyrażenia (3.57), tzn. żeby nakryć wszystkie jedynki funkcji. Minimalnymi rozwiÄ…zaniami sÄ… wiÄ™c zbiory (A,B> oraz.(C.DK

Na podstawie dotychczasowych rozważali sformuÅ‚ować można peÅ‚ny algorytm realizacji Etapu II w metodzie Quine'a-McCluskey’a. Przedstawiono go na rys. 3.21, a dodatkowo zilustrowano na poniższym przykÅ‚adzie.

Przykład 3.14 [11]

Należy rozwiÄ…zać tablicÄ™ Quine’a przedstawionÄ… na rys. 3.22a. W tablicy tej nie wystÄ™pujÄ… zasadnicze proste implikanty, natomiast można do niej zastosować reguÅ‚y dominacji wierszy i kolumn. W rezultacie, uzyskuje siÄ™:

Aa C, B a F, E a G. E a I. Hal,    (3.59)

a aj, bac, e a k\ fad, gak, h a c. lac, lah

2 tablicy z rys. 3.22a należy zatem usynąć wiersze C.F.G,I oraz kolumny a,b,e,f,g,h,1. W ten sposób uzyskuje siÄ™ tablicÄ™ z rys. 3.22b. Nie wystÄ™pujÄ… w niej wtórne zasadnicze implikanty, natomiast można do niej zastosować reguÅ‚Ä™ dominacji wierszy, gdyż

V.

A a D    (3.60)

UsuwajÄ…c wiersz D uzyskuje siÄ™ tablicÄ™ z rys. 3.22c. WystÄ™puje w ^nieJ jeden wtórny zasadniczy implikant A. WykreÅ›lajÄ…c wiersz A oraz nakrywane przezeÅ„ kolumny (jedynki) d.j uzyskuje siÄ™ tablicÄ™ z rys. 3-22 d. W tablicy tej nie wystÄ™pujÄ… wtórne zasadnicze implikanty ani ^też nie można do niej zastosować reguÅ‚ dominacji wierszy i kolumn. Należy zatem przeprowadzić analizÄ™ PÄ™tricka: