Exam 2 Flashcards
A sentence that contains a finite number of variables and becomes a statement when specific values are substituted for the variables
Predicate
The set of all values that may be substituted in place of the variable
Domain
Ex:
{x £ D | P(x)}
Truth set
Symbol inside down A denotes “for all” and is called:
Universal quantifier
A statement of the form “upsidedown Ax £ D, Q(x)”. Defined true if, and only if, Q(x) is true for every x in D.
Universal statement
A value for x for which Q(x) is false is called a _____________ to the universal statement
Counterexample
The technique used to show the truth of the universal statement:
1^2 >= 1, 2^2 >= 2, 3^2 >= 3, 4^2 >= 4
Hence “upside down x £ D, x^2 >= x” is true.
This is called:
method of exhaustion
Consists of showing the truth of the predicate separately for each individual element of the domain.
Method of exhaustion
The symbol E denotes “there exists” and is called the:
Existential quantifier
Is a statement of the form “Ex £ D such that Q(x).” It is defined as true if, and only if, Q(x) is true for at least one x in D.
Existential statement
A reasonable argument can be made that the most important form of statement in mathematics is:
Universal conditional statement
The negation of a universal statement (“all are”) is logically equivalent to an:
Existential statement
Note that’s when we speak of __________________, we mean that the statements always have identical truth values no matter what predicates are substituted for the predicate symbols and no matter what sets are used for the domains of the predicate variables.
Logical equivalence for quantified statements
~(upside down Ax, if P(x) then Q(x)) is logically equivalent Ex such that P(x) and ~Q(x)
Negation of a universal conditional statement
The ____________ of a real number a is a real number b such that ab=1.
Reciprocal
~(upsidedown A x in D, exists y in E such that P(x,y)) is equivalent to (their exists x in D such that inside down Ay in E, ~P(x,y)
Negations of multiply-quantified statements
An integer n is ______ if, and only if, n equals twice some integer.
Symbolically:
Their exists and integer k such that n = 2k
Even
An integer n is ______ if, and only if, n equals twice some integer plus 1.
Symbolically:
Their exists and integer k such that n = 2k + 1
Odd
An integer n is ______ if, and only if, n > 1 and for all positive integers r and s, if n = rs, then either r or a equals n.
Symbolically:
For all positive integers r and a, is n = rs then either r = 1 and s = n or r= n and s= 1
Prime
An integer n is ______ if, and only if, n > 1 and for some integers r and s, with 1
Composite
To show that every element of a set satisfies a certain property, suppose x is a particular but arbitrarily chosen element of the set, and show that x satisfies the property
Method of generalizing from generic particular
If the existence of a certain kind of object is assumed or has been deduced then it can be given a name,as long as that name is not currently being used to denote something else
Existential instantiation
Star the steps to write a proof:
- Copy statement of the theorem to be proved on your paper
- Clearly mark the beginning with “proof”
- Make you’re proof self-contained
- write you’re proof in complete, grammatically correct sentences
- Keep reader informed about status of each statement
- Give reason for each assertion in proof
- Display equations and inequalities
- Include “little words and phrases” that make logic of your arguments clear
Common proof mistakes:
- Arguing from examples
- using the same letter to mean two different things
- Jumping to conclusions
- Circular reasoning
- Confusion between what is known and what is still to be shown
- Use of “any” rather than “some”
- Misuse of the word if
A real number r is __________ if and only if, it can be expressed as a quotient of two integers with a nonzero denominator.
Rational
The word rational contains the word ratio, which is another word for ____________. A rational number can be written as a ratio of integers
Quotient
If neither of the two real numbers is zero, then their product is also not zero
Zero product property
It follows that ________ is a quotient if two integers with a nonzero denominator and hence is a rational number
(m+n)/mn
The notion of do is ability is the central concept of one of the most beautiful subjects in advanced mathematics: ____________, the study of properties of integers
Number theory
If n and d are integers and d != 0 then
n is divisible by d if, and only if n equals d times some integer
Instead of “n is divisible by d” we can say that:
n is a multiple of d
d is a factor of n
d is a divisor of n
d divided n
One of the most useful properties of divisibility is that it is __________. If one number divides a second and the second divides a third, then the first number divides the third.
Transitive
Given any real number x, the _________ of x, denoted [x], is defined as follows:
[x] = that unique integer n such that n <=x
Floor
Given any real number x, the _________ of x, denoted [x], is defined as follows:
[x] = that unique integer n such that n -1 < x <=n
Ceiling
- Suppose the statement to be proved is false. That is, suppose that the negation of the statement is true.
- Show that this supposition leads logically to a contradiction
- Conclude that the statement to be proved is true
Method of proof by contradiction
[PBAC] meaning
Particular but arbitrary chosen
What is the definition along rational numbers?
x = a/b and y = c/d and b != 0 and d != 0
