Stærðfræðimynstur í tölvunarfræði
09.12.14
Haustpróf 23. ágúst 1994
Allar spurningarnar hafa sama vægi. Einungis þarf að svara
6 spurningum af 7. Bestu 6 svörin gilda.
Öll skrifleg hjálpargögn leyfileg.
1.
a) Setjið eftirfarandi setningar fram sem yrðingar í umsagnarökfræði.
Óðalið á að vera mengi allra hluta.
i) Sumir Íslendingar eru stærri en allir Japanir.
ii) Fyrir hvern Íslending er til einn Japani og einn Kínverji
þannig að samanlögð þyngd þeirra er meiri en Íslendingsins.
b) Sýnið neitun setninganna í a)-lið á einfölduðu formi, bæði sem
yrðingar í umsagnarökfræði og sem venjulegar setningar.
2.
Sannið að ef ac = bc (mod m) og gcd(c, m) = 1, þá
er a = b (mod m).
3.
Formúlan hér að neðan hefur lokaða formið f(n). Finnið það með
ágiskun (prófið að stinga inn nokkrum gildum) og sannið að formúlan
hafi þetta lokaða form með þrepun.
(1 - 1/4)(1 - 1/9) ... (1 - 1/n); n = 2, 3, 4, ...
(Vísbending: Lokaða formið f(n) er af gerðinni ( ? )/2 )
4.
Sjoppa ein hefur 12 tegundir sælgætis sem allt kostar 5 kr. stykkið.
a) Á hve marga vegu er hægt að velja bland í poka fyrir 40 kr.?
b) En ef það verða að vera a.m.k. tvö stykki af hverri tegund sem
er valin?
5.
Lát A vera mengið {1, 2, 3, 4}. Í eftirfarandi liðum sýnið dæmi
um vensl, eða sannið að engin slík vensl séu til.
a) Eru til vensl R á A, þannig að R
eru samhverf og andsamhverf?
b) Eru til vensl S á A, þannig að S
eru sjálfhverf, andsamhverf, en ekki samhverf?
c) Eru til vensl T á A, þannig að T
eru ósamhverf en ekki andsamhverf?
6.
Sannið að öll tré eru tvíflokka gröf.
7. Sýnið löggenga endanlega stöðuvél (með lokastöðum, ekki
úttaki), sem samþykkir þá tvíundarstrengi sem eru þannig að ef túlkaðir
sem tvíundartölur k þá gildir að þeir gefa afganginn 3 þegar
deilt er í þá með 4 (þ.e. k = 3 (mod 4) ).