Wiskundige logica

Fout bij het aanmaken van de miniatuurafbeelding: Bestand is zoek

inleiding

Deze inleiding slaat op de vorm van dit examen zoals dit gegeven werd tot en met 2004. Een bijwerking is gewenst, gezien de veranderingen van het vak.

Van logica en structuren hebben jullie vanaf dit jaar blijkbaar 2 aparte (hopelijk nog steeds beiden schriftelijke) examens (logica in januari en structuren in juni), wat het waarschijnlijk iets eenvoudiger zal maken (vorige jaren was dit 1 vak uit het tweede semester, met 1 examen in juni). Onderschat dit toch niet, en vooral het logica-gedeelte niet! Je moet vlot oefeningen kunnen maken in de stijl van de oefenzittingen, maar altijd van de moeilijkste soort (meestal erg lange zinnen). Panikeer dus niet als je net je examen krijgt, en het ziet ernaar uit dat je nog geen halve vraag van de 7 vragen kan, begin er gewoon aan en dat loopt wel los. Oefeningen zijn dus bewijzen of iets al dan niet logisch waar is, een logisch gevolg van een (verzameling) zin(nen) is, winki-bewijzen, beweringen uit Tarski-werelden, e.d…niks dat je niet gezien hebt. Voor structuren komt het grotendeels op hetzelfde neer, maar aangezien er nu een apart examen voor is (en vroeger maakte dat maar 1 of 2 vragen meestal uit op het examen), zal er nu waarschijnlijk ook meer theorie over dat gedeelte gevraagd worden. De algemene regel is dat als je dit vak goed kon in de oefenzittingen, dat de examens ervan geen probleem zullen zijn om te maken. Let wel op: prof. Denef verbetert vrij streng, dus zorg ervoor dat alles zeker correct genoteerd is (niet al té intuïtief, maar in de juiste taal van de propositie- of predikatenlogica). Dit kan wel eens zorgen voor verassende (in de negatieve zin) resultaten als je je punten krijgt.

Examen juni 2005

1) Bewijs: een sigma-1-zin die waar is in N is bewijsbaar uit PA_0.

2) Vraag komt letterlijk uit cursus (ergens in laatste 11 blz van deel III): "Zij T een berekenbare theorie ... ... ... Bewijs dat de afbeelding N^2 -> N: (m,n) ->F(m,n) berekenbaar is.

Hierbij moet je twee dingen zeggen: - Omdat T berekenbaar is en omdat uit m het bewijs kan afgeleid worden kan men controleren of er effectief zo'n Theta te vinden op algoritmische wijze en dus ook met behulp van een masjien (hypothese van Church) - Vervolgens kun je starten met (omdat wegens de stelling van vraag 1 als theta(n,y) waar is ze bewijsbaar is) theta(n,0) voor bepaalde duur te trachten bewijzen uit PA_0. Stop en start met theta(n,1) voor bep. duur, stop start terug met theta(n,0). Stop en start dan met theta(n,2) etc. Dit allemaal zolang er geen bewijs gevonden wordt. (een dergelijk bewijs zal eens gevonden worden wegens semi-beslisbaarheid).

3) Geef trouwe vertaling in Tarski-predtaal: Minstens 2 driehoeken bevinden zich achter al de vierhoeken die rechts van alle vijfhoeken liggen.

4) Bewijs dmv WinKE bewijs: (3) is een logisch gevolg van (1) en (2).

   *1* (A x) (U(x) => (A y) (W(y) => ~R(x,y)))
   *2* (A x) (U(x) => (A y) (S(y) => R(x,y)))
   *3* (E x) (U(x) /\ W(x)) => (E y) ~S(y)

5) Bereken |{f:R->R| (E C) zodat C deelverz van R is en C eindig is en f constant is op R\C}|

Reservevraag: zeg alles wat je weet over de formule van Goedel

Andere vraag ipv. 5: Bewijs dat de afbeelding die n -> 2^n definieerbaar is. Maakt gebruik van de beta(n,u,v) in het lemma dat gebruikt wordt bij het bewijs van de definieerbaarheid van berekenbare relaties.