0 Daumen
525 Aufrufe

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.

Avatar von

1 Antwort

0 Daumen
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.
Avatar von 289 k 🚀

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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community