# Matematica | MATHEMATICAL LOGIC

## Matematica MATHEMATICAL LOGIC

 0512300042 DIPARTIMENTO DI MATEMATICA EQF6 MATHEMATICS 2020/2021

 OBBLIGATORIO YEAR OF COURSE 3 YEAR OF DIDACTIC SYSTEM 2018 PRIMO SEMESTRE
SSD CFU HOURS ACTIVITY TYPE OF ACTIVITY MAT/01 7 56 LESSONS SUPPLEMENTARY COMPULSORY SUBJECTS
Objectives
CRITICAL KNOWLEDGE OF LOGICAL CONNECTIVES, QUANTIFIERS, LAWS THAT REGULATE THEM AND THE MAIN TECHNIQUES FOR THEIR FORMAL STUDY. CRITICAL KNOWLEDGE OF FORMAL SYSTEMS AND THEIR MOST RELEVANT PROPERTIES.

** EXPECTED LEARNING OUTCOMES:
* KNOWLEDGE AND UNDERSTANDING

- KNOWLEDGE OF THE SYNTAX OF PROPOSITIONAL AND FIRST-ORDER LOGIC.
- KNOWLEDGE OF THE SEMANTICS OF PROPOSITIONAL LOGIC AND FIRST-ORDER LOGIC.
- KNOWLEDGE OF NATURAL DEDUCTION FOR PROPOSITIONAL AND FIRST-ORDER LOGIC.
- KNOWLEDGE OF BOOLEAN ALGEBRAS AND THEIR REPRESENTATION
- KNOWLEDGE OF THE COMPLETENESS OF PROPOSITIONAL LOGIC AND FIRST-ORDER LOGIC.
- KNOWLEDGE OF THE COMPACTNESS OF PROPOSITIONAL AND FIRST-ORDER LOGIC.
- KNOWLEDGE OF THE MAIN APPLICATIONS OF COMPACTNESS AND COMPLETENESS OF FIRST-ORDER LOGIC.

* ABILITY TO APPLY KNOWLEDGE AND UNDERSTANDING

- ABILITY TO RIGOROUSLY AND CONSCIOUSLY REPRODUCE THE PROOFS OF THE MAIN COURSE RESULTS.
- ABILITY TO RECOGNISE AND PROVIDE EXAMPLES OF TAUTOLOGIES, CONTRADICTIONS AND SATISFIABLE SETS OF FORMULAS.
- ABILITY TO PUT PROPOSITIONAL AND FIRST-ORDER FORMULAS INTO NORMAL FORM.
- ABILITY TO BUILD CORRECT NATURAL DEDUCTIONS.
- ABILITY TO FORMALIZE MATHEMATICAL STATEMENTS IN FIRST-ORDER LANGUAGE
- ABILITY TO APPLY THE MAIN THEOREMS IN SPECIFIC CASES.
- ABILITY TO CONNECT THE VARIOUS COURSE TOPICS TOGETHER.

** AUTONOMY OF JUDGMENT
THE STUDENT WILL BE ABLE TO PROVE OR REFUTE SIMPLE STATEMENTS ABOUT THE COURSE TOPICS.

** COMMUNICATION SKILLS
THE STUDENT WILL BE ABLE TO FULLY AND RIGOROUSLY DESCRIBE THE MAIN CONCEPTS SEEN DURING THE COURSE.
Prerequisites
BASIC KNOWLEDGE OF ALGEBRA AND SET THEORY
Contents
PROPOSITIONAL LOGIC (20 HOURS):
- THE SYNTAX OF PROPOSITIONAL LOGIC. TRUTH TABLES. SATISFIABILITY. TAUTOLOGIES.
- NATURAL DEDUCTION. FORMAL THEOREMS.
- THE SAT PROBLEM. RESOLUTION METHOD. THE PROBLEM P = NP
- THE DEDUCTION THEOREM FOR PROPOSITIONAL LOGIC.
- THE COMPLETENESS THEOREM FOR PROPOSITIONAL LOGIC.
- THE COMPACTNESS THEOREM PROPOSITIONAL LOGIC.

BOOLEAN ALGEBRAS (14 HOURS):
- PARTIALLY ORDERED SETS. LATTICES. BOOLEAN ALGEBRAS.
- FIRST PROPERTIES OF BOOLEAN ALGEBRAS. FILTERS IN BOOLEAN ALGEBRAS. ULTRAFILTERS AND THEIR CHARACTERIZATIONS. THE ULTRAFILTER THEOREM. STONE THEOREM. THE LINDENBAUM ALGEBRA OF PROPOSITIONAL CALCULATION. ALGEBRAIC COMPLETENESS OF THE PROPOSITIONAL CALCULATION.

FIRST-ORDER LOGIC (22 HOURS):
- THE LANGUAGE OF FIRST-ORDER LOGIC. QUANTIFIERS.
- FIRST ORDER STRUCTURES. REALIZATIONS AND MODELS OF FIRST-ORDER FORMULAS.
- NATURAL DEDUCTION FOR THE FIRST ORDER. FORMAL THEOREMS.
- SETS OF CONSISTENT FORMULAS.
- COMPLETENESS OF FIRST-ORDER LOGIC.
- COMPACTNESS THEOREM FOR FIRST-ORDER LOGIC
- APPLICATIONS OF COMPACTNESS AND COMPLETENESS. EXPRESSIVE LIMITATIONS OF THE FIRST ORDER LOGIC.
Teaching Methods
THE COURSE INCLUDES THEORETICAL LESSONS WITH GROUP DISCUSSIONS (7CFU) IN THE CLASSROOM. DURING THE DISCUSSIONS, STUDENTS (POSSIBLY IN GROUPS) SOLVE THEORETICAL PROBLEMS WHICH WILL THEN BE USED TO ACHIEVE MORE INVOLVED RESULTS. THIS LAST PHASE PROMOTES THE ABILITY TO IMAGINE POSSIBLE STRATEGIES TO FORMALIZE INTUITIONS AND TO BUILD COMPLEX CONCEPTS STARTING FROM BASIC ONES.
Verification of learning
THE EXAM AIMS TO EVALUATE THE WHOLE KNOWLEDGE AND UNDERSTANDING OF THE CONCEPTS INTRODUCED DURING THE LECTURES, AS WELL AS THE ACCURACY AND INDEPENDENCE IN USING SUCH TOOLS.

THE EXAMINATION CONSISTS OF AN ORAL INTERVIEW WHERE IT WILL BE EVALUATED THE KNOWLEDGE ACQUIRED ON BASIC AND MOST ADVANCED CONCEPTS IN PROPOSITIONAL LOGIC, FIRST-ORDER LOGIC AND BOOLEAN ALGEBRAS.

THE FINAL MARK IS UP TO THIRTY. LAUDEM WILL BE ATTRIBUTED TO STUDENTS THAT PROVE THEMSELVES TO BE ABLE TO INDEPENDENTLY USE THE KNOWLEDGE AND SKILLS ACQUIRED ON THE MOST ADVANCED TOPICS OF THE COURSE, AND ARE ABLE TO FIND CONNECTIONS WITH CONTEXTS DIFFERENT THAN THOSE PRESENTED IN THE LECTURES.
Texts
- DIRK VAN DALEN - LOGIC AND STRUCTURE. FOURTH EDITION. SPRINGER 2008.

- LECTURE NOTES.