Propositional Formula Position

logic

Definition

Propositional Formula Position

A propositional formula position is a finite sequence of positive integers that specifies one occurrence of a subformula inside a propositional formula.

If $A{|}_{\pi }=B$, we also say that $B$ occurs in $A$ at the position $\pi$.

Recursive Definition

The following clauses state which sequences are valid positions and what subformula each position denotes. They are read as inductive rules: every valid position is obtained by finitely many applications of the clauses below.

Root Position

For every propositional formula $A$, the empty sequence $\epsilon$ is a position in $A$, and

$$A{|}_{\epsilon }=A$$

Further:

$$\mathrm{pol}(A,\epsilon )\stackrel{\text{def}}{=}1$$

Conjunction and Disjunction

Let $A{|}_{\pi }=B$. If $B$ has the form:

$$B_1\wedge \cdots \wedge B_n\text{or}{B}_1\vee \cdots \vee B_n$$

then for all $i\in \{1,\dots ,n\}$ the position $\pi .i$ is a position in $A$, and:

$$A{|}_{\pi .i}\stackrel{\text{def}}{=}{B}_i$$

Further:

$$\mathrm{pol}(A,\pi .i)\stackrel{\text{def}}{=}\mathrm{pol}(A,\pi )$$

Negation

Let $A{|}_{\pi }=B$. If $B$ has the form:

$$\neg B_1$$

then $\pi .1$ is a position in $A$, and:

$$A{|}_{\pi .1}\stackrel{\text{def}}{=}{B}_1$$

Further:

$$\mathrm{pol}(A,\pi .1)\stackrel{\text{def}}{=}-\mathrm{pol}(A,\pi )$$

Implication

Let $A{|}_{\pi }=B$. If $B$ has the form:

$$B_1\to B_2$$

then $\pi .1$ and $\pi .2$ are positions in $A$, and:

$$A{|}_{\pi .i}\stackrel{\text{def}}{=}{B}_i$$

Further:

$$\begin{array}{rl}\mathrm{pol}(A,\pi .1)& \stackrel{\text{def}}{=}-\mathrm{pol}(A,\pi )\\ \mathrm{pol}(A,\pi .2)& \stackrel{\text{def}}{=}\mathrm{pol}(A,\pi )\end{array}$$

Equivalence

Let $A{|}_{\pi }=B$. If $B$ has the form:

$$B_1\leftrightarrow B_2$$

then $\pi .1$ and $\pi .2$ are positions in $A$, and:

$$A{|}_{\pi .i}\stackrel{\text{def}}{=}{B}_i$$

Further:

$$\begin{array}{rl}\mathrm{pol}(A,\pi .1)& \stackrel{\text{def}}{=}0\\ \mathrm{pol}(A,\pi .2)& \stackrel{\text{def}}{=}0\end{array}$$

Occurrence

If $A{|}_{\pi }=B$ we say that $B$ occurs in $A$ at position $\pi$. Different positions may determine different occurrences of the same subformula.

Examples

$p\wedge (q\vee r)$

Let

$$A=p\wedge (q\vee r).$$

Then the following are positions in $A$:

$$\epsilon ,1,2,2.1,\mathrm{2.2.}$$

The corresponding subformulas are:

$$A{|}_{\epsilon }=p\wedge (q\vee r),$$ $$A{|}_1=p,A{|}_2=q\vee r,$$ $$A{|}_{2.1}=q,A{|}_{2.2}=r.$$

$p\vee p$

Let

$$A=p\vee p.$$

Then

$$A{|}_1=p\text{and}A{|}_2=p.$$

So the same subformula $p$ occurs in $A$ at two different positions. This is why positions are useful when one wants to talk about one fixed occurrence.