[FrontPage] [TitleIndex] [WordIndex] 

Contents

  1. Propositional Logic
  2. Karnaugh Maps
  3. Predicate Logic
  4. Unification
  5. Prolog

Propositional Logic

Hamburger/Richards Problem 2.9:

Prove that the following logical statement

is a tautology -- i.e., is always true. Carry out this proof in two distinct ways:

  1. By a truth table
  2. By substitution (i.e., using rules), starting with distributivity.

Karnaugh Maps

This question explores Karnaugh maps, an alternate representation for propositional formulae used in (old-fashioned) hardware design. It is supposed to be self-contained, but may not be enough for those with no prior exposure. Additional information may be found on the wikipedia page on Karnaugh maps, in the Computer Architecture textbook, or at any number of other web resources. If you use these resources, you must of course credit them in your solution.

Now the fun starts....

  1. Draw the Karnaugh maps for the following functions:
    1. Parity, i.e., the function (on four inputs) that is true if the number of true inputs (propositions) is even
    2. (q0 v q1) ^ (q2 v q3)

    3. q0 -> ((q1 ^ q2) v q3)

  2. Populate a four-variable Karnaugh map with the formula made true by the truth assignment corresponding to that square. For example, if q0 is false, q1 is true, q2 is true, and q3 is false, the truth assignment might be written as as not(q0), q1, q2, not(q3) (but that renders extremely poorly on the wiki; you can use the overbar notation that makes it prettier!).
  3. There is an important observation to be made about the formulae in adjacent squares. What simple property can be stated about every pair of adjacent squares (two squares sharing a top, bottom, or side) in a Karnaugh map?
  4. (Hopefully) observe that this property holds for some non-adjacent squares as well. However, these squares can be made adjacent by wrapping the right edge of the Karnaugh map around to meet its left edge and, simultaneously, wrapping the top to meet the bottom. Explain.

  5. One can use a Karnaugh map to read off formulae for boolean operations in disjunctive normal form. For example, OR can be expressed as not(q0)q1 v q0 not(q1) v q0 q1 simply by reading the formulae corresponding to the squares with 1s. Using this simple-minded method, how many booleans would appear in the formula corresponding to a k variable Karnaugh map with n 1s? (Hint: for the 2-variable function OR, with 3 1s, the answer is 6.)

  6. Fortunately, the formula for OR can be simplified by combining terms. (Shockingly enough, it reduces to q0 v q1) In a traditional Karnaugh map -- such as AND, OR, or XOR, above, but including the larger variants -- suppose that a 2m x 2n rectangular region contains exclusively 1s. (For example, in the Karnaugh map for OR, the second column is a 2x1 region of 1s and the second row is a 1x2 region of 1s.) What does this tell you about the formula corresponding to this Karnaugh map? In particular, if you have a k-variable Karnaugh map with an m x n rectangular region of 1s, how many variables would that region require to represent in disjunctive normal form under the naive method of the previous question? How many does it in fact require?

Predicate Logic

Write the following statements in the first order predicate calculus. Each of your answers should take the form of a predicate calculus sentence with no unbound variables, i.e., a rule that defines the predicate in question.

  1. A horse is a mammal.
  2. Mammals have four legs and no arms, or two arms and two legs.
  3. A mother is a female parent. (Hint: A mother must be someone's mother....)

Extra credit: extend this last definition to prove the punchline/chorus of the following set of statements: http://www.wwco.com/gean/grandpa/ (you should definitely visit the .wav file!). You may also read an exerpted description in the Luger (predicate logic) handout -- problem 12 from page 78.

Unification

Luger problem 6. Attempt to unify the following pairs of expressions. Either show their most general unifiers (see Luger for definition) or explain why they will not unify. You may assume that lower case letters are predicates or constants and upper case letters are variables.

  1. p(X,Y) and p(a,Z)
  2. p(X,X) and p(a,b)
  3. ancestor(X,Y) and ancestor(bill,father(bill))
  4. ancestor(X,father(X)) and ancestor(david,george)
  5. q(X) and -q(a), where - is negation

Prolog

If you're having trouble with Prolog: try a web tutorial like this one or the textbook from Union College

  1. Louden 12.26 (with gprolog spelling): Explain the difference in Prolog between the following two definitions of the sibling relationship: 
    •        sibling1(X,Y) :- X\=Y, parent(Z,X), parent(Z,Y).
       sibling2(X,Y) :- parent(Z,X), parent(Z,Y), X\=Y.

    where X\=Y means X doesn't unify with Y.

  2. Bring up gprolog (or some other standard Prolog system of your choosing); see ReadingRoom/Prolog.

    Type (or cut and paste) in the mini-adventure game from our adaptation of Fun with Prolog; code at adv1.pl. (Note that this is a minor adaptation of Fun with Prolog with some modifications for our particular prolog interpreter). You will probably want to put this code in a file and consult it into prolog. The filename should end in .pl -- e.g., fox.pl -- and can be consulted into prolog using [] and . but not the .pl extension: 

    • [fox].

    Alternatively, you can type straight into gprolog, but remember that this requires consulting user -- [user]. -- and ends with a control-D. The adventure game explanation tells you that Prolog will respond to the following queries in this way: 

    •         ?- location(fox, X).
        X = woods
        ?- connect(yard, X).
        X = house
        X = woods

    Verify this, then explain why Prolog gives one answer to the first query and two to the second. (To see this in action, you may have to hit a after gprolog gives you the first answer to connect(yard,X). This is because gprolog doesn't automatically assume that you want all answers....)

  3. Run the adventure game program by typing go. at the prolog query interface. You can try various commands, as shown in the description of the adventure game. If you cause an error, type a (abort) at the prompt to get back to the prolog query interface. You can also end the game cleanly (without winning) by typing done. at the game prompt, >>>.

    You should see that the program's behavior is somewhat different from the transcript at the top of the page. In particular, you can't get anywhere. This is because one precondition for changing your location isn't met: your location needs to be connected to where you're going. Remedy this problem by editing your code and reconsulting it in. Verify that you can move from the house to the duck_pen and back.

    Note: If you want to be able to assertz and retract statements, the predicate in question must be dynamic. This is why we told you to add :- dynamic( location/2 ). to your file; it tells Prolog that the 2-argument predicate location may change over the course of its execution. You may make other predicates dynamic in the same way.

  4. Now you can get to the duck_pen, but you still can't win. In order to win, you need to make it possible to satisfy you_have(egg). Add rules to make it possible to obtain the egg, but only if you are in the duck_pen. Verify the behavior of these additions and demonstrate that it is now possible to win the game.

  5. Extra Credit: There are several other additions required to get the code to behave as indicated in the transcript at the beginning of the game description. Extend the game with at least one of these features, or add a different feature (and at least one new rule) of your own choosing.

    1. Add the gate, making it necessary to open the gate in order to get into the duck_pen.

    2. Add code to allow the ducks to get out of the duck_pen (when the gate is open, if you have created a gate).

    3. Be creative....I'm sure that you can find something cool to add!
    Feel free to modify existing code to make this work.

    When you are done with this question, you should turn in a file containing your complete prolog code (including any necessary parts of the original adventure game from "Fun with Prolog") electronically. (This is so I can run it and see how cool it is!) In addition, if you did the extra credit, please turn in a brief English explanation of what feature you added to the game and a reasonably well documented version of your new rules (i.e., how you think they work).

2013-07-17 10:42