Discrete Structures
Week 04 Instructor:
Bushra Zahra
Tautology and Contradiction
A compound proposition that is always true, no matter what the truth values of the
propositional variables that occur in it, is called a tautology.
A compound proposition that is always false is called a contradiction.
p ∨ ￢ p is tautology.
p ￢p p ∨ ￢p p ∧ ￢p
T F T F
F T T F
V when 1 is true in ∧ both must are true
Logical Equivalence
Logical equivalence means that two logical statements (propositions) always have the
same truth value in every possible situation. In other words, they are logically the
same, even if they look different.
Logical equivalence can be verified using a truth table. If two expressions have the
same truth value for all combinations of inputs, they are equivalent.
Why is Logical Equivalence
Important?
o Simplifies complex logical expressions.
o Helps in designing circuits and algorithms.
o Provides a foundation for reasoning in mathematics and computer science.
Logical Equivalence Example
p q p→q p q ¬p q ∨ ¬p
T T T T T F T
T F F T F F F
F T T F T T T
F F T F F T T
Logical Equivalence
Converse
The proposition q → p is converse of p → q.
Contrapositive
The contrapositive of p → q is the proposition ￢ q → ￢ p.
Inverse
The proposition ￢ p → ￢ q is called the inverse of p → q.
Logical Equivalence
Converse
The proposition q → p is converse of p → q.
Contrapositive
The contrapositive of p → q is the proposition ￢ q → ￢ p.
Inverse
The proposition ￢ p → ￢ q is called the inverse of p → q.
Logical Equivalence
Implicatio Inverse Convers Contrapositiv
n e e
p q ¬p ¬q p→q ¬p → ¬q q→p ¬q → ¬p
T T F F T T T T
T F F T F T T F
F T T F T F F T
F F T T T T T T
Logical Equivalence
Equivalence Name
p∧T≡p Identity laws
p∨F≡p
p∧T≡p Domination laws
p∨F≡p
p∨p≡p Idempotent laws
p∧p≡p
￢ ( ￢ p) ≡ p Double negation law
p∨q≡q∨p Commutative laws
p∧q≡q∧p
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) Associative laws
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) Distribution Laws
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Logical Equivalence
Equivalence Name
￢ (p ∧ q) ≡ ￢ p ∨ ￢ q De Morgan’s laws
￢ (p ∨ q) ≡ ￢ p ∧ ￢ q
p ∨ (p ∧ q) ≡ p Absorption laws
p ∧ (p ∨ q) ≡ p
p ∨￢p ≡ T Negation laws
p ∧￢p ≡ F
Why Predicate Logic?
Propositional Logic is not expressive enough
Predicate Logic is more expressive and powerful
Propositional logic used in discrete structures to handle more complex and detailed
reasoning. It allows us to express statements involving variables, quantifiers, and
relationships, making it incredibly useful in mathematics, computer science, and other
fields.
Predicate Logic
3+2=5 Yes
X+2=5 No
X + 2 = 5 for any choice of X in {1, 2, 3} Yes
Computer X is under attack by an intruder No
