Course: Discrete Structures

(501215-3)

Chapter 1

The Foundations: Logic and

Proofs

1
1.1 Propositional Logic .. Count..
1.2 Propositional Equivalences
1.3 Predicates and Quantifiers
1.4 Nested Quantifiers
1.5 Rules of Inference
1.6 Introduction to Proofs
1.7 Proof Methods and Strategy

2 P. 1
 1.3 Predicates and Quantifiers
• Predicate logic
• Predicate: a property that the subject of the statement can
have
• Predicate logic P(x): x>3 Extend propositional logic by the
following features:
• Variable: x, y, z
• Predicate: P(x), M(x)
• Quantifiers: ", $
• propositional function are a generalization of propositions.
– The value of the P at x
– P(x1,x2, …, xn): n-place predicate or n-ary predicate

3
 Predicates and Quantifiers
Domain: The domain of a predicate variable is the
collection of all possible values that the variable may
take, domain is denoted by U

Example:
• Let P(x, y) = “x > y”. Domain: integers,

Both x and y are integers.

• P(4, 3) means “4 >3”, so P(4, 3) is TRUE;
• P(1, 2) means “1>2” , so P(1, 2) is FALSE;

4
 Predicates and Quantifiers
Example:
Let U = Z, the integers = {. . . -2, -1, 0 , 1, 2, 3, . . .} and P(x): x > 0 is the
predicate.

• P(x): x > 0 has no truth value until the variable x is bound.

• Propositional functions become propositions (and thus have truth
values) when all their variables are either:
• Replaced by a value from their domain
• Bound by a quantifier

Examples of propositions where x is assigned a value:

• P(-3) is false,
• P(0) is false,
• P(3) is true.

5
 Propositional Functions
Examples:

• P(y)v ¬ P(0) is not a proposition. The variable y

has not been bound. However, P(3)v ¬ P(0) is a
proposition which is true.

• Let R be the three-variable predicate R(x, y z): x + y= z

Find the truth value of
• R(2, -1, 5) ?
• R(3, 4, 7)?
• R(x, 3, z)?

6
 Propositional Functions
Examples:
Let P(x, y, z) denote that x + y = z and U be the integers for all
three variables.
• P(−4, 6, 2) is true.
• P(5, 2, 10) is false.
• P(5, x, 7) is not a proposition.

Let Q(x, y, z) denote that x − y = z and U be the integers.

• P(1, 2, 3) ∧ Q(5, 4, 1) is true.
• P(1, 2, 4) → Q(5, 4, 0) is true.
• P(1, 2, 3) → Q(5, 4, 0) is false.
• P(1, 2, 4) → Q(x, 4, 0) is not a proposition.

7
 Quantifiers
• Quantification
We need quantifiers to formally express the meaning of the
words “all” and “some”.
– Universal quantification: a predicate is true for
every element
– Existential quantification: there is one or more
element for which a predicate is true

8
 The Universal Quantifier
• Definition 1: The universal quantification of P(x) is the
statement “P(x) for all values of x in the domain”,
denoted by "x P(x)
– “for all x P(x)” or “for every x P(x)”
– ∀x P(x) asserts that P(x) is true for every x in the
domain U.
– All students are excellent
• Counterexample: an element for which P(x) is false
– When all elements in the domain can be listed, P(x1)Ù
P(x2) Ù…Ù P(xn)
• Example: U={1,2,3},"xP(x) =P(1) Ù P(2) Ù P(3)
9
 The Universal Quantifier
• The truth value depends not only on P, but also on the
domain U.

Example:
Let P(x) denote x > 0.
• If U is the integers then ∀x P(x) is false.
• If U is the positive integers then ∀x P(x) is true.

10
 The Existential Quantifier
• Definition 2: The existential quantification of P(x) is the
proposition “There exists an element x in the domain
such that P(x)”, denoted by $x P(x)
– “there is an x such that P(x)” or “for some x P(x)”
– ∃xP(x) asserts that P(x) is true for some x in the
domain.
– Some students are excellent
– When all elements in the domain can be listed, P(x1)Ú
P(x2) Ú…Ú P(xn)
• Example: U={1,2,3}, $xP(x) =P(1) Ú P(2) Ú P(3)

11
 TABLE 1 (1.3)

12 P. 34
 Other Quantifiers
• Uniqueness quantifier: $!x P(x) or $1x P(x)
– There exists a unique(one and only one) x
such that P(x) is true
Example:
Let P(x) denote x + 1 = 0 and U are the integers.
Then ∃!x P(x) is true.

Example:
Let P(x) denote x > 0 and U are the integers.
Then ∃!x P(x) is false.

13
 Other Quantifiers
• Quantifiers with restricted domains
– "x<0 (x2>0)
• Conditional: "x(x<0 ® x2>0)
– $z>0 (z2=2)
• Conjunction: $z(z>0 Ù z2=2)

14
 Quantifiers
• Precedence of quantifiers
– " and $ have higher precedence than all
logical operators
– Ex: "x P(x)Ú Q(x)
• ("x P(x))Ú Q(x)

15
 Logical Equivalence involving Quantifiers

• Definition 3: two statements S and T

involving predicates and quantifiers are
logically equivalent, denoted by S º T, if and
only if they have the same truth value no
matter which predicates are substituted
and which domain is used
– E.g. "x (P(x) Ù Q(x)) º "x P(x) Ù "x Q(x)

16
 Negating Quantified
Expressions
• ¬"x P(x) º $x ¬P(x)
– Negation of the statement “Every student in
your class has taken a course in Preparatory Math
2”
– “There is a student in your class who has not
taken a course in Preparatory Math 2”
• ¬$x P(x) º "x ¬P(x)

17
 TABLE 2 (1.3)

18 P. 41
 Example
• What are the negations of the following
expressions: ∃x (x=2), ∀x (x2>x), ∃x (x2 =2)
• ¬∃x ( x = 2) º ∀x ¬(x=2) º ∀x (x ≠ 2 )
• ¬∀x (x2 > x) º ∃x ¬(x2> x ) º ∃x (x2 ≤ x )
• ¬∃x (x2 = 2) º ∀x ¬(x2 = 2 ) º ∀x (x2 ≠ 2)
• ¬∀x (x = x2) º …
• ¬∃x (x2 < 0) º …
• ∃x ¬(x2 > 0) º …
19
 Translating from English into Logical
Expressions
• “Every student in this class has studied
Preparatory Math 2”
• “Some student in this class has visited
Madina”
• “Every student in this class has visited
either Makkah or Madina”

20
• Using Quantifiers in system specifications
– “Every mail message larger than one megabyte will be compressed”
• let S(m , y) ="Mail message m is larger than y megabytes," where
domain(x)={all mail messages}
• let y is a positive real number,
• let C (m )= "Mail message m will be compressed.“
• Specification: "m (S(m , 1 ) ® C(m)).
– “If a user is active, at least one network link will be available”
• Let A(u) ="User u is active," where domain(u)={all users},
• let S(n , x) ="Network link n is in state x " ,domain(n) ={all network
links}, domain(x)={all possible states for a network link}
• Specification : $ u A(u) ® $ n S(n , available).
• Examples from Lewis Carroll: “All lions are fierce”, “Some lions do not
drink coffee”, Some fierce creatures do not drink coffee”
• Let P (x)="x is a lion," Q (x)="x is fierce," R (x)="x drinks coffee,"
respectively. Domain(x)={all creatures}
• "x(P (x)® Q (x)), $x(P (x) Ù ¬R (x)), $x(Q (x) Ù ¬R (x))

21
 1.4 Nested Quantifiers
• Two quantifiers are nested if one is within
the scope of the other
– "x $y (x+y=0)
– "x " y ((x>0) Ù (y<0) ® (xy<0))
• Thinking of quantification as loops
– "x"y P(x, y)
– "x $y P(x, y)
– $x"y P(x, y)
– $x $y P(x, y)

22
 • The order of quantifiers is important
unless all quantifiers are universal
quantifiers or all are existential quantifiers
– "x"y P(x, y) vs. "y"x P(x, y)
• P(x,y): “x+y=y+x”
– "x $y Q(x, y) vs. $y"x Q(x, y)
• Q(x,y): “x+y=0”

23
 TABLE 1 (1.4)

24 P. 53
 Translating mathematical statements into
statements involving nested quantifiers
• “The sum of two positive integers is
always positive”
– ∀x∀y((x > 0) ∧ (y > 0) → (x +y > 0)),
domain(x)=domain(y)=ℤ
– ∀x∀y(x +y > 0), domain(x)=domain(y)= ℕ
• “Every real number except zero has a
multiplicative inverse”
(a multiplicative inverse of a real number
x is a real number y such that xy=1)
– ∀x((x = 0) → ∃y(xy = 1)), domain(x)= ℝ
25
 Translating from nested quantifiers into
English
• "x (C(x) Ú $y (C(y) Ù F(x, y))
– C(x): “x has a computer”, F(x,y): “x and y are friends”
– Domain of x, y: “all students in your school”
– every student in your school has a computer or has a
friend who has a computer
• $x"y"z (F(x, y)Ù F(x, z) Ù (y¹z) ® ¬F(y, z))
– F(a, b): “a and b are friends”
– Domain of x, y, z: “all students in your school”
– there is a student none of whose friends are also friends
with each other
26
 Translating English sentences
into logical expressions
• “If a person is female and is a parent, then
this person is someone’s mother”
– F(x): “x is female,” P(x):“x is a parent,” and
M(x, y):“x is the mother of y.”
– ∀x((F (x) ∧ P(x)) → ∃y M(x, y)).
• “Everyone has exactly one best friend”
– ….

27
 Negating nested quantifiers
• Negation of "x $y (xy=1)
– ¬∀x∃y(xy = 1) º ∃x¬∃y(xy = 1) º ∃x∀y¬(xy = 1).
Since ¬(xy ≠1)º (xy ≠1),
so "x $y (xy=1)º $x "y(xy ≠ 1).
• “There does not exist a bady who has taken
a flight on every airline in the world”
– P(w,f ) :“w has taken f ”, Q(f, a):“f is a flight on a.”
– ∀w ∀a∃f (P(w, f ) ∧ Q(f, a)) ≡ ∀w∃a ∃f (P(w, f )
∧ Q(f, a)) ≡ ∀w∃a∀f (P (w, f ) ∧ Q(f, a)) ≡
∀w∃a∀f ( P(w, f )∨ Q(f, a)).
28