MAT1030 – Diskret matematikk Plenumsregning 6: Ukeoppgaver fra kapittel 5 Roger Antonsen

Fulltekst

(1)MAT1030 – Diskret matematikk Plenumsregning 6: Ukeoppgaver fra kapittel 5. Roger Antonsen Matematisk Institutt, Universitetet i Oslo. 21. februar 2008.

(2) Oppgave 5.1 Skriv følgende mengder på listeform.. MAT1030 – Diskret matematikk. 21. februar 2008. 2.

(3) Oppgave 5.1 Skriv følgende mengder på listeform. (a) Mengden av alle vokaler. MAT1030 – Diskret matematikk. 21. februar 2008. 2.

(4) Oppgave 5.1 Skriv følgende mengder på listeform. (a) Mengden av alle vokaler (b) {x ∈ N : 10 ≤ x ≤ 20 og x er delbar med 3}. MAT1030 – Diskret matematikk. 21. februar 2008. 2.

(5) Oppgave 5.1 Skriv følgende mengder på listeform. (a) Mengden av alle vokaler (b) {x ∈ N : 10 ≤ x ≤ 20 og x er delbar med 3} (c) Mengden av alle naturlige tall som gir en rest på 1 når de deles på 5.. MAT1030 – Diskret matematikk. 21. februar 2008. 2.

(6) Oppgave 5.1 Skriv følgende mengder på listeform. (a) Mengden av alle vokaler (b) {x ∈ N : 10 ≤ x ≤ 20 og x er delbar med 3} (c) Mengden av alle naturlige tall som gir en rest på 1 når de deles på 5.. Løsning. MAT1030 – Diskret matematikk. 21. februar 2008. 2.

(7) Oppgave 5.1 Skriv følgende mengder på listeform. (a) Mengden av alle vokaler (b) {x ∈ N : 10 ≤ x ≤ 20 og x er delbar med 3} (c) Mengden av alle naturlige tall som gir en rest på 1 når de deles på 5.. Løsning (a) {a, e, i, o, u, y, æ, ø,å}. MAT1030 – Diskret matematikk. 21. februar 2008. 2.

(8) Oppgave 5.1 Skriv følgende mengder på listeform. (a) Mengden av alle vokaler (b) {x ∈ N : 10 ≤ x ≤ 20 og x er delbar med 3} (c) Mengden av alle naturlige tall som gir en rest på 1 når de deles på 5.. Løsning (a) {a, e, i, o, u, y, æ, ø,å} (b) {12, 15, 18}. MAT1030 – Diskret matematikk. 21. februar 2008. 2.

(9) Oppgave 5.1 Skriv følgende mengder på listeform. (a) Mengden av alle vokaler (b) {x ∈ N : 10 ≤ x ≤ 20 og x er delbar med 3} (c) Mengden av alle naturlige tall som gir en rest på 1 når de deles på 5.. Løsning (a) {a, e, i, o, u, y, æ, ø,å} (b) {12, 15, 18} (c) {1, 6, 11, 16, . . .}. MAT1030 – Diskret matematikk. 21. februar 2008. 2.

(10) Oppgave 5.2 Skriv ned følgende mengder på “predikatform”.. MAT1030 – Diskret matematikk. 21. februar 2008. 3.

(11) Oppgave 5.2 Skriv ned følgende mengder på “predikatform”. (a) {4, 8, 12, 16, 20}. MAT1030 – Diskret matematikk. 21. februar 2008. 3.

(12) Oppgave 5.2 Skriv ned følgende mengder på “predikatform”. (a) {4, 8, 12, 16, 20} (b) {000, 001, 010, 011, 100, 101, 110, 111}. MAT1030 – Diskret matematikk. 21. februar 2008. 3.

(13) Oppgave 5.2 Skriv ned følgende mengder på “predikatform”. (a) {4, 8, 12, 16, 20} (b) {000, 001, 010, 011, 100, 101, 110, 111} (c) {1, 4, 9, 16, 25, . . .}. MAT1030 – Diskret matematikk. 21. februar 2008. 3.

(14) Oppgave 5.2 Skriv ned følgende mengder på “predikatform”. (a) {4, 8, 12, 16, 20} (b) {000, 001, 010, 011, 100, 101, 110, 111} (c) {1, 4, 9, 16, 25, . . .}. Løsning. MAT1030 – Diskret matematikk. 21. februar 2008. 3.

(15) Oppgave 5.2 Skriv ned følgende mengder på “predikatform”. (a) {4, 8, 12, 16, 20} (b) {000, 001, 010, 011, 100, 101, 110, 111} (c) {1, 4, 9, 16, 25, . . .}. Løsning (a) {x ∈ N : x ≤ 20 og x er delbar med 4}. MAT1030 – Diskret matematikk. 21. februar 2008. 3.

(16) Oppgave 5.2 Skriv ned følgende mengder på “predikatform”. (a) {4, 8, 12, 16, 20} (b) {000, 001, 010, 011, 100, 101, 110, 111} (c) {1, 4, 9, 16, 25, . . .}. Løsning (a) {x ∈ N : x ≤ 20 og x er delbar med 4} eller {x : x = 4y for et naturlig tall y ≤ 5}. MAT1030 – Diskret matematikk. 21. februar 2008. 3.

(17) Oppgave 5.2 Skriv ned følgende mengder på “predikatform”. (a) {4, 8, 12, 16, 20} (b) {000, 001, 010, 011, 100, 101, 110, 111} (c) {1, 4, 9, 16, 25, . . .}. Løsning (a) {x ∈ N : x ≤ 20 og x er delbar med 4} eller {x : x = 4y for et naturlig tall y ≤ 5} (b) {x : x er en streng med tre bit}. MAT1030 – Diskret matematikk. 21. februar 2008. 3.

(18) Oppgave 5.2 Skriv ned følgende mengder på “predikatform”. (a) {4, 8, 12, 16, 20} (b) {000, 001, 010, 011, 100, 101, 110, 111} (c) {1, 4, 9, 16, 25, . . .}. Løsning (a) {x ∈ N : x ≤ 20 og x er delbar med 4} eller {x : x = 4y for et naturlig tall y ≤ 5} (b) {x : x er en streng med tre bit} eller {x : x ∈ {0, 1}3 }. MAT1030 – Diskret matematikk. 21. februar 2008. 3.

(19) Oppgave 5.2 Skriv ned følgende mengder på “predikatform”. (a) {4, 8, 12, 16, 20} (b) {000, 001, 010, 011, 100, 101, 110, 111} (c) {1, 4, 9, 16, 25, . . .}. Løsning (a) {x ∈ N : x ≤ 20 og x er delbar med 4} eller {x : x = 4y for et naturlig tall y ≤ 5} (b) {x : x er en streng med tre bit} eller {x : x ∈ {0, 1}3 } (c) {x : det fins et naturlig tall y slik at x = y 2 }. MAT1030 – Diskret matematikk. 21. februar 2008. 3.

(20) Oppgave 5.2 Skriv ned følgende mengder på “predikatform”. (a) {4, 8, 12, 16, 20} (b) {000, 001, 010, 011, 100, 101, 110, 111} (c) {1, 4, 9, 16, 25, . . .}. Løsning (a) {x ∈ N : x ≤ 20 og x er delbar med 4} eller {x : x = 4y for et naturlig tall y ≤ 5} (b) {x : x er en streng med tre bit} eller {x : x ∈ {0, 1}3 } (c) {x : det fins et naturlig tall y slik at x = y 2 } eller {x 2 : x ∈ N}. MAT1030 – Diskret matematikk. 21. februar 2008. 3.

(21) Oppgave 5.2 Skriv ned følgende mengder på “predikatform”. (a) {4, 8, 12, 16, 20} (b) {000, 001, 010, 011, 100, 101, 110, 111} (c) {1, 4, 9, 16, 25, . . .}. Løsning (a) {x ∈ N : x ≤ 20 og x er delbar med 4} eller {x : x = 4y for et naturlig tall y ≤ 5} (b) {x : x er en streng med tre bit} eller {x : x ∈ {0, 1}3 } (c) {x : det fins et naturlig tall y slik at x = y 2 } eller {x 2 : x ∈ N} eller {x ∈ N : ∃y (x = y 2 )}. MAT1030 – Diskret matematikk. 21. februar 2008. 3.

(22) Oppgave 5.2 Skriv ned følgende mengder på “predikatform”. (a) {4, 8, 12, 16, 20} (b) {000, 001, 010, 011, 100, 101, 110, 111} (c) {1, 4, 9, 16, 25, . . .}. Løsning (a) {x ∈ N : x ≤ 20 og x er delbar med 4} eller {x : x = 4y for et naturlig tall y ≤ 5} (b) {x : x er en streng med tre bit} eller {x : x ∈ {0, 1}3 } (c) {x : det fins et naturlig tall y slik at x = y 2 } eller {x 2 : x ∈ N} eller {x ∈ N : ∃y (x = y 2 )} eller {x : x er et kvadrattall}. MAT1030 – Diskret matematikk. 21. februar 2008. 3.

(23) Oppgave 5.3 La A = {1, {1}, {2}, 3}. Avgjør hvilke av følgende påstander som er sanne og usanne.. Løsning. MAT1030 – Diskret matematikk. 21. februar 2008. 4.

(24) Oppgave 5.3 La A = {1, {1}, {2}, 3}. Avgjør hvilke av følgende påstander som er sanne og usanne.. Løsning (a) 1 ∈ A. MAT1030 – Diskret matematikk. 21. februar 2008. 4.

(25) Oppgave 5.3 La A = {1, {1}, {2}, 3}. Avgjør hvilke av følgende påstander som er sanne og usanne.. Løsning (a) 1 ∈ A Sann. MAT1030 – Diskret matematikk. 21. februar 2008. 4.

(26) Oppgave 5.3 La A = {1, {1}, {2}, 3}. Avgjør hvilke av følgende påstander som er sanne og usanne.. Løsning (a) 1 ∈ A Sann (b) 1 ⊆ A. MAT1030 – Diskret matematikk. 21. februar 2008. 4.

(27) Oppgave 5.3 La A = {1, {1}, {2}, 3}. Avgjør hvilke av følgende påstander som er sanne og usanne.. Løsning (a) 1 ∈ A Sann (b) 1 ⊆ A Usann. MAT1030 – Diskret matematikk. 21. februar 2008. 4.

(28) Oppgave 5.3 La A = {1, {1}, {2}, 3}. Avgjør hvilke av følgende påstander som er sanne og usanne.. Løsning (a) 1 ∈ A Sann (b) 1 ⊆ A Usann (c) {1} ∈ A. MAT1030 – Diskret matematikk. 21. februar 2008. 4.

(29) Oppgave 5.3 La A = {1, {1}, {2}, 3}. Avgjør hvilke av følgende påstander som er sanne og usanne.. Løsning (a) 1 ∈ A Sann (b) 1 ⊆ A Usann (c) {1} ∈ A Sann. MAT1030 – Diskret matematikk. 21. februar 2008. 4.

(30) Oppgave 5.3 La A = {1, {1}, {2}, 3}. Avgjør hvilke av følgende påstander som er sanne og usanne.. Løsning (a) 1 ∈ A Sann (b) 1 ⊆ A Usann (c) {1} ∈ A Sann (d) {1} ⊆ A. MAT1030 – Diskret matematikk. 21. februar 2008. 4.

(31) Oppgave 5.3 La A = {1, {1}, {2}, 3}. Avgjør hvilke av følgende påstander som er sanne og usanne.. Løsning (a) 1 ∈ A Sann (b) 1 ⊆ A Usann (c) {1} ∈ A Sann (d) {1} ⊆ A Sann. MAT1030 – Diskret matematikk. 21. februar 2008. 4.

(32) Oppgave 5.3 La A = {1, {1}, {2}, 3}. Avgjør hvilke av følgende påstander som er sanne og usanne.. Løsning (a) 1 ∈ A Sann (b) 1 ⊆ A Usann (c) {1} ∈ A Sann (d) {1} ⊆ A Sann (e) {{1}} ⊆ A. MAT1030 – Diskret matematikk. 21. februar 2008. 4.

(33) Oppgave 5.3 La A = {1, {1}, {2}, 3}. Avgjør hvilke av følgende påstander som er sanne og usanne.. Løsning (a) 1 ∈ A Sann (b) 1 ⊆ A Usann (c) {1} ∈ A Sann (d) {1} ⊆ A Sann (e) {{1}} ⊆ A Sann. MAT1030 – Diskret matematikk. 21. februar 2008. 4.

(34) Oppgave 5.3 La A = {1, {1}, {2}, 3}. Avgjør hvilke av følgende påstander som er sanne og usanne.. Løsning (a) 1 ∈ A Sann. (f) 2 ∈ A. (b) 1 ⊆ A Usann (c) {1} ∈ A Sann (d) {1} ⊆ A Sann (e) {{1}} ⊆ A Sann. MAT1030 – Diskret matematikk. 21. februar 2008. 4.

(35) Oppgave 5.3 La A = {1, {1}, {2}, 3}. Avgjør hvilke av følgende påstander som er sanne og usanne.. Løsning (a) 1 ∈ A Sann. (f) 2 ∈ A Usann. (b) 1 ⊆ A Usann (c) {1} ∈ A Sann (d) {1} ⊆ A Sann (e) {{1}} ⊆ A Sann. MAT1030 – Diskret matematikk. 21. februar 2008. 4.

(36) Oppgave 5.3 La A = {1, {1}, {2}, 3}. Avgjør hvilke av følgende påstander som er sanne og usanne.. Løsning (a) 1 ∈ A Sann. (f) 2 ∈ A Usann. (b) 1 ⊆ A Usann. (g) {2} ∈ A. (c) {1} ∈ A Sann (d) {1} ⊆ A Sann (e) {{1}} ⊆ A Sann. MAT1030 – Diskret matematikk. 21. februar 2008. 4.

(37) Oppgave 5.3 La A = {1, {1}, {2}, 3}. Avgjør hvilke av følgende påstander som er sanne og usanne.. Løsning (a) 1 ∈ A Sann. (f) 2 ∈ A Usann. (b) 1 ⊆ A Usann. (g) {2} ∈ A Sann. (c) {1} ∈ A Sann (d) {1} ⊆ A Sann (e) {{1}} ⊆ A Sann. MAT1030 – Diskret matematikk. 21. februar 2008. 4.

(38) Oppgave 5.3 La A = {1, {1}, {2}, 3}. Avgjør hvilke av følgende påstander som er sanne og usanne.. Løsning (a) 1 ∈ A Sann. (f) 2 ∈ A Usann. (b) 1 ⊆ A Usann. (g) {2} ∈ A Sann. (c) {1} ∈ A Sann. (h) {2} ⊆ A. (d) {1} ⊆ A Sann (e) {{1}} ⊆ A Sann. MAT1030 – Diskret matematikk. 21. februar 2008. 4.

(39) Oppgave 5.3 La A = {1, {1}, {2}, 3}. Avgjør hvilke av følgende påstander som er sanne og usanne.. Løsning (a) 1 ∈ A Sann. (f) 2 ∈ A Usann. (b) 1 ⊆ A Usann. (g) {2} ∈ A Sann. (c) {1} ∈ A Sann. (h) {2} ⊆ A Usann. (d) {1} ⊆ A Sann (e) {{1}} ⊆ A Sann. MAT1030 – Diskret matematikk. 21. februar 2008. 4.

(40) Oppgave 5.3 La A = {1, {1}, {2}, 3}. Avgjør hvilke av følgende påstander som er sanne og usanne.. Løsning (a) 1 ∈ A Sann. (f) 2 ∈ A Usann. (b) 1 ⊆ A Usann. (g) {2} ∈ A Sann. (c) {1} ∈ A Sann. (h) {2} ⊆ A Usann. (d) {1} ⊆ A Sann. (i) {3} ∈ A. (e) {{1}} ⊆ A Sann. MAT1030 – Diskret matematikk. 21. februar 2008. 4.

(41) Oppgave 5.3 La A = {1, {1}, {2}, 3}. Avgjør hvilke av følgende påstander som er sanne og usanne.. Løsning (a) 1 ∈ A Sann. (f) 2 ∈ A Usann. (b) 1 ⊆ A Usann. (g) {2} ∈ A Sann. (c) {1} ∈ A Sann. (h) {2} ⊆ A Usann. (d) {1} ⊆ A Sann. (i) {3} ∈ A Usann. (e) {{1}} ⊆ A Sann. MAT1030 – Diskret matematikk. 21. februar 2008. 4.

(42) Oppgave 5.3 La A = {1, {1}, {2}, 3}. Avgjør hvilke av følgende påstander som er sanne og usanne.. Løsning (a) 1 ∈ A Sann. (f) 2 ∈ A Usann. (b) 1 ⊆ A Usann. (g) {2} ∈ A Sann. (c) {1} ∈ A Sann. (h) {2} ⊆ A Usann. (d) {1} ⊆ A Sann. (i) {3} ∈ A Usann. (e) {{1}} ⊆ A Sann. (j) {3} ⊆ A. MAT1030 – Diskret matematikk. 21. februar 2008. 4.

(43) Oppgave 5.3 La A = {1, {1}, {2}, 3}. Avgjør hvilke av følgende påstander som er sanne og usanne.. Løsning (a) 1 ∈ A Sann. (f) 2 ∈ A Usann. (b) 1 ⊆ A Usann. (g) {2} ∈ A Sann. (c) {1} ∈ A Sann. (h) {2} ⊆ A Usann. (d) {1} ⊆ A Sann. (i) {3} ∈ A Usann. (e) {{1}} ⊆ A Sann. (j) {3} ⊆ A Sann. MAT1030 – Diskret matematikk. 21. februar 2008. 4.

(44) Oppgave 5.4 La E = {x ∈ N : x ≤ 12}, A = {x : x er oddetall}, B = {x : x > 7}, og C = {x : x er delelig med 3}. Lag Venn-diagrammer for mengdene. Skriv ned følgende mengder på listeform. (a) A ∩ B (b) B ∪ C (c) A (d) (A ∪ B) ∩ C (e) (A ∪ C ) ∪ C. MAT1030 – Diskret matematikk. 21. februar 2008. 5.

(45) 7. 8. 5. 11. 1. 9 3. 2. 10. 12. 6. MAT1030 – Diskret matematikk. 4. 21. februar 2008. 6.

(46) 7 5. E = {x ∈ N : x ≤ 12}. 8 11. 10 A = {x : x er oddetall}. 1. 9 3. B = {x : x > 7}. 12. C = {x : x er delelig med 3} 2. 6. MAT1030 – Diskret matematikk. 4. 21. februar 2008. 6.




(50) (a) A ∩ B. 7 5. E = {x ∈ N : x ≤ 12}. 8 11. 10 A = {x : x er oddetall}. 1. 9 3. B = {x : x > 7}. 12. C = {x : x er delelig med 3} 2. 6. MAT1030 – Diskret matematikk. 4. 21. februar 2008. 7.




(54) (a) A ∩ B. 7 5. E = {x ∈ N : x ≤ 12}. 8 11. 10 A = {x : x er oddetall}. 1. 9 3. B = {x : x > 7}. 12. C = {x : x er delelig med 3} 2. 6. 4. Svar (a): {9, 11}. MAT1030 – Diskret matematikk. 21. februar 2008. 7.

(55) (b) B ∪ C. 7 5. E = {x ∈ N : x ≤ 12}. 8 11. 10 A = {x : x er oddetall}. 1. 9 3. B = {x : x > 7}. 12. C = {x : x er delelig med 3} 2. 6. MAT1030 – Diskret matematikk. 4. 21. februar 2008. 8.



(58) (b) B ∪ C. 7 5. E = {x ∈ N : x ≤ 12}. 8 11. 10 A = {x : x er oddetall}. 1. 9 3. B = {x : x > 7}. 12. C = {x : x er delelig med 3} 2. 6. 4. Svar (b): {3, 6, 8, 9, 10, 11, 12}. MAT1030 – Diskret matematikk. 21. februar 2008. 8.

(59) (c) A. 7 5. E = {x ∈ N : x ≤ 12}. 8 11. 10 A = {x : x er oddetall}. 1. 9 3. B = {x : x > 7}. 12. C = {x : x er delelig med 3} 2. 6. MAT1030 – Diskret matematikk. 4. 21. februar 2008. 9.



(62) (c) A. 7 5. E = {x ∈ N : x ≤ 12}. 8 11. 10 A = {x : x er oddetall}. 1. 9 3. B = {x : x > 7}. 12. C = {x : x er delelig med 3} 2. 6. 4. Svar (c): {2, 4, 6, 8, 10, 12}. MAT1030 – Diskret matematikk. 21. februar 2008. 9.

(63) (d) (A ∪ B) ∩ C. 7 5. E = {x ∈ N : x ≤ 12}. 8 11. 10 A = {x : x er oddetall}. 1. 9 3. B = {x : x > 7}. 12. C = {x : x er delelig med 3} 2. 6. MAT1030 – Diskret matematikk. 4. 21. februar 2008. 10.






(69) (d) (A ∪ B) ∩ C. 7 5. E = {x ∈ N : x ≤ 12}. 8 11. 10 A = {x : x er oddetall}. 1. 9 3. B = {x : x > 7}. 12. C = {x : x er delelig med 3} 2. 6. 4. Svar (d): {3, 6, 9}. MAT1030 – Diskret matematikk. 21. februar 2008. 10.

(70) (e) (A ∪ C ) ∪ C. 7 5. E = {x ∈ N : x ≤ 12}. 8 11. 10 A = {x : x er oddetall}. 1. 9 3. B = {x : x > 7}. 12. C = {x : x er delelig med 3} 2. 6. MAT1030 – Diskret matematikk. 4. 21. februar 2008. 11.






(76) (e) (A ∪ C ) ∪ C. 7 5. E = {x ∈ N : x ≤ 12}. 8 11. 10 A = {x : x er oddetall}. 1. 9 3. B = {x : x > 7}. 12. C = {x : x er delelig med 3} 2. 6. 4. Svar (e): {1, 2, 4, 5, 7, 8, 10, 11}. MAT1030 – Diskret matematikk. 21. februar 2008. 11.

(77) Oppgave 5.6 Illustrer den andre absorpsjonsloven, A ∪ (A ∩ B) = A, ved å bruke Venn-diagrammer.. MAT1030 – Diskret matematikk. 21. februar 2008. 12.

(78) Oppgave 5.6 Illustrer den andre absorpsjonsloven, A ∪ (A ∩ B) = A, ved å bruke Venn-diagrammer.. A ∪ (A ∩ B). MAT1030 – Diskret matematikk. 21. februar 2008. 12.

(79) Oppgave 5.6 Illustrer den andre absorpsjonsloven, A ∪ (A ∩ B) = A, ved å bruke Venn-diagrammer.. = A ∪ (A ∩ B). MAT1030 – Diskret matematikk. 21. februar 2008. 12.

(80) Oppgave 5.6 Illustrer den andre absorpsjonsloven, A ∪ (A ∩ B) = A, ved å bruke Venn-diagrammer.. = A ∪ (A ∩ B). MAT1030 – Diskret matematikk. A. 21. februar 2008. 12.

(81) Oppgave 5.6 Illustrer den andre absorpsjonsloven, A ∪ (A ∩ B) = A, ved å bruke Venn-diagrammer.. = A ∪ (A ∩ B). A. Diagrammet for A ∪ (A ∩ B) får vi ved å slå sammen følgende diagrammer:. MAT1030 – Diskret matematikk. 21. februar 2008. 12.

(82) Oppgave 5.6 Illustrer den andre absorpsjonsloven, A ∪ (A ∩ B) = A, ved å bruke Venn-diagrammer.. = A ∪ (A ∩ B). A. Diagrammet for A ∪ (A ∩ B) får vi ved å slå sammen følgende diagrammer:. A. MAT1030 – Diskret matematikk. 21. februar 2008. 12.

(83) Oppgave 5.6 Illustrer den andre absorpsjonsloven, A ∪ (A ∩ B) = A, ved å bruke Venn-diagrammer.. = A ∪ (A ∩ B). A. Diagrammet for A ∪ (A ∩ B) får vi ved å slå sammen følgende diagrammer:. og A. MAT1030 – Diskret matematikk. 21. februar 2008. 12.

(84) Oppgave 5.6 Illustrer den andre absorpsjonsloven, A ∪ (A ∩ B) = A, ved å bruke Venn-diagrammer.. = A ∪ (A ∩ B). A. Diagrammet for A ∪ (A ∩ B) får vi ved å slå sammen følgende diagrammer:. og A. MAT1030 – Diskret matematikk. A∩B. 21. februar 2008. 12.

(85) Oppgave 5.7 (med Venn-diagrammer) Vis at A ∩ B = A ∪ B ved å bruke Venn-diagrammer.. MAT1030 – Diskret matematikk. 21. februar 2008. 13.

(86) Oppgave 5.7 (med Venn-diagrammer) Vis at A ∩ B = A ∪ B ved å bruke Venn-diagrammer. Venn-diagrammet for A ∩ B:. MAT1030 – Diskret matematikk. 21. februar 2008. 13.


(88) Oppgave 5.7 (med Venn-diagrammer) Vis at A ∩ B = A ∪ B ved å bruke Venn-diagrammer. Venn-diagrammet for A ∩ B: A. MAT1030 – Diskret matematikk. 21. februar 2008. 13.

(89) Oppgave 5.7 (med Venn-diagrammer) Vis at A ∩ B = A ∪ B ved å bruke Venn-diagrammer. Venn-diagrammet for A ∩ B: A. MAT1030 – Diskret matematikk. 21. februar 2008. 13.

(90) Oppgave 5.7 (med Venn-diagrammer) Vis at A ∩ B = A ∪ B ved å bruke Venn-diagrammer. Venn-diagrammet for A ∩ B: A∪B. MAT1030 – Diskret matematikk. 21. februar 2008. 13.

(91) Oppgave 5.7 (med Venn-diagrammer) Vis at A ∩ B = A ∪ B ved å bruke Venn-diagrammer. Venn-diagrammet for A ∩ B: A∩B. MAT1030 – Diskret matematikk. 21. februar 2008. 13.

(92) Oppgave 5.7 (med Venn-diagrammer) Vis at A ∩ B = A ∪ B ved å bruke Venn-diagrammer. Venn-diagrammet for A ∩ B: A∩B. MAT1030 – Diskret matematikk. 21. februar 2008. 13.


(94) Oppgave 5.7 (med Venn-diagrammer) Vis at A ∩ B = A ∪ B ved å bruke Venn-diagrammer. Venn-diagrammet for A ∩ B:. Venn-diagrammet for A ∪ B:. MAT1030 – Diskret matematikk. 21. februar 2008. 13.

(95) Oppgave 5.7 (med Venn-diagrammer) Vis at A ∩ B = A ∪ B ved å bruke Venn-diagrammer. Venn-diagrammet for A ∩ B:. Venn-diagrammet for A ∪ B:. MAT1030 – Diskret matematikk. 21. februar 2008. 13.

(96) Oppgave 5.7 (med Venn-diagrammer) Vis at A ∩ B = A ∪ B ved å bruke Venn-diagrammer. Venn-diagrammet for A ∩ B:. Venn-diagrammet for A ∪ B: A. MAT1030 – Diskret matematikk. 21. februar 2008. 13.

(97) Oppgave 5.7 (med Venn-diagrammer) Vis at A ∩ B = A ∪ B ved å bruke Venn-diagrammer. Venn-diagrammet for A ∩ B:. Venn-diagrammet for A ∪ B:. MAT1030 – Diskret matematikk. A∪B. 21. februar 2008. 13.

(98) Oppgave 5.7 (med Venn-diagrammer) Vis at A ∩ B = A ∪ B ved å bruke Venn-diagrammer. Venn-diagrammet for A ∩ B:. Venn-diagrammet for A ∪ B: A∪B. MAT1030 – Diskret matematikk. 21. februar 2008. 13.

(99) Oppgave 5.7 (med Venn-diagrammer) Vis at A ∩ B = A ∪ B ved å bruke Venn-diagrammer. Venn-diagrammet for A ∩ B:. Venn-diagrammet for A ∪ B:. Siden Venn-diagrammene er like, må A ∩ B = A ∪ B.. MAT1030 – Diskret matematikk. 21. februar 2008. 13.

(100) Oppgave 5.8 Er påstanden “enhver mengde med n elementer har 2n delmengder” sann når n = 0?. MAT1030 – Diskret matematikk. 21. februar 2008. 14.

(101) Oppgave 5.8 Er påstanden “enhver mengde med n elementer har 2n delmengder” sann når n = 0?. Løsning. MAT1030 – Diskret matematikk. 21. februar 2008. 14.

(102) Oppgave 5.8 Er påstanden “enhver mengde med n elementer har 2n delmengder” sann når n = 0?. Løsning Når n = 0 er mengden tom.. MAT1030 – Diskret matematikk. 21. februar 2008. 14.

(103) Oppgave 5.8 Er påstanden “enhver mengde med n elementer har 2n delmengder” sann når n = 0?. Løsning Når n = 0 er mengden tom. Hvor mange delmengder har en tom mengde?. MAT1030 – Diskret matematikk. 21. februar 2008. 14.

(104) Oppgave 5.8 Er påstanden “enhver mengde med n elementer har 2n delmengder” sann når n = 0?. Løsning Når n = 0 er mengden tom. Hvor mange delmengder har en tom mengde? Den har nøyaktig én delmengde, nemlig den tomme mengden.. MAT1030 – Diskret matematikk. 21. februar 2008. 14.

(105) Oppgave 5.8 Er påstanden “enhver mengde med n elementer har 2n delmengder” sann når n = 0?. Løsning Når n = 0 er mengden tom. Hvor mange delmengder har en tom mengde? Den har nøyaktig én delmengde, nemlig den tomme mengden. Siden 20 = 1, blir svaret ja.. MAT1030 – Diskret matematikk. 21. februar 2008. 14.

(106) Oppgave 5.9 La A = {a, b, c} og B = {p, q}.. MAT1030 – Diskret matematikk. 21. februar 2008. 15.

(107) Oppgave 5.9 La A = {a, b, c} og B = {p, q}. Skriv ned følgende mengder på listeform.. MAT1030 – Diskret matematikk. 21. februar 2008. 15.

(108) Oppgave 5.9 La A = {a, b, c} og B = {p, q}. Skriv ned følgende mengder på listeform. (a) A × B (b) A2 (c) B 3. MAT1030 – Diskret matematikk. 21. februar 2008. 15.

(109) Oppgave 5.9 La A = {a, b, c} og B = {p, q}. Skriv ned følgende mengder på listeform. (a) A × B (b) A2 (c) B 3. Løsning. MAT1030 – Diskret matematikk. 21. februar 2008. 15.

(110) Oppgave 5.9 La A = {a, b, c} og B = {p, q}. Skriv ned følgende mengder på listeform. (a) A × B (b) A2 (c) B 3. Løsning (a) A × B =. MAT1030 – Diskret matematikk. 21. februar 2008. 15.

(111) Oppgave 5.9 La A = {a, b, c} og B = {p, q}. Skriv ned følgende mengder på listeform. (a) A × B (b) A2 (c) B 3. Løsning (a) A × B = {(a, p), (a, q). MAT1030 – Diskret matematikk. 21. februar 2008. 15.

(112) Oppgave 5.9 La A = {a, b, c} og B = {p, q}. Skriv ned følgende mengder på listeform. (a) A × B (b) A2 (c) B 3. Løsning (a) A × B = {(a, p), (a, q), (b, p), (b, q). MAT1030 – Diskret matematikk. 21. februar 2008. 15.

(113) Oppgave 5.9 La A = {a, b, c} og B = {p, q}. Skriv ned følgende mengder på listeform. (a) A × B (b) A2 (c) B 3. Løsning (a) A × B = {(a, p), (a, q), (b, p), (b, q), (c, p), (c, q)}. MAT1030 – Diskret matematikk. 21. februar 2008. 15.

(114) Oppgave 5.9 La A = {a, b, c} og B = {p, q}. Skriv ned følgende mengder på listeform. (a) A × B (b) A2 (c) B 3. Løsning (a) A × B = {(a, p), (a, q), (b, p), (b, q), (c, p), (c, q)} (b) A2 =. MAT1030 – Diskret matematikk. 21. februar 2008. 15.

(115) Oppgave 5.9 La A = {a, b, c} og B = {p, q}. Skriv ned følgende mengder på listeform. (a) A × B (b) A2 (c) B 3. Løsning (a) A × B = {(a, p), (a, q), (b, p), (b, q), (c, p), (c, q)} (b) A2 = {(a, a), (a, b), (a, c). MAT1030 – Diskret matematikk. 21. februar 2008. 15.

(116) Oppgave 5.9 La A = {a, b, c} og B = {p, q}. Skriv ned følgende mengder på listeform. (a) A × B (b) A2 (c) B 3. Løsning (a) A × B = {(a, p), (a, q), (b, p), (b, q), (c, p), (c, q)} (b) A2 = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c). MAT1030 – Diskret matematikk. 21. februar 2008. 15.

(117) Oppgave 5.9 La A = {a, b, c} og B = {p, q}. Skriv ned følgende mengder på listeform. (a) A × B (b) A2 (c) B 3. Løsning (a) A × B = {(a, p), (a, q), (b, p), (b, q), (c, p), (c, q)} (b) A2 = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}. MAT1030 – Diskret matematikk. 21. februar 2008. 15.

(118) Oppgave 5.9 La A = {a, b, c} og B = {p, q}. Skriv ned følgende mengder på listeform. (a) A × B (b) A2 (c) B 3. Løsning (a) A × B = {(a, p), (a, q), (b, p), (b, q), (c, p), (c, q)} (b) A2 = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)} (c) B 3 =. MAT1030 – Diskret matematikk. 21. februar 2008. 15.

(119) Oppgave 5.9 La A = {a, b, c} og B = {p, q}. Skriv ned følgende mengder på listeform. (a) A × B (b) A2 (c) B 3. Løsning (a) A × B = {(a, p), (a, q), (b, p), (b, q), (c, p), (c, q)} (b) A2 = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)} (c) B 3 = {(p, p, p), (p, p, q). MAT1030 – Diskret matematikk. 21. februar 2008. 15.

(120) Oppgave 5.9 La A = {a, b, c} og B = {p, q}. Skriv ned følgende mengder på listeform. (a) A × B (b) A2 (c) B 3. Løsning (a) A × B = {(a, p), (a, q), (b, p), (b, q), (c, p), (c, q)} (b) A2 = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)} (c) B 3 = {(p, p, p), (p, p, q), (p, q, p), (p, q, q). MAT1030 – Diskret matematikk. 21. februar 2008. 15.

(121) Oppgave 5.9 La A = {a, b, c} og B = {p, q}. Skriv ned følgende mengder på listeform. (a) A × B (b) A2 (c) B 3. Løsning (a) A × B = {(a, p), (a, q), (b, p), (b, q), (c, p), (c, q)} (b) A2 = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)} (c) B 3 = {(p, p, p), (p, p, q), (p, q, p), (p, q, q), (q, p, p), (q, p, q). MAT1030 – Diskret matematikk. 21. februar 2008. 15.

(122) Oppgave 5.9 La A = {a, b, c} og B = {p, q}. Skriv ned følgende mengder på listeform. (a) A × B (b) A2 (c) B 3. Løsning (a) A × B = {(a, p), (a, q), (b, p), (b, q), (c, p), (c, q)} (b) A2 = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)} (c) B 3 = {(p, p, p), (p, p, q), (p, q, p), (p, q, q), (q, p, p), (q, p, q), (q, q, p), (q, q, q)}. MAT1030 – Diskret matematikk. 21. februar 2008. 15.

(123) Oppgave 5.10 Uttrykk hver av følgende mengder som et Kartesisk produkt av mengder.. MAT1030 – Diskret matematikk. 21. februar 2008. 16.

(124) Oppgave 5.10 Uttrykk hver av følgende mengder som et Kartesisk produkt av mengder.. Løsning Eventuelt på tavla.. MAT1030 – Diskret matematikk. 21. februar 2008. 16.

(125) Oppgave 5.13 Se på følgende algoritme.. MAT1030 – Diskret matematikk. 21. februar 2008. 17.

(126) Oppgave 5.13 Se på følgende algoritme. 1. Input en bitstreng b. MAT1030 – Diskret matematikk. 21. februar 2008. 17.

(127) Oppgave 5.13 Se på følgende algoritme. 1. Input en bitstreng b 2. n ← det usignerte bitet som har b som sin binære representasjon. MAT1030 – Diskret matematikk. 21. februar 2008. 17.

(128) Oppgave 5.13 Se på følgende algoritme. 1. Input en bitstreng b 2. n ← det usignerte bitet som har b som sin binære representasjon 3. teller ← 0. MAT1030 – Diskret matematikk. 21. februar 2008. 17.

(129) Oppgave 5.13 Se på følgende algoritme. 1. Input en bitstreng b 2. n ← det usignerte bitet som har b som sin binære representasjon 3. teller ← 0 4. While n > 0 do. MAT1030 – Diskret matematikk. 21. februar 2008. 17.

(130) Oppgave 5.13 Se på følgende algoritme. 1. Input en bitstreng b 2. n ← det usignerte bitet som har b som sin binære representasjon 3. teller ← 0 4. While n > 0 do 4.1. n ← n ∧ (n − 1) [∧ betyr her bitvis ‘og’, her anvendt på den binære representasjonen av n og n − 1]. MAT1030 – Diskret matematikk. 21. februar 2008. 17.

(131) Oppgave 5.13 Se på følgende algoritme. 1. Input en bitstreng b 2. n ← det usignerte bitet som har b som sin binære representasjon 3. teller ← 0 4. While n > 0 do 4.1. n ← n ∧ (n − 1) [∧ betyr her bitvis ‘og’, her anvendt på den binære representasjonen av n og n − 1] 4.2. teller ← teller + 1 [skrivefeil i boka: det står − i stedet for +]. MAT1030 – Diskret matematikk. 21. februar 2008. 17.

(132) Oppgave 5.13 Se på følgende algoritme. 1. Input en bitstreng b 2. n ← det usignerte bitet som har b som sin binære representasjon 3. teller ← 0 4. While n > 0 do 4.1. n ← n ∧ (n − 1) [∧ betyr her bitvis ‘og’, her anvendt på den binære representasjonen av n og n − 1] 4.2. teller ← teller + 1 [skrivefeil i boka: det står − i stedet for +]. 5. Output teller. MAT1030 – Diskret matematikk. 21. februar 2008. 17.

(133) Oppgave 5.13 Se på følgende algoritme. 1. Input en bitstreng b 2. n ← det usignerte bitet som har b som sin binære representasjon 3. teller ← 0 4. While n > 0 do 4.1. n ← n ∧ (n − 1) [∧ betyr her bitvis ‘og’, her anvendt på den binære representasjonen av n og n − 1] 4.2. teller ← teller + 1 [skrivefeil i boka: det står − i stedet for +]. 5. Output teller Vis at returverdien er antall enere i b.. MAT1030 – Diskret matematikk. 21. februar 2008. 17.

(134) Eksempel Anta at input er 100101.. MAT1030 – Diskret matematikk. 21. februar 2008. 18.

(135) Eksempel Anta at input er 100101. teller 0. MAT1030 – Diskret matematikk. binær representasjon av n og n − 1 1001001. 21. februar 2008. 18.

(136) Eksempel Anta at input er 100101. teller 0. MAT1030 – Diskret matematikk. binær representasjon av n og n − 1 1001001 1001000. 21. februar 2008. 18.

(137) Eksempel Anta at input er 100101. teller 0 1. MAT1030 – Diskret matematikk. binær representasjon av n og n − 1 1001001 1001000 1001000. 21. februar 2008. 18.

(138) Eksempel Anta at input er 100101. teller 0 1. MAT1030 – Diskret matematikk. binær representasjon av n og n − 1 1001001 1001000 1001000 1000111. 21. februar 2008. 18.

(139) Eksempel Anta at input er 100101. teller 0 1 2. MAT1030 – Diskret matematikk. binær representasjon av n og n − 1 1001001 1001000 1001000 1000111 1000000. 21. februar 2008. 18.

(140) Eksempel Anta at input er 100101. teller 0 1 2. MAT1030 – Diskret matematikk. binær representasjon av n og n − 1 1001001 1001000 1001000 1000111 1000000 0111111. 21. februar 2008. 18.

(141) Eksempel Anta at input er 100101. teller 0 1 2 3. MAT1030 – Diskret matematikk. binær representasjon av n og n − 1 1001001 1001000 1001000 1000111 1000000 0111111 0000000. 21. februar 2008. 18.

(142) Eksempel Anta at input er 111101.. MAT1030 – Diskret matematikk. 21. februar 2008. 19.

(143) Eksempel Anta at input er 111101. teller. MAT1030 – Diskret matematikk. binær representasjon av n og n − 1. 21. februar 2008. 19.

(144) Eksempel Anta at input er 111101. teller 0. MAT1030 – Diskret matematikk. binær representasjon av n og n − 1 1111001. 21. februar 2008. 19.

(145) Eksempel Anta at input er 111101. teller 0. MAT1030 – Diskret matematikk. binær representasjon av n og n − 1 1111001 1111000. 21. februar 2008. 19.

(146) Eksempel Anta at input er 111101. teller 0 1. MAT1030 – Diskret matematikk. binær representasjon av n og n − 1 1111001 1111000 1111000. 21. februar 2008. 19.

(147) Eksempel Anta at input er 111101. teller 0 1. MAT1030 – Diskret matematikk. binær representasjon av n og n − 1 1111001 1111000 1111000 1110111. 21. februar 2008. 19.

(148) Eksempel Anta at input er 111101. teller 0 1 2. MAT1030 – Diskret matematikk. binær representasjon av n og n − 1 1111001 1111000 1111000 1110111 1110000. 21. februar 2008. 19.

(149) Eksempel Anta at input er 111101. teller 0 1 2. MAT1030 – Diskret matematikk. binær representasjon av n og n − 1 1111001 1111000 1111000 1110111 1110000 1101111. 21. februar 2008. 19.

(150) Eksempel Anta at input er 111101. teller 0 1 2 3. MAT1030 – Diskret matematikk. binær representasjon av n og n − 1 1111001 1111000 1111000 1110111 1110000 1101111 1100000. 21. februar 2008. 19.

(151) Eksempel Anta at input er 111101. teller 0 1 2 3. MAT1030 – Diskret matematikk. binær representasjon av n og n − 1 1111001 1111000 1111000 1110111 1110000 1101111 1100000 1011111. 21. februar 2008. 19.

(152) Eksempel Anta at input er 111101. teller 0 1 2 3 4. MAT1030 – Diskret matematikk. binær representasjon av n og n − 1 1111001 1111000 1111000 1110111 1110000 1101111 1100000 1011111 1000000. 21. februar 2008. 19.

(153) Eksempel Anta at input er 111101. teller 0 1 2 3 4. MAT1030 – Diskret matematikk. binær representasjon av n og n − 1 1111001 1111000 1111000 1110111 1110000 1101111 1100000 1011111 1000000 0111111. 21. februar 2008. 19.

(154) Eksempel Anta at input er 111101. teller 0 1 2 3 4 5. MAT1030 – Diskret matematikk. binær representasjon av n og n − 1 1111001 1111000 1111000 1110111 1110000 1101111 1100000 1011111 1000000 0111111 0000000. 21. februar 2008. 19.

(155) Løsning. MAT1030 – Diskret matematikk. 21. februar 2008. 20.

(156) Løsning Vi skal vise at returverdien er antall enere i inputverdien.. MAT1030 – Diskret matematikk. 21. februar 2008. 20.

(157) Løsning Vi skal vise at returverdien er antall enere i inputverdien. Det er tilstrekkelig å vise at hvert steg i While-løkken reduserer antall enere med nøyaktig én.. MAT1030 – Diskret matematikk. 21. februar 2008. 20.

(158) Løsning Vi skal vise at returverdien er antall enere i inputverdien. Det er tilstrekkelig å vise at hvert steg i While-løkken reduserer antall enere med nøyaktig én. Vi må vise at bitvis ∧ av representasjonene til n og n − 1 reduserer antall enere med nøyaktig én.. MAT1030 – Diskret matematikk. 21. februar 2008. 20.

(159) Løsning Vi skal vise at returverdien er antall enere i inputverdien. Det er tilstrekkelig å vise at hvert steg i While-løkken reduserer antall enere med nøyaktig én. Vi må vise at bitvis ∧ av representasjonene til n og n − 1 reduserer antall enere med nøyaktig én. La b1 . . . bk være representasjonen til n.. MAT1030 – Diskret matematikk. 21. februar 2008. 20.

(160) Løsning Vi skal vise at returverdien er antall enere i inputverdien. Det er tilstrekkelig å vise at hvert steg i While-løkken reduserer antall enere med nøyaktig én. Vi må vise at bitvis ∧ av representasjonene til n og n − 1 reduserer antall enere med nøyaktig én. La b1 . . . bk være representasjonen til n. Vi kan anta at n > 0. Da må minst et bit være en ener.. MAT1030 – Diskret matematikk. 21. februar 2008. 20.

(161) Løsning Vi skal vise at returverdien er antall enere i inputverdien. Det er tilstrekkelig å vise at hvert steg i While-løkken reduserer antall enere med nøyaktig én. Vi må vise at bitvis ∧ av representasjonene til n og n − 1 reduserer antall enere med nøyaktig én. La b1 . . . bk være representasjonen til n. Vi kan anta at n > 0. Da må minst et bit være en ener. La bm være eneren som forekommer lengst til høyre, for 1 ≤ m ≤ k.. MAT1030 – Diskret matematikk. 21. februar 2008. 20.

(162) Løsning Vi skal vise at returverdien er antall enere i inputverdien. Det er tilstrekkelig å vise at hvert steg i While-løkken reduserer antall enere med nøyaktig én. Vi må vise at bitvis ∧ av representasjonene til n og n − 1 reduserer antall enere med nøyaktig én. La b1 . . . bk være representasjonen til n. Vi kan anta at n > 0. Da må minst et bit være en ener. La bm være eneren som forekommer lengst til høyre, for 1 ≤ m ≤ k. Vi har følgende situasjon, hvor vi ser at bitvis ∧ fjerner nøyaktig én ener. (Eventuelt flere detaljer i plenum.). MAT1030 – Diskret matematikk. 21. februar 2008. 20.

(163) Løsning Vi skal vise at returverdien er antall enere i inputverdien. Det er tilstrekkelig å vise at hvert steg i While-løkken reduserer antall enere med nøyaktig én. Vi må vise at bitvis ∧ av representasjonene til n og n − 1 reduserer antall enere med nøyaktig én. La b1 . . . bk være representasjonen til n. Vi kan anta at n > 0. Da må minst et bit være en ener. La bm være eneren som forekommer lengst til høyre, for 1 ≤ m ≤ k. Vi har følgende situasjon, hvor vi ser at bitvis ∧ fjerner nøyaktig én ener. (Eventuelt flere detaljer i plenum.) b1 b2 . . . bm−1 100 . . . 00 b1 b2 . . . bm−1 011 . . . 11 b1 b2 . . . bm−1 000 . . . 00 MAT1030 – Diskret matematikk. 21. februar 2008. 20.

(164) Oppgave 5.14 Se på følgende sekvens av steg i pseudokode, hvor x og y er bitstrenger av lik lengde.. MAT1030 – Diskret matematikk. 21. februar 2008. 21.

(165) Oppgave 5.14 Se på følgende sekvens av steg i pseudokode, hvor x og y er bitstrenger av lik lengde. 1. x ← x ⊕ y [⊕ står for bitvis eksklusiv eller]. MAT1030 – Diskret matematikk. 21. februar 2008. 21.

(166) Oppgave 5.14 Se på følgende sekvens av steg i pseudokode, hvor x og y er bitstrenger av lik lengde. 1. x ← x ⊕ y [⊕ står for bitvis eksklusiv eller] 2. y ← x ⊕ y. MAT1030 – Diskret matematikk. 21. februar 2008. 21.

(167) Oppgave 5.14 Se på følgende sekvens av steg i pseudokode, hvor x og y er bitstrenger av lik lengde. 1. x ← x ⊕ y [⊕ står for bitvis eksklusiv eller] 2. y ← x ⊕ y 3. x ← x ⊕ y. MAT1030 – Diskret matematikk. 21. februar 2008. 21.

(168) Oppgave 5.14 Se på følgende sekvens av steg i pseudokode, hvor x og y er bitstrenger av lik lengde. 1. x ← x ⊕ y [⊕ står for bitvis eksklusiv eller] 2. y ← x ⊕ y 3. x ← x ⊕ y Vis at effekten av sekvensen av steg er å bytte verdiene til x og y .. MAT1030 – Diskret matematikk. 21. februar 2008. 21.


(170) Løsning La x = x1 . . . xn og y = y1 . . . yn .. MAT1030 – Diskret matematikk. 21. februar 2008. 22.

(171) Løsning La x = x1 . . . xn og y = y1 . . . yn . La oss se på hva som skjer bitvis, for xi og yi , hvor 1 ≤ i ≤ n.. MAT1030 – Diskret matematikk. 21. februar 2008. 22.

(172) Løsning La x = x1 . . . xn og y = y1 . . . yn . La oss se på hva som skjer bitvis, for xi og yi , hvor 1 ≤ i ≤ n. Steg 1, x ← x ⊕ y , setter xi lik xi ⊕ yi .. MAT1030 – Diskret matematikk. 21. februar 2008. 22.

(173) Løsning La x = x1 . . . xn og y = y1 . . . yn . La oss se på hva som skjer bitvis, for xi og yi , hvor 1 ≤ i ≤ n. Steg 1, x ← x ⊕ y , setter xi lik xi ⊕ yi . Steg 2, y ← x ⊕ y , setter yi lik (xi ⊕ yi ) ⊕ yi .. MAT1030 – Diskret matematikk. 21. februar 2008. 22.

(174) Løsning La x = x1 . . . xn og y = y1 . . . yn . La oss se på hva som skjer bitvis, for xi og yi , hvor 1 ≤ i ≤ n. Steg 1, x ← x ⊕ y , setter xi lik xi ⊕ yi . Steg 2, y ← x ⊕ y , setter yi lik (xi ⊕ yi ) ⊕ yi . Steg 3, x ← x ⊕ y , setter xi lik (xi ⊕ yi ) ⊕ ((xi ⊕ yi ) ⊕ yi ).. MAT1030 – Diskret matematikk. 21. februar 2008. 22.

(175) Løsning La x = x1 . . . xn og y = y1 . . . yn . La oss se på hva som skjer bitvis, for xi og yi , hvor 1 ≤ i ≤ n. Steg 1, x ← x ⊕ y , setter xi lik xi ⊕ yi . Steg 2, y ← x ⊕ y , setter yi lik (xi ⊕ yi ) ⊕ yi . Steg 3, x ← x ⊕ y , setter xi lik (xi ⊕ yi ) ⊕ ((xi ⊕ yi ) ⊕ yi ). Vi må vise at (xi ⊕ yi ) ⊕ yi er lik den opprinnelige xi .. MAT1030 – Diskret matematikk. 21. februar 2008. 22.

(176) Løsning La x = x1 . . . xn og y = y1 . . . yn . La oss se på hva som skjer bitvis, for xi og yi , hvor 1 ≤ i ≤ n. Steg 1, x ← x ⊕ y , setter xi lik xi ⊕ yi . Steg 2, y ← x ⊕ y , setter yi lik (xi ⊕ yi ) ⊕ yi . Steg 3, x ← x ⊕ y , setter xi lik (xi ⊕ yi ) ⊕ ((xi ⊕ yi ) ⊕ yi ). Vi må vise at (xi ⊕ yi ) ⊕ yi er lik den opprinnelige xi . Vi må vise at (xi ⊕ yi ) ⊕ ((xi ⊕ yi ) ⊕ yi ) er lik den opprinnelige yi .. MAT1030 – Diskret matematikk. 21. februar 2008. 22.

(177) Løsning La x = x1 . . . xn og y = y1 . . . yn . La oss se på hva som skjer bitvis, for xi og yi , hvor 1 ≤ i ≤ n. Steg 1, x ← x ⊕ y , setter xi lik xi ⊕ yi . Steg 2, y ← x ⊕ y , setter yi lik (xi ⊕ yi ) ⊕ yi . Steg 3, x ← x ⊕ y , setter xi lik (xi ⊕ yi ) ⊕ ((xi ⊕ yi ) ⊕ yi ). Vi må vise at (xi ⊕ yi ) ⊕ yi er lik den opprinnelige xi . Vi må vise at (xi ⊕ yi ) ⊕ ((xi ⊕ yi ) ⊕ yi ) er lik den opprinnelige yi . xi 1 1 0 0. yi 1 0 1 0. MAT1030 – Diskret matematikk. (xi ⊕ yi ) ⊕ ((xi ⊕ yi ) ⊕ yi ) 0 1 0 1 1 1 0 1 1 0 1 1 1 0 1 0 0 0 0 0. 21. februar 2008. 22.

(178) Løsning La x = x1 . . . xn og y = y1 . . . yn . La oss se på hva som skjer bitvis, for xi og yi , hvor 1 ≤ i ≤ n. Steg 1, x ← x ⊕ y , setter xi lik xi ⊕ yi . Steg 2, y ← x ⊕ y , setter yi lik (xi ⊕ yi ) ⊕ yi . Steg 3, x ← x ⊕ y , setter xi lik (xi ⊕ yi ) ⊕ ((xi ⊕ yi ) ⊕ yi ). Vi må vise at (xi ⊕ yi ) ⊕ yi er lik den opprinnelige xi . Vi må vise at (xi ⊕ yi ) ⊕ ((xi ⊕ yi ) ⊕ yi ) er lik den opprinnelige yi . xi 1 1 0 0. yi 1 0 1 0. (xi ⊕ yi ) ⊕ ((xi ⊕ yi ) ⊕ yi ) 0 1 0 1 1 1 0 1 1 0 1 1 1 0 1 0 0 0 0 0. Kolonnene 1 og 6 er like, og kolonnene 2 og 4 er like. MAT1030 – Diskret matematikk. 21. februar 2008. 22.


(180) Løsning Vi kunne også ha løst oppgaven ved å vise at (p ⊕ q) ⊕ q er logisk ekvivalent med p.. MAT1030 – Diskret matematikk. 21. februar 2008. 23.

(181) Løsning Vi kunne også ha løst oppgaven ved å vise at (p ⊕ q) ⊕ q er logisk ekvivalent med p. p q (p ⊕ q) ⊕ q 1 1 1 0 0 1 0 0. MAT1030 – Diskret matematikk. 21. februar 2008. 23.

(182) Løsning Vi kunne også ha løst oppgaven ved å vise at (p ⊕ q) ⊕ q er logisk ekvivalent med p. p q (p ⊕ q) ⊕ q 0 1 1 1 0 0 1 0 0. MAT1030 – Diskret matematikk. 21. februar 2008. 23.

(183) Løsning Vi kunne også ha løst oppgaven ved å vise at (p ⊕ q) ⊕ q er logisk ekvivalent med p. p q (p ⊕ q) ⊕ q 0 1 1 1 1 0 0 1 0 0. MAT1030 – Diskret matematikk. 21. februar 2008. 23.

(184) Løsning Vi kunne også ha løst oppgaven ved å vise at (p ⊕ q) ⊕ q er logisk ekvivalent med p. p q (p ⊕ q) ⊕ q 0 1 1 1 1 1 0 0 1 0 0. MAT1030 – Diskret matematikk. 21. februar 2008. 23.

(185) Løsning Vi kunne også ha løst oppgaven ved å vise at (p ⊕ q) ⊕ q er logisk ekvivalent med p. p q (p ⊕ q) ⊕ q 0 1 1 1 1 1 0 1 0 1 0 0. MAT1030 – Diskret matematikk. 21. februar 2008. 23.

(186) Løsning Vi kunne også ha løst oppgaven ved å vise ekvivalent med p. p q (p ⊕ q) ⊕ 0 1 1 1 1 0 1 0 1 0 0. MAT1030 – Diskret matematikk. at (p ⊕ q) ⊕ q er logisk q 1 0. 21. februar 2008. 23.

(187) Løsning Vi kunne også ha løst oppgaven ved å vise ekvivalent med p. p q (p ⊕ q) ⊕ 0 1 1 1 1 0 1 1 0 1 0 0. MAT1030 – Diskret matematikk. at (p ⊕ q) ⊕ q er logisk q 1 0. 21. februar 2008. 23.

(188) Løsning Vi kunne også ha løst oppgaven ved å vise ekvivalent med p. p q (p ⊕ q) ⊕ 0 1 1 1 1 0 1 1 1 0 1 0 0. MAT1030 – Diskret matematikk. at (p ⊕ q) ⊕ q er logisk q 1 0. 21. februar 2008. 23.

(189) Løsning Vi kunne også ha løst oppgaven ved å vise ekvivalent med p. p q (p ⊕ q) ⊕ 0 1 1 1 1 0 1 1 1 0 1 0 0. MAT1030 – Diskret matematikk. at (p ⊕ q) ⊕ q er logisk q 1 0 1. 21. februar 2008. 23.

(190) Løsning Vi kunne også ha løst oppgaven ved å vise ekvivalent med p. p q (p ⊕ q) ⊕ 0 1 1 1 1 0 1 1 1 0 0 1 0 0. MAT1030 – Diskret matematikk. at (p ⊕ q) ⊕ q er logisk q 1 0 1. 21. februar 2008. 23.

(191) Løsning Vi kunne også ha løst oppgaven ved å vise ekvivalent med p. p q (p ⊕ q) ⊕ 0 1 1 1 1 0 1 1 1 0 0 1 0 0 0. MAT1030 – Diskret matematikk. at (p ⊕ q) ⊕ q er logisk q 1 0 1. 21. februar 2008. 23.

(192) Løsning Vi kunne også ha løst oppgaven ved å vise ekvivalent med p. p q (p ⊕ q) ⊕ 0 1 1 1 1 0 1 1 1 0 0 1 0 0 0. MAT1030 – Diskret matematikk. at (p ⊕ q) ⊕ q er logisk q 1 0 1 0. 21. februar 2008. 23.

(193) Løsning Vi kunne også ha løst oppgaven ved å vise ekvivalent med p. p q (p ⊕ q) ⊕ 0 1 1 1 1 0 1 1 1 0 0 1 0 0 0 0. MAT1030 – Diskret matematikk. at (p ⊕ q) ⊕ q er logisk q 1 0 1 0. 21. februar 2008. 23.

(194) Løsning Vi kunne også ha løst oppgaven ved å vise ekvivalent med p. p q (p ⊕ q) ⊕ 0 1 1 1 1 0 1 1 1 0 0 1 0 0 0 0. at (p ⊕ q) ⊕ q er logisk q 1 0 1 0. Da må (xi ⊕ yi ) ⊕ yi (den nye verdien til yi ) være lik xi. MAT1030 – Diskret matematikk. 21. februar 2008. 23.

(195) Løsning Vi kunne også ha løst oppgaven ved å vise ekvivalent med p. p q (p ⊕ q) ⊕ 0 1 1 1 1 0 1 1 1 0 0 1 0 0 0 0. at (p ⊕ q) ⊕ q er logisk q 1 0 1 0. Da må (xi ⊕ yi ) ⊕ yi (den nye verdien til yi ) være lik xi Da må (xi ⊕ yi ) ⊕ ((xi ⊕ yi ) ⊕ yi ) (den nye verdien til xi ) være lik yi .. MAT1030 – Diskret matematikk. 21. februar 2008. 23.

(196) Oppgave 5.15. MAT1030 – Diskret matematikk. 21. februar 2008. 24.

(197) Oppgave 5.15 La A = {1, 2, 3, 4, 5} og la R være relasjonen på A som er definert slik:. MAT1030 – Diskret matematikk. 21. februar 2008. 24.

(198) Oppgave 5.15 La A = {1, 2, 3, 4, 5} og la R være relasjonen på A som er definert slik: R = {(1, 3), (1, 4), (2, 1), (2, 2), (2, 4), (3, 5), (5, 2), (5.5)}. MAT1030 – Diskret matematikk. 21. februar 2008. 24.

(199) Oppgave 5.15 La A = {1, 2, 3, 4, 5} og la R være relasjonen på A som er definert slik: R = {(1, 3), (1, 4), (2, 1), (2, 2), (2, 4), (3, 5), (5, 2), (5.5)}. (a) Skriv ned relasjonen R på matriseform.. MAT1030 – Diskret matematikk. 21. februar 2008. 24.

(200) Oppgave 5.15 La A = {1, 2, 3, 4, 5} og la R være relasjonen på A som er definert slik: R = {(1, 3), (1, 4), (2, 1), (2, 2), (2, 4), (3, 5), (5, 2), (5.5)}. (a) Skriv ned relasjonen R på matriseform. (b) Tegn den grafiske representasjonen av R.. MAT1030 – Diskret matematikk. 21. februar 2008. 24.

(201)

No results found