Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » wohlgeformte formeln

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

wohlgeformte formeln

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

newsys
Jungspund

Dabei seit: 04.11.2007
Beiträge: 15

wohlgeformte formeln

Zitatantwort auf diesen Beitrag erstellen

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?

18.04.2008 14:05

Nehmen Sie newsys in Ihre Freundesliste auf

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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

18.04.2008 14:30

Nehmen Sie Tobias in Ihre Freundesliste auf

newsys
Jungspund

Dabei seit: 04.11.2007
Beiträge: 15

Ok - danke!

18.04.2008 14:40

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » wohlgeformte formeln