Logika dla informatyków/Ćwiczenia 1

Ćwiczenie 1

Zbadać, czy następujące formuły są tautologiami rachunku zdań i czy są spełnialne:

1. $(p\to r)\wedge (q\to s)\wedge (\mathrm{\neg }p\vee \mathrm{\neg }s)\to (\mathrm{\neg }p\vee \mathrm{\neg }q)$;
2. $(p\to q)\vee (q\to r)$;
3. $((p\to q)\to r)\wedge \mathrm{\neg }(((q\to r)\to r)\to r))$;
4. $(p\to q)\wedge (\mathrm{\neg }p\to r)\to (r\to \mathrm{\neg }q)$;
5. $((\mathrm{\neg }p\to q)\to r)\to \mathrm{\neg }(p\to q)$;
6. $p\vee (\mathrm{\neg }p\wedge q)\vee (\mathrm{\neg }p\wedge \mathrm{\neg }q)$;
7. $(p\to q)\vee (p\to \mathrm{\neg }q)$;
8. $q\vee r\to (p\vee q\to p\vee r)$;
9. $(p\vee q\vee r)\wedge (q\vee (\mathrm{\neg }p\wedge s))\wedge (\mathrm{\neg }s\vee q\vee r)\to q$.

Ćwiczenie 2

Czy następujące zbiory formuł są spełnialne?

1. $\{p\to \mathrm{\neg }q,q\to \mathrm{\neg }r,r\to \mathrm{\neg }p\}$;
2. $\{p\to q,q\to r,r\vee s\leftrightarrow \mathrm{\neg }q\}$;
3. $\{\mathrm{\neg }(\mathrm{\neg }q\vee p),p\vee \mathrm{\neg }r,q\to \mathrm{\neg }r\}$;
4. $\{s\to q,p\vee \mathrm{\neg }q,\mathrm{\neg }(s\wedge p),s\}$.

Ćwiczenie 3

Czy zachodzą następujące konsekwencje?

1. $p\wedge q\to \mathrm{\neg }r,p\models r\to \mathrm{\neg }q$;
2. $p\to q,p\to (q\to r)\models p\to r$;
3. $p\to (q\to r),p\to q\models q\to r$;
4. $(p\to q)\to r,\mathrm{\neg }p\models r$;
5. $(p\to q)\to r,\mathrm{\neg }r\models p$;
6. $p\to q,r\to \mathrm{\neg }q\models r\to \mathrm{\neg }p$.

Ćwiczenie 4

Dla dowolnej formuły Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} niech Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \hat{\var\varphi}} oznacza dualizację formuły Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} , tzn. formułę powstającą z Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} przez zastąpienie każdego wystąpienia $\wedge$ symbolem $\vee$ oraz każdego wystąpienia $\vee$ symbolem $\wedge$.

(i) Dowieść, że Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} jest tautologią wtedy i tylko wtedy, gdy Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \neg\hat{\var\varphi}} jest tautologią.

(ii) Dowieść, że Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\leftrightarrow\psi} jest tautologią wtedy i tylko wtedy, gdy Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \hat{\var\varphi}\leftrightarrow\hat{\psi}} jest tautologią.

Ćwiczenie 5

Znależć formułę zdaniową Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} , która jest spełniona dokładnie przy wartościowaniach $\varrho$ spełniających warunki:

1. Dokładnie dwie spośród wartości $\varrho (p)$, $\varrho (q)$ i $\varrho (r)$ są równe 1.
2. $\varrho (p)=\varrho (q)=\varrho (r)$.

Rozwiązanie: Można to robić na różne sposoby, ale najprościej po prostu wypisać alternatywę koniunkcji, np. $(p\wedge q\wedge \mathrm{\neg }r)\vee (p\wedge \mathrm{\neg }q\wedge r)$.

Ćwiczenie 6

Udowodnić, że dla dowolnej funkcji $f:\{0,1{\}}^k\to \{0,1\}$ istnieje formuła Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} , w której występują tylko spójniki $\to$ i $\mathrm{\perp }$ oraz zmienne zdaniowe ze zbioru $\{p_1,\dots ,p_k\}$, o tej własności, że dla dowolnego wartościowania zdaniowego $\varrho$ zachodzi równość Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle [[\var\varphi]]\varrho = f(\varrho(p_1),\ldots, \varrho(p_k))} . (Inaczej mówiąc, formuła Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} definiuje funkcję zerojedynkową $f$.)

Wskazówka: Indukcja ze względu na $k$.

 

Ćwiczenie 7

Niech $X$ będzie dowolnym zbiorem niepustym. Dowolną funkcję Parser nie mógł rozpoznać (błąd składni): {\displaystyle v:\mbox{\small ZZ}\to P(X)} nazwijmy wartościowaniem w zbiorze $P(X)$. Każdej formule zdaniowej Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} przypiszemy teraz pewien podzbiór Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle [[\var\varphi]]\warpi} zbioru $X$, który nazwiemy jej wartością przy wartościowaniu $v$.

• $[[\mathrm{\perp }]]v=\mathrm{\varnothing }$ oraz $[[top]]v=X$;
• $[[p]]v=v(p)$, gdy $p$ jest symbolem zdaniowym;
• Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle [[\neg\var\varphi]]v= X-[[{\var\varphi]]v} ;
• Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle [[\var\varphi\vee\psi ]]v=[[\var\varphi]]v \cup [[\psi]]v} ;
• Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle [[\var\varphi\wedge\psi ]]v=[[\var\varphi]]v \cap [[\psi]]v} ;
• Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle [[\var\varphi\to\psi]]v= (X-[[\var\varphi]]v) \cup[[\psi]]v} .

Udowodnić, że formuła Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} jest tautologią rachunku zdań wtedy i tylko wtedy, gdy jest prawdziwa w $P(X)$, tj. gdy dla dowolnego $v$jej wartością jest cały zbiór $X$.

Ćwiczenie 8

Uzupełnić szczegóły dowodu Faktu 1.7. Pokazać, że długość postaci normalnej może wzrosnąć wykładniczo w stosunku do rozmiaru formuły początkowej.

Ćwiczenie 9

Niech formuła Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\to\psi} będzie tautologią rachunku zdań. Znaleźć taką formułę $\vartheta$, że:

• Zarówno Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\to\vartheta} jak i $\vartheta \to \psi$ są tautologiami rachunku zdań.
• W formule $\vartheta$ występują tylko te zmienne zdaniowe, które występują zarówno w Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} jak i w $\psi$.

Ćwiczenie 10

Niech Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi(p)} będzie pewną formułą, w której występuje zmienna zdaniowa $p$ i niech $q$ będzie zmienną zdaniową niewystępującą w Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi(p)} . Przez Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi(q)} oznaczmy formułę powstałą z Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi(p)} przez zamianę wszystkich $p$ na $q$. Udowodnić, że jeśli

Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi(p), \var\varphi(q) \models p\leftrightarrow q}

to istnieje formuła $\psi$, nie zawierająca zmiennych $p$ ani $q$, taka że

Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi(p)\models p\leftrightarrow\psi} .