CS 60, Fall 2002

Assignment 09, Due Tue. 26 November

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 chapters 9 and 10 in the textbook. Problems 1 to 3 require rex solutions, while problems 4 and 5 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 decimal to seven-segment encoding and the inverse, which might be used in testing or in OCR (optical-character recognition) applications, perhaps. These are also in file /cs/cs60/a/09/a09.rex on turing.

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

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

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

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

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

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

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

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

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

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

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, 0]) => 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, as each digit is treated separately.

Similar to the above rule sets, 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:

Give a rex rule set for the inverse function

BCDtoDecimalDigit

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

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

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

Problem 3:

Construct a single simplified SOP (sum-of-products) rex equation for a function that converts one-digit BCD to seven-segment code. Requirement: The solution must be a single equation producing a list of bits, one for each segment s0, …, s6, using only the logic functions ||, &&, and ! (i.e. “or”, “and”, and “not”.) Each bit is derived from a single logic expression, as shown in the lecture slides. “Simplified” in this case means that your solution must be a sum of maximal sub-cubes.

To get full credit, you must take the “don’t care” combinations into account as well, as these give you the maximum possible simplifications.

In contrast to the previous problem, the solution will therefore not to be in the form of a set of rules, one for each input combination. Also, do not implement your function as a sequential evaluation that tries each combination, since this would not be an SOP form.

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

In /cs/cs60/a/09/a09.rex on turing there is rex code for testing your solution.

Extra Credit Problem A:

Similar to the problem 3, construct a single rex equation for the function that converts one-digit seven-segment code to BCD. This should also use the SOP form, as in problem 3.

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 4:

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/09/movies.pl').

This 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 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.

Problem 5:

Use Prolog to provide a solver for a generalized version of the game "Twenty-Four". In the original game, players view a card with four numbers on it and try to make an arithmetic combination of the numbers using the operators +, *, / so that the result is 24. Each number must be used exactly once. Each operator can be used any number of times.

In our generalization of the game, the fixed number 24 is replaced with a variable, the set of operators is specified in a list, and the list of numbers can have any length, not just 4. (By definition, no result can be made if the list is empty.)

Define a 4-ary predicate solve such that

solve(Ops, Values, Result, Tree)

will solve for a syntax-tree Tree using operators Ops on the set Values to give the value Result. For example, alluding to the original “24” game, a dialog with Prolog would be:

| ?- solve(['+', '*', '-'], [2, 3, 4, 5], 24, Tree).

Tree = [*,[+,[-,3,2],5],4]

Assume that the set of operators will always be a subset of ['+', '*', '-', '/'] and that '/' denotes integer division.

Below we provide some predicates that could be helpful in solving this

problem. Use recursion and back-tracking to do the work for you.

eval(Exp, Result) is true iff Result is the numeric value an expression tree Exp:

eval(R, R) :- number(R).

eval(['+', A, B], R) :- eval(A, AR), eval(B, BR),

R is AR + BR.

eval(['*', A, B], R) :- eval(A, AR), eval(B, BR),

R is ARBR.

eval(['-', A, B], R) :- eval(A, AR), eval(B, BR),

R is AR - BR.

eval(['/', A, B], R) :- eval(A, AR), eval(B, BR),

R is AR // BR.

split(X, Y, Z) is true iff X is splittable into non-empty lists Y and Z.

split(X, Y, Z) :- split1(X, Y, Z), Y \== [], Z \== [].

split1([], [], []).

split1([A | X], [A | L], R) :- split1(X, L, R).

split1([A | X], L, [A | R]) :- split1(X, L, R).

Running Prolog on turing:

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

prolog +l a09.pl

to the Unix prompt. Ignore the message 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.