Propositional logic

Declarative sentences

Propositional logic deals with statements, which are defined as declarative sentences having truth value.^[30][1] Examples of statements might include:

• Wikipedia is a free online encyclopedia that anyone can edit.
• London is the capital of England.
• All Wikipedia editors speak at least three languages.

Declarative sentences are contrasted with questions, such as "What is Wikipedia?", and imperative statements, such as "Please add citations to support the claims in this article.".^[31][32] Such non-declarative sentences have no truth value,^[33] and are only dealt with in nonclassical logics, called erotetic and imperative logics.

Compounding sentences with connectives

In propositional logic, a statement can contain one or more other statements as parts.^[1] Compound sentences are formed from simpler sentences and express relationships among the constituent sentences.^[34] This is done by combining them with logical connectives:^[34][35] the main types of compound sentences are negations, conjunctions, disjunctions, implications, and biconditionals,^[34] which are formed by using the corresponding connectives to connect propositions.^[36][37] In English, these connectives are expressed by the words "and" (conjunction), "or" (disjunction), "not" (negation), "if" (material conditional), and "if and only if" (biconditional).^[1][14] Examples of such compound sentences might include:

• Wikipedia is a free online encyclopedia that anyone can edit, and millions already have. (conjunction)
• It is not true that all Wikipedia editors speak at least three languages. (negation)
• Either London is the capital of England, or London is the capital of the United Kingdom, or both. (disjunction)^[f]

If sentences lack any logical connectives, they are called simple sentences,^[1] or atomic sentences;^[35] if they contain one or more logical connectives, they are called compound sentences,^[34] or molecular sentences.^[35]

Sentential connectives are a broader category that includes logical connectives.^[2][35] Sentential connectives are any linguistic particles that bind sentences to create a new compound sentence,^[2][35] or that inflect a single sentence to create a new sentence.^[2] A logical connective, or propositional connective, is a kind of sentential connective with the characteristic feature that, when the original sentences it operates on are (or express) propositions, the new sentence that results from its application also is (or expresses) a proposition.^[2] Philosophers disagree about what exactly a proposition is,^[11][2] as well as about which sentential connectives in natural languages should be counted as logical connectives.^[35][2] Sentential connectives are also called sentence-functors,^[38] and logical connectives are also called truth-functors.^[38]

Example argument

The following is an example of an argument within the scope of propositional logic:

Premise 1: If it's raining, then it's cloudy.

Premise 2: It's raining.

Conclusion: It's cloudy.

The logical form of this argument is known as modus ponens,^[40] which is a classically valid form.^[41] So, in classical logic, the argument is valid, although it may or may not be sound, depending on the meteorological facts in a given context. This example argument will be reused when explaining § Formalization.

Validity and soundness

An argument is valid if, and only if, it is necessary that, if all its premises are true, its conclusion is true.^[39][42][43] Alternatively, an argument is valid if, and only if, it is impossible for all the premises to be true while the conclusion is false.^[43][39]

Validity is contrasted with soundness.^[43] An argument is sound if, and only if, it is valid and all its premises are true.^[39][43] Otherwise, it is unsound.^[43]

Logic, in general, aims to precisely specify valid arguments.^[35] This is done by defining a valid argument as one in which its conclusion is a logical consequence of its premises,^[35] which, when this is understood as semantic consequence, means that there is no case in which the premises are true but the conclusion is not true^[35] – see § Semantics below.

Propositional variables

Since propositional logic is not concerned with the structure of propositions beyond the point where they cannot be decomposed any more by logical connectives,^[40][1] it is typically studied by replacing such atomic (indivisible) statements with letters of the alphabet, which are interpreted as variables representing statements (propositional variables).^[1] With propositional variables, the § Example argument would then be symbolized as follows:

Premise 1: ${\displaystyle P\to Q}$

Premise 2: ${\displaystyle P}$

Conclusion: ${\displaystyle Q}$

When P is interpreted as "It's raining" and Q as "it's cloudy" these symbolic expressions correspond exactly with the original expression in natural language. Not only that, but they will also correspond with any other inference with the same logical form.

When a formal system is used to represent formal logic, only statement letters (usually capital roman letters such as ${\displaystyle P}$, ${\displaystyle Q}$ and ${\displaystyle R}$) are represented directly. The natural language propositions that arise when they're interpreted are outside the scope of the system, and the relation between the formal system and its interpretation is likewise outside the formal system itself.

Gentzen notation

If we assume that the validity of modus ponens has been accepted as an axiom, then the same § Example argument can also be depicted like this:

${\displaystyle {\frac {P\to Q,P}{Q}}}$

This method of displaying it is Gentzen's notation for natural deduction and sequent calculus.^[44] The premises are shown above a line, called the inference line,^[16] separated by a comma, which indicates combination of premises.^[45] The conclusion is written below the inference line.^[16] The inference line represents syntactic consequence,^[16] sometimes called deductive consequence,^[46] which is also symbolized with ⊢.^[47][46] So the above can also be written in one line as ${\displaystyle P\to Q,P\vdash Q}$.^[h]

Syntactic consequence is contrasted with semantic consequence,^[48] which is symbolized with ⊧.^[47][46] In this case, the conclusion follows syntactically because the natural deduction inference rule of modus ponens has been assumed. For more on inference rules, see the sections on proof systems below.

Syntax

Given a set of atomic propositional variables ${\displaystyle p_{1}}$, ${\displaystyle p_{2}}$, ${\displaystyle p_{3}}$, ..., and a set of propositional connectives ${\displaystyle c_{1}^{1}}$, ${\displaystyle c_{2}^{1}}$, ${\displaystyle c_{3}^{1}}$, ..., ${\displaystyle c_{1}^{2}}$, ${\displaystyle c_{2}^{2}}$, ${\displaystyle c_{3}^{2}}$, ..., ${\displaystyle c_{1}^{3}}$, ${\displaystyle c_{2}^{3}}$, ${\displaystyle c_{3}^{3}}$, ..., a formula of propositional logic is defined recursively by these definitions:^{[2][15][51][i]}

Definition 1: Atomic propositional variables are formulas.

Definition 2: If ${\displaystyle c_{n}^{m}}$ is a propositional connective, and ${\displaystyle \langle }$A, B, C, …${\displaystyle \rangle }$ is a sequence of m, possibly but not necessarily atomic, possibly but not necessarily distinct, formulas, then the result of applying ${\displaystyle c_{n}^{m}}$ to ${\displaystyle \langle }$A, B, C, …${\displaystyle \rangle }$ is a formula.

Definition 3: Nothing else is a formula.

Writing the result of applying ${\displaystyle c_{n}^{m}}$ to ${\displaystyle \langle }$A, B, C, ...${\displaystyle \rangle }$ in functional notation, as ${\displaystyle c_{n}^{m}}$(A, B, C, ...), we have the following as examples of well-formed formulas:

• ${\displaystyle p_{5}}$
• ${\displaystyle c_{3}^{2}(p_{2},p_{9})}$
• ${\displaystyle c_{3}^{2}(p_{1},c_{2}^{1}(p_{3}))}$
• ${\displaystyle c_{1}^{3}(p_{4},p_{6},c_{2}^{2}(p_{1},p_{2}))}$
• ${\displaystyle c_{4}^{2}(c_{1}^{1}(p_{7}),c_{3}^{1}(p_{8}))}$
• ${\displaystyle c_{2}^{3}(c_{1}^{2}(p_{3},p_{4}),c_{2}^{1}(p_{5}),c_{3}^{2}(p_{6},p_{7}))}$
• ${\displaystyle c_{3}^{1}(c_{1}^{3}(p_{2},p_{3},c_{2}^{2}(p_{4},p_{5})))}$

What was given as Definition 2 above, which is responsible for the composition of formulas, is referred to by Colin Howson as the principle of composition.^[40][j] It is this recursion in the definition of a language's syntax which justifies the use of the word "atomic" to refer to propositional variables, since all formulas in the language ${\displaystyle {\mathcal {L}}}$ are built up from the atoms as ultimate building blocks.^[2] Composite formulas (all formulas besides atoms) are called molecules,^[50] or molecular sentences.^[35] (This is an imperfect analogy with chemistry, since a chemical molecule may sometimes have only one atom, as in monatomic gases.)^[50]

The definition that "nothing else is a formula", given above as Definition 3, excludes any formula from the language which is not specifically required by the other definitions in the syntax.^[38] In particular, it excludes infinitely long formulas from being well-formed.^[38] It is sometimes called the Closure Clause.^[54]

Constants and schemata

Mathematicians sometimes distinguish between propositional constants, propositional variables, and schemata. Propositional constants represent some particular proposition,^[58] while propositional variables range over the set of all atomic propositions.^[58] Schemata, or schematic letters, however, range over all formulas.^[38][1] (Schematic letters are also called metavariables.)^[39] It is common to represent propositional constants by A, B, and C, propositional variables by P, Q, and R, and schematic letters are often Greek letters, most often φ, ψ, and χ.^[38][1]

However, some authors recognize only two "propositional constants" in their formal system: the special symbol ${\displaystyle \top }$, called "truth", which always evaluates to True, and the special symbol ${\displaystyle \bot }$, called "falsity", which always evaluates to False.^[59][60][61] Other authors also include these symbols, with the same meaning, but consider them to be "zero-place truth-functors",^[38] or equivalently, "nullary connectives".^[51]

Interpretation (case) and argument

For a given language ${\displaystyle {\mathcal {L}}}$, an interpretation,^[66] valuation,^[52] Boolean valuation,^[67] or case,^[35][k] is an assignment of semantic values to each formula of ${\displaystyle {\mathcal {L}}}$.^[35] For a formal language of classical logic, a case is defined as an assignment, to each formula of ${\displaystyle {\mathcal {L}}}$, of one or the other, but not both, of the truth values, namely truth (T, or 1) and falsity (F, or 0).^[68][69] An interpretation that follows the rules of classical logic is sometimes called a Boolean valuation.^[52][70] An interpretation of a formal language for classical logic is often expressed in terms of truth tables.^[71][1] Since each formula is only assigned a single truth-value, an interpretation may be viewed as a function, whose domain is ${\displaystyle {\mathcal {L}}}$, and whose range is its set of semantic values ${\displaystyle {\mathcal {V}}=\{{\mathsf {T}},{\mathsf {F}}\}}$,^[2] or ${\displaystyle {\mathcal {V}}=\{1,0\}}$.^[35]

For ${\displaystyle n}$ distinct propositional symbols there are ${\displaystyle 2^{n}}$ distinct possible interpretations. For any particular symbol ${\displaystyle a}$, for example, there are ${\displaystyle 2^{1}=2}$ possible interpretations: either ${\displaystyle a}$ is assigned T, or ${\displaystyle a}$ is assigned F. And for the pair ${\displaystyle a}$, ${\displaystyle b}$ there are ${\displaystyle 2^{2}=4}$ possible interpretations: either both are assigned T, or both are assigned F, or ${\displaystyle a}$ is assigned T and ${\displaystyle b}$ is assigned F, or ${\displaystyle a}$ is assigned F and ${\displaystyle b}$ is assigned T.^[71] Since ${\displaystyle {\mathcal {L}}}$ has ${\displaystyle \aleph _{0}}$, that is, denumerably many propositional symbols, there are ${\displaystyle 2^{\aleph _{0}}={\mathfrak {c}}}$, and therefore uncountably many distinct possible interpretations of ${\displaystyle {\mathcal {L}}}$ as a whole.^[71]

Where ${\displaystyle {\mathcal {I}}}$ is an interpretation and ${\displaystyle \varphi }$ and ${\displaystyle \psi }$ represent formulas, the definition of an argument, given in § Arguments, may then be stated as a pair ${\displaystyle \langle \{\varphi _{1},\varphi _{2},\varphi _{3},...,\varphi _{n}\},\psi \rangle }$, where ${\displaystyle \{\varphi _{1},\varphi _{2},\varphi _{3},...,\varphi _{n}\}}$ is the set of premises and ${\displaystyle \psi }$ is the conclusion. The definition of an argument's validity, i.e. its property that ${\displaystyle \{\varphi _{1},\varphi _{2},\varphi _{3},...,\varphi _{n}\}\models \psi }$, can then be stated as its absence of a counterexample, where a counterexample is defined as a case ${\displaystyle {\mathcal {I}}}$ in which the argument's premises ${\displaystyle \{\varphi _{1},\varphi _{2},\varphi _{3},...,\varphi _{n}\}}$ are all true but the conclusion ${\displaystyle \psi }$ is not true.^[35][40] As will be seen in § Semantic truth, validity, consequence, this is the same as to say that the conclusion is a semantic consequence of the premises.

Propositional connective semantics

An interpretation assigns semantic values to atomic formulas directly.^[66][35] Molecular formulas are assigned a function of the value of their constituent atoms, according to the connective used;^[66][35] the connectives are defined in such a way that the truth-value of a sentence formed from atoms with connectives depends on the truth-values of the atoms that they're applied to, and only on those.^[66][35] This assumption is referred to by Colin Howson as the assumption of the truth-functionality of the connectives.^[40]

Semantics via truth tables

Since logical connectives are defined semantically only in terms of the truth values that they take when the propositional variables that they're applied to take either of the two possible truth values,^[1][35] the semantic definition of the connectives is usually represented as a truth table for each of the connectives,^[1][35][72] as seen below:

${\displaystyle p}$	${\displaystyle q}$	${\displaystyle p\land q}$	${\displaystyle p\lor q}$	${\displaystyle p\rightarrow q}$	${\displaystyle p\Leftrightarrow q}$	${\displaystyle \neg p}$	${\displaystyle \neg q}$
T	T	T	T	T	T	F	F
T	F	F	T	F	F	F	T
F	T	F	T	T	F	T	F
F	F	F	F	T	T	T	T

This table covers each of the main five logical connectives:^{[14][15][16][17]} conjunction (here notated ${\displaystyle p\land q}$), disjunction (p ∨ q), implication (p → q), biconditional (p ↔ q) and negation, (¬p, or ¬q, as the case may be). It is sufficient for determining the semantics of each of these operators.^[1][73][35] For more truth tables for more different kinds of connectives, see the article "Truth table".

Semantic truth, validity, consequence

Given ${\displaystyle \varphi }$ and ${\displaystyle \psi }$ as formulas (or sentences) of a language ${\displaystyle {\mathcal {L}}}$, and ${\displaystyle {\mathcal {I}}}$ as an interpretation (or case)^[n] of ${\displaystyle {\mathcal {L}}}$, then the following definitions apply:^[71][69]

• Truth-in-a-case:^[35] A sentence ${\displaystyle \varphi }$ of ${\displaystyle {\mathcal {L}}}$ is true under an interpretation ${\displaystyle {\mathcal {I}}}$ if ${\displaystyle {\mathcal {I}}}$ assigns the truth value T to ${\displaystyle \varphi }$.^[69][71] If ${\displaystyle \varphi }$ is true under ${\displaystyle {\mathcal {I}}}$, then ${\displaystyle {\mathcal {I}}}$ is called a model of ${\displaystyle \varphi }$.^[71]
• Falsity-in-a-case:^[35] ${\displaystyle \varphi }$ is false under an interpretation ${\displaystyle {\mathcal {I}}}$ if, and only if, ${\displaystyle \neg \varphi }$ is true under ${\displaystyle {\mathcal {I}}}$.^[71][81][35] This is the "truth of negation" definition of falsity-in-a-case.^[35] Falsity-in-a-case may also be defined by the "complement" definition: ${\displaystyle \varphi }$ is false under an interpretation ${\displaystyle {\mathcal {I}}}$ if, and only if, ${\displaystyle \varphi }$ is not true under ${\displaystyle {\mathcal {I}}}$.^[69][71] In classical logic, these definitions are equivalent, but in nonclassical logics, they are not.^[35]
• Semantic consequence: A sentence ${\displaystyle \psi }$ of ${\displaystyle {\mathcal {L}}}$ is a semantic consequence (${\displaystyle \varphi \models \psi }$) of a sentence ${\displaystyle \varphi }$ if there is no interpretation under which ${\displaystyle \varphi }$ is true and ${\displaystyle \psi }$ is not true.^[69][71][35]
• Valid formula (tautology): A sentence ${\displaystyle \varphi }$ of ${\displaystyle {\mathcal {L}}}$ is logically valid (${\displaystyle \models \varphi }$),^[o] or a tautology,^{[82][83][80][52]} if it is true under every interpretation,^[69][71] or true in every case.^[35]
• Consistent sentence: A sentence of ${\displaystyle {\mathcal {L}}}$ is consistent if it is true under at least one interpretation. It is inconsistent if it is not consistent.^[69][71] An inconsistent formula is also called self-contradictory,^[1] and said to be a self-contradiction,^[1] or simply a contradiction,^[84][85][86] although this latter name is sometimes reserved specifically for statements of the form ${\displaystyle (p\land \neg p)}$.^[1]

For interpretations (cases) ${\displaystyle {\mathcal {I}}}$ of ${\displaystyle {\mathcal {L}}}$, these definitions are sometimes given:

• Complete case: A case ${\displaystyle {\mathcal {I}}}$ is complete if, and only if, either ${\displaystyle \varphi }$ is true-in-${\displaystyle {\mathcal {I}}}$ or ${\displaystyle \neg \varphi }$ is true-in-${\displaystyle {\mathcal {I}}}$, for any ${\displaystyle \varphi }$ in ${\displaystyle {\mathcal {L}}}$.^[35][87]
• Consistent case: A case ${\displaystyle {\mathcal {I}}}$ is consistent if, and only if, there is no ${\displaystyle \varphi }$ in ${\displaystyle {\mathcal {L}}}$ such that both ${\displaystyle \varphi }$ and ${\displaystyle \neg \varphi }$ are true-in-${\displaystyle {\mathcal {I}}}$.^[35][88]

For classical logic, which assumes that all cases are complete and consistent,^[35] the following theorems apply:

• For any given interpretation, a given formula is either true or false under it.^[71][81]
• No formula is both true and false under the same interpretation.^[71][81]
• ${\displaystyle \varphi }$ is true under ${\displaystyle {\mathcal {I}}}$ if, and only if, ${\displaystyle \neg \varphi }$ is false under ${\displaystyle {\mathcal {I}}}$;^[71][81] ${\displaystyle \neg \varphi }$ is true under ${\displaystyle {\mathcal {I}}}$ if, and only if, ${\displaystyle \varphi }$ is not true under ${\displaystyle {\mathcal {I}}}$.^[71]
• If ${\displaystyle \varphi }$ and ${\displaystyle (\varphi \to \psi )}$ are both true under ${\displaystyle {\mathcal {I}}}$, then ${\displaystyle \psi }$ is true under ${\displaystyle {\mathcal {I}}}$.^[71][81]
• If ${\displaystyle \models \varphi }$ and ${\displaystyle \models (\varphi \to \psi )}$, then ${\displaystyle \models \psi }$.^[71]
• ${\displaystyle (\varphi \to \psi )}$ is true under ${\displaystyle {\mathcal {I}}}$ if, and only if, either ${\displaystyle \varphi }$ is not true under ${\displaystyle {\mathcal {I}}}$, or ${\displaystyle \psi }$ is true under ${\displaystyle {\mathcal {I}}}$.^[71]
• ${\displaystyle \varphi \models \psi }$ if, and only if, ${\displaystyle (\varphi \to \psi )}$ is logically valid, that is, ${\displaystyle \varphi \models \psi }$ if, and only if, ${\displaystyle \models (\varphi \to \psi )}$.^[71][81]

Semantic proof systems

${\displaystyle {\begin{array}{|c|c|c|c|}x_{0}&x_{1}&{\bar {x_{1}}}&x_{0}\&{\bar {x_{1}}}\\\hline 0&0&1&0\\0&1&0&0\\1&0&1&1\\1&1&0&0\end{array}}}$

Example of a truth table

Semantic proof systems rely on the concept of semantic consequence, symbolized as ${\displaystyle \varphi \models \psi }$, which indicates that if ${\displaystyle \varphi }$ is true, then ${\displaystyle \psi }$ must also be true in every possible interpretation.^[94]

Syntactic proof systems

Syntactic proof systems, in contrast, focus on the formal manipulation of symbols according to specific rules. The notion of syntactic consequence, ${\displaystyle \varphi \vdash \psi }$, signifies that ${\displaystyle \psi }$ can be derived from ${\displaystyle \varphi }$ using the rules of the formal system.^[94]