Algebra Boole'a. Prawa Demorgana



Pobieranie 91.63 Kb.
Data28.04.2016
Rozmiar91.63 Kb.

Algebra Boole'a. Prawa Demorgana

 1. Algebra Boole'a. Prawa Demorgana


Zależności logiczne zostały ujęte w algebrze Boole'a. W oparciu o zasadę tej algebry możemy tworzyć układy, które będą działać w sensie logicznym identycznie jak układy o większej liczbie elementów. Za pomocą zasad tej algebry dokonujemy minimalizacji układów logicznych. Jedną z reguł algebry Boole'a są prawa Demorgana:



I prawo Demorgana

Zaprzeczenie koniunkcji (iloczynu logicznego) równej jest sumie zaprzeczeń.



II prawo Demorgana

Zaprzeczenie sumy logicznej jest równe iloczynowi logicznemu.


Znając zależności logiczne dla sumy i iloczynu logicznego oraz negacji można te prawa udowodnić. W tym celu sporządzamy tablicę pracy elementów określonych logiką Demorgana.

Początek formularza



x1

x2











0

0




 1

1




1

0

1




 1

1




1

1

0




 1

0




1

1

1




 0

0




0

I prawo Demorgana jest prawdziwe, ponieważ i są równe.

Dół formularza

Początek formularza



x1

x2











0

0







1

1




0

1







1

0




1

0







0

1




1

1







0

0



II prawo Demorgana jest prawdziwe, ponieważ i są równe.

Dół formularza

Zad.1

Jak sobie poradzi uczeń, który zna prawa Demorgana i okaże się, że chce zrealizować operacje logiczną , a w sprzedaży brakuje bramek iloczynu logicznego, są natomiast bramki sumy logicznej i negacji.



Odp.:

Rys. 1. Realizacja funkcji przy użyciu dwóch bramek negacji i bramki OR.

Na wyjściu Y otrzymujemy sygnał

W algebrze Boole'a obowiązują następujące podstawowe prawa:



  1. Prawo przemienności dodawania i mnożenia
    a×b b =×a
    b+a a+b =

  2. owarP :icśonzcął

    1. aineżonm
      a×b×c b(a =×)c a( =×c)b

    2. ainawadod
      c+b+a )c+b(+a = c+)b+a( =

  3. owarP icśonleizdzor

    1. aineżonm ainawadod medęlgzw
      a = )c+b(a×a+b×c

    2. ainawadod aineżonm medęlgzw
      b+a×c )b+a( =×)c+a(




a+1 = 1

a+ = 1

a+0 = a

a×0 0 =

a× = 0

a+a×b = a

a×a a =

a×1 = a

a+a = a

a×a+b× a =

a(a+b) = a

a(b+c) = ab+ac

a(+b) = a×b

(a+b)(a+) = a

(a+b)+c = a+(b+c)

= a

a+b = a+b

a+bc = (a+b)(a+c)

Zad. 2

Udowodnić jedną z tożsamości algebry Boole'a



Odp:.

Wybieramy jedną zależność: a+bc = (a+b)(a+c) i tworzymy dla niej tablicę prawdy:

Początek formularza


a

b

c

a+b

a+c

(a+b)(a+c)

a+bc

bc

0

0

0

0










0

0

0

1

0










0

0

1

0

1










0

0

1

1

1










1

1

0

0

1










0

1

0

1

1










0

1

1

0

1










0

1

1

1

1










1

Proszę zwrócić uwagę na stany w kolumnach a, b, c. Nie zostały one wpisane losowo, tylko zgodnie z wrastającą liczbą dziesiętną. Dlatego na początku są stany 000, które reprezentują liczbę 0, później 001 dla liczby 1, oraz 010 dla 2, 011 - 3, 100 - 4, aż do 111, czyli liczby 7. Najważniejsze jest aby stanów było 23 czyli 8.

Dół formularza

Kolumny (a+b)(a+c) i a+bc są sobie równe, a więc zależność: a+bc = (a+b)(a+c) jest prawdziwa.



Zad. 3.

Zbudować układ rozwinięty i uproszczony, który będzie pracował jak: ab+a



Odp.:

Układ rozwinięty

Od razu widać, że w układzie występują dwa sygnały "a" i "b":




Rys. 2. Sposób zaznaczania sygnałów "a" i "b".

Następnie postępując zgodnie z podstawowymi zasadami matematycznymi (najpierw mnożenie, później dodawanie), przyglądamy się pierwszemu członowi - iloczynowi ab. Taki iloczyn możemy zrealizować za pomocą bramki AND:



Teraz zajmujemy się drugim składnikiem a:



Dwa składniki są połączone sumą, a więc wyjścia bramek łączymy za pomocą bramki OR:



Rys. 3. Kompletny układ realizujący funkcję: ab+a



Układ uproszczony

Przyglądamy się równaniu ab+a i zastanawiamy się, w jaki sposób można go uprościć. Można wyłączyć "a" przed nawias: 


a(b+
Szukamy w zależnościach algebry Boole'a czemu jest równe b+
b+=1. 
Podstawiamy do równania: 
a×1=a, czyli
ab+a = 1.
Okazuje się, że układ uproszczony ma postać przewodu o sygnale "a":

Czyli w cale nie musimy budować skomplikowanego układu z rys. 3, bo tak samo będzie "pracował" przewód o sygnale "a".



Twierdzenie

W przypadku kiedy iloczyn i suma ma więcej sygnałów niż dwa, to obowiązują te same zasady iloczynu i sumy co dla dwóch sygnałów. Jeżeli mamy n sygnałów, to wszystkich możliwych kombinacji może być 2n.



Zad. 4.

Stworzyć tablicę pracy bramki AND trójwejściowej.



Odp.:

Ponieważ mamy trzy sygnały (n=3), więc kombinacji jest 8. Zgodnie z twierdzeniem, kiedy iloczyn ma więcej sygnałów, to obowiązują te same zasady, co dla dwóch sygnałów, czyli tablica prawdy przedstawia się następująco:



x1

x2

x3

x1×x2×x3

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

0

1

0

0

0

1

0

1

0

1

1

0

0

1

1

1

1

Zad. 5

Korzystając z tożsamości algebry Boole'a uprościć wyrażenie: (a+)[abc+(a+c)]+ab(a+b).



Odp.:

(a+)[abc+(a+c)]+ab(a+b)=(a+)(abc+a+c)+ab(a+b)=aabc+aa+ac+abc+a+c+aba+


+abb=abc+a+ac+0+a+c+ab+ab=abc+a+ac+c+ab=ab(c+)+a(1+c)+c=ab+a+c=a(b+)+c=a+c

Czyli jeżeli wykonalibyśmy dużym nakładem pracy układ pracujący jak: (a+)[abc+(a+c)]+ab(a+b), to działałby tak samo jak układ: a+c. Z tymże układ drugi jest o wiele tańszy w wykonaniu, niezawodny (tylko jedna bramka AND i OR) i mniej pracochłonny. O potrzebie dokonywania uproszczeń nie trzeba chyba nikogo przekonywać.


©absta.pl 2016
wyślij wiadomość

    Strona główna