Blatt 7

2.

Welche der folgenden aussagenlogischen Aussagen stellen eine Tautologie dar?

a)

a → a

Tautologie

Aus etwas Falschem kann man alles, also auch etwas Falsches, folgern und aus etwas Wahrem kann man etwas Wahres folgern.

b)

a → (b → a)

 ≡ ¬a ∨ (¬b ∨ a)

 ≡ ¬a ∨ a ∨ ¬b

Tautologie

c)

(b → a) → a

keine Tautologie

Gegenbeispiel:

a: falsch

b: falsch

d)

a ∧ ¬a

keine Tautologie

unerfüllbar (Kontradiktion)

e)

keine Tautologie

a ∧ a ≡ a

f)

Tautologie

¬¬a → a ≡ a → a (siehe Aufgabe a))

g)

(¬a → ¬b) → (b → a)

Tautologie

Wahrheitstafel

I(a)            I(b)            I(¬a → ¬b)            I(b → a)            I(g)

f                 f                   w                            w                        w

f                 w                 f                              f                          w

w               f                   f                              f                          w

w               w                 f                              w                        w

h)

(a → (b → c)) → ((a → b) → (a → c))

Tautologie

Wahrheitstafel

I(a)    I(b)     I(c)   I(a → (b → c))  I((a → b) → (a → c))   I(h)

f         f          f              w                        w                                     w

f         f          w            w                        w                                     w

f         w        f              w                        w                                     w

f         w        w            w                        w                                     w

w       f          f              w                        w                                     w

w       f          w            w                        w                                     w

w       w        f              f                          f                                       w

w       w        w            w                        w                                     w

3.

Wandeln Sie folgende aussagenlogische Formeln in die konjunktive Normalform (KNF) um:

a)

a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c)

b)

a ↔ (b ∧ c) ≡ (a → (b ∧ c)) ∧ ((b ∧ c) → a) ≡ (¬a ∨ (b ∧ c)) ∧ (¬(b ∧ c) ∨ a) ≡ (¬a ∨ b) ∧ (¬a ∨ c) ∧ (a ∨ ¬b ∨ ¬c)

c)

(¬a ∧ (¬b → c)) → d ≡ ¬(¬a ∧ (b ∨ c)) ∨ d ≡ ¬((¬a ∧ b) ∨ (¬a ∧ c)) ∨ d ≡ (¬(¬a ∧ b) ∧ ¬(¬a ∧ c)) ∨ d ≡ ((a ∨ ¬b) ∧ (a ∨ ¬c)) ∨ d ≡ (a ∨ ¬b ∨ d) ∧ (a ∨ ¬c ∨ d)

5.

a)

Wandeln Sie folgende prädikatenlogische Formel in eine KNF um: 

∀Y (∀X (P(Z, X) ∨ Q(X, Y)) → (∃X P(Z, X) ∨ ∀X Q(X, Y)))

≡ ∀Y (¬ ∀X (P(Z, X) ∨ Q(X, Y)) ∨ ∃X P(Z, X) ∨ ∀X Q(X, Y))

≡ ∀Y (∃X (¬P(Z, X) ∧ ¬Q(X, Y)) ∨ ∃V P(Z, V) ∨ ∀W Q(W, Y))

≡ ∀Y ∃X ∃V ∀W ((¬P(Z, X) ∧ ¬Q(X, Y)) ∨ P(Z, V) ∨ Q(W, Y))

≡ ∀Y ∀W ((¬P(Z, f(Y)) ∧ ¬Q(f(Y), Y)) ∨ P(Z, g(Y)) ∨ Q(W, Y))

≡ (¬P(Z, f(Y)) ∧ ¬Q(f(Y), Y)) ∨ P(Z, g(Y)) ∨ Q(W, Y))

≡ (¬P(Z, f(Y)) ∨ P(Z, g(Y)) ∨ Q(W, Y)) ∧ (¬Q(f(Y), Y) ∨ P(Z, g(Y)) ∨ Q(W, Y))