Informatiker Board | Druckvorschau: wohlgeformte formeln

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- wohlgeformte formeln (http://www.informatikerboard.de/board/thread.php?threadid=406)

Geschrieben von newsys am 18.04.2008 um 14:05:

wohlgeformte formeln

Hallo allerseits,

ich habe diese Aufgabe:
Beweisen Sie, dass die Zeichenkette $[latex]((A\wedge B)C)[/latex]$ kein wohlgeformter Ausdruck der Aussagenlogik ist.

Ich habe es nun so gemacht:
Definition 2.2 nach Script Kap 2. Aussagenlogik-Syntax[12]:
Die wohlgeformten Ausdrücke der Aussagenlogik (Formeln) sind induktiv definiert:

1. Alle Aussagensymbole sind (atomare) Formeln. Beispiel: A,B,C,D,...
2. Falls F und G Formeln sind, so sind $[latex](F\wedge G),(F\vee G),(F\Rightarrow G) und (F\Leftrightarrow G) [/latex]$ (komplexe) Formeln.
3. Falls F eine Formel ist, so ist auch $[latex]\neg F[/latex]$ eine (komplexe) Formel.
4. Es gibt keine anderen Formeln, als die, die durch endliche Anwendungen der Schritte 1-3 erzeugt werden.

A ist eine atomare Formel (Definition 2.2.1), da es ein Aussagensymbol ist.
B ist ebenfalls eine atomare Formel (Definition 2.2.1), da es ein Aussagensymbol ist.
Somit ist auch $[latex](A\wedge B)[/latex]$ eine Formel. (Definition 2.2.2)
C ist eine atomare Formel (Definition 2.2.1), da es ein Aussagensymbol ist.
Aber: $[latex]((A\wedge B)C)[/latex]$ ist kein wohlgeformter Ausdruck der Aussagenlogik, da zwischen der ersten geschlossen Klammer und dem C kein Operand vorhanden ist. Somit kann man $[latex]((A\wedge B)C)[/latex]$ nicht durch endliche Anwendungen der Schritte 1-3 erzeugen.

Kann ich das so machen? Gibt es eine andere Art diese Aufgabe zu lösen?

Geschrieben von Tobias am 18.04.2008 um 14:30:

Vorweg: Ja, so kann man es machen. Du gehst von innen nach außen vor. Eine zweite Möglichkeit ist von außen nach innen. Dabei gehst du zuerst einmal davon aus, dass die inneren (komplexen) Formeln wohlgeformt sind und entscheidest, ob die nächst äußeren Formeln konstruierbar sind.

In konkreten Fall:

Annahme: X = (A ^ B) und C sind wohlgeformte komplexe Formeln.
(XC) entspricht keiner gültigen Regel. => Ausdruck nicht wohlgeformt