Predicate

Logic

1
 Propositional Logic Redux

Recall: A proposition is a declarative sentence that is either

true or false.
A compound proposition is a expression formed from
propositional variables (e.g., P, Q), values (T and F) and
logical operators (e.g., ^, v).
And elimination / and introduction
And elimination lets us infer the truth of either of the
conjuncts from the truth of a conjunctive sentence. For
instance, P  Q lets us conclude both P and Q are true.

And introduction allows us to infer the truth of a conjunction

from the truth of its conjuncts. For instance, if P and Q are
true, then P  Q is true.
Tautology and Contradiction

A tautology is a compound proposition that is

always true.
A contradiction is a compound proposition that is
always false.
A contingency is neither a tautology nor a
contradiction.
A compound proposition is satisfiable if there is
at least one assignment of truth values to the
variables that makes the statement true.
 Examples

p p pp pp
T F T F

F T T F
   
 Logical Equivalence

Two compound propositions, p and q, are logically

equivalent if p  q is a tautology.
Notation: p  q
De Morgan‟s Laws:

 p q  p q

 p q  p q


 Predicate Logic

Some statements cannot be expressed in propositional

logic, such as:
All men are mortal.
Some trees have needles.
X > 3.
Predicate logic can express these statements and make
inferences on them.
 Subjects and Predicates
In predicate logic,
every atomic sentence consists of
one predicate
and
one or more “subjects”
including subjects, direct objects,
indirect objects, etc.

in mathematics “subjects” are called “arguments”

(Shakespeare used the term „argument‟ to mean „subject‟)

8
 Example 1

Subject Predicate

Jay is asleep

Kay is awake

Elle is a dog

9
 Example 2

Subject Predicate Object

Jay respects Kay

Kay is next to Elle

Elle is taller than Jay

10
 Example 3

Direct Indirect
Subject Predicate
Object Object
Jay sold Elle to Kay

Kay bought Elle from Jay

Kay prefers Elle to Jay

11
 What is a Predicate?
A predicate is an "incomplete" expression –
i.e., an expression with one or more blanks –
such that,
whenever the blanks are filled by noun phrases,
the resulting expression is a sentence.

noun phrase1 predicate noun phrase2

sentence
12
 Compare with Connective
A connective is an "incomplete" expression –
i.e., an expression with one or more blanks –
such that,
whenever the blanks are filled by sentences,
the resulting expression is a sentence.

sentence1 connective sentence2

sentence3
13
 Examples

is tall

is taller than

recommends to

14
 Symbolization Convention
1. Predicates are symbolized by upper case letters.
2. Subjects are symbolized by lower case letters.
3. Predicates are placed first.
4. Subjects are placed second.

Pred sub1 sub2 …

15
 Examples

Jay is tall Tj

Kay is tall Tk

Jay is taller than Kay Tjk

Kay is taller than Elle Tke

Jay recommended Kay to Elle Rjke

Kay recommended Elle to Jay Rkej

16
 Compound Sentences - 1

Jay is not tall Tj

Jay is not taller than Kay Tjk

both Jay and Kay are tall Tj & Tk

neither Jay nor Kay is tall Tj & Tk

Jay is taller than both Kay and Elle Tjk & Tje

17
 Compound Sentences - 2
Jay and Kay are married (individually)
=
Jay is married, and Kay is married Mj & Mk

Jay and Kay are married (to each other) Mjk

and are married

18
 Quantifiers
Quantifiers are linguistic expressions denoting
quantity.

Examples
every, all, any, each, both, either
some, most, many, several, few
no, neither
at least one, at least two, etc.
at most one, at most two, etc.
exactly one, exactly two, etc.

19
 Quantifiers – 2
Quantifiers combine
common nouns and verb phrases
to form sentences.
predicate logic treats
Examples both common nouns
every senior is happy and verb phrases
as predicates
no freshman is happy
at least one junior is happy
few sophomores are happy
most graduates are happy

20
The Two Special Quantifiers
of Predicate Logic
English
official name symbol
expressions
universal
quantifier
every, any 
existential
quantifier
some, at least
one 

21
 Names of Symbols

 upside-down „A‟  backwards „E‟

Actually, they
are both
upside-down.

A E
22
How Traditional Logic Does Quantifiers

Quantifier Phrases are Simply Noun Phrases

every one is happy

some one is happy

Jay is happy

Kay is happy

subject predicate

23
How Modern Logic Does Quantifiers

Quantifier Phrases are

Sentential Adverbs

24
 Scope of Quantifiers
The part of a logical expression to which a quantifier is
applied is called the scope of this quantifier.

e.g., (x P(x))  (y Q(y))

e.g., (x P(x))  (x Q(x))

25
 Existential Quantifier
some one is happy
there is some one who is happy
there is some one such that he/she is happy
there is some x such that x is happy
x Hx
pronunciation
there is an x (such that) H x

26
 Universal Quantifier
every one is happy
every one is such that he/she is happy
whoever you are you are happy
no matter who you are you are happy
no matter who x is x is happy
x Hx
pronunciation
for any x H x

27
 Negating Quantifiers
modern logic takes „‟ to mean at least one
which means one or more
which means one, or two, or three, or …

if a (counting) number is not one or more

it must be zero

thus, the negation of „at least one‟

is „not at least one‟
which is „none‟
28
 Negative-Existential Quantifier
no one is happy
there is no one who is happy
there is no one such that he/she is happy
there is no x such that x is happy
there is not some x such that x is happy
x Hx
pronunciation
there is no x (such that) H x

29
 Negative-Universal Quantifier
not every one is happy
not every one is such that he/she is H
it is not true that whoever you are you are H
it is not true that no matter who you are you are H
it is not true that no matter who x is x is H
x Hx
pronunciation
not for any x H x

30
 Quantifying Negations - 1
suppose not everyone is happy xHx
then there is someone
who is

=
not happy
i.e., there is some x :
x is not happy xHx

the converse argument is also valid

31
 Quantifying Negations - 2
suppose no one is happy xHx
then no matter who you are
you are

=
not happy
i.e. no matter who x is
x is not happy xHx

the converse argument is also valid

32
Why is Predicate Logic Useful?

Verifying Program Correctness

Given
if (x<0) x = -x;
What is true before? (called precondition)
??
What is true after? (called postcondition)
greaterThan(x,0)
Systems Specifications
E.g., Every mail message larger than one megabyte
will be compressed.