An Introduction to Propositional Logic

0:00 Logic is at the core of computers and everything they do. When you get a phone call, you want your ringtone to play, but only if your phone's not set to silent mode. The login button on an app shouldn't work until the user types in both a username and a password; and if one or the other is wrong, then the user should see an error. This kind of reasoning — "if", "then", "not", "and", "or" — is logic, and it's what ensures computers know what to do and when, based on whether statements are true or false. And these ideas are so important that computer scientists use formal logical systems for expressing ideas about statements and whether or not they are true.

0:46 One of the most important logical systems is called propositional logic. Propositional logic deals with propositions, which are sentences that can be either true or false. For example, we might have a proposition like "The robot is blue." To make it easier to talk about these propositions, we'll often use a variable, like the letter P, to stand for a proposition. Depending on the state of the world, the proposition might be true if the robot in question is blue, or the proposition might be false if the robot is some other color. Where things start to get more interesting is when we start modifying and combining logical variables into more complex logical formulas.

1:32 One way to modify a logical formula is to take its negation. If P is a proposition like "The robot is blue", then we can use this negation symbol to represent the negation of P (which we often call "not P"). In this case "not P" is true when the robot is not blue. If we have more than one logical formula, we can combine them in other ways. This symbol, called conjunction or and, takes two logical formulas and expresses the idea that both are true. So if P is the proposition "The robot is blue" and Q is the proposition "The robot has an antenna", then the conjunction "P and Q" is a formula

2:20 that's true when the robot in question is both blue and has an antenna as well. Meanwhile, this symbol, called disjunction or or, takes two logical formulas and expresses the idea that at least one of them is true. In this case, the disjunction "P or Q" is a formula that's true as long as the robot is blue or has an antenna (or maybe both). Especially once we start dealing with multiple logical variables in a formula, it can be useful to figure out under what circumstances the formula is true and under what circumstances the formula is false. To do that, we can create a truth table — a table that lists all of the possible combinations of values for

3:07 the logical variables in a formula and what that means for whether the formula is true or false. In this case, with two variables P and Q, there are four possible combinations of values: they could both be false, P could be false while Q is true, P could be true while Q is false, or both could be true. For the formula "P and Q", there's only one setting of these variables where it holds true — P needs to be true and Q needs to be true as well. In all other cases, the formula "P and Q" is false. But for the formula "P or Q", three of the four combinations of values allow the

3:53 formula to hold true, and only in the case where P and Q are both false is the formula false. Notice that for the formula "P or Q", it's true if P is true, or if Q is true, or if both are true. Sometimes, though, we'll want to express the idea that P is true or Q is true, but not both. For that, we can use this symbol, called exclusive or. In this case, "P exclusive or Q" is true when the robot is blue, it's true when the robot has an antenna, it's false when the robot is not blue and doesn't have an antenna, and it's also false when the robot is both blue and has an antenna.

4:45 In addition to "not", "and", "or", and "exclusive or", we also have this symbol, called logical implication. If P means the robot is blue, and Q means that the robot has an antenna, then this formula, we read as "P implies Q" or alternatively "if P then Q", tells us that if it's true that the robot is blue, then it also must be true that the robot has an antenna. So for this robot, it's blue, and it has an antenna, so "P implies Q" is true. But for this robot, it's blue, but it has no antenna. So "P implies Q" is false here — for it to be true,

5:33 the fact that the robot is blue would have to imply that the robot has an antenna. Importantly, "P implies Q" says nothing about what the world must be like if P is false. If P is false — in other words, if the robot isn't blue — then the formula isn't saying anything about whether Q is true or not. Maybe the robot has an antenna, maybe it doesn't: in either case, "P implies Q" is true. It can be a little tricky to wrap your mind around the idea that "P implies Q" is true in all cases where P is false. But this fits logically with how we use the ideas of "if" and "then" in everyday life — for example, imagine you said something like "If it's my birthday, then I will eat cake".

6:25 For that to be true, then on your birthday you need to eat cake; but on days where it's not your birthday, you might eat cake or you might not and you could still be telling the truth. The only way you wouldn't be telling the truth is if it's your birthday but you don't eat cake. So, let's go back to blue robots and antennas. The formula "P implies Q" is true for a blue robot with an antenna, and it's true for any robot that isn't blue. So there's another way to express this same idea too — we could equivalently say "not P or Q", which is true when the robot isn't blue, or when the robot has an antenna.

7:11 In other words, these two formulas are logically equivalent to each other. And we can prove that by writing out the truth tables for each formula — we can describe the situations where "P implies Q" is true, and describe the situations where "not P or Q" is true, and it turns out the truth tables are the same: no matter what the values are for these variables P and Q, these two logical formulas will always have the same truth value. Many logical formulas are equivalent to each other. For example, you might try on your own proving that "P exclusive or Q" means the same thing as "(P and not Q) or (not P and Q)". And

8:00 you can try on your own to find other logical formula that are equivalent to both of these too. Here's an exercise we can try together: is "P implies Q" equivalent to "Q implies P"? We can answer that by drawing out the truth tables. "P implies Q" means that if P is true, then Q is true — so if P is true and Q is false, then the whole formula is false. And if P is false, we know that the formula is true no matter what. Meanwhile, "Q implies P" means that if Q is true, then P is true. And when Q is false, the formula, again, is always true. Notice that these two truth tables are different.

8:47 So "P implies Q" and "Q implies P" mean two different things. And that makes sense too, given how we intuitively think about "if" and "then". When I say "If it's a holiday, then the bank is closed", that doesn't mean the same thing as "If the bank is closed, then it must be a holiday" — the bank might be closed for some other reason too. If we want to express the idea that both "P implies Q" and "Q implies P", we can use this double-arrow symbol, the biconditional, which we often read as "if and only if". "P if and only if Q" means that if P is true, then Q is true; and if P is false, Q is false. In other

9:35 words, P and Q always have the same truth value — either they're both true, or they're both false. Here, it's true for a blue robot with an antenna, or if the robot is not blue and has no antenna, but it's false if only one of the two propositions is true. There's a lot of symbols at play here, but it all comes down to trying to formally describe logical ideas that are all pretty intuitive to people, but that computers need us to be completely precise about. By learning the language of logic, we enable ourselves to communicate with that same precision, and express our ideas using the building blocks that computers use in all of the complex, sophisticated programs we use every day.