MAE 106: Discrete Mathematics with Probability Fall 2018

The course blog for MAE 106: Discrete Mathematics with Probability.

This course is intended to emphasize the basic concepts of elementary logic, sets and operations on sets, combinations and permutations, and discrete probability.

The course syllabus can be found here: Course Syllabus.

Test 2: 31 October 2018

  1. You should know the following formulas.
    • Combination \displaystyle\binom{n}{r} = \frac{n!}{r!(n-r)!}n choose r” (order does not matter)
    • \displaystyle\binom{n}{r} = \binom{n}{n-r} (The symmetry property) p. 167
    • Permutation \displaystyle P(n, r) = \frac{n!}{(n-r)!}n permute r” (order does matter)
  2. Do the following exercises.
    • 5.7.1 (a)–(h), 5.7.3, 5.7.4 (c)–(d), 5.7.5, 5.7.7, 5.7.9, 5.7.10, 5.7.11.
    • 8.1, 5.8.3, 5.8.4, 5.8.5 (a, c, e, g, k), 5.8.7, 5.8.12, 5.8.13, 5.8.15, 5.8.17, 5.8.18, 5.2.20
    • 5.11.1, 5.11.3, 5.11.4, 5.11.5, 5.11.6, 5.11.8, 5.11.15, 5.11.22, 5.11.24. Note that in 5.11.8, it should read “exactly 4 females?”
  3. Investigate Pascal’s triangle. Pascal’s triangle is a pattern that can be seen in Fig 7.8 on p. 280. There are many patterns that can be found in Pascal’s triangle. For example, the symmetry property can be seen in Fig. 7.9 on p. 283. The Fibonacci numbers (1, 1, 2, 3, 5, 8, 13, …), which is a sequence of numbers in which each number is the sum of the two preceding numbers, can also be found in Pascal’s triangle as seen in Fig. 7.10 on p. 283. The next couple of exercises will help you explore more patterns in Pascal’s triangle.
    • 7.1.1, 7.1.2, 7.1.3, 7.1.4 (a, b, f) [Pascal’s Theorem 7.1.3]
    • 7.1.12 (a, b, c, d, e). [The sum of entries in a row.] For part (c) iii: \binom{11}{0} + \binom{11}{1} + \cdots + \binom{11}{11}. For part (d): Generalize your findings to find an expression for the sum of row n. In other words, what is the value of \binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n}.
    • 7.1.13.
    • 7.1.15 (a, b, c, d, e, f). [The sum of the squared entries in a row.]
    • 7.1.17 (a, b, c, d). [The sum of the alternating sign entries in a row.]
    • 7.1.18.

Tags: ,

We know that we have distributive rules that handle the disjunction and the conjunction, such as the following

    \begin{align*} p \and (q \orr r) &\Leftrightarrow (p \and q) \orr (p \and r)\\ p \orr (q \and r) &\Leftrightarrow (p \orr q) \and (p \orr r). \end{align*}

But, does there exist a rule, for example, that would handle distributivity of the conjunction with the implication? In other words,

    \[\text{is } p \and (q \rightarrow r) \text{ logically equivalent to } (p \and q) \rightarrow (p \and r)?\]

At least, the above case, the answer is no. We can see this by constructing a truth table like the one below; the truth values of p \and (q \rightarrow r) are not the same as (p \and q) \rightarrow (p \and r).  Hence, p \and (q \rightarrow r) and (p \and q) \rightarrow (p \and r) are not logically equivalent. Therefore, it’s not a rule that we can apply in our proofs.

Rendered by QuickLaTeX.com

Tags: , , ,

Quiz: 24 October 2018

  1. Do the following exercises.
    • Kohar 5.2.2, 5.2.3, 5.2.8, 5.2.10, 5.2.16, 5.2.18, 5.2.22, 5.2.23, 5.2.24, 5.2.25
    • Kohar 5.3.1, 5.3.2, 5.3.3, 5.3.5, 5.3.6, 5.3.7
    • Kohar 5.4.1, 5.4.2 (a)–(b), 5.4.3, 5.4.5, 5.4.9, 5.4.10, 5.4.12
    • Kohar 5.5.1
    • Kohar 5.6.2, 5.6.3, 5.6.4
  2. The members of Kingston City Council are to vote either yes or no (but not both) on each of seven issues. In marking a ballot, each councilor has the option of abstaining on as many as six of the issues, but cannot abstain on all seven issues.  In how many ways can a ballot be marked? [Ans: 2186]
  1. Draw the Venn diagram for three sets A, B, and C that are mutually exclusive.
  2. Determine whether the following statements are true or false. Use a Venn diagram to aid you in answering.
    • If A \cup B = \varnothing, then A = \varnothing, and B = \varnothing.
    • (A \cup A') = \varnothing
    • If A \subseteq B, then A \cap B = A.
    • If A \subset B and B \subset C, then A \subset C.
    • If all cadets are students, and all students are academics, then all cadets are academics.
  3. Kohar 3.4.3, 3.4.5, 3.4.6, 3.4.9, 3.4.10, 3.4.11, 3.4.12, 3.4.13, 3.7.3.
  4. Kohar 3.5.3, 3.5.4
  5. Using the rules of set algebra show the following: A' \cap B' \cap C' = (A \cup B \cup C)'
  1. Exercises 3.1.1, 3.1.2, 3.1.3, 3.1.5, 3.1.6, 3.1.8
  2. Exercises 3.3.1, 3.3.3, 3.3.4, 3.3.5, 3.3.7, 3.3.8, 3.3.10, 3.3.11
  3. Exercises 3.7.4
  4. Create Venn diagrams for the following sets:
    • A \cap C
    • A \cup B \cup C
    • ((A \cap B) \cup C')
    • (A \cup B) \cap C
    • A' \cap B' \cap C'
    • B \cup C
      1. Know the following definitions.
        • Argument (what constitutes a valid argument?)
        • Fallacy
        • Modus ponens
        • Modus tollens
      2. Do the following exercises from the textbook (Kohar).
        • 2.2.3 (a), (b), 2.2.4, 2.2.5, 2.2.6, 2.2.7, 2.2.8, 2.2.9, 2.2.12, 2.2.13, 2.2.14, 2.2.15, 2.2.16, 2.2.17, 2.2.19
        • 2.4.1, 2.4.2
        • 2.9.4 a) b) c), 2.9.5, 2.9.6, 2.9.7
      3. Using the rules of inference, prove that modus ponens is a valid argument; that is, show that [(p\to q)\wedge p]\to q\Leftrightarrow \mathbb{T}.
      4. The following argument is called affirming the consequent. Is it valid?

    (Premise) p \rightarrow q
    (Premise) q
    (Conclusion) \therefore p

      1. The following argument is called denying the antecedent. Is it valid?

    (Premise) p \rightarrow q
    (Premise) \neg p
    (Premise) \therefore \neg q

Class will begin earlier than usual at 9:30 am. The quiz will start at this time.

Quiz: 19 September 2018 (at the beginning of class)

Do the following exercises from the textbook (Kohar).

  • 1.4.2
  • 1.6.2, 1.6.4
  • 1.7.1, 1.7.3, 1.7.4 (c), 1.7.5, 1.7.6, 1.7.7, 1.7.8, 1.7.9, 1.7.10, 1.7.12, 1.7.16
  • 1.8.6
  • 2.2.3 (a), (b), 2.2.4, 2.2.5, 2.2.6, 2.2.7, 2.2.8, 2.2.9, 2.2.14, 2.2.15, 2.2.17, 2.2.19

Quiz on 12 September 2018.

  1. Memorize the following definitions:
    • Proposition (Definition 1.2.1)
    • Prime Proposition (Definition 1.2.3)
    • Compound Proposition (Definition 1.2.5)
    • Paradox (Definition 1.2.7)
  2. Know the truth tables for the following:
    • Negation \neg
    • Conjunction \wedge
    • Disjunction \vee
    • Exclusive Disjunction \veebar
    • Implication \rightarrow
  3. Complete the following exercises in the textbook (Kohar).
    • Section 1.2—1.2.3, 1.2.4, 1.2.5
    • Section 1.3—1.3.1, 1.3.2, 1.3.5, 1.3.6, 1.3.10, 1.3.11