Aussagenlogik, Assoziativgesetz

Wissenschaft Mathematik
#1

hallo!

Es soll gezeigt werden, dass

((a \leftrightarrow b) \leftrightarrow c) \leftrightarrow (a\leftrightarrow(b\leftrightarrow c))

immer „true“ ist.

Das Assoziativgesetz gilt ja nur für AND und OR, aber nicht für ÄQUIVALENT.
Ich habe gerade mal alle 8 möglichen Fälle
a=b=c=true
a=b=true, c=false
…

ausprobiert und es kommt tatsächlich immer „true“ raus.
Muss man, um dies zu zeigen, wirklich alle acht Fälle ausprobieren oder geht das kürzer?

Gruß
Paul

#2

Hi Paul,

in der Mathematik gibt es mehrere Wege, um etwas zu beweisen. Ich kenne jetzt nur 3:

  1. dirkt Beweisen:
    Du zählst eins auf und damit ist es bewiesen für den Fall. Beweist du alle 8 Fälle direkt, dann stimmen alle Fälle und du kannst damit dann eine Aussage treffen.
    Oder du sagst einfach ein Gegenbeweis.

2)Indirket Beweisen: Du sagst einfach, dass es nicht geht und beweist dir dann selbst das Gegenteil. Du versuchst also deine Vermutun zu widerlegen, was aber nicht geht. Damit hättest du es auch bewiesen.

  1. Induktiver Beweis: Keine Ahnung, wie das hier funktionieren würde, ich weiß nur, dass es diese Möglichkeit gibt.

mfg,

Hanzo

#3

Hallo,

Das Assoziativgesetz gilt ja nur für AND und OR, aber nicht für ÄQUIVALENT.

wie kommst Du darauf? Auch der Äquivalenz-Operator (und ebenso seine Verneinung, das Exklusiv-Oder) ist assoziativ. Das sollst Du ja hier beweisen.

ausprobiert und es kommt tatsächlich immer „true“ raus.
Muss man, um dies zu zeigen, wirklich alle acht Fälle
ausprobieren oder geht das kürzer?

Du könntest einfach die \Leftrightarrow-Definition anwenden:

x \Leftrightarrow y
: := :
x \cdot y + \overline{x} \cdot \overline{y}

Damit ist

(a \Leftrightarrow b) \Leftrightarrow c

(a \cdot b + \overline{a} \cdot \overline{b}) \cdot c
+
\overline{a \cdot b + \overline{a} \cdot \overline{b}} \cdot \overline{c}

und wenn Du das via deMorgan-Verneinungsgesetze in die DNF (disjunktive Normalform) umformst, lautet das Ergebnis

a \cdot b \cdot c + \overline{a} \cdot b \cdot \overline{c} + a \cdot \overline{b} \cdot \overline{c} + \overline{a} \cdot \overline{b} \cdot c =: d

Dasselbe machst Du mit

a \Leftrightarrow (b \Leftrightarrow c) = …

und kommst wiederum auf die obige DNF. Damit ist der Beweis erbracht:

((a \Leftrightarrow b) \Leftrightarrow c)
\Leftrightarrow
(a \Leftrightarrow (b \Leftrightarrow c))
= d \Leftrightarrow d
= d \cdot d + \overline{d} \cdot \overline{d}
= d + \overline{d}
= \rm wahr

Gruß
Martin