Formalizing Predicate Logic

Predicate

Definition

A predicate is a symbol denoting an T/F attribute (property) of a value or the relationship between multiple values

We call a predicate that takes a single value a unary predicate, two values a binary predicate and values a -ary predicate.

Examples

  • Billy is a child
    • "Billy" is a value
    • "child" is a attribute of Billy
  • Billy likes ice cream
    • "Billy" is a value
    • "likes" is a relation (predicate)
    • "ice cream" is the value Billy likes
  • 10 is greater than 5
    • "10" and "5" are values
    • is an "infix predicate"
  • Barbara plays the piano
    • "Barbara" is a value, "plays" is a binary predicate, "piano" is a value
    • plays(x, y) means x plays y
    • plays(Barbara, Piano)

Quantifiers

$

quantifier

Quantifier and Quantified Statements

Open Sentence

Definition

A sentence that contains a variable, where the truth of the sentence is determined by the value of the variable chosen from the domain of the variable

Quantified Statement

Definition

  1. A universally quantified statement is of the form
    • Read as "For all in , is true"
  2. An existentially quantified statement is of the form
    • Read as "There exists (at least one) value of in for which is true"

Negation of Quantifiers

Definition

Quantified Statement Negation

Nested Quantifiers

Important - Order matters

Where is false, is true.

Important - Domain matters

where is true (), is false.

Scope of Quantifiers

Info

Quantifiers will cover the entire scope they are in

Example

Examples

  1. Something is rotten in the state of Denmark

& \exists x \cdot \op{rotten}(x) \land \op{inDenmark}(x) \
& \exists x \cdot \op{rotten}(x) \land \op{in}(x, \text{Denmark}) \
& \exists x \cdot \op{rotten}(x, \text{Denmark}) && \text{where } \op{rotten} (a, b) \text{ means} \
&&& a \text{ is rotten in } b
\end

  1. Someone is happy or hungry
    $$\exists x \cdot \op{happy}(x) \lor \op{hungry}(x)$$
  2. Every child likes Mickey Mouse

Remember to give meanings to each predicate

Example

means is a bicycle, means is in the garage

All bicycles are in the garage

Some bicycles are in the garage

All things are bicycles in the garage

Everything is a bicycle or is in the garage

Something is a bicycle or is in the garage

Be careful, is a very weak statement.

Nested Quantifiers

Example

  1. Everything doesn't like something
  2. Nothing likes everythingAre equivalent.

Example - Order Matters

Binding of variables:

where means is older than

The meaning is not the same.

Functions

Question

How would we formalize "Mary's age is less than 20"?

where means b's age is a.

But this means Mary could have multiple ages.

Info

We can use functions to establish that there is only 1 value.

Example

  1. Eunsuk was born north of Toronto
  2. For all , if "input" has the value , then "output" has the value squared.

Formalizing English Sentences

Steps

Reasonable order to formalize:

  1. Connectives
  2. Quantifiers
  3. Constants
  4. Functions
  5. Predicates
Important

For SE212 (and in general), remember to give the predicates and functions meaning on assignments and exams. For brevity, meanings have been omitted since they are self-evident.

Example

Formalize:

All students who like software engineering also like logic

solution

You could formalize this as:

Which is logically equivalent.

Where:

  • means is a student
  • means likes

Typed predicate logic:

Example

Formalize:

All rich actors collect some valuables

solution

Typed predicate logic:

Example

Formalize:

Not everyone who lives in Louisiana speaks French, but everyone who lives in Louisiana knows someone who lives in Louisiana who speaks French

solution

  • Not everyone who lives in Louisiana speaks French
  • But
  • Everyone who lives in Louisiana knows someone who lives in Louisiana who speaks French
Example

Formalize:

Every house has at least one child under the age of 10 living in it has at least two different sizes of pumpkins

in typed predicate logic.

solution

where:

  • means lives in
  • means the age of
  • means has
  • means the size of

Selective Formalization

If asked to formalize sentences for an argument, and then to prove that the argument is valid, we can choose what we want to formalize based on what we wish to prove.

Steps

  • For all sentences (premises and conclusion):
    1. Pick the smallest phrases without connectives that you can answer "is it true or false" to
    2. Identify all possible logical connectives
    3. Identify what might be quantified, implicit quantifiers, and constants
    4. Identify possible predicates and functions. The quantified variables must be arguments to the predicates
    5. Look for similar phrases and determine how much detail needs to be provided (how much information can one predicate/function capture)
    6. Think of an outline for the proof