Discrete Structures

**To the Bottom of the
Page**

Instructor: Dr. Shieu-Hong Lin

Class Time: **T
TH **at **Busn 209**

· Contact Dr. Lin in advance to set up an appointment.

· Monday to Thursday: 8:30am~10:30am.

Course Syllabus: compact version

**About the reading reports:**

· **Effort (2
points):** How much time have you spent for the reading?
What percentage of the contents in the reading do you think you understand?
Have you come to the class this week? **Assessment**: The student is
expected to **(i)** have attended the class this week at least
once (0.5 point), and**(ii) have either **gained a good understanding
of **80% or more of the contents** **or** have spent at
least **three hours** in the reading (1.5 points).

· **Reflection on
the reading (2 points)**: Put down 1~2 paragraphs of your thoughts such as notes of new
insight you gained, interesting things encountered, questions of things you
don’t understand, and so forth.** ****Assessment**: the student is
expected to show substantial evidence of understanding or effort of trying to
understand the contents in the reading.

*****************************************************************************************************

**Week 1: Introduction
to Propositional Logic**

- Reading
#1, due Thursday,
**Feb. 9****:**(i) Carefully read Sections 1.1 and 1.3 in Discrete*Mathematics and Its Applications*, 7th Ed. Submit your report online under Canvas. (ii) Read Section 1.2 if it takes**less than****3 hours**for you to read 1.1 and 1.3 in (i). **Homework #1,**Thursday,**Feb. 9****: Please click here**to download**propositional logic.**Either**hand in your work on paper**in the class or**scan and upload an electronic version**under Canvas.**Clarification on Homework #1****:**(i) For problem #1 and #3, your compound proposition should only be composed of the three atomic propositions D4, D100 and D400, parentheses as needed, and the logic operators ˄, ˅, and ̚ as needed. Don’t use other logic operators. (ii) For problem #5, please do include 8 rows in the truth table, corresponding to all the 8 possible combinations of truth values for three independent atomic propositions. Do so even though the truth values D4, D100 and D400 are dependent and some of the 8 combinations could not happen.

******************************************************************************************************* **** **

**Week ****2:
Algebraic Laws and Logical Equivalence in Propositional Logic**

- Reading #2, due Thursday,
**Feb. 16****:**(i) Review Sections 1.1 and 1.3 in Discrete*Mathematics and Its Applications*, 7th Ed. again. (ii) Read Section 1.2 and Section 1.4. **Homework #2,**due Thursday,**Feb. 16****: Please click here**to download**propositional logic**.

Showcase: An Eclipse logic program for solving Sudoku puzzles

******************************************************************************************************* **** **

**Week ****3:
Introduction to Predicate Logic. **

- Reading #3, due Thursday,
**Feb. 23****:**Read Sections 1.4 and 1.5 in Discrete*Mathematics and Its Applications*, 7th Ed. **Homework #3**, due Thursday,**March. 2****: Please click here**to download**predicate logic**.

** **** **

**Week ****4:
Predicate Logic, Rules of Inference, and Basics of Proofs****.
**

- Reading #4, due Thursday,
**March. 2****:**(i) Review Sections 1.4 and 1.5 in Discrete*Mathematics and Its Applications*, 7th Ed. if you need more exposure to familiar with predicate logic. (ii) Read Sections 1.6-1.8 if you are confident about Sections 1.4 and 1.5.

** **** **

**Week ****5:
Review on Logic. **

- Reading #5, due Thursday,
**March. 9****:**(i) Review Sections 1,1, 1.3, 1.4 and 1.5 in Discrete*Mathematics and Its Applications*, 7th Ed.to prepare for Test #1. (ii) Read Sections 1.6-1.8.

**Test #1** on Logic (in-class
open-book test), Thursday,
**Mar. 9****: **(i) Cover all the things from
Reading #1 Reading #4 on logic. (ii) Make sure
you understand the all the homework problems and the related concepts very
well. (iii) Make sure you understand the algebraic laws
and logic equivalence depicted in Tables 6, 7,
and 8 in Section 1.3 and are capable of using them for determining logic
equivalence.

** **** **

**Week 6 and Week 7: Sets, Set
Operations, and Proofs |
Mission Conference Mar. 15~17**

- Reading
#6, due Thursday, Mar. 16 (extended to Monday May 20)
**:****(i) Required**: Sections 2.1-2.2 in Discrete*Mathematics and Its Applications*, 7th Ed. (ii)**Optional**if you are interested: Sections 12.1-12.3 in Discrete*Mathematics and Its Applications*, 7th Ed.

- Reading #7 due Thursday,
**Mar. 23****:**Review Sections 2.1-2.2 and Sections 1.6-1.8 in Discrete*Mathematics and Its Applications*, 7th Ed. - Homework
#4 due Thursday,
**Mar. 23****: Please click here**to download**sets and direct proofs.**

** **** **

**Week 8: More on Sets, Set Operations, and Proofs | ****Basics of
Counting **

- Reading
#8 due Thursday,
**Mar. 30****:**Read Sections 6.1, 6.3 and 8.5 in Discrete*Mathematics and Its Applications*, 7th Ed. - Homework #5
**Mar. 30 (****submission open till April 6 without penalty)****: Please click here**to download**sets and direct proofs.**

** **** **

**Week 9: Basics of
Counting **

- Reading
#9 due Thursday,
**April 6****: Re-read****Sections 6.1, 6.3 and 8.5 one more time**in Discrete*Mathematics and Its Applications*, 7th Ed. - Homework
#6
**: Please click here**Homework #6 on**counting and derangement,**due Thursday, April 13**(submission open till Tuesday, April 25 without penalty)****.**

**Test #2** on Logic and Sets (in-class
open-book test), Tuesday,
**April 11****: **

·
**Range**: Cover all the things from
Reading #1 to Reading #7 on logic and sets. Make
sure you understand all the problems in Homework#1~Homework#5. There are 43
questions in total, leading to 43 points in total. Getting 33 points would be
considered as 100%.

·
**On predicate logic**: Make sure you review the concepts
of predicate logic needed for doing **Problem#3 in Homework #3**. You need to understand
the algebraic laws and logic equivalence
depicted in Tables 6, 7, and 8 in Section 1.3
and are capable of using them for determining logic equivalence.

·
**On sets**: Make sure you review the
related concepts needed for doing Homework #4 and Problem #1 in Homework #5.
You need to be able to reason about the subset relationship among sets, set
equality, and the use of logic behind them. It would be helpful if you understand
set identities depicted in Table 1 in Section 2.2 and are capable of using them
to reason about the equality of sets.

** **** **

**Weeks 10-11: Binomial Coefficients
+ Relations **

- Reading
#10 due Thursday,
**April 27****:**Read**Sections 6.1~6.4**(note that 6.2 & 6.4 are new) in Discrete*Mathematics and Its Applications*, 7th Ed. - Reading
#11 due Thursday,
**May 4****:**Read**Sections 9.1 – 9.3**on relations in Discrete*Mathematics and Its Applications*, 7th Ed.

- Homework
#7
**: Please click here**Homework #7 on**counting,**due Thursday, May 4.

** **** **

**Power point class notes** available under
**Files** in our Canvas class site.

References: (i) Set operations in Python

** **** **

**TAs: **William Gertsch,
Ho Leung**. **

**TA hours in MATH lab (Grove 10): Wednesday 4:30~5:30pm and Thursday 3:00~4:00pm
starting from Wednesday 03/22**

** **** **

**To
the Top of this Page**