This document summarizes key concepts from a lecture on logical equivalence and propositional logic:
1. It defines logical equivalence as two proposition forms having identical truth values for all possible substitutions. Equivalence is checked using truth tables.
2. De Morgan's laws state that the negation of a conjunction is equivalent to the disjunction of the negated components, and vice versa.
3. A tautology is a proposition form that is always true, while a contradiction is always false, regardless of variable truth values.
4. Laws of logic include commutative, associative, distributive, identity, negation, double negation, idempotent, universal bound, and absorption laws.
This document summarizes key concepts from a lecture on logical equivalence and propositional logic:
1. It defines logical equivalence as two proposition forms having identical truth values for all possible substitutions. Equivalence is checked using truth tables.
2. De Morgan's laws state that the negation of a conjunction is equivalent to the disjunction of the negated components, and vice versa.
3. A tautology is a proposition form that is always true, while a contradiction is always false, regardless of variable truth values.
4. Laws of logic include commutative, associative, distributive, identity, negation, double negation, idempotent, universal bound, and absorption laws.
This document summarizes key concepts from a lecture on logical equivalence and propositional logic:
1. It defines logical equivalence as two proposition forms having identical truth values for all possible substitutions. Equivalence is checked using truth tables.
2. De Morgan's laws state that the negation of a conjunction is equivalent to the disjunction of the negated components, and vice versa.
3. A tautology is a proposition form that is always true, while a contradiction is always false, regardless of variable truth values.
4. Laws of logic include commutative, associative, distributive, identity, negation, double negation, idempotent, universal bound, and absorption laws.
This document summarizes key concepts from a lecture on logical equivalence and propositional logic:
1. It defines logical equivalence as two proposition forms having identical truth values for all possible substitutions. Equivalence is checked using truth tables.
2. De Morgan's laws state that the negation of a conjunction is equivalent to the disjunction of the negated components, and vice versa.
3. A tautology is a proposition form that is always true, while a contradiction is always false, regardless of variable truth values.
4. Laws of logic include commutative, associative, distributive, identity, negation, double negation, idempotent, universal bound, and absorption laws.
Download as PPTX, PDF, TXT or read online from Scribd
Download as pptx, pdf, or txt
You are on page 1/ 19
Discrete Structures (CSC 102)
Lecture 2 Logical Equivalence Definition: Two proposition form are called logically Equivalent if and only if they have identical truth values for each possible substitution of proposition for their proposition variable.
The logical equivalence of proposition forms P and Q are written
P≡Q Equivalence of two compound proposition P and Q
1. Construct the truth table for P.
2. Construct the truth table for Q using the same proposition variables for identical component proposition. 3. Check each combination of each truth values of the proposition variables to see whether the truth value of P is the same as the truth value of Q. Equivalence check a. If in each row the truth value of P is the same as the truth value of Q, then P and Q are logically equivalent.
b. If in some row P has different truth value
from Q, then P and Q are not logically equivalent. Example
Prove that ¬(¬p) ≡ p ?
Solution: p ¬p ¬(¬p) T F T F T F
As you can see the corresponding values of p and
¬(¬p) are same, hence equivalence is justified. Example Show that the proposition forms ¬(pʌq) and ¬pʌ¬q are NOT Logically Equivalent . p q p q pʌq ¬(pʌq) ¬pʌ¬q T T F F T F F T F F T F T F
F T T F F T F
F F T T F T T De Morgan’s Law De Morgan’s Law States that:
The negation of an AND proposition is
logically equivalent to the OR proposition in which each component is negated.
The negation of an AND proposition is
logically equivalent to the OR proposition in which each component is negated. Symbolically (De Morgan’s Law)
Question: Negate the following compound proposition.
1. John is Six feet tall and he weighs at least 200 pounds. 2. The bus was late OR Tom’s watch was slow. Solution
1. John is not Six feet tall OR he weighs
less than 200 pounds. 2. The bus was not late and Tom’s watch was not slow. Inequality and De Morgan’s Law
Question use the De Morgan’s laws to write the
negation of: -1<x<=4
Solution: The given proposition is equivalent to:
-1<x AND x<=4
By De Morgan Law the negation is:
-1>=x OR x>4 Tautology and Contradiction Definition: A tautology is a proposition form that is always true regardless of the truth values of the individual proposition substituted for its proposition variables. A proposition whose form is tautology is called tautological proposition.
Definition: A contradiction is a proposition form that is
always False regardless of the truth values of the individual proposition substituted for its proposition variables. A proposition whose form is contradiction is called contradictory proposition. Example
Show that the proposition form p˅¬p is a tautology
and proposition form pʌ¬p is a contradiction.
p ¬p p˅¬p pʌ¬p T F T F F T T F
Exercise: if t is a tautology and c is contradiction,
show that p˅t ≡ t, and pʌc ≡ c ? Laws of Logic 1. Commutative laws: pʌq ≡ qʌp; p˅q ≡ q˅p
