What is a Sub Formula and What is a Maximal Sub Formula in Propositional Logic

Question

What is a Sub formula of a Propositional Formula? Suppose I have a formula C or -C Then what are the sub formulas of this and what is the maximal sub formula of this Propositional Formula. I am a bit confused of these terms. Kindly explain.

Thanks,

Answer 1

The notion of a subformula is absolutely standard -- have you consulted a textbook or two? If so, which book(s), and which page(s) did you not understand?

Informally, a subformula is a part of a wff which is itself a wff. More formally the best approach is via the idea of the constructional history for a wff, with the subformulae being the wffs that appear in the history. Any decent textbook will explain this, and explain how you set out constructional histories as trees.

"Maximal subformula" is not standard jargon, so I'll comment on that. The usual way of setting things up formally is to allow any wff that appears on a construction tree of the wff $A$ to count as a subformula of $A$, including $A$ itself -- so trivially the maximal subformula of $A$, in the natural sense of the biggest one, is $A$ itself. The maximal proper subformula(e) of $A$ would be the subformula or subformulae which appear at the penultimate level of the construction tree.

Answer 2

To add to Peter Smith's answer, let's say we wrote formulas with the following formation rules.

1. All lower case letters of the Latin Alphabet are formulas.
2. If $\alpha$ and $\beta$ are formulas, then so is X$\alpha$$\beta$.

A subformula of a formula is a string within the formula which can appear independently on its own and still qualify as a formula.

For instance, we might consider the formula

XXaXbdXcXdXde.

XcXdXde is also a formula, so it qualifies as a subformula of XXaXbdXcXdXde. a is also a subformula of XXaXbdXcXdXde. When we write formulas this way, we can determine all subformulas of a formula by moving from left to right in a certain way. The subformulas for this example are:

XXaXbdXcXdXde.

XaXbd.

a.

Xbd.

b.

d.

XcXdXde.

c.

XdXde.

d.

Xde.

d.

e.

This list does involve redundancy, but the general pattern here used allows you to find all subformulas of a formula in this notation.