Spraw1 2015(1) .pdf

Grupa1 :
8–10 s.104
8–10 s.140
10–12 s.104

Numer indeksu:
Wersja:

A

000000

8–10 s.105

8–10 s.139

10–12 s.139

10–12 s.140

Logika dla informatyków
Sprawdzian nr 1, 20 listopada 2015
czas pisania: 30+60 minut
Zadanie 1 (2 punkty). Jeśli dla dowolnych formuł ϕ i ψ logiki pierwszego rzędu formuła
(∃x ϕ) ⇒ (∃x ψ) ⇒ ∀x (ϕ ⇒ ψ) jest tautologią to w prostokąt poniżej wpisz dowód tej tautologii w systemie naturalnej dedukcji. W przeciwnym przypadku wpisz odpowiedni kontrprzykład.

ϕ : x = 5,

Uniwersum: N,

ψ:x=7

Zadanie 2 (2 punkty). W prostokąt poniżej wpisz dwie formuły, odpowiednio w dysjunkcyjnej
i koniunkcyjnej postaci normalnej, mające następującą tabelkię zero-jedynkową.
p
T
T
T
T
F
F
F
F

q
T
T
F
F
T
T
F
F

CNF: (p ∨ q) ∧ (p ∨ r)

1

Proszę zakreślić właściwą grupę ćwiczeniową.

r
T
F
T
F
T
F
T
F

ϕ
T
T
T
T
T
F
F
F

DNF: p ∨ (q ∧ r)

Zadanie 3 (2 punkty). Jeśli zbiór klauzul {¬q ∨ p, s ∨ q, ¬r ∨ ¬p, ¬s ∨ q} jest sprzeczny, to
w prostokąt poniżej wpisz rezolucyjny dowód sprzeczności tego zbioru. W przeciwnym przypadku wpisz wartościowanie spełniające ten zbiór.

σ(p) = T, σ(q) = T, σ(r) = F, σ(s) = T

Zadanie 4 (2 punkty). Mówimy, że w algebrze zbiorów wyrażenie W jest uproszczeniem wyrażenia W 0 jeśli oba wyrażenia oznaczają ten sam zbiór, oba zawierają tylko zmienne, binarne
symbole ∪, ∩, \ i nawiasy, oraz W zawiera mniej symboli niż W 0 . Np. A ∪ B jest uproszczeniem
(A \ B) ∪ B. Jeśli istnieje uproszczenie wyrażenia A ∩ ((C ∪ B) \ B) to w prostokąt poniżej wpisz
dowolne takie uproszczenie. W przeciwnym przypadku wpisz słowo „NIE”.

A ∩ (C \ B)

Zadanie 5 (2 punkty). Jeśli formuły (p ⇔ q) ∧ r oraz (p ∧ q) ⇔ (p ∧ r) są równoważne to
w prostokąt poniżej wpisz słowo „RÓWNOWAŻNE”. W przeciwnym przypadku wpisz odpowiedni kontrprzykład.

Grupa1 :
8–10 s.104
8–10 s.140
10–12 s.104

Numer indeksu:
Wersja:

A

000000

8–10 s.105

8–10 s.139

10–12 s.139

10–12 s.140

Zadanie 6 (5 punktów). Które z poniższych zdań są prawdziwe dla wszystkich formuł ϕ i ψ
rachunku zdań?
1. Jeśli ϕ ⇒ ψ jest spełnialna oraz ¬ψ jest tautologią, to ¬ϕ jest spełnialna.
2. Jeśli ϕ ⇒ ψ jest spełnialna oraz ¬ψ jest tautologią, to ϕ jest spełnialna.
Podaj dowody ich prawdziwości. W pozostałych przypadkach wskaż kontrprzykłady.
Zadanie 7 (5 punktów). Udowodnij, że jeżeli dla pewnych zbiorów A i B zachodzi A \ B =
B \ A, to A = B.
Zadanie 8 (5 punktów). Rozważmy odwzorowanie T przyporządkowujące formułom zbudowanym ze zmiennych zdaniowych oraz spójnikow ∨, ∧, ¬ (i nawiasów) formuły zbudowane ze
zmiennych, spójników ⇒, ⊥ (i nawiasów) w następujący sposób.
T (p) = p,

dla wszystkich zmiennych p

T (ϕ1 ∨ ϕ2 ) = (T (ϕ1 ) ⇒ ⊥) ⇒ T (ϕ2 )
T (ϕ1 ∧ ϕ2 ) = (T (ϕ1 ) ⇒ (T (ϕ2 ) ⇒ ⊥)) ⇒ ⊥
T (¬ϕ) = T (ϕ) ⇒ ⊥
Udowodnij, że dla wszystkich formuł ϕ zbudowanych ze zmiennych zdaniowych oraz spójnikow
∨, ∧, ¬ (i nawiasów) formuły ϕ i T (ϕ) są równoważne.
Rozwiązanie. Przeprowadzimy dowód indukcyjny względem struktury formuły ϕ. Niech F
oznacza zbiór wszystkich formuł zbudowanych ze zmiennych zdaniowych oraz spójnikow ∨, ∧, ¬
(i nawiasów) i niech
X = {ϕ ∈ F | ϕ ≡ T (ϕ)}.
Musimy pokazać, że X zawiera zmienne zdaniowe (to jest podstawa indukcji) oraz że jest zamknięty na spójniki ∨, ∧, ¬ (krok indukcyjny).
Podstawa indukcji: Weźmy dowolną zmienną zdaniową p. Ponieważ T (p) = p, formuły
T (p) oraz p są równoważne, a stąd p ∈ X.
Krok indukcyjny: Weźmy dowolne formuły ϕ1 i ϕ2 i załóżmy, że ϕ1 , ϕ2 ∈ X (to jest
założenie indukcyjne). Pokażemy, że także ϕ1 ∨ ϕ2 , ϕ1 ∧ ϕ2 oraz ¬ϕ1 należą do zbioru X.
Z założenia indukcyjnego wiemy, że ϕ1 ≡ T (ϕ1 ) oraz ϕ2 ≡ T (ϕ2 ).
• T (ϕ1 ∨ ϕ2 ) = (T (ϕ1 ) ⇒ ⊥) ⇒ T (ϕ2 ), a zatem z założenia indukcyjnego jest to formuła
równoważna (ϕ1 ⇒ ⊥) ⇒ ϕ2 ). Korzystając z rownoważności p ⇒ q ≡ ¬p ∨ q otrzymujemy
równoważną formułę ¬(¬ϕ1 ∨ ⊥) ∨ ϕ2 , która uprasza się do ϕ1 ∨ ϕ2 . Zatem T (ϕ1 ∨ ϕ2 ) ≡
ϕ1 ∨ ϕ2 , co pokazuje że ϕ1 ∨ ϕ2 ∈ X.
• Przypadek ϕ1 ∧ ϕ2 jest podobny:
T (ϕ1 ∧ ϕ2 ) = (T (ϕ1 ) ⇒ (T (ϕ2 ) ⇒ ⊥)) ⇒ ⊥ ≡ (ϕ1 ⇒ (ϕ2 ⇒ ⊥)) ⇒ ⊥
≡ ¬(ϕ1 ⇒ (ϕ2 ⇒ ⊥)) ∨ ⊥ ≡ ϕ1 ∧ ¬(ϕ2 ⇒ ⊥) ≡ ϕ1 ∧ (ϕ2 ∧ ¬⊥) ≡ ϕ1 ∧ ϕ2 .
Zatem T (ϕ1 ∧ ϕ2 ) ≡ ϕ1 ∧ ϕ2 , co pokazuje, że ϕ1 ∧ ϕ2 ∈ X.
• T (¬ϕ1 ) = T (ϕ1 ) ⇒ ⊥ ≡ ϕ1 ⇒ ⊥ ≡ ¬ϕ1 ∨ ⊥ ≡ ¬ϕ1 . Zatem ¬ϕ1 ∈ X.
Na mocy zasady indukcji zbiór X zawiera wszystkie formuły z F, a to oznacza, że dla wszystkich
formuł ϕ zbudowanych ze zmiennych zdaniowych oraz spójnikow ∨, ∧, ¬ (i nawiasów) formuły
ϕ i T (ϕ) są równoważne.
1

Proszę zakreślić właściwą grupę ćwiczeniową.

Grupa1 :
8–10 s.104
8–10 s.140
10–12 s.104

Numer indeksu:
Wersja:

D

000000

8–10 s.105

8–10 s.139

10–12 s.139

10–12 s.140

Logika dla informatyków
Sprawdzian nr 1, 20 listopada 2015
czas pisania: 30+60 minut
Zadanie 1 (2 punkty). Jeśli dla dowolnych formuł ϕ i ψ logiki pierwszego rzędu formuła
(∃x ϕ ⇒ ψ) ⇒ (∃x ϕ) ⇒ ∃x ψ jest tautologią to w prostokąt poniżej wpisz dowód tej tautologii w systemie naturalnej dedukcji. W przeciwnym przypadku wpisz odpowiedni kontrprzykład.

Uniwersum: N,

ϕ : x = 5,

ψ:⊥

Zadanie 2 (2 punkty). Mówimy, że w algebrze zbiorów wyrażenie W jest uproszczeniem wyrażenia W 0 jeśli oba wyrażenia oznaczają ten sam zbiór, oba zawierają tylko zmienne, binarne
symbole ∪, ∩, \ i nawiasy, oraz W zawiera mniej symboli niż W 0 . Np. A \ B jest uproszczeniem
(A ∪ B) \ B. Jeśli istnieje uproszczenie wyrażenia (A ∩ (C \ B)) ∪ B to w prostokąt poniżej wpisz
dowolne takie uproszczenie. W przeciwnym przypadku wpisz słowo „NIE”.

(A ∩ C) ∪ B

1

Proszę zakreślić właściwą grupę ćwiczeniową.

Zadanie 3 (2 punkty). W prostokąt poniżej wpisz dwie formuły, odpowiednio w dysjunkcyjnej
i koniunkcyjnej postaci normalnej, mające następującą tabelkię zero-jedynkową.
p
T
T
T
T
F
F
F
F

q
T
T
F
F
T
T
F
F

CNF: (p ∨ q) ∧ (q ∨ r)

r
T
F
T
F
T
F
T
F

ϕ
T
T
T
F
T
T
F
F

DNF: q ∨ (p ∧ r)

Zadanie 4 (2 punkty). Jeśli zbiór klauzul {¬p ∨ q, ¬r ∨ s, ¬q ∨ ¬s, ¬p ∨ r} jest sprzeczny,
to w prostokąt poniżej wpisz rezolucyjny dowód sprzeczności tego zbioru. W przeciwnym przypadku wpisz wartościowanie spełniające ten zbiór.

Zadanie 5 (2 punkty). Jeśli formuły (p ⇔ q) ∨ r oraz (p ∨ q) ⇔ (p ∨ r) są równoważne to
w prostokąt poniżej wpisz słowo „RÓWNOWAŻNE”. W przeciwnym przypadku wpisz odpowiedni kontrprzykład.

Grupa1 :
8–10 s.104
8–10 s.140
10–12 s.104

Numer indeksu:
Wersja:

D

000000

8–10 s.105

8–10 s.139

10–12 s.139

10–12 s.140

Zadanie 6 (5 punktów). Rozważmy odwzorowanie T przyporządkowujące formułom zbudowanym ze zmiennych zdaniowych oraz spójnikow ∨, ∧, ¬ (i nawiasów) formuły zbudowane ze
zmiennych, spójników ⇒, ¬ (i nawiasów) w następujący sposób.
T (p) = p,

dla wszystkich zmiennych p

T (ϕ1 ∨ ϕ2 ) = ¬(T (ϕ1 )) ⇒ T (ϕ2 )
T (ϕ1 ∧ ϕ2 ) = ¬(T (ϕ1 ) ⇒ ¬(T (ϕ2 )))
T (¬ϕ) = ¬(T (ϕ))

Udowodnij, że dla wszystkich formuł ϕ zbudowanych ze zmiennych zdaniowych oraz spójnikow
∨, ∧, ¬ (i nawiasów) formuły ϕ i T (ϕ) są równoważne.
Rozwiązanie. Przeprowadzimy dowód indukcyjny względem głębokości formuły ϕ. Indukcja
względem struktury ϕ byłaby bardziej naturalna, ale chcemy pokazać, że można to zrobić inaczej
niż w wersji A.
Niech F oznacza zbiór wszystkich formuł zbudowanych ze zmiennych zdaniowych oraz spójnikow ∨, ∧, ¬ (i nawiasów) i niech
X = {n ∈ N | dla każdej formuly ϕ ∈ F o głębokości n, ϕ ≡ T (ϕ)}.
Podstawa indukcji: Weźmy dowolną formułę o głębokości 1. Jest to pewna zmienna zdaniowa p. Ponieważ T (p) = p, formuły T (p) oraz p są równoważne, a stąd 1 ∈ X.
Krok indukcyjny: Weźmy dowolne n ≥ 1 i załóżmy, że wszystkie liczby nie większe niż
n należą do X, czyli że dla wszystkich formuł ϕ o głębokości ≤ n formuły ϕ oraz T (ϕ) są
rownoważne (to jest założenie indukcyjne). Pokażemy, że także n+1 ∈ X, czyli że dla wszystkich
formuł ϕ o głębokości n+1 formuły ϕ oraz T (ϕ) są rownoważne. Weźmy zatem dowolną formułę
ϕ ∈ F o głębokości n + 1 i rozważmy następujące trzy przypadki.
ϕ = ϕ1 ∨ ϕ2 : Formuły ϕ1 oraz ϕ2 mają głębokość nie większą niż n, więc z założenia indukcyjnego ϕ1 ≡ T (ϕ1 ) oraz ϕ2 ≡ T (ϕ2 ). Wtedy T (ϕ1 ∨ ϕ2 ) = ¬(T (ϕ1 )) ⇒ T (ϕ2 ) ≡
¬ϕ1 ⇒ ϕ2 ≡ ϕ1 ∨ ϕ2 , a stąd ϕ ≡ T (ϕ).
ϕ = ϕ1 ∧ ϕ2 : Formuły ϕ1 oraz ϕ2 mają głębokość nie większą niż n, więc z założenia indukcyjnego ϕ1 ≡ T (ϕ1 ) oraz ϕ2 ≡ T (ϕ2 ). Wtedy T (ϕ1 ∧ ϕ2 ) = ¬(T (ϕ1 ) ⇒ ¬(T (ϕ2 ))) ≡
¬(ϕ1 ⇒ ¬ϕ2 ) ≡ ϕ1 ∧ ϕ2 , a stąd ϕ ≡ T (ϕ).
ϕ = ¬ϕ1 : Formuła ϕ1 ma głębokość nie większą niż n, więc z założenia indukcyjnego ϕ1 ≡
T (ϕ1 ). Wtedy T (¬ϕ1 ) = ¬(T (ϕ1 )) ≡ ¬ϕ1 , a stąd ϕ ≡ T (ϕ).
We wszystkich możliwych przypadkach pokazaliśmy, że ϕ ≡ T (ϕ), a z tego wynika że dla wszystkich formuł ϕ o głębokości n + 1 formuły ϕ oraz T (ϕ) są rownoważne, czyli n + 1 ∈ X.
Na mocy zasady indukcji zbiór X zawiera wszystkie liczby naturalne ≥ 1, a to oznacza, że
dla wszystkich formuł ϕ (o dowolnej głębokości) zbudowanych ze zmiennych zdaniowych oraz
spójnikow ∨, ∧, ¬ (i nawiasów) formuły ϕ i T (ϕ) są równoważne.
Zadanie 7 (5 punktów). Które z poniższych zdań są prawdziwe dla wszystkich formuł ϕ i ψ
rachunku zdań?
1. Jeśli ϕ ⇒ ψ jest tautologią oraz ¬ψ jest spełnialna, to ¬ϕ jest spełnialna.
1

Proszę zakreślić właściwą grupę ćwiczeniową.

2. Jeśli ϕ ⇒ ψ jest tautologią oraz ¬ψ jest spełnialna, to ϕ jest spełnialna.
Podaj dowody ich prawdziwości. W pozostałych przypadkach wskaż kontrprzykłady.
Zadanie 8 (5 punktów). Udowodnij, że jeżeli dla pewnych zbiorów A, B i C zachodzi A∩B =
A ∩ C oraz A ∪ B = A ∪ C, to B = C.