Tekst źródłowy strony Logika dla informatyków/Ćwiczenia 1

<span id=cwicz_1> Ćwiczenie 1 </span><br>
Zbadać, czy następujące formuły są tautologiami rachunku zdańi czy są spełnialne:
#<math>(p\to r)\wedge(q\to s)\wedge(\neg p\vee \neg s)\to (\neg p\vee \neg q)</math>;
#<math>(p\to q)\vee(q\to r)</math>;
#<math>((p\to q)\to r)\wedge\neg(((q\to r)\to r)\to r))</math>;
#<math>(p\to q)\wedge(\neg p\to r)\to (r\to\neg q)</math>;
#<math>((\neg p\to q)\to r)\to \neg(p\to q)</math>;
#<math>p\vee(\neg p\wedge q)\vee(\neg p\wedge\neg q)</math>;
#<math>(p\to q)\vee (p\to \neg q)</math>;
#<math>q\vee r\to (p\vee q\to p\vee r)</math>;
#<math>(p\vee q\vee r)\wedge(q\vee(\neg p\wedge s))\wedge (\neg s\vee q\vee r)\to q</math>.


<span id=cwicz_2> Ćwiczenie 2 </span><br>
Czy następujące zbiory formuł są spełnialne?
#<math>\{p\to \neg q, q\to \neg r, r\to \neg p\}</math>;
#<math>\{p\to q, q\to r, r\vee s\leftrightarrow \neg q\}</math>;
#<math>\{\neg(\neg q\vee p), p\vee\neg r, q\to\neg r\}</math>;
#<math>\{s\to q, p\vee\neg q, \neg(s\wedge p), s\}</math>.


<span id=cwicz_3> Ćwiczenie 3 </span><br>
Czy zachodzą następujące konsekwencje?
#<math>p\wedge q\to\neg r, p\models r\to \neg q</math>;
#<math>p\to q, p\to(q\to r)\models p\to r</math>;
#<math>p\to(q\to r), p\to q\models q\to r</math>;
#<math>(p\to q)\to r, \neg p\models r</math>;
#<math>(p\to q)\to r, \neg r\models p</math>;
#<math>p\to q, r\to \neg q\models r\to\neg p</math>.


<span id=cwicz_4> Ćwiczenie 4 </span><br>
Dla dowolnej formuły <math>\var\varphi</math> niech <math>\hat{\var\varphi}</math> oznacza dualizację formuły <math>\var\varphi</math>, tzn. formułę powstającą z <math>\var\varphi </math>przez zastąpienie każdego wystąpienia <math>\wedge</math> symbolem <math>\vee</math> orazkażdego wystąpienia <math>\vee</math> symbolem <math>\wedge</math>. 

(i) Dowieść,że  <math>\var\varphi</math> jest tautologią wtedy i tylko wtedy, gdy <math>\neg\hat{\var\varphi}</math>jest tautologią.

(ii)Dowieść, że <math>\var\varphi\leftrightarrow\psi</math> jest tautologią wtedy i tylko wtedy, gdy <math>\hat{\var\varphi}\leftrightarrow\hat{\psi}</math> jest tautologią.


<span id=cwicz_5> Ćwiczenie 5 </span><br>
Znależć formułę zdaniową&nbsp;<math>\var\varphi</math>, która jest spełniona dokładnie przy wartościowaniach&nbsp;<math>\varrho</math> spełniających warunki:

#Dokładnie dwie spośród wartości <math>\varrho(p)</math>, <math>\varrho(q)</math> i <math>\varrho(r)</math> są równe&nbsp;1.
#<math>\varrho(p) = \varrho(q) \not= \varrho(r)</math>.

''Rozwiązanie:'' Można to robić na różne sposoby, ale najprościej po prostu wypisać alternatywę koniunkcji, np. <math>(p\wedge q\wedge \neg r)\vee(p \wedge\neg q \wedge r)</math>. 


<span id=cwicz_6> Ćwiczenie 6 </span><br>
<span id="udacczleka" \> Udowodnić, że dla dowolnej funkcji <math>f:\{0,1\}^k\to\{0,1\}</math>istnieje formuła&nbsp;<math>\var\varphi</math>, w której występują tylko spójniki <math>\to</math> i <math>\bot</math>oraz zmienne zdaniowe ze zbioru <math>\{p_1,\ldots, p_k\}</math>, o tej własności, że dla dowolnego wartościowania zdaniowego&nbsp;<math>\varrho</math> zachodzi równość<math>[[\var\varphi]]\varrho = f(\varrho(p_1),\ldots, \varrho(p_k))</math>. (Inaczej mówiąc, formuła&nbsp;<math>\var\varphi</math> definiuje funkcję zerojedynkową&nbsp;<math>f</math>.) 

''Wskazówka:'' Indukcja ze względu na&nbsp;<math>k</math>.


<span id=cwicz_1> Ćwiczenie 7 </span><br>
<span id="krecic">&nbsp;</span> Niech <math>X</math> będzie dowolnym zbiorem niepustym. Dowolną funkcję <math>v:\mbox{\small ZZ}\to\pot X</math> nazwijmy ''wartościowaniem'' w&nbsp;zbiorze <math>\pot X</math>. Każdej formule zdaniowej&nbsp;<math>\var\varphi</math> przypiszemy teraz pewien podzbiór <math>[[\var\varphi]]\warpi</math> zbioru&nbsp;<math>X</math>, który nazwiemy jej ''wartością'' przy wartościowaniu&nbsp;<math>v</math>.

*<math>[[\bot]]v=\emptyset</math> oraz <math>[[top]]v=X</math>;
*<math>[[p]]v=v(p)</math>, gdy <math>p</math> jest symbolem zdaniowym;
*<math>[[\neg\var\varphi]]v= X-[[{\var\varphi]]v</math>;
*<math>[[\var\varphi\vee\psi ]]v=[[\var\varphi]]v \cup [[\psi]]v</math>;
*<math>[[\var\varphi\wedge\psi ]]v=[[\var\varphi]]v \cap [[\psi]]v</math>;
*<math>[[\var\varphi\to\psi]]v= (X-[[\var\varphi]]v) \cup[[\psi]]v</math>.
Udowodnić, że formuła <math>\var\varphi</math> jest tautologią rachunku zdań \wtw, gdy jest ''prawdziwa'' w&nbsp;<math>\pot X</math>, tj.&nbsp;gdy dla dowolnego <math>v</math>jej wartością jest cały zbiór&nbsp;<math>X</math>.


<span id=cwicz_8> Ćwiczenie 8 </span><br>
<span id="wziawszy" \> Uzupełnić szczegóły dowodu&nbsp;[[Logika dla informatyków/Rachunek zdań#fakt17|Faktu 1.7]].Pokazać, że długość postaci normalnej może wzrosnąć wykładniczo w stosunku do rozmiaru formuły początkowej.


<span id=cwicz_9> Ćwiczenie 9 </span><br>
Niech formuła <math>\var\varphi\to\psi</math> będzie tautologią rachunku zdań. Znaleźć taką formułę&nbsp;<math>\vartheta</math>, że:
*Zarówno <math>\var\varphi\to\vartheta</math> jak i <math>\vartheta\to\psi</math> są tautologiami rachunku zdań.
*W formule&nbsp;<math>\vartheta</math> występują tylko te zmienne zdaniowe,które występują zarówno w&nbsp;<math>\var\varphi</math> jak i&nbsp;w&nbsp;<math>\psi</math>.
<!--%% D. Niwinski-->


<span id=cwicz_10> Ćwiczenie 10 </span><br>
Niech <math>\var\varphi(p)</math> będzie pewną formułą, w której występuje zmienna zdaniowa&nbsp;<math>p</math> i niech <math>q</math> będzie zmienną zdaniową niewystępującą w&nbsp;<math>\var\varphi(p)</math>. Przez&nbsp;<math>\var\varphi(q)</math> oznaczmy formułę powstałą z&nbsp;<math>\var\varphi(p)</math> przez zamianę wszystkich&nbsp;<math>p</math> na&nbsp;<math>q</math>. Udowodnić, że jeśli

<math>\var\varphi(p), \var\varphi(q) \models p\leftrightarrow q</math>

to istnieje formuła&nbsp;<math>\psi</math>, nie zawierająca zmiennych&nbsp;<math>p</math> ani&nbsp;<math>q</math>,taka że 

<math>\var\varphi(p)\models p\leftrightarrow\psi</math>.<!--%% D. Niwinski-->