Transcript Chapter 2

Chapter 2: Logic & Incidence Geometry
Back To the Very Basic Fundamentals
1
Copyright, 1996 © Dale Carnegie & Associates, Inc.
Logic Rule 0
• No unstated assumptions
may be used in a proof!
2
Theorems and Proofs
• A mathematical theorem is a conditional
statement of the form:
If H, then C.
(In symbols: H  C)
• A mathematical proof is a list of
statements, along with a justification for
each statement, ending with the conclusion
expected.
3
Logic Rules
(1)
Rule 1:The following are the six types of
justifications allowed for statements in
proofs:
1. By hypothesis. . .
2. By axiom . . .
3. By theorem . . .
4. By definition . . .
5. By (previous) step . . .
6. By rule . . . of logic
4
Logic Rules
(2)
Rule 2: Indirect Proof [redutio ad absurdum (RAA)] :
• To prove a statement H  C, assume the negation
of statement C (RAA hypothesis and deduce an
absurd statemtent, using H if needed.
• To prove: H  C
1. Assume H  ~C (Symbol for negation of C: ~C)
2. Use this idea to arrive at a contradiction to H or some
other known theorem, definition or axiom. ( Symbol
for contradiction: )
5
Logic Rules(Some of DeMorgan’s Laws) (3)
• Rule 3: The statement ~(~S) means S.
• Rule 4: The statement ~[H  C] is the same
statement as H & ~C. (& and  mean “and”)
(Alternate symbols: H  ~C)
• Rule 5: The statement ~ [S1  S2] means the
same thing as [~ S1  ~S2].
( means “or”)
• A contradiction (absurd statement) is a
statement of the form S  ~S. ()
6
Logic Rules: Quantifiers (1)
(4)
• Quantifiers are of two types:
– Universal: For all x …, For any x …, For every x…, If
x is any…
(Symbol: x)
(Note: For all… x does NOT imply the existence of anything!)
– Existential: There exists an x…, For some x…, There
are x…, There is an x…
(Symbol: x)
• Statements involving quantifiers: If S is a
statement that says something about x, written S(x),
and it is quantified, we write for example: x S(x)
or x S(x).
7
Logic Rules: Quantifiers (2)
(5)
• Rule 6: The statement ~[x S(x) ] means
the same as x ~S(x).
• Rule 7: The statement ~[x S(x)] means the
same as x ~S(x).
8
Logic Rules: Implication
(6)
• Rule 8: If P  Q and P are several steps in a
proof, then Q is a justifiable step.
• Conditional Statement: P  Q (If P, then Q.)
– Its converse: Q  P
– Its inverse: P  ~Q (negation)
– Its contrapositive: ~Q  ~P
• Logically equivalent: P  Q. “P if and only if Q”
P is logically equivalent to Q. (P and Q are the
same thing!)
9
Logic Rules: Tautologies
(6)
• Rule 9: Statements that are true strictly
because of their form and not what
individual parts might “say”.
A) [ [P  Q ]  [Q  R] ]  [P  R]
(Transitive)
B) [P  Q]  P, or, [P  Q]  Q (Inclusive)
C) [~Q  ~P]  [P  Q] (Contrapositive)
1
0
Logic Rules
(7)
• Rule 10: (The Excluded Middle) For every
statement P, P  ~P is a valid step in a proof.
• Rule 11: (Proof by cases) Suppose the
disjunction of statements S1  S2  …  Sn is
already a valid step in a proof. Suppose that
the proofs of C are carried out from each of the
case assumptions S1, S2 … Sn. Then C can be
concluded as a valid step in the proof.
1
1
Equivalence Relations: Logic Rule 12
•
•
•
An equivalence relationship ”=” between two objects “X
and Y” is a relationship with these three properties:
1. X (X=X), i.e. X is equivalent to itself. (reflexive)
2. X Y (X=Y  Y=X). (symmetric)
3. X Y Z[(X=Y & Y=Z) X=Z]. (transitive).
Also: If X=Y and S(X) is a statement about X,
then S(X)  S(Y).
Examples of equivalence relations:
a = b (equality) x  y (similar) AB  CD (congruent)
l || m (parallel) p  q (perpendicular)
Example of relations not equivalence classes.
c < d (less than)
C  D (proper subset)
1
2
Incidence Geometry
(1)
• Incidence Axioms
I-1: For every point P and for every
point Q not equal to P there exists a
unique line l incident with P and Q.
I-2: For every line l there exist at least
two distinct points that are incident with l.
I-3: There exist three distince points with
the property that no line is incident with all
three of them.
1
3
Incidence Geometry
(2)
Incidence Propositions
P-2.1: If l and m are distinct lines that are not parallel,
then l and m have a unique point in common.
P-2.2: There exist three distinct lines that are not
concurrent.
P-2.3: For every line there is at least one point not
lying on it.
P-2.4: For every point there is at least one line not
passing through it.
P-2.5: For every point P there exist at least two lines
through P.
1
4
Parallel
• Def of Parallel: l || m if l ~ I m
• Parallel Postulate (Euclid):
 l P, ~(P I l)  !m (P I m & l || m)
• Notation: P a point, l and m lines,
~ I not incident
1
5
Example 5: Isomorphism -- 1) one and only one
element goes to each member of the other set. 2) All
elements in the range are used up.
System 1: 3 points in the "universe" A, B, C
U = { A, B, C}
Points
Lines
A
a = {A,C}
B
b = {A,B}
C
c = {B,C}
System 2: 3 lines in the "universe" a,b,c
U = {a,b,c}
Lines
Points
a
A = {a,b}
b
B = {b,c}
c
C = {a,c}
1
6
Projective and Affine Planes
A projective plane is a model of the incidence
axioms having the elliptical property (any two
lines meet) and such that every line has at least
three distinct points lying on it.
An affine plane is a model of incidence geometry
having the Euclidean parallel property
1
7
Equivalence Classes
• An equivalence class C is the set of all objects y
equivalent to some object x.
C ={ y : y~x}
• Example: Given the affine plane A and a line l in
A (l A) the set of all lines m parallel to l would
be an equivalence class and represented by
[l] = {x : x || l, l  A} m  [l] (m is one of the
x’s. We write m ~ l and also [m] ~ [l].
1
8
Points at Infinity
• Points at infinity, by definition, are these
equivalence classes defined in the above example.
• The line at infinity l is the set of all the points at
infinity! l ={[t] : [t] ~ [l], l any line in A},
i.e. l = {[l], [k],[r] . . . where l, k, r  A but none
are parallel to each other}.
1
9