8.1: Propositional logic

The simpler — but less powerful — of the two logic systems we’ll study is called propositional logic. It has this name because the core building block is the proposition. A proposition is simply a statement that has a “truth value," which means that it is either true or false. The statement “all plants are living beings" could be a proposition, as could “Barack Obama was the first African-American President" and “Kim Kardashian will play the title role in the upcoming Batman Reborn." By contrast, questions like “are you okay?" cannot be propositions, nor can commands like “hurry up and answer already!" or phrases like “Lynn’s newborn schnauzer," because they are not statements that can be true or false. (Linguistically speaking, propositions have to be in the indicative mood.)

We normally use capital letters (what else?) to denote propositions, like:

Let A be the proposition that UMW is in Virginia.

Let B be the proposition that the Queen of England is male.

Let C be the proposition that dogs are carnivores.

Don’t forget that a proposition doesn’t have to be true in order to be a valid proposition (B is still a proposition, for example). It just matters that it is labeled and that it has the potential to be true or false.

Propositions are considered atomic. This means that they are indivisible: to the logic system itself, or to a computer program, they are simply an opaque chunk of truth (or falsity) called “A" or whatever. When we humans read the description of A, we realize that it has to do with the location of a particular institution of higher education, and with the state of the union that it might reside (or not reside) in. All this is invisible to an artificially intelligent agent, however, which treats “A" as nothing more than a stand-in label for a statement that has no further discernible structure.

So things are pretty boring so far. We can define and label propositions, but none of them have any connections to the others. We change that by introducing logical operators (also called logical connectives) with which we can build up compound constructions out of multiple propositions. The six connectives we’ll learn are:

\(\wedge\) — “and"	\(\neg\) — “not"
\(\vee\) — “or"	\(\Rightarrow\) — “implies" (or “if…then …")
\(\oplus\) — “xor" (exclusive “or")	\(\Leftrightarrow\) — “equiv" (equivalent)

Just as the ordinary algebraic operators (+, -, etc.) can be used to join numbers and produce another number, and just as the set operators can be used to join sets and produce another set, the logical operators can be used to join propositions and produce another proposition. The expression “34 + 59" produces the number 93. The expression “{X,Y}\(\cup\){Y,Z}" produces the set {X,Y,Z}. And the expression “A \(\wedge\) B" produces the value false, since although UMW is located in Virginia, the Queen is female.

Let’s run through the six operators, some of which are intuitive and some of which are not:

\(\wedge\) ("and")

The proposition X\(\wedge\)Y is true when both X and Y are true propositions. “A\(\wedge\)C" represents the proposition “UMW is in Virginia and dogs are carnivores," which has a truth value of true since both components are true. This operation is sometimes called a conjunction. Notice that the “\(\wedge\)" sign somewhat resembles the “\(\cap\)" sign for set intersection. This is not an accident. An element is in the intersection of two sets if it is a member of the first and the second set. Hence mathematicians have chosen symbols which reinforce this connection.

\(\vee\) ("or")

The proposition X\(\vee\)Y is true when either X or Y (or both) are true propositions. “B\(\vee\)C" represents the proposition “The Queen of England is male or dogs are carnivores," which has a truth value of true since the second component is true. This operation is sometimes called a disjunction. The \(\vee\) looks somewhat like the “\(\cup\)" sign for set union, since an element is in the union of two sets if it is an element of the first set or the second set (or both). This operator is sometimes called an “inclusive or" since it is true if both propositions are true.

\(\oplus\) ("xor")

The \(\oplus\) operator is just like \(\vee\) except that it’s exclusive: the proposition X\(\oplus\)Y is true when either X or Y (but not both) are true propositions. “B\(\vee\)C" and “B\(\oplus\)C" are both true, but “A\(\oplus\)C" is false, since UMW is in Virginia and dogs are carnivores.

\(\neg\) ("not")

This operator is different from the others in that it’s unary, which means that it only operates on one proposition instead of two. All it does is flip the value from true to false (or vice versa.) The proposition “A" is true, but the proposition “\(\neg\)A" is false. “\(\neg\)B," on the other hand, is true. This operation is sometimes called a negation.

\(\Rightarrow\) ("implies")

Okay, now for the toughest one. We’re going to spend significant time thinking through this one carefully, because it’s both important (in some ways, the most important of the operators) and also potentially baffling. I’ve studied this stuff for years, and I still sometimes get stuck when trying to figure out \(\Rightarrow\).

If we say “X\(\Rightarrow\)Y," we’re claiming that “if X is true, then Y is true." Note carefully that we are not claiming that X itself is true. We’re simply asserting that if it’s true, then Y must necessarily also be true. We call the first part of a \(\Rightarrow\) proposition the premise, and the second part the conclusion. Here, X is the premise and Y the conclusion.

So far, it seems easy. It gets tougher when you realize that X\(\Rightarrow\)Y is true whenever either X is false or Y is true (or both). For example, A\(\Rightarrow\)C is a true proposition, believe it or not. In English, it says “UMW being in Virginia implies that dogs are carnivores." The proposition B\(\Rightarrow\)A is also true: “The Queen of England being male implies that UMW is in Virginia." What possible sense can we make out of these nonsensical claims?

The key to understanding it, for me at least, is twofold. First, remember that to a computer (or a logic system), there is no meaning to the propositions: they’re simply atomic building blocks, each of which is true or false. So the fact that to a human, the content of the propositions might have nothing to do with each other — English Queens and dogs — is irrelevant to a computer: it just thinks indifferently in terms of “X" and “Y," and has no idea what real-world entities any of this refers to. Second, think in terms of ruling out counterexamples. When I assert X\(\Rightarrow\)Y, what I’m saying is “it’s impossible for X to be true and Y false, because X’s truthfulness would imply Y’s truthfulness." Just as when I assert X\(\vee\)Y I’m promising that either X or Y is true (or both), when I assert X\(\Rightarrow\)Y I’m promising that either X is true or Y is false (or both).

In this way, it starts to make sense when someone says, “Iowa being in the Southern hemisphere implies that Batman’s cape is red." That assertion is like a promise: “if it turns out that Iowa is in the Southern hemisphere, then I guarantee Batman’s cape is red." But since Iowa isn’t in the Southern hemisphere, all bets are off. The conclusion was conditional on the premise.

The reason this operator is so important is that in artificial intelligence, the name of the game is concluding new facts from known existing facts, so that knowledge is increased. Every time a ’bot learns that X\(\Rightarrow\)Y is true, and then also learns that the premise (X) is true, it can conclude that the conclusion (Y) is true, even if it was never explicitly told that Y was true. This rule of logic is called modus ponens, and is the workhorse of automated knowledge bases.

\(\Leftrightarrow\)("equiv")

Finally, the proposition X\(\Leftrightarrow\)Y is true whenever X and Y have the same value: they’re either both true, or both false. This can be seen as “implies in both directions," since X\(\Leftrightarrow\)Y means “if X is true, then Y is true; and if Y is true, then X is true." This operator is also the inverse of \(\oplus\), since X\(\oplus\)Y is true only if X and Y are different, and X\(\Leftrightarrow\)Y is true only if they’re the same.

These operators, which each produce another proposition (called a compound proposition) from the proposition(s) they operate on, can be combined to form complex expressions. For instance:

• \(\neg\)B is the proposition that the Queen of England is not male. (This is true.)

• A \(\wedge\) \(\neg\)B is the proposition that UMW is in Virginia and the Queen of England is not male. (This is also true.)

• C \(\oplus\) (A \(\wedge\) \(\neg\) B) is the proposition that either dogs are carnivores or UMW is in Virginia and the Queen of England is not male. (This is false, because both halves of the xor are true.)

• (C \(\oplus\) (A \(\wedge \neg\) B)) \(\Rightarrow\) \(\neg\)A is the proposition that if either dogs are carnivores or UMW resides in Virginia and the Queen of England is not male, then UMW must not reside in Virginia. (This is true, since dogs are carnivores and UMW resides in Virginia and the Queen of England is not male, so the left-hand side of the \(\Rightarrow\) is false, which means that the entire expression is true regardless of the truth value of the right-hand side (which is also false, since UMW doesn’t not reside in Virginia.)

• Etc.

Truth tables

Several times in this book, we’ve drawn the distinction between intension — the inner, conceptual meaning — and extension — the exhaustive list of examples. A set can have both an intension like “the prime numbers less than ten" and an extension like {2,3,5,7}. A relation can have an intension like “isDaughterOf" and an extension like “{(Lisa,Homer), (Lisa,Marge), (Maggie,Homer), (Maggie,Marge)}." So, too, with the logical connectives. When we say that the “\(\wedge\)" operator means “both propositions must be true," we’re specifying the conceptual meaning of the “and" operator. Another way to describe it, however, would be to just list its value for all the possible inputs.

Such an exhaustive list is called a truth table. We specify every possible combination of inputs, and list the output for each one of them. Here’s the truth table for “\(\wedge\)":

X	Y	X\(\wedge\)Y
0	0	0
0	1	0
1	0	0
1	1	1

 

We use “1" to represent true and “0" for false, just to make the table more compact. The “\(\wedge\)" operator works on two propositions, either of which can have a truth value or 0 or 1. There are therefore, by the Fundamental Theorem of Counting, four different combinations of inputs, and so our truth table has four rows. The right-most column shows the output for each of these sets of inputs. It indicates that X\(\wedge\)Y is 1 only when both inputs are 1, and 0 otherwise. Even if we didn’t grasp the simple concept that “\(\wedge\)" is supposed to represent the concept of “and," we could just look up the value of X\(\wedge\)Y if we knew the truth values of X and Y.

Sometimes we show more than one output in a truth table. For instance, this truth table shows the values for the other five operators:

X	Y	X\(\vee\)Y	X\(\oplus\)Y	\(\neg\)X	X\(\Rightarrow\)Y	X\(\Leftrightarrow\)Y
0	0	0	0	1	1	1
0	1	1	1	1	1	0
1	0	1	1	0	0	0
1	1	1	0	0	1	1

Take a moment and look carefully through the entries in that table, and make sure you agree that this correctly represents the outputs for the five operators. (Note that “\(\neg\)", being a unary operator, only has X as an input, which means that the value of Y is effectively ignored for that column.)

Now sometimes we have a more complex expression (like the (C \(\oplus\) (A \(\wedge \neg\)B)) \(\Rightarrow\) \(\neg\)A example from above) and we want to know the truth value of the entire expression. Under what circumstances — i.e., for what truth values of A, B, and C — is that expression true? We can use truth tables to calculate this piece by piece.

Let’s work through that example in its entirety. First, we set up the inputs for our truth table:

A	B	C
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

In this case, there are three inputs to the expression (A, B, and C) and so we have \(2^3\), or eight, rows in the truth table.

Now we work our way through the expression inside out, writing down the values of intermediate parts of the expression. We need to know the value of \(\neg\)B to figure some other things out, so let’s start with that one:

A	B	C	\(\neg\)B
0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	0

Now we can compute A \(\wedge \neg\)B, a component of the expression:

A	B	C	\(\neg\)B	A\(\wedge \neg\)B
0	0	0	1	0
0	0	1	1	0
0	1	0	0	0
0	1	1	0	0
1	0	0	1	1
1	0	1	1	1
1	1	0	0	0
1	1	1	0	0

  This produces a 1 only for rows where A is true and B is false. Knowing this allows us to compute the value of (C \(\oplus\) (A \(\wedge \neg\)B)):

A	B	C	\(\neg\)B	A\(\wedge \neg\)B	(C\(\oplus\)(A\(\wedge \neg\)B))
0	0	0	1	0	0
0	0	1	1	0	1
0	1	0	0	0	0
0	1	1	0	0	1
1	0	0	1	1	1
1	0	1	1	1	0
1	1	0	0	0	0
1	1	1	0	0	1

which is true only when the value of C is different than the value of (A \(\wedge \neg\)B). We’re almost there now. All we need is \(\neg\)A:

A	B	C	\(\neg\)B	A\(\wedge \neg\)B	(C\(\oplus\)(A\(\wedge \neg\)B))	\(\neg\)A
0	0	0	1	0	0	1
0	0	1	1	0	1	1
0	1	0	0	0	0	1
0	1	1	0	0	1	1
1	0	0	1	1	1	0
1	0	1	1	1	0	0
1	1	0	0	0	0	0
1	1	1	0	0	1	0

and we can finally obtain our answer:

A	B	C	\(\neg\)B	A\(\wedge \neg\)B	(C\(\oplus\)(A\(\wedge \neg\)B))	\(\neg\)A	(C\(\oplus\)(A\(\wedge \neg\)B))\(\Rightarrow\)\(\neg\)A
0	0	0	1	0	0	1	1
0	0	1	1	0	1	1	1
0	1	0	0	0	0	1	1
0	1	1	0	0	1	1	1
1	0	0	1	1	1	0	0
1	0	1	1	1	0	0	1
1	1	0	0	0	0	0	1
1	1	1	0	0	1	0	0

That last step is the hardest one. We look at the third output column (C\(\oplus\)(A\(\wedge \neg\)B) and the fourth (\(\neg\)A) and mark down a 1 for each row in which the third is 0 or the fourth is 1. (Review the truth table for the “\(\Rightarrow\)" operator if you have doubts about this.) The final result is that our complex expression is true for all possible values of A, B, and C, except when they have the values 1, 0, and 0, or else 1, 1, and 1, respectively. In our original example, we know that UMW is in Virginia, the Queen is not male, and dogs are carnivores, so our input values are 1, 0, and 1 for A, B, and C. Therefore, for those inputs, this expression is true.

Tautologies

Let’s work through this process for a different example. Suppose I want to know under what circumstances the expression \(\neg\)Z \(\wedge\) (X \(\Leftrightarrow\) Y) \(\wedge\) (X \(\oplus\) Z) \(\Rightarrow\) (X \(\wedge\) \(\neg\) Z) evaluates to true. When we follow the above procedure, it yields the following truth table:

X	Y	Z	\(\neg\)Z	X\(\Leftrightarrow\)Y	\(\neg\)Z\(\wedge\)(X\(\Leftrightarrow\)Y)	X\(\oplus\)Z	A^1	(X\(\wedge\neg\)Z)	B
0	0	0	1	1	1	0	0	0	1
0	0	1	0	1	0	1	0	0	1
0	1	0	1	0	0	0	0	0	1
0	1	1	0	0	0	1	0	0	1
1	0	0	1	0	0	1	0	1	1
1	0	1	0	0	0	0	0	0	1
1	1	0	1	1	1	1	1	1	1
1	1	1	0	1	0	0	0	0	1

(If you’re looking for some practice, cranking through this example on your own and then comparing your answers to the above truth table isn’t a bad idea at all.)

You’ll notice that the “answer" column has all 1’s. This means that the expression is always true, no matter what the values of the individual propositions are. Such an expression is called a tautology: it’s always true. The word “tautology" has a negative connotation in regular English usage: it refers to a statement so obvious as to not tell you anything, like “all triangles have three sides," or “the fatal overdose was deadly." But in logic, tautologies are quite useful, since they represent reliable identities.

The tautology above was a contrived example, and not useful in practice. Here are some important others, though:

X	\(\neg\)X	X\(\vee\neg\)X
0	1	1
1	0	1

Sometimes called the law of the excluded middle, this identity states that either a proposition or its negative will always be true. (There is no third option.)

X	Y	X\(\vee\)Y	\(\neg\)(X\(\vee\)Y)	\(\neg\)X	\(\neg\)Y	\(\neg\)X\(\wedge\neg\)Y	\(\neg\)(X\(\vee\)Y)\(\Leftrightarrow\)(\(\neg\)X\(\wedge\neg\)Y)
0	0	0	1	1	1	1	1
0	1	1	0	1	0	0	1
1	0	1	0	0	1	0	1
1	1	1	0	0	0	0	1

This is one of De Morgan’s Laws, which we’ve seen previously with regards to sets (p. ). Here is the other:

X	Y	X\(\wedge\)Y	\(\neg\)(X\(\wedge\)Y)	\(\neg\)X	\(\neg\)Y	\(\neg\)X\(\vee\neg\)Y	\(\neg\)(X\(\wedge\)Y)\(\Leftrightarrow\)(\(\neg\)X\(\vee\neg\)Y)
0	0	0	1	1	1	1	1
0	1	0	1	1	0	1	1
1	0	0	1	0	1	1	1
1	1	1	0	0	0	0	1

The first can be expressed as “the negation of the disjunction is equal to the conjunction of the negations," and the second as “the negation of the conjunction is equal to the disjunction of the negations." If that helps at all.

One last identity is this one:

X	Y	Z	Y\(\vee\)Z	X\(\wedge\)(Y\(\vee\)Z)	X\(\wedge\)Y	X\(\wedge\)Z	(X\(\wedge\)Y)\(\vee\)(X\(\wedge\)Z)	A^2
0	0	0	0	0	0	0	0	1
0	0	1	1	0	0	0	0	1
0	1	0	1	0	0	0	0	1
0	1	1	1	0	0	0	0	1
1	0	0	0	0	0	0	0	1
1	0	1	1	1	0	1	1	1
1	1	0	1	1	1	0	1	1
1	1	1	1	1	1	1	1	1

This is none other than the distributive law, which we also saw for set union and intersection (p. ) and which you should also remember from introductory algebra: \(x\cdot(y+z)=x\cdot y+x\cdot z\).

It’s interesting, actually, when you compare the distributive law from algebra to the distributive law for logic: \[\begin{aligned} x\cdot(y+z) &= x\cdot y+x\cdot z \\ X\wedge(Y\vee Z) & \Leftrightarrow(X\wedge Y)\vee(X\wedge Z)\end{aligned}\] The “\(\wedge\)" operator is analogous to “\(\cdot\)" (times), while “\(\vee\)" corresponds to “+" (plus). In fact, if you look at the truth tables for these two operators again, you’ll see an uncanny resemblance:

X	Y	X\(\wedge\)Y	X\(\vee\)Y
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	(1)

Except for the (1) that I put in parentheses, this truth table is exactly what you’d get if you mathematically multiplied (\(\wedge\)) and added (\(\vee\)) the inputs! At some level, logically “and-ing" is multiplying, while “or-ing" is adding. Fascinating.

---

1. Here, “A” stands for ¬Z∧(X⇔Y)∧(X⊕Z) and “B” is “¬Z∧(X⇔Y)∧(X⊕Y)⇒(X∧¬Z),” which were too long to fit in the table heading
2. Here, “A” is X∧(Y∨Z)⇔(X∧Y)∨(X∧Z).