Mathematical Logic Basics: AND, OR, and NOT Explained

Introduction to Mathematical Thinking. Logical Combinators Now let’s continue. Hopefully you are progressing. You should not expect to fully comprehend all of the concepts in an assignment in a single session. Or even before the next session. What you should do before the next one is attempt each question. That's what "complete the assignments" means. The goal is to develop certain ways of thinking, not to solve problems by a given deadline. The only way to develop a new way of thinking is to keep trying to think in different ways. This is difficult, of course, but it will be useful. In order to be more precise about our use of language in mathematical contexts, we've developed precise definitions of the key connecting words "and", "or" and "not." There are several other terms that can be made precise. Also there exists a trickier form of the word and. Let's start with and. We often want to combine two statements into a single statement using the word "and." So we need to analyze the way the word "and" works. In mathematics, the symbol for the standard deviation is an inverted V, known as a wedge. Sometimes you'll see & used but we’re going to stick to the common mathematical practice of using a wedge. For example, we might want to say that PI is greater than 3 and less than 3.2. We could do this as follows: PI is greater than 3 and less than 3.2. In fact, for this example where we're just talking about the position of numbers on the real line there's an even simpler notation we would typically write. 3 < pi < 3.2 But as an example illustrates, the word and can be used to join two statements. The official term for such an expression is a conjunction. The conjuncts in a conjunction are called phi and psi. Relative to the conjunction, the two constituents phi and psi are called conjuncts. Under what circumstances is the conjunction of phi and psi true? If phi is true and psi is true, then the conjunction will be true. Under what circumstances is the conjunction of phi and psi false? If either phi is false or psi is false or both are false, then the conjunction will be false. This may seem like a self-evident, trivial statement, but the definition actually leads to a surprising conclusion. Here is that conclusion. In the mathematical universe, phi and psi are identical. They both mean that phi and psi are both true. In mathematical palettes, conjunctions are commutative. In everyday English, the word 'and' is used to combine two sentences or clauses. For example, 'John took the free kick and the ball went into the net.' That doesn't mean the same as the sentence: 'The ball went into the net and John took the free kick.' Both conjunctions introduce clauses. The first sentence means that John took the free kick, and the ball went into the net at the same time. The second sentence means that John took the free kick and then, later, the ball went into the net. But soccer fans know that these two sentences have very different meanings. In everyday English, the word "and" is not always used in a commutative manner. Let's take a look at this one. Consider the sentence "It rained on Saturday," which we will call A. And now consider the sentence "It snowed on Saturday," which we will call B. Now consider whether or not the conjunction of these two sentences accurately reflects the meaning of the sentence "It rained and snowed on Saturday." Yes. Although there are some instances in which the answer would be no in general, we would be inclined to say that, overall, the answer is yes. A useful way to represent a definition like this is with a truth table. We'll list the components statements, in this case phi and psi, and they'll go together to make the conjunction phi and psi. Then we'll draw a table that lists all possible truth values for phi, psi and phi ^ psi. So what do we see, it is possible that both phi and psi are true. Or it is possible that phi is true and psi is false. Or it is possible that phi is false and psi is true. Or it is possible that both phi and psi are false. The next step is to place an F or a T in each of the four squares, depending on whether the sentence describes both phi and psi. You should then label these final columns "F" for "False" and "T" for "True" to represent the definition of phi and psi. According to the definition, phi and psi is true whenever both phi and psi are true. There is a T going to go here, but that's the only condition under which phi and psi is true. In all other circumstances it is false. So the entries for these are all F. So in a single table we've captured the entire definition of phi and psi, emphasizing the fact that the truth of the conjunction depends only on the truth or falsity of its conjuncts. The definition was entirely in terms of truth and falsity; that is, the meaning of phi and psi was irrelevant. It was only about truth and falsity. This will be the case for all the definitions we will give in order to make language precise. They'll depend on the truth of what's said, not on its meaning or logical connections. Now, let's work with the logical operator or. We want to be able to assert that statement A is true or statement B is true. For example, we might want to say that a is greater than 0 or the equation x squared plus a equals 0 has a real root. Another example might be that ab = 0 if a = 0 or b = 0. These are both statements that we get when we unite two statements with the word or. Both statements are true, but they differ in meaning. The word or has different meanings in the first sentence and the second sentence. In the first sentence, there is no possibility that both parts could be true at the same time. Either a will have a positive value, or this equation will have a real root. They cannot both occur. If a is positive, then this equation does not actually have a real root. In the second sentence, if either a or b is zero, then ab equals zero. If both a and b are zero, then ab is also zero. That is why those are different examples. In the first case we have an exclusive or, in the second case we have an inclusive or. If you look at either word's definition, if you say "either this or that," then what happens is that the either simply reinforces an exclusive or if one happens to be there. In the case of the second one, you could say ab = 0 if either a = 0 or b = 0. And actually, this does not conflict with the idea that they are exclusive. We simply accept that both could be true. In everyday English, the word or can be ambiguous. In mathematics, however, the choice between the inclusive and exclusive or must be made explicitly in order to avoid ambiguity. For various reasons, it is more convenient in mathematics to use an inclusive or rather than an exclusive or. The mathematical symbol we use for the inclusive or is the v symbol. It's known as a disjunctive symbol. Given two sentences phi and psi, if phi or psi is true, then phi or psi is true; this sentence is called a disjunction of phi and psi. The constituents of the disjunction are phii and psi. Recall that the symbol for a conditional in mathematics is a "v". Such as: (3 < 5) v (1 = 0). This means that at least one of these two statements must be true—they could both be true as well. For instance, the following rather silly statement is true: (3 < 5) v (1 = 0). Nobody of mathematicians will write this down except as an example. Silly examples like this are actually quite useful in mathematics because they help us understand the definitions that are being used. A distinction can be true even though one of its disjuncts is patently false. So, this emphasizes the fact that for a distinction to be true, all you need to do is find one of the disjuncts which is true, doesn't matter if one or more of the other disjuncts is apparently false. Let's see if we understand this concept. Here is a quick quiz: Let A be the sentence, "It will rain tomorrow," and let B be the sentence, "It will be dry tomorrow." Here's the question: Does the disjunction A v B accurately reflect the meaning of the sentence, "Tomorrow it will rain or it will be dry all day"? The above disjunctive statement is false. Now let’s move on to examining the truth table for phi and psi. Well, if you got this one right, your truth table has to look like this. True, true, true, false. A disjunction is true if both of its disjuncts are true, or if one of them is true. A disjunction is false only when both disjuncts are false. Now that we have established the meaning of the word all, we can move on to the word not. If psi is a sentence, then we want to be able to say that psi is false. So given psi, we want to create the sentence not psi. The symbol mathematicians use today is this one, which bears a slight resemblance to a negation symbol with a little vertical hook. Older textbooks will use a tilde instead. We prefer to stick to the modern notation (this sort of negative sign with the hook). If psi is true, then the negation of psi is false. And if psi is false, then the negation of psi is true. We typically use special notations in particular circumstances, such as writing x ≠ y instead of not (x = y). But you must be careful. For example, it is no good to w not the case a less than x less than or equal to b. You might be tempted to write something like a not less than x not less than or equal to b. Advice is to avoid that. That is better than this one. This one is completely unambiguous. It means that it's not the case that x is between a and b in that fashion. This one, well, it could mean several things, including that you agree or disagree with the statement. You better do not use such statements and use something like this. We should always go for clarity in mathematics. Remember, the whole point of this discussion is to avoid ambiguity, which can lead to confusion. In more advanced situations, we will have to rely on language alone, so it is important that we use it in a non-ambiguous fashion. Negation is a concept that seems straightforward, but it is not trivial. If we take the negation not(the case) that pi is less than 3, then this means that pi is greater than or equal to 3. This is easy to understand, with no problems. Let us illustrate with a sentence that is not quite so obvious. Consider this one: All foreign cars are badly made. What would the negation of this sentence be? There are four possibilities. Possibility 1: all foreign cars are well made. Possibility 2: all foreign cars are not badly made. Possibility 3: at least one foreign car is well made. Possibility 4: at least one foreign car is not badly made. This is not a quiz, but it would be nice for you to think for a few moments about which of these sentences is the negation of the original sentence, or maybe you think it's something else. Maybe you think it's something to do with domestic cars, domestic being the opposite of foreign. A is one of the most common ones for beginners to pick. But if you think about what the sentence really means, it's obviously not true that there are no good foreign cars. Why? Is the original sentence true? No, of course it's not. There are many good foreign-made cars. Although it is not true that all foreign cars are badly made, it is still the case that some foreign cars are badly made. But this sentence is in fact a false sentence. We know that just by our knowledge of the world. So if that sentence is false, then its negation must be true. But this is not the case. It is false to say that "all foreign cars are well made," so that cannot be the negation. What about b? Same reasoning, that can't be the negation because it's simply not the case that all foreign cars are not badly made. These are false, so they cannot be the negation of a false sentence. The negation of a false sentence will have to be true. Therefore, whatever the negation of this original sentence is, it will have to be something that's true. And we know what's true and false in terms of cars being well made. Well, is this one true? Well, yeah, that's true. Is this one true? Well, these are both true. So these are both possibilities for negating that. Think about that. Which of these is the negation of this? We will come back to this one, but now here comes some formal notation from sort of algebraic notation. Eventually, we may be able to reason precisely, seeing which of two things or a different thing is the negation of the other. One moment. The following sentence implies that all domestic cars are well made: "All domestic cars are well made." Somebody may assume that this sentence means that all foreign cars are poorly made, because it seems to contradict this statement: "All foreign cars are well made." There is a sort of negation between these two sentences, but the negation of the original sentence is not true. How do I know that? Because the original sentence is false and therefore whatever is being negated by the second sentence must be true. However, this is not true. It is also false. And because it is false, it cannot possibly have been a negation of the original sentence. In fact, this one falls far short of being a negation of that for a reason. The original sentence is about foreign cars. Since it mentions nothing about domestic cars, the negation can only be about foreign cars. These are bad candidates for negation because they talk about foreign cars. This one, however, is not a good candidate for negation because it does not talk about foreign cars; rather, it discusses domestic cars. Negating a word in a sentence is not the same as negating the entire sentence. That is the reason for this variant to be bad in our situation. Another quiz, here it is, the task is to fill in the truth table for negation. This one's much simpler than the previous table, as there's only one statement involved. Phi, and then we negate it. An easy truth table can be formed from the following rules. If phi is true, then the negation is false; if phi is false, then the negation is true. That last example about the negation of the sentence "All foreign cars are badly made" should illustrate why we're devoting time to making simple bits of language precise. In figuring out what the correct negation is, we relied on our knowledge of the everyday world. This works well in everyday situations that we're familiar with, but in a lot of mathematics we're dealing with an unfamiliar world. We can't rely on what we already know about a subject; we have to use language with which we described that world. Once we have studied language sufficiently, we will be able to apply rigorous mathematical reasoning to determine the negation of a foreign sentence. Try to think differently. Work together. Collaborate, share your knowledge and experience. Practice is the key.