1. Grundlagen der Informatik Boolesche Algebra / …

1 Peter Sobe11. Grundlagen der InformatikBoolesche Algebra / AussagenlogikInhalt Grundlagen digitaler Systeme Boolesche Algebra / aussagenlogik Organisation und Architektur von Rechnern Algorithmen, Darstellung von Algorithmen mit Struktogrammen und Programmablaufpl nen Zahlensysteme und interne InformationsdarstellungPeter Sobe2 Boolesche AlgebraLogikkalk l (George Boole, 1847) Definition:Eine Menge B von Elementen, ber der zwei Operationen (+ und *) erkl rt sind, ist genau dann eine Boolesche Algebra (B.)

2 +, *), wenn f r beliebige Elemente a, b, c B folgende Axiome gelten:(1) a+b = b+aa*b = b*a(2) 0+a=a1*a=a(3) (a+b)*c = (a*c)+(b*c)(a*b)+c = (a+c)*(b+c)(4) a+k(a)=1a*k(a)=0 Kommutativit tNullelement 0 bzgl. + und Einselement 1 bzgl. * existiertDistributivit t einer Op. gegen ber der anderen jedem Element a B existiert ein komplement res Element k(a)Peter Sobe3 Boolesche AlgebraDualit tsprinzip:Zu jeder Aussage, die sich aus den vier Axiomen der Booleschen Algebra herleiten l sst, existiert eine duale Aussage, die dadurch entsteht, dass man die Operationen + und * und gleichzeitig die neutralen Elemente 0 und 1 gelten weiterhin.

3 (5)a+1 = 1a*0 = 0(6)a+a=aa*a=a(7)a+(a*b) = aa*(a+b) = a(8)k(a) + (a+b)=1k(a)*(a*b) = 0(9)a+(b+c) = (a+b)+ca*(b*c) = (a*b)*cIdempotenzgesetzAbsorptionsgesetz AssoziativgesetzPeter Sobe4 Boolesche AlgebraEs gelten weiterhin (Fortsetzung):(10)F r jedes a aus B existiert genau ein a aus b = a, b = a. (11) 1 = 0 0 = 1(12)(a+b) = a * b(a*b) = a + bDie Boolesche Algebra legt noch keinen speziellen Anwendungsfall , was aus Elementen und Operationen besteht, kann eine Boolesche Algebra sein, sofern die oben genannten Eigenschaften der NegationDe Morgansches GesetzPeter Sobe5 Boolesche AlgebraAnwendung als.

4 Mengenalgebra Schaltalgebra AussagenlogikDie Schaltalgebra und aussagenlogik entsprechen einander bez glich ihrer Variablen, Operationen und Gesetzm Sobe6 Anwendung als SchaltalgebraSchaltvariablev {0,1}Bin re Schaltfunktion:f: {0,1}N {0,1}z = f(v1,v2, .., vN); z, vi {0,1}f(v1,v2, .., vN) ..Peter Sobe7 Anwendung als SchaltalgebraDefinition einer Schaltfunktion durch eine WahrheitstafelN-stellige Funktionm=2 NEingabemuster 2mverschiedene N-stellige Schaltfunktionen nur einespezielle Schaltfunktion gezeigtPeter Sobe8 Anwendung als SchaltalgebraEinstellige Schaltfunktionen durch eine Wahrheitstafel1-stellige Funktionm=21=2 Eingabemuster 2m = 22= 4 verschiedene einstellige Schaltfunktionen aNullfunktion Identit tNegationEinsfunktion0001110101 Peter Sobe9 Anwendung als

5 SchaltalgebraZweistellige Schaltfunktionen durch eine Wahrheitstafel2-stellige Funktionm=22=4 Eingabemuster 2m = 24= 16 verschiedene einstellige Schaltfunktionen5 Funktionen hier als sinnvolle herausgestellt ab 0 0 00110110 0 01110111 0 Sobe10 Anwendung als SchaltalgebraAusgew hlte Funktionen:UNDODERNEGATIONL=A UND BA=1A=0B=1B=0L=A ODER BA=1A=0B=1B=0A=1A=0L= NICHT (A)Peter Sobe11 Anwendung als SchaltalgebraAusgew hlte Funktionen:UND mit negiertem Operanden AUND mit negiertem Operanden BL=A UND NICHT(B)A=1A=0B=1B=0L=NICHT(A) UND BA=0B=0A=1B=1 Peter Sobe12 Anwendung als SchaltalgebraAusgew hlte Funktionen:UND mit negierten Operanden A und BODER mit negierten Operanden A und BL=NICHT(A) UND NICHT(B)DE MORGAN:L = NICHT(A ODER B) A=0B=0 NOR-Funktion(ODER, das am Ausgang negiert ist)L=NICHT(A) ODER NICHT(B)DE MORGAN.

6 L = NICHT ( A UND B)A=0B=1B=0A=1 NAND-Funktion(UND, das am Ausgang negiert ist)Peter Sobe13 Anwendung als SchaltalgebraAusgew hlte Funktionen:XOR-Funktion (exklusives ODER)L=( NICHT(A) UND B) ODER (A UND NICHT(B))L= A XOR BA=0A=1A=0A=1B=1B=0B=1B=0 Peter Sobe14 SchaltalgebraDie Schaltalgebra ist eine spezielle Boolesche AlgebraB:= {0,1}Nullelement: 0 .. bedeutet Schalter ge ffnetEinselement: 1 .. bedeutet Schalter geschlossenOperation +: ODER Operation *: UNDN egation :NICHT( )Es gelten die Axiome 1 bis 4 der Booleschen restlichen Regeln k nnen hergeleitet Sobe15 SchaltalgebraDie Axiome der Booleschen Algebra gelten.

7 (1)a+b = b+a= a*b = b*a=(2) 0+a=a= 1*a=a= abbaabba0aaa1aPeter Sobe16 SchaltalgebraDie Axiome der Booleschen Algebra gelten.(3)(a+b)*c = (a*c)+(b*c)= (a*b)+c = (a+c)*(b+c)=(4)a+k(a)=1=a*k(a)=0= abccabcbcaccabaa1aa0 Peter Sobe17 SchaltalgebraSchaltsymbole f r die gebr uchlichsten Funktionen:UNDODERNEGATIONXOR& 11=1 Peter Sobe18 SchaltalgebraSchaltsymboleNANDNORN egierte Eing nge,Am Beispiel NICHT(a) UND b& 1&Peter Sobe19 SchaltalgebraVollst ndige Verkn pfungsbasisMit NAND l sst sich jede beliebige Schaltfunktion.

8 A ODER B = NICHT (NICHT(A) UND NICHT(B)) &&&&&&Peter Sobe20 Anwendung als AussagenlogikAussagen sind formulierte Feststellungen, zum Beispiel T r geschlossen Bedingungen, zum Beispiel x<5 Relationen, wie a(i)<a(i+1) berechnete Aussagen, wie 2000 ist ein Schaltjahr Aussagen .. k nnen den Ablauf (Steuerfluss) eines Programms beeinflussen k nnen logisch verkn pft werden und ergeben neue Aussagen sind m glicherweise Eingabe oder Ausgabe von Programmen und werden durch Programme berechnet Peter Sobe21 AussagenlogikDie aussagenlogik ist eine Boolesche gelten damit die Gesetze der Booleschen zur aussagenlogik : Werte:falsch und wahrals Entsprechung f r 0 und 1 Operationen.

9 Bezeich-nungOperator-SymbolC-OperatorKon junktionUNDAND &&DisjunktionODEROR ||NegationNICHTNOT ( berstrich)!Peter Sobe22 aussagenlogik Definition der Operationen UND, ODER, NICHT ber Wahrheitstabellen a UND b a ODER b NICHT aaba UND bfalschfalschfalschfalschwahrfalschwahrf alschfalschwahrwahrwahr aba ODER bfalschfalschfalschfalschwahrwahrwahrfal schwahrwahrwahrwahr aNICHT afalschwahrwahrfalschPeter Sobe23 Vergleich zw. aussagenlogik und SchaltalgebraAussagenlogik f r Programme (Software)Schaltalgebra zur Realisierung von Schaltungen (Hardware) Die Unterscheidung verschwindet, wenn Hardware direkt programmierbar wird, FPGAs.

10 If (a>b && a<c) {..}else {..}abcCOMPPQ&P>QP=QP<QCOMPPQP>QP=QP<QPeter Sobe24 Bedingungs-Ausdr ckeEinzelne Aussagen k nnen Bedingungsausdr cke seinAusage kalt: temperatur <10 Aussage zu_schnell: V >100 Bedingungsausdr cke werden durch aussagenlogische Operationenverkn :NICHT (zahl < 0) UND NICHT (zahl > 64)zahl >= 0 UND zahl <= 64 NICHT (zahl <0 ODER zahl >64)Alle drei Beispiele bedeuten das gleiche sie dr cken aus, dass zahl im Intervall zwischen 0 und 64 liegtPeter Sobe25 Eigenschaften (1) a UND b = b UND a Kommutativit t bez glich UND a ODER b = b ODER aKommutativit t bez glich ODERa UND wahr = a Neutrales Element (wahr) bez glich UND a ODER falsch = aNeutrales Element (falsch) bez glich ODERa UND k(a)