Sissejuhatus matemaatilisse loogikasse



Yüklə 7,9 Kb.
tarix13.11.2017
ölçüsü7,9 Kb.

SISSEJUHATUS MATEMAATILISSE LOOGIKASSE

Eksam 7.II 2003

D


  1. (15 p.) Vastata eksami esimese tunni jooksul:
    Defineerida:


    1. Teooria T on korrektne semantika S suhtes,

    2. Teooria T on täielik semantika S suhtes,

    3. Teooria T on vasturääkiv,

    4. Sekvents,

    5. Sekventsi valemkuju,
      Sõnastada, esitada:

    6. Formaalse aksiomaatilise teooria üldskeem (mis fikseeritakse konkreetse teooria defineerimiseks, milliseid tingimusi need komponendid peavad rahuldama),

    7. Mis on põhiline erinevus formaalse ja mitteformaalse aksiomaatilise meetodi vahel,

    8. Mida mõistame valemite semantika all,

    9. Lausearvutuse korrektsuse teoreem,

    10. Lausearvutuse täielikkuse teoreemi põhilemma,

    11. Predikaatarvutuse täielikkuse teoreem,

    12. Esimest järku teooriate korrektsuse teoreem,

    13. Võrduse aksioomid (mis lisati puhtale predikaatarvutusele)

    14. Kvantorite vasakule ja paremale sissetoomise tuletusreeglid.


2. (20 p.) Predikaadid, I järku keeled, interpretatsioonid.

  1. Anda valemid kahe predikaadi A(x) ja B(x) implikatsiooni ja ekvivalentsi tõesuspiirkondade leidmiseks A ja B tõesuspiirkondade kaudu,

  2. Kas trigonomeetrilised funktsioonid sin(x), cos(x) ja tan(x) sobivad reaalarvude hulgal defineeritud interpretatsioonis funktsionaalsümboli interpreteerimiseks? Miks? Aga lõigul [0,1] defineeritud interpretatsioonis?

  3. Leida reaalarvude hulga selline alamhulk, kus jagamistehe sobib funktsionaalsümboli interpretatsiooniks. Põhjendada valikut.

  4. Olgu interpretatsiooni kandjas 4 elementi: M = {a,b,c,d}. Mitu erinevat interpretatsiooni saab sellise kandja puhul anda konstantsümbolile? 1-kohalisele funktsionaalsümbolile?
    2-kohalisele predikaatsümbolile? Põhjendada.

  5. Konstrueerida signatuuris, mis koosneb predikaatsümbolist R(x,y), valem, mis on kehtestatav, aga pole tõene ühelgi lõpliku kandjaga interpretatsioonil. Tõestada, et valemil on nõutud omadused. Näpunäide: võtta eeskujuks range võrduse omadused mingil lõpmatul hulgal (näiteks N, Z, R).


3. (15 p.) Turingi masinate hargnemine

  1. Anda hargnemise definitsioon.

  2. Selgitada, mida tähendab kolmeks haruks hargnemine võrreldes IF-THEN-ELSE-konstruktsioonide kahe haruga programmeerimiskeelte süntaksis.

  3. Selgitada, mida tähendab kompositsioon tingimuse kontrollimise masinaga võrreldes IF-THEN-ELSE-konstruktsiooniga,

  4. Sõnastada teoreem hargnemisest ja tõestada,

  5. Kas ja kuidas mõjutab teoreemi tõestuseks antavat konstruktsiooni asjaolu, et tingimuse kontrolli masin võib lõpetada oma töö juhtimise andmisega tabeli tühja lahtrisse?


3A (MLE eksami tegijatele, 15 p.). Elementaarkonjunktsioonide ja DNK tõesuspiirkonnad.

  1. Sõnastada lemma täieliku elementaarkonjunktsiooni tõesuspiirkonna kohta.

  2. Sõnastada ja tõestada teoreem TDNK olemasolu kohta.

  3. Milline on samaselt tõese valemi TDNK?

  4. Millises vahekorras on valemite A(X,Y) ja B(X,Y) TDNK-d, kui kumbki nendest valemitest ei järeldu teisest?

  5. Kui pika ainult muutujaid X ja Y sisaldavate valemite jada A1,…,An saab moodustada, kus ükski valem pole teisega samaväärne ja iga i>1 korral valem Ai järeldub eelmisest valemist ? Tuua näide.


Dostları ilə paylaş:


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2019
rəhbərliyinə müraciət

    Ana səhifə