3.7. Feladatok

  1. Mennyi a formula értéke Gödel-féle, Łukasiewicz-féle, Kleene-féle, illetve szorzat logikában, ha , és ? Hogyan változna meg az érték, ha a Łukasiewicz-féle összekötőjelekkel ( és ) számolunk? Mennyi a formula értéke a megadott értékekkel számolva a Post-féle 6-, illetve 11-értékű logikában? Milyen más Post logikákban van értelme a kiértékelésnek? Modellezze a számításokat intervallum-értékekkel is!

  2. Mennyi a formula értéke Gödel-féle, Łukasiewicz-féle, Kleene-féle, szorzat, illetve a bitek ( -re skálázott) logikájában, ha , , és ? Hogyan változna meg az érték, ha a Łukasiewicz-féle összekötőjelekkel ( és ) számolunk? Hány értékű Post logikákban van értelme a kiértékelésnek? Mennyi az eredmény? Modellezze a számításokat intervallum-értékekkel is!

  3. Modellezze a Belnap-féle logikát intervallum-értékekkel!

  4. Modellezze a Post-féle logika műveleteit intervallum-értékekkel (használja az eltolás operátort)!

  5. Számítsa ki az intervallum-értékű paradigmával hogy a következő formulák kielégíthetőek-e!

    • ;

    • ;

    • ;

    • .

  6. Alkalmazza a prímfaktorizáció intervallum-értékű algoritmusát az számokra!

  7. Oldjon meg polinomiálisan sok lépésben egy legalább NP-teljes problémát az intervallum-értékű paradigmában (pl. partíció probléma: adott számhalmaz elemei két egyenlő összegű részre oszthatók-e, Hamilton-út probléma, gráfban maximális számosságú független csúcshalmaz kiválasztása, három színnel színezhető-e egy gráf, utazóügynök probléma)!

  8. (kutatási feladat) Hasonlítsa össze az intervallum-értékű paradigmát valamely más számítási paradigmával (pl. optikai számítások: D. Woods, T. J. Naughton: Optical computing, Applied Mathematics and Computation 215 (2009), 1417–1430; vektor-összeadó rendszerek: A. Thayse: Encoding of parallel program schemata by vector addition systems, International Journal of Parallel Programming 8 (1979), 209–218; stb.)!

  9. (kutatási feladat) Oldjon meg egy EXP-nehéz problémát polinomiális lépésszámú intervallum-értékű számítással!