DISCRETE MATHEMATICS

&
APPLICATIONS

1
Chapter 1: Propositional Logic

1.1. Propositional Logic

1.2. Propositional Equivalences

1.3. Predicates and Quantifiers

1.4. Nested Quantifiers

1.5. Rules of Inference

2
 1.1
Propositional Logic

3
DEFINITION

Definition. A proposition is a declarative sentence that is either true or false.

Examples. (1) If is divisible by then is divisible by

(2) is the smallest prime number.

(3) After rain comes sunshine!

(4)

(5) For every , if and then

Convention. If a proposition is true then we say that its truth value is true (denoted by ).

Otherwise, we will say that the truth value of is false (denoted by ).

4
COMPOUND PROPOSITIONS
Definition. Let be a proposition.
(1) The negation of

Example. She is naughty.

She is not naughty.

5
COMPOUND PROPOSITIONS
Let and be two propositions.
(2) The conjunction of and :

and proposition that is true when both and are true, and is false otherwise.
Example. Let She is very naughty, She is not obstinate

She is very naughty but not obstinate.

6
COMPOUND PROPOSITIONS (cont.)

Let and be two propositions.

(3) The disjunction of and :

Example. Students who have missed more than 4 slots can not pass this class.

Students who have not taken any progress test can not pass this class.
Students who have not taken any progress or have missed more than 4 slots can not pass this class.

7
COMPOUND PROPOSITIONS (cont.)
Let and be two propositions.
(4) The exclusive or of and :
only or only proposition that is true when exactly one of and is true, and is false otherwise.
Example. You can adopt a cat.
.
You can adopt a cat or a hamster, but not both.

8
COMPOUND PROPOSITIONS (cont.)
Let and be two propositions.

(5) Conditional statement:

proposition that is false when is true and is false, and is true otherwise.

Example. You get a on the final exam.

You will pass this class.

9
COMPOUND PROPOSITIONS (cont.)
Let and be two propositions.

(6) Biconditional statement:

proposition that is true when and have the same truth value, and is false otherwise.

Example. He is now at least 20 years old.

He is allowed to get married this year.

10
SUMMARY
Remark. A bit is a symbol taking two values, and . A bit can represent the truth value of a
proposition:
and

Table. Combined truth table using bit operations.

11
LOGICAL EXPRESSIONS
Example. Translate the following propositions into logical expressions.
(1) When I am over 25, I will marry Leslie.
Put I am over 25 years old,
.
Then logical expression of (1) is .

(2) I would marry Daisy or Kate when I am rich and famous.

Put I am rich , I am f
I marry Daisy and I marry Kate.
Then logical expression of (2) is .

12
 1.2
Propositional Equivalences

13
LOGICAL EQUIVALENCES

Definition. (1) A compound proposition that is always true, no matter what the truth values of
propositions that occur in it, is called a tautology.
(2) A compound proposition that is always false is called a contradiction.
(3) A compound proposition that is neither a tautology nor a contradiction is called a contigency.

Definition. Two compound propositions are said to be (logically) equivalent if () is a tautology.

If and are equivalent, we will write
.

14
SOME BASIC LOGICAL EQUIVALENCES

15
LOGICAL EQUIVALENCES - TRUTH TABLE METHOD

In practice, one can verify logical equivalences using truth tables.

Example. Prove that .

16
PRACTICE
Verify the following logical equivalences.
(a) .
(b)
(c) .
(d) .
(e) .

17
 1.3
Predicates and Quantifiers

18
PREDICATE

Statements involving variables such as

, ,
are not propositions. Such statements are called propositional function.

Example. Consider . For specified values of , then it becomes a proposition. For instance, and .

Remark. In , the symbol is called variable and the part is called predicate.

19
QUANTIFIERS:
Let be a propositional function.
Universal quantification:
For all values of , is true.
Existential quantification:

20
LOGICAL EXPRESSIONS WITH QUANTIFIERS

Example. For each of the following statements, find a logical expression using quantifiers and
propositional functions.
(1) Every prime number is not divisible by .

Solution. First, introduce a variable :

For every number that is prime, is not divisible by .
Next, put is not divisible by .
With the domain , we find the logical expression
.

21
(2) Some student in HT’s class has visited Thach That district.
Solution. First, introduce a variable :
There is a student in HT’s class with the property that has visited Thach That district.
Next, put has visited Thach That district.
With the domain students in HT’s class, we find the logical expression
.

(3) Every student of FPT University has visited Thach That and Quoc Oai.
Solution.

22
 1.4
Nested Quantifiers

23
NESTED QUANTIFIERS

Exercise. Translate the following statements into English, where the domain of variables is .
a) where .
b) where
c) where

24
LOGICAL EXPRESSIONS WITH NESTED QUANTIFIERS

Examples. For each of the following statements, find a logical expression using quantifiers and
propositional functions.

(1) Some student of FPT University gave flowers to all female students.

Solution. First, introduce two variables and :

There is a student of FPT University gave flowers to all students that are female.
Next, put gave flower to and is female.
With the domain students of FPTU, we find the logical expression
.

25
(2) If a person is female and is a parent, then this person is someone’s mother.
Solution. First, introduce two variables and :
For every person , if is female and is a parent, then there is a person such that is the mother of
.
Next, put is the mother of , is female
and is a parent.
With the domain all people, we find the logical expression
.

26
NEGATING NESTED QUANTIFIERS
(1) . (2) .

(3) . (4) .

(5) . (6) .

27
 1.5
Rules of Inference

28
AN EXAMPLE
Example. Suppose we have an argument:
If you have one million dollars, then you can buy a villa.
Put You have one million dollars and You can buy a villa.
How do we deduce that is true provided is true?
Observe that is a tautology.
Now, since both and are true, it implies that must be true also.

In summary, the process of inference can be depicted as

29
DEFINITIONS

Definition. (1) An argument is a sequence of propositions

.
The final proposition is called the conclusion, while are called premises.
(2) An argument is said to be valid if the truth of all premises implies that the conclusion is true.
(3) The verification of validity must be based on a tautology. Otherwise, arguments are called
fallacies.

30
TABLE: RULES OF INFERENCES

31
Example. Show that the following premises
,
,

together lead to the conclusion

If I do not finish writing the program, then I will wake up feeling refreshed.
Solution. Put , ,
, .
.

32
TABLE: RULES OF INFERENCES FOR QUANTIFIED STATEMENTS

33
EXAMPLE
Example. Show that the following premises
,

together lead to the conclusion .

Solution. .
With domain the logical expression of is .
Put , we have .
The inference is

34
PRACTICE

35
PRACTICE

36
PRACTICE

37
PRACTICE

38
PRACTICE

39
PRACTICE

40
PRACTICE

41
PRACTICE

42
PRACTICE

43
PRACTICE

44
45
46
47
48
49
50
51