Logika dla informatyków/Ćwiczenia 1

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ć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} .