Informatyka MIMUW

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 3
Udowodnij, że dla każdej formuły $\varphi$ logiki zdaniowej w postaci CNF istnieje formuła $\psi$ logiki zdaniowej w postaci 3-CNF taka, że $\psi$ jest spełnialna wtedy i tylko wtedy, gdy $\varphi$ jest spełnialna.

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$