Logic: Mathematics Computer Science

LECTURE SLIDES
on
LOGIC
for
MATHEMATICS
and
COMPUTER SCIENCE
(LMCS, p. 1)
I.2
This set of lecture slides is a companion to

the textbook
Logic for Mathematics
and Computer Science
by Stanley Burris, Prentice Hall, 1998.
At the top of each slide one sees LMCS,
referring to the textbook, usually with a page
number to indicate the page of the text that
(more or less) corresponds to the slide.
(LMCS, p. 5)
ARISTOTLE (4th Century B.C.)
Invented Logic
All men are mortal.

Socrates is a man.
Socrates is mortal.
Some students are clever.

Some clever people are lazy.
Some students are lazy.
I.3
(LMCS, p. 5)
I.4
The four kinds of statements permitted in

the categorical syllogisms of Aristotle.
A
All S is P.
universal affirmative
No S is P.
universal negative
Some S is P.
particular affirmative
Some S is not P.
particular negative
Mnemonic Device:
A ff I rmo
nEgO
(LMCS, pp. 56)
I.5
Syllogisms
Syllogisms are 3 line arguments:

Major Premiss
(Use P and M)
Minor Premiss
(Use S and M)
Conclusion
S P
Actually you can write the premisses in any

order.
The major premiss is the one with the
predicate of the conclusion.
The minor premiss is the one with the
subject of the conclusion.
(LMCS, pp. 56)
I.6
Now there are 2 2 2 1 = 8 possibilities

for the major premiss
and likewise 8 possibilities for the minor
premiss
but just 2 2 = 4 possibilities for the
conclusion S P
So there are 256 different syllogisms.
A main goal of Aristotelian logic was to
determine the valid categorical syllogisms.
(LMCS, pp. 56)
I.7
Classification of Syllogisms
The mood XYZ of a syllogism is the AEIO
classification of the three statments in a
syllogism, where the first letter X refers to
the major premiss, etc.
For example the syllogism
All students are clever.
No clever people are lazy.
No students are lazy.

has the mood EAE.
There are 64 distinct moods.
(LMCS, pp. 56)
I.8
The figure of a syllogism refers to whether or

not the middle term M comes first or second
in each of the premisses.
The four figures for syllogisms:
1st Figure
2nd Figure
M P
P M
S M
S M
S P
S P
3rd Figure
4th Figure
M P
P M
M S
M S
S P
S P
(LMCS, pp. 67)
I.9
Venn Diagrams for A, E, I, O statements:

SHADED regions have NO ELEMENTS in
them.
E
A
S
O
S
[Note: the shading for the Venn diagram for A is not

correct in the textbook this mistake occurred when,
shortly before going to press, all the figures in the text
needed to be redrawn with heavier lines. For a few
other items that need to be changed see the Errata
sheet on the web site. S.B.]
(LMCS, pp. 67)
I.10
The first figure AAI syllogism:

S
All M is P .
All S is M .
Some S is P .
This is not a valid syllogism by modern

standards, for consider the example:
All animals are mobile.
Unicorns are animals.
Some unicorns are mobile.
[In this case modern means subsequent to

C.S. Peirces paper of 1880 called The Algebra of
Logic.]
(LMCS, pp. 67)
I.11
But by Aristotles standards the first figure

AAI syllogism is valid:
All M is P .
All S is M .
Some S is P .
The previous example about unicorns would

not be considered by Aristotle.
After all, why argue about something that
doesnt even exist.
(LMCS, pp. 67)
I.12
Third figure III syllogism:
Some M is P .
Some M is S.
Some S is P .
There are two situations to consider:

S
S
or
P
M
The second diagram gives a

counterexample. This is not a valid
syllogism. To be a valid syllogism the
conclusion must be true in all cases that
make the premisses true.
(LMCS, p. 8)
I.13
The Valid Syllogisms

Major premiss
Minor premiss
First figure
Second figure
Third figure
Fourth figure
Conclusion
A
E
I
O
A
E
I
O
A
E
I
O
A
E
I
O
AAAA EEE E
AE I OAE I O
etc.
means we assume the classes S, P, M are

not empty.
(LMCS, pp. 1011)
I.14
George Boole (1815 1864)

Booles Key Idea: Use Equations
For the universal statements:
The statement
becomes the equation
All S is P .
S P0 = 0
or just
SP 0 = 0.
No S is P .
SP = 0
or just
SP = 0.
Boole also had equations for the particular

statements. But by the end of the 1800s they
were considered a bad idea.
(LMCS, pp. 1011)

Example
The first figure AAA syllogism
All M is P.
All S is M.
All S is P.
becomes the equational argument
MP 0 = 0
SM 0 = 0
SP 0 = 0.
I.15
(LMCS, p. 1011)
I.16
We see that the equational argument (about

classes)
M P 0 = 0,
SM 0 = 0
SP 0 = 0
is correct as
SP 0 = S1P 0
= S(M M 0)P 0
= SM P 0 SM 0P 0
= 00
= 0.
For equational arguments you can use the
fundamental identities.
(LMCS, p. 12)
I.17
Fundamental Identities
for the Calculus of Classes
1.
X X
idempotent
2.
X X
idempotent
3.
X Y
Y X
commutative
4.
X Y
Y X
commutative
5.
X (Y Z) =
(X Y ) Z
associative
6.
X (Y Z) =
(X Y ) Z
associative
7.
X (X Y ) =
absorption
8.
X (X Y ) =
absorption
(LMCS, p. 12)
I.18
9.
X (Y Z) =
(X Y ) (X Z)
distributive
10.
X (Y Z) =
(X Y ) (X Z)
distributive
11.
X X0 =
12.
X X0 =
13.
X 00 =
14.
X 1 =
15.
X 1 =
16.
X 0 =
17.
X 0 =
18.
(X Y )0 =
X0 Y 0
De Morgans law
19.
(X Y )0 =
X0 Y 0
De Morgans law.
(LMCS, p. 13)
I.19
Boole applied the algebra of equations to

arguments with many premisses, and many
variables, leading to:
Many Equations with Many Variables
F1(A1, . . . , Am, B1, . . . , Bn) = 0
...
Fk (A1, . . . , Am, B1, . . . , Bn) = 0
F (B1, . . . , Bn) = 0.
Booles work marks the end of the focus on
Aristotles syllogisms, and the beginning of
Mathematical Logic.
(LMCS)
Chapter 1 of LMCS gives four different
methods for analyzing such equational
arguments:
Fundamental Identities
for algebraic manipulations
Venn Diagrams
The Elimination Method of Boole
The Tree Method of Lewis Carroll
I.20
(LMCS, p. 21)
I.21
A
ABC
Venn Diagrams
ABC
A BC
subdivide the plane into connected

constituents.
B
is not a Venn
A
diagram.
(LMCS, p. 22)
I.22
Venns Venn Diagrams
Two Classes
Four Classes
Three Classes
Five Classes
(LMCS, p. 22)
I.23
Venns Construction for 6 Regions
Draw the three

circles first, then
add: (4) the blue
region, (5) the red
region, and finally
(6) the green region.
(This can be
continued for any
number of regions.)
This
diagram is courtesy of Frank Ruskey from his

Survey of Venn Diagrams:
www.combinatorics.org/Surveys/ds5/VennEJC.html
(LMCS, p. 22)
I.24
Edwards Construction for 6 Regions
Draw the
perpendicular lines
and the circle first.
Then follow the
circle with: (4) the
blue region, (5) the
red region, and (6)
the green region.
Join the endpoints of
the perpendicular
lines to make closed
regions.
This
diagram is courtesy of Frank Ruskey from his

Survey of Venn Diagrams:
(LMCS, p. 22)
I.25
A Symmetric Venn Diagram

Venn diagrams
with n regions that
admit a symmetry
of rotation by 2/n
are symmetric.
This can hold only
if the regions are
congruent and n is
prime. Such are
known for
n = 2, 3, 5, 7, but
not for n 11.
This
diagram, using 5 congruent ellipses, is courtesy

of Frank Ruskey from his Survey of Venn Diagrams:
(LMCS)
I.26
Simplification of the Premisses

(Useful before shading a Venn diagram.)
Write each premiss as a union of intersections
of classes or their complements.
Then put each of the intersections equal to 0.
Example
Express the premiss A(B 0C)0 = 0
AB AC 0 = 0
and then break this up into:
AB = 0
and
AC 0 = 0.
as
(LMCS, p. 25)
I.27
Example
Given
(AC B)(AB 0 C 0) = 0,
for the Venn diagram first simplify this to

AB 0C = 0
and
BC 0 = 0
Now proceed to shade the intersections AB 0C

and BC 0 :
B
(LMCS, pp. 2324)
I.28
Two methods for such simplification:

Use Fundamental Identities
(We have already discussed this.)
Booles Expansion Theorem
For two variables A, B this looks like:
F (A, B) = F (1, 1)AB F (1, 0)AB 0

F (0, 1)A0B F (0, 0)A0B 0
or just expanding on A gives
F (A, B) = F (1, B)A F (0, B)A0
(LMCS, pp. 2324)

Example
For
F (A, B) = (A0 B)0

F (1, 1) = (10 1)0 = 1
F (1, 0) = (10 0)0 = 1
F (0, 1) = (00 1)0 = 0
F (0, 0) = (00 0)0 = 1
Thus
F (A, B) = AB AB 0 A0B 0.
I.29
(LMCS, p. 26)
I.30
Reducing the Number

of Premiss Equations to One
One can replace the premiss equations
F1 = 0
...
Fk = 0
by the single equation
F1 . . . Fk = 0.
This follows from the fact that A B = 0

holds iff A = 0 and B = 0 hold.
(LMCS, p. 26)
I.31
Example
The two premisses
A(B 0C)0 = 0
(A B)C 0 = 0
become
A(B 0C)0
(A B)C 0
= 0.
(LMCS, p. 26)
I.32
Booles Main Result

The Elimination Theorem
Given the single premiss
E(A1, . . . , Am, B1, . . . , Bn) = 0
what is the most general conclusion
F (B1, . . . , Bn) = 0
involving only the classes B1, . . . , Bn ?
Answer: F is the intersection of instances of
E obtained by putting 0s and 1s in for the Ai,
in all possible ways. So F is:
E(0, . . . , 0, B1, . . . , Bn) E(1, . . . , 1, B1, . . . , Bn)
(LMCS)
I.33
Example
Find the most general conclusion involving
only P and S that follows from
P Q0 = 0
QR0 = 0
RS 0 = 0
First collapse the premisses into a single

premiss E = 0 by setting
E(P, Q, R, S) = P Q0 QR0 RS 0.
The most general conclusion for P and S is

E(P, 0, 0, S) E(P, 0, 1, S) E(P, 1, 0, S) E(P, 1, 1, S) = 0.
This is P (P S 0)1S 0 = 0, and simplifies to

P S 0 = 0.
(LMCS, p. 17,18)
I.34
Lewis Carrolls TREE METHOD

Showing
F = 0
FX = 0
reduces to showing
and
F X0 = 0
since
F = F X F X 0.
To show a conclusion F = 0 is valid simply

build an (upside down) tree
starting with the conclusion
with each branch multiplying out to 0.
(LMCS, p. 17,18)
I.35
Example
1. P Q0 = 0
To show that
is valid:
2. QR0 = 0
3. RS 0 = 0
P S0 = 0
PS
Q
R
3
Q
R
(LMCS, pp. 1618)
I.36
Translating the lengthy argument in Example

1.3.4 into equations:
1. Good-natured tenured
mathematics professors
ABC D
or
are dynamic .
ABCD 0 = 0.
2. Grumpy student advisors

play slot machines .
A0 M L
Etc.
or
A0M L0 = 0.
(LMCS)
I.37
A Naive Approach to
1.
4.
7.
10.
ABCD 0 = 0
GM C 0 = 0
M I 0J 0 = 0
H 0 F L0 = 0
A 0 M L0 = 0
B 0F H = 0
HM K 0 = 0
M LF = 0
2.
5.
8.
11.
3.
6.
9.
12.
F ED = 0
D 0 BEG0 = 0
KJL0 E 0 = 0
KIAE 0 = 0
MF = 0
MF
A
B
C
D
E
G G
B
C
B
C
ETC.
(LMCS, p. 18)
A Smart Approach
1. ABCD 0 = 0 2.
4. GM C 0 = 0 5.
7. M I 0J 0 = 0
8.
10. H 0F L0 = 0 11.
MF = 0
I.38
A 0 M L0 = 0
B 0F H = 0
HM K 0 = 0
M LF = 0
3.
6.
9.
12.
MF
L
11
10
K
E
E
D
12
1
4
J
7
F ED = 0
D 0BEG0 = 0
KJL0E 0 = 0
KIAE 0 = 0

Logic: Mathematics Computer Science

Uploaded by

Copyright:

Available Formats

Logic: Mathematics Computer Science

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Logic: Mathematics Computer Science

Uploaded by

Copyright:

Available Formats

LECTURE SLIDES

This set of lecture slides is a companion to

All men are mortal.

Some students are clever.

Some students are lazy.

The four kinds of statements permitted in

(LMCS, pp. 56)

Syllogisms are 3 line arguments:

Actually you can write the premisses in any

(LMCS, pp. 56)

Now there are 2 2 2 1 = 8 possibilities

(LMCS, pp. 56)

No students are lazy.

(LMCS, pp. 56)

The figure of a syllogism refers to whether or

(LMCS, pp. 67)

Venn Diagrams for A, E, I, O statements:

[Note: the shading for the Venn diagram for A is not

(LMCS, pp. 67)

The first figure AAI syllogism:

This is not a valid syllogism by modern

[In this case modern means subsequent to

(LMCS, pp. 67)

But by Aristotles standards the first figure

The previous example about unicorns would

(LMCS, pp. 67)

Third figure III syllogism:

There are two situations to consider:

The second diagram gives a

The Valid Syllogisms

means we assume the classes S, P, M are

(LMCS, pp. 1011)

George Boole (1815 1864)

becomes the equation

Boole also had equations for the particular

(LMCS, pp. 1011)

We see that the equational argument (about

Boole applied the algebra of equations to

subdivide the plane into connected

Venns Venn Diagrams

Venns Construction for 6 Regions

Draw the three

diagram is courtesy of Frank Ruskey from his

diagram is courtesy of Frank Ruskey from his

A Symmetric Venn Diagram

diagram, using 5 congruent ellipses, is courtesy

Simplification of the Premisses

for the Venn diagram first simplify this to

Now proceed to shade the intersections AB 0C

(LMCS, pp. 2324)

Two methods for such simplification:

F (A, B) = F (1, 1)AB F (1, 0)AB 0

(LMCS, pp. 2324)

F (A, B) = (A0 B)0

Reducing the Number

This follows from the fact that A B = 0

Booles Main Result

First collapse the premisses into a single