Lista 01 - logika - Zadania PDF

Preview

Summary

Zadania...

Description

Matematyka Dyskretna – Elektronika

20.02.2018

Lista 1. Logika. 1. Zgodnie z używanym obecnie kalendarzem gregoriańskim rok jest przestępny, jeśli dzieli się przez 4, lecz nie dzieli się przez 100, chyba, że dzieli się przez 400. Niech p oznacza zdanie „R jest rokiem podzielnym przez 4”, q – „rok R jest podzielny przez 100” i r – „rok R jest podzielny przez 400”. Zapisz za pomocą zdań p, q i r zdanie: „rok R jest przestępny”. 2. Spoś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)]. 3. Sprawdź za pomocą metody zero-jedynkowej, 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. 4. 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)]. 5. Zapisz formułę p =⇒ q, korzystając wyłącznie z: a) koniunkcji i negacji: b) alternatywy i negacji. 6. Korzystając wyłącznie z implikacji i negacji, zapisz formułę: a) p ∨ q; b) p ∧ q . 7. Za pomocą alternatywy, koniunkcji i negacji zapisz spójnik „albo” (inaczej alternatywa wykluczająca lub operator XOR). 8. Zbadaj, czy poniższe schematy wnioskowania są poprawne: p =⇒ (q ∨ r), ∼ r (p ∧ q) =⇒ r, ∼ q (∼ p) ∨ q, p . ; c) ; b) a) p =⇒ q p =⇒ r q p ∨ q, (∼ p) ∨ q p =⇒ q, p =⇒ (∼ q) (p ∨ q) =⇒ r, ∼ q d) . ; f) ; e) ∼p p =⇒ r q

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

9. 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. 10. 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ę? 11. Liczba naturalna dzieli się przez 10 wtedy i tylko wtedy, gdy dzieli się przez 2 i przez 5. Wywnioskuj stąd, że jeżeli n nie dzieli się przez 10, to n jest liczbą nieparzystą lub nie dzieli się przez 5. Wskaż prawa rachunku zdań, z których korzystasz. 12. Spójnik Pierce’a (inaczej operator NOR) jest zdefiniowany wzorem (p ⊥ q) ⇐⇒ ((∼ p) ∧ (∼ q)). Kreska Sheffera, (inaczej operator NAND) jest zdefiniowana wzorem p|q ⇐⇒ ((∼ p) ∨ ((∼ q)). Wyraź: a) alternatywę, implikację oraz równoważność za pomocą negacji oraz koniunkcji; b) koniunkcję, implikację oraz równoważność za pomocą negacji oraz alternatywy; c) negację, koniunkcję, alternatywę, implikację oraz równoważność za pomocą spójnika Pierce’a. d) negację, koniunkcję, alternatywę, implikację oraz równoważność za pomocą kreski Sheffera.

13. Przyjmijmy oznaczenia: N p to negacja p oraz Cpq, Apq, Kpq, Epq to odpowiednio implikacja, alternatywa, koniunkcja i równoważność zdań p i q. System ten (tzw. notacja polska) pozwala zapisywać formuły rachunku zdań bez użycia nawiasów. a) Zapisz w zwykłej notacji KC pN qp. b) Zapisz w notacji polskiej zasady sprzeczności, wyłączonego środka oraz prawa de Morgana. 14. 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óregokolwiek z tych oświadczeń wynika fałszywość dwóch pozostałych. 15. 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. 16. W języku arytmetyki liczb naturalnych (0, 1, 2, . . . , +, ·) zapisz: a) Liczba 10 jest parzysta. b) Liczba m jest mniejsza od n. c) Kwadrat dowolnej liczby parzystej jest liczbą parzystą. d) Liczba k dzieli liczbę m. e) Liczba p jest liczbą pierwszą. f) Liczba m jest liczbą złożoną. g) Równanie x3 + y3 = z 3 nie ma rozwiązań w liczbach dodatnich. √ h) Liczba 2 jest niewymierna. 17. W języku arytmetyki liczb naturalnym uzupełnionym o predykat Pr(p) ≡ „ p jest liczbą pierwszą” i symbol mniejszości zapisz: a) Każda liczba parzysta większa od 2 jest sumą dwóch liczb pierwszych. (hipoteza Goldbacha) b) Istnieje nieskończenie wiele liczb pierwszych. (Euklides) c) Istnieje nieskończenie wiele par liczb pierwszych bliźniaczych, tzn. takich, że p oraz p + 2 są pierwsze. (hipoteza) 18. Oznaczmy predykaty M (x) ≡ „ x jest mężczyzną”, D(x, y) ≡ „ x jest dzieckiem y”. Zapisz przy ich użyciu: a) x jest bratem y (rodzonym lub przyrodnim); b) x jest rodzonym bratem y; c) x jest córką y; d) x jest dziadkiem y; e) x jest kuzynką y; f) x ma dokładnie dwóch wnuków....