Discrete Mathematics and Linear Algebra.
A sequence of propositions aimed at demonstrating the truth of a claim, known as the conclusion.
The conclusion (what is claimed) and the premises (the preceding propositions that support the conclusion).
If all premises are true, then the conclusion must also be true for all possible cases.
A valid argument that shows the truth of a mathematical statement from definitions, axioms, and other theorems.
It validly shows why the mathematical statement being proved is true.
Universal conditionals.
By showing that its negation is true.
m can be written as 2k for some integer k.
Proof by Contraposition and Proof by Contradiction.
If a | b and b | c, then a | c for all integers a, b, and c.
Indirect proofs do not start with antecedences but use alternative methods to reach conclusions.
Then n is also even (by Theorem 4.5).
As a universal conditional statement by expanding set C to a larger set D and adding P(x).
Prove p → r (case 1).
For all integers m and n, if m and n are even, then m + n is even.
The sum is even.
An integer n is even if, and only if, n equals twice some integer.
To show that if P is true, then Q is also true.
It means n must be odd.
Because it contains an infinite number of elements.
Quod Erat Demonstrandum.
∃ x ∈ D such that P(x) and Q(x).
It marks the end of a mathematical proof.
Using definitions, axioms, and other theorems.
Finding an even integer n that is the sum of two odd numbers.
Yes, 54 = 6(9).
It cannot be used if the concerned set is not finite and there are infinite elements that can make P(x) true.
Yes, 21 = 3(7).
The supposition that m and n have no common factors is false.
To perform deductions until reaching the conclusion.
To find an x in D that makes Q(x) true.
To show that its negation is true.
To establish the truth of mathematical statements.
a = 1 and b = -1, where a^2 = b^2 but a ≠ b.
A contradiction (i.e., p ∧ ~p).
d | n ⇔ ∃ an integer k such that n = d * k.
(m is even) or (m is odd).
An existential statement ∃ x ∈ D such that Q(x) is true if and only if Q(x) is true for at least one x in D.
The sum of any two rational numbers is rational.
It means 'd divides n'.
Yes, because it can be expressed as 281 / 1000.
p → q ≡ ~q → ~p.
It is assumed that √2 is rational.
The meanings of all terms in the proposition.
If a divides b and b divides c, then a divides c.
m² + m + 1 = 2p² + 2p + 1 = 2(2p² + p) + 1.
P(x) → ~Q(x).
Yes, different methods can be used for different cases.
-1, 0, and 1.
n is odd ⇔ ∃ an integer k such that n = 2k + 1.
Constructive proofs of existence.
A real number r is rational iff there exist integers a and b such that r = a / b and b ≠ 0.
A real number that is not rational, such as π or √2.
The logical equivalence between an implication and its contrapositive.
There is no greatest integer.
A method where one assumes the negation of the statement to be proven and shows that this leads to a contradiction.
3, 5, and 7 are all odd numbers.
The statement to be proved is true.
If m is odd, then m² + m + 1 is odd.
p ∧ ~p.
Show ~p is true.
p ∨ q ⟶ r.
Q represents 'm + n is even.'
It shows that no greatest integer can exist.
n is even ⇔ ∃ an integer k such that n = 2k.
0.
Definitions, Axioms, and Other theorems.
Direct proof.
2.
When D is finite or has only finite elements that can make P(x) true.
Suppose the statement to be proved is false (i.e., the negation of the statement is true).
If n and d are integers and d ≠ 0, then n is divisible by d if n equals d times some integer.
N is a greatest integer and N is not a greatest integer.
The number of elements in that set is limited.
For all real numbers a and b, a + b = b + a.
Prove q → r (case 2).
Yes, because 0 = 2 · 0.
It implies that all elements in set C satisfy the condition Q(x).
An integer n is odd if, and only if, n equals twice some integer plus 1.
p = ad + bc and q = bd.
Proof by contradiction.
It allows for the use of the method of exhaustion in the proof.
If m² is even, then m is even.
There exist a, b in R such that a^2 = b^2 and a ≠ b.
d is a factor of n, d is a divisor of n, or n is a multiple of d.
They serve as premises or a starting point for proofs.
The double of a rational number is a rational number.
a = 1 and b = -1.
m² = 2n².
m = 2r and n = 2s for some integers r and s.
(m is even) ∨ (m is odd) ⟶ m² + m + 1 is odd.
M is greater than N.
It indicates that m² + m + 1 is odd.
b ≠ 0 and d ≠ 0.
If ab = c, then a ≤ c or b ≤ c.
n = 2k + 1 for some integer k.
∀x ∈ D, if P(x) then Q(x).
Yes, 42 = 7(6).
As laws that require no proof.
Assume r and s are rational numbers.
Theorem 4.7 states that √2 is an irrational number.
A statement of the form ∀ SFU students x, x is a smart guy.
∀ m ∊ N, m² + m + 1 is odd.
By showing that 2r = r + r is a sum of two rational numbers, thus rational.
Suppose there is a greatest integer N.
It means all SFU students are smart guys.
m² + m + 1 is odd.
∀ x ∈ D, if P(x) then Q(x).
∀ m ∈ N, m² + m + 1 is odd.
Quod Erat Demonstrandum, meaning 'which was to be demonstrated.'
That the sum of any two odd integers is even.
If n is not even, then n² is not even.
Proving the contrapositive proves the original theorem.
n = 10, which can be expressed as 10 = 5 + 5 and 10 = 3 + 7.
For all x in D, if P(x) then Q(x).
It signifies that the proof is complete and the theorem is true.
It shows that the universal conditional statement is false.
m = 6 and n = 4.
(p ∨ q) ⟶ r.
A proof that demonstrates the existence of a mathematical object by providing a method to construct it.
It gives 3² = m/n.
An integer M can be found that is greater than N.
Because it is the sum of two integers r and s.
Because products and sums of integers are integers.
A mathematical statement that has been proved to be true.
Antecedences.
For all real numbers r and s, if r and s are rational, then r + s is rational.
∃x ∈ D such that P(x) ∧ ~Q(x).
A proof that assumes the opposite of what is to be proven and derives a contradiction.
Checking each case to see if it can make the conditional true.
By showing that its negation is true.
The original statement must also be true.
∀ x ∈ D, ~(P(x) and Q(x)).
Conclude that p → q.
A rational number can be expressed as r = a / b, where a and b are integers and b ≠ 0.
For all n ∈ Z, if -1 ≤ n ≤ 1, then n³ = n.
n² is odd.
Yes, 40 = 5(8).
A statement that we assume to be true.
A statement is either true or false, but not both.
A statement whose truth can be immediately deduced from a previously proved theorem.
You get n² = 2k², indicating n² is even.
To show that r + s is rational when r and s are rational.
For all real numbers a and b, a + b is a real number.
An integer that can be expressed as m = 2r for some integer r.
The sum of any two even integers is even.
Theorem 4.2.
The assumption must be false.
It signifies that the proof is complete.
6/4 = 3/2.
Yes, for example (p ∨ q ∨ s) ⟶ r.
It represents an odd number.
Because b ≠ 0 and d ≠ 0.
1.
Assume P(x) is true.
There is no greatest integer.
Show that Q(x) is also true by using the assumption from Step 1, definitions, axioms, and previously established results.
It means that m/n is in lowest terms.
∀x ∈ D, if P(x) then Q(x).
M = N + 1.
~(P(x) ∧ Q(x)) ≡ ~P(x) ∨ ~Q(x).
Yes, because -301 = 2(–151) + 1.
Assume that m and n are even integers.
n is odd ⇔ ∃ an integer k such that n = 2k + 1.
n is even ⇔ ∃ an integer k such that n = 2k.
n² = 2p + 1, where p = 2k² + 2k, showing n² is odd.
Yes, because it can be expressed as 7 / 1.
An integer a divides an integer b if there exists an integer k such that b = ak.
It signifies that the proof is complete.
Assume ~q is true.
A statement that explains the meaning of a term or statement.
k is an integer defined as the product of integers r and s.
P represents 'm and n are even.'
An integer n is even if, and only if, n equals twice some integer.
N = {0, 1, 2, 3, ...}.
If n² is even, then n is even.
r + s is rational by definition of a rational number.
∀ x ∈ D, if P(x) then ~Q(x).
m + n = 2r + 2s = 2(r + s) = 2t, where t is an integer.
Thus, a divides c by definition of divisibility.
m² + m + 1 = 2l + 1, where l = 2q² + 3q + 1.
An integer n is odd if, and only if, n equals twice some integer plus 1.
Method of exhaustion.
-1.
Quod Erat Demonstrandum, meaning 'which was to be demonstrated'.
