Foundations of Computation (Critchlow and Eck)

1.1: Propositional Logic

A proposition is a statement which is either true or false. In propositional logic, we take propositions as basic and see what we can do with them. Since this is mathematics, we need to be able to talk about propositions without saying which particular propositions we are talking about, so we use symbolic names to represent them. We will always use lowercase letters such as and to represent propositions. A letter used in this way is called a propositional variable. Remember that when I say something like “Let p be a proposition,” I mean “For the rest of this discussion, let the symbol p stand for some particular statement, which is either true or false (although I am not at the moment making any assumption about which it is).” The discussion has mathematical generality in that p can represent any statement, and the discussion will be valid no matter which statement it represents.

What we do with propositions is combine them with logical operators. A logical operator can be applied to one or more propositions to produce a new proposition. The truth value of the new proposition is completely determined by the operator and by the truth values of the propositions to which it is applied.1 In English, logical operators are represented by words such as “and,” “or,” and “not.” For example, the proposition “I wanted to leave and I left” is formed from two simpler propositions joined by the word “and.” Adding the word “not” to the proposition “I left” gives “I did not leave” (after a bit of necessary grammatical adjustment).

But English is a little too rich for mathematical logic. When you read the sentence “I wanted to leave and I left,” you probably see a connotation of causality: I because I wanted to leave. This implication does not follow from the logical combination of the truth values of the two propositions “I wanted to leave” and “I left.” Or consider the proposition “I wanted to leave but I did not leave.” Here, the word “but” has the same logical meaning as the word “and,” but the connotation is very different. So, in mathematical logic, we use s to represent logical operators. These symbols do not carry any connotation beyond their defined logical meaning. The logical operators corresponding to the English words “and,” “or,”and “not” are ∧, ∨, and ¬.

The operators ∧, ∨, and ¬ are referred to as conjunction, disjunction, and negation, respectively. (Note that is read as “ and ,” is read as “ or ,” and ¬p is read as “not p.”) 1It is not always true that the truth value of a sentence can be determined from the truth values of its component parts. For example, if p is a proposition, then “Sarah Palin believes p” is also a proposition, so “Sarah Palin believes” is some kind of operator. However, it does not count as a logical operator because just from knowing whether or not p is true, we get no information at all about whether “Sarah Palin believes p” is true.