Propositional Logic
|= A
A is a tautology
Predicate Logic
|= A
A is true in all interpretations
A is a valid wff !?!
A is a quantology
1.
Santa Claus does not exist
S: Santa
Claus
! ! ! Ø $x (x=s)
|- $x (x=s)
Nx: x
is jolly man who dresses in red and defies the laws of nature by visiting all
children of the world in less than 24 hours.
2.
Santa Claus exists
$x
(Nx Ù "y
(Ny ® x=y))
Santa Claus does not exist
Ø
$x (Nx Ù "y
(Ny ® x=y))
3.
Russell’s Theory of Definite Descriptions
The Prince of Wales is a logican
Px : x is a Prince of Wales
Lx : x is a logican
$x((Px
Ù "y(Py
® y=x)) Ù Lx)
4.
Expressive power of quantifiers and identity
Someone talked
$xTx
At least 2 persons had sexual relations with Clinton
$x$y((Rx Ù Ry) Ù Ø(x=y))
At least 3 persons had …
$x$y$z(((Rx Ù Ry) Ù Rz) Ù((Ø(x=y) Ù Ø(x=z)) Ù Ø(y=z)))
5.
At most one person watched Clinton
"x"y((Wx Ù Wy) ® x=y)
At most two persons watched Clinton
"x"y"z(((Wx Ù Wy) ÙWz) ® ((x=y) Ú (x=z)))
and so on and so forth
6.
Numerical quantifiers
There is exactly one
President of the United States
$x(Px Ù "y(Py
®
x=y))
There are 2 leaders of the Tory Party
$x$y(((Lx Ù Ly) Ù Ø(x=y)) Ù "z(Lz ®((z=x) Ú (z=y))))
7.
“There are three people in this marriage”
Mx : x is in this marriage
$x$y$z((Mx Ù My Ù Mz) ÙØ(x=y) Ù Ø(x=z) Ù Ø(y=z)
Ù"w(Mw ® w=x Ú w=y Ú w=z))
8.
Relationships !!!
one place predicates
x is happy Hx
two-place predicates
x loves y Lxy
three-place predicates
x is between y and z
Bxyz
Relations - expressed by relational
predicates - predicates with 2 or more slots
9.
Relational predicate express a relation which holds between objects -
eg love between Othello and Desdemona
10.
Order makes a difference
“x is more boring than y”
Compare
<Toronto,
London>
<London,
Toronto>
<Cambridge,
Oxford>
<Oxford,
Cambridge>
11.
Same or different
“x is the same age as y”
different objects
<Newton-Smith, Jones>
same object
<Dobaci, Dobaci>
12.
Some require different objects
“x is taller than y”
Not even in Dobaci’s case is it true that Dobaci is taller than Dobaci.
Some require the same object
“x is identical to y”
<Dobaci, Dobaci>
13.
Hodges’ little pictures
a·¾¾¾¾>·b
a is taller than b
a·<¾¾¾¾>·b
a loves b
b loves a
14.
∙Romeo
∙Juliet
∙Thatcher
∙Heath
∙Dobaci
¯
∙Isabel
15.
a∙®∙b a∙®∙b
c∙®∙d c∙®∙d
Unrequited & Unrequited
uncomplicated love but
complicated love
16.
a∙«∙b a∙«∙b
c∙«∙d c∙«∙d
Requited but Requited &
boring love exciting
love
17.
Domains
set {a, b, c, d}
(unordered)
Relation : loving
picture
a b c d
· ·
· ·
18.
The story with ordered pairs
{ <a, b> <b,
a> <b, c>
<a, c> <d,
d> }
19.
Pair of objects <a , b> satisfies
relation predicate Rxy just in case a bears R to b.
We take variables in alphabetical order and
assign first object in pair to first variable …
Or better we use numerical subscripts: x1 , x2
, …
20.
Hodges:
A binary relation is called reflexive
if every dot in its graph has a loop attached.
21.
Reflexive
"xRxx
Domain : audience
same age as
loves ???
likes ???
domain of narcicists ???
22.
Hodges:
A binary relation is called irreflexive
if no dot in its graph has a loop attached.
23.
Irreflexive
"xØRxx
being the father of
loves ???
24.
Non-reflexive
not reflexive
not irreflexive
$xRxx Ù $xØRxx
admires
25.
reflexive "xRxx
irreflexive "xØRxx
non-reflexive
Ø"xRxx
Ù Ø"xØRxx
$xØRxx Ù $xØØRxx
$xØRxx Ù $xRxx
26.
Hodges
A binary relation is called symmetric if no arrow in its graph
is single
27.
Symmetry
a·<¾>·b c·<¾>·d
"x"y(Rxy
® Ryx)
same height as
loves ???
28.
Asymmetric
one way arrows only
a b c
·¾>·¾¾>·
"x"y(
Rxy ® ØRyx
)
taller than
loves ???
29.
Non-symmetric
not symmetric
not asymmetric
a·¾¾>·b c·<¾¾>·d
$x$y( Rxy Ù Ryx
) Ù $x$y( Rxy Ù ØRyx )
liking
hating
admiring
30.
Symmetric
"x"y (Rxy ® Ryx)
Asymmetric
"x"y (Rxy ® ØRyx)
Non-symmetric
Ø"x"y(Rxy®Ryx) Ù Ø"x"y(Rxy®ØRyx)
$x$y Ø(Rxy®Ryx) Ù $x$y Ø(Rxy®ØRyx)
$x$y ØØ(RxyÙØRyx) Ù $x$yØØ(RxyÙØØRyx)
$x$y (RxyÙØRyx) Ù $x$y (Rxy Ù Ryx)
31.
A binary relation is called transitive
if its graph contains no broken journey
without a short cut.
32.
Transitive
a b c
·¾>· ¾¾>·
being as nice as
being as tall as
"x"y"z((Rxy Ù Ryz) ®Rxz)
33.
A binary relation is called intransitive
if its graph contains no broken journey
with a short cut.
34.
Intransitive
a b c
·¾>· ¾¾>·
being the parent of
being twice as heavy
as
"x
"y "z ((Rxy Ù Ryz)® ¬Rxz)
35.
Non-transitive
not transitive
not intransitive
a b c
·¾>· ¾¾>·
d e f
·¾>· ¾¾>·
36.
Non-transitive
$x$y$z((Rxy
Ù Ryz)Ù Rxz) Ù$x$y$zz((Rxy Ù Ryz)
Ù ØRxz)
indistinquishable in weight on this scale
likes ?
37.
Hodges
A binary relation is called connected
if in its graph, any two dots are connected by an arrow in one direction or the
other (or both).
38.
Connected
"x"y (Ø(x=y)
® (Rxy Ú Ryx))
- greater than -
39.
Doing things with relations
Show that any asymmetrical relation is
irreflexive.
Asymmetrical
"x"y(
Rxy ® ØRyx)
irreflexive
"xØRxx
40.
"x"y(Rxy®ØRyx) |- "xØRxx
CES
{ "x"y( Rxy ® ØRyx), Ø"xØRxx }
41.
"x"y(Rxy ® ØRyx)
Ø"xØRxx
$xØØRxx
ØØRaa
Raa
"y(Ray ® ØRya)
(Raa ® ØRaa)
ØRaa ØRaa
42.
Some relations do neat
things.
Domain : audience
+ lecturer
--- is the same age as ....
Reflexive
Symmetric
Transitive
Take yourself and a bundle of two-way arrows.
Get a cluster around you of equally aged persons.
43.
44.
Equivalence Relation
Reflexive
Symmetric
Transitive
equality in a respect
45.
Equivalence relations produce partitions.
Partition
bunch of subsets
everyone is in one
no one is in two of them
everyone in one is related to everyone else in it and to no one outside
of it
46.
Now pray tell me what Time is ? You know the very trite Saying of St
Augustin, If no one asks me, I know; but if
any Person should require me to tell him, I cannot. But because Mathematicians frequently make use of
Time, they ought to have a distinct Idea of the meaning of that Word, otherwise
they are Quacks. My Auditors may
therefore very justly require an Answer from me, which I shall now give, and
that in the planest and least ambiguous Expressions, avoiding as much as
possible all trifling and empty words.
I Barrow Lectiones Geometricae
47.