Introduction:
A proof may be a
valid argument that introduces the truth of a mathematical equation. A proof
can use the hypotheses of the therm. If any axioms assumed to be true, and previously
proved thermos. Using these ingredients and rules of inference the final step
of the proof establishes the truth of the statement being proved.
The topic
based for a statement to move from formal proofs of thermos toward more
informal proofs.
EXAMPLE 6
Let P (n) be “If a and b are positive integers
with a≥b then an≥bn ,”where the domain
consists of all
nonnegative integers. Show that P(0 ) is
true.
Trivial proof:
The
hypothesis p®q must be true if q
is true
As P (0)
Then the
statement as follows
a0
³ b0
a0 =1,
b0=1
This implies
1 ≥ 1.
Hence proved
P (0) is true for the given statement.
Example:
Prove that the sum of two rational numbers is
rational.
As
Two integers
p and q with q≠0, such that r=p/q.
And
Two integers
t and u with u≠0, such that s=t/u.
Adding these
two eq.
r + s = p/q
+ t/u
= ( pu + qt ) / qu.
So two
integers are derived pu + qt and qu with qu≠0, thus r + s is rational.
Proofs
by contradiction:
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.
The main
purpose of the contradiction proofs is to find the substitutions of the given
proposition.
Example
“Show
that at least four of any 22 days must fall on the same day of the weak.”
Proof:
As p be the proposition: at least four of any 22 days must fall on the same
day of the weak. This implies ~p is true.
There exist
7 days of the weak. 21 days from 22 occupies three days must fall on same days.
And r be proposition: 22 days are chosen.
This shows
at least one day must fall on the same day 4 times.
The
substitution is ~p → (r ^ ~r).
Consequently
p is true.
Example
“Prove
that √2 is irrational.”
Proof:
As p be the proposition: “√2 is irrational”.
√2 is not
irrational. ~p.
√2=a/b.
Taking
square on both sides.
2=a2/b2
2b2=a2.
Therefor
a=2c.
2b2=4c2.
b2=2c2. Here b2
is even.
So the √2 is
not a rational number.
The
contradiction is (p ^ ~p).
Example:
Show
that these statement about the integer n are equivalent:
P1:
n is even.
P2:
n – 1 is odd.
P3:
n2 is even.
Proof:
Three conditional statements as P1→P2, P2→P3 and P3→P1
are true.
Let n=2k, that is even.
And n-1=2k-1 is odd this implies n-1=2(k-1) +1.
If n-1 is an odd integer then n-1=2k+1.
So n=2k+2.
Taking square
n2=
(2k+2)2=4k2+8k+4
= 2(2k2+4k+2)
As 2k2+4k+2
is even.
Hence given conditions are true.
Mistakes
in proofs:
There are many errors made in constructing mathematical
proof. Here we discussed about some of these. Even professional mathematicians
make such errors, especially when working with complicated formulas.
(e.g)
The famous supposed proof that “1=2”.
Sol:
Let a &
b are two equal positive integers.
Steps;
1-
a
= b
Given
2-
a2
= ab
Multiply both sides by a
3-
a2
– b2 = ab – b2 Subtract b2
from both sides
4-
(a
– b)(a + b) = b(a – b) Factor both
sides
5-
a
+ b = b
Divide both sides by a - b
6-
2b
= b
Replace a by b as a = b
7-
2
= 1
Divide both sides by b
All steps are valid except 5, we divided both sides by a – b.
As a – b = 0. So that is the error. Division by same quantity
is valid until it become not a zero.
Propositions, propositional variables, connectives (¬, ˄, ˅, →, ↔) and the parentheses used in
the proper manner to form formula or a normal form or a propositional form.
A product of the variables and their negations in a
formula is called an elementary product.
(e.g)
¬p ˄q, q ˄ r ˄ ¬s, q etc.
A sum of the variables and their negations in a formula
is called an elementary sum.
(e.g)
¬p ˅ q, q ˅ p ˅ s, p etc.
A variable or the negation of a variable is called
literal.
*A necessary and sufficient condition for an elementary
product to be identically false (a contradiction) is that it contains at least
one pair of literals in which one is the negation of other.
F ˄. . . . is equal to F.
*A necessary and sufficient condition for an elementary
sum to be identically true (a tautology) is that it contains at least one pair
of literals in which one is the negation of other.
T ˅. . . . is equal to T.
Note: First replace → and
↔ by ˅, ˄ and ¬. Then use De Morgan’s law where need.
“A formula which is equivalent to a given formula and
consists of sum a elementary products is called a disjunctive normal form
(DNF)”
(e.g)
(p → q) ˄ ¬q
Sol:
(p → q) ˄ ¬q
=(¬p ˅ q) ˄ ¬q
=(¬p ˄ q) ˅ (q ˄ ¬ q)
DNF.
Conjunctive
normal form:
“A formula which is equivalent to a given formula and
consists of a product of elementary sums is called a conjunctive normal form
(CNF)”
(e.g)
(p → q) ˄ ¬q
Sol:
(p → q) ˄ ¬q
= (¬p ˅ q) ˄
¬q CNF.
Principal
disjunctive normal form:
“An
equivalent formula consisting of minterms only is known as principal
disjunctive normal form (PDNF)”. Such a normal form is also called sum of
products canonical form.
(e.g)
p ˅ ¬q
Sol:
p ˅ ¬q
= [p ˄ ( q ˅ ¬q)] ˅ [¬q ˄ (p ˅ ¬p)]
= ( p ˄ q) ˅ ( p ˄ ¬ q) ˅ ( ¬q ˄ p) ˅ (¬q ˄ ¬p)
= ( p ˄ q) ˅ ( p ˄ ¬q) ˅ ( ¬p ˄ ¬q)] PDNF.
Principal
conjunctive normal form:
“An equivalent formula consisting of conjunction of
maxterms only is known as principal conjunctive normal form (PCNF). This normal
form is also called the product of sums canonical form.
(e.g)
p ↔ q
Sol:
p ↔ q
= ( p → q) ˄
( q → p)
= (¬p ˅ q) ˄
( ¬q ˅ p) PCNF.
Normal
form for first order logic:
“A formula F
in the first order logic is said to be in a prenex normal form if and only if
the formula F is in the form of (Q1x1). . .(Qnxn)
(M) where every (Qixi), i =1, . . . n is either (Ʉxi)
or (Ǝxi), and M is a formula containing no quantifiers. (Q1x1). . .(Qnxn)
is called the prefix and M is called the matrix of the formula F.”
(e.g)
Ʉx P(x) → Ǝx Q(x)
Sol:
Ʉx P(x) → Ǝx Q(x)
= ¬ Ʉx P(x) → Ǝx Q(x)
= Ǝx (¬P(x)) ˅ Ǝx Q(x)
= Ǝx (¬P(x) ˅ Q(x))
0 Comments