Hw10-w-cover - Homework 10 Discrete Mathematics Profesor : Andrew Lee PDF

Preview

Summary

Homework 10
Discrete Mathematics
Profesor : Andrew Lee...

Description

CIS 375 Introduction to Discrete Mathematics Homework 10 Reading: Read Scheinerman’s text, section 22 and out class handouts on strong induction and structural induction. Study the examples given in lectures and those in the text carefully before attempting this assignment. Due Date: This homework is officially due in class on Thursday, Nov 30, 2017. However, it comes with an automatic extension: anything submitted by noon on Friday, December 1 will be accepted as being on time. You can submit it in class or to the “CIS 375” bin outside of CST 4-226. You are required to fill out a disclosure cover sheet completely and staple your submission. Submission that fails to meet this requirement will not be graded.

Exercises In the following exercises, the term “mathematical induction” is being used in a broad sense. It can refer to any forms of mathematical induction we have studied in class, which includes (but not limited to) strong induction, structural induction etc.. 1. (20 point) Prove, by mathematical induction, that any integer postage greater than 7 cents can be formed by using only 3-cent and 5-cent stamps. For example, an integer postage of 11 cents can be formed by using two 3-cent and one 5-cent stamps. 2. (20 point) Prove, by mathematical induction, that for all odd n, m ∈ N, an n × m chessboard with the corner squares colored white has one more white square than black square. 3. Let M be a set of binary strings which is defined as follows: (a) (Basis) 010 ∈ M (b) (Inductive step) If s ∈ M, then 01s, s10, 0s1 ∈ M . (c) (Implicit exclusion rule) Nothing else is in M. • (5 point) List all the strings s in M with | s | ≤ 7. • Prove, by mathematical induction, that, for any s ∈ M , number of 0′ s in s = 1 + number of 1′ s in s.

cis 375

introduction to discrete mathematics

homework 10

2

4. (20 point) Let m be a positive integer and W F F m be the set of all well formed formulas as defined below: Definition (W F F m ) Let m be a positive integer. (a) (Basis)

pi ∈ WF F m for i = 1, · · · , m.

If φ, ψ ∈ WF F m , then (¬φ)∈ WF F m ( φ ∨ ψ)∈ WF F m ( φ ∧ ψ)∈ WF F m ( φ → ψ)∈ WF F m

(b) (Inductive step)

¬: ∨: ∧ →:

(c) (Implicit exclusion rule)

Nothing else is in W F F m .

Let T be the function T : W F F m → W F F m defined recursively as follows:   pi      (   ¬ T ( ψ)) T ( φ) = ( T ( φ1 ) ∨ T ( φ2 ))     ( T ( φ1 ) ∧ T ( φ2 ))     (¬ T ( φ1 ) ∨ T ( φ2 ))

if φ = pi for some i (1 ≤ i ≤ m). if φ = (¬ψ) for some ψ ∈ W F F m . if φ = (φ1 ∨ φ2 ) for some φ1 , φ2 ∈ WF F m . if φ = (φ1 ∧ φ2 ) for some φ1 , φ2 ∈ WF F m . if φ = (φ1 → φ2 ) for some φ1 , φ2 ∈ WF F m .

Prove, by mathematical induction, that T (φ ) is logically equivalent to φ and T (φ ) does not use the symbol → for any φ ∈ W F F m . 5. (20 point) Consider the set of full binary trees F BT as defined below: Definition (F BT ) (a) (Basis)

The tree with a singleton node is a full binary tree.

(b) (Inductive step) If Tl and Tr are full binary trees, then the tree T that are obtained from creating a new root node, with Tl as its left subtree and Tr as its right subtree, is also a full binary tree and we will denote T by Tl ⊲⊳ Tr . (c) (Implicit exclusion rule)

Nothing else is in F BT .

Prove, by using mathematical induction, that nodes( T ) ≥ 2 · height ( T ) + 1 for any T ∈ F RT .

Andrew C. Lee, EECS Dept, Syracuse University

Name:

Assignment #

Section (please circle):

M001 (TuTh 2-3:20pm)

M004 (TuTh 11am-12:20pm)

Yes

No

Did you consult with anyone (excluding the course instructor or tas/graders) on parts of this assignment?

Yes

No

Did you consult an outside source (such as an Internet site or a book other than the course textbook) on parts of this assignment?

If you answered Yes to one or more questions, please give the details of these consultations (who/what/where/etc.):

I assert that, to the best of my knowledge, the information on this sheet is true.

Signature:

Date: In the spirit of this cover sheet: Some of the wording on this cover sheet was developed in consultation with Prof. Royer....