Category: Resources (Page 1 of 2)

Lesson 25 Handout – Strong Induction examples

Theorem NT 5.1: Every natural number $n>1$ is either prime or divisible by a prime.

Theorem NT 5.2: Suppose $p$ is prime and $a_{1}, a_{2}, a_{3}, \ldots, a_{n}$ are $n$ integers, where $n \geq 2$. If $p \mid a_{1} \cdot a_{2} \cdot a_{3} \cdot \ldots \cdot a_{n},$ then $p \mid a_{i}$ for at least one of the $a_{i}(1 \leq i \leq n)$.

Theorem NT 5.3: If $n$ is an integer greater than 1 then $n$ can be written as a product of primes.
(HINT: Prove using strong induction. Consider two cases, when $k+1$ is prime, and when it is composite)

Lesson 15 bonus example: Proofs involving gcd

Hi everyone,

On Tuesday we introduced the idea of greatest common divisor and we looked at several theorems about properties of the gcd.

Definition. The greatest common divisor of integers $a$ and $b$, denoted $\gcd(a,b)$, is the largest integer that divides both $a$ and $b$.

In your homework, you are asked to prove propositions that involve the gcd. It may help to keep the following in mind:

To prove that a number $x$ is the gcd of $a$ and $b$

We need to show two things:

1.  $x$ is a common divisor of $a$ and $b$ (that is, $x|a$ and $x|b$)

2.  if  $y|a$ and $y|b$, then $x\geq y$ (“if $y$ is a common divisor of $a$ and $b$, then $x\geq y$”

Here is an example, so we can see how it works in practice:

Proposition. If $a, b$ are integers then $\gcd(a,b) = \gcd(a+b,b)$.

VIDEO: Example – proof with gcd

Lesson 8: Negating Statements, Counting Lists

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:

  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:

Continue reading

Lesson 6: Biconditionals, Truth Tables, and Logical Equivalence

Hi everyone! Read through the material below, watch the videos, and follow up with your instructor if you have questions.

Lesson 6: Biconditionals, Truth Tables, and Logical Equivalence

Topic. This lesson covers:

  1. Sec 2.4 Biconditional Statements
  2. Sec 2.5 Truth tables for Statements
  3. Sec 2.6 Logical equivalence

Learning Outcomes.

  • Identify instances of biconditional statements in both natural language and first-order logic, and translate between them.
  • Construct truth tables for statements.
  • Determine logical equivalence of statements using truth tables and logical rules.

Homework. There is one WeBWorK assignment on today’s material:

  1. WeBWorK: Assignment3-Sec2.1-2.6

Lecture Notes:

Continue reading

Lesson 4: Indexed Sets

Hi everyone! Read through the material below, watch the videos, and follow up with your instructor if you have questions.

Lesson 4: Indexed Sets

Topic. This lesson covers:

  • Sec 1.8: Indexed Sets

Learning Outcomes.

  • Take unions and intersections of collections of sets indexed by the natural numbers or other sets.

Homework. There is 1 written assignment on today’s material:

  1. Homework: Section 1.8 p.29: 3, 5, 6, 8

Lecture Notes:

Continue reading

Lesson 2: Cartesian Products and Subsets

Hi everyone! Read through the material below, watch the videos, and follow up with your instructor if you have questions.

Lesson 2: Cartesian Products and Subsets

Topic. This lesson covers:

  • Sec 1.2: Cartesian Products
  • Sec 1.3: Subsets

Learning Outcomes.

  • Identify and manipulate ordered pairs and Cartesian products of sets.
  • Identify and manipulate subsets of sets.

WeBWorK. There is 1 WeBWorK assignment on today’s material:

  1. Assignment1-Sec1.2-1.3

Lecture Notes:

Continue reading

Getting Started with WeBWorK

Your first WeBWorK assignment is due on Tuesday, September 8th, at the start of class, and will cover the material from Lesson 2.  Here’s what you have to do:

Assignment.  To get started , you must complete the following three steps.

Step 1.  Log in to WeBWorK here. I have created Usernames and Passwords for each student registered for my class.

Username.  Your username for WeBWorK consists of your first initial plus your last name, all lowercase (for example, John Smith would have username ‘jsmith’).

Password.  Your password is your Student ID (EmplID in CUNYFirst).

Step 2.   Update your email address if you wish.  To do this, select “Password/Email” from the main menu on the left.  Use whatever email address you like (I suggest using one that you check often).

Step 3.  Complete the first assignment, titled Assignment1-Sec1.2-1.3. Click on an assignment on the main screen to get started.

If you have any trouble – either with logging in, or with completing the assignment, post a comment here or send me an email and I will get back to you.

WeBWorK Tips:

  1. Click on a problem to see the details (the list of problems appears in the menu on the left).  Enter an answer and hit “Submit Answers”.  Don’t worry, if you get it wrong you can try it again.
  2. You can work on the problems in any order you wish.  You can do some problems now, and come back and do the rest another day (your work will be saved, as long as you submit your answers).
  3. If you want to print out a copy of the assignment, click on the assignment name in the main menu on the left, and then click the link in the main screen area that reads “Download a hardcopy of this homework set.”
« Older posts