Discrete Mathematics and Its Applications - 131 Lecture Notes môn English Studies| Trường Đại học Thăng Long

20:56, 09/01/2026
Discrete Mathematics and Its Applications - 131 Lecture Notes - Studocu
DiscreteMathematicsandItsApplications Ngày 9 tháng 10 năm 2022
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 1/285 Ghi chú What is Discrete Mathematics?
- the part of mathematics devoted to the study of discrete objects.(1)
(1)Examples of discrete objects: integers, steps taken by a computer program,
distinct paths to travel from point A to point B on a map, ways to pick a winning set of numbers in a lottery.
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 2/285 Ghi chú
Kinds of Problems Solved Using Discrete Mathematics
- How many ways can a password be chosen following specific rules?
- How many telephone numbers of a specific rule are there?
- What is the probability of winning a particular lottery?
- What is the shortest path between two cities using a transportation system?
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 3/285 20:56, 09/01/2026
Discrete Mathematics and Its Applications - 131 Lecture Notes - Studocu Ghi chú
- Find the shortest tour that visits each of a group of cities only once
and then ends in the starting city.
- How can we represent English sentences so that a computer can reason with them?
- How can we prove that there are infinitely many prime numbers?
- How can a list of integers be sorted so that the integers are in increasing order? - V.v.
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 4 / 285 Ghi chú
Goals of a Course in Discrete Mathematics - Mathematical Reasoning, - Combinatorial Analysis, - Discrete Structures, - Applications.
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 5 / 285 Ghi chú
Lastly, Discrete Mathematics is a Gateway Course.
Important for many subsequent courses: - in Computer Science, - in Mathematics, - in other Disciplines.
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 6 / 285 20:56, 09/01/2026
Discrete Mathematics and Its Applications - 131 Lecture Notes - Studocu Ghi chú
Textbook: Discrete Mathematics and its Applications
(by Kenneth Rosen) (sixth edition)
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 7 / 285 Ghi chú Learning Support Channels - Elearning - Library - V.v.
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 8 / 285 Ghi chú CHAPTER 1
The Foundations: Logic and Proofs
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 9 / 285 20:56, 09/01/2026
Discrete Mathematics and Its Applications - 131 Lecture Notes - Studocu Ghi chú
Section 1.1: Propositional Logic
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 10 / 285 Ghi chú Propositions
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 11 / 285 Ghi chú Proposition
A proposition is a declarative sentence that is either true or false.
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 12 / 285 20:56, 09/01/2026
Discrete Mathematics and Its Applications - 131 Lecture Notes - Studocu Ghi chú Examples of propositions:
The Moon is made of green cheese.
Tokyo is the capital of Vietnam.
Toronto is the capital of Canada. 1 + 0 = 1. 0 + 0 = 2.
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 13 / 285 Ghi chú
Examples that are not propositions: Sit down! What time is it? x + 1 = 2. x + y = z.
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 14 / 285 Ghi chú
- The proposition that is always true is denoted by T; always false is denoted by F.
- We usually use letters such as p, q, r, s ... to denote propositions,
they are called propositional varialbes.
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 15 / 285 20:56, 09/01/2026
Discrete Mathematics and Its Applications - 131 Lecture Notes - Studocu Ghi chú Let pbe a proposition. Definition (Negation) The negation of p, denoted by p(also denoted by ¯ p , is the
statement "It is not the case that p.” The proposition pis read "not p."
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 16 / 285 Ghi chú
Example: If p denotes pdenotes not the case that the earth is round.=, or more simply not round.=
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 17 / 285 Ghi chú
Definition (The truth value of the negation)
The truth value of the negation of p,
p, is the opposite of the truth value of p. TF F T
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 18 / 285 20:56, 09/01/2026
Discrete Mathematics and Its Applications - 131 Lecture Notes - Studocu Ghi chú Let pand qbe propositions. Definition (Conjunction)
The conjunction of pand q, denoted by p q, is the proposition "p and q”. The conjunction p
qis true when both pand qare true and is false otherwise. p q p q T T T T F F F T F F F F
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 19 / 285 Ghi chú Example: If p denotes then p
q denotes Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 20 / 285 Ghi chú Definition (Disjunction)
The disjunction of pand q, denoted by p q, is the proposition "p or q”. The disjunction p
qis false when both pand qare false and is true otherwise. T T T T F T F T T F F F
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 21 / 285 20:56, 09/01/2026
Discrete Mathematics and Its Applications - 131 Lecture Notes - Studocu Ghi chú Example: If p denotes then p
q denotes Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 22 / 285 Ghi chú Definition (Exclusive Or)
The exclusive or of pand q, denoted by p q, is the proposition "p or q, but not both".
The exclusive or of pand qis true when exactly one of pand qis true and is false otherwise. T T F T F T F T T F F F
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 23 / 285 Ghi chú Example: If p denotes then p
q denotes Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 24 / 285 20:56, 09/01/2026
Discrete Mathematics and Its Applications - 131 Lecture Notes - Studocu Ghi chú
Definition (Conditional Statement) The conditional statement p
qis the proposition "if p, then q." p
qis false when pis true and qis false, and true otherwise. T T T T F F F T T F F T
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 25 / 285 Ghi chú
- In the conditional statement p
q,pis called the hypothesis (or
antecedent or premise) and qis called the conclusion (or consequence).
- A conditional statement is also called an implication.
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 26 / 285 Ghi chú Example: If p denotes then p
q denotes Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 27 / 285 20:56, 09/01/2026
Discrete Mathematics and Its Applications - 131 Lecture Notes - Studocu Ghi chú Some other ways to express p q:
"if p, then q” ”pimplies q” ”if p,q” ”ponly if q” ”pis sufficient for q”
” a sufficient condition for qis p” ”qif p” ”qwhenever p”
”qwhen p” ”qis necessary for p”
”anecessary condition for pis q” ”qfollows from p” ”qunless p”
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 28 / 285 Ghi chú
Converse, Contrapositive, Inverse From p
q, we can form new conditional statements. q pis called the converse of p q q pis called the contrapositive of p q p qis called the inverse of p q
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 29 / 285 Ghi chú
Example: Find the converse, inverse, and contrapositive of "It
raining is a sufficient condition for my not going to town." Solution:
Converse: If I do not go to town, then it is raining.
Inverse: If it is not raining, then I will go to town.
Contrapositive: If I go to town, then it is not raining.
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 30 / 285 20:56, 09/01/2026
Discrete Mathematics and Its Applications - 131 Lecture Notes - Studocu Ghi chú
Definition (Biconditional Statement) The conditional statement p
qis the proposition "p if and only if q." p
qis true when pand qare of the same true values, is false otherwise. T T T T F F F T F F F T
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 31 / 285 Ghi chú
- A biconditional statement is also called a bi-implication.
Example: Let pbe the statement "You can take the flight" and let
qbe the statement "You buy a ticket." Then p qis the statement
"You can take the flight if and only if you buy a ticket."
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 32 / 285 Ghi chú Some other ways to express p q:
"pis necessary and sufficient for q." "if pthen q, and conversely." "piff q.
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 33 / 285 20:56, 09/01/2026
Discrete Mathematics and Its Applications - 131 Lecture Notes - Studocu Ghi chú Compound Propositions
- Compound propositions are propositions which are formed by
existing propositions using logical operators. Example: The truth table of p q p q . p q q p q p q p q p q T T F T T T T F T T F F F T F F F T F F T T F F
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 34 / 285 Ghi chú The truth table of p q r: p q r rp q p q r T T T F T F T T F T T T T F T F T F T F F T T T F T T F T F F T F T T T F F T F F T F F F T F T
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 35 / 285 Ghi chú
Translate sentences using propositional variables and logical connectives
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 36 / 285 20:56, 09/01/2026
Discrete Mathematics and Its Applications - 131 Lecture Notes - Studocu Ghi chú
There are 2 steps to translate:
- Identify atomic propositions and represent using propositional variables.
- Determine appropriate logical connectives.
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 37 / 285 Ghi chú
Example: "If I go to Tuấn’s or to the country, I will not go shopping." Solution: p: I go to Tuấn’s. q: I go to the country. r: I will go shopping. Answer: p q r
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 38 / 285 Ghi chú
Section 1.2: Propositional Equivalences
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 39 / 285 20:56, 09/01/2026
Discrete Mathematics and Its Applications - 131 Lecture Notes - Studocu Ghi chú
Tautology, Contradiction, and Contingency
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 40 / 285 Ghi chú Definition (Tautology)
A compound proposition that is always true, is called a tautology.
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 41 / 285 Ghi chú Example: Hình: Tautology
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 42 / 285 20:56, 09/01/2026
Discrete Mathematics and Its Applications - 131 Lecture Notes - Studocu Ghi chú Definition (Contradiction)
A compound proposition that is always false, is called a contradiction.
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 43 / 285 Ghi chú Example: Hình: Contradiction
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 44 / 285 Ghi chú Definition (Contingency)
A compound proposition that is neither a tautology nor a
contradiction, is called a contingency.
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 45 / 285 20:56, 09/01/2026
Discrete Mathematics and Its Applications - 131 Lecture Notes - Studocu Ghi chú Example: Hình: Contingency
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 46 / 285 Ghi chú Logical Equivalence
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 47 / 285 Ghi chú
Let A, B be two compound propositions.
Definition (Logical Equivalence)
A and B are said logically equivalent if they always have the same truth values.
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 48 / 285 20:56, 09/01/2026
Discrete Mathematics and Its Applications - 131 Lecture Notes - Studocu Ghi chú We denote A Bor A
Bif A and B are logically equivalent. Example: p q p q. p q p q p q p q p q T T T F F F F T F T F F T F F T T F T F F F F F T T T T
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 49 / 285 Ghi chú Example: p q r p q p r p q r q r p q r p q p r p q p r T T T T T T T T T T F F T T T T T F T F T T T T T F F F T T T T F T T T T T T T F T F F F T F F F F T F F F T F F F F F F F F F
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 50 / 285 Ghi chú
Some Basic Logical Equivalences
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 51 / 285 20:56, 09/01/2026
Discrete Mathematics and Its Applications - 131 Lecture Notes - Studocu Ghi chú
Hình: Some logical equivalences - Table 6, page 24, the book by Rosen
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 52 / 285 Ghi chú
Hình: Some logical equivalences - Table 6, page 24, the book by Rosen
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 53 / 285 Ghi chú
Some more logical equivalences, which are useful: p q p q p q q p
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 54 / 285 20:56, 09/01/2026
Discrete Mathematics and Its Applications - 131 Lecture Notes - Studocu Ghi chú
In order to check whether a compound proposition is tautology or
not, we may contruct a truth table. But beside this way, we may have
another way to do this: make use of logically equivalences already given above. Example: Show that p q p q is a tautology.
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 55 / 285 Ghi chú Solution: p q p q p q p q by truth table for p q p q by the first De Morgan law p p q q by associative and commutative laws T Tlaws for disjunction Tby truth tables domination law
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 56 / 285 Ghi chú
Section 1.3: Predicates and Quantifiers
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 57 / 285 20:56, 09/01/2026
Discrete Mathematics and Its Applications - 131 Lecture Notes - Studocu Ghi chú Definitions
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 58 / 285 Ghi chú
One of the effects of the propositional logic is to transtale many
sentences/ statements/ arguments ... in to a new ’language’ (The
language of propositional logic). This may be helpful because the new
language may help us understand the sentences/statements ... better.
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 59 / 285 Ghi chú
Now, we mention to a new way to translate sentences/statements ...
which have the form: "All ...", "There is ...". For example: - All cars have wheels.
- All basketball players at TLU are over 5 feet tall.
- There is a student in this class who is not affected by corolavirus.
- There is a person who never dies.
Discrete Mathematics and Its Applications Ngày 9 tháng 10 năm 2022 60 / 285