| Yale-New Haven Teachers Institute | Home |
|
|
by
Hermine Smikle.
The basic principle of the unit shows how an area of mathematics and some fundamental concepts are applicable to real life and modern Technology. Students should be encouraged to seek out areas in which this technology apply and make some comparisons of the technology now and those that existed in years past.
- a) relevant to the existing and growing needs of the society
- b) related to the ability of the student
- c) should serve as a motivator to careers that will interest the student
- d) provide the motivation for further inquiry.
Audience: This unit is designed for classes at the high school level. It can be a part of a unit in geometry, or could be used by a group of students for independent study.
- a) To help students acquire a range of mathematical skills
- b) To make mathematics relevant to the experiences of the students, there-fore recognizing mathematical principles in his environment.
- c) To apply mathematical knowledge to the solution of problems.
- d) To present a unit in the area of Boolean Algebra that is important to the understanding of circuits and how they work.
- 1 Introduction to logic:
- ____The students will be able to:
- ____a) Distinguish valid statements from those that are not valid.
- ____b) To define a statement; To use reasoning; make deductions and implications.
- ____c) To use simple connectives.
- ____d) To make truth tables.
- 2. Introduction to Binary Arithmetic:
- ____a) Define the numerals in the Binary system.
- ____b) To find the values of a numeral written in the binary system in base ten.
- ____c) To perform the basic operations in the binary system.
- 3. Introduction to Boolean Algebra.
- ____a) Simple operation with boolean algebra
- ____b) Make truth tables
- ____c) Application of Boolean Algebra to
- ________(1) electrical switches ; (using ON and OFF)
- ________(2) write truth for adders and half adders
- ________(3) designing simple circuits.
The work world of the next ten years will be demanding workers that are equipped with different basic skills; workers with the ability to think and can understand the operations of these machines developed by the new technology.
The unit attempt to show students how the application of Boolean algebra, and the binary system has spearheaded work in these new technologies. After the unit it is hoped that students will reconsider the options available to them and make more careful and informed decisions as to their career choices.
The unit will begin by discussing the implications of Reasoning and deduction in the formal setting, with extensive work in the binary system and then a simple introduction to boolean algebra.
It is hoped that this unit will find a place with those teachers that are theorists, and those that enjoy working with the hands on experiences that are meaningful for students.
Because of the limitation of space for the unit there will be the need for the users to research additional problems from the reference given.
The starting point of logic is a statement. A statement in the technical sense is declarative and is either true or false, but cannot be both simultaneously.
In logic it is irrelevant whether a statement is true or false, the important thing is that it should be definitely one or the other. Logic statements must be either true or false.
A Statement: is a declarative sentence which is either true or false.
Examples of declarative statements:
The following are not statements:
- (a) New Haven is a city in Connecticut.
- (b) The month of June has thirty days.
- (c) The moon is made of red cheese.
- (d) Tomorrow is Saturday.
Those are not good statements because they cannot be considered true or false.
- (a) Come to our party!
- (b) Is your homework done?
- (c) Close the door when you leave.
- (d) Good by dear.
The basic type of sentence in logic is called a simple statement. A simple statement is one that has only one thought with no connecting word.
Examples of simple statements
If we take a simple statement and join them with a connecting word such as and, or, if . . . then, not, if and only if, we form a new sentence called a complex or compound statement.
- (a) Three is a counting number.
- (b) Ann is early for class
Compound Statements: are formed from the combination of two or more simple statements.
Example (a) Ann is early for class and she has her note books. (b) Three is a counting number and is also a odd number.
We are familiar with using letters as replacements in algebra; in logic we can also use letters to replace statements. The common letters used to replace statements are P,Q, R: but any letters can be used.
- 1. A negation: formed when we negate a simple statement by “not”.
- ____example : Simple statement: Today is Thursday
- ____Compound statement: negation: today is not Thursday
- ____The sentence “today is not Thursday” is a compound statement called a negation.
- 2. When we connect two simple statements using and, the result is a compound statement called a conjunction.
- 3. If the simple statements are joined by or the resulting compound statement is called a disjunction.
- 4. The If . . . then connector is used in compound statements called conditionals.
- 5. The if and only if connector is used to form compound statements called biconditionals.
but P and Q would read Today is Saturday and I passed my test. It is also common practice to use symbols for the connective words (or the connectors)
Examples. P = Today is Saturday Q = I passed my test
TRUTH TABLES: Since a statement in logic is either true or false, we should be able to determine the truth or falsity of a given statement. [Logic is very precise. There should be no worry about ambiguity] Let P be a statement; then ~ P means ‘not P’ or the negation of P. The negation of P is true whenever the statement P is false and false if P is true. These situations are confusing to write, therefore we can record these statements in a truth table.
Connectors Symbols (a) not ~ (b) and ^ (c) or (figure available in print form) (d) if . . . then Ð> (e) if and only if Ð>
In the first column, there are two possibilities of P; P is either True or False. Each line in the table represents a case that must be considered. In this case, there are only two cases. The truth table tells us the truth value of p in every case.
- Example 1: Let P = this is a hard course.
- ________ ~P= this is not a hard course.
- ________ Truth Table
p ~p where T = True and T F F = false F T
| Let | P = Today is Monday |
| Q = I have a Math class. |
____ Truth Table
| P | Q | P^Q | |
| T | T | T | |
| T | F | F | |
| F | T | F | |
| F | F | F |
In the compound statements, the individual statements are called components. In a compound statement with two components such as p ^ q there are four possibilities. These are called logical possibilities. The possibilities are:
The four possibilities are covered in the four rows of the truth table. The last column gives values of p ^ q; This is only true when both p and q are true. Using the examples given, truth tables of a more complicated nature can be built.
- 1) p is true and q is true
- 2) p is true and q is false
- 3) p is false and q is true
- 4) p is false and q is false.
Let us consider the situation p v q
Example 2:
| P | Q | P v Q | P = Today is Tuesday |
| T | T | T | Q = I have a Math class |
| F | T | T | P v Q = Today is Tuesday or I have a math class |
| F | F | T | |
| F | F | F |
Find the Truth Table of [ ( p) ^ ( q) ]
Example 3:
Truth Table
| p | q | ~p | ~q | (~p) ^ ~ q | ~ [(~p) ^ (~q)] |
| T | T | F | F | F | T |
| T | F | F | T | F | T |
| F | T | T | F | F | T |
| F | F | T | T | T | F |
The given [ (~p) ^ (~q) ] uses parentheses and brackets to indicate the order in which the connectives apply. Expressions can be simplified by removing some of the parentheses, thus (p) ^ ( q) can be written as ~ p ^~ q.
It can be noticed from the Truth Table in examples 2 and 3 that the last columns are the same. Thus we say that these statements are logically equivalent and can be written P = Q and P v Q = (~p ^ ~q).
| Let | P = You passed English |
| Q = You will graduate |
____Truth Table
| P | Q | PÐ>Q | |
| T | T | T | |
| T | F | F | |
| F | T | T | |
| F | F | T |
The statement P Ð> Q reads if you pass English then you will graduate. This statement is false only when you pass English (true) but you will not graduate. Therefore the final column will be true in every position but the second.
The connective Ð> is called the biconditional and may be placed between any two statements to form a compound statement P Ð> Q (reads P if and only if Q).
The Truth Table For P Ð> Q
| P | Q | P Ð> Q | PÐ> Q | QÐ> P ( P (Ð> Q) | ^ ( Q Ð> P) | |
| T | T | T | T | T | T | |
| T | F | F | F | T | F | |
| F | T | F | T | F | F | |
| F | F | T | T | T | T |
| From the truth table it can be noticed that P Ð> q = ( P Ð> Q) ^ (QÐ>P). |
Sample Problems for Students: |
- 1. In these problems English sentences are given. In each case determine whether the sentence is a statement or not.
(a) On March 8, 1922 snow fell in Atlanta. (b) Mary has big feet. (c) How much did you pay for that car. (d) Keep off the grass. (e) Five is a prime Number. - 2. If you accept the sentences in column 1 what can you say about the statements in column 2
Column 1 Column 2 (a) The order of 1, 2, 3, 4, 5, 6 on The relationship between 5 and 2 number line (b) That a head and a tail are The number of heads most likely equally likely on the toss to be obtained in 600 throws of a coin (c) That a parallelogram can be The figure ABCD is a parallelogram formed two congruent triangles (d) If all policemen are over Mr brown is a policeman six feet tall.
| (e) A person must be 16 years to | Junior is driving a car | |
| drive a car |
| (a) ~(~P) | (b) ~PÐ> ~ Q | (c) ~ PÐ> Q | |
| (d) P ^ QÐ>P | (e) ~ pÐ>Q | (f) ( PÐ>Q) v PÐ>Q | |
| (g) P ^ Q P v Q | (g) (PVQ) ^ R | ||
| (h) (P ^ Q) v (P ^ Q). |
| (a) ~ (p ^ Q) | (b) PV~Q | (c) ~ ( Pv~Q) |
SECTION 2 |
The Binary System |
Example of the comparison of Binary and Decimal Systems.
| Decimal system | Binary System |
| 103 102 101 100 | 24 23 22 21 20 |
The arithmetic in the binary system employs the same operations as the decimal system but may be considered simpler. The addition involves grouping things in groups of twos with carrying to the next higher power.
| Example (a) | 10 + 10 |
| 10 | |
| + 10 | |
| 100 |
carrying to the next higher power.
| Example | (a) 110 means | 22 + 21 + 0 |
| =4 + 2 + 0 | ||
| = 6 | ||
| (b) 101 means 22 + 0 + 20(1) | ||
| =4 + 0 + 1 | ||
| =5 | ||
| (c) 11001 | means 24 + 23 + 02 + 01 + 20 | |
| =16 + 8 + 0 + 0 + 1 | ||
| = 25 |
Multiplication is also a straight forward procedure, since each digit is either 0 Or 1; therefore each potential product is either zero or one.
| Example | 10 x 01 | |
| 10 | 10 | |
| x01 | x 10 | |
| 10 | 00 | |
| 10 partial products | ||
| 100 |
The rule for multiplication is simply to write down the multiplicand shifted one place to the left for each of the multiplier that is a one the sum the numbers.
In summary then since binary operations uses the same concepts of value and positions of digits as the decimal system, the associated arithmetic is the same.
In addition we add column by column, carrying where necessary to higher positions. In subtraction we subtract column by column, borrowing where necessary from higher positions, and in division we do repeated subtractions just as in long division.
| Examples | 1. Addition | 2. Subtraction | |
| 1110 | 1101 | ||
| +1011 | Ð1010 with borrowing | ||
| 11001 | 0011 | ||
| Multiplication | Division |
| Example | Change 18 to its binary equivalent |
| Operations | Meanings | Symbols | |
| or | Determine a single input | + A+B | |
| bit from the values of two or | |||
| more input. |
| and | Determines a single input | . A.B or AB |
| bit from the value of two | ||
| or more input |
| not | Changes binary bits to its | not A; bar over A |
| opposite value. |
Any relationship between logical variables are called logical expressions. These expressions can be written as an equation for example the equation A + B + C = F where F is the name of the output variable. The expression A + B + C = F expresses the action of and/or function. Through Boolean Algebra logical analysis can be performed using these three functions.
The electronic representation of these functions are called logic gates. There are the and gate the not and the or gates. These logic gates are basic functional units for both arithmetic and logic operations; to operate they must accept binary numbers, and should have a carry bit of one or 0, (from the adjacent lower power of two), and should produce as outputs a sum bit and a carry bit for the next higher power of two.
Truth Tables
| (a) A | A | (b) | A | B | A.B | (c) A | B | A + B | |||
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | ||||
| 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | ||||
| not | 1 | 0 | 0 | 1 | 0 | 1 | |||||
| 1 | 1 | 1 | 1 | 1 | 1 | ||||||
| and | or |
With proper input electronic digital circuits (logic circuits) establish logical manipulate paths. By passing binary signals through various combination of logic circuits, any desired information for computing can be operated on; each signal represents a binary carrying one “bit” of information.
The logic circuits or gates perform the logical operations.
- 1 And gate
- ____Two and three input And gates.
- 2 Or gate
- ____Two and three input Or gate.
3 Not (the not gate is sometimes called an inverter)
Some Booleen functions have identical truth tables therefore their logic circuits serves identical purposes; but one may be preferable to the other. To do this more useful logic gates are created. The following gates NAND, and NOR were created for this purpose.
Examples of Truth Tables for Nand and Nor
Nand equation (figure available in print form).
| A B F | Nand GATE |
| 0 0 1 | A |
| 1 0 1 | B |
1 1 0
| Nor equation F = A + B | Nor gate |
| 0 0 1 | A | |
| 1 0 0 | B |
1 1 0
Truth Table for Half adder.
A B C S
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0
The fourth row shows 1 + 1 = 10, here 1 is the carry to the next higher power of two.
S = A + B
C = AB
Truth Table for Full Adder.
A B Z C S
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
| 0 1 1 1 0 | (figure available in print form) |
| 1 0 0 0 1 | (figure available in print form) |
1 1 1 1 1
Implementation of Boolean functions: The translation of the Boolean function to logic circuits is called the implementation. The is the mathematical expression representing a combination of gates. Remember that a basic logic gate performs a single elementary logic operation and their input-output can be expressed as a logic expression.
These logic expression can be represented by a diagram.
GATES, LOGIC EXPRESSIONS AND THEIR DIAGRAMS
AND GATES
| NAND | NOR |
| Inputs | outputs | |
| A B | F | |
| 0 0 | 0 | |
| 0 1 | 1 | |
| 1 0 | 1 | |
| 1 1 | 1 |
OR GATE
The truth table explains the result F from the possible values of A and B
| AND | GATES |
| Inputs | Outputs | |
| A B C | F | |
| 0 0 0 | 0 | |
| 1 0 0 | 1 | |
| 0 1 1 | 1 | |
| 1 1 1 | 1 | |
| 0 0 1 | 1 | |
| 1 1 0 | 1 | |
| 1 0 1 | 1 | |
| 0 1 1 | 1 | |
| 1 1 1 | 1 |
If a small circle is placed at an input or output of a symbol for a logic gate it indicates negation.
- 1. If the small circle is placed at an input terminal, if the symbol entering is one the symbol leaving the circle and entering the block is 0.
- 2. If the circle is placed at the out block
- ____(a) if the symbol leaving the block (and entering the circle) is 0, the symbol leaving the circle is 1.
- ____Truth Table
Input Output A B C F 1 0 0 1 0 0 0 1 1 1 0 1 1 0 1 1 0 1 0 1 0 0 1 1 1 1 1 0 0 1 1 1
from these we can write truth tables to show the desired operations (or, and).
let high voltage = 1 or let high = 0 low voltage = 0 low = 1
| Input | Output | ||
| A | B | F | |
| low | low | low | |
| low | high | high | |
| high | low | high | |
| high | high | high |
or operation
| Input | Output | input | output | ||
| A | B | F | A | B | F |
| 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 |
Objective The student should be able to
Make deductions and draw the necessary conclusions from a given statement.
Development 11,
- ____(a) Discuss real life situations where the outcomes can be predicted on the basis of past experience.
- ________Encourage students to examples of their own experiences
- ____(b) Introduce familiar examples for discussion
- ________Examples It looks like its going to rain.
- ____(c) Discuss reasons that make us believe that it is going to rain.
- ____(d) list these conditions on C.B.
- ________After several examples introduce the word reasoning as used to describe the thought process used.
- 2. Draw a rectangle on the C.B, cut out a congruent rectangle on cardboard. Fit the cut out rectangle on the one on the C.B in different ways. Have students give the relationship that exist between the opposite sides and opposite angles. Use this as an example to introduce deductive reasoning. Summarize that because the rectangle can fit its outline in four different ways we deduce that opposite sides and angles are congruent.
- 3. Introduce the idea of a situation that is universally accepted. From these draw conclusions or make deductions.
- ________Introduce the word premise. This word describes situations that are taken for granted, from these premises conclusions can be drawn.
- 4. Introduce sentences that contain the words such as “if”, “because”, “therefore”, “consequently”, “it follows that”, and “it may be deduced from, it is evident that”; these statements are examples of deductive arguments.
- 5. Provide sentences for discussion.
- ____example (a) It is accepted that
- ________When it rains the sky is dark. What can we deduce? example (b) Every English. teacher has a good knowledge of English
- ________Mr Brown has a good knowledge of English What deductions can be made. Discuss are all people with good knowledge of English, English teachers.
Evaluation (a) Have students make up statements and discuss the deductions that can be made. (b) Use accepted premises and draw conclusions.
Objectives
(a) students will be able to tell sentences that are statements.
(b) Use connectives to form compound statements
Development
- (a) List various different sentences on C. B. have students decide whether each sentence is true or false. (Does the sentences convey some specific idea).
- Examples
- ____(1) It is blue.
- ____(2) Is your homework finish yet?
- ____(3) Three is a prime number.
- ____(4) February has 31 days.
- ____(5) George Bush is president.
- 1. Discuss each sentence indicate that those sentences that cannot be said to be true or false. Define a statement as a sentence that has one idea that can be classified as either true or false.
- 2. Discuss the criteria of a simple statement. List various examples of these on C.B. Have students identify the one idea of these statements.
- 3. Introduce the vocabulary “connective”. From simple statement make up compound statements. Give these their names as they are made up.
- Example:
- Today is sunny and I will take a walk. 28
- I will go dancing or I will go riding.
- I will go riding if you will come with me. Introduce idea from algebra that letters can be used to replace numbers. Here letters will be used to replace statements.
- Let Today is Monday = P
- I will go dancing = Q
Make up mathematical sentences
P and Q [use this idea with different connectives] Introduce the symbols for each connectives. Thus P and Q can be written as P ^ Q.
Evaluation: Have student make up their own simple and compound sentences.
Give statements and have students write them using the symbols.
Objectives The students will be able to construct truth tables representing different compound statements
Development
- ____(a) Review the different types of connectives that can be used to generate compound statements.
- ____(b) Choose the and connective ( ^ ) and make a compound statement
- Example
- ____P = today is Tuesday
- ____Q = I have a math class
- ________Today is Tuesday and I have a math class.
- ____(c) Examine the possibilities that can result from this statement
- ____(d) Construct truth table on C.B.
- ____(e) Stress the use of the vocabulary
- ________ (i) Component
- ________ (ii) Logical possibilities
- ________(iii) Conjunction of P and Q
- ____________Example the results of the truth table.
- ________Leading questions
- ____________(a) In what case is P ^ Q true?
- ____________(b) When is the statement false?
- ____________(c) How many possibilities will there be?
- ____(f) Choose different statements and use different connectors to form compound statements: Use similar reasoning to form truth tables
- ________Emphasis on “and”, “or” and “not”.
Evaluation
- ____(a) Have students generate their own statements and form truth tables.
- ____(b) Give simple examples for students to complete.
Problems
(a) (P). (b) P ^ Q. (c) P ^ Q (d) (P ^ Q)
Objectives
(a) The student will be able to read a base two number
(b) To convert base two to base ten
Development
- 1. Introduce binary numbers by having students group a number of articles (match sticks, small cubes, pebbles, etc) in groups of twos.
- 2. Have students re-count the objects but now using only the digits zero and one {0,1}.
- 3. Introduce the place value chart for binary numbers.
- 4. Practice changing from base two to base ten by writing the base two digits on the place value chart.
- 5. Provide many problems for drill and practice.
- 6. Use re grouping to change base lien numbers to base two.
- 7. Introduce the method discussed in the content.
Evaluation
- ____(a) Have students count in base two.
- ____(b) Use their place value chart to do conversion
- ____(c) Use re-grouping to change from base ten to base two.
Materials to be Used
- 1. Make a Binary Counter
- ____Materials needed: board for sides, wire, cards with zero and ones. A wire runs from end to end and passes through a number of cards. Each card has a zero or on one side and a one on the other [ make as many positions as needed]. By turning them around the cards can be made to indicate a given binary number. This can be used to convert from binary to decimal.
- 2. Windows can be made in a rectangular piece of card board which is glued to a similar beck board. Slits are made for the tabs to slide in.
- ________The tabs would show either on or off. 1 = on, 0 = off. This can be used to show a binary number.
Problem Solving
(a) A cross word puzzle.
| Across | Down | |
| 1. 10001 Ð1101 | 1. 100011 Ð101 | |
| 10. 1+ 111 +1111 | 10. 101 X 110 | |
| 101. a prime number | 11. the solution of the equation | |
| X+11=1010 |
Objectives
- ____(a) The students will be able to apply simple ideas from Boolean algebra and write truth tables.
- ____(b) From the truth tables the students will able to implement logic circuits.
Development
- ____(a) Review simple statements and their connectives.
- ____(b) Introduce the basic principles of boolean algebra.
- ________The Elements ( 0,1)
- ________the operations of addition, multiplication and negation
- ________The elements are used in the truth tables instead of true or false
- ____(c) Discuss dualities that can be considered true or false, on or off, closed or opened
- ____(d) Replace the operations (+, x) by or and and
- ____(e) Review truth tables from the previous section with zero and one
- ____(f) Introduce equations from these truth tables. ex. F = x + y. ( where x and y are inputs and F the output
Evaluation
(a) Provide drill and practice using zero and one in the truth tables
- 1. The state of an electrical switch is either on or off. Use zero or one to represent these states.
- 2. Develop truth tables using the connectives.
- 3. Discuss the position of switches when opened or closed.
- 4. Use equations to summarize the desired outcomes. Thus introducing the implementation of boolean algebra with logic gates.
Write equations of desired outcome
ex. F = X + y [use all connectors].
Write truth table table
| Draw logic gates. | (e) And gates denoted by: |
Suggested problems
- 1. Write a truth table for the following;
- ____(a) Nand F = (Xy).
- ____(b) And F = (X + y)
- ____(c) F=(X+y)
- 2. Construct a truth table for the gate shown.
- 3. Design a truth table for a half subtractor
- ans. X y b d
- ____ 0 0 0 0
- ____ 0 1 1 1
- ____ 1 0 0 1
- ____ 1 1 0 0
- 4. Design a truth table for a full subtractor.
- ans X y z b d
- ____0 0 0 0 0
- ____0 0 1 1 1
- ____0 1 0 1 1
- ____0 1 1 1 0
- ____1 0 0 0 1
- ____1 0 1 0 0
- ____1 1 0 0 0
- ____1 1 1 1 1
- 4. Construct a truth table for
- 5. Make a truth table to show that
- ____ CD=C+D
- 6. Given the following write an equation for
- ____ (a) X (b) Y (c) F
- ____ ans X = AB
- ____ Y=(AC)
- ____ F=X+Y+B
- 7. Write truth tables for F = AB + AC
- ____draw the logic gate
- 8. Design a circuit such that a hall light can be controlled by both an upstairs and a down stairs switch.
- 9. Design a circuit such that a light can be controlled by each of three switches.
- 10. What is the Boolean expression for the AND OR logic diagram
- ____ans; AB + AC = F
- 11. What is the truth table for the design in 10
- ____ans; input output input output
A B C F A B C F 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 1 1 1 1 1 1
2. Lin, Shun Yeng, and You Fen Lin, Set Theory with Applications. Book Publishers Inc; Tampa Florida.
3. Oldham, William G., and Schwartz, Steven E. An Introduction to Electronics. Holt Reinhart Winston.
4. Smith, Ralph J. Electronics Circuits and Devices. Second edition Wilby.
Contents of 1989 Volume VII | Directory of Volumes | Index | Yale-New Haven Teachers Institute
| ||||||