Part1

Page 1: Introduction to Mathematical Logic

  • Symbols and notation in mathematical logic:

    • Common symbols include: → (implication), ¬ (negation), ↔ (biconditional), ≡ (equivalence).

    • Quantifiers: ∀ (for all), ∃ (there exists).

    • Logical operators: ⋀ (and), ⋁ (or).

Page 2: Plan

  • Chapter structure of the document:

    • Introduction

    • Chapter I: Propositional Logic

    • Chapter II: Predicate Logic

Page 3: References

  • Key texts in mathematical logic:

    • Principia Mathematica by Alfred North Whitehead and Bertrand Russell (1997, originally published in 1910).

    • Introduction à la logique by Alfred Tarski (1971).

    • Logique mathematique, tome 1 by Cori R. and Lascar D. (2003).

    • Logique pour l'informatique et pour l'intelligence artificielle by Ricardo Caferra (2010).

Page 4: Introduction to Mathematical Logic

  • Definition of mathematical logic

    • Fundamental questions regarding logic and computing.

    • Overview of logical systems.

Page 5: Definition of Mathematical Logic

  • Mathematical logic:

    • A discipline introduced at the end of the 19th century.

    • Focuses on mathematics as a language.

    • Establishes the truth value of propositions.

    • Aims to construct mathematical reasoning.

Page 6: Interaction Between Logic and Computing

  • Applications include:

    • Computer architecture

    • Algorithmic complexity

    • Expert systems

    • Ontologies and semantic web

    • Automated theorem provers.

Page 7: Logical Systems

  • Components of logical systems:

    • Formulas: Mathematical statements formally expressed using combinatorial methods (like symbols and trees).

    • Semantics: Associating meanings (true or false) to formulas to define their validity.

    • Deduction: Deriving new formulas from initial ones (axioms) using rules.

Page 8: Propositional Logic - Chapter I

  • Key topics covered include:

    • Definition of a proposition.

    • Connectives and formulas.

    • Truth tables.

    • Concepts like tautology, contradiction, equivalence.

    • Normal forms (CNF, DNF).

    • Resolution methods.

Page 9: Objectives of Propositional Calculus

  • Goals include:

    • Writing formulas (syntax).

    • Determining the truth value of a formula (semantics).

    • Proving new results (deduction).

Page 10: Definition of Proposition

  • A proposition:

    • An assertion that can be either true or false.

    • Examples:

      • All men will die (true).

      • Socrates is a liar (debatable).

      • Every prime number is odd (false).

      • 1 + 1 = 2 (true).

    • Non-examples:

      • What are you doing here? (interrogative).

      • I cannot believe my eyes! (exclamative).

      • Be quiet! (imperative).

Page 11: Propositional Variables

  • Representing propositions:

    • Examples of representation:

      • All men will die is represented as P.

      • Socrates is a liar as Q.

      • Every prime number is odd as R.

      • 1 + 1 = 2 as S.

    • Principles that propositional values must satisfy:

      • Identity Principle: P is P.

      • Non-Contradiction Principle: P cannot be both true and false.

      • Law of Excluded Middle: P is either true or its negation is true.

Page 12: Logical Connectors

  • Logical connectives allow the construction of new propositions:

    • Connectors include:

      • Disjunction (or, ⋁)

      • Implication (implies, →)

      • Equivalence (equivalent to, ↔)

    • Priorities:

      • Negation (¬) has higher priority.

      • Conjunction (⋀) has lower priority than disjunction (⋁).

Page 13: Truth Tables

  • Propositions can have two truth values: TRUE (V) or FALSE (F).

    • Important distinction between the proposition and its truth value.

    • Example truth table:

      • P Q:

      • V V, V F, F V, F F.

Page 14: Exercises

  • Determine the truth values of propositions and write their negations:

    • Example propositions:

      • 5 is less than 10

      • 5 is even.

    • Translate propositions into propositional language and compute truth values using truth tables.

Page 15: Exercise Solutions

  • Truth values of propositions:

    • P: 5 is less than 10 (True).

      • ¬P: 5 is greater or equal to 10 (False).

    • Q: 5 is even (False).

      • ¬Q: 5 is odd (True).

    • Translations:

      • 5 is less than 10 AND 5 is even ≡ (P⋀Q) is False.

      • 5 is less than 10 OR 5 is even ≡ (P⋁Q) is True.

      • If 5 is less than 10, then 5 is even ≡ (P→Q) is False.