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%


A+ : 10%

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/ 

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

     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



Copyright by SGLee, SKKU  sglee@skku.edu

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