Speaking Mathematically: Discrete Structures I

Speaking Mathematically
Winter 2013 COMP 1380 Discrete Structures I Computing Science Thompson Rivers University
Course Outline

Speaking Mathematically Number Systems Computer Arithmetic Logic and Truth Tables Boolean Algebra and Logic Gates Vectors and Matrices Sets and Counting Probability Theory and Distributions Statistics and Random Variables
TRU-COMP1380
Unit Objectives

Introduce variables for a given sentence. Use of the symbols, , , , in mathematical sentences. Tell if a given list of something is a set. Give the Cartesian product of two sets. Tell if a given relation is a function.
TRU-COMP1380
Unit Contents
1. 2. 3.
Variables The Language of Sets The Language of Ralations and Functions
TRU-COMP1380
1. Variables
Definition of a variable
Something that can have a value but you do not know what the value is. Example 1
How to introduce variables for a given sentence?
Is there a number with the following property: doubling it and adding 3 gives the same result as squaring it? -> Is there a number x with the following property: 2 x + 3 = x2? No matter what number might be chosen, if it is greater than 2, then its square is greater than 4. -> ???
Example 2
Example 3
Are there two numbers with the property that the sum of their squares equals the square of their sum?
Given any real number, its square is nonnegative.
Speaking Mathematically 5
Example 4
TRU-COMP1380
Some Important Kinds of Math Statements
Conditional statement
If ..., then ... For all [] ..., if ..., then ... For all [] ..., there is [] ... E.g., Every real number has an additive inverse.
-> For all real number r, there is an additive inverse for r. -> real number r, -r r + (-r) = 0.
Universal conditional statement
Universal existential statement

Existential universal statement
There is [] ... such that [] ... E.g., Some positive integer is less than or equal to every positive integer.
-> There is a positive integer such that the number is less than or equal to every positive integer. -> a positive integer m positive integer n, m n
TRU-COMP1380
2. The Language of Sets
Definition of a set: A collection of elements of the same type
Interesting examples
Let A = {1, 2, 3}, B = {3, 1, 2} and C = {1, 1, 2, 3, 3, 3}. How are A, B, and C related? Is {0} = 0? Is {1, {1}} a set? Is {1, a, b} a set? For each nonnegative integer n, let Un = {n, -n}. Find U1, U2, and U0. {x S | P(x)} meaning ??? the set of elements in S that satisfy P. E.g.,

An interesting notation
{x Z | -2 < x < 5} = { ??? } {x N | -2 < x < 5} = { ??? }

TRU-COMP1380
Subsets

AB AB
means x A, x B means ??? (x A, x B) and ( y B y A)
Interesting example Which of the following are true statements?

a) b) c) d)
e)
f) g)
2 {1, 2, 3} {2} {1, 2, 3} 2 {1, 2, 3} {2} {1, 2, 3} {3, 1, 2} {1, 2, 3} {2} {{1}, {2}} {2} {{1}, {2}}
TRU-COMP1380
Definition of Cartesian product of A and B: A B = {(a, b) | a A and b B} Is A B equal to B A? Examples Let A = {1, 2, 3} and B = {1, 2}
a) b) c)
Find A B Find B A Find B B
TRU-COMP1380
3. The Language of Relations and Functions
Definition of a relation: Let A and B are sets. A relation (or also called mapping) R from A to B is a subset of A B. A is called the domain of R and B is called its co-domain. Example Let A = {1, 2} and B = {1, 2, 3} and define a relation R from A to B as follows: Given any (x, y) A B, x R y means that (x y) / 2 is an integer.
a) b) c)
Can you give a diagram for R? Is 1 R 3? Is 2 R 3? Is 2 R 2? What are the domain and co-domain of R?
TRU-COMP1380
10
1. 2.
Definition of a function: A funcfion F from a set A to a set B is a relation with domain A and co-domain B that satisfies the following two properties: x A, y B x F y another popular notation F(x) = y x A and y and z B, x F y and x F z -> y = z (What does this mean?) {y B | x F y for some x A} is called the image of F, denoted by F(A). Example Let A = {2, 4, 6} and B = { 1, 3, 5}. Which of the relations R, S and T defined below are functions from A to B?
a)
b) c)
R = {(2, 5}), (4, 1), (4, 3), (6, 5)} (x, y) A B, (x, y) S means that y = x + 1. 2 T 5, 4 T 1, 6 T 1 (i.e., T(2) = 5; T(4) = 1; T(6) = 1)
TRU-COMP1380
A) F(1) = A; F(2) = B; F(3) = D 1 2 3 A B C D
D) 1 2 3 E) A B C D A B C D
B)
1 2 3
A B C D F)
1 2 3
C) 1 2 3 A B C D
1 2 3
A B C D
12
TRU-COMP1380

Speaking Mathematically: Discrete Structures I

Uploaded by

Copyright:

Available Formats

Speaking Mathematically: Discrete Structures I

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Speaking Mathematically: Discrete Structures I

Uploaded by

Copyright:

Available Formats

Speaking Mathematically

Variables The Language of Sets The Language of Ralations and Functions

How to introduce variables for a given sentence?

Some Important Kinds of Math Statements

Universal conditional statement

Universal existential statement

Existential universal statement

2. The Language of Sets

Definition of a set: A collection of elements of the same type

{x Z | -2 < x < 5} = { ??? } {x N | -2 < x < 5} = { ??? }

means x A, x B means ??? (x A, x B) and ( y B y A)

Interesting example Which of the following are true statements?

Find A B Find B A Find B B

3. The Language of Relations and Functions

A) F(1) = A; F(2) = B; F(3) = D 1 2 3 A B C D

You might also like