Logica voor Informatici

Fout bij het aanmaken van de miniatuurafbeelding: Bestand is zoek

Prof. Jan Denef

Het gaat hier om het vak Wiskundige logica en structuren uit eerste Bachelor, niet om het licentie-vak Wiskundige logica, dat ook door Jan Denef gedoceerd wordt.

De informatica-studenten krijgen dit vak in het eerste semester van eerste Bachelor. Zij hebben in januari een schriftelijk examen. De andere studenten (met name wiskunde en fysica) volgen dit vak in het tweede semester. Zij hebben een schriftelijk examen in juni. De leerstof is grotendeels hetzelfde, al wordt er aan wiskunde en fysica een wat uitgebreider gedeelde algebraïsche structuren gegeven.

Komend academiejaar (2006-'07) zal dit vak verdwijnen. Informaticastudenten krijgen dan in het eerste semester van eerste Bachelor een vak Logica voor informatici. Wiskundestudenten krijgen in het eerste semester een vak Wiskundevaardigheden: bewijzen en redeneren, en in het tweede semester een vak Algebraïsche structuren. Al deze vakken zijn keuzevakken voor Fysicastudenten.

Inleiding

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, WinKe-bewijzen, beweringen uit Tarski-werelden, e.d... niks dat je niet gezien hebt. Voor structuren komt het grotendeels op hetzelfde neer.

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.

De puntenverdeling is als volgt:

• Logica (12 punten)
  • Theorie: 2 punten
  • Oefeningen: 10 punten
• Structuren (8 punten)
  • Theorie: 2 punten
  • Oefeningen: 6 punten

Examens

Vorige examens zijn te bezichtigen op de toledo-site voor het vak.

2006-06-19

Deel 1:

1. (2p) Bewijs de onvolledigheidsstelling van Gödel (voor een theorie met een eindig aantal zinnen).
2. (5p) Geef een trouwe vertaling van de volgende naar de Tarski-pred-taal van de volgende uitspraken:
   • Er staat juist één grote driehoek op het bord. (Relatie-identifiers: Triangle, Large)
   • Er staat juist één grote driehoek op het bord, en die staat achter alle vierkanten die links van alle vijfhoeken staan. (Relatie-identifiers: Triangle, Large, Square, LeftOf, Pentagon, BackOf)
3. (3p) Gegeven de zinnen
   • $(1)(\mathrm{\forall }x)[U(x)\to (\mathrm{\exists }y)R(y,x)]$
   • $(2)(\mathrm{\exists }x)[U(x)\wedge (\mathrm{\forall }y)(R(x,y)\to P(x,y))]$
   • $(3)(\mathrm{\forall }x)(\mathrm{\forall }y)[R(x,y)\to (R(y,x)\vee \mathrm{\neg }U(y))]$
   • $(4)(\mathrm{\exists }x)(\mathrm{\exists }y)P(x,y)$

   Bewijs dat zin 4 een logisch gevolg is van de eerst drie met een WinKE-bewijs, waarbij je elke stap motiveert.

4. (2p) Vervang in de vorige vraag zin 3 door
   • $(3^{\prime })(\mathrm{\exists }x)(\mathrm{\forall }y)R(x,y)$

   Bewijs dat zin 4 geen logisch gevolg is van 1, 2 en 3' door een DecaWorld te construeren die een tegenvoorbeeld vormt.

Deel 2:

1. (2p) Bewijs dat een groep waarvan de orde een priemgetal is, cyclisch is.
2. (3p)
   • (Wiskunde) Beschouw een pred-taal ${ℒ}$. We definieren een equivalentierelatie $\sim$ op de verzameling van alle zinnen van ${ℒ}$, door $A\sim B$ als en slechts als $A\leftrightarrow B$ logisch waar is. We definieren de klasse van A als $[A]=\{X|X\sim A\}$. Zij ${𝒜}$ de verzameling van alle klassen. Definieer een bewerking als $*:{𝒜}\times {𝒜}\to {𝒜}:([A],[B])\mapsto [(A\leftrightarrow B)]$. Bewijs dat * goed gedefinieerd is, en dat ${𝒜},*$ een commutatieve groep is met als neutraal element de klasse van een logisch ware zin. Bepaal ook de orde van elk element van de groep.
   • (Fysica en co) Bewijs dat er geen punt (x, y) met gehele coördinaten op de rechte met vergelijking ax + by = c ligt (waarbij a, b en c gehele getallen zijn) als en slechts als ggd(a, b) geen deler is van c.
3. (3p) Jan Denef en Evariste Galois spelen een wiskundige Russische roulette. Hierbij gebruiken ze een ronde kogelhouder met 257 kogelgaten. We nummeren het bovenste kogelgat met 0, en vervolgens met de klok mee van 1 tot 256. Het bovenste kogelgat blijft dus steeds nummer 0, ook al is de kogelhouder gedraaid en is dit een andere kogelgat geworden. Om de beurt schieten Jan en Evariste een keer op de ander, waarbij Jan als eerste schiet. Het zijn goede schutters, dus als ze schieten, raken ze hun doel ook. Er is echter slechts één kogel. Voor de eerste beurt bevindt die zich in het gat met nummer 256. Er wordt enkel geschoten als de kogel zich in het gat met nummer 0 bevindt.
   • Na elke beurt wordt de kogelhouder vijf eenheden gedraaid. Dus na $n\in \mathbb{\mathbb{N}}$ beurten bevindt de kogel zich in het kogelgat met nummer $256+5n(\mathrm{mod}257)$. Wie wordt als eerste geraakt, en na hoeveel beurten gebeurt dit?
   • Beschouw nu het geval waarbij de kogel na $n\in \mathbb{\mathbb{N}}\setminus \{0\}$ in het kogelgat met nummer $256+5^n(\mathrm{mod}257)$ bevindt. Wie wordt nu als eerste geraakt?

EXAMENVRAGEN 16-06-2005

1. In de onvolledigheidsstelling van Gödel wordt een voorwaarde gegeven ivm berekenbaarheid. Formuleer deze voorwaarde, geef uitleg, en geef een tegenvoorbeeld wanneer deze voorwaarde niet voldaan is.

2. Vertaal naar Tarski-predtaal: Zin 1: Er ligt hoogstens één driehoek achter alle vierkanten. Zin 2: Er ligt hoogstens één figuur achter alle vierkanten die er links van liggen.

3. Gegeven (1): (V x) { V(x) -> (V y) ( ~W(y) -> R(x,y) ) } (2): (V x) { V(x) -> (E y) ( S(y) /\ ~R(x,y) ) } Bewijs dat (3): (E x) { V(x) -> ( S(x) /\ W(x) ) } een logisch gevolg is van (1) en (2) mbv een winKE-waarheidsboom.

4. Gegeven: (1): (V y) { (E x) ( R(x,y) \/ V(x) ) -> (V x) ( V(x) /\ R(y,x) ) } (2): (V y) { (E x) ( R(x,y) /\ V(x) ) -> (V x) ( V(x) /\ R(y,x) ) } (3): (V x)(V y) { V(x) /\ R(y,x) } \/ (V x)(V y) { ~R(x,y) /\ ~V(y) } Kijk of (3) een gevolg is van (1) en (2), zo ja, geef een WinKE-bewijs, zo nee, geef een tegenvoorbeeld.

5. Formuleer en bewijs: de orde van een deelgroep van een eindige groep is…

6. Waar of niet waar en leg uit. (1) Zij K en L cyclische deelgroepen van een groep G. Dan is ( K(doorsnede)L ) ook cyclisch. (2) Zij G een eindige groep met minstens 2 elementen, en elk element heeft orde 1 of 2. Dan is G (=~) Z_(2,+)

7. Zij n € N, dan ‘bestaat er een n-voud dat in decimale schrijfwijze enkel uit 9’s bestaat’ <=> ‘ggd(n,10)=1’.