Notes taken for CSCB36 course at UofT, this post is for Chapter 6, Predicate Logic.

Overview

Predicate logic is a generalisation of propositional logic.

A predicate is a boolean-valued function. The set $D$ of possible values for a predicate’s arguments is called its domain of discourse. The number $n$ of a predicate’s arguments is called it arity. So a n-ary predicate with domain of discourse $D$ is the function: $P: D \times D \times … \times D \to \{0,1\}$.

Combining Predicates

Using Propositional Connectives

We can use propositional connectives to combine predicates, for example:

We can then conveniently connect them to form new predicates:

Using Quantifiers

We can also use quantifiers, there are 2 main ones:

Take from above example, we can construct the following predicates:

Syntax of Predicate Logic

First-order Languages

A first-order lanauge contains:

All symbols within the language, alongside with connectives, quantifiers, parentheses and comma constitute the basic vocabulary of first-order formulas.

First-order language with equality is just the language that includes $\approx$ predicate symbol.

Formulas

Definition: The set of first-order formulate of $L$ is the smallest set such that:

Basis: Any atomic formula is in the set.

Induction Step: If $F_1$ and $F_2$ are in the set, and $x$ is a variable of $L$ then the following are also in the set:

Note When Omitting Parentheses

When omitting parentheses for quantifiers, they only apply to the formula right after it.

For example: $\exists x A \wedge B$ is the same as $(\exists A) \wedge B$.

Free Variables

Free variables are all the variables that is not immidiately followed by a quantifier. Say $\exists y A(x, y)$, in this case $x$ is a free variable.

The definition of a function called $free(F)$ to compute all free variables in a formula is the following.

Definition:

Basis: $F$ is an atomic formula, say $A(t_1, t_2,…)$, $A$ is an n-ary connective. In this case, $free(F)$ is the set of terms $t_1, 1 \leq i \leq n$.

Induction Step: $F$ is not an atomic formula. Then $F$ must be constructed from one or two formulas $F_1, F_2$ using a propositional connective or a quantifier. Assume that we have determined the set of free variables of $F_1$ and $F_2$. The set of free variables of $F$ are as follows:

Definition: An occurrence of variable $x$ is free in $F$ iff it does not occur within a subformula of $F$ of the form $\forall x E$ or $\exists x E$.

If a formula $F$ has no free variables, then it is called a sentence.

If we write out the tree representation, occurrence of variable $x$ is only free if the path to the root contains no $\forall x$ or $\exists x$.

Predicate Logic Semantics

For propositional logic, we cannot determine the truth value of a formula unless we did truth assignment. However it is more complicated for predicate logic (first-order formulas).

Note that if we are just given a first-order formula, it doesn’t really have a meaning. For example $\exists y (A(x,y) \wedge B(c, y) \wedge C(y))$ where $c$ is a constant.

We must know the domain, meaning of each predicate and the contant to parse the meaning of this formula.

Structures, Valuations and Interpretations

Definition: Let $L$ be a first-order language. A structure $S$ for $L$ contains:

Definition: Given a structure $S$ for $L$, a valuation of $S$ is a function that maps each variable of $L$ to some element of the structure’s domain $D$.

Definition: An interpretation $I$ of $L$ is a pair $(S, e)$, where $S$ is the structure and $e$ is the valuation.

Truth Value of a Formula

Definition: Let $L$ be a first-order language and $S$ be a structure for $L$. The truth value of a formula $F$ in $L$ in interpretation $I = (S, e)$, for any valuation $e$ of $S$ is defined as follows.

Basis: $F$ is an atomic formula, say $F = A(t_1, …., t_n)$, where $A$ is an n-ary predicate symbol of $L$ and each $t_i$ is a term of $L$. In this case, $F$ is true in $(S, e)$ if $(t^I_i,… t^I_n) \in A^S$ and is false otherwise.

Induction Step: $F$ is not an atomic formula. Then $F$ is constructed from one or two formulas $F_1, F_2$, using propositional connective or a quantifier. Assume, by induction, that we have determined the truth value for $F_1$ and $F_2$.

Variables not free in a formula does not affect its truth value.

Validity and Satisfiability

Definition: Let $F$ be a formula of the first-order language $L$. $F$ is

Logical Implication and Logical Equivalence

Definition: A formula $F$ logically implies formula $F’$ iff every interpretation that satisfies $F$ also satisfied $F’$.

Definition: A formula $F$ is logically equivalent to formula $F’$ iff each interpretation either satisfies both or falsifies both.

Theorm: Note that

Important Logical Equivalences

$Q$ is just generic quantifier, $Q’$ is the other one.

For all other connectives, you can also do similar things, but do not change $Q$ to $Q’$.