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 booleanvalued 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 nary 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
Firstorder Languages
A firstorder 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 firstorder formulas.
Firstorder 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 firstorder 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 nary 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 (firstorder formulas).
Note that if we are just given a firstorder 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 firstorder language. A structure $S$ for $L$ contains:
 A nonempty set $D$, called the domain of $S$.
 For each nary predicate symbol $A$ of $L$, an nary 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 firstorder 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 nary 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 firstorder 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’$.