1.4 – Predicates and Quantifiers
1. Let Q(x) be the statement “x + 1 > 2x.” If the domain a consists of all integers, what are
these truth values?
a. Plug in and see the value
b. ∀xQ(x)= The value is false because for all x+1 is not greater than 2 times x
2. Suppose that the domain of the propositional function P(x) consists of −5, −3,−1, 1, 3,
and 5. Express these statements without using quantifiers, instead using only negations,
disjunctions, and conjunctions.
a. Expressing only using OR and AND
b. Exists are denoted by OR and for all is denoted by AND
c. ∀x((x ≠ 1) → P(x))
i. P(-5) AND P(-3) AND P(-1) AND P(3) AND P(5)
2.1 Sets
Set – Unordered collection of objects called elements or members
• Two sets are equal if they have the same elements. Order doesn’t matter
A is a subset of B denoted by A⊆B
Cardinality of S is the number of elements the set S has, denoted by |S|
The power set of s is the set of all subsets of the set S
1. Set builder notation {0, 3, 6, 9, 12}
2. x∈Z ∨x 3=0 It would be expressed as such
3. If you need to determine whether a number is an element of a set count brackets
carefully
4. What is the cardinality of each of these sets?
a. {∅, {∅}} = COUNT BRACKETS 2.3 – Functions
Function – A and B are nonempty sets. Function f from A to B is an assignment of exactly one
element of B to each element of A.
Function from Z to Z. It takes in Z and returns the next highest prime.
Domain – Set of all numbers that it could take
• Integers
Range – All of the answers
• Set of all primes
Codomain – All of the possible answers
• The integers
Preimage – The value you give to receive a specific answer
• f(15) = 17
• 15 is the preimage of 17
One-to-One (injuction) – There are no two things in A that lead to a B
Onto (surjective) – Everything in A leads to everything in B
Bijective – Both Onto and One-to-One
Nonnegative Integers contain 0 and all positive integers , positive Integers contain all
positive numbers except for 0 1. Determine if it’s a function
a. If you have a function from Z to R and your question doesn’t include the domain
it’s not a function
b. Function can only return one value so f (n) = ± n. is not a function
c. If the function makes you divide by 0 it’s not a function
2. Find the domain and range of these functions
a. the function that assigns to a bit string the number of bits in the string
b. Domain – All bit strings
c. Range – Positive Integers
3. Determine whether each of these functions from Z to Z is one-to-one.
a. Can’t have 2 values give the same results
b. f (n) = n +It’s not one to one because -2 and 2 will give you the same result
4. f(S) means apply everything to the set. I.e plug in the x in the S
5. Find f ○ g and g ○ f , where f (x) = x + 1 and g(x) = x + 2, are functions from R to R
a. This is fog: f(g(x))
2
i. f(x+2) = (x+2) + 1
b. This is gof: g(f(x))
i. g(x +1) = (x +1) + 2
4.1 Divisibility and Modular Arithmetic
Quotient – Denoted by q
• If you divide a by b then you get a quotient plus a remainder
• Quotient can be negative but it has to be an Integer
Remainder – Denoted by r
• Remainder is always greater than or equa

More
Less