Hi everyone! This online lesson is provided as a resource – we will also go over this material in class.

Lesson 8: Negating Statements, Counting Lists

Topic. This lesson covers:

  1. Sec 2.10 Negating Statements
  2. Sec 3.1 Counting Lists
  3. Sec 3.2 Factorials

Learning Outcomes.

  • Apply rules for negating various types of statements, both in formal logic and natural language
  • Count collections of lists with various properties

Homework. There is one WeBWorK assignment on today’s material (Note: some of the material in this assignment will be covered in the next lesson):

  1. WeBWorK: WeBWorK Assignment5-Sec3.1-3.4

Lecture Notes:

Lesson-8_-Negating-statements-counting-listsDownload

Vocabulary

  • list
  • entry
  • length
  • empty list
  • multiplication principle
  • repetitive and non-repetitive lists
  • factorial

Negating Statements

Our final topic in Logic is something that will be of considerable use to us in proofs – rules for simplifying the negations of statements. We have already learned how negations work with conjunctions and disjunctions (De Morgan’s Laws), and today we complete our collection by learning how they work with conditional statements and quantifiers.

Rules for negating statements (quantifiers and conditional statements)

  • $\sim(\forall x \in S, P(x))=\exists x \in S, \sim P(x)$
  • $\sim(\exists x \in S, P(x))=\forall x \in S, \sim P(x)$
  • $\sim(P \Rightarrow Q)=P \wedge \sim Q$

RECALL: Rules for negating conjunctions and disjunctions (De Morgan’s Laws)

  • $\sim (P\wedge Q) = (\sim P \vee \sim Q)$
  • $\sim (P\vee Q) = (\sim P \wedge \sim Q)$

Example 1. Find the negation of the sentence, both in symbols and in words.
a. $R$: $x$ and $y$ are both odd.
b. $S$: All prime numbers are odd.
c. The square of every real number is non-negative.
d. For every real number $x$, there is a real number $y$ for which $y^{3}=x$
e. If $x$ is odd, then $x^{2}$ is even.

VIDEO: Negating Statements

Chapter 3: Combinatorics

In the course so far we have covered two very important topics related to proofs, Set Theory and Logic. We now take a slight detour into Combinatorics, or the science of counting. This will let us flex our logical reasoning muscles (as we develop various formulas for counting things), and will also provide great material that we will revisit later while proving things.

Counting Lists

It turns out that lists are a very useful way to think about organizing and counting objects. A list is similar to a set, with some exceptions (the order matters, and objects can be repeated).

Definition. A list is an ordered sequence of objects (called entries in the list).  The length of a list is simply the number of entries.  A list is typically written enclosed in parentheses, with objects separated by commas.  An ordered pair $(a,b)$ is simply a list of length 2.

  • Example: $(a,b,c,d,e)$ is a list of length 5.
  • Order matters in a list, so $(a,b,c,d,e)\neq (b,d,e,c,a)$
  • Objects can be repeated in a list:  $(a,a,b,c)$ is a list of length 4.
  • The empty list, or list with no entries, is the only list with length 0.

Example 2. Make a list of length 3 in which the first entry comes from the set $\{a, b, c\},$ the second entry comes from the set $\{3,4\},$ and the third entry comes from the set $\{a, x\}$ . How many such lists are there?

VIDEO: Introduction to Lists – Example 2

Multiplication Principle.  Suppose in making a list of length $n$ that there are $a_1$ possible choices for the first entry, $a_2$ possible choices for the second entry, $a_3$ possible choices for the third entry, and so on. The the number of different lists that can be made in this way is the product $a_1\cdot a_2 \cdot a_3 \cdot …\cdot a_n$

Example 3.  A standard license plate consists of three letters followed by four numbers.  For example JRB-4412 and MMX-8901 are two different standard license places.  How many different standard license plates are possible?

Example 4. Consider making lists from the set $\{A, B, C, D, E, F, G\}$.  How many length-4 lists are possible if:
a) repetition is allowed? “repetitive lists”
b) repetition is NOT allowed? “non-repetitive lists”
c) repetition is NOT allowed and the list must contain an E?
d) repetition is allowed and the list must contain an E?

NOTE: Depending on your prior experience, you may be more familiar with the phrases “with replacement” (repetitive list), and “without replacement” (non-repetitive list).

VIDEO: Counting Lists – Examples 3 and 4

Definition. If n is a non-negative integer, then n factorial, written n!, is the number of non-repetitive lists of length n that can be made from n symbols.

Example 5. Using the definition, calculate $3!$, $2!$, $1!$, $0!$.  What is $4!$ ?

Exit Question

This problem involves making lists of length $7$ from the set $\{0, 1, 2, 3, 4, 5, 6, 7\}$.
a) How many such lists are there if repetition is allowed?
b) How many such lists are there if repetition is allowed and the first three entries must be odd?
c) How many such lists are there if repetition is not allowed?
d) How many such lists are there if repetition is not allowed and the first three entries must be odd?
e) How many such lists are there in which repetition is allowed, and the list must contain at least one repeated number?

Answer

a) $8^7 = 2097152$
b) $4^3\cdot8^4=262144$
c) $8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2 = 40320$
d) $4\cdot3\cdot2\cdot5\cdot4\cdot3\cdot2 = 2880$
d) $8^7 – 8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2 = 2056832$