Seien x1, x2, . . . , xn ∈ {w, f}. Wann ist der Ausdruck (·((x1 ↔ x2) ↔ x3) ↔ . . .) ↔ xn) wahr?

Question

Aufgabe:

Seien x1, x2, . . . , xn ∈ {w, f}. Wann ist der Ausdruck (·((x1 ↔x2) ↔ x3) ↔ . . .) ↔ xn) wahr?

Comments

Hast du versucht, die konjuktive Normalform (DNF) zu bilden?

https://en.wikipedia.org/wiki/Logical_biconditional#Truth_table

---

achso ja hab schon versucht aber es ist bis xn deswegen wusste nicht wie kann ich mit dem problem umgehen .hab versucht n=1  x1=w

n=2

x₁ ⇔x₂   x₁=w

x1=w,x2=w .

x1=f ,x2=f

aber wie kann ich bis xn beweisen ?

Answer 1

Abkürzungshalber sei E(n):=(·((x1 ↔x2) ↔ x3) ↔ . . .) ↔ xn),

Dann ist

$$E(n)$$ wahr, wenn die Mächtigkeit der Menge $$\left\{x_i=w\right\}$$ der Parität von n entspricht.

Mit anderen Worten für n gerade E(n) ist wahr, wenn die Anzahl der x_i = w gerade ist und für n ungerade, wenn die Anzahl der x_i = w ungerade ist.

Wie kann man das sehen? Wir können Ausdrücke A<=>B in boolesche Algebra übersetzen: 1 + A + B (MOD 2). Diese ist Assoziativ.
Somit haben wir E(n) ≅ n-1 + x_1 + ... + x_n (MOD 2)
Hier empfiehlt sich Fallunterscheidung, und Bemerkung, dass gleiche Werte x_i=x_j nichts zur Summe beitragen, m.a.W. Wahrheitswert nicht ändern.