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 singlesession. Or even before the next session. What you should do before the next one isattempt 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'vedeveloped 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 ofthe word and. Let's start with and. We often want to combine two statements into a singlestatement 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 practiceof using a wedge.

For example, we might want to say that PI is greater than 3 and less than 3.2. We could dothis as follows: PI is greater than 3 and less than 3.2. In fact, for this example where we'rejust talking about the position of numbers on the real line there's an even simpler notationwe would typically write. 3 < pi < 3.2 But as an example illustrates, the word and can be used to join two statements. Theofficial term for such an expression is a conjunction. The conjuncts in a conjunction arecalled phi and psi. Relative to the conjunction, the two constituents phi and psi are calledconjuncts. Under what circumstances is the conjunction of phi and psi true? If phi is true and psi istrue, then the conjunction will be true. Under what circumstances is the conjunction of phiand psi false? If either phi is false or psi is false or both are false, then the conjunction willbe false. This may seem like a self-evident, trivial statement, but the definition actually leads to asurprising conclusion. Here is that conclusion. In the mathematical universe, phi and psi are identical. They both mean that phi and psiare both true. In mathematical palettes, conjunctions are commutative. In everyday English, the word 'and' is used to combine two sentences or clauses. Forexample, 'John took the free kick and the ball went into the net.' That doesn't mean thesame 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 freekick, and the ball went into the net at the same time. The second sentence means thatJohn took the free kick and then, later, the ball went into the net. But soccer fans know thatthese 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 willcall A. And now consider the sentence "It snowed on Saturday," which we will call B. Nowconsider whether or not the conjunction of these two sentences accurately reflects themeaning of the sentence "It rained and snowed on Saturday." Yes. Although there are some instances in which the answer would be no in general, wewould 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 thecomponents statements, in this case phi and psi, and they'll go together to make theconjunction 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 istrue and psi is false. Or it is possible that phi is false and psi is true. Or it is possible thatboth phi and psi are false. The next step is to place an F or a T in each of the four squares, depending on whetherthe 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 isa T going to go here, but that's the only condition under which phi and psi is true. In allother circumstances it is false.

So the entries for these are all F. So in a single table we've captured the entire definition ofphi and psi, emphasizing the fact that the truth of the conjunction depends only on the truthor falsity of its conjuncts. The definition was entirely in terms of truth and falsity; that is, the meaning of phi and psiwas irrelevant. It was only about truth and falsity. This will be the case for all the definitionswe 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 Ais true or statement B is true. For example, we might want to say that a is greater than 0 or the equation x squared plusa equals 0 has a real root. Another example might be that ab = 0 if a = 0 or b = 0. Theseare 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 inthe 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 bothoccur. 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 arezero, 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. Ifyou look at either word's definition, if you say "either this or that," then what happens isthat the either simply reinforces an exclusive or if one happens to be there. In the case ofthe 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 acceptthat both could be true. In everyday English, the word or can be ambiguous. In mathematics, however, the choicebetween 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 ratherthan 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 iscalled 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 betrue 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 usunderstand the definitions that are being used. A distinction can be true even though one of its disjuncts is patently false. So, thisemphasizes the fact that for a distinction to be true, all you need to do is find one of thedisjuncts which is true, doesn't matter if one or more of the other disjuncts is apparentlyfalse. Let's see if we understand this concept. Here is a quick quiz: Let A be the sentence, "It willrain 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 willrain or it will be dry all day"? The above disjunctive statement is false. Now let’s move on to examining the truth tablefor 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 isfalse only when both disjuncts are false.

Now that we have established the meaning of the word all, we can move on to the wordnot. If psi is a sentence, then we want to be able to say that psi is false. So given psi, wewant to create the sentence not psi. The symbol mathematicians use today is this one, which bears a slight resemblance to anegation symbol with a little vertical hook. Older textbooks will use a tilde instead. Weprefer 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 istrue. We typically use special notations in particular circumstances, such as writing x ≠ y insteadof not (x = y). But you must be careful. For example, it is no good to w not the case a less than x lessthan or equal to b. You might be tempted to write something like a not less than x not lessthan 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 thecase 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 suchstatements 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 toconfusion. In more advanced situations, we will have to rely on language alone, so it isimportant that we use it in a non-ambiguous fashion.

Negation is a concept that seems straightforward, but it is not trivial. If we take thenegation not(the case) that pi is less than 3, then this means that pi is greater than orequal 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 foreigncars 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: allforeign 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 ofthese sentences is the negation of the original sentence, or maybe you think it's somethingelse. Maybe you think it's something to do with domestic cars, domestic being the oppositeof foreign. A is one of the most common ones for beginners to pick. But if you think about what thesentence really means, it's obviously not true that there are no good foreign cars. Why? Isthe 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 someforeign cars are badly made. But this sentence is in fact a false sentence. We know thatjust by our knowledge of the world. So if that sentence is false, then its negation must betrue. But this is not the case. It is false to say that "all foreign cars are well made," so thatcannot be the negation. What about b? Same reasoning, that can't be the negation because it's simply not thecase that all foreign cars are not badly made. These are false, so they cannot be the negation of a false sentence. The negation of afalse sentence will have to be true. Therefore, whatever the negation of this original sentence is, it will have to be somethingthat'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. Sothese are both possibilities for negating that. Think about that. Which of these is thenegation of this? We will come back to this one, but now here comes some formal notation from sort ofalgebraic notation. Eventually, we may be able to reason precisely, seeing which of twothings or a different thing is the negation of the other. One moment. The following sentence implies that all domestic cars are well made: "Alldomestic cars are well made." Somebody may assume that this sentence means that allforeign cars are poorly made, because it seems to contradict this statement: "All foreigncars are well made." There is a sort of negation between these two sentences, but the negation of the originalsentence is not true. How do I know that? Because the original sentence is false andtherefore 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 havebeen a negation of the original sentence. In fact, this one falls far short of being a negationof 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 asnegating 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 muchsimpler than the previous table, as there's only one statement involved. Phi, and then wenegate it. An easy truth table can be formed from the following rules. If phi is true, then the negationis 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 everydayworld. This works well in everyday situations that we're familiar with, but in a lot ofmathematics we're dealing with an unfamiliar world. We can't rely on what we already know about a subject; we have to use language withwhich we described that world. Once we have studied language sufficiently, we will be able to apply rigorous mathematicalreasoning to determine the negation of a foreign sentence. Try to think differently. Work together. Collaborate, share your knowledge and experience.Practice is the key.