Diskret matematikk Oblig 5, høsten 2022 Innleveringsfrist: søndag 2. oktober, kl. 23.59 Leveres som én pdf-fil på Canvas. Oppgave 1 Bruk sannhetstabeller til å vise at De Morgans lover også gjelder...

How much would it cost to do =?


Diskret matematikk Oblig 5, høsten 2022 Innleveringsfrist: søndag 2. oktober, kl. 23.59 Leveres som én pdf-fil på Canvas. Oppgave 1 Bruk sannhetstabeller til å vise at De Morgans lover også gjelder for tre utsagn, dvs. at (p  q  r)  p  q  r Når vi benytter De Morgans lover ved regning med logiske uttrykk, er regelen altså at vi flytter negasjonstegnet inn i parentesen og bytter konjunksjon med disjunksjon og omvendt. Augustus De Morgan (1806 – 1871) var en britisk matematiker. Oppgave 2 Bruk sannhetstabeller til å avgjøre om følgende to utsagn er logisk ekvivalente: i) (? → ?) ∧ (? → ?) ii) (?  ?) → ? Oppgave 3 Bruk sannhetstabeller til å avgjøre om følgende utsagn er en tautologi: (? → ?)  (? → ?) Oppgave 4 Bruk sannhetstabeller til å avgjøre om følgende utsagn er en tautologi: (?  (?  ¬?)) ↔ ? Oppgave 5 Gitt et utsagn p → q. a) Angi det kontrapositive utsagnet. b) Vis ved hjelp av sannhetstabeller at utsagnet p → q er logisk ekvivalent med det kontrapositive utsagnet. 2 Oppgave 6 Hva blir de kontrapositive utsagnene til følgende utsagn? a) Hvis vinden løyer, så blir regattaen avlyst. b) Hvis flyet ikke blir forsinket, så rekker Ole både fotballkampen og et kinobesøk. c) Dersom Pernille har penger, så kan hun kjøpe en bok eller en ringperm. d) Safen kan åpnes bare hvis Kari har riktig nøkkel. Oppgave 7 Gitt følgende sammensatte logiske uttrykk:  )()( qrqqp → Bruk lovene i logikk gitt på det vedlagte arket, til å finne ut hvilket av følgende uttrykk dette er ekvivalent med: (i) q → p (ii)  p  q (iii) (q  p) Bruk kun en lov i hvert trinn og angi for hvert trinn nummeret på den loven du har brukt. Oppgave 8 Gitt følgende logiske utsagn: ))(( qpp  Benytt lovene i logikk gitt på det vedlagte arket til å finne hvilket av følgende utsagn dette er logisk ekvivalent med: (i) p  q (ii) p (iii) p  q (iv) p  q Bruk kun én lov i hvert trinn og angi for hvert trinn hvilken lov du bruker. Oppgave 9 Angi hvilken slutningsregel er brukt i hvert av følgende tilfeller. a) Hvis det regner, blir slalåmbakken stengt. Det regner. Følgelig blir slalåmbakken stengt. 3 b) Hvis sola skinner, så bader Anne. Anne bader ikke. Altså skinner ikke sola. c) Hvis Hans spiller tennis, så blir han sliten. Hvis Hans blir sliten, så drikker han vann. Følgelig: Hvis Hans spiller tennis, så drikker han vann. Oppgave 10 Undersøk om følgende slutninger er gyldige. a) Hvis Guri har kjøpt lottokupong, så vinner hun. Guri vinner. Følgelig har Guri kjøpt lottokupong. b) Hvis Guri har kjøpt lottokupong, så vinner hun. Guri vinner ikke. Altså har Guri ikke kjøpt lottokupong. 4 CFH, 11.09.14 Lover for logikk og mengder Lov Logikk Mengder 1. Assosiative lover )()( rqprqp  (A  B)  C = A  (B  C) )()( rqprqp  (A  B)  C = A  (B  C) 2. Kommutative lover pqqp  A  B = B  A pqqp  A  B = B  A 3.Distributive lover )()()( rpqprqp  A  (B  C) = (A  B)  (A  C) )()()( rpqprqp  A  (B  C) = (A  B)  (A  C) 4. De Morgans lover qpqp  )( BABA = qpqp  )( BABA = 5. Idempotenslover ppp  A  A = A ppp  A  A = A 6.Absorpsjonslover pqpp  )( A  (A  B) = A pqpp  )( A  (A  B) = A 7. Dobbel negasjon / Involusjonslov  ( p)  p AA = 8. Inverslover Spp  UAA = Fpp  = AA 9. Identitetslover pSp  AUA = pFp  AA = 10. Dominanslover FFp  A   =  SSp  A  U = U 11. Implikasjon qpqp → 12. Kontrapositive pqqp →→ utsagn Inklusjons- og eksklusjonsprinsippet |A  B  C| = |A| + |B| + |C| – | A  B| – |A  C| – |B  C| + |A  B  C|