Quiz 1 for the course

CS CS 5303, Spring 2012

Name ___________________________________________________

Books and notes allowed.

1. Prove that the sets {∨, ¬} and {→, ¬} are sufficient, i.e., that all other propositional connectives can be described in terms of these connectives.

2. Use natural deduction to prove that p → q |− ¬p ∨ q.

3. Use resolution to prove that ¬p |− p → q.

4. Use program synthesis to solve the Archimedes problem re
whether the crown was made of gold or of silver. We know that
m_{1} = ρ_{1} * V_{1}, that
m_{2} = ρ_{2} * V_{2}, and that
based on the values ρ_{1} and ρ_{2}, we
can tell whether the crown was made of gold or of silver:

- if ρ
_{1}= ρ_{2}, this means that the crown was made of gold, and - if ρ
_{1}≠ ρ_{2}, this means that the crown was made of silver.

5. (For extra credit) Prove that there exists an irrational
number x for which the power x^{√5} is
rational.