Predicate Logic

Predicate LogicIntroductionTerminologyTermPredicateQuantifierWFF (of First-Order Logic)WFFNotation: Seven Kinds of SymbolsApplication: Parse TreeFree and Bound VariablesApplication: Determining Free or Bound using Parse TreeSubstitutionMotivationFormal DefinitionInterpretationsValues of Variable-Free TermsTotal FunctionsValues of Formulas Containing Only Variable-Free TermsEnvironmentsMeaning of TermsQuantified FormulasValues of Quantified FormulasValidity and SatisfiabilityExercise: Give an Interpretation and an environment such that ...Overall RemarksSemantic EntailmentRelevance LemmaSemantic EntailmentExercise: Semantic EntailmentNatural DeductionTrivial: Forall-eliminationTrivial: Exists-introductionChallenging: Forall-introduction Challenging: Exists-elimination



Predicate logic generalizes propositional logic with the following new things:



Definition. A term is defined inductively as:



Definition. A predicate represents a property of an object or a relation among multiple objects.

Remark. We can think of a predicate as a function mapping from into .




WFF (of First-Order Logic)


Definition. The set of well-formed formulas of first-order logic is inductively defined as follows:


Notation: Seven Kinds of Symbols

Remarks. Function symbols and predicate symbols have assigned arities.


Application: Parse Tree


Free and Bound Variables

Definition. There are two types of variables in a formula:



Application: Determining Free or Bound using Parse Tree

To determine whether a variable is free or bound, we can use a parse tree:



Definition. For a variable , a term , and a formula , denotes the resulting formula by replacing each free occurrence of variable in formula with term .

Remark. Subsitution does NOT affect bound occurrences of a variable.



Formal Definition

Definition. Let be a variable and a term.

For a term , the term is with each occurrence of replaced by .

For a formula ,

  1. If is a predicate, recursively substitute each with .

  1. If can be splitted into other formulas, recursively apply rule 1.

  1. If is bounded in , then substituting into does nothing.

  1. If contains no bounded variable, leave the quantifier alone and do substituion.

  1. If contains a bounded variable, we need to find a new variable with no name clash and do the substitution.



, then is?


Definition. Fix a set of constant symbols, function symbols, variable symbols and predicate symbols. An interpretation for the set consists of


Values of Variable-Free Terms

Definition. Fix an interpretation . For each term containing no variables (only constants), the value of under interpretation , denoted , is as follows:

Remark. The value of a term is always a member of the domain of .


Total Functions

Motivation. Recall that your function's interpretation must be defined on the entire domain. That is, for a function with arity , we need to define an interpretation such that the function satisfies

Definition. Functions capable of doing this (that is, the result is in domain) are called total functions.

Example. Let . The addition function is a total function since the sum of any two natural numbers gives another natural number. However, the subtraction function is not, as .


Values of Formulas Containing Only Variable-Free Terms

Definition. Fix an interpretation . For each formula containing no variables, the value of under interpretation , denoted , is as follows:

Remark. simply means evaluates to True under the interpretation .


Definition. An environment is a function that assigns a value in the domain to every variable symbol in the language.


Meaning of Terms

Principle. The combination of an interpretation and an environment supplies a meaning (value) for every term.

Definition. Fix an interpretation and an environment . For each term , the value of under and , dentoed , is as follows:

Example. Let be where is a constant and let be where is a variable. Let be the interpretation with domain , and . Then but is undefined. To give a value, we must also specify an environment . For example, if (inside this environment has value ), then .


Quantified Formulas

Definition. For any environment and domain element , the environment " with maps to ", denoted , is given by

In other words, and for any other variable , .

Remark. is a new environment!

Example. Let for some and such that . Then .


Values of Quantified Formulas

Definition. The values of and are given by

Remark. The values of and do not depend on the values of ; only matters for free occurrences of but nontheless environments must be specified for all variables.


Validity and Satisfiability

Definition. A formula is

Remark. The term "tautology" is not used in predicate logic.

Remark. If there is no need to specify an environment, then simply defining an interpretation and writing will suffice.

Remark. To show a formula is valid or unsatisfiable, start with "let be an arbitrary interpretation and be an arbitrary environment", then show that (for valid) and (for unsatisfiable); to show a formula is satisfiable, give examples of being true under some and false under some .


Exercise: Give an Interpretation and an environment such that ...


  1. Define the domain.
  2. Map each constant to a domain element.
  3. Give each function a meaning.
  4. Give each predicate a meaning.
  5. Map each variable to a domain element.

Now use reduction to show the statement holds.


Example I. (with variables but no quantifier): Consider this language of predicate logic:

Give an interpretation and environment such that .

Solution I:


Example II: Use the same language as above, give an interpretation and environment such that .

Remark II: is free so its value is given by the environment; even though and do not appear in the formula, we need to define their mapping as part of . To make the statement true, there must be at least one tuple in the set of with second element being .

Solution II:


Overall Remarks
  1. The constants get their meaning through and the variables through .

  2. Map every constant to a domain element in and every variable to a domain element in , even if some of them do not appear in the formula.

  3. The function and predicate must be able to every possible domain elements (or combinations of domain element, in the case its arity is greater than one).

  4. To show , show that ; LHS gets its value from only if there is no free variable.

  5. Use the satisfaction rules precisely

Semantic Entailment

Relevance Lemma

Lemma. Let be a well-formed predicate formula, be an interpretation, and be two environments such that for every that occurs free in . Then if and only if .


Semantic Entailment

Let be a set of well-formed predicate logic formulas and is a well-formed predicate logic formula. For an interpretation and an environment , we write if and only if for every , we have that .

Definition. We say that semantically entails , written as , if and only if for any interpretation and environment , we have implies . This can also be written as .

Remark. means that is valid (recall how we interpret this in propositional logic).

Notes. Suppose . Then means

Thus, to prove these, take an arbitrary interpretation and environment and show that if this satisified then it must also satisfy . You may also assume towards a contradiction that and proceed from there. To prove