FOL - first order logic

Names

(a-r) 

• Specific names of people, places, things 

• Always lowercase letters from a-r 

Names ex:

Ex: 

e- Tweety 

l- Sylvester 

In FOL every name has to pick out a single individual (person, thing, etc) 

• Can't pick out/represent more than one thing 
  

Predicates

 (A-Z and s-z)

• A sentence with one or more blanks that would become a full sentence if those blanks were filled with names.

• The part of the sentence describing the subject 
  

Ex: Mr. Morton walked down the street. 

Predicates ex

— is a bird. 

— has feathers.

A cat is chasing -–.

B(x):___x is a bird.

F(x):___x has feathers 

C(x): A cat is chasing_____x

R(x,y)

• ______x is chasing _____y

• can use any letter instead of R (A-Z) 

Sentence ex

Name:

m: Mr.Morton 

Predicate: 

W(x): ______x walked down the street

• Can be A- Z in capital letters

•  and s-z in lowercase letters- in parentheses

• Need to know where the different letters/predicates go to- that's what the little x , or s-z is for 

If you have a predicate and name, you should fill it with the name/subject 

• (a,r) 

r: Rhea

S()- is shopping

S(r) : Rhea is shopping

Otherwise, if it isn't filled in with a name

• Use s-z

S(z) : _____z is shopping

a-r : names- will always name something

A-Z: predicates

s-z: variables - will never name anything, variable

• There should either be a name or a variable in a predicate

Full sentences vs not full sentences 

When you have a predicate and a variable- not a full sentence 

Only when you put a name in there it becomes a full sentence 

B(y)

• Not a sentence 

• Only has a predicate and a variable 

• Says  ___y is a bird 

B(l)

- full sentence 

- Has a name and a predicate 

- says Sylvester is a bird 

full sentence vs non full sentence

F(z) - _____x has feathers 

(F)e - Tweety has feathers 

 Sylvester is a bird 

  B(l)

Sylvester and Tweety have feathers

 F(l) ∧ F(e)

If a cat is chasing Tweety, then Sylvester is a bird

- C(e) → B(l) 

- can do brackets on the outside, but they are optional

If Sylvester and Tweety have feathers , then a cat is chasing Tweety. 

- [F(l) ∧ F(e)] → C(e)

If you have a two place predicate, you have to fill it with 2 

• With a one place predicate put 1 

R(x,y) 

_____x is rubbing _____y

R(x,y) 

_____x is rubbing _____y

R(e,l) 

Tweety is rubbing Sylvester 

R(x,y) 

_____x is rubbing _____y

R(e,e) 

Tweety is rubbing Tweety 

R(x,y) 

_____x is rubbing _____y

F(l) F(e)

• Not a well formed sentence of FOL 

Universal Quantifier - (∀)

For all ____, ____ is ____ 

• Represents everything 

∀x B(x) 

Variables (s-z) 

“For all x, x is a bird.” 

• Says everything is a bird, so if you put anything in x- it will be a bird

• You can substitute anything for x and that thing will be B- a bird 

∀x ¬B (x) 

“For all x, x is not a bird.”

• Everything is a not bird 

• For all x, it's not the case that x is a bird 

“All things have feathers”

∀x F (x) 

∀y F (y) 

Variables (s-z)

• Anything from s-z

• Just placeholders that tell you what a thing is quantifying

Existential quantifier (Ǝ) 
Ǝ(x)

-Represents something 

• at least one thing 

Something has feathers

Ǝx F(x) 

“There is some x such that x has feathers”

F(l) V F(e) 

- also represents that something has feathers

- at least one, tweety or sylvester

- but there will most times be more than 2 things or variables, so the V is not sustainable 

 Ǝx  -F(x)

There is something that does not have feathers 

• There is some x such that x does not have feathers 

-∀ x F(x)

• There is something that does not have feathers 

• It is not the case the for all x, x has feathers 

  • some can have feathers though

Nothing is a bird 

∀x -B(x)

• All things are not birds 

• For all X it is not the case that X is a bird

Nothing is a bird 

-Ǝx B(x) 

• It is not true that at least one thing is a bird 

• It is not the case that some such x is a bird 

Not everything is a bird 

-∀x B(x) 

- says everything is a bird, then negates it 

- It is not the case that for all x, x is a bird 

- it's not true that everything is a bird

Not everything is a bird 

Ǝx -B(x)

- there is something that is not a bird 

- Some such x is not bird 

- at least one x is not a bird 

Everyone

depends on the domain, relative 

• Everyone is happy - the students in the room are happy 

• Only describing the students in the room 

Domain 

• A domain must have at least one member. Every name must pick out exactly one member of the domain, but a member of the domain may be picked out by one name, many names, or none at all. 

Domain: animals in the pet store 

Ǝx -F(x)

• There is some x such that x does not have feathers in the pet store 

• There is at least one animal in the pet store that has no feathers 

• (there is an animal with no feathers in the pet store) 

• It used to say that there is something that has feathers, but it changes depending on the domain 

 ∀x -B(x)

For all x in the pet store it is not the case X is a bird/X is not a bird 

All the animals in the pet store are non birds 

• None of the animals in the pet store are birds 

• There are no birds in the petstore 

Domain: all animals (or all animals in the pet store) 

P(x): ____x is in the display case 

B(x): ____x is in the back if the store 

D(x): ____x is a dog 

C(x): ____x is a cat 

Domain: all animals (or all animals in the pet store) 

P(x): ____x is in the display case 

B(x): ____x is in the back if the store 

D(x): ____x is a dog 

C(x): ____x is a cat 

Domain: all animals (or all animals in the pet store) 

P(x): ____x is in the display case 

B(x): ____x is in the back if the store 

D(x): ____x is a dog 

C(x): ____x is a cat 

Domain: all animals (or all animals in the pet store) 

P(x): ____x is in the display case 

B(x): ____x is in the back if the store 

D(x): ____x is a dog 

C(x): ____x is a cat 

 All the animals in the display case are dogs 

∀x (P(x) → D(x) )

All animals in the display case are dogs 

• Forall x if its in a display case, then it's a dog 

• If it has the property of being a P- in the display case, then it's a dog

A sentence can be symbolized as ∀x (F(x) → G(x) ) it can be paraphrased in English as ‘every F is G’

If you see: Every F is G 

Then symbolize :  ∀x (F(x) → G (x)) 

• For all F is x then G is x 

In the universal ∀x we will use

conditional most times 

• Want to say all of these things are also those things 

• You can also use a conjunction 

Domain: all animals (or all animals in the pet store) 

P(x): ____x is in the display case 

B(x): ____x is in the back if the store 

D(x): ____x is a dog 

C(x): ____x is a cat 

Some animal in the back of the store is a cat 

• Has 2 properties 

  • Is in the back of the store

  • Is a cat

Ǝx (B(x) ⋀ C(x))

• Says there is something in the domain that satisfies both sentences B and C  

• At least one thing x , is in the back of the store and is a cat

A sentence that can be symbolized Ǝx (F(x) ∧ G(x)) can be paraphrased as “some F is G” in English 

• Some thing is F and G

Do not use  → (conditionals) with Ǝ (existential quantifier) 

-Ǝx (B(x) → C(x))

Not correct

Do not use  → (conditionals) with Ǝ (existential quantifier) 

-Ǝx (B(x) → C(x))

Not correct

• Says there is not at least one thing in the domain that satisfies the conditional 

• Made true if there is at least one cat 

• True if there is a single cat - one cat 

• Made true by the very existence of a cat 

• True if there is something that is not in the back of the store, conditional is also true 

True if the antecedent is true and consequent is false- 

You will never use conditionals with Ǝ existentials because it is too easy for the conditional to be true

• Generally -Ǝ existentials go with conjunctions 

Domain: all animals (or all animals in the pet store) 

P(x): ____x is in the display case 

B(x): ____x is in the back if the store 

D(x): ____x is a dog 

C(x): ____x is a cat 

 None of the animals in the display case are cats.

All things- if they are in the display case, then they are not cats

• ∀x (P(x) → -C(x) )

There is not one thing that is in the back of the display case, and a cat 

• -Ǝx (P(x) ⋀ -C(x))

A sentence that can be paraphrased as “no F is G” can be symbolized as Ǝx (F(x) ∧ G(x)) and also ∀x (F(x) → -G(x) ). 

P(x): ____x is in the display case 

B(x): ____x is in the back if the store 

D(x): ____x is a dog 

C(x): ____x is a cat 

Only cats are in the back of the store

For everything if it's in the back of the store, it is a cat

• ∀x(B(x)→ C(x))

There is no thing that is in the back of the store its a non cat 

No thing in the back of the store is not a cat 

-Ǝx(B(x) ∧ -C(x))

When Ǝx is negated it means there's NO thing

 Ǝx- at least one thing 

 -Ǝx- no thing 

A sentence that can be paraphrased as “only Fs are Gs” can be symbolized as -Ǝx(G(x) ∧-F(x)) and also as ∀x(G(x)→ F(x))

P(x): ____x is in the display case 

B(x): ____x is in the back if the store 

D(x): ____x is a dog 

C(x): ____x is a cat 

Some animal in the display case is not a dog 

Some animal is in the display case, and is not a dog 

• Ǝx(P(x) -D(x))

Not every animal, if in the display case is a dog 

• -∀x(P(x)→ D(x))

A sentence that can be paraphrased as “some Fs are not Gs” can be symbolized as Ǝx (F(x) ∧-G(x)) and also -∀x(F(x)→G(x)).

All Fs are Gs - different than only Fs are Gs

Empty predicate 

A(x):____x is an ape

D(x):---______x will make the dean’s list 

All apes will make the dean’s list 

∀x (A(x)→D(x))

• For everything x, if it's an ape it makes the dean’s list 

• It is true because there are no apes, so it is possible that they can make the dean's list 

• Vacuously true, because one of the premises are not true 

When F is an empty predicate, (doesn’t have a name) any sentence ∀x (F(x)→….) is vacuously true. 

Therefore, ∀x (A(x)→D(x)) does not entail Ǝx (A(x) D(x))

For everything that's an ape, it will make the dean's list, does not entail  at least one thing is an ape and has made the dean's list. 

Counterintuitive to have empty predicates 

A(s)→D(s)

• Conditional with blank- true for every single x no matter what name you stick in it 

• If it will always be true 

Conditional/consequent has to be false and antecedent is true 

• Antecedent  is always false bc its vacuous

Domain: Rutgers students 

A(x):____x is an ape

D(x):---______x will make the dean’s list 

All apes will make the dean’s list

No matter who you put antecedent will always be false- so conditional/overall sentence is true 

If jay is an ape, then jay is on the dean's list 

It is false that jay is an ape, so the conditional is true 

• The conditional is always true when antecedent is false 

When F is an empty predicate 

Any form where F comes after universal will be vacuously true 

The Scope of Quantifiers 
Domain: all people 

S(x):_____x is suffering 

p: Peter

m: Mary 

∀x S(x) →S(p)

If all people are suffering, then Peter is suffering

Scope is just antecedent 

• Splits   ∀x S(x) - for all people suffering, and peter suffering 

• Because he is in the domain

Domain: all people 

S(x):_____x is suffering 

p: Peter

m: Mary 

∀x S(x) →S(p)

If all people are suffering, then Peter is suffering 

If everyone is suffering, Peter is suffering 

• Scope only connects them, but also splits every person and peter 

Domain: all people 

S(x):_____x is suffering 

p: Peter

m: Mary 

∀x (S(x) →S(p))

Take every single thing in domain- if it is suffering, Peter is suffering 

(If something is suffering, peter is suffering) 

• If a person is suffering, then peter is suffering (applies to all people/everything in the domain 

Every person such that, If they are suffering Peter is suffering

When you put parentheses around sentence/before quantifier- it's like negation

• Scope is the entire thing 

When you put parentheses around sentence/before quantifier- it's like negation

• Scope is the entire thing 

∀x (S(x) →S(p))