Logika dla informatyków/Ćwiczenia 1: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 1: Linia 1:
<span id=cwicz_1> Ćwiczenie 1 </span><br>
+
{{Cwiczenie|1|cwicz_1|
 
Zbadać, czy następujące formuły są tautologiami rachunku zdańi czy są spełnialne:
 
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 r)\wedge(q\to s)\wedge(\neg p\vee \neg s)\to (\neg p\vee \neg q)</math>;
Linia 10: Linia 10:
 
#<math>q\vee r\to (p\vee q\to p\vee r)</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>.
 
#<math>(p\vee q\vee r)\wedge(q\vee(\neg p\wedge s))\wedge (\neg s\vee q\vee r)\to q</math>.
 +
}}
  
 
+
{{Cwiczenie|2|cwicz_2|
<span id=cwicz_2> Ćwiczenie 2 </span><br>
 
 
Czy następujące zbiory formuł są spełnialne?
 
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 \neg q, q\to \neg r, r\to \neg p\}</math>;
Linia 18: Linia 18:
 
#<math>\{\neg(\neg q\vee p), p\vee\neg r, q\to\neg r\}</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>.
 
#<math>\{s\to q, p\vee\neg q, \neg(s\wedge p), s\}</math>.
 +
}}
  
 
+
{{Cwiczenie|3|cwicz_3|
<span id=cwicz_3> Ćwiczenie 3 </span><br>
 
 
Czy zachodzą następujące konsekwencje?
 
Czy zachodzą następujące konsekwencje?
 
#<math>p\wedge q\to\neg r, p\models r\to \neg q</math>;
 
#<math>p\wedge q\to\neg r, p\models r\to \neg q</math>;
Linia 28: Linia 28:
 
#<math>(p\to q)\to r, \neg r\models p</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>.
 
#<math>p\to q, r\to \neg q\models r\to\neg p</math>.
 +
}}
  
 
+
{{Cwiczenie|4|cwicz_4|
<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>.  
 
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>.  
  
Linia 36: Linia 36:
  
 
(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ą.
 
(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ą.
 +
}}
  
 
+
{{Cwiczenie|5|cwicz_5|
<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:
 
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:
  
Linia 45: Linia 45:
  
 
''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>.  
 
''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="udacczleka" \>
<span id=cwicz_6> Ćwiczenie 6 </span><br>
+
{{Cwiczenie|6|cwicz_6|
<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>.)  
+
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>.
 
''Wskazówka:'' Indukcja ze względu na&nbsp;<math>k</math>.
 +
}}
  
 
+
<span id="krecic">&nbsp;</span>
<span id=cwicz_1> Ćwiczenie 7 </span><br>
+
{{Cwiczenie|7|cwicz_7|
<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>.
+
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>[[\bot]]v=\emptyset</math> oraz <math>[[top]]v=X</math>;
Linia 63: Linia 64:
 
*<math>[[\var\varphi\to\psi]]v= (X-[[\var\varphi]]v) \cup[[\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>.
 
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="wziawszy" \>
 +
{{Cwiczenie|8|cwicz_8|
 +
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_8> Ćwiczenie 8 </span><br>
+
{{Cwiczenie|9|cwicz_9|
<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:
 
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ń.
 
*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>.
 
*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-->
 
<!--%% D. Niwinski-->
 +
}}
  
 
+
{{Cwiczenie|10|cwicz_10|
<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
 
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
  
Linia 84: Linia 86:
  
 
<math>\var\varphi(p)\models p\leftrightarrow\psi</math>.<!--%% D. Niwinski-->
 
<math>\var\varphi(p)\models p\leftrightarrow\psi</math>.<!--%% D. Niwinski-->
 +
}}

Wersja z 09:21, 29 wrz 2006

Ćwiczenie 1

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

  1. ;
  2. ;
  3. ;
  4. ;
  5. ;
  6. ;
  7. ;
  8. ;
  9. .

Ćwiczenie 2

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

  1. ;
  2. ;
  3. ;
  4. .

Ćwiczenie 3

Czy zachodzą następujące konsekwencje?

  1. ;
  2. ;
  3. ;
  4. ;
  5. ;
  6. .

Ć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 symbolem orazkażdego wystąpienia symbolem .

(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  spełniających warunki:

  1. Dokładnie dwie spośród wartości , i są równe 1.
  2. .

Rozwiązanie: Można to robić na różne sposoby, ale najprościej po prostu wypisać alternatywę koniunkcji, np. .

Ćwiczenie 6

Udowodnić, że dla dowolnej funkcji istnieje formuła Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} , w której występują tylko spójniki i oraz zmienne zdaniowe ze zbioru , o tej własności, że dla dowolnego wartościowania zdaniowego  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ą .)

Wskazówka: Indukcja ze względu na .

 

Ćwiczenie 7

Niech będzie dowolnym zbiorem niepustym. Dowolną funkcję Parser nie mógł rozpoznać (błąd składni): {\displaystyle v:\mbox{\small ZZ}\to\pot X} nazwijmy wartościowaniem w zbiorze Parser nie mógł rozpoznać (nieznana funkcja „\pot”): {\displaystyle \pot 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 , który nazwiemy jej wartością przy wartościowaniu .

  • oraz ;
  • , gdy 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ń \wtw, gdy jest prawdziwaParser nie mógł rozpoznać (nieznana funkcja „\pot”): {\displaystyle \pot X} , tj. gdy dla dowolnego jej wartością jest cały zbiór .

Ć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łę , że:

  • Zarówno Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\to\vartheta} jak i są tautologiami rachunku zdań.
  • W formule  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 .

Ć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  i niech 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  na . 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 , nie zawierająca zmiennych  ani ,taka że

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