LOGIKA 2
Tautologie, równoważność logiczna formul, postać normalna
Zad.1 W jakich sytuacjach poniższe zdania sa falszywe ?
a) Nie lubie szpinaku.
b) Prosta jest analiza, prosta jest algebra.
c) Mam psa lub kota.
d) Jeżeli sie uczyleś systematycznie, zdasz egzamin.
Zad.2 Kiedy formula Ź(p '" q) "! (Źp (" Źq) jest prawdziwa, a kiedy falszywa ? Zbuduj dla niej matryce
logiczna .
Zad.3 Jeżeli Jan nie jest kosmita , to, jeśli Jan jest kosmita , to nie pije i nie pali.
Czy powyższe zdanie jest prawdziwe ?
Zad.4 Czy poniższe formuly sa tautologiami ?
(a) (p q) (Źp Źq)
(b) p1 (p2 (p3 (p4 (p5 (" Źp5))))
Zad.5 Czy zdania b) i c) mówia to samo, co a) ?
a) Jeśli niedz
wiedzie sa szlaku, siedzimy w schronisku.
b) Jeśli niedz
wiedzi nie ma na szlaku, nie siedzimy w schronisku.
c) Jeśli nie siedzimy w schronisku, niedz
wiedzi nie ma na szlaku.
Zad.6 Uzasadnij, że formuly p q i Źp Źq nie sa logicznie równoważne.
Zad.7 Jak zdefiniować implikacje za pomoca '", (", Ź ?
Zad.8 Jak zdefiniować alternatywe wykluczaja ca •" (XOR), czyli ,,dokladnie jedno z dwojga , za pomoca
pomoca '", (", Ź (nie trzeba używać wszystkich) ?
Zad.9 Oznaczmy przez (NAND) negacje koniunkcji (tzn. p q jest falszywe wyla cznie wtedy, gdy oba
zdania sa prawdziwe). Zdefiniuj za pomoca funktory: Ź, '".
Zad.10 Bramki logiczne. Przedstaw poprzednie rozwia zanie za pomoca bramek logicznych. Narysuj uklad
logiczny odpowiadaja cy formule Ź(Ź(p (" q) '" p). Zredukuj liczbe bramek.
Zad.11 Sprowadz
formuly do postaci normalnej koniunkcyjnej.
(1) p '" q (2)p (" q (3)p q
(4) p "! q (5)Ź(p '" q) (6)Ź(p (" q)
(7) Ź(p q) (8)Ź(p "! q) (9)(Źp Źq) (q p)
Zad.12 Sprawdzić, czy ostatnia formula z zadania poprzedniego jest tautologia , wykorzystuja c jej postać
normalna .
ZD1. Oceń prawdziwość zdania: Wszyscy studenci lubia matematyke wtedy i tylko wtedy, gdy nie jest
prawda , że to nieprawda, że wszyscy studenci lubia matematyke.
ZD2. Czy formula p1 (p2 (p3 (p4 (p5 (p6 p1))))) jest tautologia ?
ZD3. Czy oba zdania mówia to samo ? Prosze spróbować ocenić to ,,zdroworozsa dkowo , a potem
korzystaja c ze schematów logicznych tych zdań.
(1) a) Jeśli siedzimy w schronisku, niedz
wiedzie sa na szlaku.
b) Niedz
wiedzie sa na szlaku lub nie siedzimy w schronisku.
(2) a) To nieprawda, że jeżeli siedzimy w schronisku, to niedz
wiedzie sa na szlaku.
b) Jeżeli siedzimy w schronisku, to niedz
wiedzi nie ma na szlaku.
ZD4. Oceń ,,zdroworozsa dkowo , czy zdania a) i b) mówia to samo. Czy sa logicznie równoważne ?
a) Gdy czlowiek ma prawo jazdy, jest pelnoletni.
b) Czlowiek ma prawo jazdy lub nie jest pelnoletni.
ZD5. Zdefiniuj równoważność za pomoca implikacji (można też używa ć '", (", Ź) i sprawdz
poprawność
tej definicji buduja c matryce logiczne.
ZD6.
(a) Zdefiniuj (NAND) za pomoca i Ź.
(b) Zdefiniuj za pomoca funktory: (", , "!.
1
2
ZD7. Zbuduj obwody logiczne równoważne bramkom AND, OR oraz NOT, wykorzystuja c jedynie bramki
NOR.
ZD8. Oto pewien obwód logiczny.
p
?
q
1. Znajdz
formule logiczna odpowiadaja ca temu obwodowi.
2. Znajdz
prostszy obwód, który te sama funkcje realizuje przy pomocy mniejszej liczby bramek.
ZD9. Niech p oznacza ,,komputer jest sprawny , q  ,,komputer jest zaatakowany przez wirusa . Zalóżmy,
że zdażyla sie sytuacja opisana zdaniem
Ź(p (" (Źp '" q)).
Za pomoca sprowadzenia formuly do postaci normalnej, prosze powiedzieć o jaka sytuacje chodzi.
ZD10. Sprawdz
, czy formula jest tautologia wszystkimi znanymi sposobami (metoda zero-jedynkowa ,
skrócona metoda zero-jedynkowa , przez sprowadzenie do postaci normalnej, może jeszcze inna ).
Ź(Ź(Ź(Źp q) q '" r) p (" Źq)
Przy sprowadzaniu do postaci normalnej prosze popróbować różnej kolejności, tzn. zacza c od najbardziej
zewne trzej formuly lub od najbardziej wewnetrznych i ocenić, który sposób jest lepszy.
ZD11. Zadanie rozluz
niaja ce: La dujemy na wyspie LiR, na rozstaju dróg. Jedna z dróg prowadzi do
dobrych i wesolych ludzi, a druga  do smutnych kanibali. Spotykamy dwóch mieszkańców wyspy (po
których wygla dzie nie możemy poznać kim sa ). Mieszkańcy zawsze odpowiadaja na pytania tylko ,,tak
lub ,,nie . Możemy zadać tylko jedno pytanie (tylko jednemu z nich). Jak sie dowiedzieć, która droga jest
dobra ?