Tautologie Aufgaben Lösungen

Skripte

Projekte

Impressum

Zurück zur Übersicht Zurück zu DNF und KNF

2. Tautologie

Aufgaben

Aufgabe 1:
Ist die folgende Formel eine Tautologie? Begründen Sie die Antwort.

(A ∨(A ∧B)) → A

Aufgabe 2:
Ist die folgende Formel eine Tautologie? Begründen Sie die Antwort.

(A ∧(A ∨B)) → A

Aufgabe 3:
Ist die folgende Formel eine Tautologie? Begründen Sie die Antwort.

(A ∨(¬ A ∧B)) → (A ∨B)

Aufgabe 4:
Ist die folgende Formel eine Tautologie? Begründen Sie die Antwort.

(A ∧(¬ A ∨B)) → (A ∧B)

Aufgabe 5:
Ist die folgende Formel eine Tautologie? Begründen Sie die Antwort.

((A ∨B) ∧(A ∨¬ B)) → A

Aufgabe 6:
Ist die folgende Formel eine Tautologie? Begründen Sie die Antwort.

((A ∧B) ∨(A ∧¬ B)) → A

Aufgabe 7:
Ist die folgende Formel eine Tautologie? Begründen Sie die Antwort.

((A ∨B) ∧(A ∨C)) → (A ∨(B ∧C))

Aufgabe 8:
Ist die folgende Formel eine Tautologie? Begründen Sie die Antwort.

((A ∧B) ∨(A ∧C)) → (A ∧(B ∨C))

Aufgabe 9:
Ist die folgende Formel eine Tautologie? Begründen Sie die Antwort.

((A ∧B) ∨(C ∧D)) → ((A ∨C) ∧(B ∨C) ∧(A ∨D) ∧(B ∨D))

Aufgabe 10:
Ist die folgende Formel eine Tautologie? Begründen Sie die Antwort.

((A ∨B) ∧(C ∨D)) → ((A ∧C) ∨(B ∧C) ∨(A ∧D) ∨(B ∧D))

Aufgabe 11:
Ist die folgende Formel eine Tautologie? Begründen Sie die Antwort.

((A ∧B) ∨(¬ A ∧C)) → ((A ∧B) ∨(¬ A ∧C) ∨(B ∧C))

Aufgabe 12:
Ist die folgende Formel eine Tautologie? Begründen Sie die Antwort.

((A ∨B) ∧(¬ A ∨C)) → ((A ∨B) ∧(¬ A ∨C) ∧(B ∨C))

Lösungen

Aufgabe 1:

(A ∨(A ∧B)) → A

≡

(A ∨(A ∧B)) → A

≡

¬ (A ∨(A ∧B)) ∨A

≡

(¬ A ∧¬ (A ∧B)) ∨A

≡

(¬ A ∧(¬ A ∨¬ B)) ∨A

≡

¬ A ∨A

≡

Die Formel (A ∨(A ∧B)) → A ist eine Tautologie.

Aufgabe 2:

(A ∧(A ∨B)) → A

≡

(A ∧(A ∨B)) → A

≡

¬ (A ∧(A ∨B)) ∨A

≡

(¬ A ∨¬(A ∨B)) ∨A

≡

(¬ A ∨(¬ A ∧¬ B)) ∨A

≡

(¬ A ∨¬ A) ∨(¬ A ∧¬ B) ∨A

≡

(¬ A ∨A) ∨(¬ A ∧¬ B)

≡

T∨(¬ A ∧¬ B)

≡

Die Formel (A ∧(A ∨B)) → A ist eine Tautologie.

Aufgabe 3:

(A ∨(¬ A ∧B)) → (A ∨B)

≡

(A ∨(¬ A ∧B)) → (A ∨B)

≡

¬(A ∨(¬ A ∧B)) ∨(A ∨B)

≡

(¬ A ∧¬(¬ A ∧B)) ∨(A ∨B)

≡

(¬ A ∧( A ∨¬ B)) ∨(A ∨B)

≡

((¬ A ∧A) ∨( ¬ A ∧¬ B)) ∨(A ∨B)

≡

(¬ A ∧¬ B) ∨(A ∨B)

≡

¬(A ∨B) ∨(A ∨B)

≡

Die Formel (A ∨(¬ A ∧B)) → (A ∨B) ist eine Tautologie.

Aufgabe 4:

(A ∧(¬ A ∨B)) → (A ∧B)

≡

(A ∧(¬ A ∨B)) → (A ∧B)

≡

¬ (A ∧(¬ A ∨B)) ∨(A ∧B)

≡

(¬ A ∨¬(¬ A ∨B)) ∨(A ∧B)

≡

(¬ A ∨(A ∧¬ B)) ∨(A ∧B)

≡

(¬ A ∨A) ∧(¬ A ∨¬ B)) ∨(A ∧B)

≡

(¬ A ∨¬ B) ∨(A ∧B)

≡

¬(A ∧B) ∨(A ∧B)

≡

Die Formel (A ∧(¬ A ∨B)) → (A ∧B) ist eine Tautologie.

Aufgabe 5:

((A ∨B) ∧(A ∨¬ B)) → A

≡

((A ∨B) ∧(A ∨¬ B)) → A

≡

¬((A ∨B) ∧(A ∨¬ B)) ∨A

≡

(¬(A ∨B) ∨¬(A ∨¬ B)) ∨A

≡

((¬ A ∧¬ B) ∨(¬ A ∧B)) ∨A

≡

((¬ A∨¬ A)∧(¬ A∨B)∧(¬ B∨¬ A)∧(¬ B∨B)) ∨A

≡

(¬ A ∧(¬ A∨B)∧(¬ B∨¬ A)) ∨A

≡

¬ A ∨A

≡

Die Formel ((A ∨B) ∧(A ∨¬ B)) → A ist eine Tautologie.

Aufgabe 6:

((A ∧B) ∨(A ∧¬ B)) → A

≡

((A ∧B) ∨(A ∧¬ B)) → A

≡

¬((A ∧B) ∨(A ∧¬ B)) ∨A

≡

(¬(A ∧B) ∧¬(A ∧¬ B)) ∨A

≡

((¬ A ∨¬ B) ∧(¬ A ∨B)) ∨A

≡

¬ A ∨A

≡

Die Formel ((A ∧B) ∨(A ∧¬ B)) → A ist eine Tautologie.

Aufgabe 7:

((A ∨B) ∧(A ∨C)) → (A ∨(B ∧C))

≡

((A ∨B) ∧(A ∨C)) → (A ∨(B ∧C))

≡

¬((A ∨B) ∧(A ∨C)) ∨(A ∨(B ∧C))

≡

(¬(A ∨B) ∨¬(A ∨C)) ∨(A ∨(B ∧C))

≡

((¬ A ∧¬ B) ∨(¬ A ∧¬ C)) ∨(A ∨(B ∧C))

≡

(¬ A ∧(¬ B ∨¬ C)) ∨(A ∨(B ∧C))

≡

(¬ A ∧¬(B ∧C)) ∨(A ∨(B ∧C))

≡

¬ (A ∨(B ∧C)) ∨(A ∨(B ∧C))

≡

Die Formel ((A ∨B) ∧(A ∨C)) → (A ∨(B ∧C)) ist eine Tautologie.

Aufgabe 8:

((A ∧B) ∨(A ∧C)) → (A ∧(B ∨C))

≡

((A ∧B) ∨(A ∧C)) → (A ∧(B ∨C))

≡

¬((A ∧B) ∨(A ∧C)) ∨(A ∧(B ∨C))

≡

(¬ (A ∧B) ∧¬ (A ∧C)) ∨(A ∧(B ∨C))

≡

( (¬ A ∨¬ B) ∧(¬ A ∨¬ C)) ∨(A ∧(B ∨C))

≡

(¬ A ∨(¬ B ∧¬ C)) ∨(A ∧(B ∨C))

≡

(¬ A ∨¬(B ∨C)) ∨(A ∧(B ∨C))

≡

¬(A ∧(B ∨C)) ∨(A ∧(B ∨C))

≡

Die Formel ((A ∧B) ∨(A ∧C)) → (A ∧(B ∨C)) ist eine Tautologie.

Aufgabe 9:

((A ∧B) ∨(C ∧D)) → ((A ∨C) ∧(B ∨C) ∧(A ∨D) ∧(B ∨D))

≡

((A ∧B) ∨(C ∧D)) → ((A ∨C) ∧(B ∨C) ∧(A ∨D) ∧(B ∨D))

≡

¬ ((A ∧B) ∨(C ∧D)) ∨((A ∨C) ∧(B ∨C) ∧(A ∨D) ∧(B ∨D))

≡

(¬(A ∧B) ∧¬(C ∧D)) ∨((A ∨C) ∧(B ∨C) ∧(A ∨D) ∧(B ∨D))

≡

((¬ A ∨¬ B) ∧(¬ C ∨¬ D)) ∨((A ∨C) ∧(B ∨C) ∧(A ∨D) ∧(B ∨D))

≡

((¬ A ∧¬ C) ∨(¬ A ∧¬ D) ∨(¬ B ∧¬ C) ∨(¬ B ∧¬ D))∨

((A ∨C) ∧(B ∨C) ∧(A ∨D) ∧(B ∨D))

≡

(¬ (A ∨C) ∨¬(A ∨D) ∨¬(B ∨C) ∨¬(B ∨D))∨

((A ∨C) ∧(B ∨C) ∧(A ∨D) ∧(B ∨D))

≡

¬( (A ∨C) ∧(A ∨D) ∧(B ∨C) ∧(B ∨D))∨

((A ∨C) ∧(B ∨C) ∧(A ∨D) ∧(B ∨D))

≡

Die Formel ((A ∧B) ∨(C ∧D)) → ((A ∨C) ∧(B ∨C) ∧(A ∨D) ∧(B ∨D)) ist eine Tautologie.

Aufgabe 10:

((A ∨B) ∧(C ∨D)) → ((A ∧C) ∨(B ∧C) ∨(A ∧D) ∨(B ∧D))

≡

((A ∨B) ∧(C ∨D)) → ((A ∧C) ∨(B ∧C) ∨(A ∧D) ∨(B ∧D))

≡

¬((A ∨B) ∧(C ∨D)) ∨((A ∧C) ∨(B ∧C) ∨(A ∧D) ∨(B ∧D))

≡

(¬(A ∨B) ∨¬(C ∨D)) ∨((A ∧C) ∨(B ∧C) ∨(A ∧D) ∨(B ∧D))

≡

((¬ A ∧¬ B) ∨(¬ C ∧¬ D)) ∨((A ∧C) ∨(B ∧C) ∨(A ∧D) ∨(B ∧D))

≡

((¬ A ∨¬ C)∧(¬ A ∨¬ D)∧(¬ B∨¬ C)∧(¬ B ∨¬ D)) ∨

((A ∧C) ∨(B ∧C) ∨(A ∧D) ∨(B ∧D))

≡

(¬(A ∧C)∧¬(A ∧D)∧¬ (B∧C)∧¬ (B∧D)) ∨

((A ∧C) ∨(B ∧C) ∨(A ∧D) ∨(B ∧D))

≡

¬((A ∧C) ∨(A ∧D)∨(B∧C) ∨(B∧D)) ∨

((A ∧C) ∨(B ∧C) ∨(A ∧D) ∨(B ∧D))

≡

Die Formel ((A ∨B) ∧(C ∨D)) → ((A ∧C) ∨(B ∧C) ∨(A ∧D) ∨(B ∧D)) ist eine Tautologie.

Aufgabe 11:

((A ∧B) ∨(¬ A ∧C)) → ((A ∧B) ∨(¬ A ∧C) ∨(B ∧C))

≡

((A ∧B) ∨(¬ A ∧C)) → ((A ∧B) ∨(¬ A ∧C) ∨(B ∧C))

≡

¬((A ∧B) ∨(¬ A ∧C)) ∨((A ∧B) ∨(¬ A ∧C) ∨(B ∧C))

≡

(¬(A ∧B) ∧¬(¬ A ∧C)) ∨((A ∧B) ∨(¬ A ∧C) ∨(B ∧C))

≡

((¬ A ∨¬ B) ∧( A ∨¬ C)) ∨((A ∧B) ∨(¬ A ∧C) ∨(B ∧C))

≡

((¬ A ∧A) ∨(¬ A ∧¬ C)∨(¬ B ∧A) ∨(¬ B ∧¬ C)) ∨

((A ∧B) ∨(¬ A ∧C) ∨(B ∧C))

≡

((¬ A ∧¬ C)∨(¬ B ∧A) ∨(¬ B ∧¬ C)) ∨

((A ∧B) ∨(¬ A ∧C) ∨(B ∧C))

≡

((¬ C ∧(¬ A ∨¬ B)) ∨(¬ B ∧A)) ∨

((A ∧B) ∨(¬ A ∧C) ∨(B ∧C))

≡

((¬ C ∨¬ B) ∧(¬ C ∨A) ∧(¬ A ∨¬ B ∨¬ B) ∧(¬ A ∨¬ B ∨A)) ∨

((A ∧B) ∨(¬ A ∧C) ∨(B ∧C))

≡

((¬ C ∨¬ B) ∧(¬ C ∨A) ∧(¬ A ∨¬ B)) ∨

((A ∧B) ∨(¬ A ∧C) ∨(B ∧C))

≡

(¬ (C ∧B) ∧¬(C ∧¬ A) ∧¬(A ∧B)) ∨

((A ∧B) ∨(¬ A ∧C) ∨(B ∧C))

≡

¬ ((C ∧B) ∨(C ∧¬ A) ∨(A ∧B)) ∨((A ∧B) ∨(¬ A ∧C) ∨(B ∧C))

≡

Die Formel ((A ∧B) ∨(¬ A ∧C)) → ((A ∧B) ∨(¬ A ∧C) ∨(B ∧C)) ist eine Tautologie.

Aufgabe 12:

((A ∨B) ∧(¬ A ∨C)) → ((A ∨B) ∧(¬ A ∨C) ∧(B ∨C))

≡

((A ∨B) ∧(¬ A ∨C)) → ((A ∨B) ∧(¬ A ∨C) ∧(B ∨C))

≡

¬ ((A ∨B) ∧(¬ A ∨C)) ∨((A ∨B) ∧(¬ A ∨C) ∧(B ∨C))

≡

(¬(A ∨B) ∨¬(¬ A ∨C)) ∨((A ∨B) ∧(¬ A ∨C) ∧(B ∨C))

≡

((¬ A ∧¬ B) ∨(A ∧¬ C)) ∨((A ∨B) ∧(¬ A ∨C) ∧(B ∨C))

≡

((¬ A ∨A) ∧(¬ A ∨¬ C) ∧(¬ B ∨A) ∧(¬ B ∨¬ C)) ∨

((A ∨B) ∧(¬ A ∨C) ∧(B ∨C))

≡

(((¬ A ∧¬ B) ∨¬ C) ∧(¬ B ∨A) ) ∨

((A ∨B) ∧(¬ A ∨C) ∧(B ∨C))

≡

((((¬ A ∧¬ B) ∨¬ C) ∧¬ B) ∨(((¬ A ∧¬ B) ∨¬ C) ∧A) ) ∨

((A ∨B) ∧(¬ A ∨C) ∧(B ∨C))

≡

((((¬ A ∧¬ B)∧¬ B) ∨(¬ C∧¬ B) ) ∨(((¬ A ∧¬ B)∧A) ∨(¬ C∧A))) ) ∨

((A ∨B) ∧(¬ A ∨C) ∧(B ∨C))

≡

((¬ A ∧¬ B) ∨(¬ C∧¬ B) ∨(¬ C∧A) ) ∨

((A ∨B) ∧(¬ A ∨C) ∧(B ∨C))

≡

(¬ ( A ∨B) ∨¬(C ∨B) ∨¬(C ∨¬ A) ) ∨((A ∨B) ∧(¬ A ∨C) ∧(B ∨C))

≡

¬ (( A ∨B) ∧(C ∨B) ∧(C ∨¬ A) ) ∨((A ∨B) ∧(¬ A ∨C) ∧(B ∨C))

≡

Die Formel ((A ∨B) ∧(¬ A ∨C)) → ((A ∨B) ∧(¬ A ∨C) ∧(B ∨B)) ist eine Tautologie.

Sascha Frank

Last modified: Wed Jun 10 18:42:57 CEST 2009