Vollständiges Junktorensystem

25.08.2014, 11:49	Sabrina11111	Auf diesen Beitrag antworten »
Vollständiges Junktorensystem Meine Frage: Laut Definition ist ein Junktorensystem vollständig, wenn man die Formel mit $\begin{eqnarray} \neg \end{eqnarray}$ und $\begin{eqnarray} \wedge \end{eqnarray}$ ODER mit $\begin{eqnarray} \neg \end{eqnarray}$ und $\begin{eqnarray} \vee \end{eqnarray}$ darstellbar ist. Meine Ideen: Ich dachte jetzt: Gut dann muss man eine Formel eben so umformen, dass sie nur mit diesen dargestellt wird. ABER wieso ist dann [ $\begin{eqnarray} \vee,\wedge \end{eqnarray}$ ] kein vollständiges Junktorensystem? Einfaches Beispiel: $\begin{eqnarray} (a\vee b)\wedge(c\vee d) \end{eqnarray}$ Das ist ja laut "Lösung" kein vollständiges Junktorensystem. Man kann es aber so umformen zu der äquivalenten Formel: $\begin{eqnarray} (\neg (\neg(a\vee b)\vee\neg(c\vee d)) \end{eqnarray}$ Dann bestünde es doch nur aus $\begin{eqnarray} \neg \end{eqnarray}$ und $\begin{eqnarray} \vee \end{eqnarray}$ was der Definition entspräche.. Orde wo liegt mein Denkfehler? Leider findet sich keine brauchbare Literatur, die es mir verständlich erklärt..
27.08.2014, 18:03	Stephan Kulla	Auf diesen Beitrag antworten »
Zum Beispiel kannst du $\begin{eqnarray} \neg A \end{eqnarray}$ nicht durch eine Aussage ausdrücken, die nur die Junktoren $\begin{eqnarray} \land \end{eqnarray}$ und $\begin{eqnarray} \lor \end{eqnarray}$ enthalten (Grund: $\begin{eqnarray} A \lor A \Leftrightarrow A \end{eqnarray}$ und $\begin{eqnarray} A \land A \Leftrightarrow A \end{eqnarray}$ und damit ist jede Aussage bestehend aus $\begin{eqnarray} A \end{eqnarray}$ , $\begin{eqnarray} \land \end{eqnarray}$ und $\begin{eqnarray} \lor \end{eqnarray}$ äquivalent zu $\begin{eqnarray} A \end{eqnarray}$ ).
27.08.2014, 19:10	Sabrina12432	Auf diesen Beitrag antworten »
Hm, ok ja das macht Sinn... Aber so ganz einleuchten will es mir noch nicht, worauf ich achten muss, denn äquivalente Formen können ja [latex]\neg[\latex] und [latex]\vee[\latex] oder [latex]\wedge[\latex] enthalten. Gibts da ein Vorgehen, dass man beachten sollte? Oder ist das Wahl der Mittel einfaches Nachdenken?
27.08.2014, 22:53	Stephan Kulla	Auf diesen Beitrag antworten »
Ein vollständiges Junktorensystem sollte eine Menge von Junktoren sein, so dass sich jede Aussage nur mit Hilfe dieser Junktoren formulieren lässt. Nun ist $\begin{eqnarray} \land \end{eqnarray}$ und $\begin{eqnarray} \neg \end{eqnarray}$ ein vollständiges Junktorensystem. Wenn man also ein Junktorensystem gegeben hat und $\begin{eqnarray} \land \end{eqnarray}$ und $\begin{eqnarray} \neg \end{eqnarray}$ mit diesen Junktoren ausdrücken kann, dann kann man auch jede Aussage mit diesen Junktoren ausdrücken (eben weil jede Aussage mit $\begin{eqnarray} \land \end{eqnarray}$ und $\begin{eqnarray} \neg \end{eqnarray}$ ausdrückbar ist). Um zu zeigen, dass etwas kein vollständiges Junktorensystem ist, musst du zeigen, dass es Junktoren gibt, die nicht mit den gegebenen Junktoren ausdrückbar sind. Hier reicht es nur die Junktoren $\begin{eqnarray} \land \end{eqnarray}$ und $\begin{eqnarray} \neg \end{eqnarray}$ zu überprüfen.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »