02 Logische Grundfunktionen

Logische Grundfunktionen

Hier geht es um dieselbe Aussagenlogik wie in GDS (siehe GDS: Aussagenlogik), nur in der Schreibweise der Technik: 0/1 statt f/w, und als Bausteine für Schaltungen.

2.1 NAND und NOR

Definition

• NAND („not and“): $\neg (A\wedge B)$, nur 0, wenn beide Eingänge 1 sind
• NOR („not or“): $\neg (A\vee B)$, nur 1, wenn beide Eingänge 0 sind

A	B	NAND	NOR
0	0	1	1
0	1	1	0
1	0	1	0
1	1	0	0

2.2 De Morgan

Regeln von De Morgan

$\neg (A\vee B)=\neg A\wedge \neg B\text{(NOR)}$ $\neg (A\wedge B)=\neg A\vee \neg B\text{(NAND)}$

Fallstrick

Beim Negieren dreht sich der Operator um (∧ ↔ ∨). In der Mitschrift vom 10.10. stehen die Regeln mit dem gleichen Operator auf beiden Seiten. Das ist falsch. Gegenprobe: $A=1,B=0$ → NOR $=0$, aber $\neg A\vee \neg B=0\vee 1=1$.

Merkhilfe

„Strich zerbrechen, Zeichen wechseln“: Der Negationsstrich über $A\wedge B$ wird in zwei Striche zerlegt, und aus ∧ wird ∨.

2.3 Äquivalenz

$A\leftrightarrow B=\neg A\neg B\vee AB$

(„beide 0 oder beide 1“; ohne Operator geschrieben bedeutet $AB$ hier $A\wedge B$.)

2.4 Mengen in Logik-Schreibweise (Arbeitsblätter S. 39)

Mengenbeziehungen lassen sich als logische Formeln über die Elemente schreiben:

Mengenbegriff	Logische Formel
Teilmenge $A\subseteq B$	$\forall a(a\in A\to a\in B)$
echte Teilmenge $A\subset B$	$\forall a(a\in A\to a\in B)\wedge \exists a(\overline{a\in A}\wedge a\in B)$
Vereinigung	$\forall a(a\in A\cup B\leftrightarrow a\in A\vee a\in B)$
Schnitt	$\forall a(a\in A\cap B\leftrightarrow a\in A\wedge a\in B)$
disjunkt	$\overline{\exists a(a\in A\wedge a\in B)}$, d.h. $A\cap B=\varnothing$

Zur Folie

Auf der Folie steht bei $A\subseteq B$ zusätzlich „$\vee A=\varnothing$“. Das ist eigentlich überflüssig: Für $A=\varnothing$ ist $a\in A$ immer falsch, die Implikation also immer wahr. Der Zusatz macht diesen Sonderfall nur sichtbar.

In der Vorlesung durchgespielt mit $A=\{0,1,3,7\}$, $B=\{0,1,2,3,5,7\}$:

• $A\subseteq B$ ✓ und sogar $A\subset B$ (z.B. $2\in B$, $2\notin A$)
• $A\cup B=B$, $A\cap B=A$
• nicht disjunkt

Selbsttest

Baue NOT, AND und OR nur aus NAND-Gattern. (Tipp: $\neg A=\text{NAND}(A,A)$.)

Zurück: 01 Zahlensysteme · Weiter: 03 Boolesche Funktionen und Addierer