Summary of "Discrete Math - 1.3.3 Constructing New Logical Equivalences"

Summary of “Discrete Math - 1.3.3 Constructing New Logical Equivalences”

This video focuses on demonstrating how to construct new logical equivalences by using previously known equivalences and laws in propositional logic. The instructor uses two main methods to prove logical equivalences: truth tables and formal proofs using logical laws. The video emphasizes understanding and applying laws such as De Morgan’s laws, double negation, distributive, commutative, identity, and domination laws to transform and verify logical statements.

Main Ideas and Concepts

Constructing Logical Equivalences: Using known equivalences and laws to build new equivalences step-by-step.
Two Methods to Prove Logical Equivalence:
1. Truth Tables:
  - Create columns for propositions and their negations.
  - Compute intermediate compound propositions stepwise.
  - Compare final columns to verify equivalence.
2. Two-Column Proofs Using Logical Laws:
  - Start with one side of the equivalence.
  - Apply known logical laws to transform the expression stepwise.
  - Continue until the expression matches the other side of the equivalence.
  - Write down each transformation and the law used.
Key Logical Laws Used:
- De Morgan’s Laws:
  - Negation of a disjunction becomes a conjunction of negations.
  - Negation of a conjunction becomes a disjunction of negations.
- Double Negation Law:
  - Negating a negation returns the original proposition.
- Distributive Law:
  - Distributes conjunction over disjunction or vice versa.
- Commutative Law:
  - Order of propositions in conjunction or disjunction can be swapped.
- Identity Law:
  - Disjunction with false leaves the other proposition unchanged.
- Domination Law:
  - Disjunction with true is always true.
- Negation Law:
  - A proposition or its negation is always true (tautology).
- Implication Rewrite:
  - “If P then Q” is equivalent to “not P or Q”.
Example Walkthroughs:
- Proving that ¬(P ∧ Q) ≡ ¬P ∨ ¬Q using truth tables and stepwise logical laws (De Morgan’s Law, double negation, distributive law, etc.).
- Showing that the implication (P ∧ Q) → (P ∨ Q) is a tautology by rewriting it and applying the laws.
- A practice example proving ¬¬P ∨ Q ≡ ¬Q ∧ P using De Morgan’s law, double negation, and commutative law.
Encouragement to Practice: The instructor notes that mastering these proofs requires practice and familiarity with the laws.
Next Topic Preview: Introduction to predicate logic, which extends propositional logic.

Detailed Methodology / Instructions for Constructing Logical Equivalences

Using a Truth Table:
- List all basic propositions (e.g., P, Q).
- Add columns for negations and intermediate compound propositions.
- Calculate truth values for each row step-by-step.
- Compare the final columns of the two expressions to confirm equivalence.
Using Logical Laws in a Two-Column Proof:
- Write the original expression on the left side.
- Aim to transform it into the target expression on the right side.
- Apply one logical law per step, writing the resulting expression and naming the law used.
- Repeat until the expression matches the target.
- Common laws to apply: De Morgan’s, double negation, distributive, commutative, identity, domination, implication rewrite.
Verifying Tautologies:
- Rewrite implications as disjunctions using the implication rewrite law.
- Use De Morgan’s laws and negation laws to simplify.
- Rearrange using commutative and associative laws.
- Identify tautologies using negation and domination laws.