Introduction to Mathematical Logic

Inleiding wiskundige logica

Owner	Bachelor Wiskunde
Coordinator	dr. B. Afshari
Part of	Bachelor Wiskunde, year 1Dubbele bachelor Wis- en Natuurkunde, year 1Dubbele bachelor Wiskunde en Informatica, year 1Bachelor Bèta-gamma, major Wiskunde, year 2

Course manual 2021/2022

Course content

Dit vak biedt een inleiding in de twee belangrijkste formalismes uit de wiskundige logica: de propositielogica en de predicatenlogica; in beide gevallen worden zowel de formele taal, de semantiek als een afleidingssysteem (natuurlijke deductie) behandeld.

Wat betreft de propositielogica komen de volgende onderwerpen aan de orde: formules en inductie naar de complexiteit van formules, waarheidstafels, tautologieën en propositionele equivalenties, functionele volledigheid en disjunctieve normaalvormen, natuurlijke deductie, correctheid, volledigheid en compactheid (met bewijzen).

Van de predicatenlogica behandelen we de taal en semantiek van de eerste-orde logica, vertalen van natuurlijke taal naar de predicatenlogica, semantische begrippen als geldigheid en equivalentie, theorieën en axiomatiseringen, expressiviteit, natuurlijke deductie, correctheid, volledigheid en compactheid (zonder bewijs).

Study materials

Literature

Syllabus

• Introduction to Mathematical Logic, Bahareh Afshari, 2022 (available via Canvas pages)

Other

• Logic and Structure, Dirk van Dalen, Fifth Edition, 2013 (available online from UvA library)

• Logic in Computer Science, Michael Huth and Mark Ryan, 2008 (available online from UvA library)

• The Logic Manual, Volker Halbach Oxford University Press, 2010 (copies available from UvA library)

Objectives

• Studenten kunnen begrippen definiëren en beweringen bewijzen met behulp van formule-inductie.
• Studenten kunnen de waarheidstafel van een formule construeren.
• Studenten kunnen bepalen of een gegeven semantische gevolg-relatie geldt of niet.
• Studenten kunnen een formule omzetten in disjunctieve normaalvorm.
• Studenten kunnen geldige formules afleiden in het systeem van natuurlijke deductie.
• Studenten kunnen bewijzen dat het systeem van natuurlijke deductie correct en volledig is.
• Studenten kunnen bewijzen dat de propositielogica compact is.
• Studenten kunnen een bewering vanuit de natuurlijke taal vertalen naar de predicatenlogica.
• Studenten kunnen eenvoudige geldige formules afleiden in het systeem van natuurlijke deductie.
• Studenten kunnen van eenvoudige structurele eigenschappen bepalen of ze in de predicatenlogica uitdrukbaar zijn of niet.
• Studenten kunnen het verband uitleggen tussen de begrippen theorie, definieerbaarheid en axiomatisering.
• Studenten kunnen de betekenis en het belang van de begrippen correctheid, volledigheid en compactheid aangeven.
• Studenten kunnen logica in perspectief plaatsen ten op zichten van de wiskunde, computerwetenschappen en andere relevante disciplines.
• Studenten kunnen toepassingen van logica in andere vakgebieden herkennen.
• Studenten kunnen de logica gebruiken bij het oplossen van problemen.

Teaching methods

• Lecture
• Self-study
• Seminar

Learning activities

Attendance

Aanwezigheidseisen opleiding (OER-B):

• Van elke student wordt actieve deelname verwacht aan het onderdeel waarvoor hij/zij staat ingeschreven.
• Als een student door persoonlijke omstandigheden niet aanwezig kan zijn bij een verplicht onderdeel van het programma, dient hij/zij dit zo snel mogelijk schriftelijk te melden bij de betreffende docent en de studieadviseur.
• Het is niet toegestaan om verplichte onderdelen van een onderdeel te missen als er geen sprake is van overmacht.
• Bij kwalitatief of kwantitatief onvoldoende deelname, kan de examinator de student uitsluiten van verdere deelname aan het onderdeel of een gedeelte daarvan. Voorwaarden voor voldoende deelname worden van te voren vastgelegd in de studiewijzer en op Canvas.
• Bij alle onderwijseenheden van jaar 1 en 2 is een student verplicht bij minimaal 80% van de werkcolleges en tutoraten aanwezig te zijn. Bovendien moet worden deelgenomen aan eventuele tussentoetsen en verplicht gesteld huiswerk. Als niet aan deze verplichting is voldaan, wordt de student uitgesloten voor de herkansing van de onderwijseenheid. In geval van persoonlijke omstandigheden, zoals in OER-A Artikel 6.4 omschreven, wordt in overleg met de studieadviseur een afwijkende regeling voorgesteld.

Additional requirements for this course:

Aanwezigheid bij de werkcolleges is verplicht. Als je niet bij minstens 80% van de werkcolleges aanwezig bent geweest dan vervalt je recht op het hertentamen, zoals vermeldt in het OER-B artikel 4.9 lid 2.

Assessment

Item and weight	Details
Final grade
80% Final Exam
20% Assignments

De score op het tentamen moet minimaal 50/100 zijn.

Het huiswerk met de laagste score telt niet mee voor het eindcijfer.

Inspection of assessed work

The manner of inspection will be communicated via the lecturer's website.

Assignments

 Er zijn in totaal zes huiswerkopdrachten.

 

Fraud and plagiarism

The 'Regulations governing fraud and plagiarism for UvA students' applies to this course. This will be monitored carefully. Upon suspicion of fraud or plagiarism the Examinations Board of the programme will be informed. For the 'Regulations governing fraud and plagiarism for UvA students' see: www.student.uva.nl

Course structure

Timetable

The schedule for this course is published on DataNose.

Honours information

Op dit vak is geen honoursuitbreiding mogelijk.

Additional information

The course will be given in English.

Processed course evaluations

Hieronder vind je de aanpassingen in de opzet van het vak naar aanleiding van de vakevaluaties.

Contact information

Coördinator

• dr. B. Afshari