Intro

Tautology

• A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it
  • $p\vee \mathrm{\neg }p$

Contradiction

• A compound proposition that is always false, no matter what the truth values of the propositional variables that occur in it
  • $p\wedge \mathrm{\neg }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\equiv q$ is a tautology.
• $p\equiv q$

Some different ways to express 2 propositions are equivalent

$1^{st}$ way

Use truth table

$2^{nd}$ way

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

$3^{rd}$ way

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

Important logical equivalences

Important logical equivalences (Conditional statement)

Important logical equivalences (BiConditional statement)

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