Lecture 3 - Propositional Logic Laws

A set of vocabulary flashcards covering key concepts and laws from the lecture notes on tautology, contradiction, truth tables, logical equivalence, and common laws of propositional logic.

Tautology

A compound proposition that is always true under every possible assignment of truth values.

Contradiction

A compound proposition that is always false under every possible assignment of truth values.

Truth table

A table listing all possible truth values for variables and the resulting truth value of the expression.

Proposition

A declarative statement that has a definite truth value (true or false).

Logical equivalence

Two propositions that have the same truth value for every possible assignment; denoted by p ≡ q or p ↔ q.

Implication (p → q)

A conditional statement meaning 'if p then q,' which is logically equivalent to ¬p ∨ q.

Negation

The NOT operator (¬); inverts the truth value of a proposition.

Disjunction

The OR operator (p ∨ q); true if at least one of p or q is true.

Conjunction

The AND operator (p ∧ q); true only if both p and q are true.

De Morgan’s laws

Negation distributes over ∨ and ∧: ¬(p ∨ q) ≡ ¬p ∧ ¬q and ¬(p ∧ q) ≡ ¬p ∨ ¬q.

Double negation

Negating twice returns the original: ¬¬p ≡ p.

Identity laws

p ∨ false ≡ p and p ∧ true ≡ p.

Domination laws

p ∨ true ≡ true and p ∧ false ≡ false.

Complement laws

p ∨ ¬p ≡ true and p ∧ ¬p ≡ false.

Distributive laws

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r); p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r).

Associative laws

(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) and (p ∧ q) ∧ r ≡ p ∧ (q ∧ r).

Commutative laws

p ∨ q ≡ q ∨ p and p ∧ q ≡ q ∧ p.

Idempotent laws

p ∨ p ≡ p and p ∧ p ≡ p.

Absorption laws

p ∨ (p ∧ q) ≡ p and p ∧ (p ∨ q) ≡ p.

Conditional identity

p → q ≡ ¬p ∨ q (the equivalence of implication to disjunction with negation).

Biconditional (iff) identity

p ↔ q ≡ (p → q) ∧ (q → p) (p is true exactly when q is true).