Logic Study Problems

Problem 1

Consider the following claim:

Claim: For every dinosaur D, if D eats meat, then D has sharp teeth and D is not huge.

State the negation and the contrapositive of the claim. Your answer should be in words, with all negations (e.g. "not") on individual predicates.

Write out your solution, actually write it out on paper, before consulting the annotated solution

Problem 2

(a) For which values of p, q, and r is the following logical expression true? $$ (\neg p \vee q) \wedge (q \rightarrow r) \wedge (\neg r \vee p)$$

Give a succinct description of which combinations of input values work, rather than the whole truth table.

(b) Show that the following two expressions aren't logically equivalent: $$(p \rightarrow q) \wedge r$$ $$p \rightarrow (q \wedge r)$$

Write out your solution, actually write it out on paper, before consulting the annotated solution

Problem 3

Recall that "\(\exists ! x \in A,\ P(x)\)" means that there is exactly one value x in the set A that makes P(x) true.

(a) Express "\(\exists ! x \in A,\ P(x)\)" using the other standard logical operations. You can use any combination of shorthand symbols (e.g. \(\wedge\)) and words (e.g. "and"). Concentrate on capturing the meaning correctly.

hints

solution

(b) State the negation of your answer to (a), moving all instances of "not" onto individual predicates.

solution

Problem 4

Suppose we know that penguins are a type of animal and we are given the following facts:

1. All chestnut-eating animals are fun-loving
2. No penguin eats mulberries
3. Some well-dressed animals are uncomfortable
4. At least one penguin is uncomfortable
5. All animals eat mulberries or chestnuts
6. No uncomfortable animal eats mulberries

(a) Create shorthand notation for each predicate (e.g. a shorthand for "x eats chestnuts" and convert each statement into logical shorthand. You may assume that "not comfortable" is the same as "uncomfortable". Using shorthand will make parts (b) and (c) easier to do.

Write out your solution, actually write it out on paper, before consulting the solution.

(b) Use logical equivalences to convert these statements into implications where possible. By "implication", we mean a formula that looks like \(\forall x, P(x) \Rightarrow Q(x)\). Hint: you can do this for four of the six facts. The other two facts end up as existential statements.

solution.

(c) Write out the contrapositive of each implication, so that you have eight implications. Draw a graph picture showing which facts (positive or negative) imply which other facts. It should contain an arrow for each of the eight implications.

solution.

(d) Which of the following statements can be proved from the facts above?

1. Every comfortable penguin eats mulberries
2. At least one penguin is well-dressed
3. No penguins are fun-loving
4. There is at least one fun-loving well-dressed animal
5. All penguins are fun-loving
6. All penguins are uncomfortable

For each true statement, sketch a proof using your graph of implications and the two existential facts. For each false statement, try to construct a concrete counterexample, i.e. set of animals with their key properties which fits all of the given facts but not the false statement.

solution.