Comp 200: Modeling and Abstraction

[an error occurred while processing this directive] [an error occurred while processing this directive] Comp 200: Modeling and Abstraction

COMP 200

Elements of Computer Science

Boolean Algebra and Conditionals

Read section 4 of HTDP.

Conditionals

Problem 1: The following is the labbie pay rate at the CS Department.

$10 for labbies with less than one year of experience
$11 for labbies with a year or more of experience.

Write a function that produces the pay rate given the number of years of experience.

The main data in this problem are numbers representing the years of experience. It is partitioned into two parts:

less than one year
greater or equal to one year.

To process this data, we need to have a way to check for the range in which the input data belongs. In Scheme, we use what is called a "cond." Here is the Scheme function that computes the above pay rate.

;;contract: pay-rate number->number 
;;header: (define (pay-rate years)...) 
;;purpose: (pay-rate years) returns 10 if years<1, 11 otherwise 
;;examples:
;;(= (pay-rate .5) 10) 
;;(= (pay-rate 1) 11) 
;;(= (pay-rate 2) 11) 
;;definition: 
(define (pay-rate years) 
  (cond 
    [(< years 1) 10]
    [(>= years 1) 11]))

The syntax for cond is as follows.

(cond
  [booleanExpr1  returnValue1]
  [booleanExpr2  returnValue2]
  etc...
  [else  catchAllReturnValue])

In the above, booleanExpr1, booleanExpr2 denote what is called "boolean expressions." A boolean expression is something that represents true or false. Scheme has two atomic expressions, true and false, to represent the notion of truth and falsity.

The semantic for cond in the above is as follows.

evaluate boolExpr1: if true evaluate and return returnValue1 and the computation is done, else if false
evaluate boolExpr2: if true evaluate and return returnValue2 and the computation is done, else if false
continue to evaluate down the list of conditionals until a true expression is found and evaluate and return the corresponding value; if all are false then
evaluate and return the catchAllReturnValue, and the computation is done.

Boolean Algebra

Boolean algebra (named in honor of the mathematician George Boole who invented a pure logic math "game" just for the fun of it) deals with the formal computation of true/false. There are three operations on true/false: AND, OR, NOT. Here are the rules describing these operations. They are displayed in the form of "truth tables."

x	y	x AND y
T	T	T
T	F	F
F	T	F
F	F	F

x	y	x OR y
T	T	T
T	F	T
F	T	T
F	F	F

x	NOT x
T	F
F	T

All logical expressions can written in terms of the above three operations! Actually, we only need AND/NOT or OR/NOT. Electrical engineers use boolean algebra as the tool to design electronic circuitries. They build what is called "logic gates" that correspond to the boolean operations AND, OR, NOT, and from there, the digital computers!

Diagrams representing logic gates (to be drawn in class).

In class exercises

Build the truth tables for
1. NOT (x AND y)
2. (NOT x) OR (NOT y)
3. NOT (x OR y)
4. (NOT x) AND (NOT y)
5. (NOT x) OR y
What do you observe from 1.a and 1.b?
What do you observe from 1.c and 1.d?
How can we express x AND y in terms of NOT/OR?
How can we express x OR y in terms of NOT/AND?

De Morgan's Laws

NOT (x AND y) = (NOT x) OR (NOT y) (see exercise 2 above)
NOT (x OR y) = (NOT x) AND (NOT y) (see exercise 3 above)

What do we mean by "if x then y"?

Given two boolean expressions x, y, we define "if x then y" to be the boolean expression (NOT x) OR y.

Solving Logic Problems using boolean algebra and logic gates

Example (from Principles of Computer Science by Cullen Schaffer, Prentice Hall 1988):

Ed will go to the party if and only if Dan or Carol goes.
Dan will go if and only if Ann goes and Bob does not.
Ann and Carol and Bob have decided not to go.
What will Ed do?

Solution (to be discussed in class)

Let E be the statement Ed goes, D be the statement Dan goes and C be the statement Carol goes. Statement1 of the problem translates into E = D OR C.
Let A be the statement Ann goes and B be the statement Bob goes. Statement 2 of the problem translates into D = A AND NOT B.
Statement 3 of the problem translates into A, C, B are false.
Statement 4 of the problem can be best answered by building a logic circuit for E in terms of A, B, C, D and examine the value of E when A, C, B are false.

Using EXCEL to do Boolean Algebra

In class exercises; We will the Logical functions in EXCEL to set up truth tables for all the exercises done in the above.

Click here to download the solution.

Last revised 08/26/2007 12:00 AM

Maintained by the professor; see contact information on the course home page