Problem J
Röknet

Inni í hverri tölvu má finna svokölluð röknet. Þessi net eru notuð til að reikna gildi röksegða, og mynda því grunninn að flóknari reikningum sem tölvan framkvæmir. Röknet samanstanda af mismunandi gerðum af hlutum sem geta haft allt að tvo innganga og allt að einn útgang. Hlutur tekur sanngildi inn um þessa innganga, framkvæmir einhverja einfalda reglu til að búa til nýtt sanngildi, og sendir það svo út um útganginn. Þessa hluti er svo hægt að tengja saman þannig að útgangur á einum hlut er tengdur við inngang á öðrum hlut. Hlutirnir mynda því net sem sanngildi ferðast í gegnum.

Í þessu verkefni ætlum við að skoða fimm gerðir af hlutum:

• OG rökhlið hefur tvo innganga. Ef báðir inngangarnir eru sannir, þá er satt sent út um útganginn, en ósatt annars.

• EDA rökhlið hefur tvo innganga. Ef báðir inngangarnir eru ósannir, þá er ósatt sent út um útganginn, en satt annars.

• EKKI rökhlið hefur einn inngang. Ef inngangurinn er sannur, þá er ósatt sent út um útganginn, en satt annars.

• INNTAK hefur engan inngang en einn útgang. INNTAK er sérstakur hlutur sem notaður er til að senda alltaf sama sanngildið út um útganginn.

• UTTAK hefur einn inngang en engan útgang. UTTAK er sérstakur hlutur sem notaður er til að skoða hvaða sanngildi kemur inn um innganginn.

Í eftirfarandi mynd sjáum við dæmi um svona röknet.

Figure 1: Mynd af fyrsta sýnidæminu

Gefin lýsing á svona rökneti, getur þú reiknað hvaða sanngildi koma í UTTAK hlutina?

Inntak

Á fyrstu línu er jákvæða heiltalan $N$ sem táknar fjölda hluta í röknetinu. Svo fylgja $N$ línur, ein fyrir hvern hlut. Það eru fimm gerðir af línum eftir því um hvers konar hlut er að ræða:

• INNTAK nafn sanngildi táknar hlut af gerðinni INNTAK að nafni nafn sem sendir sanngildið sanngildi út um útganginn.

• UTTAK inn táknar ónefndan hlut af gerðinni UTTAK. Inngangur hlutarins er tengdur við útgang hlutarins að nafni inn.

• OG inn1 inn2 nafn táknar OG rökhlið að nafni nafn. Inngangar rökhliðsins eru tengdir við útganga hlutanna sem heita inn1 og inn2.

• EDA inn1 inn2 nafn táknar EDA rökhlið að nafni nafn. Inngangar rökhliðsins eru tengdir við útganga hlutanna sem heita inn1 og inn2.

• EKKI inn nafn táknar EKKI rökhlið að nafni nafn. Inngangur rökhliðsins er tengdur við útgang hlutarins að nafni inn.

Nafn hlutanna eru mismunandi og samanstanda af enskum lágstöfum og tölustöfum. Ef útgangur hlutar $A$ er tengdur við inngang hlutar $B$, þá mun hlutur $A$ vera skilgreindur í inntakinu áður en hlutur $B$ er skilgreindur í inntakinu.

Úttak

Fyrir hvern hlut af gerð UTTAK á að skrifa út eina línu með nafninu á inngangnum og sanngildinu sem kemur inn um innganginn; SATT ef það er satt, OSATT ef það er ósatt. Þessar línur eiga að koma í sömu röð og hlutirnir af gerð UTTAK eru skilgreindir í inntakinu.

Stigagjöf

Lausnin mun verða prófuð á miserfiðum inntaksgögnum, og er gögnunum skipt í hópa eins og sýnt er í töflunni að neðan. Lausnin mun svo fá stig eftir því hvaða hópar eru leystir.

11
INNTAK 1 SATT
INNTAK 2 SATT
EKKI 2 3
OG 1 3 4
INNTAK 8 SATT
EDA 8 4 9
UTTAK 9
INNTAK 5 OSATT
EDA 4 5 6
EKKI 6 7
UTTAK 7

9 SATT
7 SATT

6
INNTAK banani SATT
UTTAK banani
INNTAK epli OSATT
UTTAK epli
UTTAK banani
INNTAK gurka SATT

banani SATT
epli OSATT
banani SATT