Logical equivalence

 Two propositions are said to be logically

equivalent if their truth tables are identical.
p q ~p  q pq
TT TT TT TT

TT FF FF FF
FF TT TT TT
FF FF T
T TT
 Example: ~p  q is logically equivalent to p  q
Discrete math 1/49
 Converse (1)
 The converse of a conditional statement is
formed by interchanging the hypothesis
and conclusion of the original statement.
In other words, the parts of the sentence
change places but the words "if" and "then"
do not leave their places.
 Conditional:  "If 9 is an odd number, then 9
is divisible by 2.“
 Converse: "If 9 is divisible by 2, then 9 is
an odd number.“

Discrete math 2/49

Converse (2)
 Is the Converse of a given condition logically
equivalent to the Condition?
 The truth table for the proposition & its converse are p  q
&qp
p q pq qp
T T T T
T T TF T
T F T
T F F T
F T T F
F F T T
 The two propositions are not logically equivalent
Discrete math 3/49
 Inverse (1)
 The inverse of a conditional statement is
formed by negating the hypothesis and
negating the conclusion of the original
statement. In other words, the word "not"
is added to both parts of the sentence.
 Conditional:  "If 9 is an odd number, then 9
is divisible by 2.“
 Inverse:  "If 9 is not an odd number, then
9 is not divisible by 2.“

Discrete math 4/49

Inverse (2)
 Is the Inverse of a given condition logically
equivalent to the Condition? Or is it logically
equivalent to the Converse of the condition?

Condition converse Inverse

p q pq qp ~p  ~q
T T T T T
T F F T T
TF T
T
TT TF T
F
T F F T T
F F T T T
F T T F F
Discrete math 5/49
F F T T T
Contrapositive
 The contrapositive of a conditional
statement is formed by
 negating both the hypothesis and the
conclusion, and then
 interchanging the resulting negations.

 In other words, the contrapositive negates

and switches the parts of the sentence. 

 It does BOTH the jobs of the INVERSE and

the CONVERSE
Discrete math 6/49
Example: Contrapositive
 Conditional:  "If 9 is an odd number,
then 9 is divisible by 2.“

 Contrapositive:  "If 9 is not divisible

by 2, then 9 is not an odd number."

Discrete math 7/49

 Contrapositive
 The Contrapositive of the proposition
p  q is ~q  ~p are logically equivalent.

p q pq ~q  ~p
T T T T
T F F F
F T T T
F F T T

Discrete math 8/49

 Double implication
 The double implication “p if and only if q” is
defined in symbols as p  q
p q pq (p  q) ^ (q  p)
T T T T
T F F F
F T F F
F F T T

p  q is logically equivalent to (p q)^(q  p)

Discrete math 9/49
 Tautology
 A proposition is a tautology if its truth table
contains only true values for every case
 Example: p  p v q

p q ppvq
T T T
T F T
F T T
F F T
Discrete math 10/49
 Contradiction
 A proposition is a contradiction if its truth
table contains only false values for every
case
 Example: p ^ ~p
p p ^ (~p)
T F
F F

Discrete math 11/49

 De Morgan’s laws for logic
 The following pairs of propositions are
logically equivalent:

 ~ (p  q) and (~p) ^ (~q)

 ~ (p ^ q) and (~p)  (~q)

Discrete math 12/49

Distributive laws of propositions
 p  (q ^ r) = (p  q) ^ (p r)
 p ^ (q  r) = (p ^ q)  (p ^ r)

Discrete math 13/49

Precedence of propositions
~ is the highest
^


↔ lowest
 Example: The proposition
~p^qr↔qp^r
is equivalent to or is computed according to:
(((~p) ^ q)  r) ↔ ( q  (p ^ r))
Discrete math 14/49
 Proofs
 A mathematical system consists of
 Undefined terms

 Definitions

 Axioms

Discrete math 15/49

 Undefined terms

 Undefined terms are the basic building blocks

of a mathematical system. These are words
that are accepted as starting concepts of a
mathematical system.
 Example: in Euclidean geometry we have
undefined terms such as
 Point

 Line

Discrete math 16/49

 Definitions
 A definition is a proposition constructed
from undefined terms and previously
accepted concepts in order to create a
new concept.
 Example. In Euclidean geometry the
following are definitions:
 Two triangles are congruent if their vertices
can be paired so that the corresponding
sides are equal and so are the corresponding
angles.
Discrete math 17/49
 Axioms
 An axiom is a proposition accepted as true without
proof within the mathematical system.
 There are many examples of axioms in
mathematics:
 Example: In Euclidean geometry the following are
axioms
 Given two distinct points, there is exactly one line that

contains them.
 Given a line and a point not on the line, there is exactly

one line through the point which is parallel to the line.

Discrete math 18/49

 Theorems
 A theorem is a proposition of the form
pq
which must be shown to be true by a sequence
of logical steps that assume that p is true, and
use definitions, axioms and previously proven
theorems.

Discrete math 19/49

 Lemmas and corollaries
 A lemma is a small theorem which is used
to prove a more general theorem.
 A corollary is a theorem that can be proven
to be a logical consequence of a general
theorem.
 Example from Euclidean geometry: "If the three
sides of a triangle have equal length, then its
angles also have equal measure."

Discrete math 20/49

 Types of proof
 A proof is a logical argument that consists
of a series of steps using propositions in
such a way that the truth of the theorem is
established.
 Direct proof: p  q
 A direct method of attack that assumes the
truth of proposition p, axioms and proven
theorems so that the truth of proposition q is
obtained.

Discrete math 21/49

 Indirect proof
There are two ways of indirect proofs:
 The method of proof by contradiction of a
theorem p  q consists of the following
steps:
1. Assume p is true and q is false
2. Show that ~p is also true.
3. Then we have that p ^ (~p) is true.
4. But this is impossible, since the statement p ^ (~p)
is always false. There is a contradiction!
5. So, q cannot be false and therefore it is true.

Discrete math 22/49

 Indirect proof
 The method of proof by showing that the
contrapositive (~q)  (~p) is true.
 Since (~q)  (~p) is logically equivalent to
p  q,
then the theorem is proved.
 Example: show that  is a subset of every set.
 From the definition of subsets, X  Y if every element of X is
also contained in Y, let p stands for element in X and q
element in Y. Then to show
p  q,
we show (~q)  (~p). That is if the element is not in Y it is not in
X. But there are no elements in the empty set,
thus ~p is always true and hence (~q)  (~p) is true. Therefore
p  q is true.

Discrete math 23/49

 Valid arguments
 Deductive reasoning: the process of
reaching a conclusion q from a sequence of
propositions p1, p2, …, pn.
 The propositions p1, p2, …, pn are called
premises or hypothesis.
 The proposition q that is logically obtained
through the process is called the
conclusion.

Discrete math 24/49

 Rules of inference (1)

1. Law of detachment 2. Modus tollens

or modus ponens  pq
 pq  ~q
 p  Therefore, ~p
 Therefore, q

Discrete math 25/49

 Rules of inference (2)
3. Rule of Addition 5. Rule of conjunction
 p  p
 Therefore, p  q  q
 Therefore, p ^ q
4. Rule of
simplification
 p^q
 Therefore, p

Discrete math 26/49

 Rules of inference (3)

6. Rule of hypothetical
syllogism
p  q
q  r
 Therefore, p  r

Discrete math 27/49

 Rules of inference (4)

7. Rule of disjunctive syllogism

 p  q

 ~p

 Therefore, q

Discrete math 28/49

 Resolution proofs
 A clause is a compound statement with terms
separated by “or”, and each term is a single
variable or the negation of a single variable
 Example: p  q  (~r) is a clause
(p ^ q)  r  (~s) is not a clause

 In proving a statement, the hypothesis and

conclusion are written as clauses

Discrete math 29/49

Proof Only one rule example
 Example:
 pq
 ~p  r
 Therefore, q  r
Its proof follows:
1. p  q Ξ ~ ~p  q Ξ ~p  q Ξ ~q  p Using
contrapositive
2. ~p  r Ξ pr
3. 1 & 2 ~q  p, rule 6, & p  r implies
~q  r
4. ~q  r Ξ q  r
Discrete math 30/49
Example
 Let p, q, r & s be four propositions such that
p v q, p  r, q  s therefore r v s
1. Assume ~ (r v s)= ~r ^ ~s Thus ~r & ~s are
true from rule 4
2. ~p v r from p  r
3. ~q v s from q  s
4. From 1 ~r, ~s
5. From 4, 2 and rule 7 ~p
6. From 4, 3 and rule 7 ~q
7. Therefore ~(pvq)
8. Contradicting 5 & 6 p v q

Discrete math 31/49

Example
 Given p  (p q)
p
show q and p  q
1. p  (p q) ↔ ~ p  (p q) ↔ ~ p 
(~ p  q) ↔ ~ p  ~ p  q ↔ ~ p  q
2. P
3. From 1, 2, and rule 7 q
4. From 2, 3 since p & q then p  q

Discrete math 32/49

Predicate Logic
 A predicate is that part of a sentence which
states something about the object of the
sentence.
 A predicate is a statement with a place for
an object. When this place is filled, the
predicate becomes a statement about the
object that fills it.
 A predicate is a proposition with a hole in it
this hole is a variable.

Discrete math 33/49

Predicates & Propositions
 A statement such as x > 5 is not a
proposition: its truth depends upon the
value of variable x.

 Before we can reason about such

statements, we will need to declare, or
introduce, the variables concerned.

 The declaration x : a introduces a variable

x and tells us that it is an element of the
set a.

Discrete math 34/49

 For every and for some
 Most statements in mathematics and
computer science use terms such as
for every and for some.
 For example:
 For every triangle T, the sum of the angles
of T is 180 degrees.
 For every integer n, n is less than p, for
some prime number p.

Discrete math 35/49

 Universal quantifier

 One can write P(x) for every x in a

domain D
 In symbols: x ε D, P(x)
  is called the universal quantifier

Discrete math 36/49

 Truth of  as propositional function
 The statement x P(x) is
 True if P(x) is true for every x  D
 False if P(x) is not true for some x  D
 Example: Let P(n) be the propositional
function n2 + 2n is an odd integer
n  D = {all integers}
 P(n) is true only when n is an odd

integer, false if n is an even integer.

Discrete math 37/49

 Existential quantifier

 For some x  D, P(x) is true if there

exists an element x in the domain D for
which P(x) is true. In symbols: x, P(x)
 The symbol  is called the existential
quantifier.

Discrete math 38/49

 Examples
 Let the universe set be the positive integers, and
 let s(x) be the predicate “x is even integer”,
 t(x,y) be “x = 2y”, p(x) be “x is a prime integer”, and
 r(x) for “x >2”
then we can rewrite the following statements as predicates:

1. “If x is an even integer, then there is an integer y

such that x = 2y” can be written as
 s(x)  y (t(x,y))
 What is the truth value of the expression?
 TRUE

Discrete math 39/49

 More Examples
2. “There is a prime integer x such that x =
2y for some y” can be written
 x(p(x) ^ y (t(x,y)))
 What is the truth value of the expression?
 TRUE
3. “For all integers x, if x is a prime, then
if x>2, then x is not an even integer” can
be written
 x (p(x)  (r(x)  ~s(x)))
 What is the truth value of the expression?
 TRUE

Discrete math 40/49

Free & bound variables
 In a predicate if a variable is preceded by a quantifier,
then it is bounded by the quantifier otherwise it is free
variable the portion of the expression for which the
bound is applied is called the scope of the quantifier
Examples:
 In s(x)  y (t(x,y)) y is bounded & x is free
could be interpreted in only one way
 Now consider x p(x) ^ y (t(x,y))
In this expression x is bounded in x p(x) & y is free.
But in y (t(x,y)) y is bounded and x is free.
 Adding the parenthesis make the expression x(p(x)
^ y (t(x,y))) interpreted in a different way
 In the expression x (p(x)  (r(x)  ~s(x))) the
scope of x is the (p(x)  (r(x)  ~s(x))) i.e. we
talk about the same x

Discrete math 41/49

Understanding predicate
expressions
 Rewrite the following predicate
expressions in English:
 x (p(x) ^ y (t(x,y) ^ r(x)))
For each integer x, x is prime, and there
is an integer y such that x is 2y and x >2

Discrete math 42/49

 Counterexample
 The universal statement x P(x) is false
if x  D such that P(x) is false.
 The value x that makes P(x) false is
called a counterexample to the
statement x P(x).
 Example: P(x) = "every x is a prime
number", for every integer x.
 But if x = 4 (an integer) this x is not a prime
number. Then 4 is a counterexample to
P(x) being true.

Discrete math 43/49

 Rules of inference for
quantified statements

1. Universal instantiation 3. Existential

  xD, P(x) instantiation
 d  D   x  D, P(x)

 Therefore P(d)  Therefore P(d) for

2. Universal generalization some d D

 P(d) for any d  D 4. Existential
generalization
 Therefore x, P(x)
 P(d) for some d D

 Therefore  x, P(x)

Discrete math 44/49

Generalized De Morgan’s laws for
Logic
 If P(x) is a propositional function, then each pair of
propositions in a) and b) below have the same
truth values:
a) ~(x P(x)) and x ~P(x)
"It is not true that for every x, P(x) holds" is equivalent to
"There exists an x for which P(x) is not true“
b) ~(x P(x)) and x ~P(x)
"It is not true that there exists an x for which P(x) is
true" is equivalent to "For all x, P(x) is not true"

Discrete math 45/49

Nested quantifiers(1)
 In each of the most cases, an individual
quantifier applies to a single variable.
 Now consider the example:
 Assume that the universe of discourse is the
set of all nonzero real numbers. Then,
 the statement “for all x, there exists a y
such that x + y = 1" can be written as
 xyP (x; y) where P (x; y) is the predicate
x + y = 1.
 Note that separate quantifiers are used for x
and y.
Discrete math 46/49
Nested quantifiers(1)
 We refer to a sequence of quantifiers applied to
a predicate P as nested quantifiers because
each quantifier applies to a predicate obtained
by applying other quantifiers in the sequence
to the original predicate P.
 For example, in the proposition xy P (x; y),
the outermost quantifier, x,is actually
applied to the predicate y P (x; y).
 This implies that quantifiers themselves can
be affected by other quantifiers; that is,
nested quantifiers applied to the same
predicate are not applied independently of
one another, even if they are applied to
different variables.
Discrete math 47/49
The Order of Quantifiers
 The proposition xyP (x; y) is equivalent
to the proposition yxP (x; y).
 That is, the order in which universal
quantifiers are applied to different
variables is irrelevant.
 Similarly, the order in which existential
quantifiers are applied to different
variables does not affect the resulting
proposition.
 However, the order in which quantifiers
are applied is important when existential
and universal quantifiers are mixed, as
the following example shows.
Discrete math 48/49
Example on order of quantifiers
 Consider the proposition x y P(x; y).
 This proposition is true if, for every x, y
P(x; y) is true.
 That is there exists at least one value of y
for which P(x; y) is true.
 The proposition is false if there exists any
value of x for which yP (x; y) is false. But
what make yP (x; y) false?
 if there exists any value of x for which P(x;
y) is false for every y.

Discrete math 49/49