Tautologies, Well-Formed Formulae, Functional Completeness and Normal Forms

In propositional logic, compound propositions can behave differently depending on the truth values of their component propositions. Some expressions are always true, some are always false, and others may be true in some cases and false in others.

These ideas lead to the concepts of tautology, contradiction, contingency, well-formed formulae, functionally complete sets of connectives, and normal forms.

---

Tautology

A compound proposition that is true for every possible combination of truth values of its variables is called a tautology.

In a truth table, a tautology has only T values in its final column.

For example, consider

$$(p \rightarrow q)\lor(q\rightarrow p)$$

Its truth table is:

The final column contains only T.

Therefore,

$$\boxed{(p\rightarrow q)\lor(q\rightarrow p)}$$

is a tautology.

Another Example

Consider

$$p\rightarrow(q\rightarrow p)$$

Again, the final column contains only T.

Hence,

$$\boxed{p\rightarrow(q\rightarrow p)}$$

is a tautology.

---

Contradiction

A compound proposition that is false for every possible combination of truth values of its variables is called a contradiction.

Its final truth-table column contains only F.

Consider

$$(p\land\neg p)\land q$$

Since

$$p\land\neg p$$

can never be true, the entire expression is always false.

Therefore,

$$\boxed{(p\land\neg p)\land q}$$

is a contradiction.

---

Contingency

A proposition that is neither always true nor always false is called a contingency.

In other words, the final column of its truth table contains both T and F.

For example,

$$p\land q$$

is a contingency because it is true when both $p$ and $q$ are true, but false in other cases.

Thus, compound propositions can be classified as:

• Tautology — always true
• Contradiction — always false
• Contingency — sometimes true and sometimes false

---

Identifying Tautology and Contradiction in Larger Expressions

Consider the expressions

$$(p\lor q)\lor\neg p$$

and

$$(p\land q)\land\neg p$$

Their truth table is:

The expression

$$(p\lor q)\lor\neg p$$

has only T in its final column, so it is a tautology.

The expression

$$(p\land q)\land\neg p$$

has only F in its final column, so it is a contradiction.

---

Well-Formed Formula

What Is a Well-Formed Formula?

A logical expression is constructed using:

• propositional variables such as $p,q,r$
• logical connectives such as $\neg,\land,\lor,\rightarrow,\leftrightarrow$
• parentheses

However, not every arbitrary arrangement of these symbols forms a meaningful logical expression.

A syntactically correct logical expression is called a well-formed formula, abbreviated as WFF.

It is commonly pronounced “woof.”

For example,

$$p\land(q\lor r)$$

is a well-formed formula.

But an expression such as

$$p\land\lor q$$

is not a WFF because the logical operators have not been used according to the rules of propositional logic.

Rules for Constructing a Well-Formed Formula

Well-formed formulae can be defined recursively.

Propositional Variables and Constants

Every propositional variable is a WFF.

Thus,

$$p,\quad q,\quad r$$

are well-formed formulae.

Logical constants such as

$$T\quad\text{and}\quad F$$

may also be treated as well-formed formulae.

Negation

If $P$ is a WFF, then

$$\neg P$$

is also a WFF.

For example, if

$$p$$

is a WFF, then

$$\neg p$$

is also a WFF.

Similarly, if

$$p\lor q$$

is a WFF, then

$$\neg(p\lor q)$$

is also a WFF.

Combining Formulae

If $P$ and $Q$ are WFFs, then the following are also WFFs:

$$(P\land Q)$$ $$(P\lor Q)$$ $$(P\rightarrow Q)$$ $$(P\leftrightarrow Q)$$

By repeatedly applying these rules a finite number of times, more complex well-formed formulae can be constructed.

For example,

$$(p\land q)\rightarrow(\neg r\lor p)$$

is a WFF because it is formed from valid variables and connectives according to these rules.

---

Functionally Complete Set of Connectives

Functional Completeness

A set of logical connectives is called a functionally complete set of connectives if every propositional formula can be expressed using only the connectives belonging to that set.

In other words, even if a formula originally contains several different logical operators, it should be possible to rewrite it using only the connectives from the functionally complete set.

Eliminating the Conditional

Recall the logical equivalence

$$p\rightarrow q \equiv \neg p\lor q$$

Therefore, the conditional connective $\rightarrow$ is not strictly necessary because it can be expressed using only negation and disjunction.

Eliminating the Biconditional

The biconditional can be expressed in different ways.

One useful identity is

$$p\leftrightarrow q \equiv (p\land q)\lor(\neg p\land\neg q)$$

Another equivalent form is

$$p\leftrightarrow q \equiv (p\rightarrow q)\land(q\rightarrow p)$$

Since every implication can itself be replaced by negation and disjunction, the biconditional can also be eliminated.

Therefore, both

$$\rightarrow$$

and

$$\leftrightarrow$$

can be expressed using combinations of

$$\neg,\land,\lor.$$

Hence,

$$\{\neg,\land,\lor\}$$

is a functionally complete set.

Reducing the Number of Required Connectives

Using De Morgan's Laws, conjunction can be expressed using only negation and disjunction:

$$p\land q \equiv \neg(\neg p\lor\neg q)$$

Similarly, disjunction can be expressed using only negation and conjunction:

$$p\lor q \equiv \neg(\neg p\land\neg q)$$

Therefore, conjunction is unnecessary if $\neg$ and $\lor$ are available.

Likewise, disjunction is unnecessary if $\neg$ and $\land$ are available.

This means that the following sets are functionally complete:

$$\boxed{\{\neg,\lor\}}$$

and

$$\boxed{\{\neg,\land\}}$$

Every propositional formula can be rewritten using only one of these two sets.

These are examples of minimal functionally complete sets, because removing one of the connectives from either set would destroy its ability to represent every propositional formula.

---

Normal Forms

Why Do We Need Normal Forms?

One way to determine whether two logical expressions $P$ and $Q$ are equivalent is to construct their truth tables and compare the final columns.

However, when the number of variables increases, truth tables become increasingly large.

For example, a formula containing $n$ propositional variables requires

$$2^n$$

rows in its truth table.

Instead of always comparing large truth tables, logical expressions can be converted into standard structures called normal forms.

A normal form provides a systematic representation of a logical expression.

Two important normal forms are:

1. Disjunctive Normal Form (DNF)
2. Conjunctive Normal Form (CNF)

Before studying them, it is useful to understand elementary products and elementary sums.

---

Disjunctive Normal Form

Elementary Product

An elementary product is a conjunction of propositional variables or their negations.

Examples include

$$p\land q$$ $$p\land\neg q$$ $$\neg p\land q$$

and

$$\neg p\land\neg q.$$

Each variable or negated variable appearing in such an expression is called a literal.

For example, in

$$p\land\neg q\land r,$$

the literals are

$$p,\quad\neg q,\quad r.$$

Elementary Sum

An elementary sum is a disjunction of propositional variables or their negations.

Examples include

$$p\lor q$$ $$p\lor\neg q$$ $$\neg p\lor q$$

and

$$\neg p\lor\neg q.$$

Important Properties

An elementary product is always false if it contains a variable together with its negation.

For example,

$$p\land\neg p\land q$$

is always false because

$$p\land\neg p$$

is a contradiction.

Thus,

$$\boxed{p\land\neg p\equiv F}$$

Similarly, an elementary sum is always true if it contains a variable together with its negation.

For example,

$$p\lor\neg p\lor q$$

is always true because

$$p\lor\neg p$$

is a tautology.

Thus,

$$\boxed{p\lor\neg p\equiv T}$$

What Is Disjunctive Normal Form?

A logical expression is said to be in Disjunctive Normal Form (DNF) if it is a disjunction of elementary products.

In simple terms:

DNF has an OR of AND terms.

For example,

$$(p\land q)\lor(\neg p\land r)$$

is in DNF.

Another example is

$$p\lor(q\land r).$$

Here, the single literal $p$ itself can be treated as an elementary product.

Therefore, this expression is also in DNF.

However,

$$p\land(q\lor r)$$

is not in DNF because the outermost operation is conjunction and one of its components is a disjunction.

Procedure for Obtaining DNF

A logical expression can be converted into Disjunctive Normal Form by following these steps.

Step 1: Eliminate Conditional and Biconditional Connectives

Replace every implication using

$$p\rightarrow q \equiv \neg p\lor q.$$

Replace every biconditional using, for example,

$$p\leftrightarrow q \equiv (p\land q)\lor(\neg p\land\neg q).$$

After this step, the expression should contain only

$$\neg,\land,\lor.$$

Step 2: Push Negations Inward

Use De Morgan's Laws:

$$\neg(p\land q) \equiv \neg p\lor\neg q$$

and

$$\neg(p\lor q) \equiv \neg p\land\neg q.$$

Also use double negation:

$$\neg\neg p\equiv p.$$

Continue until negation applies directly to individual variables.

Step 3: Apply the Distributive Law

Use

$$p\land(q\lor r) \equiv (p\land q)\lor(p\land r)$$

until the expression becomes a disjunction of elementary products.

Example: Convert an Expression to DNF

Consider

$$p\land(p\rightarrow q).$$

First eliminate the implication:

$$p\land(p\rightarrow q)$$ $$\equiv p\land(\neg p\lor q)$$

Now apply the distributive law:

$$\equiv (p\land\neg p)\lor(p\land q).$$

Since

$$p\land\neg p\equiv F,$$

we obtain

$$\equiv F\lor(p\land q).$$

Therefore,

$$\boxed{p\land(p\rightarrow q)\equiv p\land q}$$

which is in Disjunctive Normal Form.

Another DNF Example

Consider

$$p\lor\left(\neg p\rightarrow\left(q\lor(q\rightarrow\neg r)\right)\right).$$

First eliminate the innermost implication:

$$q\rightarrow\neg r \equiv \neg q\lor\neg r.$$

Thus,

$$p\lor\left(\neg p\rightarrow \left(q\lor(\neg q\lor\neg r)\right)\right).$$

Now eliminate the remaining implication.

Since

$$\neg p\rightarrow X \equiv \neg(\neg p)\lor X \equiv p\lor X,$$

we get

$$p\lor \left( p\lor \left(q\lor\neg q\lor\neg r\right) \right).$$

Therefore,

$$\equiv p\lor q\lor\neg q\lor\neg r.$$

But

$$q\lor\neg q\equiv T.$$

Hence,

$$p\lor q\lor\neg q\lor\neg r \equiv T.$$

So the original expression is a tautology.

It is also already expressible as a disjunction of literals during the simplification process, which is compatible with DNF.

---

Conjunctive Normal Form

What Is Conjunctive Normal Form?

A logical expression is said to be in Conjunctive Normal Form (CNF) if it is a conjunction of elementary sums.

In simple terms:

CNF has an AND of OR terms.

For example,

$$(p\lor q)\land(\neg p\lor r)$$

is in CNF.

Each parenthesized expression is an elementary sum, and these elementary sums are connected by conjunction.

Another example is

$$p\land(q\lor\neg r).$$

The literal $p$ can itself be treated as an elementary sum containing one literal.

Therefore, this expression is also in CNF.

However,

$$p\lor(q\land r)$$

is not in CNF.

Procedure for Obtaining CNF

The procedure for obtaining CNF is similar to that used for DNF.

Step 1: Eliminate Conditional and Biconditional Connectives

Replace implications and biconditionals so that only

$$\neg,\land,\lor$$

remain.

For example,

$$p\rightarrow q \equiv \neg p\lor q.$$

Step 2: Push Negations Inward

Use De Morgan's Laws and double negation until every negation applies directly to a variable.

Step 3: Apply the Appropriate Distributive Law

For CNF, distribute OR over AND:

$$p\lor(q\land r) \equiv (p\lor q)\land(p\lor r).$$

Continue until the expression becomes a conjunction of elementary sums.

Example: Obtain CNF

Consider

$$p\land(p\rightarrow q).$$

First eliminate the implication:

$$p\land(p\rightarrow q)$$ $$\equiv p\land(\neg p\lor q).$$

The expression now consists of a conjunction of:

$$p$$

and

$$\neg p\lor q.$$

Therefore, it is already in Conjunctive Normal Form:

$$\boxed{p\land(\neg p\lor q)}$$

Another CNF Example

Consider

$$p\lor(q\land r).$$

This is not initially in CNF because a conjunction occurs inside a disjunction.

Apply the distributive law:

$$p\lor(q\land r)$$ $$\equiv (p\lor q)\land(p\lor r).$$

Now both

$$p\lor q$$

and

$$p\lor r$$

are elementary sums.

Therefore,

$$\boxed{(p\lor q)\land(p\lor r)}$$

is the Conjunctive Normal Form of the expression.