ApCoCoA-1:Examples Tutorial De Logic

Etwas Aussagen-Logik

In der Logik ist man auf der Suche nach Wahrheitswerten von Formeln. Logische Formel können entweder "wahr" (Wahrheitswert 1) oder "falsch" (Wahrheitswert 0) sein. Die Suche nach den Wahrheitswerten einer Formel verwandeln wir, wie schon bei der Suche nach den Lösungen eines linearen Gleichungssystems (siehe Kapitel Lineare Gleichungssysteme), in die Suche nach Nullstellen. Dies bedeute für uns, dass wir die logischen Formeln in Polynome über dem Körper $\mathbb {F} _{2}$, welcher nur aus den Elementen 0 und 1 besteht, übersetzen müssen.

Zuallererst müssen wir festlegen, wie wir Texte in aussagenlogische Formeln übersetzen. Dafür brauchen wir zunächst mal Abkürzungen (hier $A$ und $B$), welche für eine Aussage stehen, die entweder wahr oder falsch sein kann.

Diese Übersetzungen haben dann, abhängig von den Wahrheitswerten von $A$ und $B$, die folgenden Wahrheitswerte.

Diese logischen Formeln übersetzen wir jetzt in Polynome über $\mathbb {F} _{2}$, so dass die Belegung "Wahrheitswert 1" in die "Nullstelle 1" übersetzt wird.

So gilt z.B. $ab+a=0$ für die folgenden Kombinationen von $a$ und $b$: $a,b=0$, $a=0,b=1$ und $a,b=1$. Dies sind genau die gleichen Werte, bei denen $A\Rightarrow B$ den Wahrheitswert 1 hat ($A,B=0$, $A=0,B=1$ und $A,B=1$).

Die ganze Sache funktioniert natürlich nur dann, wenn man für $A$ und $B$ nicht nur Elementarereignisse einsetzen kann, sondern auch schon erzeugte logische Formeln/Polynome. Die Übersetzungsregeln ändern sich nur geringfügig, vorausgesetzt wir haben bereits mit den obigen Regeln die Formeln $F$ und $G$ in die Polynome $f$ und $g$ übersetzt.

Setzen wir für $f$ die Übersetzung von $A$, also $a+1$, und für $g$ die Übersetzung von $B$, also $b+1$, ein, so erhalten wir über $\mathbb {F} _{2}$ die obige Tabelle zurück. Hierbei ist zu beachten, dass im Polynomring $\mathbb {F} _{2}\left[x,y\right]$ $1+1=0$ gilt, also gilt auch $2f=0$ unabhängig von $f$.

Beispiel

In einer Firma werden zur Zeit die drei Projekte $A$, $B$ und $C$ bearbeitet. Um herauszufinden, welche Projekte bis zum Ende der Woche abgeschlossen werden, befragt der Chef der Firma die jeweiligen Projektleiter und erhält folgende Angaben:

1) Es können nicht alle Projekte fertiggestellt werden.

2) Um Projekt $B$ fertigstellen zu können, muss Projekt $A$ fertiggestellt sein.

3) Es wird auf jeden Fall Projekt $B$ oder Projekt $C$ fertiggestellt.

4) Projekt $C$ kann nur fertiggestellt werden, wenn Projekt $B$ fertiggestellt ist.

Bestimmen Sie diejenigen Projekte, die bis zum Ende der Woche fertiggestellt werden.

Lösung mit CoCoA

Festlegung der Abkürzungen:

$A$ = "Projekt $A$ wird bis Ende der Woche fertig" = $a+1$,

$B$ = "Projekt $B$ wird bis Ende der Woche fertig" = $b+1$,

$C$ = "Projekt $C$ wird bis Ende der Woche fertig" = $c+1$.

Übersetzung der Aussagen:

"Es können nicht alle Projekte fertiggestellt werden":

$F_{1}:=\neg \left(A\wedge B\wedge C\right)$.

Zuerst übersetzten wir $\left(A\wedge B\right)$ mittels der ersten Tabelle zu $ab+1=:f$ und $C$ zu $c+1=:g$, damit wird dann (siehe zweite Tabelle) $\left(\left(A\wedge B\right)\wedge C\right)$ zu $\left(ab+1\right)\left(c+1\right)+\left(ab+1\right)+\left(c+1\right)=abc+1$. Jetzt fehlt nur noch das $\neg$ in der Übersetzung, also lautet das zugehölrige Polynom

$f_{1}=abc$.

"Um Projekt $B$ fertigstellen zu können, muss Projekt $A$ fertiggestellt sein":

$F_{2}:=\left(B\Rightarrow A\right)$,

mit dem zugehörigen Polynom

$f_{2}=ba+b$.

"Es wird auf jeden Fall Projekt $B$ oder Projekt $C$ fertiggestellt":

$F_{3}:=\left(B\vee C\right)$,

das zugehörige Polynom lautet

$f_{3}=bc+b+c+1$.

"Projekt $C$ kann nur fertiggestellt werden, wenn Projekt $B$ fertiggestellt ist":

$F_{4}:=\left(C\Rightarrow B\right)$,

und

$f_{4}=cb+c$.

CoCoA

Zuerst müssen wir in {\CoCoA} den passenden Ring eingeben

Use S::=Z/(2)[a,b,c];

Dann brauchen wir noch das Körperideal, welches die Nullstellen auf $0$ und $1$ festlegt

K:=Ideal(a^2+a, b^2+b, c^2+c);

Als nächstes geben wir die übersetzten Polynome ein

I:=Ideal(abc, ba+b, bc+b+c+1, cb+c) + K;

und erhalten mittels

ReducedGBasis(I);

die Antwort

[b+1, a+1, c].

Antwort:

Also müssen der Wahrheitswert von $A$, die Nullstelle von $a+1$, und der Wahrheitswert von $B$, die Nullstelle von $b+1$, $1$ sein und der Wahrheitswert von $C$, die Nullstelle von $c$, $0$. Also werden die Projekte $A$ und $B$ bis Ende der Woche fertig.

---

Weiter geht's im Kapitel Ein rundes Beispiel.

---