Transcript A2 Mathematical Logic

A2 Part A Mathematical Logic
Appetizer: True or False
1. 2  2
2. If 2 = 3, then 5 = 6.
3. If 1 = 2, then I am the Pope.
4. Open the window.
5. If the proof is wrong, then the proposition is
wrong.
6. If 1=2 or 3 = 4, then 2 = 3.
7. If I come, then I come.
8. If it is a rhombus, then its diagonals are perp.
9. If the diagonals of a quad. are perp, then it is a
rhombus.
Truth Tables
(I) “P and Q”, denoted by PQ
P
Q
PQ
T
T
T
T
F
F
F
T
F
F
F
F
Truth Table for “P or Q”,
denoted by P Q
P
Q
PQ
T
T
T
T
F
T
F
T
T
F
F
F
Truth Table for negation of P,
denoted by ~P
P
~P
T
F
F
T
Negate the following statements:
(i) The sun is spherical and the plane
can fly.
(ii) London is not the capital of China
or the house is made of wood.
(iii) All birds are white.
(iv) Some men are tall.
(v) All women are kind and helpful.
Section 2 Equivalence of Two
Propositions
Two propositions with the same
components P, Q, R,… are said to be
logically equivalent(or equivalent) if they
have the same truth value for any truth
values of their components.
De Morgan’s Law
Let P, Q be two propositions, then
~(PQ) 
(~ P ) ∨(~ Q)
(II) ~(PQ) 
(~ P ) ∧(~ Q)
(I)
Proof of ~(PQ)  (~P)(~Q)
P
Q
PQ
T
T
T
F
F
F
F
T
F
F
T
F
T
T
F
T
F
T
T
F
T
F
F
F
T
T
T
T
~(PQ)
~P ~Q (~P)(~Q)
Proof of ~(P  Q)  (~P)  (~Q)
P
Q
P Q ~(P Q) ~P
~Q (~P) (~Q)
T
T
T
F
F
F
F
T
F
T
F
F
T
F
F
T
T
F
T
F
F
F
F
F
T
T
T
T
Section 3 Conditional Propositions:
If P then Q, denoted by P Q
Determine the truth value of the following:
1. If Fun is a boy, then he is a human being.
2. If Fun is a human being,
then Fun is a boy.
 8.
3. If x = 2 then x2 = 4.
4. If x2 = 4, then x = 2.
5. If a triangle is isosceles, then it is
equilateral.
6. If a triangle is equilateral, then it is
isosceles.
7. If |a|= -a, then a < 8.
Truth Table for P Q
P
Q
PQ
T
T
T
T
F
F
F
T
T
F
F
T
How many statements can be
formed by using:
P, Q,
,,  and ~ .
There are 16 equivalent statements can be formed.
In general, there are 2 to the power 2n equivalent
statements formed by n statements.
Popular questions
1.
If x = 2, then x2 = 4.
2. If x2= 4, then x = 2.
Are they true?
6. x = 2  x2 = 4.
7.
x2 = 4  x = 2.
1. Make the truth tables for these four
propositions.
Definition 3.4
2. Are they equivalent?
Let P Q be a conditional proposition.
This proposition has the following three
derivatives(衍生命題):
1. The converse(逆命題) Q P,
2. The inverse(否命題) (~P) (~Q)
3. The contrapositive(逆反命題) (~Q)  (~P)
Proof by contrapositive(反證法)
P Q  (~Q) (~P)
Example 1
If n2 is an even integer then n is an
even integer.
Proof:
If n is odd, then n = 2k + 1 and
(2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1
is odd. Thus by contrapositive, the
proposition is correct.
Example 2
Given that p and m are real numbers
such that p3+m3=2, prove that
p + m  2.
Proof:
Assume that p+m>2,
then p3+m3>(2-m)3+m3
=6m2-12m+8
=6(m-1)2+2  2.
Thus, by contrapositive, p + m  2.
Class work : Use the method of contradiction to
contradiction(歸謬法)
proveProof
that 3 by
is irrational.
(~P)  F
Example 3.3
Use the method of contradiction to prove
that 2 is irrational.
Proof: Suppose that 2 is not irrational, then
2 = p/q for some natural numbers p, q
where (p, q) = 1. Since
2 =p2/q2, therefore 2q2=p2. This implies
that 2|p2 and hence 2|p. So p=2k for some
integer k. Putting it back to 2q2=p2,
2q2=(2k)2 i.e. q2=2k2. Again, we have 2|q
and 2|(p, q) , which is a contradiction.
Theorem (proved by Euclid): There
are infinitely many prime numbers.
Proof:
Assume there are only n prime numbers, say
p1, p2, p3,…,pn. Now construct a new number
p= p1p2p3…pn + 1, then p is a new prime
number since p is not divisible by pi’s and p >
pi’s. This leads to a contradiction that p1, p2,
p3,…,pn are the only prime numbers. So there
are infinitely many prime numbers.
Examples of proof by contradiction
~(PQ) ~( (~P)Q)  P(~Q) F
1. If x=2, then x is irrational.
Proof: Assume that x= 2 and x is
not rational, then …
2. If a + b2 = c + d2, then b = d.
Proof: Assume that a + b2 = c + d2
but bd, then 2 = (a – c)/(d – a),
which is rational and hence is a
contradiction. Thus b = d.
P.65, Q.6
Illustrative Examples
3. If ABC is a acute triangle and
A>B>C, prove that B> 45.
Proof:
Assume that ABC is a acute triangle
and B 45, then C < 45.
But A=180 - B- C > 90 leads to a
contradiction that ABC is a acute
triangle. Thus,by the method of
contradiction, B> 45.
Illustrative Examples
4. If x=n and y=n+1, then x and y are
relatively prime.
Proof: Assume that x=n and y=n+1 and x
and y have common factor other than 1, say
f, then n=fg and n+1=fh. So 1 = f(h-g) and
hence f=1, which is a contradiction. Thus
the proposition is true.
.
5. Given that a, b,c and d are
real numbers and ad-bc=1, prove
that a2+b2+c2+d2+ab+cd1.
Proof:
Assume that a, b,c and d are real numbers
and ad-bc=1, but a2+b2+c2+d2+ab+cd=1, then
a2+b2+c2+d2+ab+cd=ad-bc. Multiplying it by
2, we get 2a2+2b2+2c2+2d2+2ab+2cd2ad+2bc=0
i.e.(a+b)2+(b+c)2+(c+d)2+(a-d)2=0
a+b=b+c=c+d=a-d=0
i.e.a=b=c=d=0, which contradict to that
ad-cd=1. Thus, by the method of
contradiction, a2+b2+c2+d2+ab+cd  1.
Section 4
Biconditional Propositions
Definition 4.1
Let P and Q be two propositions.
The biconditional proposition PQ
(read as “P if and only if Q”) is
defined as
P Q  (PQ) (QP)
Complete the Truth Table of
P Q  (PQ) (QP)
P
Q
T
T
T
F
F
T
F
F
PQ
QP (PQ) (QP)
Theorem 4.1
1. If (PQ)(Q R) then P R.
2. If (PQ)(Q  R) then P  R.
3. P Q  Q  P
Group discussion: Prove proposition 1-3
If (PQ)(Q R) then P R.
Proof:
P
T
F
F
F
Q
T
T
F
F
R
T
T
T
F
PQ
T
T
T
T
 Q R
T
T
T
T
T
T
T
T

T
T
T
T
P R
T
T
T
T
Classwork:1.Translate the propositions on P.64 Q4 to symbols.
2.Negate the above Propositions.
Universal Quantifier :  for all
Existential Quantifier:  for some
1.
Some birds are white.
In symbol, (bird B)(B is white)
2. For any integer n , the equation x2-nx+1=0 must
have a real solution.
(integer n)(x2-nx+1=0 has a real solution)
3. The equation xn+yn=zn has no integral solutions for
all integers n  3.
(integer n 3)(xn+yn=zn has no integral
solutions.)
4. For some real numbers n, if n2=4 then n = 2.
(real n)(n2=4  n = 2)
Resources
Write down the contrapositive of the
following propositions:
• If you pass both Physics and
Chemistry, then you are able to
promote to F.7.
•
If x2  4 and x > 0, then x  2.
Sometimes the proposition is
conditional i.e. PQ,
We need to negate it in order to prove it
by contradiction.i.e. ~ (PQ) F.
But ~ (PQ)  ?
(Hint: Find an equivalent statement for
PQ which involves P, Q, ~ and .)
PQ  (~P)Q
P
Q
PQ
T
T
T
FTT
T
F
F
FFF
F
T
T
TTT
F
F
T
TTF
(~P )  Q
~(PQ) ~( (~P)Q)  P(~Q)
1.
2.
3.
4.
5.
Write down the negation of
P Q
If today is Sunday, you need not go to
school.
If I can live without food, then I need
not earn money.
P (P Q)
In the classroom, all students are girls.
Write the negation of:
7. Nobody can answer the question.
8. For any positive integer n, n + 8 > 0.
9. All students are clever and some of
them are lazy.
10. For any even number x, if x is divisible
by 3 then x is divisible by 6.
11. There exist natural numbers p and q
such that 2 = p/q.
Definition 3.2
When the conditional proposition P Q
is always true, we write P Q and read
as P implies Q.
For instance, it is correct to write
“x = 2  x2 = 4”,
but incorrect to write
“x + a = b  x = a + b”
Definition 3.3
Let P Q be a conditional proposition.
Then P is called the sufficient condition
(充分條件) for Q,
and Q is the necessary condition(必要條
件) for P.
Pick out the different one from
the following statements:
1.
2.
3.
4.
5.
6.
If I receive a bonus, I shall have a
holiday in Spain.
I shall have a holiday in Spain if I receive
a bonus.
I shall have a holiday in Spain provided
that I receive a bonus.
I receive a bonus only if I shall have a
holiday in Spain.
Receiving a bonus is a sufficient condition
for a holiday in Spain.
Having a holiday in Spain is a necessary
condition for receiving a bonus.
B
Example 4.1
h
A
m
n
C
In the Figure, P is a point on AC such
that BPAC, PA = m, PB = h and PC = n.
Prove that h2= mn iff ABC = 90.
Exercise on Logic
1.
2.
3.
4.
5.
6.
7.
8.
Prove that if 3|n2 then 3|n.
Prove that 3 is irrational.
Prove that 2+ 3 is irrational.
Prove that for any real numbers a, b, c and d,
if a + bi = c + di then a = c and b=d, where i2=
-1.
Prove that log2 is irrational.
If 2p-1 is a prime number, then p is prime.
Given that a > 0 and b > 0, prove that
[(a+b)/2]3  (a3+b3)/2
Given that b and c are odd integers, prove
that x2 + bx + c = 0 has no integral roots.