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>
+
<span id=cwicz_1> Ćwiczenie 1 </span><br>
 
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 12: Linia 12:
  
  
<span id=cwicz_2> Ćwiczenie 2 </span>
+
<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 20: Linia 20:
  
  
<span id=cwicz_3> Ćwiczenie 3 </span>
+
<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>;

Wersja z 08:47, 21 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} .