Notwendige und hinreichende Bedingung

Um zu vollständigen Beweisen zu gelangen, ist die einfache Beweisführung A ⇒ B (A impliziert B) nicht ausreichend.

Beispiel 1:

Aussage P: x ist durch 6 teilbar.
Aussage Q: x ist durch 3 teilbar

Implikation: P ⇒ Q

Hinreichende Bedingung

P ist hinreichend für Q

Wenn x durch 6 teilbar ist, muss x auch durch 3 teilbar sein.

... und Q ⇒ P?

Notwendige Bedingung

Q ist notwendig, aber nicht hinreichend für P

Damit x durch 6 teilbar ist, muss x mindestens auch durch 3 teilbar sein.

A ist hinreichend für B. Es genügt, dass A wahr ist, dann ist zwingend auch B wahr. B ist notwendig für A. Ohne B kann A nicht erfüllt sein (siehe Wahrheitstafel Implikation).

Vollständig ist eine Beweisführung, wenn ein notwendiger und hinreichender Beweis angeführt werden kann: A ⇔ B.

Beispiel 2:

Aussage: P: x ist durch 6 teilbar
Aussage Q: x ist (durch 3 teilbar) ∧ gerade

Notwendige und hinreichende Bedingung

P ⇔ Q

Q ist notwendig und hinreichend für P

Wenn x gerade (durch 2 teilbar) und durch 3 teilbar ist, dann ist x auch durch 6 teilbar. Die Umkehrung dieser Aussage ist ebenso wahr.

Ein vollständiger Beweis muss auch im Umkehrschluss zu richtigen Aussagen führen:

{A ⇔ B} ⇔ { (A ⇒ B) ∧ (B ⇒ A) }