Aussagenlogik

03.09.2012, 16:43

hollisch

Aussagenlogik

Meine Frage:
Guten Tag zusammen! Hier meine Frage:

Wieviele paarweise zueinander nicht logisch äquivalente Aussagen kann
man aus n Elementaraussagen zusammensetzen?

Meine Ideen:
Ich habe in einer vorangegangenen Aufgabe bereits folgendes überlegt:

Wieviele Zeilen hat die Wahrheitstafel einer aus n Elementaraussagen zu-
sammengesetzten Aussage?
Da eine Aussage aufgrund des Prinzips der Zweiwertigkeit die Werte wahr und falsch annehmen kann und ich die Zusammengesetzte Aussage aus n Aussagen bild, gleicht dies dem Anordnen von Objekten mit Zurücklegen und beachtung der Reihenfolge. Folglich hat diese gesuchte Wahrheitstafel $\begin{eqnarray*} 2^n \end{eqnarray*}$ Zeilen.

Dann habe ich versucht herauszufinden, wie viele paarweise zusammengesetzte Aussage - bestehend aus den Elementaraussagen $\begin{eqnarray*} A_i, A_j\text{ mit }i,j=1,\ldots,n\text{ und }i\neq j \end{eqnarray*}$ - Tautologien sind.

Ich komm nicht auf die Lösung Big Laugh

Ich hab lediglich herausgefunden, dass die Aussage $\begin{eqnarray*} A_i\iff A_j\ \ \ \ \frac{1}{2}\binom{n}{2}=\frac{n(n-1)}{4} \end{eqnarray*}$ mal wahr ist. Warum ich das überhaupt gemacht habe? Ich dachte mir, wenn eine Aussage logisch äquivalent ist - also $\begin{eqnarray*} A\equiv B \end{eqnarray*}$ , dann ist $\begin{eqnarray*} A\iff B \end{eqnarray*}$ eine Tautologie. Die Anzahl der Tautologien wollte ich dann von $\begin{eqnarray*} 2^n \end{eqnarray*}$ subtrahieren.

Habt ihr vielleicht Ideen?

03.09.2012, 19:50

Huggy

Auf diesen Beitrag antworten »

RE: Aussagenlogik

Zitat:

Original von hollisch
Wieviele Zeilen hat die Wahrheitstafel einer aus n Elementaraussagen zu-
sammengesetzten Aussage?
Da eine Aussage aufgrund des Prinzips der Zweiwertigkeit die Werte wahr und falsch annehmen kann und ich die Zusammengesetzte Aussage aus n Aussagen bild, gleicht dies dem Anordnen von Objekten mit Zurücklegen und beachtung der Reihenfolge. Folglich hat diese gesuchte Wahrheitstafel $\begin{eqnarray*} 2^n \end{eqnarray*}$ Zeilen.

Das ist der richtige Anfang.
Jetzt musst du nur noch überlegen, wieviele verschiedene Wahrheitstafeln mit $\begin{eqnarray*} 2^n \end{eqnarray*}$ Zeilen man bilden kann. Sind die Wahrheitstafeln zweier aus n Elementaraussagen gebildeten verknüpften Aussage nicht identisch, so sind die verknüpften Aussagen auch nicht logisch äquivalent.
Überprüfe dein Ergebnis an den Fällen n = 1 und n = 2. Da solltest du die Antwort schon kennen.

03.09.2012, 21:18

hollisch

Auf diesen Beitrag antworten »

na so schnell bin ich leider noch nicht^^

es stellt sich mir leider noch die Frage, ob die Wahrheitstafeln, die ich zu bilden habe auch Aussagen doppelt beinhalten dürfen, sprich

$\begin{eqnarray*} \begin{tabular}{|c|c|}\hline $A$ & $A$ \\ \hline 1 & 1\\ \hline 0 & 0 \\ \hline \end{tabular} \end{eqnarray*}$

Wie sieht es mit doppelten Negationen aus?
Z.B. sei A eine zweiwertige Aussage, so sind $\begin{eqnarray*} A \iff A, \neg \neg A \iff A, A \vee \neg A, \neg (\neg A \wedge A) \end{eqnarray*}$ Tautologien

03.09.2012, 21:25

hollisch

Auf diesen Beitrag antworten »

was genau ist eigentlich mit

"Wieviele paarweise zueinander nicht logisch äquivalente Aussagen kann
man aus n Elementaraussagen zusammensetzen?"

gemeint? So ganz versteh ich nämlich die Frage nicht^^. Soll ich die verknüpfen durch Konjunktion, Antivalenz etc. (lese ich am Wort "zusammensetzen")
Gilt paarweise auch für $\begin{eqnarray*} i=j \end{eqnarray*}$ ?

03.09.2012, 21:45

Huggy

Auf diesen Beitrag antworten »

Bei den n Elementaraussagen sind n verschiedene Aussagen gemeint, denke ich. Wenn darunter gleiche Aussagen wären, wären die möglichen Verknüpfungen schon in den Verknüpfungen für weniger als n Elementaraussagen enthalten.

Bei z. B. n =1 mit A als Elementaraussage sind die Wahrheitstafeln für $\begin{eqnarray*} f(A)=A \end{eqnarray*}$ und $\begin{eqnarray*} f(A)=\neg\neg A \end{eqnarray*}$ identisch. Wenn du also nur die verschiedenen Wahrheitstafeln zählst, gibt es darunter keine äquivalenten Verknüpfungen. Schreib halt mal alle Wahrheitstafeln für n =1 auf. Dann blickst du leichter durch.

Paarweise gilt natürlich nicht für i = j, denn jede Verknüpfung ist zu sich selbst äquivalent.

03.09.2012, 21:58

hollisch

Auf diesen Beitrag antworten »

Dann sag ich jetzt mal spontan "NULL" Big Laugh

Wenn das richtig ist, fress ich n Besen^^ das war nämlich meine erste Intuition...

03.09.2012, 22:11

Huggy

Auf diesen Beitrag antworten »

Das ist doch albern!. Mit $\begin{eqnarray*} \neg A \end{eqnarray*}$ hast du doch schon eine einstellige Verknüpfung benutzt. Das ist auch die einzige interessante einstellige Verknüpfung. Aber es gibt insgesamt 4 Stück:

A |1 2 3 4
W|WW F F
F |W FW F

Ich war zu faul, eine Latextabelle zu machen.
1 ist die wahre Aussage.
2 liefert A unverändert zurück.
3 ist die schon erwähnte Negation.
4 ist die falsche Aussage.

Bei n = 2 gibt es 16 verschiedene Wahrheitstafeln.

03.09.2012, 22:19

hollisch

Auf diesen Beitrag antworten »

Okay... sorry^^ das war wirklich albern Big Laugh

in meinem Skript steht leider nichts zu einstelligen Verknüpfungen -.- Da ist lediglich die Negation, bei der ich schon sehen konnte, dass dort lediglich die Aussage selbst benutzt wird.

Gut... wenn es also diese 4 einstelligen Verknüpfungen gibt, kenne ich noch die Implikation, die Konjunktion, Disjunktion, Antivalenz und Äquivalenz. Die funktionieren jetzt nur wenn ich zwei verschiedene Aussagen A und B verwende... oder soll ich es lieber aufgeben und mir das morgen in der Übung erklären lassen?

Ich will dich nicht länger quälen :P

03.09.2012, 22:25

Huggy

Auf diesen Beitrag antworten »

Ich bin eh gleich für heute weg.

Nicht jede 2-stellige Verknüpfung hat einen Namen oder ein Symbol. Wenn du also alle suchst, solltest du die Tafeln systematisch erzeugen, wie ich es bei n = 1 gemacht habe. Die Anzahl zu berechnen, ist dann ein rein kombinatorisches und sehr simples Problem.

03.09.2012, 22:31

hollisch

Auf diesen Beitrag antworten »

Okay, danke trotzdem smile

04.09.2012, 22:00

hollisch

Auf diesen Beitrag antworten »

ich hab die Lösung^^

Wenn ich eine aus $\begin{eqnarray*} n \end{eqnarray*}$ Elementaraussagen zusammengesetzte Aussage $\begin{eqnarray*} 2^n \end{eqnarray*}$ Zeilen hat, kann ich diese $\begin{eqnarray*} \left( 2^n\right)^{\left(2^n\right)} \end{eqnarray*}$ mal anordnen. Und das ist die Lösung.

05.09.2012, 08:11

Huggy

Auf diesen Beitrag antworten »

Da habe ich eine gute und eine schlechte Nachricht für dich.
Die gute Nachricht: Für n = 1 stimmt das Ergebnis.
Die schlechte Nachricht: Für n =2 und alle größeren n ist das falsch.

Ich will ganz offen sein. Da ich dir schon sagte, dass es bei n = 2 16 Möglichkeiten gibt, sehe ich es als Zeichen extremer geistiger Faulheit, dass du deine Formel nicht mal für n = 2 überprüft hast.

Neuer Versuch?

06.09.2012, 17:58

hollisch

Auf diesen Beitrag antworten »

Es hat bei mir "klick" gemacht^^...

Lösung ist $\begin{eqnarray*} 2^{2^n} \end{eqnarray*}$

Aber die Begründung ist die Gleiche.

Hab's auch heute nochmal in meiner Übung erfragt und die Übungsleiterin meinte es sei richtig smile

$\begin{eqnarray*} n=2 \implies 2^{4}=16 \end{eqnarray*}$

06.09.2012, 18:46

Huggy

Auf diesen Beitrag antworten »

Jetzt ist es richtig!

Neue Frage »

Antworten »

Aussagenlogik

Verwandte Themen