Description
CSE 311 Homework 3
1. Do Not Iron While Wearing Shirt (18 points)
For each of the following English statements, (i) translate it into predicate logic, (ii) write the negation of that
statement in predicate logic with the negation symbols pushed as far in as possible, and then (iii) translate the
result of (ii) back to (natural) English.
Let the domain of discourse be people and activities. You should use only the predicates Loves(x, y)
and Likes(x, y) which say that person x loves or likes (respectively) activity y; the predicates Person(x) and
Activity(x), which say whether x is a person or activity, respectively; and the predicates x = y and x 6= y, which
say whether or not x and y are the same object. You can use constants to refer to specific people or activities
such as the “Bob” in the next example.
Example: “There is some activity, other than ironing, that Bob likes.’
i. ∃x ((Activity(x) ∧ (x 6= ironing)) ∧ Likes(Bob, x))
ii. ∀x ((Activity(x) ∧ (x 6= ironing)) → ¬ Likes(Bob, x))
(Make sure you see why! It’s important to notice domain restrictions when translating to English.)
iii. Bob does not like any activity other than ironing.
(Or less natural: Every activity other than ironing is not liked by Bob.)
(a) [9 Points] Every activity that Bob loves is also loved by someone else.
(b) [9 Points] Someone who likes every activity does not love any activity.
2. May Cause Drowsiness (26 points)
Write formal proofs of each of the following.
(a) [6 Points] Given p ∧ q, p → r, and r → (s ∧ w), it follows that q ∧ w.
(b) [10 Points] Given p → q, r → ¬p, and (¬r ∧ q) → s, it follows that p → s.
(c) [10 Points] Given ((p ∧ q) → (p ∧ r)) ∧ ((p ∧ r) → (p ∧ q)), it follows that p → ((q → r) ∧ (r → q)).
You can write your proofs by hand or in LATEX. Alternatively, feel free to use either of the following tools:
• This tool will allow you to check the correctness of most proofs in Propositional Logic. You can use it
for these problems by typing in the premise and conclusion and clicking “Start Proof”. (You can take a
screenshot of your completed proof and include it in your submission.)
• Cozy IDE now has a project template called “CSE 311 HW3” that is preloaded with these three problems.
(As in HW2, you can download your completed project as a zip file and submit it in canvas.)
(Both tools only allow one premise, but they can take the “∧” of those facts as the premise instead.)
1 CSE 311
3. Contents Under Pressure (20 points)
In this problem, we will consider the following, new inference rule:
Proof By Cases
A ∨ B A → C B → C
∴ C
This rule says that, if we know that either A or B is true and that both A implies C and B implies C, then it
follows that C is true. If it is A that is true, then we get that C is true by Modus Ponens and likewise if B is
true instead. This is a valid rule of inference and you are free to use it outside of this problem as well.
(a) [8 Points] Use the Proof By Cases rule to prove the following. Given p ∧ (q ∨ r), q → (r ∧ s), and
r → (r ∧ s), it follows that p ∧ (s ∨ t)
(b) [10 Points] Prove that the “Elim ∨” rule follows from “Proof By Cases”. Specifically, use the Proof by
Cases rule to prove that, given p ∨ q and ¬p, it follows that q is true. (You may not use Elim ∨.)
(c) [2 Points] What does (b) tell us about the relative power of “Elim ∨” versus “Proof By Cases” to infer
new facts from given ones?
4. Not Intended For Human Consumption (20 points)
Let Q(x) be a predicate defined in some, fixed domain of discourse.
(a) [8 Points] Prove that, given ¬(∀y Q(y)), it follows that ∃x (Q(x) → ∀y Q(y)).
(b) [8 Points] Prove that, given ∀y Q(y), it follows that ∃x (Q(x) → ∀y Q(y)).
Hint: It is okay to simply repeat a fact proved above, again, on another line below. Just cite the
original line where it appeared as the explanation.
(c) [4 Points] Why can we conclude from parts (a) and (b) that ∃x (Q(x) → ∀y Q(y)) is a tautology? Explain.
(A formal proof is not necessary but is also allowed.)
5. Keep Away From Small Children (16 points)
Recall that an integer n is a square iff there exists a k ∈ Z such that n = k
2
. Formally, with our domain of
discourse as the integers, we can define Square(n) := ∃k (n = k
2
).
(a) [2 Points] Write the following claim in Predicate Logic: if integers n and m are squares, then nm is a
square. (Be careful!)
(b) [10 Points] Give a formal proof of the claim from part (a). In addition to the inference rules discussed in
class, you can also rewrite an algebraic expression to equivalent ones using the rule “Algebra”. (E.g., you
could write “a(b + 1) − a = ab” with Algebra as the rule / explanation.)
(c) [4 Points] Translate your formal proof from part (b) into an English proof.
2
6. Extra Credit: Some Assembly Required (0 points)
In this problem, we will extend the machinery we used in HW1’s extra credit problem in two ways. First, we will
add some new instructions. Second, and more importantly, we will add type information to each instruction.
Rather than having a machine with single bit registers, we will imagine that each register can store more
complex values such as
Primitives These include values of types int, float, boolean, char, and String.
Pairs of values The type of a pair is denoted by writing “×” between the types of the two parts. For example,
the pair (1,true) has type “int × boolean” since the first part is an int and the second part is a boolean.
Functions The type of a function is denoted by writing a “→” between the input and output types. For
example, a function that takes an int as argument and returns a String is written “int → String”.
We add type information, describing what is stored in each each register, in an additional column next to the
instructions. For example, if R1 contains a value of type int and R2 contains a value of type int → (String×int),
i.e., a function that takes an int as input and returns a pair containing a String and an int, then we could write
the instruction
R3 := CALL(R1, R2) String × int
which calls the function stored in R2, passing in the value from R1 as input, and stores the result in R3, and
write a type of “String × int” in the right column since that is the type that is now stored in R3.
In addition to CALL, we add new instructions for working with pairs. If R1 stores a pair of type String ×int,
then LEFT(R1) returns the String part and RIGHT(R1) returns the int part. If R2 contains a char and R3
contains a boolean, then PAIR(R2, R3) returns a pair of containing a char and a boolean, i.e., a value of type
char × boolean.
(a) Complete the following set of instructions so that they compute, in the final register assigned, a value of
type float × boolean:
R1 int × float
R2 int → String
R3 String → (char × boolean)
R4 := . . . . . .
The first three lines show the types already stored in registers R1, R2, and R3 at the start, before your
instructions are executed. You are free to use the values in those registers in later instructions.
Since we have unlimited space, store into a new register on each line. Do not reassign any registers.
(b) Compare the types listed next to these instructions to the propositions listed on the lines of your proof
in problem 2 (a). Give a collection of text substitutions, such as replacing all instances of “p” by “int”
(these can include both atomic propositions and operators), that will make the sequence of propositions
in problem 2 (a) exactly match the sequence of types in problem 6 (a). You may need to change your
solution to problem 6 (a) slightly to make this work.
(c) Now, let’s add another way to form new types. If A and B are types, then A + B will be the type
representing values that can be of either type A or type B. For example, String + int would be a type of
values that can be strings or integers.
To work with this new type, we need some new instructions. First, if R1 has type A, then the
instruction CASE(R1) returns the same value but now having type A + B. (Note that we can pick any
type B that we want here.) Second, if R2 stores a value of type A + B, R3 stores a function of type
A → C (a function taking an A as input and returning a value of type C), and R4 stores a function of
type B → C, then the instruction SWITCH(R2, R3, R4) returns a value of type C: it looks at the value in
3
R2, and, if it is of type A, it calls the function in R3 and returns the result, whereas, if it is of type B, it
calls the function in R4 and returns the result. In either case, the result is something of type C.
Complete the following set of instructions so that they compute, in the final register assigned, a value
of type int × (char + boolean):
R1 int × (float + String)
R2 float → (String × char)
R3 String → (String × char)
R4 := . . . . . .
The first three lines again show the types of values already stored in registers R1, R2, and R3. As before,
do not reassign any registers. Use a new register for each instruction’s result.
(d) Compare the types listed next to these instructions to the propositions listed on the lines of your proof
in problem 3 (a). Give a collection of text substitutions, such as replacing all instances of “p” by “int”
(these can include both atomic propositions and operators), that will make the sequence of propositions
in problem 3 (a) exactly match the sequence of types in problem 6 (c). You may need to change your
solution to problem 6 (c) slightly to make this work.
(e) Now that we see how to match up the propositions in our earlier proofs with types in the code above,
let’s look at the other two columns. Describe how to translate each of the rules of inference used in the
proofs from both problem 2 (a) and 3(a) so that they turn into the instructions in problem 6 (a) and (c).
(f) One of the important rules not used in problems 2 (a) or 3 (a) was Direct Proof. What new concept
would we need to introduce to our assembly language so that the similarities noted above apply could
also to proofs that use Direct Proof?
