Logical Equivalences in Propositional Logic

Important Logical Equivalences

• Double Negation: ¬¬p <=> p
• Commutative: p∨q <=> q∨p AND p∧q <=> q∧p
• Associative: (p∨q)∨r <=> p∨(q∨r) AND (p∧q)∧r <=> p∧(q∧r)
• Identity: p∧T <=> p AND p∨F <=> p
• Domination: p∨T <=> T AND p∧F <=> F
• Idempotent: p∨p <=> p AND p∧p <=> p
• Distributive: p∨(q∧r) <=> (p∨q)∧(p∨r) AND p∧(q∨r) <=> (p∧q)∨(p∧r)
• De Morgan's: ¬(p∨q) <=> ¬p∧¬q AND ¬(p∧q) <=> ¬p∨¬q
• Other Useful Equivalences: p∨¬p <=> T AND p∧¬p <=> F AND p↔q <=> (¬p∨q)∧(p∨¬q)

Using Logical Equivalences in Proofs

• Equivalences can transform propositions or parts of propositions to reach a conclusion.
• Example: ((p∧q)→p) is a tautology.
• Proof: ((p∧q)→p) <=> ¬(p∧q)∨p <=> (¬p∨¬q)∨p <=> ¬q∨(¬p∨p) <=> ¬q∨T <=> T

Truth Table Approach vs. Logical Equivalence

• Truth tables are exhaustive but become impractical for many propositions.
• Logical equivalences provide an alternative, often faster approach.

Predicate Logic

• Constants: represent specific objects (e.g., John, 7)
• Variables: represent objects of a specific type (defined by the universe of discourse).
• Predicates: represent relations or properties among objects (e.g., greater than, student, married).
• Predicates are not propositions until variables are substituted with specific values, creating propositions (e.g., John > Peter is a proposition).
• Predicate logic remedies propositional logic's limitations by explicitly modeling objects and properties, allowing statements with variables and quantification.

Quantified Statements

• Universal Quantification (∀): ∀x P(x) means P(x) is true for every x in the universe of discourse.
• Existential Quantification (∃): ∃x P(x) means P(x) is true for at least one x in the universe of discourse.

This quiz explores important logical equivalences fundamental to propositional logic. It covers concepts like double negation, commutative properties, and De Morgan's laws along with their applications in proofs and truth tables. Test your understanding of these principles and their usefulness in logical reasoning.