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

- Propositional letters are formulas.
- if $\phi$ is a formula, then $\neg \phi$ is a formula.
- if $\phi$ and $\psi$ are formulas, then $(\phi \land \psi)$, $(\phi \lor \psi)$, $(\phi \rightarrow \psi)$, $(\phi \leftrightarrow \psi)$ are formulas.
- 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:

- It is possible to have smaller set of
primitiveconnectives, for example $\neg$ and $\lor$.- $\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:

- $V \vDash \phi$ iff V(p) = 1 for p in L
- $V \vDash \neg \phi$ iff $V \nvDash \phi$
- $V \vDash \phi \land \psi$ iff $V \vDash \phi$ and $V \vDash \psi$
- $V \vDash \phi \lor \psi$ iff $V \vDash \phi$ or $V \vDash \psi$
- $V \vDash \phi \rightarrow \psi$ iff $V \nvDash \phi$ or $V \vDash \psi$
- $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 isEvery 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:

- A variable is an L-term
- A individual constant in L is an L-term.
- 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.

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

- Atomic L-formulas are L-formulas
- 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.
- 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.

- if c $\in$ L, then I(c) is an element of domain M
- if P is an n-ary predicate symbol in L, then I(P) is an n-ary relation over M
- 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.