Matematyka Dyskretna – Elektronika

25.02.2014

Lista 1. Logika.

1. Które z podanych implikacji są prawdziwe dla dowolnej liczby naturalnej n?

a) Jeżeli n jest liczbą parzystą, to n + 1 jest liczbą nieparzystą.

b) Jeżeli n jest liczbą pierwszą, to n + 1 jest liczbą złożoną.

c) Jeżeli n dzieli się przez 3, to suma cyfr liczby 3n dzieli się przez 9.

d) Jeżeli n nie dzieli się przez 10, to n jest liczbą nieparzystą lub nie dzieli się przez 5.

2. Wiedząc, że implikacja (∼ p) =⇒ q jest fałszywa, określ wartość logiczną:

a) koniunkcji zdań p oraz q;

b) alternatywy zdań p oraz q;

c) implikacji q =⇒ p.

3. Przyjmijmy, że gdy Jacek chrapie, to Agata śni. Które z poniższych zdań są prawdziwe przy tym założeniu?

a) Gdy Agata nie śni, to Jacek nie chrapie.

b) Gdy Jacek nie chrapie, to Agata nie śni.

c) Gdy Agatka śni, to Jacek chrapie.

d) Jacek nie chrapie lub Agatka śni.

e) Nie jest możliwe, aby Jacek chrapał, a Agatka nie śniła.

4. George Bernard Shaw twierdził, że przekłady są jak kochanki – wierne nie są piękne, piękne nie są wierne.

Które z poniższych zdań są równoważnym sformułowaniem poglądu, że przekład nie może być zarazem wierny
i piękny.

a) Jeżeli przekład jest wierny, to nie jest piękny.

b) Jeżeli przekład jest piękny, to nie jest wierny.

c) Jeżeli przekład nie jest wierny, to jest piękny.

d) Jeżeli przekład nie jest piękny, to jest wierny.

5. Każda karta z jednej strony jest czerwona albo niebieska, z drugiej zaś ma narysowane kółko albo trójkąt. Na

stole widzimy cztery takie karty, widoczna strona jest w nich kolejno czerwona, niebieska, trójkątem i kółkiem.
Jacek twierdzi, że karty niebieskie mają na odwrocie kółko. Które karty Placek musi odwrócić, aby sprawdzić,
czy Jacek mówi prawdę?

6. Pośród podanych formuł rachunku zdań wskaż tautologie, formuły spełnialne i formuły sprzeczne.

a) p =⇒ (∼ p =⇒ q);

c) ∼ [p =⇒ (∼ p =⇒ q)];

b) ∼ (p ∨ q) ⇐⇒ [∼ p∨ ∼ q];

d) [(p ∨ q) =⇒ r] =⇒ [(p =⇒ r) ∨ (q =⇒ r)].

7. Sprawdź za pomocą metody zerojedynkowej, czy poniższe pary wyrażeń są równoważne.

a) p =⇒ q oraz (∼ p) ∨ q;

b) ∼ (p ∧ q) oraz p =⇒ q;

c) p =⇒ (p =⇒ q) oraz p =⇒ q.

8. Wykaż, że poniższe formuły rachunku zdań są tautologiami:

a) p =⇒ (∼ p =⇒ q);

c) [p =⇒ (q ∧ r)] =⇒ [(∼ q∨ ∼ r) =⇒∼ p];

b) [∼ p ∧ (p ∨ q)] =⇒ q;

d) [(p ∨ q) =⇒ r)] =⇒ [(∼ p =⇒ (q =⇒ r)].

9. Zapisz formułę p =⇒ q, korzystając wyłącznie z: a) koniunkcji i negacji: b) alternatywy i negacji.

10. Zbadaj, czy poniższe schematy wnioskowania są poprawne:

a)

(∼ p) ∨ q, p

q

;

b)

(p ∧ q) =⇒ r, ∼ q

p =⇒ r

;

c)

p =⇒ (q ∨ r), ∼ r

p =⇒ q

.

11. W czasie kampanii wyborczej panowie Alfa, Beta i Gamma złożyli następujące oświadczenia:

Alfa: Beta zawsze kłamie.
Beta: Gamma zawsze kłamie.
Gamma: Alfa zawsze kłamie.

Uzasadnij, że przynajmniej dwa z tych oświadczeń są fałszywe. Wskazówka: Pokaż, że z prawdziwości które-
gokolwiek z tych oświadczeń wynika fałszywość dwóch pozostałych.

12U. W czasie kampanii wyborczej panowie Alfa, Beta, Gamma i Delta złożyli następujące oświadczenia:

Alfa: Beta zawsze kłamie.
Beta: Gamma przynajmniej czasem mówi prawdę.
Gamma: Delta przynajmniej czasem kłamie.
Delta: Alfa zawsze mówi prawdę.

Wykaż, że dokładnie dwa z tych zdań są prawdziwe.