Logic

• The fragment of logic that we consider is popularly known as predicate logic or first order logic.
• Basic entities in predicate logic are predicates.

Propositional Logic

• An atomic proposition is a term that is either true or false.
• Propositional logic deals with combining propositions using logical connectives to form formulas which are complicated statements.
• Common logical connectives used in propositional logic are ∨ (or– disjunction), ∧ (and– conjunction), ¬ (not– negation), ⊃ or → (implies), ≡ or ↔ (iff– equivalence).

Atomic Proposition

• Propositions are the basic building blocks of logic.
• An atomic proposition or just a proposition is a declarative sentence that is either true or false but not both.
• Examples of propositions:
  • New Delhi is the capital of India.
  • 2 + 3 = 5.
  • 3 + 3 = 8.
  • Today is Friday.

Propositional Logic: Syntax

• P = $\{p_0, p_1, . . .\}$ is a countably infinite set of propositions.
• The set Φ of formulas of propositional logic is the smallest set satisfying the following conditions:
  • Every atomic proposition is a member of Φ.
  • If α is a member of Φ, so is ¬α.
  • If α and β are members of Φ so is α ∨ β.

Derived Operators

• And: α ∧ β: ¬(¬α ∨ ¬β)
• Implies: α ⊃ β: ¬α ∨ β
• Iff: α ≡ β: (α ⊃ β) ∧ (β ⊃ α).

Propositional Logic Formulas: Examples