II.1 Introduction

Logic [Slide 18]

Logic is a tool for careful reasoning.

• Software and hardware development

  • Formal logic can lead to defect-free products
  • Heavily used in chip design (since Pentium disaster)
  • Used in safety-critical software design
  • Positive influence on all software development

• Foundation for programming languages (PL)

  • Together with Functions (Lambda calculus) form the semantic base for all PLs
  • Type checking and type inference - basis in logic
  • Computation model - limits of expressiveness

• Artificial intelligence, database systems

  • Grounded in formal logic

Propositional Logic [Slide 19]

• Proposition - atomic entity, true or false

  • letters P,Q,... denote propositional variables standing for specific propositions P,Q,… specific propositions - value: true or false
  • letters f,f₁,f₂,… are meta-variables denoting propositional variables or formulae f,f₁,f₂,… value: proposition, such as P, (P ∧ Q)

• Propositional Calculus

  • Scheme for calculating with logic formulae

• Three different propositional calculi

  • semantics-based reasoning - truth table
  • syntax-based reasoning - inference rules
  • equational reasoning - Boolean algebra

Logical Operators [Slide 20]

Logical operators provide ways to combine propositions for calculation. These are:

• ∧ (And)

  • P ∧ Q,(P ∧ Q) ∧ R,…

• ∨ (Or)

  • P ∨ Q,P ∨ (Q ∨ R),…

• ¬ (Not)

  • ¬P,((¬P) ∧ Q),…

• ⊃ (Implication)

  • P ⊃ Q,(P ∧ Q) ⊃ Q,…

• ≡ (Equivalence)

  • P ≡ Q,(P ∧ Q) ≡ (Q ∧ P),…