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

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

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.