--- Simple logic gates ---
2.1.11
Define the Boolean operators: AND, OR, NOT, NAND, NOR and XOR.
Teaching Note:
LINK Introduction to programming, approved notation sheet.
Sample Question (in this case, sort of...) - FORMER CURRICULUM
The method logic1(), shown below, returns the output from a particular logic gate.
The logic gate has two inputs, a and b.
//parameters a and b can only have the values of 0 or 1
public boolean logic1(int a, int b){
if(!(a==b)) return true;
else return false;
}
(a) Identify the logic gate represented by the above method. [1 mark]
(b) Construct the method logic2(), which would similarly return the output from
a NAND gate. [2 marks]
Possible "Spiraling" Through Logic Gates:
Step 1: Look at all three 2.1.11-13 in a "mercenary" way; just, how can you do these things /answer these assessment statement "at face value" And definitely mainly relate them to what you already know: compound boolean conditions in Java.
Step 2: Then look at the advanced material, including the video on transistors, the videos showing logic gates as dominoes, and even the crazy intense Crash Course videos.
Step 3: Then, spiral through once again the more IB CS assessment statement related part, keeping in mind what you are working with is actually happening at the very low level of transistors.
____________________________
Preamble
The only confusing part of this assessment statement is that you can interpret/apply it four different ways. But the fundamental concept is the same.
You can "define" boolean operators by:
1. In a dictionary, Boolean Logic, or Boolean Math way.
2. How they are applied in a specific programming languages like Java.
3. A truth table. (2.1.12)
4. How they operate as actual circuit logic gates. (2.1.13)
The details will follow in this assessment statement and the next, but as an overview, and also as a very useful "second spiral" just before a test/exam, take a look at this question.
Question:
(a.) Define the AND boolean operator by truth table.
(b.) Define the AND boolean operator according to Boolean logic.
(c.) Define the AND boolean operator as it is used in compound conditions in the Java programming language.
(d.) Define the AND logic gate used in microprocessors.
Answer:
(a.) Truth table for AND:
A B A and B 0 0 0 0 1 0 1 0 0 1 1 1
(b.) Boolean Logic AND: The overall value of an AND expression is true only when both operands are true.
(c.) Java AND operator: The AND operator in Java is &&. A compound condition using the && operator will only evaluate to true if both conditions/variables are true. For example, if boolean a = true; boolean b = false; and boolean c = true; then (a && b) evaluates to false, but (a && c) evaluates to true.
(d.) AND Logic Gate: The AND logic gate is a circuit which has two inputs. It is designed such that only when both of the circuits are closed (i.e. a closed path through which electricity can flow) will the oeverall gate allow electricity to be passed through it.
______________________________________
Boolean Operators in Programming
Of these four applications of boolean operators, it makes sense to start with Boolean operators in the context you have (likely) already seen them: programming, in particular compound conditional statements in Java.
--------> Do make a point of going to a programming IDE (like Netbeans or IntelliJ IDEA) and playing around with boolean logic again to remind yourself how it works.
Java Boolean Operators:
AND - &&
OR - ||
NOT - !
XOR - ^
NAND - !( && )
NOR - !( || )
5 package mrrayworthoctober; 6 7 /** 8 * 9 * @author John Rayworth 10 */ 11 public class ForBooleanOperators { 12 public static void main(String[] args) { 13 boolean a = false; 14 boolean b = false; 15 boolean c = false; 16 17 // AND 18 if(a && b){ 19 System.out.println("a and b are true"); 20 21 } 22 23 // OR 24 if(a || b){ 25 System.out.println("Either a or b are true (and possibly both are.)"); 26 } 27 28 // NOT 29 if(!a){ 30 System.out.println("a is the opposite of what it was first declared."); 31 } 32 33 // NAND 34 if(!(a && b){ { 35 System.out.println("It is not the case that a and be are true."); 36 } 37 38 // NOR 39 if(!(a || b)){ 40 System.out.println("It is not the case that one or the other (or both) are true"); 41 } 42 43 // XOR 44 if(a ^ b){ 45 System.out.println("Either a or b are true, but not both."); 46 } 47 } 48 49 } 50
Programs that demonstrate AND & OR and NAND & NOR
And and Or proven with Java
NAND and NOR proven with Java
____________________________
Now to the Definitions
In terms of the assessment statement, how would we define boolean operators?
Well, there are actually a couple of ways of "defining" boolean operators, one is with truth tables (see the next assessment statement), and one is the dictionary way. This assessment statement deals with the dictionary way. (But even the "dictionary" way can be either in terms of logic gates in the circuitry of computers, or in terms of boolean programming constructs - see the "Details" below.)
Basic Boolean Operators Definitions
AND - both boolean variables must be true for the overall expression to be true.OR - at least one of the boolean variables must be true for the overall expression to be true.
NAND - the two boolean variables can't both be true for the overall expression to be true.
(Alternatively, "returns the opposite boolean value of an AND expression").
NOR - neither of the boolean variables can be true for the overall expression to be true.
(Alternatively, "returns the opposite boolean value of an OR expression.")
NOT - inverts the value of a boolean expression.
XOR - only one of the boolean variables can be true for the overall expression to be true
More Complete Definitions; including Java example
Keep in mind that we can see that Boolean operators can actually be further defined in terms of both:
--> Boolean Compound Conditions, as in Java
--> Logic Gates, at an electrical level
| AND | Boolean Math: only when both boolean values are true is the overall expression true.
Logic gate level: Electricity flows when both input switches are closed (i.e. electricity is flowing through both of them). |
| OR |
& Logic gate level: Electricity flows when one input switch or the other is closed. |
| NAND |
& Logic gate level: Electricity flows when at most, one switch can be closed (so not both). |
| NOR |
& Logic gate level: Electricity flows though the whold circuit only when both input switches are open. |
| NOT |
& Logic gate level: Electricity flows when the input is not on (otherwise the overall gate is turned off if its input was on). |
| XOR | Boolean Math: the overall expression is true only if one but not both of the boolean values are true.
& Logic gate level: Electricity flows when one switch or the other is closed, but not both. |
------------------- EXTRA OPTIONAL -------------------
Making the Connection to Logic Gates
The logic discussed above does not just function at a higher level via programming, it is fundamentally the way computers work at the most basic level, right on the CUP and other microprocessing chips.
Transistors on Microprocessors
The first thing you probably need is an idea of what a circuit, or more particularly a transistor is. And you should appreciate that in terms of a computer a transistor is the logic gate which a the single fundamental component of all microprocessing chips like the CPU. Here's an excellent introductory video:
(Sorry, but I've lost the reference to credit the source of this.)
Logic Gates
Logic gates are the basic building blocks of microprocessing chips, including the CPU and RAM memory. They are simple transistors that have one output, and usually two inputs. Current of two different levels is passed to the inputs. Depending on the kind of logic gate it is (AND, OR, XOR etc.) only certain combinations of low/high current (low-low, or high-low etc.) will cause the circuit to be closed - i.e. to allow electricity to pass through it.
Here is a diagram of an AND gate, in which both inputs have to have high current for the circuit to be closed, and electricity flow through the logic gate.
And here is a diagram of an OR gate, in which one or the other inputs have to have a high current for the circuit to be closed, and electricity flow through the logic gate.
Logic gates can be combined. Here's an example. (More on this in the next two assessment statements.)
.C.svg)
*** A key realization for you to understand at this stage is that the result of various boolean operators and their logic gates counterparts is the same***. In fact the way a microprocessor is built from the ground results in operations entirely based on boolean logic. So everything being said about logic gates can be said about the boolean operators used in a programming language, and vice versa.
So, next, check out this great video explaining logic gates with dominoes. (Thanks Mr Walker!)
And the "logical" follow-up video. (All of this does go a bit beyond what you need for IB CS and this assessment statement, but it's kind of a shame to not go any further, because a few learnings on, and you can understand pretty well completely the basic operations of a computer.)
Plus the two appropriate Crash Course Computer Science videos (Take a deep breath!!):
Crash Course # 3 - Logic Gates
Crash Course # 5 - The ALU
Also note that the former curriculum "Red & Yellow" IB CS textbook has a good summary on pages 230 - 237.
Why XOR?
It is easy to understand why we may want to do something if one thing or another were true, or if both things were true, but you may wonder: why would we ever want to do something if either input was true, but not both?
The general answer is: when something else is done if both are true.
Half-adder Circuit
The best example is the most basic way that circuits achieve addition, the "half adder". With the half adder we want to add two one digit numbers, and have an extra place for the carry digit if needed. Here are the four possible input combinations A and B:
0 + 0 = 0 0 (The right hand place is the "sum" place, and the left hand place is the "carry" place.)
0 + 1 = 0 1
1 + 0 = 0 1
1 + 1 = 1 0 (In this case, we have to "carry the one".)
When one or the other input is 1, but not both the sum should be 1. A XOR B = 0 1
But when both are 1, the sum is 0, and the carry should be 1. A AND B = 1 0
After having done the next couple of assessment statements, you can look back at the following table and circuit diagram.
The truth table for the half adder looks like this:
| Sum | Carry | ||
| A | B | A XOR B | A AND B |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
And so the circuit diagram for a half adder looks like this:
