Problem Set 1

**Deliverable:**Submit your responses as a single PDF file on the collab site before

**6:29pm**on

**Friday, 1 September**. The PDF you submit can be a scanned handwritten file (please check the scan is readable), or a typeset PDF file (e.g., generated by LaTeX). Please make sure the PDF you submit is redable (see advice on course site).

### Collaboration Policy - Read Carefully

Remember to follow the course pledge you read and signed at
the beginning of the semester. For this assignment, you may discuss
the problems and work on solutions with anyone you want (including
other students in this class), but you must write your own solutions
and understand and be able to explain all work you submit on your
own. To confirm your own understanding, after discussing the problems
with others, you should attempt to write your solutions on your own
without consulting any notes from group work sessions. If you get
stuck, you may visit notes from the group work sessions, but should
make sure you understand things well enough to produce it on your own.
You may also use any external resources you want, with the exception
of solutions and comments from last year’s offering of this
course. Since the staff and students benefit from being able to both
reuse problems from previous years, and from being able to provide
detailed solutions to students, it is important that students do not
abuse these materials even if it is easy to find them. **Using
solutions from last year’s course would be detrimental to your
learning in this course, and is considered an honor violation.**

If you use resources other than the class materials, lectures and course staff, you should document this and mention it clearly on your submission. For everyone other than the course staff you work with, you should credit them clearly on your assignment, and should find out something interesting about their family history (you shouldn’t include this in your submission, though, especially if they share something private with you).

You are **strongly encouraged** to start early and take advantage of
the scheduled office hours for this course.

## Preparation

This problem set focuses on Chapter 1 of the MCS book, and Class 1 and Class 2.

## Directions

Solve all the problems on the next page. For full credit, your answers should be correct, clear, well-written, and convincing.

## Proofs and Certification

The introduction for the MCS book states,

“Proofs also play a growing role in computer science; they are used to certify that software and hardware will

alwaysbehave correctly, something that no amount of testing can do.”

The statement suggests “no amount of testing can certify software will always behave correctly”. Is this claim valid or invalid? Support your answer with a short justification.

The statement suggests “proofs can certify that software will always behave correctly”. Argue that this is not a correct statement.

## Inference Rules

For each candidate rule below, state whether or not the rule is sound.
Support your answer with a convincing proof. The variables $P$, $Q$,
and $R$ are Boolean propositions (either **true** or **false**).

$\infer{R}{P \implies Q, Q \implies R}$

$\infer{P}{(NOT(NOT(P)))}$

$\infer{Q \implies P}{P \implies Q}$

$\infer{NOT(Q) \implies P}{P}$

$\infer{Q \implies NOT(P)}{P \implies NOT(P)}$

## Proofs

The proof that $\sqrt{2}$ is irrational (Theorem 1.8.1) in the book includes relies on this implication: $d^2$ is a multiple of two implies $d$ is a multiple of 2. Prove that this is a valid implication to a skeptical reader.

Problem 1.4 (parts a, b, and c) from the MCS book.

Prove that for any non-negative real numbers, $x$ and $y$, if $xy = n$ then the minimum of $x$ and $y$ is not greater than $\sqrt{n}$. (Hint: prove by contradiction.)