Loogilise programmeerimise loenguülesanded

  1. (2. sept., järgmiseks loenguks) Olgu antud valem
    (¬A→B)∨((A∧¬C)↔B).
    Konstrueerige sellega ekvivalentne DNK-l valem ja ekvivalentne KNK-l valem.
    Kasutage kas rekursiivset teisendust või tõeväärtustabelit.

  2. (9. sept., tähtaeg 13. sept.) Rakendage märkimisalgoritmi Horni valemile
    F = (¬A∨¬B∨¬D) ∧ ¬E ∧ (¬C∨A) ∧ C ∧ B ∧ (¬G∨D) ∧ G.

  3. (13. sept., tähtaeg 16. sept.) Olgu meil aparaadid järgmiste keemiliste reaktsioonide sooritamiseks.
    MgO + H2 → Mg + H2O
    C + O2 → CO2
    H2O + CO2 → H2CO3
    Tõestage (märkimisalgoritmiga), et nendel eeldustel saab algmaterjalidest MgO, H2, O2 ja C valmistada süsihapet H2CO3.

  4. (16. sept., tähtaeg 20. sept.) Olgu M lõpmatu valemite hulk, mille iga lõplik osahulk on kehtestatav. Oletame, et ükski M valem ei sisalda atomaarset valemit A723. Seepärast eeldame, et ükski väärtustus An kompaktsusteoreemi tõestuses ei ole defineeritud A723-l. Leidke tõestuse poolt antav A723 väärtus.

  5. (23. sept., tähtaeg 27. sept.) Tooge lihtne näide valemite hulga M väärtustuse A leidmisest konkreetsetel lausemuutujatel An väärtustuste Ai kaudu. (Lõpmatust võib vajadusel ignoreerida.)
  6. (27. sept., tähtaeg 30. sept.) Määrake järgmise disjunktihulga jaoks Resn(F), n=0,1,2,...
    {{A,¬B,C},{B,C},{¬A,C},{B,¬C},{¬C}}.

  7. (7. okt., tähtaeg 14. okt.) Näidake resolutsioonipuuga, et A∧B∧C järeldub disjunktihulgast
    {{¬A,B},{¬B,C},{A,¬C},{A,B,C}}.

  8. (18. okt., tähtaeg 21. okt.) Tõestada induktsiooniga valemi struktuuri järgi tõlkimislemma
    A(F[x/t]) = A[x/A(t)](F),
    kus F on term või valem, t on kinnine term ja A on nende jaoks sobiv struktuur.
    F[x/t] tähendab F kõigi vabade muutujate asendatamist termiga t.

  9. (25. okt., tähtaeg 1. nov.) Vormistage prefikskuju teoreemi (4.4) tõestusele vastav algoritm.

  10. (4. nov., tähtaeg 8. nov.) Teisendage valem
    ∀z∃y(P(x,g(y),z) ∨ ¬∀xQ(x)) ∧ ¬∀z∃x¬R(f(x,z),z)
    disjunktihulgaks, rakendades järgemööda järgmisi teisendusi:
    1. Rektifitseerimine.
    2. Olemasolukvantorite lisamine valemi algusse vabade muuutujate sidumiseks.
    3. Prefikskuju.
    4. Skolemi kuju.
    5. Konjunktiivne normaalkuju.

  11. (8. nov., tähtaeg 15. nov.) Leidke järgmise Posti vastavusprobleemi lahend:
    ((001,0),(01,011),(01,101),(10,001))
    (Hoiatus: lühim lahend koosneb 66 indeksist. Arvutit kasutamata saab lahendi konstrueerida "tagantpoolt ettepoole".)

  12. (25. nov., tähtaeg 29. nov.) Näidake, et Posti vastavusprobleem on poollahenduv.

  13. (29. nov., tähtaeg 2. dets.) Tõestage kinnise resolutsiooniga, et esimesest väitest järeldub teine.
    1. Professor on õnnelik, kui kõigile tema üliõpilastele meeldib loogika.
    2. Professor on õnnelik, kui tal pole ühtegi üliõpilast.

  14. (6. dets., tähtaeg 9. dets.) Näidake, mis toimub unifitseerimisalgoritmis literaalide hulgal
    L={P(x,y),P(f(a),g(x)),P(f(z),g(f(z)))}

  15. (9. dets., tähtaeg 13. dets.) Vaatleme järgmist kinnist resolutsiooni.
    C1= {P(x,y),P(f(a),z)}, C2= {¬P(f(x),g(y)),Q(x,y)}
    C'1= {P(f(a),g(b))},  C'2= {¬P(f(a),g(b)),Q(a,b)}
    R'= {Q(a,b)}
    Järgige tõstmislemma tõestust ja leidke, milline (predikaatloogika) resolutsioonisamm sellest konstrueeritakse.

  16. (13. dets., tähtaeg 16. dets.) Väljendage järgmised faktid predikaatloogika valemitena.
    1. Iga draakon on õnnelik, kui kõik tema lapsed oskavad lennata.
    2. Rohelised draakonid oskavad lennata.
    3. Draakon on roheline, kui ta on vähemalt ühe rohelise draakoni laps.
    Näidake resolutsiooniga, et eeldustest 1–3 järeldub, et kõik rohelised draakonid on õnnelikud.