Discrete Mathematics
CS-UH 1002
Lecture 2
Spring 2024
Moumena Chaqfeh
1
In the previous lecture, we…
• Introduced the course, its learning objectives, methodologies,
outcomes, graded activities, and academic policies.
• Encouraged you to read the syllabus and ensure you understand how
the course learning outcomes are linked to your Program Learning
Outcomes (PLOs)
• Looked at the course schedule.
• Created our Connect accounts. Have you setup your account?
• Asked you to respond to the First-Day Survey. Please complete it on
Brightspace → Content → Getting Started → First-Day Survey.
2
Why Mathematics?
• The success of mathematics in solving problems across science,
engineering, society, and the arts provides ample reason.
• For most mathematicians, this not the primary motivation to
study mathematics.
• It is because of the joy they experience when doing mathematics.
• We can also feel the joy!
• Here’s a puzzle: Simplify the following algebraic expression:
𝑥 − 𝑎 𝑥 − 𝑏 𝑥 − 𝑐 … (𝑥 − 𝑧)
3
Today’s Lecture
• One of unique features of mathematics: there are definitive answers.
• In mathematics we can speak (and write) with extreme precision.
• To communicate mathematics clearly, precisely, unambiguously, we
need words composed into meaningful sentences that exactly convey
the meaning we intend.
This lecture will introduce you to the foundation of Speaking and
Writing Mathematically
4
Speaking and Writing
Mathematically
5
Introduction
• The mental effort to convert mathematical ideas into language is
vital to learning those concepts.
• Take the time to express your ideas clearly both verbally and in
writing.
• Say the ideas out loud and write them down.
• Writing can be difficult. The best way to learn is to practice.
6
Mathematical Definition
• A mathematical definition must be absolutely clear.
• Example: An integer is called even provided it is divisible by two.
Clear?
• Not entirely. The problem is that this definition contains terms that
we have not yet defined, in particular integer and divisible.
• Each of these terms can be defined in terms of simpler concepts.
7
What Do We Assume?
• The set of integers, denoted by the letter ℤ, is ℤ = … , −2, −1, 0, 1, 2, … .
• We know how to add, subtract, and multiply, and we need not prove basic
number facts such as 3 x 2 = 6.
• We assume the basic algebraic properties of addition, subtraction, and
multiplication and basic facts about order relations (<, ≤, >, ≥).
• See Appendix D in Scheinerman’s book for more details on what you may
assume.
8
Definition: Divisibility
• If n and d are integers then n is divisible by d, if and only if, n equals d
times some integer and d ≠ 0.
• Instead of “n is divisible by d”, we can say that: n is a multiple of d, or
d is a factor (or divisor) of n, or d divides n.
• The notation d|n is read “d divides n”.
• It follows that d does not divide n (d ∤ n) if, and only if, for any integer
k, n ≠ dk.
• In other words, the quotient n ∕ d is not an integer.
9
Divisibility: Examples
a) Is 21 divisible by 3? Yes, 21 = 3 · 7.
b) Does 5 divide 40? Yes, 40 = 5 · 8.
c) Does 7|42? Yes, 42 = 7 · 6
d) Is 32 a multiple of −16? Yes, 32 = (−16) · (−2).
e) Is 6 a factor of 54? Yes, 54 = 6 · 9.
f) Is 7 a factor of −7? Yes, −7 = 7 · (−1).
g) If k and m are integers, is 10km divisible by 5? Yes, We can write 10km = 5 · (2km)
and 2km is an integer because it is a
h) Does 4|15 No. 𝟏𝟓𝟒 = 3.75 which is not an integer. product of three integers.
10
Definition: Even and Odd
• Definition: The integer n is even if there exists an integer k such that n
= 2k, and n is odd if there exists an integer k, such that n = 2k + 1.
• Note that every integer is either even or odd and no integer is both
even and odd.
• We will need this basic fact about the integers in some of the example
proofs to follow.
11
Mathematical Theorem
• A Theorem is a statement (or proposition) about mathematics for
which there is a proof.
• A Proposition is a declarative sentence that is either true or false, but
not both.
12
Propositions: Examples
Which of the following sentences is a proposition?
• Toronto is the capital of Canada
• Read this carefully
•x+1=2
• What time is it?
• 4 + 5 = 10
13
The Nature of Truth
• In mathematics the word true is meant to be considered absolute,
unconditional, and without exception.
• What do you think about “All prime numbers are odd.”
• The statement is False. 2 is prime but even.
14
Conjectures, Mistakes, and Nonsenses
• A Conjecture is a statement being proposed to be true. Once a proof
is found, it becomes a theorem. It may turn out to be false.
• Mistakes: Statements that are false.
• Nonsense: “The square root of a triangle is a circle”. Since the
operation of extracting a square root applies to numbers, not to
geometric figures, the sentence doesn’t make sense.
15
Facts, Lemmas, and Corollaries
• Fact: A very minor theorem. The statement 6 + 3 = 9 is a fact.
• Lemma: A theorem whose main purpose is to help prove another,
more important theorem.
• Corollary: A result with a short proof. It is a theorem of less
importance which can be readily deduced from a previous, more
notable theorem.
16
Mathematical Proof
• A proof is an essay that incontrovertibly shows that a statement is
true.
• This can be done using definitions, other theorems, rules of inference.
• Proofs have many practical applications:
• Verification that computer programs are correct.
• Establishing that operating systems are secure.
• Enabling programs to make inferences in artificial intelligence.
• Showing that system specifications are consistent.
17
Mathematical Proof: Example
Prove that the sum of any two even integers is even.
• Proof: Given any two even integers, we need to show that their sum
is even.
• Suppose we have two particular, arbitrarily chosen even integers.
Then, we can represent them as 2r and 2s, where r and s are both
integers.
• By the distributive law of algebra, 2r + 2s = 2(r + s), which is even
because r + s is an integer. Thus the statement is true in general.
19
Writing Mathematically: Common Mistakes
• A language of our own: Common words (such as function) are used
differently in mathematics than in general use.
• Complete sentences: Mathematical notation must be part of a
sentence.
• Mismatch of categories: A line segment isn’t a number, a function
isn’t an equation, a set isn’t an operation, and so on.
• Don’t write “the function is equal to 3” when you mean “when the function is
evaluated at x = 5 the result is 3”. Note that we don’t have to be verbose.
Don’t write “f = 3”, but “f (5) = 3.”
20
Latex: Getting Started!
21
Introduction
• LATEX (pronounced LAY-tek or LAH-tek) is a tool used to create
professional-looking documents.
• It enables you to focus on the content of your document. You enter
plain text and let LATEX take care of the formatting.
• Why learn LATEX?
• Create Professional looking documents
• Focus only on content, not the format
• Utilize Existing Templates
22
A Simple Example
• What does a LATEX document look like?
• A simplest working example of a latex code:
\documentclass{article}
\begin{document}
First document. This is a simple example, with no extra parameters or packages
included.
\end{document}
This is the PDF of the above code
LATEX has taken care of the first piece of formatting, by indenting the first line of the paragraph. 23
Adding Proofs to LATEX
• You are supposed to use an existing template, which already includes the
required package to write proofs, which is amsthm.
• An example showing how can you add a proof to your document:
\documentclass{article}
\usepackage{amsthm}
\begin{document}
\begin{proof}
Your proof goes here.
\end{proof}
\end{document} This is the PDF of the above code
24
Adding Math to Proofs
Latex code
• LATEX allows two writing modes for In physics, the mass-energy
mathematical expressions: equivalence is stated
by the equation $E=mc^2$,
1. The Inline mode that is used to discovered in 1905 by Albert
write formulas as part of a text. Einstein.
• To put your equations in inline mode
use one of these delimiters: The PDF of the above code
• \( ... \)
• $ ... $
• \begin{math} ... \end{math}
25
Adding Math to Proofs
2. The display mode that has two versions: numbered and
unnumbered.
Latex code The PDF of the code
26
Example Latex Expression
27
Further Assistance
• More details on writing proofs using Latex:
• [Link]
• A reference to math symbols you might need to use:
• [Link]
th_symbols
28
What am I supposed to do?
• You are required to use an existing LATEX template to prepare for
your assignment submission. To do so, we will use Overleaf, which is
an online LATEX editor.
• These are the required steps:
1. To start using Overleaf go to [Link].
2. Use your institutional login by ”Login through your institutions” and
your NYU email address.
29
What am I supposed to do?
3. Once you are logged in, you should see the Overleaf Project
Management page.
30
What am I supposed to do?
4. To upload a project template, all
required files must be in a compressed .zip
file. You can find and download the
required template for Assignment 1 from
Brightspace under “Assignments”.
For now, download the ProofTemplate
from Brightspace to use it as a first
example.
In the Project Management page, click
New Project and in the drop-down menu
click Upload Project.
31
What am I supposed to do?
5. A box will appear, there you can drag and drop the .zip file or click
Select a .zip file to open a file browser and locate it.
32
What am I supposed to do?
6. Once you drop your
file or select it in your
file browser you will be
redirected to the editor,
where a new project
will be created with the
same name as the .zip
file.
33
What am I supposed to do?
7. After that, you can start editing. To see the result of your changes in
the PDF viewer (shown at the right side of the figure below), you have
to compile the document by simply hitting Recompile.
8. You can download your finished PDF by clicking the Download PDF
button on your PDF viewer as shown below.
For more details, visit:
[Link] 34
This is the end of today’s
lecture 😃
Next Lecture: Logic I
Readings: Rosen Book (1.1–1.3), Scheinerman Book (1.4)
35