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.

 


Russells 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 Dobacis 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.

 

 

ab ab

 

cd cd

Unrequited & Unrequited

uncomplicated love but complicated love

16.

 

 

ab ab

 

cd cd

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

 

"xRxx

 

being the father of

 

loves ???

24.

 


Non-reflexive

 

not reflexive

not irreflexive

 

 

$xRxx $xRxx

 

admires

25.

 

 

 

reflexive "xRxx

 

irreflexive "xRxx

 

non-reflexive

 

"xRxx "xRxx

 

$xRxx $xRxx

 

$xRxx $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(RxyRyx) "x"y(RxyRyx)

 

$x$y (RxyRyx) $x$y (RxyRyx)

 

$x$y (RxyRyx) $x$y(RxyRyx)

 

$x$y (RxyRyx) $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

 

"xRxx

40.


 

 

"x"y(RxyRyx) |- "xRxx

 

CES

 

{ "x"y( Rxy Ryx), "xRxx }

41.


"x"y(Rxy Ryx)

"xRxx

$xRxx

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.