Naloga 09 - Zadovoljivost
Podana je sledeča logična izjava (+ označuje logični operator ALI, stik pa predstavlja logični operator IN):
(x + y)(y + z)
(a) Je podana logična izjava (že) v konjunktivni normali obliki (CNF)? Če ni, uporabite postopek opisan na predavanjih za pretvorbo le-te v CNF.
(b) S pomočjo uvedbe novih logičnih spremenljivk pretvorite logični izraz v izraz v 3-konjunktivni normalni obliki (3-CNF), ki je zadovoljiv natanko takrat, ko je prvoten logični izraz zadovoljiv.
(c) Logično izjavo v 3-CNF obliki (iz naloge (b)) pretvorite v neusmerjen graf (po postopku opisanem na predavanjih) in poiščite eno od minimalnih pokritij grafa. Kolikšen je pri tem budžet k?
Navodila za oddajo:
Pozorno preberite navodila - naloga ima tri pod-naloge, ki jih je potrebno rešiti.
Ne oddajajte "na roke" napisanih rešitev, ampak uporabite za to računalniški program - lahko je to urejevalnik slik, naprednejši urejevalnik besedil ali pa kak namenski program - reševanje "na papir" ter oddaja slik ali skenov ne bo upoštevana !!! Rešitev naloge oddajte v PDF obliki, ime datoteke naj bo <N09-PriimekIme.pdf> in naj vsebuje le črke angleške abecede (primer: N09-KavsekBranko.pdf)!
Oddaje, ki ne bodo v skladu s temi navodili, bodo zavrnjene in ocenjene z 0 točkami !!!