MTH1020 Flashcards
What is a proof?
Mathematical proofs establish the truth of a statement to an extremely high degree of certainty. Necessarily and logically true.
Counterexample
An example which disproves a statement. Just one set of values that disproves a statement.
□
QED - goes at the end of every proof
How are conditional statements asked?
If….Then…
If P, then Q
A conditional statement asserts that…
If one statement (P) is true, then another statement (Q) is true.
In conditional statements P is…
The hypothesis or assumption
In conditional statements Q is…
The conclusion
If given a conditional statement, prove by:
Direct proof
What is a direct proof?
Assume hypothesis is true, and then show why the conclusion logically follows.
An odd number is…
If something is (odd/even), then something else is (odd/even) type of questions.
- an integer which is not divisible by 2
- i.e. a number of the form 2k + 1 for some integer k
An even number is…
If something is (odd/even), then something else is (odd/even) type of questions.
- an integer divisible by 2
- i.e. a number of the form 2k for some integer k
What is the negation of a statement?
The negation of a statement P is the assertion that P is false. Often abbreviated to ‘not P’
Negating an ‘and’ statement leads to a…
(and vice versa)
e.g. a=0 and b=0
‘or’ statement
e.g. a≠0 or b≠0
‘or’ statements in mathematics - inclusive.
“P or Q” means…
“P is true or Q is true or both”, or equivalently, “at least one of the statements P and Q is true”.
‘exclusive or’ often written as “xor” in mathematics.
“P xor Q” means…
“P is true or Q is true but NOT both”, or equivalently, “exactly one of the statements P and Q is true”.
De Morgan’s Laws:
Not (P and Q) is equivalent to (Not P) or (Not Q)
Not (P or Q) is equivalent to (Not P) and (Not Q)
Proof by Contradiction
suppose the contrary
Steps for doing a proof by contradiction, which proves a statement P as follows:
- Assume statement P is false (assume the negation of P)
- Under this assumption, show that a contradiction or nonsensical statement follows. (most important)
- Conclude that it was wrong to assume that P is false
- Conclude that P is true
If x is positive and rational then…
Then x can be written as a fraction: x = m/n , where m and n are positive integers and n≠0
Prove that something is NOT rational (irrational)
x=m/n
As m,n are both even with the highest common factor 1.
What is the converse of the conditional statement P=>Q?
Q=>P
=> implies (Q implies P)
The converse of the statement “If P then Q” is..
“If Q then P”
What is the contrapositive of the conditional statement P=>Q?
The contrapositive of the statement P=>Q is the statement (Not Q) => (Not P)
A statement is logically equivalent to its…
contrapositive
If the original statement is true, the contrapositive is…
Also true
If the original statement is false, the contrapositive is…
Also false
Proving contrapositive example: If x is irrational, then 2x + 1 is irrational. What is the contrapositive?
(If something, then something - the same e.g. in this case ‘irrational’)
Contrapositive: If 2x + 1 is rational, then x is rational.
Set notation: N=?
Natural numbers
{1, 2, 3, 4…}
Set notation: Z=?
Integers
{…-2, -1, 0, 1, 2, 3…}
Set notation: Q=?
Rational numbers/fractions
{a/b : a,b ∈ Z and b≠0}
Set notation: R=?
Real numbers
(number line)
Set notation: C=?
Complex numbers
(watch this space)
Equivalent Statements - Two statements P and Q are (logically) equivalent if…
Both P => Q
And Q => P are true
P => Q and Q => P is often abbreviated to…
P <=> Q
When P an Q are equivalent statements…
P is true precisely when Q is true
For equivalent statements, P is true if and only if…
Q is true
iff
if and only if
To prove P and Q are equivalent you need to…
Prove 2 things:
P => Q
Q => P
Divisibility definition: let m and n be integers
When there exists an integer k such that m=kn, we say that m is divisible by n. OR m is the multiple of n. OR n is a divisor or factor of m.
Define a prime number
A positive integer whose only positive divisors are 1 and itself
Define a composite
A positive integer which has a positive divisor other than 1 and itself
An integer is even when…
it is divisible by 2
“For all”
A (upside down) - change these to pictures?
“There exists”
E (backwards)
A (upside down)
“For all”
E (backwards)
“There exists”
A “for all” or universal statement claims that…
a certain property holds for all elements of the set
A “there exists” or existence statement claims…
a certain property holds for at least one element of a set
Statements involving “for all” or “there exists” are…
quantified - they claim a certain “quantified” number of elements of a set have a certain property.
The phrases “for all” and “there exists” are..
quantifiers
To prove a universal statement you need to explain…
why every element of a set has the claimed property.
To disprove a universal statement…
you only need to find one counterexample
