Spraw1 2015 .pdf

File information


Original filename: Spraw1_2015.pdf

This PDF 1.5 document has been generated by TeX / pdfTeX-1.40.14, and has been sent on pdf-archive.com on 24/11/2015 at 21:16, from IP address 156.17.x.x. The current document download page has been viewed 449 times.
File size: 103 KB (6 pages).
Privacy: public file


Download original PDF file


Spraw1_2015.pdf (PDF, 103 KB)


Share on social networks



Link to this file download page



Document preview


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.

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

1

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


Related documents


spraw1 2015
regulamin rekrutacji do klasy pierwszej
11 demografia fakultet10 11
regulamin2017
2009 20 20tuc 20sem1 20kol 20calosc 20termin 201 20gr 20b
pieni dz i bankowo wersja b

Link to this page


Permanent link

Use the permanent link to the download page to share your document on Facebook, Twitter, LinkedIn, or directly with a contact by e-Mail, Messenger, Whatsapp, Line..

Short link

Use the short link to share your document on Twitter or by text message (SMS)

HTML Code

Copy the following HTML code to share your document on a Website or Blog

QR Code

QR Code link to PDF file Spraw1_2015.pdf