The foundations: logic and proof Flashcards
1
Q
Atomic proposition
A
Propositions that cannot be expressed in terms of simpler propositions
2
Q
compound propositions
A
compound propositions are formed
from existing propositions using logical operators.
3
Q
Conditional, contrapositive, inverse, converse.
A
Conditional and Contrapositive are equivalent.
converse and inverse are equivalent ( as the inverse is converse’s contrapositive)
4
Q
Some forms of saying if p then q?
14
A
- “if p, then q” 3. “p implies q”
- “if p, q” 4. “p only if q”
- “p is sufficient for q”
- “a sufficient condition for q is p”
- “q IF p”
- “q WHENEVER p”
- “q WHEN p”
- “q is NECESSARY for p”
- “a necessary condition for p is q”
- “q FOLLOWS from p”
- “q UNLESS ¬p”
- “q PROVIDED that p”
5
Q
Some ways of saying p if and only if q ( bi implication)?
4
A
“p is necessary and sufficient for q”
“if p then q, and conversely”
“p iff q.” “p exactly when q.”
6
Q
Precedence.
A
It is generally the case that unary operators that involve only one object precede binary operators.
7
Q
z whenever o is
A
if o then z; o –> z
8
Q
a is sufficient for v
A
a–>v ; if a then v
9
Q
f is necessary for g
A
if g then f; g –> f
10
Q
Application of propositional logic.
A
- System specifications
- Boolean search
- logic puzzle
- logic circuits
11
Q
System specifications
A
System specifications
should be consistent, that is, they should not contain conflicting requirements that could be used to derive a contradiction.
When specifications are not consistent,
there would be no way to develop a system that satisfies all specifications
12
Q
Boolean Searches:
A
In Boolean searches, the connective AND is used to match records that contain both of
two search terms, the connective OR is used to match one or both of two search terms, and the
connective NOT (sometimes written as AND NOT ) is used to exclude a particular search term.
Careful planning of how logical connectives are used is often required when Boolean searches
are used to locate information of potential interest.
13
Q
logically equivalent
A
The compound propositions p and q are called logically equivalent if p ↔ q is a tautology.
The notation p ≡ q denotes that p and q are logically equivalent.
≡ : not a logical connective.
p ≡ q: not a compound proposition but a statement meaning ‘p ↔ q is a tautology’.
14
Q
conditional disjunction equivalence.
A
p → q ≡ ¬p ∨ q
15
Q
Logical Equivalences
Involving Conditional
Statements. 2 variables. (5)
A
p → q ≡ ¬p ∨ q p → q ≡ ¬q → ¬p p ∨ q ≡ ¬p → q p ∧ q ≡ ¬(p → ¬q) ¬(p → q) ≡ p ∧ ¬q
16
Q
Logical Equivalences
Involving Conditional
Statements. 3 variables. (4)
A
(p → q) ∧ (p → r) ≡ p → (q ∧ r)
(p → r) ∧ (q → r) ≡ (p ∨ q) → r
(p → q) ∨ (p → r) ≡ p → (q ∨ r)
(p → r) ∨ (q → r) ≡ (p ∧ q) → r
17
Q
Logical
Equivalences Involving
Biconditional Statements (4)
A
p ↔ q ≡ (p → q) ∧ (q → p)
p ↔ q ≡ ¬p ↔ ¬q
p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
¬(p↔ q) ≡ p ↔ ¬q
18
Q
De Morgan’s law extended:
A
Furthermore, note that De Morgan’s laws extend to
¬(p1 ∨ p2 ∨ ⋯ ∨ pn) ≡ (¬p1 ∧ ¬p2 ∧ ⋯ ∧ ¬pn)
and
¬(p1 ∧ p2 ∧ ⋯ ∧ pn) ≡ (¬p1 ∨ ¬p2 ∨ ⋯ ∨ ¬pn)
19
Q
When using De
Morgan’s laws,
remember to
A
change
the logical connective
after you negate.
20
Q
Satisfiability :
A
A compound proposition is satisfiable if there is an assignment of truth values to its variables
that makes it true (i.e, when it is a tautology or a contingency).
21
Q
unsatisfiable:
A
when the compound proposition is false for all assignments of truth values to
its variables.
Note that a compound proposition is
unsatisfiable if and only if its negation is true for all assignments of truth values to the variables,
i.e, if and only if its negation is a tautology.
22
Q
The solution to a satisfiable problem:
A
When we find a particular assignment of truth values that makes a compound proposition
true, we have shown that it is satisfiable; such an assignment is called a solution to this particular
satisfiability problem.
23
Q
Predicate
A
predicate,
ex: “is greater than 3”
—refers to a property that
the subject of the statement can have
24
Q
P(x), what do you understand from this?
A
The statement P(x) is also
said to be the value of the propositional function P at x. Once a value has been assigned to the
variable x, the statement P(x) becomes a proposition and has a truth value.
“x = y + 3.” denoted by Q(x, y), where x and y are variables, and Q is the predicate. When values are assigned to the variables x and y, the statement Q(x, y) has a truth value.
25
Propositional functions
In general, a statement involving the n variables x1, x2, … , xn can be denoted by
P(x1, x2, … , xn).
A statement of the form P(x1, x2, … , xn) is the value of the propositional function P at the
n-tuple (x1, x2, … , xn), and P is also called an n-place predicate or an n-ary predicate.
Propositional functions occur in computer programs like
if x > 0 then x := x + 1
26
Preconditions and Postconditions
The statements that describe valid
input are known as preconditions and the conditions that the output should satisfy when the
program has run are known as postconditions.
27
Predicate Calculus
The area of logic that deals with predicates
| and quantifiers is called the predicate calculus.
28
Quantification
Quantification expresses
| the extent to which a predicate is true over a range of elements.
29
Domain
domain
| specifies the possible values of the variable x for P(x).
30
The universal quantification of P(x) is the statement:
The universal quantification of P(x) is the statement
“P(x) for all values of x in the domain.”
The notation ∀xP(x) denotes the universal quantification of P(x). Here ∀ is called the
universal quantifier. We read ∀xP(x) as “for all xP(x)” or “for every xP(x).”
31
Counter Example:
An element for
which P(x) is false is called a counterexample to ∀xP(x).
32
The domain of Discourse:
Many mathematical statements assert that a property is Assessment true for all values of a variable in a particular domain, called the domain of discourse (or the universe of discourse), often just referred to as the domain
33
universal quantification can be expressed in many other
1. “for all”
2. “for every,”
3. “all of,”
4. “for each,”
5. “given any,”
6. “for arbitrary,”
7. “for each,”
8. “for any.” -- avoid use, 'any' is ambiguous unless its negatives we talking bout.
34
The existential quantification of P(x) is the proposition
The existential quantification of P(x) is the proposition
“There exists an element x in the domain such that P(x).”
We use the notation ∃xP(x) for the existential quantification of P(x). Here ∃ is called the
existential quantifier.
35
express existential quantification:
| ∃xP(x)
1. “there exists,”
2. “for some,”
3. “for at least one,”
4. “there is.”
5. “There is an x such that P(x),”
6. “There is at least one x such that P(x),”
7. “For some xP(x).”
36
Uniqueness Quantifier
denoted by ∃! or ∃1.
The notation ∃!xP(x) [or ∃1xP(x)] states
1. “There exists a unique x such that P(x) is true.”
2.“there is exactly one”
3.“there is one and only one.”
37
the universal quantification ∀xP(x) is the
| same as?
the universal quantification ∀xP(x) is the same as the conjunction
P(x1) ∧ P(x2) ∧ ⋯ ∧ P(xn),
because this conjunction is true if and only if P(x1), P(x2), … , P(xn) are all true.
[ when the elements of the
domain are x1, x2, …, xn, where n is a positive integer ]
38
existential quantification ∃xP(x) is the same as?
existential quantification ∃xP(x) is the same as the disjunction
P(x1) ∨ P(x2) ∨ ⋯ ∨ P(xn),
because this disjunction is true if and only if at least one of P(x1), P(x2), … , P(xn) is true.
[ when the elements of the
domain are x1, x2, …, xn, where n is a positive integer ]
39
CONNECTIONS BETWEEN QUANTIFICATION AND LOOPING?
We can loop through the domain elements to check the truth value of quantifiers. For universal quantifier, if there is no element for which the p(x) is false then its true. For existential quantifier if there is an element for which P(x) is true then it's true and if no element satisfies then its false.
40
restriction of a universal quantification
Note that the restriction of universal quantification is the same as the universal quantification of a conditional statement. For instance, ∀x < 0 (x raise to 2 > 0) is another way of expressing
∀x(x < 0 → x raise to 2 > 0).
41
restriction of an existential quantification
The restriction of an existential quantification is the
same as the existential quantification of conjunction. For instance, ∃z > 0 (z raise to 2 = 2) is another
way of expressing ∃z(z > 0 ∧ z raise to 2 = 2).
42
Precedence Of quantifiers:
Universal and existential quantifiers come before logical operators.
∀xP(x) ∨ Q(x) is (∀xP(x)) ∨ Q(x) not ∀x(P(x) ∨ Q(x)).
43
When is a variable bound and when is it free?
When a quantifier is used on the variable x, we say that this occurrence of the variable is bound otherwise it is free.
44
Scope of quantifier?
Variable outside this scope is?
Usage of same letters as variables:
The part of a logical expression to which a quantifier is applied is called the scope of this
quantifier.
Consequently, a variable is free if it is outside the scope of all quantifiers in the formula that specify this variable.
So, the same letter is often used to represent variables bound by different quantifiers with scopes that do not
overlap.
45
Negation of quantified expression:
¬∀xP(x) ≡ ∃x ¬P(x)
| ¬∃xP(x) ≡ ∀x¬P(x)
46
Fuzzy logic
0 : False
1 : True
Fuzzy logic is used in artificial intelligence. In fuzzy logic, a proposition has a truth value that is a number between 0 and 1, inclusive
Truth values that are between 0 and 1 indicate varying degrees of truth.
47
Order of nested Quantifier:
The order doesn't matter if its just universal quantifier or just existential. When using different quantifiers matters.
48
Negation in fuzzy logic.
The truth value of the negation of a proposition in fuzzy logic is 1 minus the truth value of the proposition
49
Conjunction in fuzzy logic.
The truth value of the conjunction of two propositions in fuzzy logic is the minimum of the truth values of the two propositions.
50
Disjunction in fuzzy logic.
Maximum one.
51
Dual of a proposition
The dual of a compound proposition that contains only the logical operators ∨, ∧, and ¬ is the compound proposition obtained by replacing each ∨ by ∧, each ∧ by ∨, each T by F, and each F by T. The dual of s is denoted by s∗.
52
Disjunctive Normal
Suppose that a truth table in n propositional variables is specified. Show that a compound proposition with this truth table can be formed by taking the disjunction of conjunctions of the variables or their negations, with one conjunction included for each combination of values for which the compound proposition is true. The resulting compound proposition is said to be in disjunctive normal form.
53
functionally complete
A collection of logical operators is called functionally complete if every compound proposition is logically equivalent
to a compound proposition involving only these logical operators.
54
NAND
```
logical operators NAND.
The proposition p NAND q is true when either p or q, or both, are false; and it is false when both p and q are true.
p ∣ q
¬(p ^ q)
| aka Sheffer stroke.
[ H. M. Sheffer ]
```
55
NOR
The proposition p NOR q is true when both
p and q are false, and it is false otherwise.
p ↓ q
¬(p ∨ q)
↓ aka Peirce arrow [ C. S. Peirce ]
56
represent ↓ and negations relation
p ↓ p = ¬p
57
represent or using only nor
(p ↓ q) ↓ (p ↓ q ) = p v q
58
Null quantification:
establish rules for null quantification that
we can use when a quantified variable does not appear in part of a statement.
a) (∀xP(x)) ∨ A ≡ ∀x(P(x) ∨ A)
b) (∃xP(x)) ∨ A ≡ ∃x(P(x) ∨ A)
a) (∀xP(x)) ∧ A ≡ ∀x(P(x) ∧ A)
b) (∃xP(x)) ∧ A ≡ ∃x(P(x) ∧ A)
a) ∀x(A → P(x)) ≡ A → ∀xP(x)
b) ∃x(A → P(x)) ≡ A → ∃xP(x)
a) ∀x(P(x) → A) ≡ ∃xP(x) → A
b) ∃x(P(x) → A) ≡ ∀xP(x) → A
59
To say that there are exactly two objects that meet some condition:
we must have two existentially quantified
variables to represent the two objects, we must say that they are different, and then we must say that an
object meets the conditions if and only if it is one of those two.
60
Vacuousness
For any universe of discourse that is empty, then for any predicate,
∃xP(x)
is always false, and
∀xP(x)
is always true. The second is always vacuously true (P(x) holds for
every x in the universe of discourse because there is no such x).
61
prenex normal form (PNF)
A statement is in prenex normal form (PNF) if and only if
it is of the form
Q1x1Q2x2 ⋯ QkxkP(x1, x2,… , xk),
where each Qi
, i = 1, 2, … , k, is either the existential quantifier or the universal quantifier, and P(x1,… , xk) is a predicate
involving no quantifiers. For example, ∃x∀y(P(x, y) ∧ Q(y)) is
in prenex normal form, whereas ∃xP(x) ∨ ∀xQ(x) is not (because the quantifiers do not all occur first).
62
Argument definition from the introduction part:
The argument, we mean a sequence of statements
that end with a conclusion.
- It is a sequence of
propositions.
63
Valid:
By valid, we mean that the conclusion, or final statement of the argument, must follow from the truth of the preceding statements, or premises, of the argument.
That is, an argument is valid if and only if it is impossible for all the premises to be true and
the conclusion to be false
64
rules of inference are used for?
To deduce new statements from statements we already have, we use
rules of inference which are templates for constructing valid arguments.
Rules of inference are
our basic tools for establishing the truth of statements.
65
fallacies?
some common forms of incorrect reasoning, called fallacies, which lead to invalid
arguments.
66
Premises:
All statements in the argument other than the final one, the conclusion.
67
Argument Formal definition:
what are its parts?
When is it valid?
An argument in propositional logic is a sequence of propositions. All but the final proposition
in the argument are called premises and the final proposition is called the conclusion. An
argument is valid if the truth of all its premises implies that the conclusion is true
68
Argument form?
An argument form in propositional logic is a sequence of compound propositions involving propositional variables. An argument form is valid if no matter which particular
propositions are substituted for the propositional variables in its premises, the conclusion is
true if the premises are all true.
69
A proposition which explains validity of argument form:
From the definition of a valid argument form, we see that the argument form with
premises p1, p2, … , pn and conclusion q is valid exactly when (p1 ∧ p2 ∧ ⋯ ∧ pn) → q is a
tautology.
70
Modus ponens
| Latin for mode that affirms.
```
The tautology (p ∧ (p → q)) → q is the basis of the rule of inference called modus ponens,
or the law of detachment.
```
71
Modus tollens:
Mode that denies
[also modus tollendo tollens (Latin for "mode that by denying denies") ]
(¬q ∧ (p → q)) → ¬p
¬q
p → q
----------
∴ ¬p
72
Hypothetical syllogism
((p → q) ∧ (q → r)) → (p → r)
73
Disjunctive syllogism
((p ∨ q) ∧ ¬p) → q
74
Addition
p → (p ∨ q)
75
Simplification
(p ∧ q) → p
76
Conjunction
((p) ∧ (q)) → (p ∧ q)
77
Resolution
| what is resolvent
((p ∨ q) ∧ (¬p ∨ r)) → (q ∨ r)
resolvent: (q ∨ r)
78
Contrapositive:
((p → q) → (¬q → ¬p)
79
Rules OF Inference:
| name them
1. Modos Ponens
2. Modos Tollens
3. Hypothetical Syllogism
4. Disjunctive Syllogism
5. Addition
6. Simplification
7. Conjunction
8. Resolution
also can use contrapositive.
80
Clause
To construct proofs in propositional
logic using the resolution as the only rule of inference, the hypotheses and the conclusion must be
expressed as clauses, where a clause is a disjunction of variables or negations of these variables
81
Common fallacies arise due... can u think of one?
Several common fallacies arise in incorrect arguments. These fallacies resemble rules of inference but are based on contingencies rather than tautologies.
82
The fallacy of affirming the
| conclusion
Considering (p → q), q as premise and p as the conclusion.
It's not a valid argument.
((p → q) ∧ q) → p) : is not a tautology.
83
The fallacy of denying the hypothesis
Using this as a tautology ((p → q) ∧ ¬p) → ¬q), which is not. False when p is false and q is true.
84
Universal Instantiation:
∀xP(x)
-------------
∴ P(c)
85
Universal Generalization:
P(c) for an arbitrary c
---------------------------------
∴ ∀xP(x)
86
Existential Instantiation:
∃xP(x)
---------------------------------------
∴ P(c) for some element c
87
Existential generalisation:
P(c) for some element c
----------------------------------------
∴ ∃xP(x)
88
Error arised frequently by use of universal generalisation?
The error of adding unwarranted assumptions about
the arbitrary element c when universal generalization is used is all too common in incorrect
reasoning
89
Rules of Inference for Quantified Statements.
Universal instantiation
Universal generalization
Existential instantiation
Existential generalization
90
universal modus ponens
This rule tells us that if ∀x(P(x) → Q(x)) is true, and if P(a) is true
for a particular element a in the domain of the universal quantifier, then Q(a) must also be true.
To see this, note that by universal instantiation, P(a) → Q(a) is true. Then, by modus ponens,
Q(a) must also be true. We can describe universal modus ponens as follows:
∀x(P(x) → Q(x))
P(a), where a is a particular element in the domain
----------------------------------------------------------------------------
∴ Q(a)
91
universal modus tollens
∀x(P(x) → Q(x))
¬Q(a), where a is a particular element in the domain
-------------------------------------------------------------------------------
∴ ¬P(a)
92
Argument form
premises p1 , p2 , p3 ,....., pn and q are true
then r is conclusion.
If this is a valid form, then what can u say about an argument form with premises p1 to pn, what will be its conclusion:
If the argument form with
premises p1, p2,… , pn, q, and conclusion r is valid,
the argument form with premises p1, p2,… , pn
and conclusion q → r is valid
If q is false, then we are done, vacuously. Otherwise, q is true, so
by the validity of the given argument form, we know that r is true.
93
Universal Transitivity
```
∀x(P(x) → Q(x))
∀x(Q(x) → R(x))
--------------------------
∴∀x(P(x) → R(x))
[where the domains of all
quantifiers are the same]
```
94
Proof:
A proof is a valid argument that establishes the truth of a mathematical statement.
95
Theorem:
A statement that can be shown to be true, less important theorems are called propositions.
Aka facts or results.
A theorem may be the universal quantification of a conditional statement with one or more premises(can be previously proven theorems) and a conclusion.
96
Axioms or Postulates:
The statements
| used in a proof can include axioms (or postulates), which are statements we assume to be true.
97
Lemma
A less important theorem that is helpful in the proof of other results is called a lemma
(plural lemmas or lemmata)
98
Corollary
A corollary is a theorem that can be established directly from a theorem that has been proved.
99
Conjecture
A conjecture is
a statement that is being proposed to be a true statement, usually on the basis of some partial
evidence, a heuristic argument, or the intuition of an expert. When a proof of a conjecture is
found, the conjecture becomes a theorem. Many times conjectures are shown to be false, so they
are not theorems.
100
Parity?
The integer n is even if there exists an integer k such that n = 2k, and n is odd if there exists an
integer k such that n = 2k + 1. (Note that every integer is either even or odd, and no integer
is both even and odd.) Two integers have the same parity when both are even or both are odd;
they have opposite parity when one is even and the other is odd.
101
Proof consists of what and approach?
Once we have chosen a proof method,
Assessment
we use axioms, definitions of terms, previously proved results, and rules of inference to complete the proof
102
Direct Proof:
A direct proof of a conditional statement p → q is constructed when the first step is the assumption that p is true; subsequent steps are constructed using rules of inference, with the final
step showing that q must also be true.
A direct proof shows that a conditional statement p → q
is true by showing that if p is true, then q must also be true, so that the combination p true and
q false never occurs.
----------------------------------------------------------------------
In a direct proof, we assume that p is true and use axioms, definitions, and
previously proven theorems, together with rules of inference, to show that q must also be true.
-----------------------------------------------------------------------
Direct proofs lead from the premises of a theorem to the conclusion.
103
To prove a theorem of the form ∀x(P(x) → Q(x)):
To prove a theorem of the form ∀x(P(x) → Q(x)), our goal is to show that P(c) → Q(c) is
true, where c is an arbitrary element of the domain, and then apply universal generalization. In
this proof, we need to show that a conditional statement is true. Because of this, we now focus
on methods that show that conditional statements are true. Recall that p → q is true unless p is
true but q is false. Note that to prove the statement p → q, we need only show that q is true if p
is true.
104
Indirect Proofs.
Proofs of theorems of this type that are not direct
proofs, that is, that do not start with the premises and end with the conclusion, are called indirect
proofs.
types : proof by contraposition,
proof by contradiction.
105
Proof by contraposition:
Proofs by contraposition make use of the fact that the conditional statement p → q is equivalent to its
contrapositive, ¬q → ¬p.
This means that the conditional statement p → q can be proved by showing that its contrapositive, ¬q → ¬p, is true.
In a proof by contraposition of p → q, we
take ¬q as a premise, and using axioms, definitions, and previously proven theorems, together
with rules of inference, we show that ¬p must follow.
106
heuristic Summary:
```
p --> q is true when:
prove that if p is true then q is true (direct proof)
OR
prove if q is false p is false (proof by contraposition)
OR
hypothesis in false
OR
Conclusion is true
[picture conditional's truth table]
```
107
vacuous proof:
We can quickly prove that a conditional statement
p → q is true when we know that p is false, because p → q must be true when p is false. Consequently, if we can show that p is false, then we have a proof, called a vacuous proof, of the
conditional statement p → q.
Vacuous proofs are often used to establish special cases of theorems that state that a conditional statement is true for all positive integers [i.e., a theorem of the
kind ∀nP(n), where P(n) is a propositional function]
108
Trivial Proof:
We can also quickly prove a conditional statement p → q if we know that the conclusion
q is true. By showing that q is true, it follows that p → q must also be true. A proof of p → q
that uses the fact that q is true is called a trivial proof. Trivial proofs are often important when
special cases of theorems are proved and
in mathematical induction.
109
Lil proof strategy:
When you want to prove a statement of the form ∀x(P(x) → Q(x)), first evaluate whether
a direct proof looks promising. Begin by expanding the definitions in the hypotheses. Start to
reason using these hypotheses, together with axioms and available theorems. If a direct proof
does not seem to go anywhere, for instance when there is no clear way to use hypotheses as in
Examples 3 and 4 to reach the conclusion, try the same thing with a proof by contraposition.
(Hypotheses such as x is irrational or x ≠ 0 that are difficult to reason from are a clue that
an indirect proof might be your best best.)
110
Rational and Irrational:
The real number r is rational if there exist integers p and q with q ≠ 0 such that r = p∕q. A
real number that is not rational is called irrational.
111
Proof By Contradiction :
| for a statement.
Suppose we want to prove that a statement p is true. Furthermore, suppose that we can find a
contradiction q such that ¬p → q is true.
Because q is false, but ¬p → q is true, we can conclude
that ¬p is false, which means that p is true.
Now,
Because the statement r ∧ ¬r is a contradiction whenever r is a proposition, we can prove
that p is true if we can show that ¬p → (r ∧ ¬r) is true for some proposition r.
112
Contradiction and contrposition:
Note that we can rewrite a proof by contraposition of a conditional statement as a proof
by contradiction. In a proof of p → q by contraposition, we assume that ¬q is true. We then
show that ¬p must also be true. To rewrite a proof by contraposition of p → q as a proof by
contradiction, we suppose that both p and ¬q are true. Then, we use the steps from the proof of
¬q → ¬p to show that ¬p is true. This leads to the contradiction p ∧ ¬p
113
Proof by contradiction of conditional:
Proof by contradiction can be used to prove conditional statements. In such proofs, we first
assume the negation of the conclusion. We then use the premises of the theorem and the negation
of the conclusion to arrive at a contradiction. (The reason that such proofs are valid rests on the
logical equivalence of p → q and (p ∧ ¬q) → F. To see that these statements are equivalent,
simply note that each is false in exactly one case, namely, when p is true and q is false.)
114
PROOFS OF EQUIVALENCE
To prove a theorem that is a biconditional statement, that is, a
statement of the form p ↔ q, we show that p → q and q → p are both true. The validity of this
approach is based on the tautology
(p ↔ q) ↔ (p → q) ∧ (q → p).
115
Show that p1, p2, … , pn are all equivalent
propositions p1, p2, p3, … , pn are equivalent. This can be written as
p1 ↔ p2 ↔ ⋯ ↔ pn
which states that all n propositions have the same truth values, and consequently, that for all i
and j with 1 ≤ i ≤ n and 1 ≤ j ≤ n, pi and pj are equivalent. One way to prove these are mutually
equivalent is to use the tautology
p1 ↔ p2 ↔ ⋯ ↔ pn ↔ (p1 → p2) ∧ (p2 → p3) ∧ ⋯ ∧ (pn → p1).
116
If the n conditional statements p1 → p2, p2 → p3, … ,
pn → p1 can be shown to
be true, then?
If the n conditional statements p1 → p2, p2 → p3, … ,
pn → p1 can be shown to
be true,
then the propositions p1, p2, … , pn are all equivalent.
use the tautology
p1 ↔ p2 ↔ ⋯ ↔ pn ↔ (p1 → p2) ∧ (p2 → p3) ∧ ⋯ ∧ (pn → p1).
This is much more efficient than proving that pi → pj for all i ≠ j with 1 ≤ i ≤ n and 1 ≤
j ≤ n. (Note that there are n^2 − n such conditional statements.)
117
division of both sides of an equation by the same quantity is valid?
Division of both sides of an equation by the same quantity is valid as
long as this quantity is not zero.
118
Circular Reasoning:
Many incorrect arguments are
based on a fallacy called "BEGGING the QUESTION'. This fallacy occurs when one or more steps of
a proof are based on the truth of the statement being proved. In other words, this fallacy arises
when a statement is proved using itself, or a statement equivalent to it. That is why this fallacy
is also called circular reasoning.
119
Proof By Cases:
To prove a
conditional statement of the form
(p1 ∨ p2 ∨ ⋯ ∨ pn) → q
the tautology
[(p1 ∨ p2 ∨ ⋯ ∨ pn) → q] ↔ [(p1 → q) ∧ (p2 → q) ∧ ⋯ ∧ (pn → q)]
can be used as a rule of inference.
This shows that the original conditional statement with a hypothesis made up of a disjunction of the propositions p1, p2, … , pn can be proved by proving
each of the n conditional statements pi → q, i = 1, 2, … , n, individually. Such an argument is
called a proof by cases.
Sometimes to prove : p → q is true, it's
convenient to use a disjunction p1 ∨ p2 ∨ ⋯ ∨ pn instead of p as the hypothesis, where
p ≡ p1 ∨ p2 ∨ ⋯ ∨ pn.
120
EXHAUSTIVE PROOF
Some theorems can be proved by examining a relatively small number of examples. Such proofs are called exhaustive proofs, or proofs by exhaustion because
these proofs proceed by exhausting all possibilities. An exhaustive proof is a special type of
proof by cases where each case involves checking a single example.
121
LEVERAGING PROOF BY CASES
Generally, look for a proof by cases when there is no obvious
way to begin a proof, but when extra information in each case helps move the proof forward.
122
Formulate a conjecture about the final decimal digit of the square of an integer and prove your
result.
The final decimal digit of a perfect square is 0, 1, 4, 5, 6, or 9.
Express integer n as 10a + b, where a,b : +ve integers and b is 0 to 9. Here a is the integer obtained by subtracting the final decimal digit of n from n and dividing by 10.
Next, note that (10a + b)^2 = 100a^2 + 20ab + b^2 =
10(10a^2 + 2b) + b^2, so that the final decimal digit of n^2 is the same as the final decimal digit
of b^2. Furthermore, note that the final decimal digit of b^2 is the same as the final decimal digit
of (10 − b)^2 = 100 − 20b + b^2. Consequently, we can reduce our proof to the consideration of
six cases.
n = 1,9 ; 2,8; 3,7; 4,6;5;0.
123
Show that there are no solutions in integers x and y of x^2+ 3y^2 = 8.
We can quickly reduce proof to checking just a few simple cases because x^2 > 8
when |x| ≥ 3 and 3y^2 > 8 when |y| ≥ 2. This leaves the cases when x equals −2,−1, 0, 1, or 2
and y equals −1, 0, or 1. We can finish using exhaustive proof.
BUT
possible values for x^2 =0, 1, 4
possible values for 3y^2 = 0,3.
largest sum of possible values for x^2 and 3y^2 = 7. Consequently, it is impossible for
x2 + 3y2 = 8 to hold when x and y are integers.
124
WLOG
When the phrase “without loss of generality” is used in a proof, we assert that by proving one case of a theorem, no additional argument is
required to prove other specified cases. That is, other cases follow by making straightforward
changes to the argument, or by filling in some straightforward initial step. Proofs by cases can
often be made much more efficient when the notion of WLOG is employed.
like |xy| = |x||y|
the case x <0, y >0
and the case y <0, x>0 can be proved in single case stating WLOG.
125
COMMON ERRORS WITH EXHAUSTIVE PROOF AND PROOF BY CASES
A common
error of reasoning is to draw incorrect conclusions from examples. No matter how many separate
examples are considered, a theorem is not proved by considering examples unless every possible
case is covered. The problem of proving a theorem is analogous to showing that a computer
program always produces the output desired. No matter how many input values are tested, unless
all input values are tested, we cannot conclude that the program always produces the correct
output.
126
existence proof
Many theorems are assertions that objects of a particular type exist. A theorem of this type is
a proposition of the form ∃xP(x), where P is a predicate. A proof of a proposition of the form
∃xP(x) is called an existence proof
127
Witness
An existence proof of ∃xP(x) can be given by finding an element a, called a witness,
such that P(a) is true.
128
Constructive proof?
An existence proof of ∃xP(x) can be given by finding an element a, called a witness,
such that P(a) is true. This type of existence proof is called constructive.
129
Non Constructive proof:
use proof by contradiction and show that the
| negation of the existential quantification implies a contradiction.
130
Uniqueness Proofs
Some theorems assert the existence of a unique element with a particular property.
The two parts of a uniqueness proof are:
Existence: We show that an element x with the desired property exists.
Uniqueness: We show that if x and y both have the desired property, then x = y.
Remark: Showing that there is a unique element x such that P(x) is the same as proving the
statement ∃x(P(x) ∧ ∀y(y ≠ x → ¬P(y))).
131
Proof Strategy
1. When you are confronted with a statement to
prove, you should first replace terms by their definitions and then carefully analyze what the
hypotheses and the conclusion mean.
2. Look for counterexamples, if yes then there's no proof.
132
Forward and Backward reasoning:
Direct proof is Forward reasoning.
Usually, it's complicated so we use backward reasoning. To reason backward to prove a statement q,
we find a statement p that we can prove with the property that p → q. (Note that it is not helpful
to find a statement r that you can prove such that q → r, because it is the fallacy of begging
the question to conclude from q → r and r that q is true.)
(Note that the steps of our backward reasoning will
not be part of the final proof. These steps serve as our guide for putting this proof together
133
Adapting Existing Proofs:
Making use to existing proofs.
134
Checkboard:
A checkerboard is a rectangle divided into squares of the same size by horizontal and
vertical lines. The game of checkers is played on a board with 8 rows and 8 columns; this
board is called the standard checkerboard a
135
Domino
A domino is a rectangular piece that is one square
| by two squares
136
Tiled:
We say that a board is tiled by dominoes when all its
| squares are covered with no overlapping dominoes and no dominoes overhanging the board.
137
polyominoes:
Identically shaped pieces constructed from congruent squares that are
connected along their edges. Such pieces are called polyominoes.
138
FERMAT’S LAST THEOREM
The equation
x^n + y^n = z^n
has no solutions in integers x, y, and z with xyz ≠ 0 whenever n is an integer with n > 2.
The equation x^2 + y^2 = z^2 has infinitely many solutions in integers x, y, and z [Pythagorean triples].
139
procedure that can be used for proving theorems in
| mathematics
Finally, note that we have not given a procedure that can be used for proving theorems in
mathematics. It is a deep theorem of mathematical logic that there is no such procedure.
140
The 3x + 1 Conjecture
Let T be the transformation that sends an even integer x to x∕2 and
an odd integer x to 3x + 1. A famous conjecture, sometimes known as the 3x + 1 conjecture,
states that for all positive integers x, when we repeatedly apply the transformation T, we will eventually reach the integer 1. For example, starting with x = 13, we find T(13) =
3 ⋅ 13 + 1 = 40, T(40) = 40∕2 = 20, T(20) = 20∕2 = 10, T(10) = 10∕2 = 5, T(5) =
3 ⋅ 5 + 1 = 16, T(16) = 8, T(8) = 4, T(4) = 2, and T(2) = 1. The 3x + 1 conjecture has
been verified using computers for all integers x up to 5.48 ⋅ 10^18.
