CS 100 (Learn) — CS 100 (Web) — Module 05
NOTE: If your internet access is restricted and you do not have access to YouTube, we have provided alternate video links.
Note: This video transcript has been slightly modified. Corrections are marked with strikethrough, and alternative wording has been placed in [square brackets] to correct some of the awkward or confusing phrasing in the videos.
In this video we are going to talk about Boolean logic.
Boolean logic is named after a dude named George Boole, who lived about a hundred and fifty years ago.
It is important for you pedantic people out there that when you write Boolean you always should use a capital B because it is named after a person. If you have never seen that rule before, whenever you use Newtons or anything like that that is named after a person you should always give respect. Make sure [it is a] capital B for Boolean.
For Boolean logic, our variables are either going to be true or false. [Do not give me any of that] "fifty shades of gray" nonsense: everything is either true or false.
This is similar to a light switch which is either on or off. A light switch is either on or it is off: there is no in-between.
[Consider] a [Boolean] variable named X: [it] has a value of either true or false.
Working with Boolean logic [is not much] different than working with numbers and other [areas] of mathematics, where you have integers and values. With Boolean logic, the [only possible] values are true and false.
Where some people get confused is that sometimes when you are working with numbers you can have Boolean results, based on certain operators.
For example, the equals (=) operator produces a value that is either true or false.
If I say "seven equals five" that is false. The equals operator can work on regular numbers, but the value it produces is a Boolean value: either false or true. Similarly, 7 is greater than 5 [is] true.
We [will use] a little table, where we keep track of all the possible values of X.
X
-
T
F
We are going to see a few examples where how we are going to use this.
The operators that work exclusively on Boolean values are:
You will see why I have this picture [of] the cosmos in the background in a few seconds.
NOT is usually the easiest one to understand... you learn [it] when you are a very small child: you would [ask] your mom "hey can i haz Cheezburger?" and your mom would say "NO you may not have a cheeseburger".
[No] is one of the first words that many babies learn: negation... [the] concept "No, you cannot have something".
If I have a Boolean variable X, if it is is true, [then] NOT(X) is false. Conversely, if X is false, [then] NOT(X) is true.
X NOT(X)
----------
T F
F T
That is how NOT works. We have [presented] it here like a fancy function: the NOT function... you use it in regular everyday language all the time (the word not).
The next [operator] we are going to talk about is AND, which is also one of the first things you learn.
If you say you want to order a cheeseburger at a restaurant and the menu says it comes with fries and salad, you are going to be very excited because when you order your cheeseburger you get fries and your salad.
If you only get fries, you are going to be very disappointed because the menu said fries AND salad. If you only get salad you are going to be [equally] disappointed, so how do we look at [AND] from a Boolean perspective?
[Consider] we have variable X that represents fries, and another variable Y which represents salad.
X Y AND(X,Y)
----------------
T T T
T F F
F T F
F F F
If you get both your fries and your salad, then you got both of them so that AND function on the two Boolean variables X and Y: if X is true and Y is true, then AND(X,Y) is true.
If either one of them are false (if Y is false or X is false or they are both false) then the [result of AND] is false. That is how the AND operator works: both things must be true.
If you say you are going to get fries AND salad, then you expect to get both of them.
OR is a little trickier. If you see on the menu that the cheeseburger comes with fries OR salad, you would expect that when your cheeseburger arrives you will be getting fries, or perhaps you will be getting salad.
Let's see what our table looks like for OR.
X Y OR(X,Y)
----------------
T T T
T F T
F T T
F F F
If I say to you: "you are going to get fries OR salad" and I give you neither, the original statement was not satisfied so that is false.
If you do not get your fries but you do get your salad... that works. If you get your fries but you did not get your salad, that also works.
But, there is a row missing in this table: what if you get your fries and your salad? Is the original statement true?
X Y OR(X,Y)
----------------
T T ???
T F T
F T T
F F F
Let's have a bit of a conversation about that.
If you go to the restaurant and you order your cheeseburger and they ask you "do you want fries or salad?" and you say both, they are probably not going to be very happy with you because they intended for you to just get one of those things: fries or the salad.
Often, when you look at menus you will see the word either. You will see "cheeseburger comes with either fries or salad". That "either" word is very important because that either [is] what we call an exclusive or: you cannot have both.
When many people use OR, this is what they mean: exclusive or... you only get one or the other.
In logic, we have a special term to refer to exclusive ORs and it is called XOR.
X Y XOR(X,Y)
----------------
T T F
T F T
F T T
F F F
For [the] XOR function, you can only have one of the two variables: Either X (note how I had to use the word either there) either X or Y. If both of them [are] true then the XOR is false.
You might be thinking: "that is what I always mean with OR... do I want to go to a play OR a movie? Do I want fries OR a salad?"
We also use OR in a different way, and it may not be obvious to you until it is pointed out. Let's say you want to go to an event and they say: "we need some ID... we will accept your watcard OR your driver's license".
[If] you show up and you have both... well [in that] circumstance you would think it is ridiculous if they turn you away. In this [example] we are talking about an inclusive OR. In this situation, you can have your watcard by itself you can have your driver's license by itself or they will be perfectly happy if you have both of them.
This is an inclusive OR. For an inclusive OR, the top role of the truth table is true if X is true (you have your driver's license) and Y is true (you have your watcard) then OR(X,Y) is also true.
X Y OR(X,Y)
----------------
T T T
T F T
F T T
F F F
In computer science, and in the world of logic, ORs are always inclusive unless you say otherwise. When you are working with a computer (or you are working with Microsoft Excel).
Microsoft Excel always has an inclusive OR [function]. If you want to use an exclusive or then there is also a function XOR.
Let's go back to this picture of the galaxy with just AND, OR, NOT you can express very complex ideas and concepts... in fact, every language that [was] ever developed by a human (that we are aware) of has some form of these terms... ancient languages, modern languages, remote languages... they all have some concept of negation, some way of two specifying OR (whether it is exclusive OR or inclusive OR) and there is some mechanism for AND.
It must be that some fundamental part of our brain is hardwired to understand these concepts. If you really want to get philosophical, computers really only understand OR, NOT, AND: these three basic concepts are used to build giant computers.
As an example here is a way of saying exclusive OR using just OR, NOT, AND:
OR(AND(X,NOT(Y)),AND(NOT(X),Y))
If the menu says you can have fries but not salad or salad but not fries... then that is much clearer and this is the way you would probably express this to a computer. It looks complicated, but this is the way that an exclusive OR is written.
Fundamentals of the universe: OR, NOT, AND.
The next time you go to a restaurant and they say fries OR salad and they do not use that key word "either", then I would encourage you to give them a lecture on the difference between inclusive OR and exclusive OR and why you deserve both fries and salad with your cheeseburger.