PHIL 109 · Introduction to Formal Reasoning and Decision Making

1 The language of propositional logic

1.1 Introduction

Suppose you don’t know whether “Leona” is the name of an animal or the name of the statue decorating the entrance to my house. I then tell you that Leona is a cat, and that if Leona is a cat then Leona is an animal. Because you trust me, you come to believe that Leona is an animal on the basis of my claims that Leona is a cat and that if Leona is a cat then Leona is an animal (you didn’t need me to tell you that this last claim is true, obviously). We can reconstruct what I did in the form of an argument (for now, this is just an example of an argument—we’ll give a more formal treatment of that notion later on):

• (1) Leona is a cat.
• (2) If Leona is a cat, then Leona is an animal.
• $\therefore$ Leona is an animal.

In the argument above, the enumerated sentences are its premises, and the “$\therefore$” symbol (read as “therefore”) precedes the conclusion. That argument has an interesting feature: it’s impossible for its premises to be true and its conclusion false. By contrast, consider the following argument:

• (1) Leona is an animal.
• (2) If Leona is a cat, then Leona is an animal.
• $\therefore$ Leona is a cat.

This second argument does not have the feature we identified in the first one: it is possible for its premises to be true and its conclusion false. Our aim in this first part is to give a mathematical model of that feature in question, which logicians call validity. To say that an argument is valid is not the same as saying that it is a good argument. Some valid arguments are really bad (we’ll see examples later). And some very good arguments are not valid. Nevertheless, the notion of validity plays an important role in the evaluation of some arguments, so we will start by analyzing it. Our strategy to analyze the notion of validity will be to construct an artificial language, the language of propositional logic (PL). Inside PL we can then construct a toy model of the notion of validity, tautological validity.

1.2 Sentences and propositions

Unsurprisingly, propositions will be the main elements of PL. There is a tight connection between propositions and some sentences, but there are also important differences.

A proposition is a bit of information, something which can be true or false. Thus, that Leona is a cat is a proposition, and so is the proposition that Leona is an animal. It is either true or false that Leona is a cat, and also either true or false that Leona is an animal. Whether you know if Leona is a cat or an animal does not affect the fact that those are indeed propositions, for the defining characteristic of a proposition is that it can be true or false, not that anyone knows whether it is true or false.

“Leona is a cat” is a sentence of English. What is the relationship between that sentence and the proposition that Leona is a cat? Could we perhaps identify them? Sentences, after all, can be true or false (at least some of them, anyway, and certainly “Leona is a cat”). No, we will not identify sentences and propositions. Rather, we will say that some sentences express a proposition. For instance, “Leona is a cat” expresses the proposition that Leona is a cat. But that very proposition can be expressed by other sentences. For instance, the sentence “Leona is a member of the species felis catus” expresses that same proposition. And so do the sentences “Leona es una gata” and “Leona est une chatte”. Because all of those sentences are different from each other, we cannot identify any of them with the proposition that Leona is a cat. Rather, that proposition is what all those different sentences express. “Leona es una gata” is a good translation to Spanish of “Leona is a cat” precisely because both sentences express the same proposition.¹

Just as different sentences can express the same proposition, so too the same sentence can express different propositions. For instance, the sentence “I am hungry” expresses one proposition when I say it and a different one when you say it. So that is another reason why we cannot identify propositions with sentences.

But there is still a tight connection between sentences and propositions, because we said that sentences can express propositions. Another way of saying the same thing is that propositions can be the meaning, or the content, or that which is said by, some sentences. The qualifier “some” is important here, because not all sentences express propositions. Sentences in the imperative and interrogative mood usually do not (“Close the door” expresses a command, and “Is the door closed?” a question, but neither commands nor questions can be true or false). Should we say, then, that a proposition is the meaning of a sentence in the indicative mood? Not really, because some sentences in the indicative mood do not have a content which can be true or false—or at least that is what some philosophers would say. Suppose, for instance, that I say “That is green” while pointing at nothing in particular. I have not managed to express any truth-evaluable content, but yet I have uttered a sentence in the indicative mood. For a different kind of example take the sentence “I apologize”. According to some philosophers, what that sentence expresses is not a proposition that can be true or false—in particular, it does not express the proposition that the speaker apologizes. Rather, in uttering that sentence the speaker is apologizing.²

So what can we say, then, about the relationship between sentences and propositions? We can say that a sentence expresses a proposition when its content (or its meaning, or what the sentence says) is something that can be true or false. Usually (but not always) sentences in the indicative mood will be used to convey information, and thus will express propositions.

1.3 Atomic vs. molecular propositions

Some propositions have other propositions as parts. Consider, for instance, the proposition:

Leona is a cat, and she is beautiful

Inside that proposition we can find these two propositions:

Leona is a cat.

Leona is beautiful.

For that reason, we will say that the proposition Leona is a cat, and she is beautiful is a molecular proposition. By contrast, consider the proposition Leona is a cat. That proposition does arguably have parts—for instance, one part corresponding to Leona, and another one referring to the class of cats. But those parts are not themselves propositions. We will call propositions that do not have other propositions as parts atomic propositions. Thus, just as chemical molecules have atoms as parts but atoms do not themselves have atoms as parts (although they do have other parts, such as electrons), so too molecular propositions have other propositions as parts but atomic propositions do not have other propositions as parts (although they do have other parts).

In chemistry, the “glue” that binds atoms together into molecules are electromagnetic interactions. What is the glue that binds atomic propositions into molecular ones? They are truth-functional connectives. In the case of Leona is a cat, and she is beautiful, the truth-functional connective is the particle “and”—known as conjunction in logic. It is a truth-functional connective because we can think of it as a function that takes truth-values as arguments and delivers truth-values as values. The definition of conjunction is that it delivers a true proposition when applied to two true propositions as arguments, and a false proposition in every other case. Thus, because it is true that Leona is a cat and is also true that Leona is beautiful, it is true that Leona is a cat, and she is beautiful.

The other truth-functional connectives that we will work with are: negation, (inclusive) disjunction, material conditional, and material biconditional. In this chapter we will define those truth-functional operations both syntactically and semantically in the context of our language of propositional logic, and in chapter 2 we will study the connections between that language and natural languages such as English.

1.4 The syntax of PL

So far we have been using sentences in English to express propositions. PL, however, is not English. It has an indefinite number of atomic sentence letters, which we write as upper-case letters of the alphabet, with indices if needed. Thus, the following are all atomic sentence letters of Propositional Logic (in what follows, we abbreviate the language as PL): $A, B, C, \ldots, P_{1}, S_{323}, \ldots$. Such a letter can be used to stand for an atomic proposition, but it is a symbol of PL, not a proposition. For instance, if we let $L$ stand for the proposition that Leona is a cat and $B$ for the proposition that Leona is beautiful, then the English sentence Leona is a cat, and she is beautiful could be translated into PL as $L \land B$.

As we said, we will work with five truth-functional connectives: negation, conjunction, disjunction, material conditional, and material biconditional. The symbols we will use for those connectives are as follows:

Truth-functional connectives

Negation: $\neg$

Conjunction: $\land$

Disjunction: $\lor$

Conditional: $\rightarrow$

Biconditional: $\leftrightarrow$

So far we have truth-functional connectives and atomic sentence letters as part of PL. But we need one more component. For consider the string of symbols $L \land B \lor C$. Is that supposed to be a conjunction of $L$ with $B \lor C$ or a disjunction of $L \land B$ with $C$? That string of symbols is ambiguous between those two meanings, so we need a way to syntactically distinguish between them. Parentheses to the rescue: we can distinguish them by writing $L \land (B \lor C)$ or $(L \land B) \lor C$. That completes our language of PL:

Language of Propositional Logic

Atomic sentence letters: $A, B, C, \ldots, A_{1}, B_{1}, C_{1}, \ldots$

Truth-functional connectives: $\neg, \land, \lor, \rightarrow, \leftrightarrow$.

Parentheses: (, ).

We will soon start writing sentences of PL and analyzing their structure. To do so, however, we need to talk about sentences of PL. PL itself is not complex enough to allow us to use it to talk about itself. So instead we will use English to talk about PL, just as we have been doing so far. For instance, the sentence “Parentheses are part of the vocabulary of PL” is an English sentence about PL. But we are going to augment English with some math vocabulary in order to be able to state general truths about PL. For instance, we want to distinguish between those sentences of PL that are grammatically correct (we’ll call them well-formed sentences, or wffs for short) from those that are not. We can point at instances of that distinction—for instance, we can say that whereas $A \lor B$ is grammatically correct, $\lor A B$ is not. But we want to make general claims about wffs, not just point to instances. It won’t do to try to generalize by saying something like the following: “for every A and B, $A \lor B$ is a wff but $\lor A B$ is not”. In that sentence, we are trying to use $A$ and $B$ as variables that range over every wff of PL, but $A$ and $B$ are not variables that range over sentences of PL, they are themselves two sentences of PL. We could get by by saying the following: “if you take any two wffs of PL and put a $\lor$ in between them, the result is a wff, whereas if you put a $\lor$ in front of them, the result is not a wff.” But it is easier to understand if we use meta-linguistic variables to talk about arbitrary sentences of PL: “If $\varphi$ and $\psi$ are wffs, then so is $\varphi \lor \psi$, but $\lor \varphi \psi$ is not.” We will use Greek letters as our meta-linguistic variables (variables that we use to talk about PL).

We are now in a position to give a full syntax for PL. A syntax for a language is a specification of which combination of symbols of the language constitute grammatically correct sentences of that language (wffs).

Syntax of PL

Base clause

Every atomic sentence letter is a wff.

Recursive clause

If $\varphi$ and $\psi$ are wffs, then so are:

• $(\neg \varphi)$

• $(\varphi \lor \psi)$

• $(\varphi \land \psi)$

• $(\varphi \rightarrow \psi)$

• $(\varphi \leftrightarrow \psi)$

Closure clause

Nothing else is a wff.

The syntax of PL takes the form of a recursive definition of wff. One important thing to note about it is that its recursive clause seems to assume that we already know what a wff is. Isn’t this viciously circular? Wasn’t the definition supposed to tell us what a wff is? How can it then assume that we can already recognize whether something is a wff? The circularity is merely apparent. Given any finite combination of symbols of PL, the definition allows us to determine whether it is a wff or not. Consider, for instance, the formula $(P \rightarrow (Q \lor R))$. Notice that the recursive clauses connect at most two wffs to make up larger wffs (with the exception of the sub-clause for the negation connective, which applies to just one wff). In this case, we know that we are dealing with a formula of the form $\varphi \rightarrow \psi$.³ So, by the sub-clause of the recursive clause that deals with $\rightarrow$, we know that $(P \rightarrow (Q \lor R))$ is a wff just in case both $P$ and $(Q \lor R)$ are wffs. Because $P$ is an atomic sentence letter, it is a wff by the base clause. $(Q \lor R)$ has the form $(\varphi \lor \psi)$, and so it is a wff just in case both $Q$ and $R$ are wffs—and they are, because they are both atomic sentence letters. We can make this process systematic by using syntax trees.

1.4.1 Syntax trees and conventions

A syntax tree tells the story of how a wff is built up out of atomic sentence letters. For instance, the syntax tree for our example formula $(P \rightarrow (Q \lor R))$ is the following:

Try it in the Logic Lab Build this syntax tree yourself, and the lab checks it.

Looking at this tree from top to bottom, we start with the complete formula and determine its main connective. The main connective of a wff is the connective whose scope is the whole formula. The scope of a connective is the set of formulas to which it applies. Thus, the main connective of a wff is the connective which applies to the whole formula (every wff that is not an atomic sentence letter has exactly one main connective; atomic sentence letters have none). In the formula above, $\lor$ cannot be the main connective because it does not apply to $P$—only $\rightarrow$ applies to both $P$ and $(Q \lor R)$. In practical terms, the main connective will be the only connective enclosed only by the outermost parentheses of the formula. $\rightarrow$ connects $P$ on the left to $(Q \lor R)$ on the right, so we draw two branches from the main formula and write down those two sub-formulae as nodes of the branches. When we reach an atomic sentence letter, that branch of the tree is complete. Thus, we no longer branch down from $P$. But, on the right-hand side, we have a new formula, $(Q \lor R)$. It is trivial in this case to determine the main connective of that formula, because it has only one: $\lor$. The connective, moreover, is connecting two atomic sentence letters. So, we branch down and terminate each branch with the corresponding atomic sentence letter.

We can also look at the tree from the bottom to the top, and that is how the tree tells the story of how the formula was constructed. We start out at the terminal nodes of the tree with three atomic sentence letters: $P, Q,$ and $R$. We connect $Q$ and $R$ together with $\lor$, and then we connect the resulting formula, $(Q \lor R)$, to $P$ with $\rightarrow$, resulting in the complete formula $(P \rightarrow (Q \lor R))$. Thus, the main connective is the last connective applied when constructing the formula.

Let’s build a syntax tree for a more complex formula: $((A \lor B) \land ((\neg A) \rightarrow (C \leftrightarrow D)))$:

Try it in the Logic Lab Build this syntax tree yourself, and the lab checks it.

This tree illustrates two important points. First, negation behaves differently in trees, because it is our only unary connective (all the others are binary connectives). Because negation applies to a single formula and not two, it generates just one branch. Second, a syntax tree can have multiple instances of the same atomic sentence letter as terminal nodes. In this case, $A$ appears twice: once as an immediate component of $(\neg A)$ and once as an immediate component of $(A \lor B)$.

Syntax trees and our recursive definition for the syntax of PL go hand in hand: a formula is a wff of PL if and only if a syntax tree can be built up for it. Consider, for instance, the formula $(P \lor Q \land R)$. We cannot build a syntax tree for it because it has no unique main connective: both $\lor$ and $\land$ are enclosed only by the outermost parentheses (the only parentheses in the formula, in this case), and so there is no unique connective that is so enclosed. For the same reason, $(P \lor Q \land R)$ is not a wff according to our recursive definition, for it is neither an atomic sentence letter nor does it have have any of the five forms specified in the recursive clause.

Let’s go back to the formula $((A \lor B) \land ((\neg A) \rightarrow (C \leftrightarrow D)))$. It strictly adheres to the definition of wff, but it is a bit of an eyesore and not very easy to parse. We can adopt conventions to make formulae more readable. The first thing we can do is to eliminate the outermost parentheses. This gives us $(A \lor B) \land ((\neg A) \rightarrow (C \leftrightarrow D))$. Once we eliminate the outermost parentheses, we can no longer say that the main connective in a formula is the one that is enclosed only by the outermost parentheses—instead, the main connective in a formula is now the only binary connective enclosed by no parentheses at all (and if there is no such connective, the formula is a negation, and its main connective is the initial $\neg$). We can also stipulate that negation applies to the wff that immediately follows it. Thus, although $\neg A \lor B$ is not strictly speaking a wff, it is equivalent to the following wff once we bring back the outermost parentheses and enclose the negation sign and the wff that immediately follows it in parentheses as well: $((\neg A) \lor B)$. If instead we want the negation sign to apply to the disjunction $A \lor B$ we have to write $\neg (A \lor B)$. Using those two conventions together, the above formula becomes $(A \lor B) \land (\neg A \rightarrow (C \leftrightarrow D))$.

Parentheses-dropping conventions

• Outermost parentheses can be dropped.

• Negations have scope over the shortest wff following them.

• In a string of conjunctions only, or of disjunctions only, the inner parentheses can be dropped: $A \land B \land C$ abbreviates $((A \land B) \land C)$. (Since grouping makes no difference to the truth-table in these cases, nothing hangs on the choice.)

1.5 The Semantics of PL: truth-tables

An atomic sentence letter can have one of two truth-values: it can be true, or it can be false. But what exactly does it mean, for instance, for “$A$” to be true? It depends on whether we are dealing with uninterpreted or interpreted PL. When we interpret PL, we make a dictionary to assign a natural-language atomic sentence to a PL atomic sentence letter. For instance, we can have the following assignment:

$$A = \text{Leona is a cat}$$

Under that interpretation, “$A$” is true just in case Leona is a cat. We will discuss interpretations of PL at length in the next chapter.

But if we have an uninterpreted sentence letter “$A$”, what would it mean for it to be true? Strictly speaking, nothing—it makes no sense to say that an uninterpreted sentence letter is true or false. But we can still suppose that “$A$” stands for an arbitrary (and unspecified) atomic proposition, which of course will be either true or false (this is why sometimes atomic sentence letters are called “propositional variables”). We can represent those two possibilities in a table:

If we now consider two atomic propositions at the same time, say $A$ and $B$, then we have four possibilities in total:

In general, for $n$ atomic propositions, there will be $2^{n}$ combinations of truth-values between them.

Let us now formally define our truth-functional connectives. We can do so by using the truth-tables just introduced:

Notice that we defined the connectives using our Greek metalinguistic variables, which range over any wff. This is the right way to do it, because we want to define (e.g.) not just $A \land B$ but all wffs of arbitrary complexity whose main connective is conjunction.

The process of drawing the truth-table for an arbitrary wff of PL is algorithmic—you can program a computer to do it. Here is one way of specifying the algorithm:

Algorithm for constructing the truth-table for a given wff of PL:

1. To calculate the number of rows that you will need, count the number of distinct atomic sentence letters in the wff. For $n$ distinct atomic sentence letters, your truth table will have $2^n$ rows of assignments. In addition, there will be one header row.

2. In the header row of the truth table, write down all the distinct atomic sentence letters in order of appearance in the wff, and then write down the wff itself.

3. For the $i$th atomic sentence letter, alternate between $2^{n-i}$ “T”s and $2^{n-i}$ “F”s until all rows are filled.

4. Create the syntax tree for the wff.

5. Use the syntax tree and the definitions of the connectives to recursively compute the truth-values for all the sub-formulae, including the full wff.

Step 5 is the crucial one. Consider again the following syntax tree:

Step 5 directs us to first calculate the truth-value of $\neg A$ using the definition of negation and the truth-values for $A$, $(C \leftrightarrow D)$ using the definition of biconditional and the truth-values for $C$ and $D$, and $(A \lor B)$ using the definition of disjunction and the truth-values for $A$ and $B$. These sub-formulae are all just one step above the terminal nodes of the tree. In the second step, we calculate the truth-value of $\neg A \rightarrow (C \leftrightarrow D)$ using the previously calculated values for $\neg A$ and $(C \leftrightarrow D)$. Finally, we calculate the truth-value of the whole formula, $(A \lor B) \land (\neg A \rightarrow (C \leftrightarrow D))$ using the definition of conjunction and the previously calculated values for $(A \lor B)$ and $\neg A \rightarrow (C \leftrightarrow D)$. The result is the following truth-table:

Try it in the Logic Lab Step through this truth table one column at a time.

What do the rows of a truth-table represent? They represent possibilities. Thus a row where both $A$ and $B$ are true represents a possibility where each of the propositions expressed by $A$ and $B$ are true. We can think of each row as a possible world: a way things could have been (as far as our atomic propositions are concerned).

A useful classification of wffs of PL distinguishes between tautologies, contradictions, and contingencies. A wff is a tautology when it is true in every row of its truth-table. It is a contradiction when it is false in every row of its truth-table. And it is a contingency when it is true in at least one row and false in at least one row. These notions are related to the notion of necessity. A necessary proposition is one that is true in every possible world, and an impossible proposition is one that is true in none. Since each row of a truth-table represents a possible world (distinguished no more finely than propositional logic allows), a tautology can only express a necessary proposition, and a contradiction can only express an impossible one.⁴ Here are examples of the three kinds of wffs:

Try it in the Logic Lab Step through this truth table one column at a time.

Try it in the Logic Lab Step through this truth table one column at a time.

Try it in the Logic Lab Step through this truth table one column at a time.

1.5.1 Truth-functional completeness and disjunctive normal form

We introduced five truth-functional connectives—a unary one (negation), and four binary ones (disjunction, conjunction, conditional and biconditional). A question you may be asking now is: why precisely those five? Why not more, or less?

Those are good questions! Something relevant to answering them is the issue of how many truth-functions there are. The question of how many truth-functions there are is actually incomplete, because it depends on how many variables we are talking about. A truth-function of $n$ variables takes as input an assignment of truth-values to those variables, and delivers a truth-value as output. As we saw, there are $2^{n}$ such assignments (the rows of the truth-table). A truth-function is completely determined by which output, T or F, it delivers for each of those $2^{n}$ inputs. Each of the $2^{n}$ rows can be given either of two outputs, independently of the others, and so the number of truth-functions of $n$ variables is $$\underbrace{2 \times 2 \times \cdots \times 2}_{2^{n} \text{ times}} = 2^{(2^{n})}.$$ For the case of just one variable there are $2^{1} = 2$ inputs (the variable can be true or false), and so $2^{2} = 4$ truth-functions, represented in this table:

Notice that the first two functions are just $\varphi$ and $\neg \varphi$. The third one is a tautological function. There are infinitely many ways of expressing a tautology with one variable: one is $\varphi \lor \neg \varphi$. Finally, the last one is a contradiction. There are also infinitely many ways of expressing a contradiction with one variable: one is $\varphi \land \neg \varphi$. This means that armed with just negation, disjunction and conjunction we can express all the possible truth-functions of one variable. So far, so good.

What happens when we move to truth-functions of two variables? Well, now we have $2^{2} = 4$ inputs, and so $2^{2^{2}} = 16$ truth-functions. Will our five connectives be enough to represent them? Yes:

But the number of truth-functions grows doubly exponentially with the number of variables, so there are 256 truth-functions of three variables, 65,536 truth-functions of four variables, more than four billion truth-functions of five variables, and so on. Now our meager collection of five connectives starts to look inadequate for the task. But, in fact, it is more than adequate to express any possible truth-function of any number of variables. The trick is that any formula whatsoever of PL can be written in disjunctive normal form, which uses only disjunction, conjunction, and negation.

You can construct the disjunctive normal form for an arbitrary formula by following this procedure:

1. Construct the truth table for the formula.

2. For every row where the column under the main connective for the formula has a T, build a conjunction of each of the atomic sentences in the formula, negating each atomic sentence that has an F in that row (and leaving the ones that have a T unnegated).

3. Disjoin all those conjunctions.

4. Special case: if there is no row with a T under the main connective (that is, if the formula is a contradiction), the procedure yields no conjunctions to disjoin. In that case, take any atomic sentence letter $A$ occurring in the formula and use $A \land \neg A$ as its disjunctive normal form.

Let us build the disjunctive normal form for the conditional $A \rightarrow C$. We know that the truth-table for this formula will have Ts under the conditional in all rows except the one where $A$ is true and $C$ is false:

Try it in the Logic Lab Step through this truth table one column at a time.

Now that we have the truth-table, we form all the relevant conjunctions: $A \land C$, $\neg A \land C$, and $\neg A \land \neg C$. Finally we disjoin them: $(A \land C) \lor (\neg A \land C) \lor (\neg A \land \neg C)$. This last formula is guaranteed to have the same truth-table as $A \rightarrow C$. In general, by construction the disjunctive normal form of a formula is guaranteed to have the same truth-table as the formula we began with. Two wffs that have the same truth-value in every row of their joint truth-table are called tautologically equivalent; equivalently, their biconditional is a tautology. (If the formula has just one row with a T, the “disjunction” consists of a single conjunction; and if it has none, the special case above applies.) Because we can build the disjunctive normal form for any formula, we are guaranteed that we can express any formula using just negation, conjunction, and disjunction.

This means, of course, that we can define conditional and biconditional in terms of disjunction, negation, and conjunction. A brute-force way of defining them is by constructing their disjunctive normal forms (we just did that for the conditional). But there are alternative definitions that are more perspicuous. For instance, we can define the conditional $\varphi \rightarrow \psi$ as $\neg \varphi \lor \psi$ and also as $\neg (\varphi \land \neg \psi)$. Moreover, we don’t really need all three of negation, conjunction, and disjunction, for disjunction can be defined in terms of negation and conjunction, and conjunction can be defined in terms of negation and disjunction.⁵ Thus, with just two of our five connectives we can express any formula of PL.

We can do even better in terms of expressive economy, for we can express any formula of PL with just one connective—although not any of our list of five. One connective which is functionally complete is the Sheffer stroke, or NAND, which is usually symbolized with “$\uparrow$” and has the following truth-table:

It is easy to see from the truth-table why the Sheffer stroke is also called NAND, because $\varphi \uparrow \psi$ has the same truth-table as $\neg (\varphi \land \psi)$. With NAND, we can define negation, conjunction, and disjunction,⁶ so it follows from what we know about disjunctive normal form that we can define every possible formula of PL with NAND alone.

There is another binary connective which is also functionally complete: NOR, usually symbolized with “$\downarrow$” and with the following truth-table:

NOR is so-named because $\varphi \downarrow \psi$ has the same truth-table as $\neg (\varphi \lor \psi)$. As with NAND, so too with NOR: with it, we can define negation, conjunction, and disjunction⁷—and, therefore, it too is functionally complete.

Given that a single connective is functionally complete, why do we bother to introduce five? Because there is a trade-off between expressive power and legibility (for us humans). Consider how a relatively simple formula like $A \rightarrow (B \lor C)$ must be expressed using just NAND: $A \uparrow ( [ (B \uparrow B) \uparrow (C \uparrow C) ] \uparrow [ (B \uparrow B) \uparrow (C \uparrow C) ] )$. This formula is extremely difficult to parse, whereas the original one is relatively trivial. Using just one connective gives us a lot of expressive power in a small package, but it does so to the detriment of legibility. That’s why we use five connectives: because we are interested in using PL. Why would anyone use only one connective, then? Because using just one connective makes it much easier to prove things about PL—something that logicians are very interested in.

Exercises

1. Give an example of three different sentences that express the same proposition.

   Show solution

   For example: “Leona is a cat,” “Leona is a member of the species felis catus,” and “Leona est une chatte.” Three different sentences, one proposition.

2. Don’t we know that some sentences in the interrogative mood express propositions?

   Show solution

   Yes: a rhetorical question (“Who doesn’t love a free lunch?”) is interrogative in form, but it is used to assert something, so it can express a proposition.

3. Why is it that for $n$ atomic propositions there are $2^{n}$ combinations of truth-values?

   Show solution

   Each of the $n$ atomic sentences is independently assigned T or F. Adding one more atomic sentence doubles the number of assignments (each old assignment extends in two ways), so there are $2^n$ rows.

4. What is wrong with defining conjunction as follows?

   $A$	$B$	$A \land B$
   T	T	T
   T	F	F
   F	T	F
   F	F	F

   Show solution

   The table is fine for the particular sentences $A,B$. A definition of a connective must cover arbitrary wffs, so it has to be stated with metavariables $\varphi,\psi$ rather than $A,B$.

5. Define conjunction in terms of negation and disjunction, and disjunction in terms of negation and conjunction.

   Show solution

   $\varphi\land\psi \equiv \lnot(\lnot\varphi\lor\lnot\psi)$ and $\varphi\lor\psi\equiv\lnot(\lnot\varphi\land\lnot\psi)$ (De Morgan).

6. Define negation, conjunction, and disjunction in terms of NAND. Do the same in terms of NOR.

   Show solution

   With NAND ($\uparrow$): $\lnot\varphi \equiv \varphi\uparrow\varphi$; $\varphi\land\psi\equiv(\varphi\uparrow\psi)\uparrow(\varphi\uparrow\psi)$; $\varphi\lor\psi\equiv(\varphi\uparrow\varphi)\uparrow(\psi\uparrow\psi)$. With NOR ($\downarrow$): $\lnot\varphi\equiv\varphi\downarrow\varphi$; $\varphi\lor\psi\equiv(\varphi\downarrow\psi)\downarrow(\varphi\downarrow\psi)$; $\varphi\land\psi\equiv(\varphi\downarrow\varphi)\downarrow(\psi\downarrow\psi)$.

7. For each of the following formulas: determine whether it is a wff according to our strict definition; determine whether it is a wff when considering the conventions for dropping parentheses; for each wff (strict or not), construct its syntax tree and its truth-table and determine whether it is a tautology, a contradiction, or a contingency.

   1. $((\neg B) \lor (A \rightarrow C)))$ Practice in the Logic Lab

   2. $\neg A \leftrightarrow ((\neg A \land B) \lor (\neg A \land \neg B))$ Practice in the Logic Lab

   3. $A \neg (B \lor C)$ Practice in the Logic Lab

   4. $\neg \neg A \lor (B \land A)$ Practice in the Logic Lab

   5. $(A \leftrightarrow B \lor C)$ Practice in the Logic Lab

   6. $(A \rightarrow B) \lor (B \rightarrow A)$ Practice in the Logic Lab

   7. $(A \land \neg A) \leftrightarrow (B \land \neg B)$ Practice in the Logic Lab

   8. $(A \lor B) \rightarrow (A \land B)$ Practice in the Logic Lab

   9. $(\neg A \land (B \lor C)) \rightarrow (C \lor A)$ Practice in the Logic Lab

   10. $\neg (A \lor B) \rightarrow C \land$ Practice in the Logic Lab

   Show solution

   Columns are listed in the row order TT, TF, FT, FF (for (i), rows TTT, TTF, TFT, TFF, FTT, FTF, FFT, FFF).

   	Wff?	Truth values	Type
   (a)	no (unbalanced parentheses)
   (b)	only with the conventions	TTTT	tautology
   (c)	no
   (d)	only with the conventions	TTFF	contingency ($\equiv A$)
   (e)	no (no unique main connective)
   (f)	only with the conventions	TTTT	tautology
   (g)	only with the conventions	TTTT	tautology
   (h)	only with the conventions	TFFT	contingency
   (i)	only with the conventions	TTTTTFTT	contingency$^{*}$
   (j)	never a wff (ends in $\land$)