Staring Back at Infinity

Basic Concepts in Symbolic Logic

Russell and Whitehead, around 1901 began working together on a book on logic and theoretical foundations of mathematics. This great book was called $ \textit{Principia Mathematica} $, which would later be recognized as a significant contribution to logic and foundational mathematics. Russell and Whitehed were highly influenced by Frege, Peano, and Schroder. What Russell and Whitehead did was basically developing an axiomatic basis for logic and mathematics. In the following sections we will introduce the basic concepts of symbolic logic to make the reader more comfortable with future subjects.

Propositional Logic

In this section we begin our study of propositional logic from $ \textit{Principia Mathematica} $. The main object of our investigation will be $ \textit{propositions} $ - sentences which are either true or false but not both. Thus, we are concerned with sentences such as $ \textit{"Friedrich Nietzsche was the author of the infamous book 'The World as Will and Representation' "} $, $ \textit{"Two plus two is equal to four"} $. Clearly the first of these two sentences is wrong but the second is true. However, a sentence such as $ \textit{"Who stole my pen?"} $ is not a proposition since it is neither true nor false. Hence, we will not be concerned with this type of sentence.

To carry out our study of propositions, we introduce the concept of $ \textit{propositional variable} $, which stands for an arbitrary but undetermined proposition. The letters $ p,q,r $ and so forth will be used to denote propositional variables.

Logical Connectives

We now turn to the first major topic in propositional logic, the question of how to form complicated propositions out of much more simplistic propositions. We can get around this problem if we consider that complex proposition as a function with more simplistic propositions as arguments. Thus, more complex propositions are formed from simpler propositions by means of functions that take propositions as arguments. Now, this brings out the question "what are the functions that yield more complex propositions from simpler ones?". They are contradictory functions (negation, "not"), logical sums, or disjunctive functions ("or"), logical products, or conjunctive function ("and"), the implicative function ("if then"). These functions as in the sense of independence is completely arbitrary since it depends on the functions that are defined primitively. Simplicity of primitive propositions and the symmetry behind handling them seem to be gained by taking the first two functions as primitive ones.

The contradictory function with argument $ p $, where $ p $ is any kind of proposition which is the negation of $ p $, that is, the proposition that means $ p $ is not true which is denoted by $ \neg p $. Therefore, $ \neg p $ is the contradictory function with $ p $ taken as the argument and it gives out the negation of $ p $.

The logical sum is a propositional function with two arguments that are $ p $ and $ q $ meaning $ p $ or $ q $ and it is denoted by $ p \lor q $. This means that at least one of the arguments inside this ordered $ \langle p,q \rangle $ pair is true. Thus, $ p \lor q $ is our propositional function that uses $ p $ and $ q $ as its arguments. However, $ p \lor q $ means at least $ p $ or $ q $ is true, not excluding the case in which both are true.

The logical product is also a propositional function that contains two arguments $ p $ and $ q $ where $ p $ and $ q $ are both true. This operation is denoted by $ p \land q $. Thus, $ p \land q $ is the logical product that takes $ p $ and $ q $ as its arguments. It can be also denoted by $ p \cdot q $ where it is called $ \textit{Logical Product of} ~~~ p ~~~ \textit{and} ~~~ q $. It can easily be understood that this function can be defined in terms of the two preceding functions. For when $ p $ and $ q $ are both true, it must be false that either $ \neg p $ or $ \neg q $ is true. Hence in this section $ p \land q $ is nothing but a shortened form of,

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

The implicative function is a propositional function with two arguments $ p $ and $ q $ and it implies the proposition where either $ \neg p $ or $ q $ is true, that is, it is the proposition where $ \neg p \lor q $. In this case if $ p $ is true, $ \neg p $ is false, and accordingly the only alternative left by the proposition $ \neg p \lor q $ is $ q $ is true. To put it differently if $ p $ and $ \neg p \lor q $ are both true at the same time then $ q $ is true. Hence, $ \neg p \lor q $ will be quoted as stating the proposition where $ \textit{"p implies q"} $ and it is denoted by $ p \rightarrow q $.

Remark 1. There is an apparent ambiguity in reading propositions like $ \neg p \lor q $. The proposition can be read as either $ (\neg p) \lor q $ (i.e., as the logical sum of $ \neg p $ and $ q $ or as $ (\neg p \lor q) $ (i.e., as the result of applying the contradictory function to $ p \lor q $). This ambiguity can be easily resolved by understanding that the notation $ \neg $ have a stronger effect compared to $ \lor , \land , \rightarrow $. Thus, $ \neg p \lor q $ is read as $ (\neg p) \lor q $ rather than $ (\neg p \lor q) $. In a similar sense, we must understand that the notations $ \lor , \land $ have stronger effects compared to $ \rightarrow $. For example, the proposition $ p \lor q \rightarrow r $ should be read as $ (p \lor q) \rightarrow r $, and the proposition $ \neg p \land q \rightarrow r \lor p $ should be read as $ ((\neg p) \land q) \rightarrow (r \lor p) $.

Truth Values and Truth Tables

Having developed a language for understanding propositional logic, we turn to the task of understanding how the notion of truth connects with our symbolic, propositional logic. In particular, we develop a framework for understanding the truth and falsity of complex propositions based on the truth and falsity of simpler ones.

Remark 2. The truth-values of the implication $ p \rightarrow q $ is true if and only if $ \neg p $ is true or $ q $ is true; so, in particular, we regard the statements of the form "if $ p $, then $ q $" as true if $ \neg p $ true. This way of thinking on this "if, then" statements are unusual, but one may understand the motivation for doing so if one thinks of $ p \rightarrow q $ as being analogous to a statement that if $ p $ holds true, then $ q $ will also hold true. If it so happens that $ \neg p $ is true, then the statement is unbroken regardless of the truth-value of $ q $, and so $ p \rightarrow q $ is true. The statement is only broken if and only if $ \neg p $ is false and $ q $ is also false. This is the only situation in which we regard $ p \rightarrow q $ as being false. Note that an implication "if $ p $, then $ q $" which is true because $ p $ is false is referred to as $ \textit{vacuously true} $.

We now understand how to determine the truth-value of a compound proposition from the truth values of the propositional variables of which it is composed. But we can do better than this. We can design a general method, which will allow us to calculate all possible truth-values of a compound proposition from all possible truth-values of the propositional variables of which it is composed. This method is called $ \textit{Truth Tables} $, tables which lists all the possible truth-values of the propositional variables contained in a compound proposition along with the corresponding truth-values of the compound proposition itself. For example, if $ p $ is a propositional variable, then the truth table of the compound proposition $ \neg p $ is as follows:

$$\begin{array} {|r|r|}\hline p & \neg p \\ \hline T & F \\ \hline F & T \\ \hline \end{array}$$

Here the possible truth values for the propositional variable $ p $ can be seen on the left column, and the contradictory, compound propositional variable $ \neg p $ can be seen on the right column. Truth is denoted by $ T $ and falsehood is denoted by $ F $.

Compound propositions which contain more propositional variables have more complicated truth tables. For example, if $ p $ and $ q $ are propositional variables, then the truth table for the proposition $ p \lor q $ is:

$$\begin{array} {|r|r|}\hline p & q & p \lor q \\ \hline T & T & T \\ \hline T & F & T \\ \hline F & T & T \\ \hline F & F & F \\ \hline \end{array}$$

When three or more propositional variables occur in a compound proposition, care must be taken to guarantee that every possible combination of truth-values of the propositional variables appears in the truth table. For example, the truth table of the proposition $ (p \land q) \rightarrow r $ looks as follows:

$$\begin{array} {|r|r|}\hline p & q & r & p \land q & (p \land q) \rightarrow r \\ \hline T & T & T & T & T \\ \hline T & T & F & T & F \\ \hline T & F & T & F & T \\ \hline T & F & F & F & T \\ \hline F & T & T & F & T \\ \hline F & T & F & F & T \\ \hline F & F & T & F & T \\ \hline F & F & F & F & T \\ \hline \end{array}$$

One can understand that the truth-values of the propositional variables $ p $, $ q $, and $ r $ are listed systematically in this truth table: the truth values of $ p $ are written in alternating groups of four, those for $ q $ are written in alternating groups of two, and those for $ r $ alternate with each successive entry. This method of organizing the entries in the truth table guarantees that every possible assignment of truth-values appears in the truth table. A similar, organized table may be used in constructing the truth table of a compound proposition that contains more than three propositional variables.

Notice that the truth-values of the compound proposition $ p \land q $ are listed in the truth table in order to allow us to compute the truth-values of the more complicated proposition $ (p \land q) \rightarrow r $ more easily. When constructing the truth table of a complicated compound proposition, including truth-values for constituent compound proposition is often helpful.