Propositional Logic (PL)

Syntax

The syntax of a language specifies its well-formed expressions, which can be grouped into categories (like terms and formulas in FOL). The language of PL only contains one category: formulas or sentences.

sentences are expressions which can be assigned a truth value. formulas and sentences are the same in PL.

propositional formulas are built from propositional(sentential) letters, connectives, like $\neg, \land, \lor, \rightarrow$, and parentheses. It is inductively defined as :

1. Propositional letters are formulas.
2. if $\phi$ is a formula, then $\neg \phi$ is a formula.
3. if $\phi$ and $\psi$ are formulas, then $(\phi \land \psi)$, $(\phi \lor \psi)$, $(\phi \rightarrow \psi)$, $(\phi \leftrightarrow \psi)$ are formulas.
4. Nothing else is a formula

Or in BNF form:

$$\phi := p | \neg \phi | (\phi \land \psi)| (\phi \lor \psi)| (\phi \rightarrow \psi)| (\phi \leftrightarrow \psi)$$

where p belongs to a certain vocabulary (a vocabulary is a given set of prop. letters).

Variants:

1. It is possible to have smaller set of primitive connectives, for example $\neg$ and $\lor$.
2. $\bot$ can be used as a primitive logical sentence symbol. It's not a prop. letter but a 0-ary connective standing for a contradiction.

An atomic formula is either a prop. letter, or $\bot$ if defined.

Inductive definitions

To prove that all formulas have property P, show this:

• (base) atomic formulas are P.
• (induction steps)
• if $\phi$ is P, then $\neg \phi$ is P.
• if $\phi$ and $\psi$ are P, then $(\phi \land \psi)$, $(\phi \lor \psi)$, $(\phi \rightarrow \psi)$, $(\phi \leftrightarrow \psi)$ are P.

Normal forms

• negation normal form
• disjunctive normal form, dnf
• conjunctive normal form, cnf

Normal forms can be obtained by using logical equivalences and substitution theorem. See the section below.

Semantics

A semantics for a language gives truth conditions for its sentences. The truth value of a sentence in PL depends on truth values of the prop. letters occurring in it. There are two truth values: 1/True and 0/False.

An interpretation/valuation maps prop. letters to truth values. By means of truth tables, given a valuation V, every formula gets a truth value. For any valuation V and formula $\phi$, define the relation $V \vDash \phi$ as:

1. $V \vDash \phi$ iff V(p) = 1 for p in L
2. $V \vDash \neg \phi$ iff $V \nvDash \phi$
3. $V \vDash \phi \land \psi$ iff $V \vDash \phi$ and $V \vDash \psi$
4. $V \vDash \phi \lor \psi$ iff $V \vDash \phi$ or $V \vDash \psi$
5. $V \vDash \phi \rightarrow \psi$ iff $V \nvDash \phi$ or $V \vDash \psi$
6. $V \vDash \phi \leftrightarrow \psi$ iff $V \vDash \phi$ and $V \vDash \psi$, or $V \nvDash \phi$ and $V \nvDash \psi$

Locality Lemma for PL

If V and V' agree on the prop. letters in $\phi$, $V \vDash \phi$ iff $V' \vDash \phi$.

proved by induction.

Logic consequence

Let $\phi$ be a sentence and $\Gamma$ a set of sentences. $\phi$ is a logical consequence of $\Gamma$, or $\Gamma \vDash \phi$, iff for all V, $V \vDash \Gamma$ implies $V \vDash \phi$.

$\Gamma$ can be infinite.

Related notions

• $\phi$ is logically true (a tautology in PL) or $\vDash \phi$ if $\phi$ is true in every valuation.
• $\phi$ and $\psi$ are logically equivalent, in symbols $\phi = \psi$, if $\phi$ and $\psi$ are true in the same valuation.
• $\Gamma$ is satisfiable if there is a valuation V s.t. all sentences in $\Gamma$ are true in V.

Each of these four logical concepts can be defined in terms of each of the others. For example:

• logical truth can be defined as $\emptyset \vDash \phi$.
• Logical consequence can be defined in terms of satisfiability:

$\Gamma \vDash \phi$ iff $\Gamma \cup {\neg \phi}$ is not satisfiable

Useful equivalences

• de Morgan's laws
• double negation
• excluded middle
• definitions of $\neg, \land, \lor, \rightarrow$ in terms of other connectives.
• distributive laws

Truth function

An n-ary truth function is a function from ${{0,1}}^n$ to {0, 1}.

PL is truthfunctionally complete, that is

Every n-ary truth function can be expressed by a PL formula

Substitution Theorem

Let $\phi[p]$ indicate that $\phi$ may have some occurrences of p, and $\phi[\psi]$ result from replacing these occurrences by $\psi$.

We have:

if $V(\psi) = V(\psi ')$, then $V(\phi[\psi]) = V(\phi[\psi '])$

and a corollary:

if $\psi = \psi '$, then $\phi[\psi] = \phi[\psi ']$

Proof:

induction on $\phi$.

• (base)
$\phi$ is an atom. If it is not p, then obviously $V(q[\psi]) = V(q) = V(q[\psi '])$. If it is p, then$V(p[\psi]) = V(\psi) = V(\psi ') = V(p[\psi '])$
• (ind.) $\phi$ is $\neg \theta$. then:

$V((\neg \theta)[\psi]) = 1$
iff $V(\neg \theta[\psi]) = 1$
iff $V(\theta[\psi]) = 0$ (truth def.)
iff $V(\theta[\psi ']) = 0$ (ind. hyp.)
iff $V(\neg \theta[\psi ']) = 1$ (truth def.)
iff $V((\neg \theta)[\psi ']) = 1$

• (ind.) $\phi$ is $\theta_1 \land \theta_2$. then:

$V((\theta_1 \land \theta_2)[\psi]) = 1$ iff
$V(\theta_1[\psi] \land \theta_2[\psi]) = 1$ iff
$V(\theta_1[\psi]) = V(\theta_2[\psi]) = 1$ iff
$V(\theta_1[\psi ']) = V(\theta_2[\psi ']) = 1$ iff
$V(\theta_1[\psi' ] \land \theta_2[\psi ']) = 1$ iff
$V((\theta_1 \land \theta_2)[\psi ']) = 1$

First-Order Logic

Syntax

A vocabulary L in FOL is a set of non-logical symbols, including individual constants, n-ary predicate symbols and n-ary function symbols.

Terms

Terms are expressions that stand for individuals. Let L be a vocabulary, the set of L-terms is defined as:

1. A variable is an L-term
2. A individual constant in L is an L-term.
3. If f is an n-ary function symbol in L and t1, ... tn are L-terms, then ft1 ... tn is an L-term.

An L-term is open if it contains at least one variable, otherwise it is closed.

Formulas

If P is an n-ary predicate and t1 ... tn are L-terms, then Pt1...tn is an atomic L-formula.

Identity is a fixed 2-ary predicate "=".

The logical symbols of FOL are connectives, identity and quantifier symbols $\forall, \exists$. A subset can be chosen, but if identity is dropped then expressive power is significantly decreased.

Definition of L-formulas:

1. Atomic L-formulas are L-formulas
2. if $\phi$ and $\psi$ are L-formulas, then $\neg \phi$, $(\phi \land \psi)$, $(\phi \lor \psi)$, $(\phi \rightarrow \psi)$, $(\phi \leftrightarrow \psi)$ are L-formulas.
3. if $\psi$ is an L-formula and x is a variable, then $\forall x \psi$ and $\exists x \psi$ are also L-formulas.

Sentences

An occurrence of x in a formula $\phi$ is free if it is not within the scope of any quantifier expressions $\forall x$ or $\exists x$. Otherwise, it is bound.

If x is bound in $\phi$, it is bound by the occurrence of $\forall x$ or $\exists x$ with the smallest scope where this x occurs.

An L-formula is a sentence if no variable occur free in it.

Substitution

$\phi(x_1/t_1,...,x_n/t_n)$ stands for the result of simultaneously replacing all free occurrence of x1 ... xn by t1, ... tn.

Note: t is free for x in $\phi$ if no free occurrence of x is within the scope of a quantifier $\forall y$ or $\exists y$ in $\phi$, for any variable y in t. Only replacing such an occurrence of x with t is permitted.

Translation into FOL

To translate or formalize natural language sentences into FOL sentences, first identify words translatable as individual constants and predicate symbols, and then quantified expressions.

Two rules of thumb:

• Universally quantified "All As are B":

$$\forall x (Ax \rightarrow Bx)$$

• Existentially quantified "Some As are B"

$$\exists x (Ax \land Bx)$$

donkey sentence: If a farmer owns a donkey he loves it.

Semantics

Interpretations/Models

An Interpretation for a vocabulary L is a pair (M, I). M is a non-empty set ( the domain or universe) and I assigns suitable values to the symbols in L.

1. if c $\in$ L, then I(c) is an element of domain M
2. if P is an n-ary predicate symbol in L, then I(P) is an n-ary relation over M
3. if f is an n-ary function symbol in L, then I(f) is an n-ary function on M

Assignments and Satisfaction

An assignment in M is a function $\sigma$ from the set Var of all variables to M.

The value of term t in M, relative to assignment $\sigma$, written $t^{M, [\sigma]}$, is defined as:

• if t is a constant c, then $t^{M, [\sigma]}$ = $c^M$
• it t is a variable x, then $t^{M, [\sigma]}$ = $\sigma(x)$
• if t is ft1 ... tk, then $t^{M, [\sigma]}$ = $f^M(t_1^{M, [\sigma]} ... t_n^{M, [\sigma]})$

Then the ternary relation $M \vDash \phi[\sigma]$ (satisfaction) on any formula is defined as:

• $M \vDash Pt_1 ... t_n [\sigma]$ iff $P^M(t_1^{M, [\sigma]} ... t_n^{M, [\sigma]})$
• $M \vDash t_1 = t_2 [\sigma]$ iff $t_1^{M, [\sigma]} = t_2^{M, [\sigma]}$
• $M \vDash \neg \phi [\sigma]$ iff $M \nvDash \phi [\sigma]$
• $M \vDash (\phi \land \psi) [\sigma]$ iff $M \vDash \phi[\sigma]$ and $M \vDash \phi[\sigma]$
• similarly for $\lor, \rightarrow, \leftrightarrow$
• $M \vDash \exists x \phi[\sigma]$ iff there is a $a \in M$ s.t. $M \vDash \phi[\sigma(a/x)]$
• $M \vDash \forall x \phi[\sigma]$ iff for all $a \in M$ we have $M \vDash \phi[\sigma(a/x)]$

where $\sigma(a/x)$ is the same as $\sigma$ except that a is assigned to x.

Locality and Truth

Locality Lemma in FOL
if $\sigma$ and $\sigma '$ agree on the free variables in $\phi$, then
$M \vDash \phi[\sigma]$ iff $M \vDash \phi[\sigma ']$

Thus, if $\phi$ is a sentence, then either all assignments in M satisfy it or none do. Then we write $M \vDash \phi$ for truth.

Logical consequence and other concepts are exactly like those in PL.

Useful Equivalences

Besides those from PL:

• define $\exists$ in terms of $\forall$ and vice versa
• distribute a quantifier in a conjuction or disjunction
• distribution when one of the formulas does not contain the bound variable
• distribution for implication

$$\forall x (\phi (x) \rightarrow \psi) = \exists x \phi(x) \rightarrow \psi$$

Normal form

Prenex normal form: All quantifiers come first and then a quantifier-free formula. It can be obtained using the listed equivalences.