CSC 341 (Fall 2021)

Lab: Formal Proof

In this lab, we’ll work on authoring proofs. Try to be as rigorous, yet concise in your proofs as possible. If you have any questions about levels of formality or formatting, please don’t hesitate to ask!

Problem 1: Formal Proof

Formally prove the following claims over strings.

Claim 1: Call an element \(u\) of a set \(S\) and an associated binary operation over that set \((+) : S → S\) a unit if \(\forall x \in S \ldotp x + u = u + x = x\). We claim that \(ϵ\) is a unit for strings and concatenation over strings.

Claim 2: Let \(x\) and \(y\) be strings. If \(x\) is a prefix of \(y\) and \(y\) is a prefix of \(x\) then \(x = y\).

(Hint: make this an algebraic argument based on the definition of prefix from the book!)

Problem 2: Induction Revisited

Consider the following definitions regarding binary trees.

Definition (Binary Tree): a binary tree is either:

  • A leaf or
  • A node with two sub-trees, its children.

We define the root of a binary tree to be a node that is not the child of any other node in the tree.

Definition (Level and Height): the level of a node in a binary tree is the length of the path from the root to that node. The height of a binary tree is the maximal level of any node in the tree. We also use “level” to denote the set of all nodes that share the same level in the tree.

Definition (Complete and Perfect Trees): a tree is complete if each of its levels contain its maximal number of possible nodes. A tree is perfect if each node of the tree contains zero or two children.

Now prove the following claim by structural induction.

Let \(h\) be the height of a complete, perfect binary tree. If \(n \leq h\), then there are \(2^n\) nodes at level \(n\) of this tree.

Problem 3: Constructive Proof (Optional)

Chess is played on a \(n \times n\) board (usually \(n = 8\)). Consider the rook piece, which can move in any number of squares in a cardinal (non-diagonal) direction. A rook’s tour is a sequence of moves for a single rook that causes the piece to visit every square of the board exactly once. When considering a tour, we are free to place our piece on the board at any position initially. Also, we only consider a square visited if the piece ends its movement on that square.

Prove via induction that there exists a rook’s tour for any chessboard of size \(n ≥ 1\).

(Hint 1: note that proving the existence of a rook’s tour means constructing a rook’s tour for an arbitrary board, i.e., designing an algorithm that generates the tour!)

(Hint 2: pay attention to the details! This is not as straightforward of a proof as you might think!)