Prädikatenlogik, Tautologie

26.06.2022, 15:08	Halfdan	Auf diesen Beitrag antworten »
Prädikatenlogik, Tautologie Hallo, ich bin mir nicht sicher ob dies der richtige Bereich ist. Also bitte verschieben falls nicht. Ich soll zeigen das F eine Tautologie ist $\begin{eqnarray} F = \lnot [ \forall_x: ( \lnot S(r(x)) \rightarrow \lnot L(x)) \land \lnot \exists_x: (S(x) \land S(r(x)))] \lor \lnot \exists_x: (S(x) \land L(x)) \end{eqnarray}$ meine erste Überlegung war daraus eine Implikation zu machen, also: $\begin{eqnarray} \equiv [ \forall_x: ( \lnot S(r(x)) \rightarrow \lnot L(x)) \land \lnot \exists_x: (S(x) \land S(r(x)))] \rightarrow \lnot \exists_x: (S(x) \land L(x)) \end{eqnarray}$ Dann habe ich die beiden Existensquantoren beseitigt in dem ich das nicht hinter sie gezogen habe. $\begin{eqnarray} \equiv [ \forall_x: ( \lnot S(r(x)) \rightarrow \lnot L(x)) \land \forall_x: \lnot(S(x) \land S(r(x)))] \rightarrow \forall_x: \lnot (S(x) \land L(x)) \end{eqnarray}$ Dann das nicht, jeweils in die Klammer, deMorgan angewandt. $\begin{eqnarray} \equiv [ \forall_x: ( \lnot S(r(x)) \rightarrow \lnot L(x)) \land \forall_x: ( \lnot S(x) \lor \lnot S(r(x)))] \rightarrow \forall_x: (\lnot S(x) \lor \lnot L(x)) \end{eqnarray}$ Dann die oder zu einer Implikation $\begin{eqnarray} \equiv [ \forall_x: ( \lnot S(r(x)) \rightarrow \lnot L(x)) \land \forall_x: (S(x) \rightarrow \lnot S(r(x)))] \rightarrow \forall_x: (S(x) \rightarrow \lnot L(x)) \end{eqnarray}$ Dann stehe ich an. Ich denke ich müsste vor der "großen" Implikation, also die Prämisse des Hauptoperators das und irgendwie wegkriegen, weiß aber nicht wie ich mit dem zweiten Allquantor verfahren muss. Wenn ich ihn nach vorne ziehen will, muss ich die Variablen umbenennen, richtig? (Was dann irgendwie mein "Ziel" untermauert.
26.06.2022, 23:59	Finn_	Auf diesen Beitrag antworten »
RE: Prädikatenlogik, Tautologie Ob man bloß mit Äquivalenzumformungen zum Ziel gelangt, sehe ich gerade nicht. Im Kalkül des natürlichen Schließens erhält man $\begin{eqnarray} [\forall_x\colon ( \lnot S(r(x)) \rightarrow \lnot L(x)) \land \forall_x\colon (S(x) \rightarrow \lnot S(r(x)))] \rightarrow \forall_x\colon (S(x) \rightarrow \lnot L(x)) \end{eqnarray}$ durch einen fast elementaren Kettenschluss: Angenommen, es gilt $\begin{eqnarray} S(u) \end{eqnarray}$ für ein beliebiges $\begin{eqnarray} u. \end{eqnarray}$ Infolge gilt $\begin{eqnarray} \neg S(r(u)) \end{eqnarray}$ gemäß der zweiten Prämisse. Infolge gilt $\begin{eqnarray} \neg L(u) \end{eqnarray}$ gemäß der ersten Prämisse. Die Implikationseinführung $\begin{eqnarray} S(u)\to\neg L(u) \end{eqnarray}$ beseitigt die Annahme. Weil $\begin{eqnarray} u \end{eqnarray}$ dabei beliebig ist, darf die Allquantifizierung $\begin{eqnarray} \forall x\colon (S(x)\to\neg L(x)) \end{eqnarray}$ eingeführt werden. Aus den Prämissen wurde die Konklusion abgeleitet, also darf man abschließende Implikationseinführung machen, um die Gesamtaussage zu erhalten.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »