Predicate Logic

#folder

Predicate logic is also known as first-order logic

Recall in Propositional Logic, we could only use T and F. In predicate logic, we can use other symbols such as . Predicate logic is often called "first-order logic" because we can quantify over values.

Predicate logic is an extension of propositional logic.

We want to:

Syntax

Definition

Untyped predicate logic consists of the following symbols:

  1. Alphabet
    • Constants (a, b, c, true, false, ...)
    • Variables (x, y, ...)
    • Function symbols
    • Predicate symbols
    • Logical connectives ()
    • Quantifiers ()
    • Functuation
    • Brackets
  2. Terms
    • Constants and variables are terms
    • Function "return" values are terms

$

logical connectives

Logical Connectives

Table

Symbols listed from highest to lowest precedence:

Symbol Informal meaning
negation
conjunction (and, both)
disjunction (or, one of)
implication
if and only if
Rules

Well-formed formulas of predicate logic are defined as follows:

  • Proposition symbols and constants are WFF (atomic formulas)
  • The result of a predicate symbol is a WFF (also atomic)
  • If and are WFFs, then each of the following are WFF:
  • If is a WFF and is a variable then is a WFF
  • If is a WFF and is a variable then is a WFF
Example

Are the following WFF in predicate logic?
are predicates, are variables, are functions, and are constants.


  1. Yes

  2. No

  3. Yes

  4. Yes

  5. No

  6. No

Semantics

See: Logic#Semantics

Unlike semantics in propositional logic, we have to deal with functions, quantifiers, etc. So we want to define a domain that we are dealing with.

This may seem like common sense, but remember:

Boolean Valuation

Example

Given a Domain = and:

Syntax Meaning
(see modular arithmetic 😭)

Find

solution

Tip

If you are ever given a set of formulas and asked to find an interpretation where a certain formula property holds, always start with the simplest formula and work your way to the more complicated ones

Validity

Definition

An argument is valid iff for all interpretations where the premises are T, the conclusion is T.

Environments

Info

There is a notation that is more well-known, but cumbersome for stating the meaning of a quantification. Instead of specifying our environments with curly braces like sets, we will just use a caret to denote the value of a domain value

We do not want to sub in the values directly to keep syntax and semantics distinct. That is, should only appear with [].

Example

Provide an interpretation in which the following formula has the truth value T, and demonstrate that the formula has this. Note is constant.

solution
Domain =

Syntax Meaning

Demonstration:

For SE212, you may skip the line labeled with (1) in this particular problem

Example - Nested Quantifiers

Find an interpretation in which the following formula is true:

solution
Domain =

Syntax Meaning

UHhhhh

Formula Properties

Very similar to Propositional Logic#Formula Properties

Satisfiability

Definition

A predicate logic formula is satisfiable iff there exists an interpretation where

Tautology

$

tautology

Tautology

The opposite of a contradiction is a tautology.

Definition

An assertion that is true in every interpretation

Example

  • is always true
  • is always true

Formula is a tautology iff for every interpretation

Note

We write when is a tautology

Contradiction

$

contradiction

Proof Method - Contradiction

Definition

Let be a statement. Note that either or must be false, so the compound statement is always false.

Example

  • " is true" is a contradiction
  • is always false

Formula is a contradiction iff for every interpretation

Consistency

Definition

A collection of closed predicate logic formulas is consistent iff there exists an interpretation in which all the formulas are

Example

Provide an interpretation that shows that the following set of formulas is consistent using the semantics of untyped predicate logic. is a constant.

solution
Remember to start with the simplest formula:

  • We know must always return false because the universal quantifier in formula 3 needs to hold true
  • From there, looking at formula 1, we see the left side of the iff is false, so the right side must also be false too. Due to the existential quantifier, we must make sure no value exists where is true
  • Formula 2 can be seen with the table afterwards

Domain =

Syntax Meaning

Counterexamples

Example

Show that is not valid

solution
Domain =

Syntax Meaning

Premise:

Conclusion:

Example

Show that is not a tautology.

solution
Domain =

Syntax Meaning
Example

Provide a counterexample for using Set Theory

solution
Domain =

Syntax Meaning

Typed Predicate Logic

Definition

A type is a set of possible values

Example

Person =
Then
Becomes
And hence we cannot make the claim that "a dead tree likes ice cream", since must be a person.

Remark

Since we have types, we don't care about predicates vs functions anymore.

Note

When doing proofs, we don't have to worry about the types. However, make sure you don't substitute the wrong type.

Axiom - Types as Sets

Syntax

Definition

Typed predicate logic consists of the following symbols:

  1. Alphabet (same as untyped, except with colon)
    • Constants (a, b, c, true, false, ...)
    • Variables (x, y, ...)
    • Function symbols
    • Predicate symbols
    • Logical connectives ()
    • Quantifiers ()
    • Functuation
    • Brackets
    • Colon
  2. Terms
    • Constants and variables are terms, and may be followed by a type
    • Function "return" values are terms
    • Logical connective expressions are terms
      • I.e if and are terms of type bool, then
    • A quantifier and variable attached to a term is term of type bool
      • Formally, if is a term of type bool and is a variable of type (and all free occurrences of in are still type ), then and are terms of type bool
Example

Are the following WFF in typed predicate logic?

  1. Yes
  2. No, expects as a param, but got
  3. No, expects as its first param, but got
  4. No, expects as its second param, but got
Remark

  • is the same as
  • is the same as

We can also write the following short forms:

Type Inference

Example

Are there types that make the following a WFF? If so, find the most general type.


  1. Write out each variable and function:Find which variables map to which functions (e.g takes the same type as for a parameter). Fill in the blanks.

  2. No, we can't have taking different number of arguments

Note that while we could just make everything one type, this wouldn't be the "most general" type. If we did that, then we would just use untyped predicate logic.

Semantics

Example

Find an interpretation in which:

is and demonstrate that your answer is correct.
Note:

solution
Domain:

Syntax Meaning