SCV0314 - LOGIC

courses

ID:

SCV0314

Duration (hours):

48

CFU:

SSD:

LOGICA MATEMATICA

Located in:

Varese - Università degli Studi dell'Insubria

Year:

2025

Date/time interval

Secondo Semestre (23/02/2026 - 29/05/2026)

Course Objectives

(1) Knowledge and understanding skills The course aims at providing basic knowledge of logical inferences, through the study of the basic notions of classical propositional logic and of first order logic. Such knowledge is aimed at forming and increasing the abstraction of information through symbolic representation and thus the ability to understand an abstract and symbolic scientific language. (2) Knowledge and understanding skills applied Some insights into more applicative tools such as SAT-solver and non-classical (modal and fuzzy) logic for program verification will be mentioned. (3) Autonomy of judgment and communication skills Expected learning outcomes include the ability to identify any errors in a mathematical argument, and to have a language property that can enunciate a theorem and describe its demonstration. (4) Ability to learn Logical mechanisms of mathematical reasoning enable the acquisition of adequate skills for improving our own knowledge and the individual development of new skills.

Course Prerequisites

For a proficient learning of this course, the student has to master the mathematical notions and the proving techniques taught in the fundamental course in Algebra and Geometry during the first year, which is, in any case, compulsory to pass before taking this examination. In particular the following notions and techniques are essentials: - Basis of discrete mathematics: theorems, and proof methods: implications, counter-nominal, reductio at absurdum, proof by induction. - Set theory: set, membership and inclusion, subset, power set, cardinality, set operations (union, intersection and complement), pairs and cartesian product, counting the elements of a finite set. - Relations: relations, properties (reflexivity, symmetry, transitivity), equivalence relations, equivalence class, quotient set, partitions, order relations, least and greatest element, least and upper bounds. - Functions: domain and codomain, range and preimage, injective, surjective and bijective functions, inverse of bijective functions, function composition.

Teaching Methods

32h lectures + 24h Exercises. The teaching activities alternates the presentations of notions and theorems and their application to the solution of exercises; students are expected to actively participate in exercises discussion. The presented exercises have an essential role in preparing the final exam.

Assessment Methods

The exam aims to verify the acquisition and the correct understanding of the contents of the course. The exam is written, lasts 90 minutes, and consists of different exercises of the kind discussed during class. The exam is composed by approximately 3/4 questions that participate in equal measure to the final grade of 31/30 (for cum laude).

Introduction to logic (goals 1-4) • What is logic: historical introduction • Language and Metalanguage • Syntax and Semantics • Satisfiability and Entailment • Proof methods: direct proofs. • Soundness of direct proofs. Failure of completeness • Indirect proofs: soundness and completeness (sketch) Propositional Logic (goals 1-4) • What is logic: inferential methods and deduction. The language of propositional logic. Propositional connectives. Semantics of Propositional Logic. Truth tables. Satisfiable formulas and tautologies. • Satisfiable sets, logical consequences, deduction theorem. Logical Equivalence, Algebra of Equivalence Classes of formulas, Boolean Algebras. Functional completeness and DNF and CNF. The fundamental equivalences, transformation of a formula into normal form. • König's Lemma and Compactness Theorem. • Automatic demonstration methods: the Tableaux. Completeness and correctness theorem for tableaux, Hintikka set. • Other deductive systems: Sequents. Clauses, resolution, Davis Putnam's procedure, completeness and correctness of the Davis-Putnam procedure. Krom clauses and Horn clauses Logic of Predicates (goals 1-4) • The language of the logic of predicates, terms, and formulas. Range of action of a quantifier, free and bound variables, substitutions. • Structures, interpretations and evaluations. Satisfiable and valid forms. Models of a formula. Logical equivalences for logic of predicates. Normal form, Skolem formulas. Transformation of a formula in Skolem form and equisatisfiability. • Tableaux for logic of the predicates, theorem of soundness and completeness for the tableaux