Logic as a Tool
Chapter 1
Understanding Propositional Logic
Propositional logic is about reasoning with propositions. These are sentences that can be assigned a truth value: true or false. They are built from primitive statements, called atomic propositions, by using propositional logical connectives. The truth values propagate over all propositions through truth tables for the propositional connectives. In this chapter I explain how to understand propositions and compute their truth values, and how to reason using schemes of propositions called propositional formulae. I will formally capture the concept of logically correct propositional reasoning by means of the fundamental notion of propositional logical consequence.
1.1 Propositions and logical connectives: truth tables and tautologies
1.1.1 Propositions The basic concept of propositional logic is proposition. A proposition is a sentence that can be assigned a unique truth value: true or false.
Some simple examples of propositions include:
The following are not propositions (why?):
- Are you bored?
- Please, don't go away!
- She loves me.
- is an integer.
- This sentence is false.
Here is why. The first sentence above is a question, and it does not make sense to declare it true or false. Likewise for the imperative second sentence. The truth of the third sentence depends on who "she" is and who utters the sentence. Likewise, the truth of the fourth sentence is not determined as long as the variable is not assigned a value, integer or not. As for the last sentence, the reason is trickier: assuming that it is true it truly claims that it is false - a contradiction; assuming that it is false, it falsely claims that it is false, hence it is not false - a contradiction again. Therefore, no truth value can be consistently ascribed to it. Such sentences are known as self-referential and are the main source of various logical paradoxes (see the appetizer and Russell's paradox in Section 5.2.1).
1.1.2 Propositional logical connectives The propositions above are very simple. They have no logical structure, so we call them primitive or atomic propositions. From primitive propositions one can construct compound propositions by using special words called logical connectives. The most commonly used connectives are:
- not, called negation, denoted ;
- and, called conjunction, denoted (or sometimes );
- or, called disjunction, denoted ;
- if then , called implication, or conditional, denoted ;
- ...if and only if ..., called biconditional, denoted .
Remark 1 It is often not grammatically correct to read compound propositions by simply inserting the names of the logical connectives in between the atomic components. A typical problem arises with the negation: one does not say "Not the Earth is square." A uniform way to get around that difficulty and negate a proposition is to say "It is not the case that ."
In natural language grammar the binary propositional connectives, plus others like but, because, unless, although, so, yet, etc. are all called