Zeigen Sie, dass \pi eine Basis ist.

Question

Aufgabe:

Das aussagenlogische Konnektiv NAND \( (\bar{\pi}) \) ist definiert als
\( \operatorname{val}_{I}(G \pi H)=\left\{\begin{array}{l} \mathbf{w}, \text { falls } \operatorname{val}_{I}(G)=\mathbf{f} \text { oder } \operatorname{val}_{I}(H)=\mathbf{f} \\ \mathbf{f}, \text { sonst } \end{array}\right. \)
für beliebige Formeln \( G, H \in For_{A L} \).

Zeigen Sie, dass \( \pi \) eine Basis ist. Geben Sie dafür (ohne Beweis) für die folgenden Formeln je eine äquivalente aussagenlogische Formel an, die nur \( \pi \) benutzt:
i) \( \neg \mathrm{P} \)
ii) \( P \wedge Q \)
iii) \( P \vee Q \)
iv) \( P \rightarrow Q \)

Problem/Ansatz:

Leider komme ich gerade nicht weiter bei folgender Aufgabe. Brauche Hilfe einen Ansatz zu finden. Es würde auch reichen eine Teilaufgabe ausführlich zu lösen damit ich einen grobe Ahnung habe wie sowas geht.

Answer 1

i) \( \neg \mathrm{P} \)

Mittels P und π eine Formel basteln.

Mittels der Wahrheitstabelle der Formel prüfen ob die Formel äquivalent zu \( \neg \mathrm{P} \) ist.

ii) \( P \wedge Q \)

Ebenso. Nur vorher noch nachdenken.

iii) \( P \vee Q \)

Da du ja schon \(\neg\) und \(\wedge\) hast, kannst du

        \(P\vee Q \equiv \neg(\neg P \wedge \neg Q)\)

verwenden.

iv) \( P \rightarrow Q \)

Da du ja schon \(\neg\) und \(\vee\) hast, kannst du

    \(P\rightarrow Q \equiv Q\vee \neg P\)

verwenden.