We're going to talk about propositions and logical operations in this little clip, and let's begin then with a discussion of propositions. So to a mathematician and, in particular in this class, we're going to use the word proposition to refer to something that is either true or false. An example would be there are five regular solids. This happens to be true. In some terms we even prove it. It implies, for example, that if you wanted to place, let's say, 100 fixed-position satellites around the earth in a uniform way, you can't do it because there isn't any 100 vertex regular solid. The biggest one is 20 vertices.
OK. Well, if I change it to six, guess what? The assertion there are six regular solids is false. So that's a simple-minded example of two well-defined propositions, one of which is true, one of which is false. Propositions don't have to be true always. What are some non-examples? Well, wake up is not a proposition, because it's an imperative. It's not true or false, and where am I is a question. It's not true or false. And it's 3:00 PM is not a proposition, because it's true or false at any given moment, but whether or not it's true or false depends on the time, and that's a complication we don't want to get into. The idea is, a proposition is some fixed assertion that's either true forever or not true forever.
Now, one of the reasons why mathematicians bring up this abstraction of propositions and the operations on them that we're about to see is that ordinary language tends to be ambiguous and that, of course, will cause problems in mathematical reasoning just as it would in a program.
One of the most ambiguous of the phrases in English that connects propositions is Or. So let's look at this example. Greeks carry swords or javelins, and if I was transcribing this into precise math notation, I could say G for Greeks implies S for swords or J for javelin, so this is an assertion that if you're Greek, then you carry a sword or a javelin. Greeks implies sword or javelin. Really, I should say Greek soldiers, but let that be implicit.
That's how we're going to translate this sentence into just using these operators to paraphrase what's going on. The problem is, what does Or mean? And it turns out that for javelins and swords it's true even if a Greek carries both a sword and a javelin. This is an inclusive Or. A Greek soldier would carry both a sword and a javelin because, in fact, a javelin is a good long-distance weapon, and a sword is good for defending yourself close in, and you certainly want to have both, especially after you've thrown your javelin, and you don't have anything left but the sword.
Now, there's many standard notations for these logical connectives that build up larger propositions out of component propositions, so one of the things is this V symbol, or disjunction symbol, is used by logicians often instead of Or, and this arrow means implies or sometimes a double bar arrow also means implies, but we're not going to get into that. I'm not going ask you to memorize these symbols. We'll just stick to the words which don't take up that much more room.
Let's look at another example. Greeks carry bronze or copper swords. Syntactically this has the same structure as the previous phrase, but we're going to translate it differently, and the reason is that we mean here that a Greek soldier is not going to carry both a bronze and copper sword. Why is that? Well, bronze swords are just way better than copper swords. They'll slice right through copper. They're much harder, and it's not worth the weight to carry this inferior copper sword when you have a much better one.
So this time we mean the Greeks carry exactly one of a bronze or a copper sword. You'd carry a copper sword if you didn't have access to a bronze one. And so now we translate that into Greek implies B for bronze or C for copper, but this time we use the X Or. X Or means that one of them is true exactly but not both and not neither. Again, there's this plus sign notation for X Or, because as we'll see it acts a little bit like adding numbers by 2 where 1 plus 1 is 0.
So let's be more precise about the two definitions of Or and X Or and how they work, and the assertion is that if I think of P and Q as placeholders for propositions that are either true or false, then the composite proposition P or Q is true if, and only if, P is true or Q is true or both are true, and I could express this assertion in English this, if and only if, by giving you a so-called truth table, where in these two columns or all these rows I've enumerated all the possible pairs of values of P and Q.
So P and Q might both be true, that P might be true and Q false, P false, Q true, and both of them are false. And for each of those possible combinations of the truth values of Q and P, I tell you the truth value of P or Q, and the notable thing is this last row where I'm telling you that the only way that P or Q is false is if both P and Q are false.
For X Or, as we said, the P or X Or Q is true if, and only if, exactly one of P and Q is true, so if I was expressing that as a truth table, we'd see that where there's TT is false, and where there's FF it's false, because it's not the case in either of those two rows that exactly one is true, but the middle row is exactly one is true. And so P X or Q is true. So this truth table is just a precise way of defining how X Or acts on truth values.
There's another connective, And, which works even more straightforwardly. The value of P and Q is true if, and only if, both P and Q are true, and there's this truth table. Again, the salient row is that it's true only if, and only if, both P and Q are true. Another crucial logical operation is the negation operation, or Not. So Not P just flips the truth value of P. If P is true, then not P is false. If not P is true, then P is false, and there it's very trivial truth table, trivial because there's only two values to be concerned about. When P is true, not P is false. When P is false, not P is true.
One of the places that this notion of combining basic propositions to using logical operations to build up more complicated composite proposition is in programming. Here's a typical kind of phrase that comes from Java. Java uses this double vertical bar to mean Or, inclusive by the way, and double ampersand to mean And, so in Java this is a piece of legitimate Java code that's doing a test to evaluate this expression, if X is greater than 0 or X is less than or equal to 0 and Y is greater than 100, then if that test comes out to be true, then you do a bunch of code that follows the test up to some delimiter that tells you where to stop. And if it's false, you just skip all that stuff and go on.
So we use sort of Boolean expressions or logical expressions like this in a very standard way in most programming languages. The other place where these operations come up is in digital logic, and the digital circuit designers have their own notation, which I'll just mention, but we're not, again, impose on you but you should be aware. One notation they use that we'll use as well because it's so economical is that not X can be abbreviated by writing a bar over the X.
More generally, not a complicated expression can be abbreviated by writing a bar over the complicated expression. I just saved some space, and so we'll use it, but not the following. In digital logic, the idea is that you're talking about circuits where the only distinction of the signal that's coming in electrically is whether it's a high voltage or a low voltage, with high voltage is denoted by 1, and low voltage denoted by 0, and the way that digital logic behaves is that the 1 corresponds to true at the 0 corresponds to false. Then the And operation is simply multiplication, because the 1 or 0 times 1 or 0 is 1 only when both of them are 1 for ordinary multiplication, which is exactly the way And behaves when 1 means true and 0 means false.
Unfortunately, the digital designers use Plus when they mean Or. They do not mean that 1 plus 1 is 2. They mean that 1 plus 1 is 1, and just a thing to watch out four. That's part of the reason we're not going to use this notation. Let's just stick to our ordinary word notation that we give on the right.