logische Verkettungen von booleschen Werten mit Variablen

[lm1811]

a, b und c sind Boolesche Variablen. Je drei der aufgeführten Ausdrücke (1-6) sind äquivalent. Geben Sie an welche.

1: a and not a
2: True and (b or not a) and ((a or (c and not c)) or c) and (b or not a)
3: False
4: (c and not b and a) and (not c and not b)
5: (a and b) or (b and c) or (c and not a)
6: (a or c) and (b or not a)


Habe diese Aufgabe auf einem meiner Übungsblätter im Modul Programmierung. Wie geht man an sowas ran? Reicht es, für a, b, c generell einen Wahrheitswert anzunehmen und damit die Verkettung aufzulösen?

Danke im Vorraus
Leo

[__deets__]

Bei drei Variablen hast du 8 mögliche Kombination. Die stellt man als Wahrheitstabelle auf, und Pakt dann jede der Ausdrücke als Spalte daneben. Äquavilent sind die, welche die gleiche Spalte haben.

[ThomasL]

Code: Alles auswählen

from itertools import product

for a, b, c in product([True, False], repeat=3):
    print(a and not a)
    print(True and (b or not a) and ((a or (c and not c)) or c) and (b or not a))
    print(False)
    print((c and not b and a) and (not c and not b))
    print((a and b) or (b and c) or (c and not a))
    print((a or c) and (b or not a))
    print()

[__blackjack__]

@lm1811: Ich vermute mal ihr habt auch schon was zum Umstellen/Vereinfachen von boole'schen Ausdrücken gemacht? Denn sowohl bei 1 als auch bei 2 sollte einem sofort jeweils ein Vereinfachungsschritt auffallen, wobei 1 dann trivial wird und bei 2 ist der Fall 1 als Teilausdruck enthalten.

Ansonsten kann man es mit dem Rechner natürlich auch einfach ”brute force” heraus bekommen, in dem man wie bereits vorgeschlagen die Wahrheitstabellen über alle möglichen Belegungen von `a`, `b`, und `c` berechnet und die dann vergleicht.

Edit: Ach so, noch eine Möglichkeit: Statt zu vereinfachen, könnte man auch alle in eine der Normalformen überführen und dann vergleichen. Und natürlich auch eine Mischung aus den Verfahren, denn über vereinfachen kann man zumindest ein Paar leicht herausfinden und eleminieren, und für Fälle die nicht so einfach/offensichtlich sind, dann eines der anderen Verfahren verwenden.

[ThomasL]

Sollte die Aufgabe nicht durch ein Programm zu lösen sein sondern auf per Hand, dann ist das hier hilfreich.
https://de.wikipedia.org/wiki/Formelsammlung_Logik

[pillmuncher]

Schön, dass es sympy gibt:

Code: Alles auswählen

>>> from sympy.abc import a, b, c
>>> from sympy.logic.boolalg import to_dnf
>>> to_dnf(a & ~a, simplify=True)
a & ~a
>>> to_dnf(True & (b | ~a) & ((a | (c & ~c)) | c), simplify=True)
(a & b) | (c & ~a)
>>> to_dnf(False, simplify=True)
False
>>> to_dnf(((c & ~b & a) & (~c & ~b)), simplify=True)
a & c & ~b & ~c
>>> to_dnf((a & b) | (b & c) | (c & ~a), simplify=True)
(a & b) | (c & ~a)
>>> to_dnf((a | c) & (b | ~a), simplify=True)
(a & b) | (c & ~a)

Hint: (p & ~p) ist immer falsch.