Logic and Codes

Problem 46

intermediate

Truth tables for logical expressions.

Notation: The expression f/n means that function f has arity n. For example, sum/2 means that sum has 2 arguments.

Define functions and/2, or/2, nand/2, nor/2, xor/2, impl/2 and equ/2 (for logical equivalence) which succeed or false according to the result of their respective operations; e.g. and(A,B) is true, if and only if both A and B are true succeed.

Note that A and B can be expressions (not only the constants true and false). A logical expression in two variables can then be written in prefix notation, as in the following example: and(or(A,B),nand(A,B)).

Now, write a function table/3 which returns the truth table of a given logical expression in two variables.

Example

table(and(A,or(A,B))) == [
    [ true,   true,    true],
    [ true,   false,   true],
    [ false,  true,    false],
    [ false,  false,   false]
]

Problem 47

easy

Truth tables for logical expressions (2).

Continue problem P46 by defining and/2, or/2, etc as being operators.

This allows to write the logical expression in the more natural way, as in the example: A and (A or not B). Define operator precedence as usual; i.e. as in Java.

Example

table(A,B, A and (A or not B)) == [
    [ true,   true,    true],
    [ true,   false,   true],
    [ false,  true,    false],
    [ false,  false,   false]
]

Problem 48

intermediate

Truth tables for logical expressions (3).

Generalize problem P47 in such a way that the logical expression may contain any number of logical variables.

Define table/2 in a way that table(List,Expr) prints the truth table for the expression Expr, which contains the logical variables enumerated in List.

Example

table([A,B,C], A and (B or C) equ A and B or A and C) ===
    [
        [ true,     true,   true,   true],
        [ true,     true,   false,  true],
        [ true,     false,  true,   true],
        [ true,     false,  false,  true],
        [ false,    true,   true,   true],
        [ false,    true,   false,  true],
        [ false,    false,  true,   true],
        [ false,    false,  false,  true]
    ]

Problem 49

intermediate

Gray code.

An -bit Gray code is a sequence of -bit strings constructed according to certain rules. For example,

C(1) = ['0', '1']
C(2) = ['00', '01', '11', '10']
C(3) = ['000', '001', '011', '010', '110', '111', '101', '100']

Find out the construction rules and write a function with the following specification:

gray(N) ==  N-bit Gray code.

Can you apply the method of "result caching" in order to make the function more efficient, when it is to be used repeatedly?

Problem 50

hard

Huffman code.

First of all, consult a good book on discrete mathematics or algorithms for a detailed description of Huffman codes. We suppose a set of symbols with their frequencies, given as a list of fr(S,F) terms.

Example:

[fr(a,45),fr(b,13),fr(c,12),fr(d,16),fr(e,9),fr(f,5)].

Our objective is to construct a list hc(S) = C terms, where C is the Huffman code word for the symbol S.

In our example, the result could be

[hc(a,'0'), hc(b,'101'), hc(c,'100'), hc(d,'111'), hc(e,'1101'), hc(f,'1100')] 

[hc(a,'01'), ... ]

The task shall be performed by the function huffman/2 defined as follows:

huffman(F) == Hs is the Huffman code table for the frequency table F.