ApCoCoA-1:Examples Tutorial De Logic

From ApCoCoAWiki
Revision as of 10:10, 18 July 2008 by StK (talk | contribs)

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 , 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 und ), welche für eine Aussage stehen, die entweder wahr oder falsch sein kann.

Logik 1.png

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

Logik 2.png

Diese logischen Formeln übersetzen wir jetzt in Polynome über , so dass die Belegung "Wahrheitswert 1" in die "Nullstelle 1" übersetzt wird.

Logik 3.png

So gilt z.B. für die folgenden Kombinationen von und : , und . Dies sind genau die gleichen Werte, bei denen den Wahrheitswert 1 hat (, und ).

Die ganze Sache funktioniert natürlich nur dann, wenn man für und 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 und in die Polynome und übersetzt.

Logik 4.png

Setzen wir für die Übersetzung von , also , und für die Übersetzung von , also , ein, so erhalten wir über die obige Tabelle zurück. Hierbei ist zu beachten, dass im Polynomring gilt, also gilt auch unabhängig von .


Beispiel

In einer Firma werden zur Zeit die drei Projekte , und 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 fertigstellen zu können, muss Projekt fertiggestellt sein.

3) Es wird auf jeden Fall Projekt oder Projekt fertiggestellt.

4) Projekt kann nur fertiggestellt werden, wenn Projekt fertiggestellt ist.

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


Lösung mit CoCoA

Festlegung der Abkürzungen:

= "Projekt wird bis Ende der Woche fertig" = ,

= "Projekt wird bis Ende der Woche fertig" = ,

= "Projekt wird bis Ende der Woche fertig" = .


Übersetzung der Aussagen:

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

.

Zuerst übersetzten wir mittels der ersten Tabelle zu und zu , damit wird dann (siehe zweite Tabelle) zu . Jetzt fehlt nur noch das in der Übersetzung, also lautet das zugehölrige Polynom

.

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

,

mit dem zugehörigen Polynom

.

"Es wird auf jeden Fall Projekt oder Projekt fertiggestellt":

,

das zugehörige Polynom lautet

.

"Projekt kann nur fertiggestellt werden, wenn Projekt fertiggestellt ist":

,

und

.


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 , die Nullstelle von , und der Wahrheitswert von , die Nullstelle von , sein und der Wahrheitswert von , die Nullstelle von , . Also werden die Projekte und bis Ende der Woche fertig.






Weiter geht's im Kapitel Ein rundes Beispiel.