Hi everyone! Read through the material below, watch the videos, and follow up with your instructor if you have questions.
Lesson 8: Negating Statements, Counting Lists
Topic. This lesson covers:
- Sec 2.10 Negating Statements
- Sec 3.1 Counting Lists
- 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):
- WeBWorK: WeBWorK Assignment5-Sec3.1-3.4
Lecture Notes:
Contents
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$
Prof Reitz – Do you know when webwork 5 will become available?
Hi Jack,
I thought it was available, but it turns out I hadn’t clicked the button to assign it to the class. You should see it in WeBWorK now – let me know if you don’t.
Thanks for the catch,
-Prof. Reitz