TU Wien:Mathematik 1 UE (diverse)/Übungen WS07/Beispiel 81

SS08 Beispiel 13

Man zeige, dass es sich bei dem logischen Ausdruck

$[(B\lor C)\land (B\rightarrow \lnot A)\land A]\rightarrow C$

um eine Tautologie bzw. bei dem Ausdruck

$(A\rightarrow C)\land (C\rightarrow B)\land A\land \lnot B$

um eine Kontradiktion handelt.

Hilfreiches

Logische Negation

Logische Negation

${\begin{array}{c|c}x&{\overline {x}}\\\hline 0&1\\1&0\end{array}}$

Logische Disjunktion

Logische Disjunktion

Auch Oder-Verknüpfung.

${\begin{array}{cc|c}x&y&x\vee y\\\hline 0&0&0\\0&1&1\\1&0&1\\1&1&1\end{array}}$

Logische Konjunktion

Logische Konjunktion

Auch Und-Verknüpfung. ${\begin{array}{cc|c}x&y&x\wedge y\\\hline 0&0&0\\0&1&0\\1&0&0\\1&1&1\end{array}}$ Vorlage:Implikation Vorlage:Tautologie Vorlage:Kontradiktion

Lösungsvorschlag von Soymilk-Drinker

Teil 1, Tautologie

$[(B\lor C)\land (B\rightarrow \lnot A)\land A)]\rightarrow C$

Bei einer Tautologie ist das Ergebnis immer wahr, unabhängig davon wie die Variablen belegt sind.

Um zu beweisen dass es sich um eine Tautologie handelt wird der indirekte Beweis verwendet, es wird also versucht zu beweisen dass es sich hierbei nicht um eine Tautologie handelt. Dazu muss nur eine einzige Variablenbelegung gefunden werden bei dem das Ergebnis falsch ist.

Schritt 1

Der Ausdruck sieht vereinfacht so aus: $...\rightarrow C$

Man sieht also dass es sich hierbei um eine Implikation handelt.

Per Definition ist eine Implikation immer wahr, falls der zweite Ausdruck wahr ist. (sieht die Implikation so aus $A\rightarrow B$, dann ist es immer wahr falls B wahr ist).

[ACHTUNG: Big Fat Warning von AxeStr: Per Definition ist A->B = -a v b (nicht a oder b), ist also immer dann wahr, wenn entweder a falsch ist (aus falschem kann alles gefolgert werden), oder b richtig (aus richtigem muss richtiges gefolgert werden).]

Da bewiesen werden soll dass der gesamte Ausdruck falsch sein kann muss also hier der zweite Ausdruck falsch sein. Der zweite Ausdruck besteht nur aus C, also muss C falsch sein.

Der erste Ausdruck ($[(B\lor C)\land (B\rightarrow \lnot A)\land A)]$) muss dann wahr sein, dann wäre das Ergebnis des gesamten Ausdrucks falsch und die Tautologie wiederlegt.

Schritt 2

Jetzt sehen wir uns der ersten Ausdruck an, dieser muss ja wahr werden. Vereinfacht sieht der Ausdruck so aus: $...\land ...\land ...$

Der Ausdruck besteht nur aus mit $\land$-Verknüpften Ausdrücken. Wenn dieser gesamte Ausdruck wahr sein muss so müssen alle einzelnen Ausdrücke auch wahr sein. Einer der Ausdrücke besteht lediglich aus A, deswegen können wir sagen dass A wahr sein muss.

Schritt 3

Es bleiben jetzt nur noch zwei unbestimmte Ausdrücke übrig ($(B\lor C)$ und $(B\rightarrow \lnot A)$) welche beide Wahr sein müssen damit der gesamte Ausdruck falsch werden kann. Die Werte von A und C wurden schon in den ersten beiden Schritten gefunden, also kann man sich einfach jetzt die verbliebene Variable B mit wahr bzw falsch belegen und nachsehen ob in einem der beiden Fälle beide Ausdrücke wahr werden.

Fall 1 (B ist wahr):

Ausdruck 1 ($(B\lor C)$) ergibt wahr

Ausdruck 2 ($(B\rightarrow \lnot A)$) ergibt falsch

Fall 2 (B ist falsch):

Ausdruck 1 ($(B\lor C)$) ergibt falsch

Ausdruck 2 ($(B\rightarrow \lnot A)$) ergibt wahr

Man sieht dass es in beiden Fällen nicht dazu kommt dass beide Ausdrücke wahr werden. Deshalb kann es im gesamten Ausdruck nicht sein dass der erste und der zweite Teil gleichzeitig wahr werden. Damit ist die Annahme wiederlegt dass es sich bei dem Ausdruck nicht um eine Tautologie handelt, daher muss der Ausdruck also eine Tautologie sein.

Teil 2, Kontradiktion

$(A\rightarrow C)\land (C\rightarrow B)\land A\land \lnot B$

Bei einer Kontradiktion ist das Ergebnis immer falsch, unabhängig davon wie die Variablen belegt sind.

Um zu beweisen dass es sich bei den Ausdruck um eine Kontradiktion handelt wird versucht das Gegenteil zu beweisen, also dass es keine ist. Dazu muss einfach nur eine Variablenbelegung gefunden werden bei der das Ergebnis des Ausdrucks wahr ist.

Schritt 1

Man sieht sehr schnell dass der Ausdruck nur aus und-Verknüpfungen von mehreren kleineren Ausdrücken besteht. Damit der gesamte Ausdruck also wahr werden kann muss jeder einzelne Ausdruck wahr werden.

Zwei der kleinen Ausdrücke sind sehr einfach ($A$ und $\lnot B$), daher kann man ablesen dass (damit der gesamte Ausdrück wahr wird) die Variable A wahr und die Variable B falsch sein muss.

Schritt 2

A und B sind nun bekannt, jetzt muss man sich also nur noch die verbliebenen beiden Ausdrücke ansehen und bestimmen ob es eine Belegung von C gibt bei der, der gesamte Ausdruck wahr wird.

$A\rightarrow C$: Da A wahr ist muss auch C wahr sein, sonst würde dieser Ausdruck ja falsch werden

$C\rightarrow B$: C ist wahr und B ist falsch, der gesamte Ausdruck daher falsch. Würde man C jetzt als falsch wählen, so wäre dieser Ausdruck zwar wahr, aber der vorherige wäre falsch.

Man sieht, es gibt keine Variablenbelegung bei der der gesamte Ausdruck wahr wird. Die Annahme es handle sich nicht um eine Kontradiktion ist damit wiederlegt, der Ausdruck ist eine Kontradiktion.

Lösungsvorschlag von mnemetz

Der Lösungsvorschlag von Soymilk-Drinker scheint mir sehr intuitiv zu sein und ich glaube, man kann diesem sehr gut folgen. Nichtsdestotrotz bin ich der Meinung, dass zu dieser Aufgabe zur schlüssigen Beweisführung eine Wahrheitstafel notwendig ist.

Teil 1 - Tautologie

$[(B\lor C)\land (B\rightarrow \lnot A)\land A)]\rightarrow C$

Tautologie

Definition: Ein Ausdruck, der für jede Belegung der Variablen wahr ist, heißt Tautologie (immer wahr ), z.B. $a\vee {\overline {a}}=1$ (${\overline {a}}$ ist der Komplement von a).

Beispiel-Aufgabe: Ist der Ausdruck ${\overline {a}}\vee b\vee a{\overline {b}}$ eine Tautologie?

Lösung: Die Wahrheitstafel muss für alle Fälle wahr ergeben!

$a$	$b$	\	${\overline {a}}$	${\overline {b}}$	$a{\overline {b}}$	\	$a\vee {\overline {b}}$	\	${\overline {a}}\vee b\vee a{\overline {b}}$
0	0	\	1	1	0	\	1	\	1
0	1	\	1	0	0	\	1	\	1
1	0	\	0	1	1	\	0	\	1
1	1	\	0	0	0	\	1	\	1

Somit handelt es sich um eine Tautologie.

Angabe "eindeutschen"

Die Angabe ist:

$[(B\lor C)\land (B\rightarrow \lnot A)\land A)]\rightarrow C$

Der "Weg" durch den Ausdruck ist durch die Klammern vorgegeben. Eingeklammerte Ausdrücke sind zuerst auszufühen.

Hilfreich scheint es mir, die Angabe einzudeutschen.

Also, beginnen wir:

1. Zuerst prüfen wir, welcher Wahrheitswert sich aus B oder C ergibt ...
2. und prüfen dann den Wahrheitswert, der sich aus der Implikation von B mit dem negierten A ergibt'.
3. Schließlich prüfen wir den Wahrheitswert der UND-Beziehung zwischen den ersten zwei gewonnenen Werten ...
4. und setzen diesen in eine UND-Beziehung mit A.
5. Schlußendlich stellen wir die Implikation A-C her.

Wahrheitstafel

Wie schon erwähnt muss, um die Tautologie nachzuweisen, für alle Wahrheitswerte von A,B,C nach den logischen Operationen ein Wahrheitswert Wahr als Ergebnis stehen.

A	B	C	\	$B\vee C$	\	$\lnot A$	$B\rightarrow \lnot A$	\	$(B\vee C)\wedge (B\rightarrow \lnot A)$	\	$(B\vee C)\wedge (B\rightarrow \lnot A)\wedge A$	\	$[(B\lor C)\land (B\rightarrow \lnot A)\land A)]\rightarrow C$
1	1	1	\	1	\	0	0	\	0	\	0	\	1
1	1	0	\	1	\	0	0	\	0	\	0	\	1
1	0	0	\	0	\	0	1	\	0	\	0	\	1
1	0	1	\	1	\	0	1	\	1	\	1	\	1
0	1	1	\	1	\	1	1	\	1	\	0	\	1
0	0	1	\	1	\	1	1	\	1	\	0	\	1
0	1	0	\	1	\	1	1	\	1	\	0	\	1
0	0	0	\	0	\	1	1	\	0	\	0	\	1

Somit ist die Tautologie hinreichend bewiesen - für alle Wahrheitswerte ist dieser Ausdruck wahr.

Anmerkung: Die Separation der Tabelle ist beabsichtigt und soll den sequentiellen Ablauf des Berechnungsvorganges verdeutlichen (Klammerausdrücke!).

Weitere Anmerkung: Eine Implikation $A\rightarrow B$ ist nur dann falsch, wenn A wahr ist und B falsch, ansonsten wahr.

Kontradiktion

$(A\rightarrow C)\land (C\rightarrow B)\land A\land \lnot B$

Um die Kontradiktion nachzuweisen, muss man für alle Wahrheitswerte von A,B,C nach den logischen Operationen ein Wahrheitswert Falsch als Ergebnis stehen.

Angabe "eindeutschen"

Die Angabe ist:

$(A\rightarrow C)\land (C\rightarrow B)\land A\land \lnot B$

1. Zuerst Prüfen wir die Implikation A-C,
2. Dann die Implikation C-B.
3. Die beiden oben gewonnenen Wahrheitswerte setzen wir in eine UND-Beziehung ...
4. die wir wiederum logisch UND mit A verknüpfen.
5. Abschließend setzen wir den letzten gewonnenen Wahrheitswert in eine UND-Beziehung mit dem negierten B.

Wahrheitstafel

A	B	C	\	$A\rightarrow C$ (W)	\	$C\rightarrow B$ (X)	\	$W\wedge X$ (Y)	\	$Y\wedge A$ (Z)	\	$\lnot B$	$Z\wedge \lnot B$
1	1	1	\	1	\	1	\	1	\	1	\	0	0
1	1	0	\	0	\	1	\	0	\	0	\	0	0
1	0	0	\	0	\	1	\	0	\	0	\	1	0
1	0	1	\	1	\	0	\	0	\	0	\	1	0
0	1	1	\	1	\	1	\	1	\	0	\	0	0
0	0	1	\	1	\	0	\	0	\	0	\	1	0
0	1	0	\	1	\	1	\	1	\	0	\	0	0
0	0	0	\	1	\	1	\	1	\	0	\	1	0

Damit ist die Kontradiktion hinreichend erwiesen.

Anti-Gittenberger-(und Anti-Panholzer)-Strategie ;-)

1. Tautologie
   1. Erklären was eine Tautologie ist
   2. Angabe beim Aufschreiben der Wahrheitstafel erklären
   3. Deuten
2. Kontradiktion
   1. Erklären was eine Kontradiktion ist
   2. Angabe beim Aufschreiben der Wahrheitstafel erklären
   3. Deuten

Hilfreiche Webressourcen

• https://web.archive.org/web/20180817161754/http://www.itc.rwth-aachen.de/go/id/fehc
• http://www.ifi.unizh.ch/cl/klenner/lehre/formale_grundlagen/Aussagenlogik.4.pdf