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 (\neg p\vee \neg s)\to (\neg p\vee \neg q)$;
2. $(p\to q)\vee (q\to r)$;
3. $((p\to q)\to r)\wedge \neg (((q\to r)\to r)\to r))$;
4. $(p\to q)\wedge (\neg p\to r)\to (r\to \neg q)$;
5. $((\neg p\to q)\to r)\to \neg (p\to q)$;
6. $p\vee (\neg p\wedge q)\vee (\neg p\wedge \neg q)$;
7. $(p\to q)\vee (p\to \neg q)$;
8. $q\vee r\to (p\vee q\to p\vee r)$;
9. $(p\vee q\vee r)\wedge (q\vee (\neg p\wedge s))\wedge (\neg s\vee q\vee r)\to q$.

Ćwiczenie 2

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

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

Ćwiczenie 3

Czy zachodzą następujące konsekwencje?

1. $p\wedge q\to \neg r,p\models r\to \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,\neg p\models r$;
5. $(p\to q)\to r,\neg r\models p$;
6. $p\to q,r\to \neg q\models r\to \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)\not =\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 \neg r)\vee (p\wedge \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 $\bot$ oraz zmienne zdaniowe ze zbioru $\{p_{1},\ldots ,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$.

• $[[\bot ]]v=\emptyset$ 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} .