BMAT205L Discrete Mathematics and

Graph Theory

Faculty: [Link]
Associate Professor

Department of Mathematics,
School of Advanced Sciences,
Vellore Institute of Technology,
Vellore, Tamilnadu.
ezhilmaran.d@[Link]

August 9, 2023

Faculty: [Link] Associate Professor (VIT) Discrete Mathematics August 9, 2023 1 / 22

 Overview

1 Module −1 Predicate Calculus

The Predicate Calculus
Inference Theory of the Predicate Calculus

2 Practice Problems

Faculty: [Link] Associate Professor (VIT) Discrete Mathematics August 9, 2023 2 / 22

 Predicate Calculus

Consider the statement

p : x is a prime number (the statement is not a proposition)

The truth value of p depends on the value of x.

p is true when x = 3, and false when x = 10.

In this section we extend the system of logic to include such an above

statements.

Faculty: [Link] Associate Professor (VIT) Discrete Mathematics August 9, 2023 3 / 22

 Definition 1. (predicates).
A predicate refers to a property that the subject of the statement can
have. A predicate is a sentence that contains a finite number of specific
values are substituted for the variables.

That is, let P(x) be a statement involving variable x and a set D. We call
P as a propositional function if for each x in D, P(x) is a proposition.

Faculty: [Link] Associate Professor (VIT) Discrete Mathematics August 9, 2023 4 / 22

 Definition 2. (universe of discourse)
The set D is called the domain of discourse (oruniverse of discourse) of P.
It is the set of all possible values which can be assigned to variables in
statements involving predicates.

Example: Let p(x) denote the statement x ≥ 4. What are the truth values
of p(5) (T ) and p(2) (F ).

Example: Let g (x, y ) denote the statement g .c.d(x, y ) = 1. What are the
truth values of g (3, 5) (T ) and g (2, 8) (F )

Faculty: [Link] Associate Professor (VIT) Discrete Mathematics August 9, 2023 5 / 22

 Definition 3. (universal quantifier)
Consider the proposition
All odd prime numbers are greater than 2. The word all in this proposition
is a logical quantifier. The proposition can be translated as follows:
For every x, if x is an odd prime then x is greater than 2

Similarly, the proposition:

Every rational number is a real number may be translated as.

For every x, if x is a rational number, then x is a real number.

The phrase for every x is called a universal quantifier.

Faculty: [Link] Associate Professor (VIT) Discrete Mathematics August 9, 2023 6 / 22

 In symbols it is denoted by (∀x) or (x).

The phrases for every x, for all x and for each x have the same meaning
and we can symbolize each by (x).

If P(x) denotes a predicate (propositional function), then the universal

quantification for P(x), is the statement.

(x) P(x) is true.

Faculty: [Link] Associate Professor (VIT) Discrete Mathematics August 9, 2023 7 / 22

 Example :
(a) Let A = {x : x is a natural number less than 9}
Here P(x) is the sentence x is a natural number less than 9. The common
property is a natural number less than 9. P(1) is true, therefore, 1 ∈ A
and P(12) is not true, therefore 12 ∈
/ A.

(b) The proposition (∀N) (n + 4 > 3) is true.

Since {n|n + 4 > 3} = {1, 2, 3, . . . } = N.

(c) The proposition (∀N) (n + 2 > 8) is false.

Since {n|n + 2 > 8} = {7, 8, 9, . . . } ̸= N.

Faculty: [Link] Associate Professor (VIT) Discrete Mathematics August 9, 2023 8 / 22

 Definition 4. (existential quantifier).
In some situations we only require that there be at least one value for each
the predicate is true. This can be done by prefixing P(x) with the phrase
there exists an. The phrase there exists an is called an existential
quantifier.

Faculty: [Link] Associate Professor (VIT) Discrete Mathematics August 9, 2023 9 / 22

 The existential quantification for a predicate is the statement There exists
a value of x for which P(x).

The symbol, ∃ is used to denote the logical quantifier there exists. The
phrases There exists an x, There is a x, for some x and for at least one x
have the same meaning.

The existential quantifier for P(x) is denoted by (∃ x) P(x)

Faculty: [Link] Associate Professor (VIT) Discrete Mathematics August 9, 2023 10 / 22

 Example :
(a) The proposition there is an integer between 1 and 3 may be written as
(∃ an integer) (the integer is between 1 and 3)

(b) The proposition (∃N) (n + 4 < 7) is true.

Since {n|n + 4 < 7} = {1, 2} ̸= ϕ.

(c) The proposition (∃N) (n + 6 < 4) is false.

Since {n|n + 6 < 4} = ϕ.

Faculty: [Link] Associate Professor (VIT) Discrete Mathematics August 9, 2023 11 / 22

 IV. Problems:

(i) Show that (x)(H(x) −→ M(x)) ∧ H(a) =⇒ M(a).

Solution:

Step 1 (x)(H(x) −→ M(x)) Rule P

Step 2 H(a) −→ M(a) Rule US
Step 3 H(a) Rule P
Step 4 M(a) {2, 3} and apply Modus Ponens

Faculty: [Link] Associate Professor (VIT) Discrete Mathematics August 9, 2023 12 / 22

 (ii) Show that
(x)(P(x) −→ Q(x)) ∧ (x)(Q(x) −→ R(x)) =⇒ (x)(P(x) −→ R(x)).
Solution:

Step 1 (x)(P(x) −→ Q(x)) Rule P

Step 2 P(a) −→ Q(a) Rule US
Step 3 (x)(Q(x) −→ R(x)) Rule P
Step 4 Q(a) −→ R(a) Rule US
Step 5 P(a) −→ R(a) {2,4},I7
Step 6 (x)P(x) −→ R(x) Rule UG

Faculty: [Link] Associate Professor (VIT) Discrete Mathematics August 9, 2023 13 / 22

 (iii) Show that (∃x)(P(x) ∧ Q(x)) =⇒ (∃x)P(x) ∧ (∃x)Q(x).
Solution:

Step 1 (∃x)(P(x) ∧ Q(x)) Rule P

Step 2 P(a) ∧ Q(a) Rule ES
Step 3 P(a) I1
Step 4 Q(a) I1
Step 5 (∃x)P(x) {3},EG
Step 6 (∃x)Q(x) {4},EG
Step 7 (∃x)P(x) ∧ (∃x)Q(x) {5,6}, I3

Faculty: [Link] Associate Professor (VIT) Discrete Mathematics August 9, 2023 14 / 22

 (iv) Show that (x)(P(x) ∨ Q(x)) =⇒ (x)P(x) ∨ (∃x)Q(x).
Solution: Proof by indirect method

Step 1 ¬((x)P(x) ∨ (∃x)Q(x)) Rule P

Step 2 ¬(x)P(x) ∧ ¬(∃x)Q(x) Rule T
Step 3 ¬(x)P(x) I1
Step 4 ¬(∃x)Q(x) I1
Step 5 (∃x)¬P(x) 3,Rule T
Step 6 (x)¬Q(x) 4,Rule T
Step 7 ¬P(a) 5,ES
Step 8 ¬Q(a) 6,US

Faculty: [Link] Associate Professor (VIT) Discrete Mathematics August 9, 2023 15 / 22

 Step 9 ¬P(a) ∧ ¬Q(a) {7,8},I3
Step 10 ¬(P(a) ∨ Q(a)) Rule T
Step 11 (x)(P(x) ∨ Q(x)) Rule P
Step 12 P(a) ∨ Q(a) US
Step 13 ¬(P(a) ∨ Q(a)) ∧ (P(a) ∨ Q(a)) {10,12}, I3
Step 14 F Rule T

Faculty: [Link] Associate Professor (VIT) Discrete Mathematics August 9, 2023 16 / 22

 (v) Show that from
(a) (∃x)(F (x) ∧ S(x)) −→ (y )(M(y ) −→ W (y ))
(b) (∃y )(M(y ) ∧ ¬W (y ))
the conclusion (x)(F (x) −→ ¬S(x)).
Solution:

Step 1 (∃y )(M(y ) ∧ ¬W (y )) Rule P

Step 2 (M(a) ∧ ¬W (a)) ES
Step 3 ¬(M(a) −→ W (a)) Rule T
Step 4 (∃y )¬(M(y ) −→ W (y )) EG
Step 5 ¬(y )(M(y ) −→ W (y )) Rule T

Faculty: [Link] Associate Professor (VIT) Discrete Mathematics August 9, 2023 17 / 22

 Step 6 (∃x)(F (x) ∧ S(x)) −→ (y )(M(y ) −→ W (y )) Rule P
Step 7 ¬(∃x)(F (x) ∧ S(x)) {5,6}, I6
Step 8 (x)¬(F (x) ∧ S(x)) Rule T
Step 9 ¬(F (a) ∧ S(a)) US
Step 10 F (a) −→ ¬S(a) Rule T
Step 11 (x)(F (x) −→ ¬S(x)) UG

Faculty: [Link] Associate Professor (VIT) Discrete Mathematics August 9, 2023 18 / 22

 Practice Problems

Check the validity of the following conclusions

1 Consider these statements. The first two are called premises
and the third is called the conclusion. The entire set is called
an argument.
“All lions are fierce.”
“Some lions do not drink coffee.”
“Some fierce creatures do not drink coffee.”
2 Consider these statements, of which the first three are
premises and the fourth is a valid conclusion.
“All hummingbirds are richly colored.”
“No large birds live on honey.”
“Birds that do not live on honey are dull in color.”
“Hummingbirds are small.”

Faculty: [Link] Associate Professor (VIT) Discrete Mathematics August 9, 2023 19 / 22

 3 Let P(x), Q(x), and R(x) be the statements “x is a clear
explanation,” “x is satisfactory,” and “x is an excuse,” respec-
tively. Suppose that the domain for x consists of all English
text. Express each of these statements using quantifiers, log-
ical connectives, and P(x), Q(x), and R(x).
a) All clear explanations are satisfactory.
b) Some excuses are unsatisfactory.
c) Some excuses are not clear explanations.
d) Does (c) follow from (a) and (b)?

Faculty: [Link] Associate Professor (VIT) Discrete Mathematics August 9, 2023 20 / 22

 4 Let P(x), Q(x), R(x), and S(x) be the statements “x is a baby,”
“x is logical,” “x is able to manage a crocodile,” and “x is
despised,” respectively. Suppose that the domain consists of
all people. Express each of these statements using quantifiers;
logical connectives; and P(x), Q(x), R(x), and S(x).
a) Babies are illogical.
b) Nobody is despised who can manage a crocodile.
c) Illogical persons are despised.
d) Babies cannot manage crocodiles.
e) Does (d) follow from (a), (b), and (c)? If not, is there a
correct conclusion?

Faculty: [Link] Associate Professor (VIT) Discrete Mathematics August 9, 2023 21 / 22

 5 Let P(x), Q(x), R(x), and S(x) be the statements “x is a
duck,” “x is one of my poultry,” “x is an officer,” and “x is
willing to waltz,” respectively. Express each of these state-
ments using quantifiers; logical connectives; and P(x), Q(x),
R(x), and S(x).
a) No ducks are willing to waltz.
b) No officers ever decline to waltz.
c) All my poultry are ducks.
d) My poultry are not officers.
e) Does (d) follow from (a), (b), and (c)? If not, is there a
correct conclusion?

Faculty: [Link] Associate Professor (VIT) Discrete Mathematics August 9, 2023 22 / 22