Skip to content

Intro ​

Tautology ​

  • A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it
    • p∨¬p

Contradiction ​

  • A compound proposition that is always false, no matter what the truth values of the propositional variables that occur in it
    • p∧¬p

Contingency ​

  • A compound proposition that is neither a tautology nor a contradiction.
  • Can have both true and false as its true values

Logical equivalences ​

  • The compound propositions p and q are called logically equivalent if p≡q is a tautology.
  • p≡q

Some different ways to express 2 propositions are equivalent ​

1st way

Use truth table

2nd way

Employ logical equivalences that we already know to transform p into q. See Important logical equivalences

3rd way

Employ logical equivalence's definition. Specifically, prove that p≡q is a tautology.

Important logical equivalences ​

image.png

Important logical equivalences (Conditional statement) ​

image.png

Important logical equivalences (BiConditional statement) ​

image.png

Satisfiable ​

  • There is an assignment of truth values to its variables that makes it true (named as solution)
  • It is Tautology or contingency
  • When it is unsatisfiable, then it is a contradiction
  • N-queens problem, Sudoku problem

Built with ❤️ and curiosity