／var／logmarcus chiu

Propositional Logic - Propositional Calculus - Sentential Logic - Statement Logic

Created on · Last Modified on

Propositional Logic or Propositional Calculus (aka Sentential Logic and Statement Logic)

  • the logic of propositions (i.e. statements)
  • is the branch of logic that studies:
    • methods of joining and/or modifying propositions
    • the logical relationships and properties that are derived from these methods of joining and/or modifying propositions

Syntax & Semantics

Syntax

Semantics

propositional symbols
  • denoted as capitalized letters (e.g. 𝐴, 𝐵, 𝐶, etc)
  • each propositional symbol has a Boolean value, either: 𝑡𝑟𝑢𝑒 or 𝑓𝑎𝑠𝑒

logical connectives/operators

proposition/formulae/sentence
  • a proposition of propositional symbol(s) and logical connective(s)
  • example propositions:
    • 𝑃 ∨ 𝑄 → 𝑅
    • 𝑃
    • ¬𝑅
  • interpretation/truth assignment
    • is a function from its set of propositional symbols to {𝑡𝑟𝑢𝑒, 𝑓𝑎𝑙𝑠𝑒}
  • relations between proposition/formulae/sentence
    • ≃ - equivalent
    • ⊨ - entails
  • types of proposition/formulae/sentence
    • valid/tautology - a formulae is valid/tautology iff every interpretation evaluates to true
    • satisfiable - a formalae is satisfiable iff there exists an interpretation that evaluates to true
    • unsatisfiable - a formulae is unsatisfiable iff there are no interpretations that evaluate to true

Equivalences

Equivalences

Description

idempotency laws
  • 𝐴 ∧ 𝐴 ≃ 𝐴
  • 𝐴 ∨ 𝐴 ≃ 𝐴

commutative laws
  • 𝐴 ∧ 𝐵 ≃ 𝐵 ∧ 𝐴
  • 𝐴 ∨ 𝐵 ≃ 𝐵 ∨ 𝐴

associative laws
  • (𝐴 ∧ 𝐵) ∧ 𝐶 ≃ 𝐴 ∧ (𝐵 ∧ 𝐶)
  • (𝐴 ∨ 𝐵) ∨ 𝐶 ≃ 𝐴 ∨ (𝐵 ∨ 𝐶)

distributive laws
  • 𝐴 ∨ (𝐵 ∧ 𝐶) ≃ (𝐴 ∨ 𝐵) ∧ (𝐴 ∨ 𝐶)
  • 𝐴 ∧ (𝐵 ∨ 𝐶) ≃ (𝐴 ∧ 𝐵) ∨ (𝐴 ∧ 𝐶)

De Morgan’s Laws

definitions of connectives

more negation laws

simplification

Inference Rules / Logical Consequences / Entailment / ⊨

the notation 𝐴 ⊨ 𝐵 (formulae 𝐵 can be derived from formulae(s) 𝐴 by inference) has an alternative notation shown below

  • 𝐴
  • 𝐵̅

which emphasizes that this is not a sentence, but an inference rule. whenever a proposition/formulae/sentence(s) matches the pattern above the line, the inference rule concludes the premise below the line

Subpages