Introduction to Mathematical Logic

Inleiding wiskundige logica

Course manual 2023/2024

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, 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

• Bahareh Afshari, Introduction to Mathematical Logic (wordt aangeboden via Canvas)

Other

• van Benthem, van Ditmarsch, Ketting en Meyer-Viol, Logica voor informatici, Tweede Editie, 1991. 

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 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
• Seminar
• Self-study

In de hoorcolleges zal de theorie worden geïntroduceerd en zullen de belangrijkste bewijzen gegeven worden; details die niet in het hoorcollege aan bod komen dienen de studenten zelf te bestuderen in de syllabus. In de werkcolleges kunnen de studenten oefenen met het toepassen van de theorie. 

Learning activities

Attendance

Programme's requirements concerning attendance (OER-B):

• Each student is expected to actively participate in the course for which he/she is registered.
• If a student cannot be present due to personal circumstances with a compulsory part of the programme, he / she must report this as quickly as possible in writing to the relevant lecturer and study advisor.
• It is not allowed to miss obligatory parts of the programme's component if there is no case of circumstances beyond one's control.
• In case of participating qualitatively or quantitatively insufficiently, the examiner can expel a student from further participation in the programme's component or a part of that component. Conditions for sufficient participation are stated in advance in the course manual and on Canvas.
• In the first and second year, a student should be present in at least 80% of the seminars and tutor groups. Moreover, participation to midterm tests and obligatory homework is required. If the student does not comply with these obligations, it can be decided to deny the positive effects of homework to be counted towards the final grade of the course. In case of personal circumstances, as described in OER-A Article A-6.4, a different arrangement will be proposed in consultation with the study advisor.

Assessment

De score op het tentamen moet minimaal 5,5/10 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 digitial learning environment.

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

Honours information

Op dit vak is geen honoursuitbreiding mogelijk.

Contact information

Coordinator

• Lide Grotenhuis MSc

Staff

• Christopher van Altena
• Daan Hoogcarspel
• Rick Klarenberg