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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 1: Linia 1:
 
{{Cwiczenie|1|cwicz_1|
 
{{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>;
 
#<math>(p\to q)\vee(q\to r)</math>;
 
#<math>(p\to q)\vee(q\to r)</math>;
Linia 31: Linia 31:
  
 
{{Cwiczenie|4|cwicz_4|
 
{{Cwiczenie|4|cwicz_4|
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> oraz każ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ą.
+
(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ą.
 
(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ą.
Linia 48: Linia 48:
 
<span id="udacczleka" \>
 
<span id="udacczleka" \>
 
{{Cwiczenie|6|cwicz_6|
 
{{Cwiczenie|6|cwicz_6|
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>.
Linia 63: Linia 63:
 
*<math>[[\var\varphi\wedge\psi ]]v=[[\var\varphi]]v \cap [[\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>.
 
*<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ń wtedy i tylko wtedy, 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>.
 
}}
 
}}
  
Linia 74: Linia 74:
 
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-->
 
}}
 
}}
Linia 83: Linia 83:
 
<math>\var\varphi(p), \var\varphi(q) \models p\leftrightarrow q</math>
 
<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  
+
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-->
 
<math>\var\varphi(p)\models p\leftrightarrow\psi</math>.<!--%% D. Niwinski-->
 
}}
 
}}

Wersja z 10:16, 1 paź 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 oraz każ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ń wtedy i tylko wtedy, 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} .