SUNY Geneseo Department of Computer Science

Boolean Logic

Previous Lecture

Misc

No Friday office hours this week

(And I will be off campus after about 10:30 tomorrow)

Questions?

Reading Summary

Sections 5.1 - 5.3

Boolean logic, a way of testing truth/falsity

• e.g., in if - then - else
• Action, alternate action

Logic

Conjunction = and, notated ^

• Both parts must be true

Disjunction = or, v

• One part true

Negation = !, -,

• Changes value to opposite

Implication, e.g., p -> q

• Always true except when p true and q false

(Truth tables)

Law of excluded middle: p v ~p is always true

Double negation: ~(~p) = p

Simplification

• p v p = p
• p ^ p = p

Commutative law

• p v q = q v p

Associative law

• p ^ ( q ^ r) = (p ^ q) ^ r

Vacuous cases

• Ways of simplifying given hint re truth value, e.g.
  • p v true = true
  • p v false = p

de Morgan's Law explains how to simplify negation in front of parentheses, e.g.,

• ~(pvq) = (~p) ^ (~q)

Distributive Law

• e.g., p v (q^r) = (pvq) ^ (pvr)

p, q can be statements in Java

Boolean algebra can lead to clearer, shorter, more direct expressions in programs

Applications of Logic

Cylinders (from graphics / geometry)

• What would a test to see if point (x,y,z) is inside the cylinder look like?

    if (  0 < z  &&  z < h  &&  x*x + y*y < r*r  )

• How about a test to see if (x,y,z) is on the cylinder?

    if (   (    x*x + y*y == r*r
             && z > 0
             && z < h )
        || (    x*x + y*y <= r*r
             && ( z == 0 || z == h )) )

A robot problem: Move a robot forward until it either is on a red tile or to a wall.

    // in some subclass of Robot:
    while (    this.colorOfTile() != java.awt.Color.red
            && this.okToMove() ) )
        this.move()

Non-Programming Applications of Logic

Databases

• Simple relational database is a table of records:

• Extract data by specifying criteria records must meet to be selected, and the fields you want
  • e.g., pick out the names of students taking CSci 141:
    • select name where course = "Csci 141"
  • How about names of students getting an A (average > 90) in Math 100?
    • select name where course = "Math 100" and average > 90

Hardware

• "True" and "False" are easy to represent electrically, and basic logic operations are easy to implement electronically.
• This is how computers work internally
• Typical arithmetic unit and "condition codes"

• Condition codes summarize the last result from arithmetic unit
• So, machine-level implementation of something like if ( a < b ) .... is roughly
  • Subtract b from a (throw away result)
  • If Negative ... (use condition code)
• How would you implement <=, >, >=, != ?
  • != is.... not(Z)
  • a <= b is ...
    • Subtract b from a
    • if or( N, Z )...
• Numbers
  • Represent numbers 0 and 1 with logic values
    • 0 = false
    • 1 = true
  • (use base 2, binary, to extend this to higher numbers)

Next

Introduction to Recursion

Read Sections 6.1 - 6.3

Next Lecture