CSC/MAT 208 (Spring 2024)

Demonstration Exercise 2

Problem 1: Boolean Blasters

Consider the following top-level Racket definitions over booleans that give implementations of the standard boolean operations not, and, and or:

(define my-not
  (lambda (b)
    (if b #f #t)))

(define my-and
  (lambda (b1 b2)
    (if b1 b2 #f)))

(define my-or
  (lambda (b1 b2)
    (if b1 #t b2)))

Prove the following claims of program equivalence about these definitions:

Claim 1: (my-not (my-and #t #f)) ≡ #t.

Claim 2: There exists a boolean b1 such that for all booleans b2, (my-or b1 b2) ≡ #t.

Claim 3 (Negation is an Involution): For any boolean b, (my-not (my-not b)) ≡ b.

Claim 4 (De Morgan’s Law): For any pair of booleans b1 and b2, (my-not (my-and b1 b2)) ≡ (my-or (not b1) (not b2)).

For any derivations that you write, you may evaluate a function call directly to the branch of the selected conditional in its body.

Problem 2: Zero Is The Hero

  1. Implement a Racket function dropzeroes that takes a list l of numbers as input and returns l but with all 0s. For example (dropzeroes '(1 3 0 1 0 2)) --> '(1 3 1 2). Make sure to test your code in Dr. Racket and add your code to this write-up using a code block.

  2. Prove the following property of dropzeroes:

    Claim (Idempotency of dropzeroes): (dropzeroes (dropzeroes l)) ≡ (dropzeroes l).

    You may take the shortcut of evaluating a recursive function call directly to the branch that it selects in a single step.

    (Hint: be precise with your program derivations and every step you make! In particular, make sure that every step is justified and you consider all possibilities of evaluation.)

Problem 3: Powerful Induction

Consider the following Racket definition:

(define pow
  (lambda (x y)
    (if (zero? y)
        1
        (* x (pow x (- y 1))))))

Prove the following claim using mathematical induction. You may take the shortcut of evaluating a recursive function call directly to the branch that it selects in a single step.

For all natural numbers x, y, and z, (* (pow x y) (pow x z)) = (pow x (+ y z)).

In your proof, you can assume that the following fact about pow holds:

Fact: for all natural numbers x and y, (* x (pow x y)) = (pow x (+ y 1)).

In your proof, make sure to be explicit where you invoke any assumptions, e.g., the induction hypothesis or this lemma.