Strfrimynstur tlvunarfri
09.12.14


Lokaprf 19. desember 1991


Allar spurningarnar hafa sama vgi. Einungis arf a svara 6 spurningum af 7. Bestu 6 svrin gilda.
ll skrifleg hjlparggn leyfileg.




1. Fyrir hverja eftirtalinna yringa umsagnarkfri sni eina tlkun (al, tskring umsgnum og gildi fasta) ar sem yringin er snn og ara ar sem hn er snn.

a) (Ex)P(x) -> (Ax)P(x)
b) (Ax)(Ey)P(x, y) -> (Ex)(Ay)P(x, y)
c) (Ex)[P(x) -> Q(x)] -> [(Ex)P(x) -> (Ex)Q(x)]
d) (Ax)[P(x) -> Q(x)] -> [P(a) -> (Ax)Q(x)]

Hva segir a okkur um essar yringar a vi skulum geta fundi tvr slkar andstar tlkanir?



2. Hanna rkrs sem tekur inn tvundarform eins tlustafs fr 0 til 9 og skilar t tvundarformi tlunnar eftir a bi er a leggja 1 vi hana (segjum a 9+1 = 0). Inntaki samanstendur af 4 bitum b1, b2, b3, b4 og ttaki er bitarnir c1, c2, c3, c4. Sem dmi, verur inntaki 0101 a ttakinu 0110.


Bi til Boolesegina fyrir c2, einfaldi hana me Karnaugh korti og sni rkrsina fyrir c2, sem kemur t r v.



3. Vi hfum n beinar endanlegar lnur sem liggja annig slttunni (planinu) a engar tvr eru samsa og engar rjr skerast sama punkti. Hva skipta n lnurnar slttunni upp mrg svi? Hr a nean sst a 4 lnur skipta slttunni upp 11 svi.



(Vsbending: Reyni a giska almennu formluna og sanni hana me repun.)



4. prfi Efnafrimynstur tlvunarfri eru 12 spurningar. Aeins a svara 9 af eim. Hve margir mguleikar eru a svara essum 9 spurningum ...
a) ef alltaf arf a svara spurningum 1 og 7?
b) ef ekki m svara bi spurningum 2 og 3?
c) ef svara arf a.m.k. 5 spurningum af fyrstu 6?
d) ef spurningarnar sem sleppt er mega ekki allar vera oddatluspurningar?



5. Vi skilgreinum innri lengd (internal path length) tvundartrs sem summu lengdar allra vega fr rt til allra hnta sem eru ekki lauf. Ytri lengd (external path length) er summa lengdar allra vega fr rt til allra laufa. Ef allir hntar tvundartrnu hafa anna hvort tv brn ea ekkert sni a ytri lengd = innri lengd + 2k, ar sem k er fjldi innri hnta (.e., ekki lauf) trnu.



6. Lt M vera mengi eirra bitastrengja sem, ef tlkair sem tvundartlur, tkna tlur sem 3 gengur upp. M = {0, 11, 110, 1001, 1100, 1111, ... }
a) Bi til endanlega stuvl sem ber kennsl M. Geri r fyrir a strengurinn s lesinn inn vinstra megin fr. (Vsbending: Lti stuvlina vera kveinni stu ef bitastrengurinn sem lesinn hefur veri inn hinga til mod 3 = i, fyrir i=0,1,2)
b) Sni reglulega mlfri sem skilgreinir mli M.
c) Sni reglulega seg fyrir M.



7. Ef um hlfgrpuna [S, +] gildir a ef x+y = x+z er y=z, er hn sg styttin fr vinstri.
a)Sni a algebran me mengi S* (mengi allra strengja me tknum r S) og agerina samtenging strengja er styttin fr vinstri.
b) Sni a vxlna hlfgrpan [{0, 1, 2, 3}, max] er ekki styttin fr vinstri.
c) Sni dmi um hlfgrpu sem er ekki vxlin og er ekki styttin fr vinstri.
d) Sni a ef hlfgrpa er styttin fr vinstri og hgri (.e., ef y+x = z+x er y=z) er hn grpa.