Klasyczna logika zdaniowa
Formuła logiki zdaniowej jest w postaci CNF (Conjunctive Normal Form) gdy jest koniunkcją (być może wielu) alternatyw (być może wielu) zmiennych zdaniowych i zanegowanych zmiennych zdaniowych. Na przykład formuła \((p_1\lor\lnot p_2\lor p_3)\land(p_2\lor p_4\lor \lnot p_5)\land(\lnot p_1\lor p_2)\) jest postaci CNF.
Formuła logiki zdaniowej jest w postaci \(k\)-CNF gdy jest w postaci CNF i żadna z alternatyw w niej występujących nie ma więcej niż \(k\) składników. Formuła z poprzedniego przykładu jest w postaci 3-CNF, ale nie 2-CNF.
Formuła logiki zdaniowej jest w postaci DNF (Disjunctive Normal Form) gdy jest alternatywą (być może wielu) koniunkcji (być może wielu) zmiennych zdaniowych i zanegowanych zmiennych zdaniowych.
Zadanie 1
Udowodnij, że dla każdej formuły \(\varphi\) logiki zdaniowej istnieje formuła \(\psi\) logiki zdaniowej w postaci DNF równoważna \(\varphi\), czyli taka, że tautologią jest formuła \(\varphi\leftrightarrow\psi.\)
Zadanie 2
Udowodnij, że dla każdej formuły \(\varphi\) logiki zdaniowej istnieje formuła \(\psi\) logiki zdaniowej w postaci CNF równoważna \(\varphi\), czyli taka, że tautologią jest formuła \(\varphi\leftrightarrow\psi.\)
Zadanie 4
Podaj wielomianowy algorytm rozwiązujący następujący problem decyzyjny:
Dane: Formuła \(\varphi\) logiki zdaniowej w postaci DNF.
Pytanie: Czy \(\varphi\) jest spełnialna?
Zadanie 5
Podaj wielomianowy algorytm rozwiązujący następujący problem decyzyjny:
Dane: Formuła \(\varphi\) logiki zdaniowej w postaci 2-CNF.
Pytanie: Czy \(\varphi\) jest spełnialna?
Zadanie 6
Zajmujemy się formułami zapisanymi wyłącznie przy użyciu spójników koniunkcji i alternatywy.
Dla dowolnej takiej formuły \(\varphi\) niech \(\hat{\varphi}\) oznacza dualizację formuły \(\varphi\), tzn. formułę powstającą z \(\varphi \) przez zastąpienie każdego wystąpienia \(\wedge\) symbolem \(\vee\) oraz każdego wystąpienia \(\vee\) symbolem \(\wedge\).
* Dowieść, że \(\varphi\) jest tautologią wtw, gdy \(\lnot\hat{\varphi}\) jest tautologią.
* Dowieść, że \(\varphi\leftrightarrow\psi\) jest tautologią wtw, gdy \(\hat{\varphi}\leftrightarrow\hat{\psi}\) jest tautologią.
* Jak należałoby określić dualizację dla formuł zawierających dodatkowo stałe \(\bot\) i \(\top\), żeby powyższe równowaźności nadal zachodziły?
Zadanie 7
Udowodnić, że dla dowolnej funkcji \(f:\{0,1\}^k\to\{0,1\}\) istnieje formuła \(\varphi\), w której występują tylko spójniki \(\to\) i \(\bot\) oraz zmienne zdaniowe ze zbioru \(\{p_1,\ldots, p_k\}\), o tej własności, że dla dowolnego wartościowania zdaniowego \(\varrho\) zachodzi równość
\([[\varphi]]_\varrho = f(\varrho(p_1),\ldots, \varrho(p_k))\).
(Inaczej mówiąc, formuła \(\varphi\) definiuje funkcję zerojedynkową \(f\).)
Zadanie 8
Dany jest nieskończony zbiór chłopców, z których każdy ma skończoną liczbę narzeczonych. Ponadto dla każdego \(k\in N\), dowolnych \(k\) chłopców ma co najmniej \(k\) narzeczonych. Dowieść, że każdy chłopiec może się ożenić z jedną ze swoich narzeczonych bez popełnienia bigamii.
Zadanie 9
Niech \(k\) będzie ustaloną liczbą naturalną. Udowodnij, korzystając z twierdzenia o zwartości, że jeśli w nieskończonym grafie \(G=\langle V,E\rangle\) jego każdy skończony podgraf jest \(k\) -kolorowalny, to sam graf \(G\) tek jest \(k\)-kolorowalny.
Zadanie 10
Dla formuły \(\gamma =\ r\leftrightarrow (p_1\lor p_2)\) zachodzi równoważność: \(\varrho\models\gamma\) wtedy i tylko wtedy, gdy \(\varrho(r)=\max(\varrho(p_1),\varrho(p_2))\).
Zbadać istnienie zbioru formuł \(\Gamma\) takiego, że \(\varrho\models\Gamma\) wtedy i tylko wtedy, gdy \(\varrho(r)=\max_{n\in\mathbb{N}}(\varrho(p_n))\).
Zadanie 11
Czy sekwent \(\{p,q\to p,\lnot q\}\vdash\{p,q\}\) jest dowodliwy w systemie Gentzena dla logiki zdaniowej?
Zadanie 12
Rozstrzygnij, czy następujące formuły mają dowód w systemie Gentzena dla logiki zdaniowej:
* \( (p\to q) \lor (q\to p)\)
* \((p\to ( q \to p)) \to p\)
Zadanie 13
W systemie Gentzena sekwent \(\Gamma,p\vdash\Delta,p\) jest aksjomatem. \(p\) oznacza zmienną zdaniową. Udowodnij, że każdy sekwent postaci
\(\Gamma,\varphi\vdash\Delta,\varphi\) jest wyprowadzalny w systemie Gentzena. Comożna powiedzieć o rozmiarze jego dowodu?
Trójwartościowe logiki zdaniowe
Zadanie 14
Logikę \(L\) nazywamy monotoniczną, jeśli z tego, że \(\Delta\models\varphi\) oraz \(\Gamma\supseteq\Delta\) wynika, że \(\Gamma\models\varphi.\)
Dla logiki trójwartościowej Sobocińskiego określamy, że \(\Delta\models\varphi\), gdy dla każdego wartościowania zmiennych zdaniowych wartościami ze zbioru \(\{0,\frac12,1\}\), jeśli wartości wszystkich zdań z \(\Delta\) wynoszą 1, to także wartość \(\varphi\) wynosi 1.
Czy logika trójwartościowa Sobocińskiego jest monotoniczna?
Zadanie 15
Odpowiedz na analogiczne pytanie co w zadaniu 13 dla logik Heytinga-Kleeene'go-Łukasiewicza, Bochvara i logiki leniwego (krótkiego) wyliczenia w Pascalu.
Zadanie 16
Jaka jest złożoność następującego problemu decyzyjnego:
Dane: Formuła \(\varphi\) logiki zdaniowej.
Pytanie: Czy istnieje wartościowanie \(\varrho\) zmiennych zdaniowych w zbiór \(\{0,\frac12,1\}\) takie, że w logice trójwartościowej Bochvara zachodzi \([[\varphi]]_\varrho=1\)?
Intuicjonistyczna logika zdaniowa
Zadanie 17
Udowodnij następujące formuły w systemie Naturalnej Dedukcji dla logiki intucjonistycznej
* \(p \to \neg \neg p\)
* \(\neg (p \lor q) \to\neg p \land\neg q\)
* \(\neg p \land\neg q \to\neg (p \lor q)\)
* \(\neg p \lor\neg q \to\neg (p \land q)\)
Zadanie 18
Udowodnij, że następujące formuły nie są tautologiami intucjonistycznej logiki zdaniowej, używając modeli Kripkego:
* \(((p\to q) \to p) \to p\)
* \(\neg (p \land q) \to (\neg p \lor\neg q)\)
Zadanie 19
Niewyrażalność spójników w zdaniowej logice intuicjonistycznej: pokaż, że
* \(\lor\) nie da się wyrazić za pomocą \(\land\), \(\to\) i \(\bot\)
* \(\land\) nie da się wyrazić za pomocą \(\lor\), \(\to\) i \(\bot\)
* \(\to\) nie da się wyrazić za pomocą \(\lor\), \(\land\) i \(\bot\)