CS 60, Fall 2002

Assignment 10,

Due Midnight, morning of Mon. 21 April

 

Logic Applications

 

This assignment employs two programming languages: rex is used to illustrate some aspects of logic circuit implementation, while Prolog, based on predicate logic, is used to illustrate databases and backtrack programming. For extra credit, you can show some relationships between Prolog and rex.

 

Reading: You should read chapter 10 in the textbook. Problems 1 and 2 require rex solutions, while problems 3 and 4 require Prolog. In addition to the textbook, other Prolog resources can be found on the course web pages:

http://www.cs.hmc.edu/courses/current/cs60/references/

http://www.cs.hmc.edu/courses/current/cs60/examples/prolog/

 

Logic circuit implementation: In this part of the assignment we are to implement simplified logic circuits for the 7-segment encoder and decoder.

The 7-segment code the one used to drive an LED display for decimal digits, similar to the one shown here for the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9:

 

 

(Squinting helps read these.) For sake of uniformity, use the following variables s0, s1, É, s6 to represent the indicated segments.

 

 

The following rex rules give the translation from a seven-segment encoding to decimal representation.  This is to be used in testing your solution to problem 2. These are also in file /cs/cs60/a/10/a10.rex on turing.

 

                    /* s0 s1 s2 s3 s4 s5 s6 */

sevenSegmentToDecimal([1, 1, 1, 0, 1, 1, 1]) => 0;

sevenSegmentToDecimal([0, 0, 1, 0, 0, 1, 0]) => 1;

sevenSegmentToDecimal([1, 0, 1, 1, 1, 0, 1]) => 2;

sevenSegmentToDecimal([1, 0, 1, 1, 0, 1, 1]) => 3;

sevenSegmentToDecimal([0, 1, 1, 1, 0, 1, 0]) => 4;

sevenSegmentToDecimal([1, 1, 0, 1, 0, 1, 1]) => 5;

sevenSegmentToDecimal([1, 1, 0, 1, 1, 1, 1]) => 6;

sevenSegmentToDecimal([1, 0, 1, 0, 0, 1, 0]) => 7;

sevenSegmentToDecimal([1, 1, 1, 1, 1, 1, 1]) => 8;

sevenSegmentToDecimal([1, 1, 1, 1, 0, 1, 1]) => 9;

 

 

Problem 1:

 

The input to a display is often in the form of BCD (binary-coded decimal). In BCD, each digit of a decimal numeral is encoded separately. For example, 61 in BCD would be 0110 0001, whereas it would be 111101 in straight binary. The advantage of BCD is that it permits a more modular decoding.

 

Give a rex rule set for the function:

 

     DecimalDigitToBCD

 

which converts a single decimal digit to BCD. For example,

 

     DecimalDigitToBCD(5) ==> [0, 1, 0, 1]

 

Note: While this could be done using recursion, we would prefer the tabular form for sake of displaying all of the conversions.

 

 

Problem 2:

 

Construct a single simplified SOP (sum-of-products) rex function BCDtoSevenSegment that converts one-digit BCD to seven-segment code. Requirement: We want a single function, not seven different functions, that produces a list of bits, one for each segment s0, É, s6, in that order using only the logic functions ||, &&, and ! (i.e. ÒorÓ, ÒandÓ, and ÒnotÓ.) Each bit is derived from a single logic expression. ÒSimplifiedÓ in this case means that your solution must be a sum of maximal sub-cubes.

 

Note that the results of this problem and Problem 1 should have the property that

sevenSegmentToDecimal(BCDtoSevenSegment(DecimalDigitToBCD(i))) == i

 

for each i in the range 0 to 9.

 

To get full credit, you must take the ÒdonÕt careÓ combinations into account as well, as these give you the maximum possible simplifications.

 

Turn in your simplification work as a separate page of Karnaugh maps.

 

Do not implement your function as a sequential evaluation that tries each combination, since this would not be an SOP form.

 

In /cs/cs60/a/10/a10.rex on turing there is rex code for testing your solution. This will be one of your two submitted files.

 

Extra Credit Problem A:

 

Similar to the problem 1, construct a single rex equation for the function that converts a seven-segment code back to BCD. This should also use the SOP form.

 

Because this is a 7-variable problem, Karnaugh maps might be unwieldy. Instead, maybe make a table for converting from 7-segment to BCD, then ÒeyeballÓ the functions for each of the 4 BCD bits. Note that there are many donÕt care combinations present (118, to be exact).

 

The nature of this problem is more that of a puzzle than of applying a particular logic design methodology.

 

Problem 3:

 

Complete the definitions of Prolog predicates that respond to the following queries, made to the Prolog database in the following ensure_loaded directive.

 

:- ensure_loaded('/cs/cs60/a/10/movies.pl').

 

This is already incorporated in a skeleton file, /cs/cs60/a/10/a10.pl,

which you can use as the start of your file to be submitted. The database defines the following predicates:

 

movie([Title, Year], Director, [... categories])

 

actress(Name, [Birth City, Birth State], Birthyear)

 

actor(Name, [Birth City, Birth State], Birthyear)

 

plays(Player, Role, [Title, Year])

 

Your predicate names must be exactly those given below, or your solutions

will not be able to pass the tests that will be applied in grading.

 

Since the essence of the solutions is in your predicate definitions and

the answers to the queries, we will provide the answers in test cases. However, we may substitute a slightly different database in grading, so your definitions should be robust.

 

In defining your predicates, remove the _ from the variables.  These

are present for now that so the compiler doesn't complain about singleton

variables, which are often the sign of an error, such as a spelling error.

 

a.     directedBandits(Director) iff Director is the director of the movie ['Bandits', 2001]

 

b.     directedByBay(Movie) iff Movie is directed by 'Michael Bay'.

 

c.     actressAfter1970(Actress) iff Actress was born after 1970.

 

d.     player(Name, BirthPlace, Birthyear) iff either actor(Name, BirthPlace, Birthyear) or actress(Name, BirthPlace, Birthyear).

 

e.     bornInLondon(Player) iff Player was born in ['London', 'England'].

 

f.     playerAndDirector(Player) iff Player is a player that also directed some movie.

 

g.     playedAndDirected(Player) iff Player is a player that directed a movie in which he or she also played.

 

h.     playedMultiple(Player) iff Player played in more than one movie.

 

i.      playedInComedy(Player) iff Player played in a comedy.

 

j.     playedNotDirected(Director) iff Director directed some movies, but    played in at least one movie he/she did not direct.

 

Running Prolog on turing:

 

Copy the skeleton file /cs/cs60/a/10/a10.pl to your local directory, then type to Unix:

 

    prolog +l a10.pl

 

to the Unix prompt. The +l is  a letter ÒellÓ, not a digit ÒoneÓ. Ignore the message that appears about licensing. It has no effect.

 

Type your queries after the prompt ?-.

 

Note that you cannot directly enter new rules after this prompt, as you can in rex. It is best to edit your rules into the file and restart. If you must edit a rule in on-line, type

 

consult(user).

 

(the period is necessary), then enter the rules, then end with control-D.

 

You can also load, or insert into your file, /cs/cs60/a/10/test.pl, which tests each of the predicates for Problem 3. To test problem 5, for example, type

test(5).


To test all problems, type 

 

test.

 

 

Problem 4:

 

Four students attend four different colleges. Each student has a different hair color, is from a different home state, drinks a different drink, and plays in a different sport. Here are some clues as to who does what.

 

  1. The student with black hair plays football.

 

  1. The student from indiana drinks lemonade.

 

  1. The student from washington drinks milk.

 

  1. The cmc student is from newyork.

 

  1. The rugby player drinks tea.

 

  1. The student who plays track goes to hmc.

 

  1. The pomona student is blond.

 

  1. The scripps student is either from california or indiana.

 

  1. The student who drinks water is from the west coast.

 

  1. The student with brown hair does not play track.

  2. The hmc student is not from washington.

  3. The scripps student does not drink lemonade.

 

Construct a prolog predicate solve(Configuration) that determines possible complete configurations, that is which students attend which colleges, drink which drinks, play which sports, and are from which states. A Configuration will be a list of four lists, each list of the form:

         [College, Drink, HairColor, Sport, State]

 

Note: The objective is not to solve the problem, but to have Prolog solve the problem.

 

So that we are all in sync with the grading program, here are the exact spellings of each attribute to be used:

 

Colleges: cmc, hmc, pomona, scripps

 

Hair color: black, blond, brown, red

 

Drink: lemonade, milk, tea, water

 

Sport: football, rugby, track, waterpolo

 

State: california, indiana, newyork, washington