__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 R*xy* 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: x_{1} , x_{2}
, …**

**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.

** **

**"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.**

** **

** **

**--- 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.**