Propositional Logic

1. Universality of NAND: Prove by construction that the NAND operation is universal for propositional logic. Specifically, show how to construct the three (boolean/propositional) operations NOT, OR, and AND out of NAND. You may show your construction using gates or truth tables or logical formulae, but you will need to use either logical formulae transformations or truth tables to demonstrate the correctness of your constructions.

   Remember: A NAND B is true exactly when NOT (A AND is true.

2. Build XOR using NAND.
3. Extra Credit/Challenge: Is NOR universal? NOR is NOT (A OR B). How about XOR (exclusive or)? Why or why not in each case?

Predicate Logic

1. Assume that you have logical predicates IsParentOf(X, Y), which is true of X and Y whenever X is Y's parent, and IsFemale(X), which is true iff X is female. Give predicate calculus statements that define IsMotherOf, IsFatherOf, IsChildOf, IsSonOf, IsDaughterOf, IsMale in terms of IsParentOf and IsFemale (as well as any other predicates you define). Think carefully about which statements should be -> and which should be <->

   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. (The definitions of IsParentOf and IsFemale, above, are not predicate calculus sentences; they are English descriptions of the intended denotation (meaning) of these predicates.)

2. Using the additional predicate AreMarried(X,Y), write rules that enforce the symmetry of marriage and the constraints that the spouse of your parent is also your parent and the child of your spouse is also your child. (NB: This is eliding the definition of step-parent/step-child. If you wish to preserve this distinction, I don't object, but it may complicate your life in subsequent exercises.)

3. Add rules for grandparent/grandchild derived from the above rules. Provide at least the grandfather gendered version; you may include or omit the others as you wish.

4. At this point, for inspiration, you may wish to visit http://www.transload.net/~terrisfunnypages/songs/grandp.html (preferably with audio turned on) or http://www.wwco.com/gean/grandpa/ (you'll have to explicitly visit the .wav file, but the animation is pretty good). You are in effect going to solve problem 12 from page 78 of Luger (the Logic handout). Here's the setup: Assume the following:

   1. AreMarried( I, W )

   2. IsMotherOf( W, D )

   3. IsFatherOf( F, I )

   4. AreMarried( F, D )

   5. IsSonOf( S₁, W )

   6. IsSonOf( S₂, D )

   7. IsMale( I )

   (I, W, D, F, etc., are all individuals, not variables. You may rename them if you'd like; these are Luger's names.)

Prove that IsGrandfatherOf( I, I ). Each line of your proof should be numbered and should contain either a lettered assumption from above, a rule from your constraints/definitions, or a new statement. If it is a new statement, it should indicate what (two) other statements you combined to produce the new statement. For example, if you use modus ponens on A and A->B to deduce B, you should list B as the new statement and give the line numbers for the statements A and A->B (which should have been previously introduced).

Prolog

If you're having trouble with Prolog: try a web tutorial like this one

1. 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 Fun with Prolog. (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....)

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

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

4. 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, with your paper copy, 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).

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