The unit addresses the mandatory requisites in mathematical logical foreseen in the ACM 2008 CS Curriculum (Discrete Structures: DS/BasicLogic [core]). In addition to those above, this document includes as objective the application of formal methods of propositional and predicate logic.

Knowledge

• Syntax and semantics of propositional and first-order logic
• Resolution methods for propositional and first-order logic
• Natural deduction systems for propositional and first-order logic

Skills

• Specification logical formulae from descriptions in natural language
• Assessment of the logical validity of formulae, semantically, axiomatically, and syntactically
• Use resolution algorithms to establish the logical validity of formulae

Competences

• Ability of abstract and rigorous reasoning
• Ability of manipulating formal structures
• Learn to learn

1. Propositional Logic
1.1. Syntax:
• Inductive definition of propositional language
1.2.Semantics:
• Truth tables and Boolean algebra
• Valoration and interpretation structure: satisfaction
1.3 Deductive systems and Decision Algorithms
• Natural deduction: Introduction and elimination rules
• Resolution: Clausal form, Horn algorithm
2. First Order Logic
2.1. Syntax:
• Alphabet and first order language
• Terms from natural language descriptions
• Free variables and substitution
2.2. Semantics:
• Valoration and interpretation structure: satisfaction relation
2.3. Deductive systems and Decision Algorithms
• Natural deduction: Introduction and elimination rules
• Resolution: Clausal form, Skolemisation, Unification
3. Mathematical Induction

Main textbook:

• Language, Proof, and Logic, David Barker-Plummer, Jon Barwise, John Etchemendy, Center for the Study of Language and Information; 2nd edition, October 2011.

Additional reading:

• Mathematical Logic: a course with exercices. Part I: propositional calculus, boolean algebras, predicate calculus, René Cori e Daniel Lascar, Oxford Press, 2007.

• A First Course in Logic: An Introduction to Model Theory, Proof Theory, Computability, and Complexity, Shawn Hedman, Oxford Texts in Logic, 2004.

• Logic in Computer Science: modelling and reasoning about systems (2nd edition), Michael Huth and Mark Ryan, Cambridge University Press, 2004