The logical symbolism by which we symbolize the sentences of a natural language can also be considered a language. Each language has syntactic rules, which determine how starting from the words of the language more complex expressions can be formed. Thereby the syntactic rules distinguish the well-formed (grammatically correct) expressions of the language from the non-well-formed (grammatically incorrect) possible sequences of words. The syntactic rules constitute the syntax of the language. Considering the syntax, we put aside the question of what the words of the language mean or which of its sentences are true and which false – we are only interested in the question of what possible sequences of words are grammatically correct and what are not. The meanings of the words and the truth or falsity of the sentences of a language is a subject of its semantics. We will now formulate some syntactic rule for the symbolic language of propositional logic we use, thus strictly defining its syntax.
The “words” of the language of propositional logic are the following symbols:
The syntactic rules of the language of propositional logic are as follows:
Together, these seven rules constitute a definition of the notion of a well-formed formula (or briefly formula) of propositional logic. Such definitions are called recursive. It is characteristic of them that the defined term (“well-formed formula” in our case) is used in the defining expression (the definiens). This does not make them circular, however, as is for example the “definition” of the term “beautiful” by the expression “something that is beautiful”. Generally, the purpose of a definition of a general term (a word or phrase that is true or false of things) is to specify what things fall under the term and what do not. This is usually achieved by giving a necessary and sufficient condition for falling under the term. The problem with circular definitions is not that they do not give a necessary and sufficient condition (to be beautiful is a necessary and sufficient condition for something to be beautiful) but that it is impossible to determine by them whether something falls under the term or not because when trying to apply them we spin in a circle. To determine whether an object is beautiful by the above circular definition, we need to determine if it is beautiful, but to determine that, we need to determine if it is beautiful, ... and so on. Although the recursive definition of “well-formed formula” uses the same term, it enables us to effectively determine for each sequence of symbols whether it falls under the defined term. This is so because of the following. First, the definition specifies what are the atomic formulas – the simple formulas that do not contain other formulas as parts. This is done in rule i). Then rules ii) to vi) specify how starting from atomic formulas and using logical connectives more and more complex formulas can be formed. Lastly, rule vii) excludes from the well-formed formulas all sequences of symbols that are not constructed in accordance with the previous rules. In effect, the definition tells us that an expression is a well-formed formula if and only if it is constructed from certain elements (which are explicitly specified) by certain rules (which are explicitly specified). The result is that, although there are infinitely many well-formed and non-well-formed sequences of symbols, for each given sequence we can check by the definition (in a finite number of steps) whether it is well-formed.^{1}
For example, “((p∧q)→(¬r∧¬s))” is a well-formed formula of propositional logic according to the above definition because of the following. By i), “p” and “q” are (well-formed) formulas. Therefore, by iii), “(p∧q)” is a formula. On the other hand, “r” and “s” are formulas by i). Therefore, by ii) “¬r” and “¬s” are formulas, and by iii) such is also “(¬r∧¬s)”. Since “(p∧q)” and “(¬r∧¬s)” are formulas, “((p∧q)→(¬r∧¬s))” is a formula by v).
According to rules iii)–vi), we should always enclose conjunctions, disjunctions, conditionals and biconditionals in parentheses. The reason is that later they may become parts of other formulas in which they must be in parentheses. For example, from “r” and “s” we are allowed to form by iii) “(r∧s)”, not “r∧s”, because if we later connect it, say, with “p” by conditional, in the first case we will get “p→(r∧s)” and in the second we will get “p→r∧s”, which is ambiguous – it is not clear whether it should be interpreted as a conditional (of “p” and “r∧s”) or as a conjunction (of “p→r” and “s”).
Putting parentheses around formulas derived by rules (iii)–(vi) results in formulas being enclosed in parentheses even if they are not part of another formula. For example, the formula we used as an illustration above was “((p∧q)→(¬r∧¬s))”, not “(p∧q)→(¬r∧¬s)”. For ease of writing, we usually omit the outermost parentheses. We write “(p∧q)→(¬r∧¬s)” instead of “((p∧q)→(¬r∧¬s))” but officially the first expression is an abbreviation for the latter.
Although negations are compound formulas like conjunctions, disjunctions … etc., by rule ii) we do not enclose ¬α in parentheses. For example, a well-formed formula is “¬¬p”, not “(¬(¬p))”. The result is that if there is no opening parenthesis after a negation sign, the latter refers to the first sentence after it. So, the first negation (from left to right) in “¬¬p” refers to “¬p”, which is the first sentence after it, and the second refers to “p”. Similarly, “¬” in “¬p∧q” refers to “p”, not to “p∧q”. If we what it to refer to “p∧q”, the latter must be enclosed in parentheses – “¬(p∧q)”.
The only type of brackets we officially have are “(” and “)”. However, we may use other types of brackets for easier reading. For example, we will treat “{[¬p→(q∧¬r)]∨p}↔(r∧s)” as the same formula as “((¬p→(q∧¬r))∨p)↔(r∧s)”.
The syntactic structure of any (well-formed) formula can be visualized by means of its so-called syntax tree, which shows the “history” of the formation of the formula by means of the syntactic rules. For example, the formula “(p∧q)→(¬r∧¬s)” has the following syntax tree:
(p∧q) → (¬r∧¬s) | |||
p ∧ q | ¬r ∧ ¬s | ||
p | q | ¬r | ¬s |
r | s |
The syntax tree has the form of a upside down tree with propositional letters at the terminal nodes at the bottom (the leaf nodes); in our case, they are “p”, “q”, “r” and “s”. These consisting of a single propositional letter formulas are called atomic. The history of the formation of the formula is given in the bottom-up direction. Moving upwards, “(p∧q)” is formed from “p” and “q” by rule iii); “¬r” and “¬s” are formed from “r” and “s”, respectively, by ii); … and so on until we get to the whole formula at the top of the tree (the root node). The last step, in which the whole formula is constructed, shows the formula’s main logical connective and the form of the whole expression. In the example, the main logical connective is conditional and the whole formula is a conditional as it is obtained by connecting “(p∧q)” and “(¬r∧¬s)” with conditional.
Formulas that are parts of a formula are called its subformulas. The syntax tree shows all subformulas of a formula. These are the formulas in the nodes of the tree. In the example, the subformulas of “(p∧q)→(¬r∧¬s)” in increasing complexity are “p”, “q”, “r”, “s”, “¬r”, “¬s”, “p∧q”, “¬r∧¬s” as well as “(p∧q)→(¬r∧¬s)” itself, which is considered a subformula of itself.
While in the syntax of propositional logic we use syntactic rules to define well-formed formulas, in the semantics of propositional logic we use semantic rules to define the formulas’ truth conditions – when a well-formed formula is true and when false. To each of the syntactic rules, there corresponds a semantic rule, which defines how the truth value of a formula obtained by the syntactic rule depends on the truth values of its constituents. In fact, we are already acquainted with the semantic rules because the truth tables of negation, conjunction, disjunction, conditional, and biconditional are their visualizations.
Here are the semantic rules:
The following are the truth tables of all the logical connectives we introduced earlier:
α | β | α ∧ β | α ∨ β | α → β | α ↔ β |
T | T | T | T | T | T |
T | F | F | T | F | F |
F | T | F | T | T | F |
F | F | F | F | T | T |
α | ¬α |
T | F |
F | T |
These tables are based on the semantic rules, not the other way around. Tables are a way to visualize the rules.
By the semantic rules, every compound formula (however complex) receives a truth value for every interpretation of its propositional letters. The propositional letters stand for certain (usually simple) sentences (propositions). Since each sentence is either true or false, the propositional letters are interpreted as truth values – T or F. This explains semantic rule I). By the other semantic rules, based on the truth values of the propositional letters, each subformula receives (in the order of increasing complexity) a certain truth value, including the formula itself. This process of truth value determination goes upwards along the syntax tree and is possible because to every syntactic rule there is a corresponding semantic rule. To illustrate, consider the formula “(p∧q)→(¬r∧¬s)”, which we used while introducing syntax trees above, and assume that the interpretation of its propositional letters is such that “p” and “q” have the value F, and “r” and “s” the value T. Then its subformulas (including the formula itself) receive the following truth values:
(p∧q) → (¬r∧¬s) | |||
T | |||
p ∧ q | ¬r ∧ ¬s | ||
F | F | ||
p | q | ¬r | ¬s |
F | F | F | F |
r | s | ||
T | T |
The diagram shows how the truth values of “p”, “q”, “r” and “s” determine (from bottom to top) the truth values first of the subformulas of “(p∧q)→(¬r∧¬s)” and finally of the formula itself. “p∧q” has the value F because “p” and “q” have the value F (a conjunction is true only if both conjuncts are true); “¬r” has the value F because “r” has the value T; … etc. The whole formula has the value T for this interpretation of its propositional letters.
Instead of the diagram above, the truth value of the formula for this interpretation of its propositional letters can be determined by a table. For this purpose, in the first row of the table we place from left to right the subformulas and finally the formula itself in the order of increasing complexity and then determine (again from left to right) their truth values:
p | q | r | s | p∧q | ¬r | ¬s | ¬r∧¬s | (p∧q)→(¬r∧¬s) |
F | F | T | T | F | F | F | F | T |
The truth values of the propositional letters in the first four columns are such as we arbitrarily interpreted them to be. In the fifth column, the truth value of “p∧q” is determined from the truth values of “p” and “q” in the first and the second column by the truth table of conjunction (semantic rule III). The truth values of “¬r” and “¬s” in the sixth and the seventh column are determined from the truth values of “r” and “s” in the third and the fourth column by the truth table of negation … etc. Generally, the truth value of each compound subformula is determined from the truth values of one or two subformulas to the left of it in the table. Thus, moving from left to right, in the rightmost column we obtain the truth value of the whole formula.
The convenience of the table compared to the diagram is that it can be supplemented with other rows for other combinations of truth values of the propositional letters. Adding, for example, a new row for the case when all four propositional letters have the value T, we get that then the whole formula has the value F:
p | q | r | s | p∧q | ¬r | ¬s | ¬r∧¬s | (p∧q)→(¬r∧¬s) |
F | F | T | T | F | F | F | F | T |
T | T | T | T | T | F | F | F | F |
As we continue to add new rows for other possible combinations of truth values of the propositional letters in the formula, we will finally exhaust all combinations. When this happens, the table will have 16 rows because 16 is the number of all possible combinations of truth values of four propositional letters. Such a complete table containing each combination of truth values of the propositional letters in a formula is called its truth table. Such a table can be made for each formula. As an example, the truth table of “¬(p→q)∨¬q” is given below:
p | q | p→q | ¬(p→q) | ¬q | ¬(p→q)∨¬q |
T | T | T | F | F | F |
T | F | F | T | T | T |
F | T | T | F | F | F |
F | F | T | F | T | T |
As there are two proportional letters in the formula, the possible combinations of truth values for them are four: one corresponding to the case when “p” and “q” are true; one to the case when “p” is true, and “q” is false; … etc. There is a row in the table for each possible case. In each row, the truth value of the whole formula is determined by determining the truth values of its subformulas from left to right (i.e. in the direction of increasing complexity) until the truth value of the whole formula is reached in the last column. In the third column, the truth values below “p→q” are determined from the truth values of “p” and “q” in the first and second column by the truth table of conditional. The truth values of “¬q” in the fifth column are determined from the truth values of “q” in the second column by the truth table of negation (on each row, the values below “¬q” are the opposite of those below “q”). The truth values of “¬(p→q)” in the fourth column are determined in the same way from the values of “p→q”. Finally, in the last column, the truth values of the whole formula are determined from the truth values in the previous two columns by the truth table of disjunction. The table shows that a sentence of the form “¬(p→q)∨¬q” is true either when p and q are false (last row) or when p is true and q is false (second row); otherwise it is false.
If a formula has only one propositional letter, its truth table will have two rows – one for the case when the letter has the value T and one for the case when it has the value F. “(р∨¬р)→¬р” is an example:
p | ¬p | p∨¬p | (p∨¬p)→¬p |
T | F | T | F |
F | T | T | T |
The truth values under “¬p” are the opposite of those under “p”. The values under “р∨¬р” are derived from those under “p” and “¬p” according to the truth table of disjunction. The values of the entire formula in the last column are derived from the values in the previous two columns by the truth table of conditional, but since for determining the truth value of a conditional the order of the two sentences matters, it is important to look first at the third column (the values of the antecedent) and then at the second column (the values of the consequent).
If a truth table has two rows (i.e., if the formula to which the table belongs has only one letter), we will write in the first column under the letter first “T” and then “F”. I.e., each truth table of a one letter formula will start like this:
T |
F |
When the propositional letters are two (e.g., “p” and “q”), for each of the two possible cases for “p” (which we continue to arrange in the same way – first T, then F) there are two cases for “q”. Therefore, we double each value under “p” and combine each pair of repeating values with the two values for “q” arranged in the same way – first T, then F. So, as a rule, the truth table of a two-letter formula will start like this:
T | T |
T | F |
F | T |
F | F |
When arranging the combinations in a truth table of a three-letter formula, we will follow the same procedure: we start from the arrangement for a two-letter formula, i.e. “TT”, “TF”, “FT”, “FF”; we double each of these four combinations because of the third letter (i.e. the sequence in the first two columns becomes “TT”, “TT”, “TF”, “TF”, “FT”, “FT”, “FF”, “FF”); and then we combine each pair of repeating values with the two values of the third letter putting first T, then F. So, the arrangement will be as follows:
T | T | T |
T | T | F |
T | F | T |
T | F | F |
F | T | T |
F | T | F |
F | F | T |
F | F | F |
Formulated recursively for any number of propositional letters, the way we order the combinations of truth values in a truth table is as follows. If the formula has one propositional letter, we write “T” in the first row and “F” in the second. If the letters are two, for the first letter we follow the same order but we duplicate each row and for the second letter write again first “T”, then “F”. If the letters are three, for the first two letters we follow the order of the previous case but we duplicate each row and for the third letter write first “T”, then “F” … etc. If the letters are n, for the first n-1 letters we follow the same order as in the previous case (that of n-1-letter formula) but we duplicate each row and for the nth letter write first “T”, then “F”.
From the way the combinations of truth values are arranged, it can be seen that each addition of a propositional letter doubles the number of rows. For one letter, the rows are 2; for two letters, the rows are 2.2 = 2^{2} = 4; for three letters, the rows are 2.2.2 = 2^{3} = 8; … etc.; for n letters the rows are 2^{n}.
Here is an example of a truth table of a three-letter formula – the table of “p→¬(q∨¬r)”:
p | q | r | ¬r | q∨¬r | ¬(q∨¬r) | р→¬(q∨¬r) |
T | T | T | F | T | F | F |
T | T | F | T | T | F | F |
T | F | T | F | F | T | T |
T | F | F | T | T | F | F |
F | T | T | F | T | F | T |
F | T | F | T | T | F | T |
F | F | T | F | F | T | T |
F | F | F | T | T | F | T |
The construction of the table differs from that of a one- or two-letter formula only in there being more rows. The values under “¬r” are opposite to those under “r”; the values of “q∨¬r” are determined from those of “q” and “¬r” by the truth table of disjunction; the values of “¬(q∨¬r)” are opposite to those in the previous column; the values of the whole formula in the last column are determined from those of “p” and “¬(q∨¬r)” (in that order) by the truth table of conditional.
Depending on its truth table, each formula falls into one of the following three groups:
Tautologies are formulas that always get the value T (regardless of the truth values of their propositional letters). “Tautologies” are also called the natural language sentences that have the form of tautologies, i.e. that are symbolized by such formulas. Such sentences are also called logically true. They have the characteristic property of being true regardless of the facts. For example, we do not need to do any historical research to establish that the sentence “Socrates had or did not have a younger brother” (“р∨¬р”) is true. We do not even need to know who Socrates is.
An example of a tautology, which (unlike “p∨¬p”) is not obvious, is “[(р→q)→p]→p”:
p | q | р→q | (р→q)→p | [(р→q)→p]→p |
T | T | T | T | T |
T | F | F | T | T |
F | T | T | F | T |
F | F | T | F | T |
We call contradictions the formulas that always get the value F (regardless of the values of their propositional letters). Contradictions are also called the natural language sentences that are symbolized by such formulas. Such sentences are also called logically false. As with the logically true sentences, we do not need to turn to reality to determine their truth value. That they are false is contained in their very meaning. Whatever the facts are, clearly the sentence “Socrates had and did not have a younger brother” (“p∧¬p”) will be false:
p | ¬p | p∧¬p |
T | F | F |
F | T | F |
(1) Is each of the following expressions a well-formed formula? |
1) | ¬(р∧¬q) |
2) | ¬(¬r) |
3) | [(q→p)]→q∧r |
4) | [¬(p→q)→p]→¬¬¬p |
5) | p→(¬r∧¬q)∨(q∧¬s) |
6) | q∧¬¬¬¬q |
7) | [¬(p)∧q]∨r |
8) | {[(s→s)→s]→s}→s |
9) | (q→q)→(r→r) |
10) | q→(q→r)→r |
11) | ¬¬[¬p→(r∨q)] |
12) | p∧(q∨r)∧s |
(2) Specify the subformulas of each formula. |
1) | (¬p∧r) ∨ (p↔¬q) |
2) | [p∧(q∨¬r)] ↔ [(p∧q)∨¬r] |
3) | (p∧¬p) ↔ (r→¬q) |
4) | [(p→¬q)→r] → (¬r∧¬p) |
(3) For each of the following formulas, determine whether it is atomic, a negation, a conjunction … etc. |
1) | ¬[(q→p)∧r]∧p |
2) | ¬r→s |
3) | ¬(p∨q)∧¬(q∨p) |
4) | ¬¬[(p↔q)→(p↔q)] |
5) | q |
6) | (¬¬p→q)∧(q→p) |
7) | ¬q∨(p→q) |
8) | ¬¬p∧¬¬r |
9) | ¬q∨¬(¬p∧q) |
10) | p∧¬[(p∨q)→r] |
(4) Construct the truth table of each formula and specify whether it is a tautology, a contradiction, or contingent. |
1) | p → (q→p) |
2) | ¬(p∨q) → (p∧q) |
3) | (p→¬q) → ¬p |
4) | [p→(¬q∨r)] ∨ (¬p∨q) |
5) | (¬p∨¬q) → ¬(p∧q) |
6) | (p→q) → (¬q→¬p) |
7) | (p∧¬q) ∨ (¬p∧q) |
8) | (¬p∧¬q) ↔ (p↔¬q) |
9) | [(p∨q)∧¬(p∧q)] ↔ (p↔¬q) |
10) | (p→q) → [(¬r∨p)→(r∧¬q)] |
11) | [(¬p∨¬q)∧¬r] → [(p∧q)↔r] |
12) | [(p→q)→r] ↔ [p→(q→r)] |
(5) Show with truth tables that the following formulas are tautologies. |
1) | p ∨ ¬p |
2) | p → [q→(p∧q)] |
3) | {p∨[(¬q∨r)∧p]} → (p∨¬r) |
4) | [(p→¬q)∧q] → ¬p |
5) | [(p∨q)∧¬p] ↔ (¬p∧q) |
6) | [(p∧q)→r] → [p→(q→r)] |