Syllabus:
by Prof. Sang-Gu Lee, sglee@skku.edu
http://matrix.skku.ac.kr/sglee/vita/LeeSG.htm
at Room 32304 (031-290-7025), Room 10109(02-760-1091)
Course Description:
Sets, relations, functions, graphs, trees, formal expressions, mathematical induction, and some algebraic structures; applications to probability and computer science and enumerative problems in combinatorial analysis. This course covers the fundamental abstract algebraic structures and concepts most often employed in computer science and probability and statistics. The ideas involved are simple, but elegant and useful and the course aims to convey some of the beauty of mathematics as well as its utility. The course integrates theory and practical applications.
Textbook :
Discrete Math - 7th Edition
Author : Richard Johnsonbaugh, DePaul University
Publisher : Pearson
Classroom : 23217 (Friday 12:00-2:45)
OH: Friday 10:00~11:30 others by appointment
Office: 32304 sglee@skku.edu (02-760-1091)
TA : LEE, Sumin(이수민 조교) 010-2474-2139 Office: 32356-C OH: Mon & Wed PM 3-4
e-mail: dltnals816@skku.edu
Grade :
Midterm 40%, Final 40%, Quiz 10%, Homework 5%, Off-Online attendance 5%
A : 10%
B+ : 15%
B : 15%
C+ : 15%
C : 15%
D, F : 20%
More details are in
http://math.newark.rutgers.edu/~bl498/teaching/237Fall2017/#textbook
THIS COURSE COVERS THE FOLLOWING CHAPTERS AND SECTIONS:
Table of Contents
1 Sets and Logic
1.1 Sets
1.2 Propositions
1.3 Conditional Propositions and Logical Equivalence
1.4 Arguments and Rules of Inference
1.5 Quantifiers
1.6 Nested Quantifiers
Problem-Solving Corner: Quantifiers
2 Proofs
2.1 Mathematical Systems, Direct Proofs, and Counter-examples
2.2 More Methods of Proof
2.3 Resolution Proofs (Skip)
2.4 Mathematical Induction
2.5 Strong Form of Induction and the Well-Ordering Property
3 Functions, Sequences, and Relations
3.1 Functions
3.2 Sequences and Strings
3.3 Relations
3.4 Equivalence Relations
3.5 Matrices of Relations
3.6 Relational Databases (Skip)
4 Algorithms
4.1 Introduction
4.2 Examples of Algorithms
4.3 Analysis of Algorithms
4.4 Recursive Algorithms
5 Introduction to Number Theory (if time permits)
5.1 Divisors
5.2 Representations of Integers and Integer Algorithms
5.3 The Euclidean Algorithm
5.4 The RSA Public-Key Cryptosystem (Skip)
6 Counting Methods and the Pigeonhole Principle (lightly covered)
6.1 Basic Principles
6.2 Permutations and Combinations
6.3 Generalized Permutations and Combinations
6.4 Algorithms for Generating Permutations and Combinations (Skip)
6.5 Introduction to Discrete Probability (Skip)
6.6 Discrete Probability Theory (Skip)
6.7 Binomial Coefficients and Combinatorial Identities
6.8 The Pigeonhole Principle
7 Recurrence Relations
7.1 Introduction
7.2 Solving Recurrence Relations
7.3 Applications to the Analysis of Algorithms (Skip)
8 Graph Theory (if time permits)
8.1 Introduction
8.2 Paths and Cycles
8.3 Hamiltonian Cycles and the Traveling Salesperson Problem
8.4 A Shortest-Path Algorithm
8.5 Representations of Graphs
8.6 Isomorphisms of Graphs
8.7 Planar Graphs
8.8 Instant Insanity (Skip)
9 Trees (if time permits)
9.1 Introduction
9.2 Terminology and Characterizations of Trees
9.3 Spanning Trees
9.4 Minimal Spanning Trees
9.5 Binary Trees
9.6 Tree Traversals
9.7 Decision Trees and the Minimum Time for Sorting
9.8 Isomorphisms of Trees
9.9 Game Trees (Skip)
10 Network Models (if time permits)
11 Boolean Algebras and Combinatorial Circuits (if time permits)
12 Automata, Grammars, and Languages (if time permits)
13 Computational Geometry (if time permits)
Appendix
A Matrices, B Algebra Review
References
http://math.newark.rutgers.edu/~bl498/teaching/237Fall2017/quiz1.pdf
Contents
(One semester course: Sample)
1 The Foundations: Logic and Proofs . . . . . . . .
2 Basic Structures: Sets, Functions, Sequences, Sums, and Matrices
3 Algorithms . . . . . . . . . . . . . . . . . . .
4 Number Theory and Cryptography . . . . .
5 Induction and Recursion . . . . . . . . . . .
6 Counting . . . . . . . . . . . . . . . . . . .
7 Discrete Probability . . . . . . . . . . . . .
8 Advanced Counting Techniques . . . . . . . .
9 Relations
10 Graphs . . . . . . . . . . . . . . . .
11 Trees . . . . . . . . . . . . . . . .
12 Boolean Algebra . . . . . . . . . . .
13 Modeling Computation . . . . . . . .
Appendixes
http://math.newark.rutgers.edu/~bl498/teaching/237Fall2017/
Weekly Schedule (Tentative)
http://math.newark.rutgers.edu/~bl498/teaching/237Fall2017/
Week |
Section covered |
Remarks |
1 |
Orientation |
|
2 |
1 Sets and Logic (HW1) |
|
3 |
2 Proofs |
Skipped section: 2.3
|
4 |
3 Functions, Sequences (Quiz1) |
|
5 |
3 Relations |
Skipped section: 3.6 EXAM #1 , EXAM #1 Solutions |
6 |
4 Algorithms (HW2) |
|
7 |
5 Number Theory (if time permits) |
Skipped section: 5.4 |
8 |
Midterm Exam |
|
9 |
6 Counting Methods (HW3) |
|
10 |
6 the Pigeonhole Principle (lightly covered) |
Skipped sections: 6.4, 6.5, 6.6 |
11 |
7 Recurrence Relations (Quiz2) |
Skipped section: 7.3 |
12 |
8 Graph Theory (HW4) |
|
13 |
8.5-8.7 : Graph Theory (if time permits) |
Skipped section: 8.8 |
14 |
9 Trees |
|
15 |
9.5-9.8 : Trees (if time permits) |
Skipped section: 9.9 |
16 |
New Final Exam |
[Notations]
1. For all <=> 2. such that <=>
3. There exist <=> 4. Therefore <=>
5. Because <=> 6. imply <=>
7. if and only if (iff) <=> 8. QED <=> (Halmos's square) ■
9. set of reals <=> 10. set of complex numbers <=>
11. in
Your Mathematics (Big Picture)
1. Calculus Concept http://matrix.skku.ac.kr/Calculus-Story/index.htm
Calculus (English)http://matrix.skku.ac.kr/Cal-Book/
2. Linear Algebra (English) http://matrix.skku.ac.kr/LA/ -
3. Discrete Math :
http://matrix.skku.ac.kr/sglee/2003-f-DM-Lecture/WhatIsDM.htm
http://matrix.skku.ac.kr/sglee/2003-f-DM-Lecture/DM-MathOfOurDay.htm
http://matrix.skku.ac.kr/sglee/2003-f-DM-Lecture/BL-DM-PBL.htm
http://matrix.skku.ac.kr/sglee/2003-f-DM-Lecture/CH-1-Lec/index.html
http://matrix.skku.ac.kr/sglee/2003-f-DM-Lecture/CH-2-Lec/index.html
http://matrix.skku.ac.kr/sglee/2003-f-DM-Lecture/CH-3-Lec/index.html
http://matrix.skku.ac.kr/sglee/catalan/catalan.htm
http://matrix.skku.ac.kr/sglee/fibonacci/fibo.htm
http://matrix.skku.ac.kr/sglee/skku-fibo/index.html
http://matrix.skku.ac.kr/sglee/skku-fibo2/3.htm
4. Statistics http://matrix.skku.ac.kr/2018-album/R-Sage-Stat-Lab-1.html
http://matrix.skku.ac.kr/2018-album/R-Sage-Stat-Lab-2.html
5. DE http://www.hanbit.co.kr/EM/sage/1_chap5.html
6. Complex Variables http://www.hanbit.co.kr/EM/sage/2_chap14.html
7. Engineering Math http://www.hanbit.co.kr/EM/sage/
8. Stat 4 BigData http://matrix.skku.ac.kr/E-Math/
9. Math4BigData http://matrix.skku.ac.kr/2017-Album/2017-Math-Modeling.htm
...
1 Sets and Logic
1.1 Sets (High school - 집합 )
1.2 Propositions (High school - 명제)
1.3 Conditional Propositions and Logical Equivalence (High school - 진리표)
1.4 Arguments and Rules of Inference (High school - 추론)
1.5 Quantifiers (For all , such that , There exist )
1.6 Nested Quantifiers ( )
1 Sets and Logic
Discrete mathematics deals with graphs and Boolean Algebras.
Set is a collection of objects.
Logic is the study of reasoning.
Logic is the true and false judgments.
1.1 Sets
Set is a collection of objects. The objects are elements or numbers. |
The vertical bar “|” is read “such that.”
read “ equals the set of all is a positive, even integer.”
Symbol
is the set of natural numbers.
(or ) is the set of integers.
is the set of rational numbers.
is the set of real numbers.
For example,
is the set of positive integers.
is the set of negative integers.
is the set of positive rational numbers.
is the set of negative rational numbers.
is the set of positive real numbers.
is the set of negative real numbers.
nonneg is the non-negative numbers.
is the set of non-negative integers.
is the set of non-negative rational numbers.
is the set of non-negative real numbers.
Cardinality |
|
is a finite set numbers of elements in . is the cardinality of . |
Example 1.1.1 |
|
The cardinality of is . The cardinality of is . contains two elements and . |
means ( imply, =>, ) is in the set .
means is not in the set .
Empty set |
|
The empty (null or avoid) set is the set with no elements. The empty set denoted and . |
Equal |
|
Two sets and are equal. (i) (ii) If and have the same elements. |
, . (Every element of is an element of .)
, . (Every element of is an element of .)
Example 1.1.2 |
|
If and . then and have the same elements. Therefore, . |
Example 1.1.3 |
|
If and ((because, ) , ) then and have the same elements. Therefore . |
: Set to not be equal to set .
and must not have the same elements. (means)
such that : There must be at least one element in that is not in .
such that : There must be at least one element in that is not in .
Example 1.1.4 |
|
Let and . . Therefore . |
Subset |
|
and are sets. is a subset of . Every element of is an element of . |
is a subset of is contained in contains
, .
Example 1.1.5 |
|
If and then every element of is an element of . Therefore . |
Let be a set.
Example 1.1.6 |
|
Let . Show that . or . , . Therefore . |
Example 1.1.7 |
|
The set of integers is a subset of the set of rational numbers . , . Therefore . |
There is at least one element such that and .
Example 1.1.9 |
|
Let . Show that . or . Taking , . Therefore, . |
Any set is a subset of itself.
, .
is a subset of every set.
Proper subset |
|
and . : Every element of is in but there is at least one element of that is not in . is a proper subset of . Notation . |
Example 1.1.10 |
|
Let and . and . |
Power Set |
|
is the set of all subsets(proper or not) of a set . is the power set of . |
Example 1.1.13 |
|
If , the numbers of are , , , , , , , . , , , , , , are proper subset of . |
The power set of a set with elements has elements.
Given two sets and . The set
is the union of and . The union consists of all elements belonging to , or both.
The set
is the intersection of and . The intersection consists of all elements belonging to both and .
The set
is the difference (or relative complement). The difference consists of all elements in that are not in . |
Example 1.1.14 |
|
If and , then
In general, . |
Example 1.1.15 |
|
Since ,
|
Set (or ) is the set of irrational numbers.
Set consists of all real numbers that are not rational.
Disjoint |
|
Sets and are disjoint. and are distinct sets in , and are disjoint A collection of sets is pairwise disjoint. |
Example 1.1.16 |
|
The sets and are disjoint. The collection of sets
is pairwise disjoint. |
is a universal set or universe. Given a universal set and , the set is the complement of . is the complement of . |
Example 1.1.17 |
|
Let . If is a universal set, then . If is a universal set, then . |
Example 1.1.18 |
|
Let the universal set be . The complement of the set of negative integers is . is the set of nonnegative integers. |
John Venn (1834-1923) British logician, philospher
Venn diagram |
|
In a Venn diagram, a rectangle depicts universal set. Subsets of the universal set are drawn as circles. The inside of a circle represents the numbers of that set. |
Example 1.1.19 |
|
A Venn diagram of A Venn diagram of A Venn diagram of |
Example 1.1.20 |
|
Among a group of students, are taking calculus, psychology and computer science ; are taking calculus and computer science ; are taking calculus and psychology ; are taking psychology and computer science ; are taking calculus ; are taking psychology ; and are taking computer science. How many are taking none of the three subjects? |
Solution: A Venn diagram of three sets CALC, PSYCH and COMPSCI.
The numbers show how many students belong to the particular region depicted.
Theorem 1.1.21 |
|
Let be a universal set and let , and be subsets of . |
Idempotent laws |
|
|
Associative laws |
|
|
Commutative laws |
|
|
Distributive laws |
|
|
Identity laws |
|
|
|
|
|
Involution laws |
|
|
Complement laws |
|
|
|
|
|
De Morgan's laws |
|
|
Absorption laws |
|
|
.
We define the union of an arbitrary family of sets to be those elements belonging to at least one set in .
.
We define the intersection of an arbitrary family of sets to be those elements belonging to every set in .
If
(a finite set)
then
, .
If
(an infinite set)
then
, .
Example 1.1.22 |
|
For , define and . Then , . |
Partition |
|
A partition of a set divides into non-overlapping subsets. A collection of non-empty subsets of is a partition of the set if every element in belongs to exactly one member of . , If is a partition of , then is pairwise disjoint . |
Example 1.1.23 |
|
Each element of
is in exactly one member of . is a partition of . |
Ordered pair |
|
An ordered pair is a pair of objects. The ordered pair is different from the ordered pair unless . and . |
Cartesian product |
|
and are sets. The cartesian product is the set of all ordered pair where and . is the Cartesian product of and . |
read “ cross .”
is the set of all ordered pairs , where and .
For arbitrary finite sets and that is true.
The Cartesian product of sets is defined to be the set of all tuples where for : it is denoted .
Example 1.1.26 |
|
If , , then
|
.
In general
.
1.2 Propositions (명제)
If a sentence is either true or false (but not both) is called a proposition (or statement).
The propositions are the basic building blocks of any theory of logic.
Definition 1.2.1 |
|
Let and be propositions. is conjunction of and . is read the proposition of “ and .” is disjunction of and . is read the proposition of “ or .” |
Example 1.2.2 |
|
It is raining, It is cold, The conjunction of and is It is raining and it is cold. The disjunction of and is It is raining or it is cold. |
The truth value of the propositions such as conjunctions and disjunction can be described by truth tables.
Definition 1.2.3 |
|
||||||||||||||||||
The truth value of the proposition is defined by truth table
|
and are both true The conjunction is true.
Otherwise The conjunction is false.
Example 1.2.4 |
|
A decade is years. A millennium is years. then is true, is false (a millennium is years). A decade is years and a millennium is years, is false. |
The inclusive-or of propositions and is true if or , or both is true.
Definition 2.6 |
|
||||||||||||||||||
The truth value of the proposition is defined by truth table
|
is the inclusive-or of and .
and are both false The conjunction is false.
Otherwise The conjunction is true.
Example 1.2.7 |
|
A millennium is years. A millennium is years. then is false, is true. The disjunction, A millennium is years or a millennium is years, is true. |
We discuss in the negation of .
Definition 2.9 |
|
is the proposition. is the negative of . is the proposition not . “” is read “not .” or “It is not the case that .” The truth value of the proposition is defined by truth table. |
but means and
neither nor means and .
Truth Table |
|
|
|
|
|
|
|
is the proposition.
is the negation of .
“” is read “not .”or “It is not the case that .”
[For example]
Paris is the capital of England.
It is not the case that Paris is the capital of England.
Paris is not the capital of England.
Operator precedence |
|
The operator , , and using in the absence of parentheses. The order of operation is , , and . In algebra, operator precedence tells us to evaluate and / before and . |
Example 1.2.12 |
|
Proposition is false, proposition is true, and proposition is false. Determine whether the proposition
is true and false. |
Solution
Truth Table |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
is false is true.
We next evaluate
is true, is false is false.
Finally we evaluate
is true, is false () is true.
1.3 Conditional Propositions and Logical Equivalence
Definition 1.3.1 |
Conditional Proposition |
If and are proposition, the proposition if then is a conditional proposition. () : if then . Proposition is hypothesis (or antecedent, 가설). Proposition is conclusion (or consequent, 결론). |
Example 1.3.2 |
hypothesis conclusion |
The Mathematics Department gets an additional . The Mathematics Department will hire one new faculty member. The hypothesis is “The Mathematics Department gets an additional .” The conclusion is “The Mathematics Department will hire one new faculty member.” |
Definition 1,3.3 |
Truth table |
||||||||||||||||||||||||||||||||||||||||||||||||
The truth value of the conditional proposition is defined by truth table:
|
is true and is false is false.
Otherwise is true.
Example 1.3.4 |
|
Let , Then is false and is true. Therefore is true, is false. |
In expressions that involve the logical operators , , and , the conditional operator is evaluated last.
For example
is interpreted.
Example 1.3.5 |
Truth table |
is true, is false and is true, find the truth value of each proposition. (a) (b) (c) (d) |
Solution
Truth table |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(a) is true and is false is false.
is true.
is false and is true is true.
(b) is true and is false is true.
is true is false.
Truth Table |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
is true and is false is false.
(c) is false and is true is true.
is true.
is true and is true is true.
(d) is false and is true is true.
Truth Table |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
is true and is true is true.
true by default or vacuously true (가정이 False이면 항진명제)
hypothesis is false conditional proposition is true
true by default (언제나 True, 항진명제)
Example 1.3.7 |
|
Write the conditional proposition. If Jerry receives a scholarship, then he will go to college, and its converse symbolically and in words. Find the truth value of the original proposition and its converse. |
Solution
Let
Jerry receives a scholarship.
Jerry go to college.
The given proposition can be written symbolically as .
The hypothesis is false, the conditional proposition is true.
The converse of the proposition is
If Jerry goes to college, then he receives a scholarship.
The converse can be written symbolically as .
Since the hypothesis is true and the conclusion is false, the converse is false.
if and only if
This proposition is true when and have same truth values.
Definition 1.3.8 |
Biconditional Proposition |
and are proposition, the proposition
is a biconditional proposition. () : . The proposition is hypothesis(or antecedent). The proposition is conclusion(or consequent). |
The truth value of the biconditional proposition is defined by truth table.
Truth Table |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Truth Table |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
and have same truth values is true.
Otherwise is false.
“ ” is “ is a necessary and sufficient condition for .”
The proposition “ ” is sometimes written “ iff .”
Example 1.3.9 |
|
The proposition is . Symbolically is
if we define . and are true, the proposition is true. |
Definition 1.3.10 |
|
Propositions and are made up of the propositions . and are logically equivalent. , provided that, given any truth values of , either and are both true, or and are both false. |
, and are logically equivalent.
Augustus De Morgan(1806-1871) British mathematician, logician
Example 1.3.11 |
De Morgan’s laws for Logic |
Show that . |
Solution
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
By writing the true tables for and .
Given any truth values of and , either and are both true or and are both false.
and are logically equivalent.
Example 1.3.13 |
|
Show that the negation of is logically equivalent to . |
Solution
[Show : ]
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
By writing the true tables for and .
Given any truth values of and , either and are both true or and are both false.
and are logically equivalent. ■
Example 1.3.14 |
|
Use the logical equivalence of and to write the negation of If Jerry receives a scholarship, then he goes to college, symbolically and in words. |
Solution
We let
Jerry receives a scholarship.
Jerry goes to college.
The given proposition can be written symbolically as . Its negation logically equivalent to .
In words, this last expression is
Jerry receives a scholarship, then he does not go to college.
is logically equivalent to .
In words
is logically equivalent to
if then and if then . ■
Definition 1.3.16 |
contrapositive 대우 |
The contrapositive (or transpositive) of the conditional proposition is the proposition . |
The converse of the conditional proposition is the proposition .
The inverse of the conditional proposition is the proposition .
Example 1.3.17 |
|
Write the conditional proposition, If the network is down, then Dale cannot access the internet, symbolically. Write the contrapositive and the converse symbolically and in words. |
Solution
Let
The network is down,
Dale cannot access the internet.
The symbolically of given proposition is .
The hypothesis is false, the conditional proposition is true.
The symbolically of contrapositive is .
In words,
If Dale can access the internet, then the network is not down.
The hypothesis and the conclusion are both true, the contrapositive is true.
The symbolically of converse is .
In words
If Dale cannot access the internet, then the network is down.
The hypothesis is false, the converse is true.
Theorem 1.3.18 |
|
Conditional proposition and its contrapositive are logically equivalent. |
Proof
The truth table
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
show that and are logically equivalent.
1.4 Arguments and Rules of Inference (추론)
The process of drawing a conclusion from a sequence of propositions is deductive reasoning(연역적 추론, 演繹的推論) (예: 3단논법).
Deductive reasoning is the process of reasoning form hypothesis to reach a conclusion.
The given propositions are the hypotheses or premises.
The proposition that follows from the hypotheses are the conclusion.
A (deductive) argument consist of hypotheses together with a conclusion.
Any deductive argument form
(1.4.3) If and and and , then .
Argument (1.4.3) is valid if the conclusion follows from the hypotheses.
If and and and are true, then is true.
Definition 1.4.1 |
|
Argument is a sequence of propositions
or . Symbol is read “therefore.” Propositions , , , are the hypotheses (or premises). Proposition is the conclusion. |
The argument is valid.
If and and and are true, then is true
Otherwise, the argument is invalid(or fallacy).
Rules of inference(추론), valid argument are used within a larger argument.
Example 1.4.2 |
The Modus ponens(긍정논법) rule of inference or law of detachment |
Determine whether the argument
is valid. |
Solution
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
First solution
By truth table.
The hypotheses and are true, the conclusion is true.
The argument is valid.
Second solution
Using the truth table by directly verifying.
The hypotheses are true, the conclusion is true.
and are true, is true. Otherwise would be false.
(즉, 이고 가 true이면 는 true인데, 만일 가 true가 아니라면 가 false라는 말인데, 그러면 가정에 모순이 된다)
The argument is valid. (따라서 맞는 argument 이다)
Rule of Inference |
Name |
Rule of Inference |
Name |
|
Modulus poenens (긍정식 논법) |
|
Conjunction (논리곱) |
|
Modulus tollens (부정식 논법) |
|
Hypothetical syllogism 가설적 삼단논법 (假言的三段論法) |
|
Addition (추가법) |
|
Disjunctive syllogism 논리합 삼단논법 (選言的 三段論法) |
|
Simplification(단순화) |
|
|
Figure 4.1 Rules of inference for propositions.
Example 1.4.3 |
Hypothetical Syllogism 가언적 삼단논법(假言的三段論法) |
Which rule of inference is used in the following argument? If the computer has one gigabyte of memory, then it can run “Blast’em.” If the computer can run “Blast’em,” then the sonics will be impressive. Therefore, if the computer has one gigabyte of memory, then the sonics will be impressive. |
Solution
Proposition is “the computer has one gigabyte of memory.”
Proposition is “the computer can run ‘Blast’em.”
Proposition is “the sonics will be impressive.”
The argument symbol is
The argument uses the hypothetical syllogism rule of inference(추론).
Example 1.4.4 |
The fallacy of affirming the conclusion |
Represent the argument
symbolically and determine whether the argument is valid. |
Solution
If we let
, I ate my hat
the argument
The argument is valid.
and are true is true.
and are true
This is possible if is false and is true.
In this case is not true thus the argument is invalid.
This fallacy is the fallacy of affirming the conclusion.
Example 1.4.5 |
|
Represent the argument The bug is either in module or in module . The bug is a numerical error. Module has no numerical error.
The bug is in module . given at the beginning of this section symbolically and show that it is valid. |
Solution
If we let
Proposition The bug is in module .
Proposition The bug is in module .
Proposition The bug is a numerical error.
The argument is
Using modus ponens
From and to conclude .
Using the disjunctive syllogism
From and to conclude .
The conclude follows from the hypotheses.
The argument is valid.
Example 1.4.6 |
|
Let Argument the (San Diego) Chargers get a good linebacker Argument the Chargers can beat the (Denver) Broncos Argument the Chargers can beat the (New York) Jets Argument the Chargers can beat the (Miami) Dolphins. |
Solution
The argument is
and Using hypothetical syllogism to conclude .
and Using modus ponens to conclude .
and Using hypothetical syllogism to conclude .
and Using modus ponens to conclude .
and Using conjunction to conclude .
Argument : the (San Diego) Chargers can beat the (New York) Jets and the Chargers can beat the (Miami) Dolphins.
The conclude does follows from the hypotheses. ■
1.5 Quantifiers (수량사(all, both처럼 양을 나타내는 한정사(determiner)나 대명사))
Definition 1.5.1 |
|
is a statement involving the variable . is a set. For each , is a proposition is a propositional function (명제 함수) or predicate (서술부, 敍述語) (with respect to ). is the domain of discourse (담론영역, universal set) of . |
* is a property that elements of has.
the set of all elements in such that is true
Example 1.5.2 |
|
The statement is an odd integer. is a propositional function with domain of discourse since for each is a proposition. |
For example,
If , we obtain the proposition
: is an odd integer.
is true.
If , we obtain the proposition
: is an odd integer.
is false.
For example,
If is a propositional function with domain of discourse , we obtain the class of proposition
.
Each is either true or false.
Definition 1.5.4 |
|
is a propositional function with domain of discourse . The statement for every , is a universally quantified statement of . The symbol means “for every.” The symbol is a universal quantifier (범용 정량자, ∀). |
The statement
is true, is true.
The statement
is false if is false for at least one .
is false is called a counter-example of .
Example 1.5.5 |
|
Consider the universally quantified statement . The domain of discourse is . |
Solution
is true.
is positive or zero.
The universally quantified statement
is false
if for at least one in the domain of discourse, the proposition is false.
A value in the domain of discourse that makes false is
a counterexample to the statement .
Example 1.5.6 |
|
The universally quantified statement is . The domain of discourse is . |
Solution
is false
If , the proposition
is false.
The value is counterexample to the statement
.
Although there are value of that makes the propositional function true, the counterexample provided shows that the universally quantified statement is false.
Example 1.5.7 |
|
is a propositional function whose domain of discourse is the set . The following pseudocode determines whether
is true or false: for to if return false return true |
The for loop examines the numbers in the domain of discourse one by one.
is false the condition in the if statement is true.
So the code returns false and terminates.
is counterexample.
, is true the condition is false.
The for loop runs to completion, after which the code returns true and terminates.
, is true, the for loop necessarily runs to completion so that every member of the domain of discourse is checked to ensure that is true for every .
, is false, the for loop terminates as soon as one element of the domain of discourse is found for which is false.
The variable is a free variable.
The variable in the universally quantified statement
is a bound variable.
A statement with free variables is not a proposition.
A statement with no free variables is a proposition.
for all , for any , .
The symbol may be read “for every,” “for all” or “for any.”
To prove that
is true.
We must every value of in the domain of discourse and show that is true.
The domain of discourse , we write a universal quantified statement as
, .
Example 1.5.8 |
|
The universally quantified statement , if , then is true. |
Solution
Verify that statement
if , then
is true for every real number .
Let .
It is true for any real number , either or .
If , the conditional proposition
if , then
is vacuously true.
If , the conditional proposition
if , then
is true.
If , the hypothesis and conclusion are both true.
Hence the conditional proposition
if , then
is true.
The universally quantified statement
, if , then
is true.
Definition 1.5.9 |
|
Let be a propositional function with domain of discourse . The statement there exists , is an existentially quantified statement. The symbol means “there exists.” The symbol is an existential quantifier of . |
The statement
is true if is true for at least one .
The statement
is false. is false.
The existential quantification is read as
“There is an such that ,”
“There is at least one such that ,”
or
“For some is true.”
Example 1.5.10 |
|
Consider the existentially quantified statement . The domain of discourse is . |
Solution
The statement is true because it is possible to find at least one real number for which the proposition
is true.
For example , we obtain the proposition
is true.
It is not the case that every value of results in a true proposition.
For example , we obtain the proposition
is false.
For every in the domain of discourse, the proposition is false
the existentially quantified statement is false.
Example 1.5.11 |
|
To verify that the existentially quantified statement
is false, we must show that
is false for every real number . Now
is false precisely when
is true. Thus, we must show that
is true for every real number . Let be any real number whatsoever. Since . If we divide both sides of this last inequality by , we obtain . Therefore, the statement
is true for every real number . Thus the statement
is false for every real number . We have shown that the existentially quantified statement
is false. |
Example 1.5.12 |
|
Suppose that is a propositional function whose domain of discourse is the set . The following pseudocode determines whether
is true or false: for to if return true return false |
The for loop examines the numbers in the domain of discourse one by one.
find is true the condition in the if statement is true.
So the code returns true and terminates.
The code found a value in the domain of discourse, is true.
, is false the condition is false.
The for loop runs to completion, after which the code returns false and terminates.
, is true, the for loop terminates as soon as one element in the domain of discourse is found for which is true.
, is false, the for loop necessarily runs to completion so that every member in the domain of discourse is checked to ensure that is false for every .
Alternative ways to write
there exists such that, for some ,
for at least one ,
The symbol may be read “there exists,” “for some” or “for at least one.” ■
Example 1.5.13 |
|
Consider the existentially quantified statement for some , if is prime, then , , and are not prime. The domain of discourse is . This is statement is true. We can find at least one positive integer that makes the conditional proposition if is prime, then , , and are not prime true. |
For example, if , we obtain the true proposition
if is prime, then and are not prime.
The point is that we found one value the makes the conditional proposition
if is prime, then , , and are not prime
true.
For this reason, the existentially quantified statement
for some , if is prime, then , , and are not prime
is true. ■
Theorem 1.5.14 |
Generalized De Morgan’s Laws for Logic |
If is a propositional function, each pair of propositions in (a) and (b) has the same truth values (i.e., either both are true or both are false). (a) (b) |
Proof
Proposition is true Proposition is false.
By Definition 5.4,
is false for at least one in the domain of discourse
Proposition is false.
is false for at least one in the domain of discourse
is true for at least one in the domain of discourse.
By Definition 5.9,
is true for at least one in the domain of discourse
Proposition is true.
Proposition is true Proposition is true.
Similarly,
if the proposition is false, the proposition is false. ■
Example 1.5.16 |
https://youtu.be/uDkBzkA9L4s U2 (Irish rock band from Dublin) |
The proposition is Every rock fan loves U2. Write its negation symbolically and in words. |
Solution
Let be the propositional function “ loves U2.”
The symbolic logic of the proposition is
.
The domain of discourse is the set of rock fans.
The negative of the proposition is
.
In word, the negative of the proposition is
There exists a rock fan who does not love U2.
Example 1.5.17 |
|
The proposition is Some birds cannot fly. Write its negation symbolically and in words. |
Solution
Let be the propositional function “ flies.”
The symbolic logic of the proposition is
.
The domain of discourse is the set of birds.
The negative of the proposition is
.
In word, the negative of the proposition is
Every bird can fly. ■
A universally quantified propositions generalize the proposition
(5.3)
in the sense that the individual propositions , , , are replaced by an arbitrary family , where is in the domain of discourse.
is replaced by
(5.4) .
The proposition is true is true for every .
The proposition is true is true for every in the domain of discourse.
Example 1.5.18 |
|
The domain of discourse of propositional function is . The propositional function is equivalent to . |
An existentially quantified propositions generalize the proposition
(5.5)
in the sense that the individual propositions , , , are replaced by an arbitrary family , where is in the domain of discourse.
is replaced by
.
Example 1.5.19 |
|
The domain of discourse of propositional function is . The propositional function is equivalent to . |
Rules of Inference for Quantified Statements
is true.
By Definition 5.4,
is true for every in the domain of discourse .
In particular, is true.
The argument
is valid.
This rule of inference is universal instantiation
(전칭 예시화, 추상적인 것을 구체적인 예를 통해서 표현하는 것).
Rule of Inference |
Name |
|
Universal instantiation (전칭 예시화) |
|
Universal generalization (전칭 일반화) |
|
Existential instantiation (존재 예시화) |
|
Existential generalization (존재 일반화) |
Figure 1.5.1 Rules of inference for quantified statement.
The domain of discourse is .
Example 1.5.21 |
|
Given that , is true. |
Using universal instantiation, to conclude
is a positive integer
Example 1.5.23 |
|
Write the following argument symbolically and then, using rules of inference, show that the argument is valid. , . is not rational. Therefore, is not an integer. |
denote the propositional function “ is an integer” and
denote the propositional function “ is rational,”
the argument becomes
( , using universal instantiation, to conclude
.
Combining and , using modus tollens(부정논법),
to conclude . ( 는 정수가 아니다) )
Thus the argument is valid.
This argument is called universal modus tollens. ■
1.6 Nested Quantifiers
Consider the statement
The sum of any two positive real numbers is positive.
That is “For all with and .”
We can rewrite it with two universal quantifiers ( and ) :
denote .
Symbolically it can be written as
.
In words, and , if and .
The domain of discourse of the two-variable proposition function is ,
each variable and .
Multiple quantifiers are nested quantifiers.
Example 1.6.1 |
|
in words. The domain of discourse is the set . For every , there exists such that . There is no greatest integer. |
Example 1.6.2 |
|
The proposition is Everybody loves somebody, Letting be the statement “ loves .” “Everybody” requires universal quantification “somebody” requires existential quantification. The symbolic logic of the proposition is . In words, for every person , there exist a person such that loves . |
Notice that
is not a correct interpretation of the original statement.
In words, there exist a person such that for all , loves .
Less formally, someone loves everyone.
The order of quantifiers is important; changing the order can change the meaning.
The statement
,
with domain of discourse , is true, if and then is true.
The statement
is false if and such that is false.
Example 1.6.3 |
|
The statement is . The domain of discourse is . and , the conditional proposition
is true. Hence, this statement is true. In words, and , if and are positive, the sum is positive. |
The statement is
.
The domain of discourse is .
and , the conditional proposition
is true.
Hence, this statement is true.
In words, and , if and are positive, the is positive.
Example 1.6.4 |
|
The statement is . The domain of discourse is . |
This statement is false because if and , the conditional proposition
is false.
The pair and is counterexample.
Example 1.6.5 |
|
is a propositional function with domain of discourse . The following pseudocode determines whether
is true or false: for to for to if return false return true |
The for loops examine members of the domain of discourse.
If they find a pair , for which is false, the condition in the if statement is true ; do the code returns false and terminates.
The pair , is a counterexample. If is true for every pair , , the condition in the if statement is always false.
The for loops run to completion, after which the code returns true [to indicate that is true] and terminates.
The statement
,
with domain of discourse , is true if , for which is true.
The statement is
is false if such that is false .
Example 1.6.6 |
|
Consider the statement . The domain of discourse is . , (namely ) for which is true. Hence, this statement is true. In words, , there is a number that when added to makes the sum zero. |
Example 1.6.7 |
|
The statement is . The domain of discourse is . namely , such that is false . Hence, this statement is false. |
Example 1.6.8 |
|
is a propositional function with domain of discourse . The following pseudocode determines whether
is true or false: for to if (exists_dj(i)) return false return true exists_dj(i) { for to if return true return false } |
If for each , there exists such that is true, then for each , is true for some .
Thus exist_dj(i) returns true for every .
Since exist_dj(i) is always false, the first for loop eventually terminates and true is returned to indicate that is true.
If for some , is false for every , then, for this , is false for every . The for loop in exist_dj(i) runs to termination and false is returned.
Since exist_dj(i) is true, false is returned to indicate that is false.
By definition, the statement
,
with domain of discourse , is true if there is at least one such that is true for every .
The statement
is false if, for every , there is at least one such that is false.
Example 1.6.9 |
|
The statement is . The domain of discourse is . There is at least one positive integer (namely ) for which is true for every positive integer . Hence, this statement is true. In words, there is a smallest positive integer (namely ). |
Example 1.6.10 |
|
The statement is . The domain of discourse is . For every positive integer , there is at least one positive integer , namely , such that is false. Hence, this statement is false. In words, there is no greatest positive integer. |
The statement
,
with domain of discourse , is true if there is at least one and at least one such that is true.
The statement
is false if, for every , and for every , is false.
Example 1.6.11 |
|
The statement is . The domain of discourse is . There is at least one integer and at least one integer such that . Hence, this statement is true. In words, is composite. |
Example 1.6.12 |
|
The statement is . The domain of discourse is . and
is false. Hence, this statement is false. In words, is prime. |
Example 1.6.13 |
|
Using the generalized De Morgan’s laws for logic, we find that the negative of
is . |
Notice how in the negative, and are interchanged.
Example 1.6.14 |
|
Write the negative of , where the domain of discourse is . |
Solution
Determine the truth value of the given statement and its negation.
Using the generalized De Morgan’s laws for logic, we find that the negative is
.
The given statement is true.
There is at least one (namely ) such that for every .
Since the given statement is true, its negation is false.
HW : Quiz #1 and Quiz #2 or (Exs. 37, 40,42, 45, 48, 51, 54, 57), Q & A
http://matrix.skku.ac.kr/sglee/vita/LeeSG.htm