14.2 Propositional Calculus

A background in symbolic logic is essential to understanding how logic programs are constructed and executed. Symbolic logic is a formal system involving both a syntax by which propositions and relationships between propositions are expressed and formal methods by which new propositions can be deduced from axioms (i.e., propositions asserted to be true). The goal of symbolic logic is to provide a formal apparatus by which the validity of these new propositions can be verified. Multiple systems of symbolic logic exist, which offer varying degrees of expressivity in describing and manipulating propositions. A proposition is a statement that is either true or false (e.g., “Pascal is a philosopher”). Propositional logic involves the use of symbols (e.g., p, q, and r) for expressing propositions. The simplest form of a proposition is an atomic proposition. For example, the symbol p could represent the atomic proposition “Pascal is a philosopher.” Compound propositions can be formed by connecting two or more atomic propositions with logical operators (Table 14.1):

Table 14.1 Logical Concepts and Operators or Connectors

The precedence of these operators is implied in their top-down presentation (i.e., highest to lowest) in Table 14.1:

The truth table presented in Table 14.2 proves the logical equivalence between p ⊃ q and ¬ p ∨ q.

Table 14.2 Truth Table Proof of the Logical Equivalence p ⊃ q ≡ ¬ p ᴠ q

A model of a proposition in formal logic is a row of the truth table. Entailment, which is a semantic concept in formal logic, means that all of the models that make the left-hand side of the entailment symbol (⊨) true also make the right-hand side true. For instance, p ∧ q ⊨ p ∨ q, which reads left to right “p ∧ q entails p ∨ q” and reads right to left “p ∨ q is a semantic consequence of p ∧ q.” Notice that p ∨ q ⊨ p ∧ q is not true because some models that make the proposition on the left-hand side true (e.g., the second and third rows of the truth table) do not make the proposition on the right-hand side true.

While implication and entailment are different concepts, they are easily confused. Implication is a function or connective operator that establishes a conditional relationship between two propositions. Entailment is a semantic relation that establishes a consequence relationship between a set of propositions and a proposition.

While different concepts, implication and entailment are related:

α ⊨ β if and only if the proposition α ⊃ β is true for all models.⁴

This statement is called the deduction theorem and a proposition that is true for all models is called a tautology (see rightmost column in Table 14.3).

Table 14.3 Truth Table Illustration of the Concept of Entailment in p ∧ q ⊨ p ᴠ q

The relationship between logical equivalence (≡) and entailment (⊨)is also notable:

Biconditional and logical equivalence are also sometimes confused with each other. Like implication, biconditional establishes a (bi)conditional relationship between two propositions. Akin to entailment, logical equivalence is a semantic relation that establishes a (bi)consequence relationship. While different concepts, biconditional and logical equivalence (like implication and entailment) are similarly related:

The rightmost column in Table 14.2 illustrates that (p ⊃ q) ⇐⇒ (¬ p ∨ q) is a tautology since (p ⊃ q) ≡ (¬ p ∨ q).

4. This statement can also be expressed as: .

5. This statement can also be expressed as: .