Computer Science 220
Assembly Language & Computer Architecture

Fall 2011, Siena College

Home     Syllabus     Schedule

Lecture 0x0e: Exam and Assignment Recap
Date: Tuesday, October 25, 2011

Agenda

Lecture Assignment 0x0e

Due at the start of class, Thursday, October 27.

Please submit answers to these questions either as a hard copy (typeset or handwritten are OK) or by email to jteresco AT siena.edu by the start of class. Please use a clear subject line when submitting by email (e.g., CS 220 Lecture Assignment 0x0e, Joe Student). We will discuss these questions at the start of class, so no late submissions are accepted.

  1. In class, we saw how any boolean function can be expressed in disjunctive form -- as a disjunction (or) of a set of terms (often called min-terms), each of which is a conjunction (and) of inputs or their negations. This is a handy if you happen to be a digital circuit designer that has a very large pile of and and not gates, and one big or gate. But what if instead you have large piles of or and not gates, but only a single big and? Show that it is possible to express any boolean function as the conjunction of a set of terms, each of which is a disjunction of inputs. (4 points)
    1. Prove that deMorgan's law for converting conjunctions to disjunctions (with negations) holds for n>2 inputs.
    2. Prove that deMorgan's law for converting disjunctions to conjunctions (with negations) holds for n>2 inputs.
    3. Use these to prove the conjecture.
  2. Suppose you are interested in constructing a circuit that is high precisely when four input lines DCBA represent a prime in 4-bit unsigned binary. (6 points, 3 each)
    1. Use a Karnaugh map to generate a logical expression with the smallest number of terms that computes this function. Do not optimize the expression further.
    2. Suppose we didn't care if the function worked on the range 12..15. Use another Karnaugh map to generate a logical expression with the smallest number of terms that computes this function.

Examples