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

https://www.pearson.com/us/higher-education/program/Johnsonbaugh-Discrete-Mathematics-7th-Edition/PGM44460.html

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% 

 

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/ 

http://dimacs.rutgers.edu/  

Weekly Schedule (Tentative)

http://math.newark.rutgers.edu/~bl498/teaching/237Fall2017/ 

Week	Section covered	Remarks
1	Orientation
2	1 Sets and Logic (HW1)	Quiz #1 ,  Quiz #1 Solutions Quiz #2 ,  Quiz #2 Solutions
3	2 Proofs	Skipped section: 2.3 Quiz #3 ,  Quiz #3 Solutions Quiz #4 ,  Quiz #4 Solutions
4	3 Functions, Sequences (Quiz1)
5	3 Relations	Skipped section: 3.6 EXAM #1 , EXAM #1 Solutions Quiz #5 ,  Quiz #5 Solutions
6	4 Algorithms (HW2)	Quiz #6 ,  Quiz #6 Solutions EXAM #2 , EXAM #2 Solutions
7	5 Number Theory  (if time permits)	Skipped section: 5.4 Quiz #9 ,  Quiz #9 Solutions
8	Midterm Exam	Sample Exams
9	6 Counting Methods  (HW3)
10	6 the Pigeonhole Principle  (lightly covered)	Skipped sections: 6.4, 6.5, 6.6 Quiz #7 ,   Quiz #7 Solutions Quiz #8 ,  Quiz #8 Solutions
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	Sample Exams

 [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   (    )

Quiz #1 ,  Quiz #1 Solutions

Quiz #2 ,  Quiz #2 Solutions

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 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 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

We first evaluate

 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: Truth table    Truth table

 

 is true and  is false       is false.

Otherwise       is true.

 

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

Copyright by SGLee, SKKU  sglee@skku.edu

http://matrix.skku.ac.kr/sglee/vita/LeeSG.htm