Wahrheitstabelle aufstellen

20.06.2021, 19:32

Little Princess

Auf diesen Beitrag antworten »

Wahrheitstabelle aufstellen

Hallo Zusammen,

ich soll eine Aussage der unten angegebenen Form mit Wahrheitstabelle verifizieren und komme leider nicht weiter. Mir ist nicht ganz klar wie ich das U hier verwerten muss. Hoffe mir kann jemand einen Tipp geben.

[attach]53208[/attach]

Ansatz:
[attach]53209[/attach]

Bin mir aber nicht wirklich sicher.

Hoffe jemand kann hier weiterhelfen.
Viele Dank

20.06.2021, 21:59

Finn_

Auf diesen Beitrag antworten »

Die Relation $\begin{eqnarray*} M\models\varphi \end{eqnarray*}$ ist definiert als

$\begin{eqnarray*} \forall I((I\models M)\implies (I\models\varphi)). \end{eqnarray*}$

Und $\begin{eqnarray*} I\models M \end{eqnarray*}$ ist definiert als $\begin{eqnarray*} \forall m\in M\colon (I\models m). \end{eqnarray*}$ Du kannst nachrechnen dass $\begin{eqnarray*} I\models (M\cup N) \end{eqnarray*}$ äquivalent zu $\begin{eqnarray*} (I\models M)\land (I\models N) \end{eqnarray*}$ ist. Wir haben somit:

1. $\begin{eqnarray*} \Phi\cup\{\psi\}\models\varphi \end{eqnarray*}$ ist äquivalent zu $\begin{eqnarray*} \forall I((I\models\Phi)\land(I\models\psi)\implies (I\models\varphi)), \end{eqnarray*}$

2. $\begin{eqnarray*} \Phi\cup\{\neg\psi\}\models\varphi \end{eqnarray*}$ ist äquivalent zu $\begin{eqnarray*} \forall I((I\models\Phi)\land(I\models\neg\psi)\implies (I\models\varphi)), \end{eqnarray*}$

3. $\begin{eqnarray*} \Phi\models\varphi \end{eqnarray*}$ ist äquivalent zu $\begin{eqnarray*} \forall I((I\models\Phi)\implies (I\models\varphi)). \end{eqnarray*}$

Wir grasen nun unendlich viele Interpretationen gleichzeitig ab, indem wir eine beliebige Interpretation $\begin{eqnarray*} I \end{eqnarray*}$ betrachten, für die $\begin{eqnarray*} I\models\varphi \end{eqnarray*}$ und $\begin{eqnarray*} I\models\psi \end{eqnarray*}$ jeweils einen festen Wahrheitswert haben. Wird beiden wahr zugeordnet, ist

1. $\begin{eqnarray*} \forall I((I\models\Phi)\land 1\implies 1) \end{eqnarray*}$ , das vereinfacht sich zu wahr,

2. vereinfacht sich auch zu wahr,

3. vereinfacht sich auch zu wahr.

Demzufolge ist "1. und 2. impliziert 3." wahr. Dies verbleibt für die restlichen drei Möglichkeiten zu prüfen, wie $\begin{eqnarray*} I\models\varphi \end{eqnarray*}$ und $\begin{eqnarray*} I\models\psi \end{eqnarray*}$ ein Wahrheitswert zugeordnet werden kann.

20.06.2021, 23:12

Finn_

Auf diesen Beitrag antworten »

Ich hab jetzt nochmal drüber nachgedacht. Die Allquantifizierung muss immer über alle Interpretationen laufen. Eine Aufteilung würde nur dann gehen, wenn die Allquantifizierung die gesamte Aussage umfasst. Da sind aber drei Allquantifizierungen innerhalb der Aussage.

Die Rechnung verbleibt dennoch richtig. Die Überlegung dabei ist allerdings die Betrachtung beliebiger Formeln $\begin{eqnarray*} \varphi,\psi \end{eqnarray*}$ , für die $\begin{eqnarray*} I\models\varphi \end{eqnarray*}$ und $\begin{eqnarray*} I\models\psi \end{eqnarray*}$ jeweils einen festen Wahrheitswert haben.

21.06.2021, 00:28

Finn_

Auf diesen Beitrag antworten »

Wenn ich so drüber nachdenke, fällt mir wieder ein Denkfehler meinerseits auf, sorry. Wenn die Formeln einen festen Wahrheitswert haben sollen, würde man sich automatisch auf solche beschränken, die entweder tautologisch oder kontradiktorisch sind. Die Aussage wäre somit lediglich für ganz spezielle Formeln gezeigt.

Stures Durchrechnen ginge wie folgt.

Sei $\begin{eqnarray*} P:=(I\models\Phi) \end{eqnarray*}$ , $\begin{eqnarray*} Q:=(I\models\psi) \end{eqnarray*}$ , $\begin{eqnarray*} R:=(I\models\varphi) \end{eqnarray*}$ . Die zu beweisende Aussage nimmt damit die Form

$\begin{eqnarray*} \forall I(P\wedge Q\implies R)\land\forall I(P\wedge\neg Q\implies R)\implies \forall I(P\implies Q) \end{eqnarray*}$

an. Man darf rechnen

$\begin{eqnarray*} \forall I(P\wedge Q\implies R)\land\forall I(P\wedge\neg Q\implies R) \end{eqnarray*}$
$\begin{eqnarray*} \equiv \forall I((P\wedge Q\implies R)\land (P\wedge\neg Q\implies R)). \end{eqnarray*}$

Nun rechnent man

$\begin{eqnarray*} (P\wedge Q\implies R)\land (P\wedge\neg Q\implies R) \end{eqnarray*}$
$\begin{eqnarray*} \equiv (\neg P\lor \neg Q\lor R)\land (\neg P\lor Q\lor R) \end{eqnarray*}$
$\begin{eqnarray*} \equiv (\neg P\lor R)\lor (\neg Q\land Q) \end{eqnarray*}$
$\begin{eqnarray*} \equiv (\neg P\lor R)\equiv (P\implies R). \end{eqnarray*}$

q. e. d.

Die letzte Rechnung ginge auch mit Wahrheitstabelle. Zuvor habe ich aber eine Regel der Prädikatenlogik bemüht.

21.06.2021, 01:30

Little Princess

Auf diesen Beitrag antworten »

Vielen Dank. Finde die Erklärung wirklich super. Die zu beweisende Aussage (zweite Formel, letzte Antwort) müsste aber am Schluss $\begin{eqnarray*} \forall I ( P \rightarrow R) \end{eqnarray*}$ heissen oder ?

Ist der Ansatz folgender Wahrheitstabelle hier korrekt ?
[attach]53210[/attach]

21.06.2021, 10:47

Finn_

Auf diesen Beitrag antworten »

Ja, aus

$\begin{eqnarray*} \forall I((P\land Q\implies R)\land (P\land\neg Q\implies R)) \end{eqnarray*}$

und

$\begin{eqnarray*} ((P\land Q\implies R)\land (P\land\neg Q\implies R)) \equiv (P\implies R) \end{eqnarray*}$

folgt laut der Ersetzungsregel schließlich die Aussage

$\begin{eqnarray*} \forall I(P\implies R). \end{eqnarray*}$

Die Tabelle ist bis auf die Überschriften $\begin{eqnarray*} \Phi,\varphi \end{eqnarray*}$ richtig. Die Überschrift » $\begin{eqnarray*} \Phi\implies\varphi \end{eqnarray*}$ « ergibt per se keinen Sinn, denn $\begin{eqnarray*} \Phi \end{eqnarray*}$ ist eine Menge.

Alternativer Beweis

Alternativ könnte man auch wie folgt vorgehen. Zunächst überzeugt man sich mit einer Wahrheitstabelle von

$\begin{eqnarray*} \models (B\to A)\land (\neg B\to A)\to A. \end{eqnarray*}$

Gemäß der Einsetzungsregel gilt daher mit der simultanen Einsetzung $\begin{eqnarray*} A:=\varphi \end{eqnarray*}$ und $\begin{eqnarray*} B:=\psi \end{eqnarray*}$ auch

$\begin{eqnarray*} \models (\psi\to\varphi)\land (\neg\psi\to\varphi)\to\varphi \end{eqnarray*}$

für beliebige Formeln $\begin{eqnarray*} \varphi,\psi \end{eqnarray*}$ . Man darf das Deduktionstheorem der Aussagenlogik auch rückwärts anwenden und erhält

$\begin{eqnarray*} \{\psi\to\varphi,\neg\psi\to\varphi\}\models\varphi. \end{eqnarray*}$

Laut Deduktionstheorem zieht außerdem die erste Prämisse $\begin{eqnarray*} \Phi\cup\{\psi\}\models\varphi \end{eqnarray*}$ die Aussage $\begin{eqnarray*} \Phi\models\psi\to\varphi \end{eqnarray*}$ nach sich, und die zweite Prämisse $\begin{eqnarray*} \Phi\cup\{\neg\psi\}\models\varphi \end{eqnarray*}$ entsprechend $\begin{eqnarray*} \Phi\models\neg\psi\to\varphi \end{eqnarray*}$ .

Nun bemühen wir die folgende allgemeine Regel:
Aus $\begin{eqnarray*} M\models\varphi_1 \end{eqnarray*}$ und $\begin{eqnarray*} M\models\varphi_2 \end{eqnarray*}$ und $\begin{eqnarray*} \{\varphi_1,\varphi_2\}\models\psi \end{eqnarray*}$ folgt $\begin{eqnarray*} M\models\psi \end{eqnarray*}$ .

Demzufolge gilt $\begin{eqnarray*} \Phi\models\varphi \end{eqnarray*}$ . q. e. d.

Anzeige

23.06.2021, 07:11

Pippen

Auf diesen Beitrag antworten »

Zitat:

Original von Finn_ Du kannst nachrechnen dass $\begin{eqnarray*} I\models (M\cup N) \end{eqnarray*}$ äquivalent zu $\begin{eqnarray*} (I\models M)\land (I\models N) \end{eqnarray*}$ ist.

Ist das nicht falsch? Da würde mich mal der Äquivalenzbeweis interessieren, auch weil ich mal sehen will, wie man die Mengenvereinigung in die PL zurückübersetzt.

23.06.2021, 10:34

zweiundvierzig

Auf diesen Beitrag antworten »

Für die Intuition kann man sich erstmal den Fall anschauen, in dem $\begin{eqnarray*} M \end{eqnarray*}$ und $\begin{eqnarray*} N \end{eqnarray*}$ einelementig sind.

Edit: Übrigens handelt es sich hier um Aussagen in der Meta-Sprache.

23.06.2021, 15:19

Finn_

Auf diesen Beitrag antworten »

Dann will ich sogleich die allgemeinere Aussage

$\begin{eqnarray*} (\forall x\in M\cup N\colon P(x)) \iff (\forall x\in M\colon P(x))\land (\forall x\in N\colon P(x)) \end{eqnarray*}$

zeigen. Zur Übersicht zunächst ein High-Level-Beweis. Wir betrachten das Prädikat $\begin{eqnarray*} P \end{eqnarray*}$ als Abbildung $\begin{eqnarray*} P\colon U\to\{0,1\} \end{eqnarray*}$ . Nun gilt

$\begin{eqnarray*} (\forall x\in A\colon P(x))\iff P(A)\subseteq\{1\}. \end{eqnarray*}$

Wie bei jeder Abbildung gilt

$\begin{eqnarray*} P(M\cup N) = P(M)\cup P(N). \end{eqnarray*}$

Die Aussage nimmt demzufolge die Form

$\begin{eqnarray*} P(M)\cup P(N)\subseteq\{1\} \iff P(M)\subseteq\{1\}\land P(N)\subseteq\{1\} \end{eqnarray*}$

an. Die Implikation von rechts nach links ist trivial. Betrachten wir die Implikation von links nach rechts. Wäre 0 in $\begin{eqnarray*} P(M) \end{eqnarray*}$ oder in $\begin{eqnarray*} P(N) \end{eqnarray*}$ enthalten, wäre es auch in $\begin{eqnarray*} P(M)\cup P(N) \end{eqnarray*}$ enthalten. q. e. d.

23.06.2021, 16:38

Finn_

Auf diesen Beitrag antworten »

KdnS-Beweis

Satz. $\begin{eqnarray*} \forall x(x\in M\cup N\to P_x)\vdash \forall x(x\in M\to P_x)\land \forall x(x\in N\to P_x). \end{eqnarray*}$

Beweis.
1. $\begin{eqnarray*} x\in M\cup N\to P_x\quad \end{eqnarray*}$ (Prämisse)
2. $\begin{eqnarray*} x\in M\quad \end{eqnarray*}$ (Annahme)
3. $\begin{eqnarray*} x\in M\cup N\quad \end{eqnarray*}$ (2.)
4. $\begin{eqnarray*} P_x\quad \end{eqnarray*}$ (MP, 1., 3.)
5. $\begin{eqnarray*} x\in M\to P_x\quad \end{eqnarray*}$ (4., tilgt 2.)
6. $\begin{eqnarray*} \forall x(x\in N\to P_x)\quad \end{eqnarray*}$ (5.)
Für $\begin{eqnarray*} N \end{eqnarray*}$ analog. q. e. d.

Satz. $\begin{eqnarray*} \forall x(x\in M\to P_x)\land \forall x(x\in N\to P_x)\vdash\forall x(x\in M\cup N\to P_x). \end{eqnarray*}$

Beweis.
1. $\begin{eqnarray*} x\in M\to P_x\quad \end{eqnarray*}$ (Prämisse)
2. $\begin{eqnarray*} x\in N\to P_x\quad \end{eqnarray*}$ (Prämisse)
3. $\begin{eqnarray*} x\in M\cup N\quad \end{eqnarray*}$ (Annahme)
4. $\begin{eqnarray*} x\in M\lor x\in N\quad \end{eqnarray*}$ (3.)
Fallunterscheidung
5. $\begin{eqnarray*} x\in M\quad \end{eqnarray*}$ (Annahme)
6. $\begin{eqnarray*} P_x\quad \end{eqnarray*}$ (MP, 1., 5.)
7. $\begin{eqnarray*} x\in N\quad \end{eqnarray*}$ (Annahme)
8. $\begin{eqnarray*} P_x\quad \end{eqnarray*}$ (MP, 2., 7.)
Ende der Fallunterscheidung
9. $\begin{eqnarray*} P_x\quad \end{eqnarray*}$ (4., 6., 8., tilgt 5. und 7.)
10. $\begin{eqnarray*} x\in M\cup N\to P_x\quad \end{eqnarray*}$ (9., tilgt 3.)
11. $\begin{eqnarray*} \forall x(x\in M\cup N\to P_x)\quad \end{eqnarray*}$ (10.)
q. e. d.

23.06.2021, 17:00

Finn_

Auf diesen Beitrag antworten »

Beweis mittels boolescher Algebra

Zunächst dürfen wir umformen

$\begin{eqnarray*} \forall x(x\in M\to P_x)\land \forall x(x\in N\to P_x) \equiv \forall x((x\in M\to P_x)\land (x\in N\to P_x)). \end{eqnarray*}$

Nun müssen wir die quantifizierte Formel noch umrechnen. Das geschieht so:

$\begin{eqnarray*} (x\in M\to P_x)\land (x\in N\to P_x) \equiv (x\notin M\lor P_x)\land (x\notin N\lor P_x) \end{eqnarray*}$

$\begin{eqnarray*} \equiv (x\notin M\land x\notin N)\lor P_x\equiv \neg(x\in M\lor x\in N)\lor P_x \end{eqnarray*}$

$\begin{eqnarray*} \equiv \neg(x\in M\cup N)\lor P_x\equiv (x\in M\cup N\to P_x). \end{eqnarray*}$

q. e. d.

23.06.2021, 18:17

Finn_

Auf diesen Beitrag antworten »

Mir ist unterdessen in den Sinn gekommen, dass es mit

$\begin{eqnarray*} (\forall x\in A\colon P(x)) \iff \neg0\in P(A) \end{eqnarray*}$

sogar noch klarer geht. Man braucht dann lediglich einmal De Morgan anwenden:

$\begin{eqnarray*} \neg 0\in P(M)\cup P(N) \equiv \neg(0\in P(M)\lor 0\in P(N)) \equiv \neg 0\in P(M)\land\neg 0\in P(N). \end{eqnarray*}$

23.06.2021, 18:40

Finn_

Auf diesen Beitrag antworten »

Nett ist auch

$\begin{eqnarray*} (\forall x\in A\colon P(x)) \iff P(A)\cap\{0\}=\emptyset. \end{eqnarray*}$

Dann hat man nämlich den Einzeiler

$\begin{eqnarray*} \emptyset = P(M\cup N)\cap\{0\} = (P(M)\cup P(N))\cap\{0\} = P(M)\cap\{0\}\cup P(N)\cap\{0\}. \end{eqnarray*}$

Und soviel ist klar: Die Vereinigung zweier Mengen ist genau dann leer, wenn beide Mengen leer sind.

24.06.2021, 22:46

Pippen

Auf diesen Beitrag antworten »

Little Princess, hat du mittlerweile die Lösung? Irgendwie ist es nämlich komisch, dass du den Beweis per Wahrheitswerttabelle machen solltest, weil die ja nur für AL-Formeln anwendbar ist. Was du hast ist aber keine AL-Formel und läßt sich mE auch nicht rückübersetzen, weil's in deiner Formel um Aussagemengen geht.

Kennt jmd. irgendwo einen guten Link, wo die semantische Folgerungsrelation |= so richtig präzise definiert und erläutert wird?

24.06.2021, 22:53

zweiundvierzig

Auf diesen Beitrag antworten »

Die Meta-Logik ist klassische zweiwertige Logik.

Edit: Zu Pippens Frage: Z.B. Ebbinghaus et al. "Math. Log." (de/en) oder jedes andere Buch oder Skript über Logik erster Stufe.

24.06.2021, 23:34

Pippen

Auf diesen Beitrag antworten »

Ich finde aber, man kann littleprincess‘ Schluss nicht per Wahrheitswerttabelle beweisen. Denn damit hätte die princess nur bewiesen, dass die aussagenlogische Form ihres Schlusses wahr und damit der Schluss gültig ist, nicht aber die prädikatenlogische Form und darum geht’s doch hier, oder?

25.06.2021, 00:57

zweiundvierzig

Auf diesen Beitrag antworten »

Für $\begin{eqnarray*} \mathfrak I \end{eqnarray*}$ mit $\begin{eqnarray*} \mathfrak I \models \Phi \end{eqnarray*}$ muss man eine Fallunterscheidung machen, ob $\begin{eqnarray*} \mathfrak I \models \psi \end{eqnarray*}$ gilt, oder nicht. Es trifft zu, dass man wie üblich die Fälle mit falscher Prämisse weglassen kann.

28.06.2021, 04:03

Pippen

Auf diesen Beitrag antworten »

Zitat:

Original von Finn_
Die Relation $\begin{eqnarray*} M\models\varphi \end{eqnarray*}$ ist definiert als

$\begin{eqnarray*} \forall I((I\models M)\implies (I\models\varphi)). \end{eqnarray*}$

Und $\begin{eqnarray*} I\models M \end{eqnarray*}$ ist definiert als $\begin{eqnarray*} \forall m\in M\colon (I\models m). \end{eqnarray*}$ .

Sehe ich das richtig, dass die Modellrelation so definiert ist, dass wenn alles vollständig ausdefiniert und hingeschrieben ist, wir nur noch Implikationen da stehen haben?

28.06.2021, 13:21

Finn_

Auf diesen Beitrag antworten »

Für aussagenlogische Formeln steht da lediglich folgendes: Die Menge $\begin{eqnarray*} M \end{eqnarray*}$ impliziert $\begin{eqnarray*} \varphi \end{eqnarray*}$ genau dann semantisch, wenn in jeder Zeile der Wahrheitstabelle, in der alle Formeln aus $\begin{eqnarray*} M \end{eqnarray*}$ erfüllt sind, auch $\begin{eqnarray*} \varphi \end{eqnarray*}$ erfüllt ist.

Für prädikatenlogische Formeln bleibt die Definition gültig, wobei die »Wahrheitstabelle« aber eine kompliziertere Form annimmt. Sie wird dann meistens unendlich groß, weil man für jede Funktion, jede Relation und jedes Element des Individuenbereichs eine »Zeile« braucht, sofern das jeweilige Symbol in der Formel auftritt. Zudem sind nicht mehr alle Quantifizierungen, Funktionen und Relationen mit endlichen Mitteln auswertbar. Solange man sich auf kleine endliche Individuenbereiche beschränkt, bleibt die Wahrheitstabelle endlich, wobei man allerdings einen Computer heranziehen sollte.

Die Definition sollte auch für die intuitionistische Logik gültig bleiben, wobei die Wahrheitswerte allerdings einer passenden Heyting-Algebra entstammen müssen, siehe Intuitionistic logic#Semantics in Wikipedia.

28.06.2021, 13:34

Pippen

Auf diesen Beitrag antworten »

Das bedeuter aber, dass das Zeichen |= letztlich immer als Implikation definiert ist.

Bsp.: M |= p <=> für_alle I(I |= M -> I |= p) <=> für_alle I((I -> M) -> (I -> p)).

So etwa müsste die Definitionskette aussehen, nicht?

p.s. Sorry, hab grad wenig Zeit, daher kein latex.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »