Ćwiczenia 9: rachunek zdań

Zadania

1. Znaleźć, o ile istnieje, taką formułę zdaniową \(\alpha\), aby następujące formuła była tautologią rachunku zdań:
   a) \( (\alpha \to p) \to (p\to q) \),
   b)\( ((r \to (\neg q \wedge p)) \to \alpha) \to (\alpha \wedge (p\to q) \wedge r) \).
2.  Udowodnić, że dla dowolnej funkcji \(f: \{0,1\}^k \to \{0,1\}\) istnieje formuła zdaniowa \(\alpha\), w której występują tylko zmienne zdaniowe \(p_1, ...,p_k\) o tej własności, że dla dowolnego wartościowania zdaniowego \(v\) zachodzi:
   \[ [\alpha]_v = f(v(p_1), \ldots, v(p_k))\]
   Innymi słowy: formuła \(\alpha\) definiuje funkcję \(f\).
3. Czy następujące zbiory formuł są spełnialne?
   a) \( \{ p \to \neg q, q \to \neg r, r \to \neg p \} \),
   b) \( \{ p\to q, q \to r, r \vee s \leftrightarrow \neg q \} \),
   c) \( \{ s \to p, p \vee \neg q, \neg (s \wedge p), s \} \).
4. Zbadać, czy następujące rozumowania są logicznie poprawne. Każde stwierdzenie trzeba zastąpić zmienną zdaniowa, następnie należy stwierdzić czy konkluzja wynika z koniunkcji przesłanek.
   a) Jeśli Jones jest komunistą, to Jones jest ateista. Jonest jest ateistą. Zatem Jones jest komunistą.
   b) Jeśli temperatura i ciśnienie nie zmieniają się, nie ma deszczu. Temperatura nie zmieniła się. Zatem jeśli spadł deszcz, to ciśnienie się zmieniło.

Praca domowa

Zadanie 115 ze zbioru zadań.