Term Project A
Due: February 26th at noon on Blackboard.
Creativity in presentation will be rewarded with bonus points.
Task 1. Find the definition of a Sheffer Stroke (denoted by j). Give a few sentences description about its history
such as who invented it, when, with what motivation. Next up, complete the following.
a) Prove that ∼p ≡ pjp.
b) Prove that p ^ q ≡ (pjq)j(pjq).
c) Build p _ q from the Sheffer Stroke (ie define _ using Sheffer Stroke only just like part b does so for ^ ).
d) Build p =) q from the Sheffer Stroke.
e) Conclude that Sheffer Stroke is an operation that all other logical operations can be built from it.
f) Suggest two reasons why we don’t use Sheffer Stroke exclusively, but rather define several bnary operations.
Task 2. You are a knight, but as opposed to physical trials, your strength will be determined by a sequence of logic
puzzles. For each puzzle, you are faced with two rooms, behind each door is a dragon (oof, that’s bad) or a donut
(delicious and good!). You must determine what is behind each one door according to puzzle rules and to the signs
on the rooms.
Your knowledge of implications and contradictions will come in handy. Solve each puzzle and clearly explain your
solution. You do not need to introduce formal logic with propositions, plain english arguments will do. Hint: you’d
likely start with If the sign on door x is true, then…” or If the dragon is behind door x, then…” or something
similar.
In the end, you must clearly state what is behind each door.
Puzzle A. The rules are:
• There may be two donuts, two dragons, or one of each.
• One sign is true and the other is false.
The doors are:
Puzzle B. The rules are:
• Again, there may be two donuts, two dragons, or one of each.
• Both signs are true or both are false.
The doors are:
1
Puzzle D. The rules are:
• Again, there may be two donuts, two dragons, or one of each.
• If there is a donut in the lower-numbered room, the sign is true. Otherwise, it is false.
• If there is a donut in the higher-numbered room, the sign is false. Otherwise, it is true.
The doors are:
Puzzle H. The rules are:
• One room contains a donut, and the other two contain dragons.
• At most one of the three signs is true.
The doors are:
Puzzle J. The rules are:
• Again, one room contains a donut, and the other two contain dragons.
• The sign on the room with the donut in it is true, and at least one of the other signs is false.
The doors are:
2