Formel zu einer Schaltung finden

Die Aufgabe

Die Wahrheitstafel einer Schaltung sei wie folgt gegeben:

Gegebene Tafel

\begin{array}{cc|c} p & q & ? \\ \hline 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{array}

Geben Sie einen logischen Ausdruck für diese Schaltung nur mit $\neg$ , $\land$ und $\lor$ an.

Eine Schaltung hat hier zwei Eingänge $p$ und $q$ und einen Ausgang. Jeder Eingang ist 0 (aus) oder 1 (an). Eine Belegung ist eine Kombination von Werten für $p$ und $q$ , also eine Zeile der Tafel. Die Tafel sagt für alle vier Belegungen, was am Ausgang herauskommt. Diese Spalte heißt ?, weil die Formel dazu fehlt.

Gesucht ist ein Ausdruck aus $p$ und $q$ , der genau diese Spalte liefert. Erlaubt sind nur drei Zeichen: $\neg$ (nicht), $\land$ (und) und $\lor$ (oder).

So gehen wir vor:

Die Begriffe klären: Literal, Konjunktionsterm, disjunktive Normalform.
Die Zeilen suchen, in denen die Schaltung 1 ausgibt.
Für jede dieser Zeilen einen Term bauen, der nur dort 1 ist.
Die Terme mit Oder verbinden und mit einer Tafel prüfen.
Ergänzung: kürzerer Name p ⇔ q und ein zweiter Weg (KNF).

Merke: Eine Formel zu einer Tafel baut man aus den Zeilen mit 1. Jede solche Zeile wird ein Term, der nur dort 1 ist. Die Terme werden mit Oder verbunden.

Literal, Konjunktionsterm, disjunktive Normalform

Aufbau einer DNF

(\text{Literal} \land \text{Literal}) \lor (\text{Literal} \land \text{Literal}) \lor \ldots

Aus Aufgabe 1 („Wahrheitstafeln aufstellen“):

\neg

(Negation) dreht den Wert um.

\land

(Konjunktion, Und) ist nur 1, wenn beide Teile 1 sind;

\lor

(Disjunktion, Oder) ist 1, sobald ein Teil 1 ist. Zeile 1 bis 4 sind

p\,q

= 0 0, 0 1, 1 0, 1 1.

Das Rezept braucht drei Wörter aus der Vorlesung:

Ein Literal ist eine Variable, ihre Verneinung oder eine der Konstanten 0 und 1. Hier brauchen wir nur $p$ , $\neg p$ , $q$ und $\neg q$ .
Ein Konjunktionsterm (kurz: Und-Term) verbindet Literale mit Und, zum Beispiel $\neg p \land q$ . Er ist nur 1, wenn alle seine Literale 1 sind.
Eine disjunktive Normalform (kurz DNF) verbindet solche Terme mit Oder. Disjunktiv heißt: mit Oder verbunden. Sie ist 1, sobald einer der Terme 1 ist.

Eine DNF benutzt also nur $\neg$ , $\land$ und $\lor$ . Genau das verlangt die Aufgabe.

Die Zeilen mit 1 suchen

Zeilen mit Ausgabe 1

(p, q) = (0, 0) \qquad (p, q) = (1, 1)

Die gesuchte Formel soll genau dann 1 sein, wenn die Schaltung 1 ausgibt. Also schaut man nur auf die Zeilen, in denen in der Spalte ? eine 1 steht.

Zeile 1: $p = 0$ , $q = 0$ .
Zeile 4: $p = 1$ , $q = 1$ .

In den Zeilen 2 und 3 steht 0. Für sie braucht man keinen Term.

Formel zu einer Schaltung finden

Die Aufgabe

Literal, Konjunktionsterm, disjunktive Normalform

Die Zeilen mit 1 suchen

Tafel der Schaltung

Abbildung 1Tafel der Schaltung

Zeile	$p$	$q$	?	$\neg p$	$\neg q$	$\neg p \land \neg q$	$p \land q$	$D$	$p \Leftrightarrow q$	$K$
1	0	0	1	1	1	1	0	1	1	1
2	0	1	0	1	0	0	0	0	0	0
3	1	0	0	0	1	0	0	0	0	0
4	1	1	1	0	0	0	1	1	1	1

Schritt 0Die Aufgabe

Schritt 1Literal, Konjunktionsterm, disjunktive Normalform

Schritt 2Die Zeilen mit 1 suchen

Tafel der Schaltung

Abbildung 1Tafel der Schaltung

Die Aufgabe

Literal, Konjunktionsterm, disjunktive Normalform

Die Zeilen mit 1 suchen