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:

• $S(x)$ - $x$ loves watching TV shows.
• $A(x)$ - $x$ loves watching anime.

We can then conveniently connect them to form new predicates:

• $S(x) \wedge \neg A(x)$ - $x$ loves watching TV shows but not anime.
• $A(x) \to S(x)$ - If $x$ loves anime, then $x$ must also like TV shows.

### Using Quantifiers

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

• $\exists x A$ - This is true if there is at least one $x$ so that $A$ holds. (existential quantifier)
• $\forall x A$ - This is true if for all possible value of $x$, $A$ holds. (universal quantifier)

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

• $\exists x (S(x) \wedge A(x))$ - There exists $x$ who likes TV shows and anime.
• $\forall x (A(x) \to S(x))$ - For all $x$, if $x$ likes anime, then $x$ must also like TV shows.

## Syntax of Predicate Logic

### First-order Languages

A first-order lanauge contains:

• Infinite set of variables.
• Set of predicate symbols.
• Set of constant symbols.

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

• A term of $L$ is a variable or a constant symbol.
• An atomic formula of $L$ is an expression of the form $A(t_1, t_2,…)$ ($A$ is a predicate symbol).

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:

• $\neg F_1$
• $(F_1 \wedge F_2)$
• $(F_1 \vee F_2)$
• $(F_1 \to F_2)$
• $(F_1 \iff F_2)$
• $\forall x F_1$
• $\exists x F_1$

### 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:

• $F = \neg F_1$. Then $free(F) = free(F_1)$.
• Connected using other propositonal connectives, then $free(F) = free(F_1) \cup free(F_2)$.
• $F = \exists x F_1$ or $F = \forall x F_1$. Then $free(F) = free(F_1) - \{x\}$.

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:

• A nonempty set $D$, called the domain of $S$.
• For each n-ary predicate symbol $A$ of $L$, an n-ary relation $A^S \subseteq D \times … \times D$.
• For each constant symbol $c$ of $L$, an element $c^S \in D$.

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$.

• $F = \neg F_1$ - $F$ is true if $F_1$ is false in $I$, false otherwise.
• $F = (F_1 \wedge F_2)$ - $F$ is true if $F_1$ and $F_2$ are both true in $I$, false otherwise.
• $F = (F_1 \vee F_2)$ - $F$ is true if at $F_1$ or $F_2$ is true in $I$, false otherwise.
• $F = (F_1 \to F_2)$ - $F$ is false if $F_1$ is true and $F_2$ is false, true otherwise.
• $F = (F_1 \iff F_2)$ - $F$ is true if $F_1$ and $F_2$ have the same truth value in $I$, false otherwise.
• $F = \forall x F_1$ - $F$ is true if $F_1$ is true in $(S, e|^x_v)$ for all $v$ in domain, false otherwise.
• $F = \exists x F_1$ - $F$ is true in $(S, e|^x_v)$ for some $v$ in domain, false otherwise.

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

• valid iff it is satisfied by every interpretation of $L$;
• satisfiable iff it is satisfied by some interpretation of $L$; and
• unsatisfiable iff it is not satisfied by any interpretation of $L$.

## 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

• $F$ logically implies $F’$ iff $F \to F’$ is valid.
• $F$ is logically equivalent to $F’$ iff $F \iff F’$ is valid.

## Important Logical Equivalences

• $\neg \forall x F \equiv \exists x \neg F$
• $\neg \exists x F \equiv \forall x \neg F$

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

• $E \wedge QxF \equiv Qx(E \wedge F)$, for any formulas $E, F$ and any variable $x$ that is not free in $E$.
• $E \vee QxF \equiv Qx(E \vee F)$, for any formulas $E, F$ and any variable $x$ that is not free in $E$.

• $QxE \to F \equiv Q’x(E \to F)$, for any formulas $E, F$ and any variable $x$ that is not free in $F$.

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