Propositional Calculus

Propositional calculus or Sentential calculus is a calculus that represents the logical structure of truth-functional connectives ("not," "and," "or," "if…, then...," and others); the connectives such that their meanings determine the truth-value of a given sentence in which they occur once the truth-values of all the simple sentences in the given sentence are given. It is often referred to as Propositional logic.

Overview

Consider the following argument:

If Jack is innocent, then Jack has an alibi and Jack is not a murderer.

Jack does not have an alibi.

Therefore, Jack is not innocent.

The truth-values, truth or falsity, of the sentences in this argument are exclusively dependent on whether each of the simple sentences in the sentences, "Jack is innocent," "Jack has an alibi," and "Jack is a murderer" is true or false. In other words, once the truth-values of the simple sentences are determined, the complex sentences in the arguments are determined only in terms of the meanings of the connectives, “if…then...,” “not,” and “and,” which are examples of truth-functional connectives. Propositional calculus, focusing on connectives of such kinds, clarifies what form a given argument ${\displaystyle A}$ (such as the one in question here) has, and studies how the correctness or incorrectness of ${\displaystyle A}$ depends on the truth-functional connectives that it contains.

The language of propositional calculus consists of propositional variables, truth-functional connectives, (most familiar ones are ${\displaystyle \lnot ,\wedge ,\vee ,\rightarrow ,\leftrightarrow }$) and parentheses. Formulas are built up from propositional variables by using truth-functional connectives and parentheses.

To propositional variables, either truth or falsity is assigned and, relative to the truth-value assignment, the truth-value of an arbitrary well-formed formula (for the definition, see the section Syntax) that contains the propositional variables is calculated based on the truth-functional connectives in the well-formed formula.

A propositional calculus has a set of axioms (possibly empty) and rules of inference. There are various kinds of propositional calculi, for which the soundness and completeness can be proved. (for the definitions of soundness and completeness, see the corresponding section Soundness and Completeness)

Studies Under Propositional Calculus

Some sentences have truth-values, truth or falsity, (declarative sentences are typical examples) and some do not (interrogative sentences, exclamatory sentences, and others). The sentences of the latter kind are excluded from what propositional calculus studies. Thus, in propositional calculus, it is assumed that every sentence is either true or false. (This assumption is called the principle of bivalence.)

Among such sentences, the sentences that do not include sentential connectives such as "and," "or," and others. (e.g. “John is a bachelor.”) are called atomic sentences. More complex sentences (e.g. “John is a bachelor and Ben is married”) are built from atomic sentences and sentential connectives.

Some sentential connectives determine the truth-values of the complex sentences in which they occur, once the truth-values of atomic sentences that the complex sentences contain are determined. For instance, the truth-value of “John is a bachelor and Ben is married” is determined purely by the meaning of the connective “and” once the truth-values of the two atomic sentences “John is a bachelor” and “Ben is married” are determined. The connectives of such a kind is called truth-functional. (Notice that this does not apply to all the sentential connectives. Consider “Ben is happy because Ben is married.” The truth-value of this sentence is still undetermined even if both the atomic sentences in this sentence are true.) Truth-functional connectives are the connectives that propositional calculus studies. Examples of such connectives are "and," "or," "if…then..." (These connectives of a certain use only. Some uses of the connectives are not truth-functional. For instance, consider counterfactual statements).

Syntax

The language of propositional calculus consists of 1. propositional variables, usually annotated by p, q, r,…, 2. truth-functional connectives, ${\displaystyle \lnot ,\wedge ,\vee ,\rightarrow ,\leftrightarrow }$, and 3. parentheses “(“ and “).” Propositional variables represent atomic sentences and ${\displaystyle \lnot ,\wedge ,\vee ,\rightarrow }$ , and ${\displaystyle \leftrightarrow }$ are usually considered as “not,” “and,” “or,” “if…then...,” and “...if and only if...” respectively. ${\displaystyle \lnot }$ is called unary (meaning that it is attachable to one wff. For the definitnion of wffs, see below.) and the other four connectives are called binary (meaning that they combine two wffs). Parentheses are used to represent the punctuations in sentences.

Well-formed formulas (wffs) are recursively built in the following way.

• Propositional variables are wffs.
• If ${\displaystyle \alpha }$ is a wff, then ${\displaystyle \lnot \alpha }$ is a wff.
• If ${\displaystyle \alpha }$ and ${\displaystyle \beta }$ are wffs, then ${\displaystyle (\alpha \star \beta )}$ is a wff where ${\displaystyle \star }$ is a binary connective.

Conventionally the outermost set of parentheses is dropped. Also, the order of strength in which propositional connectives bind is stipulated as: ${\displaystyle \leftrightarrow ,\rightarrow ,\wedge }$ and ${\displaystyle \vee ,\lnot }$. Therefore, taking these two conventions into account, say, the wff “ ${\displaystyle ((\lnot p\vee q)\rightarrow r)}$” built up by the above definition is written as “ ${\displaystyle \lnot p\vee q\rightarrow r}$.”

The connective in a given wff ${\displaystyle \phi }$ that binds last is called the main connective of ${\displaystyle \phi }$. Thus, in the case of ${\displaystyle \lnot p\vee q\rightarrow r}$, the main connective is ${\displaystyle \rightarrow }$. Wffs with ${\displaystyle \lnot ,\wedge ,\vee ,\rightarrow ,}$ and ${\displaystyle \leftrightarrow }$ as their main connectives are called negation, conjunction, disjunction, conditional, and biconditional respectively.

An argument consists of a set of wffs and a distinguished wff. The wffs of the former kind are called premises and the distinguished wff is called the conclusion. The set of premises of a given argument can possibly be empty.

For instance, the set of sentences about Jack in the opening example is represented in the language of propositional logic as follows:

${\displaystyle p\rightarrow (q\wedge \lnot r)}$

${\displaystyle \lnot q}$

${\displaystyle \lnot p}$

where p, q, and r represent “Jack is innocent,” “Jack has an alibi,” and “Jack is a murderer,” respectively. The first two wffs are the premises and the last wff is the conclusion of the argument.

Semantics

Every wff in propositional calculus gets either of the two truth-values, True and False (T and F). Relative to the assignment V of truth-values to propositional variables (a function from the set of propositional variables to {T, F}, the truth-values of other wffs are determined recursively as follows:

• p is true iff V(p)=T
• ${\displaystyle \lnot \alpha }$ is T iff ${\displaystyle \alpha }$ is F.
• ${\displaystyle \alpha \wedge \beta }$ is T iff ${\displaystyle \alpha }$ is T and ${\displaystyle \beta }$ is T.
• ${\displaystyle \alpha \vee \beta }$ is T iff ${\displaystyle \alpha }$is T or ${\displaystyle \beta }$ is T (in the inclusive sense of "or" i.e. including the case in which both are T)
• ${\displaystyle \alpha \rightarrow \beta }$ is T iff ${\displaystyle \alpha }$ is F or ${\displaystyle \beta }$ is T.
• ${\displaystyle \alpha \leftrightarrow \beta }$ is T iff ${\displaystyle \alpha }$ and ${\displaystyle \beta }$ coincide in their truth-values.

For instance, when p, q, and r get T, T and F respectively, ${\displaystyle (p\vee \lnot q)\leftrightarrow (r\wedge q)}$ gets F. For the left side of the biconditional is T because p is T and ${\displaystyle \lnot q}$ is F, and the right side is F because r is F and q is T.

A wff that gets T no matter what truth-value assignment is given is called a tautology. A set ${\displaystyle \Gamma }$ of wffs (maybe empty) implies a wff ${\displaystyle \phi }$ if and only if ${\displaystyle \phi }$ is T relative to every truth-value assignment V that assigns Ts to all the wffs in ${\displaystyle \Gamma }$. An argument, consisting of a set ${\displaystyle \Gamma }$ of wffs and a wff ${\displaystyle \phi }$, is said to be valid if ${\displaystyle \Gamma }$ implies ${\displaystyle \phi }$. (For instance, readers are invited to check that the argument about Jack is valid.)

If an argument, consisting of a premise set ${\displaystyle \Gamma }$ and a conclusion ${\displaystyle \phi }$, is valid, , we write “ ${\displaystyle \Gamma \models \phi }$,” which often reads as “ ${\displaystyle \Gamma }$ implies ${\displaystyle \phi }$.” (For the left hand side of “ ${\displaystyle \models }$,” the wffs in ${\displaystyle \Gamma }$ are written with commas between them, e.g. if ${\displaystyle \Gamma }$ is {p, q, r}, we write “p, q, r ${\displaystyle \models \phi }$.”)

Propositional Calculi

Proofs in a propositional calculus

Propositional calculus consists of a set of specified wff called axioms (the set can possibly be empty) and rules of inference. A proof of an argument is a sequence of wffs in which (1) each wff is a premise, an axiom, or a wff that is derived from previous wffs in the sequence by a rule of inference and (2) the last wff of the sequence is the conclusion of the argument. If an argument, consisting of a premise set ${\displaystyle \Gamma }$ and a conclusion ${\displaystyle \phi }$, has a proof, we write “ ${\displaystyle \Gamma \vdash \phi }$,” which reads as “ ${\displaystyle \phi }$ is provable from ${\displaystyle \Gamma }$.” (The convention for the left hand side of “ ${\displaystyle \vdash }$” is the same as the one for “ ${\displaystyle \models }$”.)

Particularly, if there is a proof for an argument with an empty set of premises, i.e. if the conclusion of the argument can be derived only from axioms based on the rules of inference, then the conclusion is called a theorem. Thus, if ${\displaystyle \phi }$ is a theorem, we can write “ ${\displaystyle \vdash \phi }$,” which reads as “ ${\displaystyle \phi }$ is a theorem.”

There are various propositional calculi, of which two of the most famous ones are provided below.

Hilbert-Style Propositional Calculus

One famous deductive system takes the language of propositional calculus that consists of propositional variables, the connectives, ${\displaystyle \rightarrow }$ and ${\displaystyle \lnot }$, and parentheses. The other connectives are defined as follows:

• ${\displaystyle \alpha \wedge \beta :=\lnot (\alpha \rightarrow \lnot \beta )}$
• ${\displaystyle \alpha \vee \beta :=\lnot \alpha \rightarrow \beta }$
• ${\displaystyle \alpha \leftrightarrow \beta :=\lnot ((\alpha \rightarrow \beta )\rightarrow \lnot (\beta \rightarrow \alpha ))}$

The axioms have one of the following forms:

• A1 ${\displaystyle \alpha \rightarrow (\beta \rightarrow \alpha )}$
• A2 ${\displaystyle (\alpha \rightarrow (\beta \rightarrow \gamma )\rightarrow ((\alpha \rightarrow \beta )\rightarrow (\alpha \rightarrow \gamma ))}$
• A3 ${\displaystyle (\lnot \alpha \rightarrow \lnot \beta )\rightarrow ((\lnot \alpha \rightarrow \beta )\rightarrow \alpha )}$

The only rule of inference is modus ponens, i.e. from ${\displaystyle \alpha }$ and ${\displaystyle \alpha \rightarrow \beta }$, derive ${\displaystyle \beta }$.

Here is an example of a proof in this system for ${\displaystyle p,(r\rightarrow p)\rightarrow (r\rightarrow (p\rightarrow s))\vdash r\rightarrow s}$^[1]:

Number	wff	Justification
1	${\displaystyle p}$	A premiss
2	${\displaystyle (r\rightarrow p)\rightarrow (r\rightarrow (p\rightarrow s))}$	A premise
3	${\displaystyle p\rightarrow (r\rightarrow p)}$	An axiom of the form A1
4	${\displaystyle r\rightarrow p}$	From 1 and 3 by modus ponens
5	${\displaystyle r\rightarrow (p\rightarrow s)}$	From 2 and 4 by modus ponens
6	${\displaystyle (r\rightarrow (p\rightarrow s))\rightarrow ((r\rightarrow p)\rightarrow (r\rightarrow s))}$	An axiom of the form A2
7	${\displaystyle (r\rightarrow p)\rightarrow (r\rightarrow s)}$	From 5 and 6 by modus ponens
8	${\displaystyle r\rightarrow s}$	From 4 and 7 by modus ponens

Natural Deduction

Another example takes the language of propositional calculus that consists of propositional variables, the connectives, ${\displaystyle \lnot ,\wedge ,\vee ,\rightarrow ,\leftrightarrow ,}$ and parentheses. The set of axioms is empty. However, it has the following rules of inference:

• Reductio ad absurdum (negation introduction)

From (p→q), (p→ ¬q), infer ¬p.

• Double negative elimination

From ¬¬p, infer p.

• Conjunction introduction

From p and q, infer (p ∧ q).

• Conjunction elimination

From (p ∧ q), infer p;

From (p ∧ q), infer q.

• Disjunction introduction

From p, infer (p ∨ q);

From p, infer (q ∨ p).

• Disjunction elimination

From (p ∨ q), (p → r), (q → r), infer r.

• Biconditional introduction

From (p → q), (q → p), infer (p ↔ q).

• Biconditional elimination

From (p ↔ q), infer (p → q);

From (p ↔ q), infer (q → p).

• Modus ponens (conditional elimination)

From p, (p → q), infer q.

• Conditional proof (conditional introduction)

If assuming p allows a proof of q, infer (p → q).

Here is an example of a proof in this system again for ${\displaystyle p,(r\rightarrow p)\rightarrow (r\rightarrow (p\rightarrow s))\vdash r\rightarrow s}$.

Number	wff	Justification
1	${\displaystyle p}$	A premise
2	${\displaystyle (r\rightarrow p)\rightarrow (r\rightarrow (p\rightarrow s))}$	A premise
3	${\displaystyle r}$	An assumption for a conditional proof
4	${\displaystyle p}$	Iteration of 1
5	${\displaystyle r\rightarrow p}$	From 3 and 4 by a conditional proof
6	${\displaystyle r\rightarrow (p\rightarrow s)}$	From 2 and 5 by modus ponens
7	${\displaystyle r}$	Assumption for a conditional proof
8	${\displaystyle p\rightarrow s}$	From 6 and 7 by modus ponens
9	${\displaystyle s}$	From 1 and 8 by modus ponens
10	${\displaystyle r\rightarrow s}$	From 7 and 9 by a conditional proof

Famous Provable Arguments

Here are some of the most famous forms of arguments that are provable in both of the calculi:

Basic and Derived Argument Forms
Name	Sequent	Description
Modus Ponens	((p → q) ∧ p) ├ q	if p then q; p; therefore q
Modus Tollens	((p → q) ∧ ¬q) ├ ¬p	if p then q; not q; therefore not p
Hypothetical Syllogism	((p → q) ∧ (q → r)) ├ (p → r)	if p then q; if q then r; therefore, if p then r
Disjunctive Syllogism	((p ∨ q) ∧ ¬p) ├ q	Either p or q; not p; therefore, q
Constructive Dilemma	((p → q) ∧ (r → s) ∧ (p ∨ r)) ├ (q ∨ s)	If p then q; and if r then s; but either p or r; therefore either q or s
Destructive Dilemma	((p → q) ∧ (r → s) ∧ (¬q ∨ ¬s)) ├ (¬p ∨ ¬r)	If p then q; and if r then s; but either not q or not s; therefore either not p or not r
Simplification	(p ∧ q) ├ p	p and q are true; therefore p is true
Conjunction	p, q ├ (p ∧ q)	p and q are true separately; therefore they are true conjointly
Addition	p ├ (p ∨ q)	p is true; therefore the disjunction (p or q) is true
Composition	((p → q) ∧ (p → r)) ├ (p → (q ∧ r))	If p then q; and if p then r; therefore if p is true then q and r are true
De Morgan's Theorem (1)	¬(p ∧ q) ├ (¬p ∨ ¬q)	The negation of (p and q) is equiv. to (not p or not q)
De Morgan's Theorem (2)	¬(p ∨ q) ├ (¬p ∧ ¬q)	The negation of (p or q) is equiv. to (not p and not q)
Commutation (1)	(p ∨ q) ├ (q ∨ p)	(p or q) is equiv. to (q or p)
Commutation (2)	(p ∧ q) ├ (q ∧ p)	(p and q) is equiv. to (q and p)
Association (1)	(p ∨ (q ∨ r)) ├ ((p ∨ q) ∨ r)	p or (q or r) is equiv. to (p or q) or r
Association (2)	(p ∧ (q ∧ r)) ├ ((p ∧ q) ∧ r)	p and (q and r) is equiv. to (p and q) and r
Distribution (1)	(p ∧ (q ∨ r)) ├ ((p ∧ q) ∨ (p ∧ r))	p and (q or r) is equiv. to (p and q) or (p and r)
Distribution (2)	(p ∨ (q ∧ r)) ├ ((p ∨ q) ∧ (p ∨ r))	p or (q and r) is equiv. to (p or q) and (p or r)
Double Negation	p ├ ¬¬p	p is equivalent to the negation of not p
Transposition	(p → q) ├ (¬q → ¬p)	If p then q is equiv. to if not q then not p
Material Implication	(p → q) ├ (¬p ∨ q)	If p then q is equiv. to either not p or q
Material Equivalence (1)	(p ↔ q) ├ ((p → q) ∧ (q → p))	(p is equiv. to q) means, (if p is true then q is true) and (if q is true then p is true)
Material Equivalence (2)	(p ↔ q) ├ ((p ∧ q) ∨ (¬q ∧ ¬p))	(p is equiv. to q) means, either (p and q are true) or ( both p and q are false)
Exportation	((p ∧ q) → r) ├ (p → (q → r))	from (if p and q are true then r is true) we can prove (if q is true then r is true, if p is true)
Importation	(p → (q → r)) ├ ((p ∧ q) → r)
Tautology	p ├ (p ∨ p)	p is true is equiv. to p is true or p is true
Tertium non datur (Law of Excluded Middle)	├ (p ∨ ¬ p)	p or not p is true

Soundness and Completeness

A calculus is sound if, for all ${\displaystyle \Gamma }$ and ${\displaystyle \phi ,\Gamma \vdash \phi }$ implies ${\displaystyle \Gamma \models \phi }$. A calculus is complete if, for all ${\displaystyle \Gamma }$ and ${\displaystyle \phi }$, ${\displaystyle \Gamma \models \phi }$ implies ${\displaystyle \Gamma \vdash \phi }$.

There are various sound and complete propositional calculi (i.e. the calculi in which the notion of proof and that of validity correspond). The two calculi above are the examples of sound and complete propositional calculi.

Notes

References

ISBN links support NWE through referral fees

• Brown, Frank Markham. 2003. Boolean Reasoning: The Logic of Boolean Equations. 1st edition, Kluwer Academic Publishers, Norwell, MA. 2nd edition, Dover Publications, Mineola, New York. ISBN 9780486427850

• Chang, C.C., and H.J. Keisler. 1973. Model Theory. Amsterdam, Netherlands: North-Holland. ISBN 9780444880543

• Klement, Kevin C. 2006. "Propositional Logic" in Internet Encyclopedia of Philosophy. edited by James Fieser and Bradley Dowden. The Internet Encylopedia of Philosophy.

• Kohavi, Zvi. 1978. Switching and Finite Automata Theory. 1st edition, McGraw–Hill, 1970. 2nd edition, McGraw–Hill, 1978. ISBN 9780070353107

• Korfhage, Robert R. 1974. Discrete Computational Structures, Academic Press, New York, NY. ISBN 0124208606

• Lambek, J., and P.J. Scott. 1986. Introduction to Higher Order Categorical Logic. Cambridge University Press, Cambridge, UK. ISBN 9780521356534

• Mendelson, Elliot. 1964. Introduction to Mathematical Logic. D. Van Nostrand Company. ISBN 9780412808302

External Links

All links retrieved December 1, 2022.

• Propositional logic, The Internet Encyclopedia of Philosophy
• Propositions, Stanford Encyclopedia of Philosophy

General Philosophy Sources

• Stanford Encyclopedia of Philosophy
• The Internet Encyclopedia of Philosophy
• Paideia Project Online
• Project Gutenberg