Logik (Teschl/Teschl 1.1 und 1.3)Eine Aussage ist ein Satz, von dem man eindeutigentscheiden kann, ob erwahr (true, = 1) oder falsch (false, = 0) ist.

Beispielea: 1 + 1 = 2b: Darmstadt liegt in Bayern.c: Der 8. April 2013 ist ein Dienstag.d: Das Glas ist halb voll.

Negation1 = ¬1 = 0, 0 = ¬0 = 1

¬ a: 1+ 1 6= 2¬ b: Darmstadt liegt nicht in Bayern.¬ c: Der 8. April 2013 ist kein Dienstag.¬ d: Das Glas ist nicht halb voll.

logik.pdf, Seite 1

Eine Aussageform

a(x): x > 1

besteht aus Variable x und Prädikat �> 1�.

Der Wahrheitswert hängt vom Wert der Variable ab.

All�Aussagen und Existenz�Aussagen

∀x : a(x) � Für alle x gilt die Aussage a(x),

∃x : a(x) � Es gibt ein x , für das a(x) gilt.

Beispiel

∀x ∈ Z : x2 ≥ 0, ∃x ∈ Z : x2 = 4.

logik.pdf, Seite 2

Logische Funktionen (Verknüpfung von Aussagen)

Die Negation ¬a = a kehrt den Wahrheitswert einer Aussage a

um: 0 = 1 und 1 = 0,

d. h. wenn a = 0, so ist a = 1 und umgekehrt.

Zweistellige logische Funktionen

verknüpfen zwei Wahrheitswerte. Die wichtigsten sind

Konjunktion (logisches und, ∧, ∗),a ∧ b ist genau dann wahr, wenn a und b wahr sind,d. h. 0 ∧ 0 = 0 ∧ 1 = 1 ∧ 0 = 0 und 1 ∧ 1 = 1.

Disjunktion (logisches oder, ∨, +),a ∨ b ist genau dann wahr, wenn mindestens eine der beidenAussagen a oder b wahr ist,d. h. 0 ∨ 0 = 0 und 0 ∨ 1 = 1 ∨ 0 = 1 ∨ 1 = 1.

logik.pdf, Seite 3

Weitere zweistellige logische Verknüpfungen

Exklusives oder (xor, ⊕),a ⊕ b ist genau dann wahr, wenn eine der beiden Aussagen a

oder b wahr und die andere falsch ist,d. h. 0⊕ 0 = 1⊕ 1 = 0 und 0⊕ 1 = 1⊕ 0 = 1.

Subjunktion (→, ⇒, wenn-dann)Ist a = 0, so ist a→ b immer wahr, ist a = 1, so ist a→ b

wahr, wenn b wahr ist,d. h. 0→ 0 = 0→ 1 = 1→ 1 = 1 und 1→ 0 = 0.

Äquivalenz (↔, ⇔, genau-dann-wenn)a↔ b ist genau dann wahr, wenn a und b den selbenWahrheitswert haben,d. h. 0↔ 0 = 1↔ 1 = 1 und 0↔ 1 = 1↔ 0 = 0.

logik.pdf, Seite 4

Wertetabellen

Für eine zweistellige logische Funktion gibt es 4 möglicheEingaben, zu denen man die Werte in einer Tabelle au�istenkann. Durch eine solche Wertetabelle (�Wahrheitstafel�) ist dielogische Funktion vollständig beschrieben.

a b a ∧ b a ∨ b a ⊕ b a→ b a↔ b

0 0 0 0 0 1 10 1 0 1 1 1 01 0 0 1 1 0 01 1 1 1 0 1 1

logik.pdf, Seite 5

Logische Äquivalenz

Es gibt insgesamt 24 = 16 unterschiedliche zweistelligelogische Funktionen. Diese sind jeweils auf unterschiedlicheWeise darstellbar.

Vergleicht man z. B. die beiden logischen Funktionen a→ b

und a ∨ b, so stellt man mit Hilfe einer Wertetabelle fest, dasssie für alle Eingaben von a und b den selben Wahrheitswerthaben:

a a b a→ b a ∨ b

0 1 0 1 10 1 1 1 11 0 0 0 01 0 1 1 1

Man sagt, die beiden Funktionen sind logisch äquivalent,Notation

(a→ b)⇔ (a ∨ b) bzw. (a→ b) = (a ∨ b).logik.pdf, Seite 6

Verneinung von All- und Existenzaussagen

∀x : a(x) ⇔ ∃x : a(x):

�Die Aussage a(x) ist nicht für alle x wahr� bedeutet, dass es(mindestens) ein x gibt, für das a(x) falsch ist.

∃x : a(x) ⇔ ∀x : a(x):

�Es gibt kein x, für das a(x) wahr ist� bedeutet, dass a(x) füralle x falsch ist.

Beispiel

¬[∀n ∈ N : 2n ≥ n2

]⇔ ∃n ∈ N : 2n < n2,

¬[∃x ∈ Q : x2 = 2

]⇔ ∀x ∈ Q : x2 6= 2,

logik.pdf, Seite 7

Indirekter Beweis

Die logische Äquivalenz (a→ b)⇔ (b → a) ist Grundlageeiner mathematischen Beweismethode, dem indirekten Beweis.

Um zu beweisen, dass B aus A folgt, zeigt man dass wenn B

falsch ist auch A falsch sein muss.

BeispielsatzIst n ≥ 3 Primzahl, so ist n ungerade.

Beweis: Man zeigt die logische äquivalente Aussage: Ist n ≥ 3gerade, so ist n keine Primzahl.

n gerade ⇒ n durch 2 teilbar ⇒ n keine Primzahl.

Zur Notation: das Zeichen �⇒� steht für die logische

Implikation: Wenn die linke Seite wahr ist, dann ist auch dierechte Seite wahr.

logik.pdf, Seite 8

Rechenregeln für Logische Operationen

(Regeln der Booleschen Algebra)

a ∧ b ⇔ b ∧ a,a ∨ b ⇔ b ∨ a Kommutativität

(a ∧ b) ∧ c ⇔ a ∧ (b ∧ c),(a ∨ b) ∨ c ⇔ a ∨ (b ∨ c) Assoziativität

a ∧ (b ∨ c)⇔ (a ∧ b) ∨ (a ∧ c),a ∨ (b ∧ c)⇔ (a ∨ b) ∧ (a ∨ c), Distributivität

a ∧ b ⇔ a ∨ b,

a ∨ b ⇔ a ∧ b de�Morgan'sche Regeln

a⇔ a doppelte Verneinung

Gleiche Regeln wie bei Mengenoperationen!

logik.pdf, Seite 9

Vereinfachen von logischen AusdrückenBeispiel:

(a ∧ b) ∧ a ⇔ (a ∨ b) ∧ a

⇔ (a ∧ a) ∨ (b ∧ a)⇔ a ∨ (b ∧ a)⇔ a

Disjunktive Normalform (DNF)

Logische Funktionen lassen sich auf wenige �Grundfunktionen�zurückführen. So lässt sich jede zweistellige logische Funktiondurch die Operationen Negation, Disjunktion (∨) undKonjunktion (∧) darstellen:

(x1 ∧ y1) ∨ (x2 ∧ y2) ∨ ... ∨ (xn ∧ yn)

Diese Darstellung heiÿt disjunktive Normalform. Dabei stehendie xi für a oder a und die yi für b oder b.

logik.pdf, Seite 10

DNF am Beispiel Subjunktion

a b a→ b

0 0 10 1 11 0 01 1 1

Die DNF hat dann die Form

(a→ b) = (a ∧ b) ∨ (a ∧ b) ∨ (a ∧ b).

Jeder Klammerausdruck steht dabei für eine Zeile (d. h. füreine Kombination von Wahrheitswerten von a, b als Eingabe),für die der die betrachtete Funktion a→ b denWahrheitswert 1 hat.

logik.pdf, Seite 11

n�stellige logische Funktionen

In gleicher Weise lassen sich auch n�stellige logischeFunktionen mit n > 2 betrachten. Eine n�stellige logischeFunktion hat 2n mögliche Eingaben, deren zugehörigeWahrheitswerte wieder in einer Tabelle aufgelistet werdenkönnen, d. h. die Wahrheitstafel einer dreistelligen logischenFunktion hat beispielsweise 8 Zeilen, die einer vierstelligenFunktion 16 Zeilen.

Beispiel

f (a, b, c) = (a ∧ b)→ c ist eine dreistellige logische Funktion.

Z. B. ist f (1, 1, 1) = (1 ∧ 0)→ 1 = 0→ 1 = 1.

logik.pdf, Seite 12

Beispiel: DNF von f (a, b, c) = (a ∨ c)→ (b ∧ c)

Man erstellt zunächst eine Wertetabelle:

a b c a ∨ c b ∧ c (a ∨ c)→ (b ∧ c)

0 0 0 1 0 00 0 1 1 0 00 1 0 1 1 10 1 1 1 0 01 0 0 0 0 11 0 1 1 0 01 1 0 0 1 11 1 1 1 0 0

Die disjunktive Normalform hat dann die Form

f (a, b, c) = (a ∧ b ∧ c) ∨ (a ∧ b ∧ c) ∨ (a ∧ b ∧ c)

logik.pdf, Seite 13

Vereinfachung des Ausdrucks im Beispiel

Unter Benutzung der Rechenregeln kann c �ausgeklammert�werden:

f (a, b, c) = (a ∧ b ∧ c) ∨ (a ∧ b ∧ c) ∨ (a ∧ b ∧ c)

=((a ∧ b) ∨ (a ∧ b) ∨ (a ∧ b)

)∧ c

Der Ausdruck innerhalb der groÿen Klammer entspricht a ∨ b.Damit erhält man

f (a, b, c) = (a ∨ b) ∧ c .

logik.pdf, Seite 14

Konjunktive Normalform (KNF)

Analog zur DNF lässt sich jede logische Funktion alsKonjuktion von Disjunktionen darstellen, d. h. innerhalb derKlammern stehen Oder�Verknüpfungen und zwischen denKlammerausdrücken Und�Verknüpfungen.

Eine Möglichkeit, die KNF zu erhalten, ist zunächst die DNFvon f zu bestimmen, zum Beispiel ist für f (a, b) = a ⊕ b

f = (a ∧ b) ∨ (a ∧ b).

Die KNF von f erhält man hieraus durch Komplementbildungund Anwendung der de�Morgan�Regeln:

f = (a ∧ b) ∨ (a ∧ b) = (a ∧ b) ∧ (a ∧ b)= (a ∨ b) ∧ (a ∨ b)

logik.pdf, Seite 15

Im Beispiel f (a, b, c) = (a ∨ c)→ (b ∧ c)

erhält man aus der Wertetabelle (siehe vorheriges Beispiel) dieDNF von f

f = (a∧b∧c)∨(a∧b∧c)∨(a∧b∧c)∨(a∧b∧c)∨(a∧b∧c)

Es folgt

f = (a ∧ b ∧ c)∧(a ∧ b ∧ c)∧(a ∧ b ∧ c)∧(a ∧ b ∧ c)∧(a ∧ b ∧ c)

= (a ∨ b ∨ c) ∧ (a ∨ b ∨ c) ∧ (a ∨ b ∨ c) ∧ (a ∨ b ∨ c) ∧ (a ∨ b ∨ c)

Bemerkung

In der KNF entspricht jeder Klammerausdruck einerTabellenzeile, in der f = 0 wird.

logik.pdf, Seite 16

NAND�Verknüpfung (Nicht�Und)

a NAND b = a ∧ b

Jede logische Funktion kann als Kombination vonNAND-Verknüpfungen ausgedrückt werden!

Begründung

Zunächst kann jede logische Funktion in der DNF alsKombinationen von Negationen, Konjunktionen undDisjunktionen dargestellt werden. Also reicht es, dieseVerknüpfungen durch NAND darzustellen:

a = a NAND a, d.h. Negation durch NAND ausgedrückt,

a ∧ b = a NAND b = (a NAND b) NAND (a NAND b),

a ∨ b = a NAND b = (a NAND a) NAND (b NAND b)

Analog: Darstellung durch NOR (Nicht-Oder) möglich.logik.pdf, Seite 17

Addition von Dualzahlen als logische Funktion

Man betrachtet zunächst einen Halbaddierer zur Additioneinstelliger Dualzahlen a, b:

a + b = (os)2 mit

s = s(a, b) = a ⊕ b Summe (sum), rechtes Bit,

o = o(a, b) = a ∧ b Übertrag (over�ow), linkes Bit

Mögliche Hardwareschaltung

a b o s

0 0 0 00 1 0 11 0 0 11 1 1 0

logik.pdf, Seite 18

Volladdierer

Berechnet (sn+1sn...s0)2 = (an...a0)2 + (bn...b0)2.

Die i�te Stufe des Volladdierers wird zusammengesetzt ausHalbaddierern (HA) und Oder�Bausteinen:

logik.pdf, Seite 19