Keine Tautologie in den Variablen A und B wenn nur UND und ODER Verknüpfungen erlaubt sind

Question

hier die Frage.

Beweisen Sie, dass es keine Tautologie in den Variablen A und B gibt, wenn nur die Verknüpfungen ∧ und ∨ (und beliebig viele Klammern) erlaubt sind. Zeigen Sie dazu mittels vollständiger Induktion, dass jeder solcher Ausdruck Wahrheitswert 0 hat, wenn A und B beide Wahrheitswert 0 haben.

Mir ist klar, dass die Behauptung gilt und warum. Auch der Ansatz es über die Wahrheitswerte 0 bei A und B zu zeigen ist klar. Mein Problem ist nur, das ganze jetzt formal korrekt zu formulieren. Mir schwebt jetzt ein Induktionsanfang der Art  Für A=0 und B=0 gilt A∨B = 0 und A∧B = 0 vor, aber ich weiß erstens nicht ob das der richtige Ansatz ist und zweitens wie ich dann weitermachen soll.

Answer 1

Ich vermute mal Induktion über die Länge solcher Ausdrücke.
Für die kürzesten, die es gibt, kann man das sicher zeigen  A ^ A , A ^ B etc.

wenn man dann annimmt, das es für alle Ausdrücke bis zu einer gewissen Länge n gilt,
muss man halt zeigen, dass der nächstlängere Ausdruck auch keine Taut. sein kann.

Comments

Ja genau so hatte ich mir das auch vorgestellt, aber wie zeigt man das mathematisch korrekt ohne einfach nen Text zu schreiben, dass das so ist.