Beweis von vollständigen Operatorensystemen mit Implikation und Konstante 0

Question

Frage zur Lösung: Vollständiges Operatorensystem durch Implikationsoperator und Konstante 0

Also mein Problem liegt eher beim generellen Verständnis bei diesen Beweisen. Wenn man beweisen soll, dass sowas ein vollständiges Operatorensystem ist, muss man ja zeigen, dass sich die UND, ODER und Negation, durch die jeweiligen Komponenten von denen gefragt wird ob sie ein Operatorensystem bilden, darstellen lassen.

Aber zum Beispiel ganz unten beim Beweis vom ODER: Die zwei Seiten sind doch nicht gleichwertig oder?

Weil wenn man sagt (a impliziert 0) impliziert b ist das doch gleichzusetzen mit -a ODER b (nach der Wahrheitstabelle jetzt)

Oder auch beim ersten: -a = a impliziert 0. Ich verstehe, dass von der Wahrheitstabelle aus, dass der einzige Ausdruck ist der das Ergebnis 0 werden lässt, aber warum sagt man deshalb, dass das Ergebnis gleichzusetzen ist mit -a ?

Will man bei solchen beweisen, generell nur zeigen, dass man die ODER, UND, Negation darstellen kann? Also wirklich nur, dass diese spezifischen Zeichen dargestellt werden können? Oder ob man genau: a UND b, a ODER b, -a, darstellen muss? Also mit Vorzeichen jetzt beachtet.

Mir leuchtet nicht ein warum a ODER b = -a ODER b (oder anders geschrieben (a impliziert 0) impliziert b ist)

Das sind die Lösungen:
\( \begin{aligned} \bar{a} &=a \rightarrow 0 \\ a \wedge b &=(\overline{\bar{a} \vee \bar{b}}) \\ &=(\overline{a \rightarrow \bar{b}}) \\ &=(\overline{a \rightarrow(b \rightarrow 0)}) \\ &=(a \rightarrow(b \rightarrow 0)) \rightarrow 0 \\ a \vee b &=(a \rightarrow 0) \rightarrow b \end{aligned} \)

Danke schonmal im Voraus an jeden der sich das durchliest ^^

Gruß naili

Answer 1

Wenn man beweisen soll, dass sowas ein vollständiges Operatorensystem ist, muss man ja zeigen, dass sich die UND, ODER und Negation, durch die jeweiligen Komponenten von denen gefragt wird ob sie ein Operatorensystem bilden, darstellen lassen.

Das muss man nicht. Es genügt zu zeigen, dass sich jeder Operator eines bekanntermaßen vollständigen Operatorensystems durch die jeweiligen Komponenten, von denen gefragt wird ob sie ein Operatorensystem bilden, darstellen lassen.

Wenn UND, ODER und Negation ein vollständiges Operationensystem sind, dann sind UND und Negation auch eines, weil sich ODER mittels

        a ∨ b ≡ ¬(¬a ∧ ¬b)

aus UND und Negation darstellen lässt.

Aber zum Beispiel ganz unten beim Beweis vom ODER: Die zwei Seiten sind doch nicht gleichwertig oder?

Doch, sind sie.

Weil wenn man sagt (a impliziert 0) impliziert b ist das doch gleichzusetzen mit -a ODER b (nach der Wahrheitstabelle jetzt)

Dann ist deine Wahrheitstabelle falsch. Ferfollständige volgende:

a	b	a→0	(a→0)→b	a∨b
0	0			0
0	1			1
1	0			1
1	1			1

Ich verstehe, dass von der Wahrheitstabelle aus, dass der einzige Ausdruck ist der das Ergebnis 0 werden lässt, aber warum sagt man deshalb, dass das Ergebnis gleichzusetzen ist mit -a ?

Ich blick die Grammatik dieses Satzes irgendwie nicht.

Hier ist die Wahrheitstabelle von a→b:

a	b	a→b
0	0	1
0	1	1
1	0	0
1	1	1

Die Wahrheitstabelle von a→0 bekommt man, indem man nur die Zeilen betrachtet, in denen b = 0 ist, Wenn b = 0 ist, dann kann man in der Wahrheitstabelle die Spalte b komplett weglassen. Dann bekommt man

a	a→0
0	1
1	0

Und dass ist nun mal da gleiche wie ¬a.

Comments

Ja also die Lösungen sind:

0  0

0  1

1  0

0  1

Das verstehe ich schon. Aber im Skript habe ich gelernt, dass sich ja der Implikant z.B. a → b durch -a v b darstellen lässt.

Und von dem Ausgangspunkt wurden dann diese Schritte wie oben ausgeführt. (bei UND jetzt)

Aber nochmal kurz zu dem ODER.

Wenn (a -> 0) -> b und -a = a -> 0

dann kann man doch die (a -> 0) von dem (a -> 0) -> b mit -a ersetzen, sodass man -a -> b bekommt.

a	-a	b	-a -> b
0	1	0	0
0	1	1	1
1	0	0	1

 1       0      1      1

Ah okay ich habs erkannt ^^

Ja okay. Danke für die Erklärung. Ich hab nur sehr Probleme irgendwie den Ansatz bei solchen Beweisen zu finden. Weil eigentlich hat es der Professor ohne die Wahrheitstafeln erklärt (was wir auch so üben sollten), aber ich mich sehr schwer getan, da die Muster zu finden.