Work Hours
Everyday: 北京时间8:00 - 23:59
Welcome!
- Glad to see everyone!
- These are uncertain times, make sure you invest in family,
friends and giving. - This is the last quarter before the summer, let’s make it count!
- And find a way to have fun.
2
What is Mathematics,
really? - It’s not just about numbers!
- Mathematics is much more than that:
- But, these concepts can be about numbers, symbols,
objects, images, sounds, anything!
Mathematics is, most generally, the study of
any and all absolutely certain truths about
any and all perfectly well-defined concepts.
Calculus is for continuous systems - Calculus f(x) versus x, considers a continuous
variable x. - Continuous numbers: x is a number which can
have any number of decimal places, - E.g. 3.1415
- Transcendental numbers: pi=3.1415926…..
Discrete systems and structures
6
Discrete Structures
We’ll Study • Propositions - Predicates
- Proofs
- Sets
- Functions
- Orders of Growth
- Algorithms
- Integers
- Summations
- Sequences
- Strings
- Permutations
- Combinations
- Relations
- Graphs
- Trees
- Logic Circuits
- Automata
7
Some Notations We’ll
Learn
9
Uses for Discrete Math in Computer
Science - Advanced algorithms
& data structures - Programming
language compilers &
interpreters. - Computer networks
- Operating systems
- Computer architecture
- Database management
systems - Cryptography
- Error correction codes
- Graphics & animation
algorithms, game
engines, etc.… - I.e., the whole field!
- Data Science and
machine learning
12
Course Objectives - Upon completion of this course, the student should
be able to: - Check validity of simple logical arguments (proofs).
- Check the correctness of simple algorithms.
- Creatively construct simple instances of valid logical
arguments and correct algorithms. - Describe the definitions and properties of a variety of
specific types of discrete structures. - Correctly read, represent and analyze various types of
discrete structures using standard notations.
Think! (Critical reasoning)
Part #1: Foundations of Logic - Mathematical Logic is a tool for working with
elaborate compound statements. It includes: - A formal language for expressing them.
- A concise notation for writing them.
- A methodology for objectively reasoning about
their truth or falsehood. - It is the foundation for expressing formal proofs
in all branches of mathematics.
Examples: English is ambiguous - Are you not going to the party tonight?
- You must be at least 5 feet tall or over the age of
14 to ride the rollercoaster. - The lawn is wet, so either it rained last night or
the sprinklers went on this morning, but not
both happened.
Foundations of Logic:
Overview - Propositional logic:
– Basic definitions.
– Equivalence rules & derivations. - Predicate logic
– Predicates.
–Quantified predicate expressions.
– Equivalences & derivations.
Propositional Logic - Propositional Logic is the logic of compound
statements built from simpler statements
using so-called Boolean connectives.
Some applications in computer science: - Design of digital electronic circuits.
- Expressing conditions in programs.
- Queries to databases & search engines.
Topic #1 – Propositional Logic
George Boole
(1815-1864)
Chrysippus of Soli
(ca. 281 B.C. – 205 B.C.)
Definition of a Proposition - Definition: A proposition (denoted p, q, r, …) is simply:
- A declarative statement with some definite meaning,
(not vague or ambiguous) - having a truth value that is either true (T) or false (F)
- it is never both, neither, or somewhere “in between”
- However, you might not know the actual truth value,
- and, the truth value might depend on the situation or context.
Topic #1 – Propositional Logic
Note, we will also use the notation:
T=1, F=0
Examples of Propositions
•
“Beijing is the capital of China.”
•
“1 + 2 = 5”
•
“It is raining.” (T/F assessed given situation.) - But, the following are NOT propositions:
•
“Who’s there?” (interrogative, question)
•
“La la la la la.” (meaningless interjection)
•
“Just do it!” (imperative, command)
•
“1 + 2” (expression with a non-true/false
value; does not assert anything)
Topic #1 – Propositional Logic
Absurd statements can be propositions - “Pigs can fly”
- “The moon is made of green cheese”
- “1+1 = 10”
Example –
Are these statements propositions? - P = “This statement is true”
- P = “This statement is false”
Example –
Are these statements propositions? - P = “This statement is true”
- Yes, and the truth value is T
- P = “This statement is false”
- No, not a proposition; cannot assign T or F
- It is not logically consistent:
- If P is T then the statement is F (i.e., P is F)
- If P is F then the statement is T (i.e., P is T)
- A proposition must be T or F but not both.
Boolean Operators / Connectives - An operator or connective combines one or more operand
expressions into a larger expression. (E.g.,
“
+
” in
numeric expressions.)
– Unary operators take 1 operand (e.g., negation, −3);
– binary operators take 2 operands (e.g., multiplication, 3
´ 4). - Propositional or Boolean operators operate on
propositions (or their truth values) instead of on numbers.
Topic #1.0 – Propositional Logic: Operators
Some Popular Boolean Operators
Formal Name Nickname Arity Symbol
Negation operator NOT Unary ¬
Conjunction operator AND Binary Ù
Disjunction operator OR Binary Ú
Exclusive-OR operator XOR Binary Å
Implication operator IMPLIES Binary ®
Biconditional operator IFF Binary ↔
Topic #1.0 – Propositional Logic: Operators
Truth tables - To evaluate the T or F status of a compound
proposition - Enumerate over all T and F assignments of all the
propositions
⼩ onyou
Exclusive or
enterAorBnotboth
ifA V Bmustv
no
Handonlyif
The Negation Operator - The unary negation operator “¬” (NOT) transforms a prop.
into its logical negation. - E.g. If p =
“I have brown hair.”
then ¬p =
“I do not have brown hair.” - The truth table for NOT:
p ¬p
T F
F T
T :≡ True; F :≡ False
“
:≡
”
means
“is defined as”
Operand
column
Result
column
The Conjunction Operator - The binary conjunction operator “
Ù
” (AND) combines two
propositions to form their logical conjunction. - E.g. If
p=
“I will have salad for lunch.” and
q=
“I will have steak for dinner.”
, - then pÙq=
“I will have salad for lunch and I will have steak for
dinner.”
Remember: “
Ù
” points up like an “A”, and it means “
Ù!”
”
Ù!”
Conjunction Truth Table - A conjunction
p1 Ù p2 Ù … Ù pn
of n propositions
will have 2n rows
in its truth table. - Remark. ¬ and Ù operations together are
sufficient to express any Boolean truth table!
p q p∧q
F F F
F T F
T F F
T T T
Operand columns
Topic #1.0 – Propositional Logic: Operators
八 And
The Disjunction Operator - The binary disjunction operator “
Ú
” (OR) combines two
propositions to form their logical disjunction. - p=
“My car has a bad engine.” - q=
“My car has a bad carburetor.” - pÚq=
“Either my car has a bad engine, or
my car has a bad carburetor.”
After the downwardpointing “axe” of “Ú”
splits the wood, you
can take 1 piece OR the
other, or both.
Ú
Topic #1.0 – Propositional Logic: Operators
Meaning is like “and/or” in English.
Disjunction Truth Table - Note that pÚq means
that p is true, or q is
true, or both are true! - So, this operation is
also called inclusive or,
because it includes the
possibility that both p and q are true. - Remark.“¬” and “
Ú
” together are also universal. (We can
write any Boolean logic function in terms of those operators.)
p q pÚq
F F F
F T T
T F T
T T T
Note
difference
from AND
Topic #1.0 – Propositional Logic: Operators
Nested Propositional Expressions - Use parentheses to group sub-expressions:
“I just saw my old friend, and either he’s grown or I’ve shrunk.” - First break it down into propositions:
- f = “I just saw my old friend”
- g = “he’s grown”
- s = “I’ve shrunk”
- = f Ù (g Ú s)
- (f Ù g) Ú s would mean something different
- f Ù g Ú s would be ambiguous
- By convention, “¬” takes precedence over both “
Ù
” and “
Ú
”. - ¬s Ù f means (¬s) Ù f , it does not mean ¬ (s Ù f)
Topic #1.0 – Propositional Logic: Operators
or
A Simple Exercise - Let
p=
“It rained last night”
,
q=
“The sprinklers came on last night,”
r=
“The lawn was wet this morning.” - Translate each of the following into English:
- ¬p =
- r Ù ¬p =
- ¬ r Ú p Ú q =
Topic #1.0 – Propositional Logic: Operators
and or
and or
and or
The Exclusive Or Operator - The binary exclusive-or operator “Å” (XOR) combines two
propositions to form their logical “exclusive or” (exclusive
disjunction) - p =
“I will earn an A in this course,” - q =
“I will drop this course,” - p Å q =
“I will either earn an A in this course, or I will drop it
(but not both!)” - A more common phrase: “Your entrée comes with either
soup or salad”
Topic #1.0 – Propositional Logic: Operators
hot hand
ad
or or
Exclusive-Or Truth Table - Note that pÅq means
that p is true, or q is
true, but not both! - This operation is
called exclusive or,
because it excludes the
possibility that both p and q are true. - Remark. “¬” and “Å” together are not
universal.
p q pÅq
F F F
F T T
T F T
T T F Note
difference
from OR.
Topic #1.0 – Propositional Logic: Operators
Natural Language is
Ambiguous - Note that English “
or
” can be ambiguous
regarding the “both” case!
•
“Pat is a singer or
Pat is a writer.” –
•
“Pat is alive or
Pat is deceased.” – - Need context to disambiguate the meaning!
- For this class, assume “
or
”
means inclusive.
p q p “or” q
F F F
F T T
T F T
T T ?
Ú
Å
Topic #1.0 – Propositional Logic: Operators
The Implication Operator - The implication p ® q states that p implies q.
- i.e., If p is true, then q is true; but if p is not true,
then q could be either true or false. - E.g., let p =
“You master ECS20.”
q =
“You will get a good job.” - p ® q =
“If you master ECS20, then you will get a good job.”
(But note, some good jobs do not require discrete math so having a good job does not
necessarily mean that you mastered ECS20).
Let’s build the truth table for p ® q
Topic #1.0 – Propositional Logic: Operators
hypothesis/antecedent conclusion/consequent
粣
Implication Truth Table - p ® q is false only when
p is true but q is not true. - p ® q does not say
that p causes q! - p ® q does not require
that p or q are ever true! - E.g. “(1=0) ® pigs can fly” is TRUE!
p q p®q
F F T
F T T
T F F
T T T
The
only
False
case!
Topic #1.0 – Propositional Logic: Operators
Examples of Implications
•
“If this lecture ever ends, then the sun will rise
tomorrow.” True or False?
•
“If Tuesday is a day of the week, then I am a
penguin.” True or False?
•
“1+1=6, if Biden is president.”
True or False?
•
“If the moon is made of green cheese, then I am
richer than Elon Musk.” True or False?
ngnntagthg Btme
Sufmfhd anymgan
be he
Examples of Implications
•
“If this lecture ever ends, then the sun will rise
tomorrow.” True or False? (p=T and q=T)
•
“If Tuesday is a day of the week, then I am a
penguin.” True or False? (p=T and q=F)
•
“1+1=6, if Biden is president.”
True or False? (p=T and q=F)
•
“If the moon is made of green cheese, then I am
richer than Elon Musk.” True or False? (p=F and q=F)
o
tifio
p.mg
o
Logic cares about T/F values and not about if
implications are sensical - Consider a sentence like,
•
“If I wear a red shirt tomorrow, then global peace will
prevail” - In logic, the sentence is True so long as either I don’t wear
a red shirt, or global peace is achieved. - But, in normal English conversation, if I were to make this
claim, you would think that I was crazy. - Why this discrepancy between logic & language?
- Logic is about self-consistency.
Q f P
English Phrases Meaning p ® q
•
“
p implies q
”
•
“if p, then q
”
•
“if p, q
”
•
“when p, q
”
•
“whenever p, q
”
•
“
q if p
”
•
“
q when p
”
•
“
q whenever p
”
•
“
p only if q
”
•
“
p is sufficient for q
”
•
“
q is necessary for p
”
•
“
q follows from p
”
•
“
q is implied by p
”
•We will see some equivalent
logic expressions later.
Topic #1.0 – Propositional Logic: Operators
In this class we will use the phrases in red above
Translating between written English and
propositional logic - Isolate the constituent propositions of a compound
proposition. (You can name them with letters that remind
you what the proposition is about.) - For conditional statements, note if it is written in terms of
“if p then q” or in terms of “q if p”. - Identify the Boolean operators being used in the
compound proposition. - Write the sentence in propositional logic.
Example 1
•
Example 2
•
If and_ then_
Example 3
•
pmhgifq
Converse, Inverse, Contrapositive - Some terminology, for an implication p ® q:
- Its converse is: q ® p.
- Its inverse is: ¬p ® ¬q.
- Its contrapositive: ¬q ® ¬ p.
- One of these three has the same meaning (same
truth table) as p ® q. Can you figure out which?
Topic #1.0 – Propositional Logic: Operators
or - Proving the equivalence of p ® q and its
contrapositive using truth tables:
p q ¬q ¬p p®q ¬q ®¬p
F F T T T T
F T F T T T
T F T F F F
T T F F T T
Topic #1.0 – Propositional Logic: Operators
Foundations of logic come from the
implication operator and its contrapositive
i F DF
The biconditional operator - The biconditional p « q states that p ® q and q ® p
- In other words, p is true if and only if (IFF) q is true.
- p =
“Italy wins the 2022 FIFA World Cup.” - q =
“Italy will be World Cup Champion for all of
2023.” - p « q =
“If, and only if, Italy wins the 2022 World
Cup, Italy will be World Cup Champion for all of
2023.”
Biconditional Truth Table - p « q means that p and q
have the same truth value. - Remark. This truth table is the
exact opposite of Å’s! - Thus, p « q means ¬(p Å q)
- p « q does not imply
that p and q are true, or that either of them causes
the other, or that they have a common cause.
p q p « q
F F T
F T F
T F F
T T T
Topic #1.0 – Propositional Logic: Operators
Boolean Operations Summary
Order of operation: ¬, Ù, Ú, Å, ®, «
i.e., p V ¬q ® p Ù q means (p V (¬q)) ® (p Ù q)
(Note, precedence of Ú, Å is ambiguous and often
depends on the programming language)
p q ¬p pÙq pÚq pÅq p®q p«q
F F T F F F T T
F T T F T T T F
T F F F T T F F
T T F T T F T T
Topic #1.0 – Propositional Logic: Operators
X
Some Alternative Notations
Name: not and or xor implies iff
Propositional logic: ¬ Ù Ú Å ® «
Boolean algebra: p pq + Å
C/C++/Java (wordwise): ! && || != ==
C/C++/Java (bitwise): ~ & | ^
Logic gates:
Topic #1.0 – Propositional Logic: Operators
Bits and Bit Operations - A bit is a binary (base 2) digit: 0 or 1.
- Bits may be used to represent truth values.
- By convention:
0 represents “false”
;
1 represents “true”. - Boolean algebra is like ordinary algebra except that
variables stand for bits, - means
“
or
”, and
multiplication means “and”. - See module 23 (chapter 10) for more details.
Topic #2 – Bits
John Tukey
(1915-2000)
Propositional Consistency
Propositional Consistency - Life is complex: we often have to satisfy multiple
logical compound propositions - Eg. A=, B=
- Two different compound propositions may be
True at the same time. We call them consistent.
Learn: - How to prove propositional consistency using
truth tables.
Topic #1.1 – Propositional Logic: Equivalences
Logical Consistency - Definition: Compound proposition p is logically
consistent with compound proposition q, IFF p
and q can be true simultaneously. - Compound propositions p and q are logically
consistent to each other IFF p and q contain T
simultaneously in at least one row of their truth
tables.
Topic #1.1 – Propositional Logic: Equivalences
E.g., Where Is the Treasure? - Among four people, P1, P2, P3, P4, at least one of is truthful,
and at least one is lying - One of the truthful ones has a treasure in their pocket.
- They each know who has the treasure and each of them
makes a statement:
S1 (by P1): I don’t have the treasure.
S2 (by P2): My pockets are empty.
S3 (by P3): P1 is lying.
S4 (by P4): P1 is lying.
Where is the treasure?
Where Is the Treasure?, contd. - How to solve?
- Name the statements, and create a truth table where the
inputs are the truthfulness of the people (Truthful, Lies) - Find a row for which all S1-S4 are True
P1 P2 P3 P4 S1-S4
consistent
Why?
T T T T No All truthful
T T T L No
T T L T Yes!
S1 (by P1): I don’t have
the treasure.
S2 (by P2): My pockets
are empty.
S3 (by P3): P1 is lying.
S4 (by P4): P1 is lying.
v
ǒǐò t
Propositional Equivalence R P4agm.es ǛR h
Rl 970 L o
Rz Tame na Ti
Rlutd
53 utd
T T L L NO PI P4，54 and
stl
Propositional Equivalence - Two syntactically (i.e., textually) different
compound propositions may be the semantically
identical (i.e., have the same meaning). We call
them equivalent. Learn: - Various equivalence rules or laws.
- How to prove equivalences using symbolic
derivations.
Topic #1.1 – Propositional Logic: Equivalences
Tautologies and Contradictions - A tautology is a compound proposition that is
always true no matter what the truth values of its
atomic propositions are! - Ex. p Ú ¬p = T always
- A contradiction is a compound proposition that is
false no matter what! - Ex. p Ù ¬p = F always
- Otherwise the compound prop. is a contingency.
(i.e. most propositions are contingencies)
Topic #1.1 – Propositional Logic: Equivalences
Logical Equivalence - Definition: Compound proposition p is logically
equivalent to compound proposition q, written
pÛq, IFF the compound proposition p«q is a
tautology. - Note, Û is often denoted by º
(We will use both notations in this class) - Compound propositions p and q are logically
equivalent to each other IFF p and q contain the
same truth values as each other in all rows of
their truth tables.
Topic #1.1 – Propositional Logic: Equivalences
Contingency letter - Prove that pÚq Û ¬(¬p Ù ¬q).
Proving Equivalence
via Truth Tables
Proving Equivalence
via Truth Tables - Ex. Prove that pÚq Û ¬(¬p Ù ¬q).
p q pÚq ¬p ¬q ¬p Ù ¬q ¬(¬p Ù ¬q)
F F
F T
T F
T T
F
T
T
T
T
T
T
T
T
T
F
F
F
F
F
F
F
F
T
T
Topic #1.1 – Propositional Logic: Equivalences
or and
Equivalence Laws - These are similar to the arithmetic identities you
may have learned in algebra, but for
propositional equivalences instead. - They provide a pattern or template that can be
used to match all or part of a much more
complicated proposition and to find an
equivalence for it. - Summarized in Table 6, Sec 1.3 of Rosen (and
posted on Canvas)
Topic #1.1 – Propositional Logic: Equivalences
or ad 的七
Equivalence Laws – Examples - Identity: pÙT Û p pÚF Û p
- Domination: pÚT Û T pÙF Û F
- Idempotent: pÚp Û p pÙp Û p
- Double negation: ¬¬p Û p
- Commutative: pÚq Û qÚp pÙq Û qÙp
- Associative: (pÚq)Úr Û pÚ(qÚr)
(pÙq)Ùr Û pÙ(qÙr)
Topic #1.1 – Propositional Logic: Equivalences
Based on Rosen, Discrete Mathematics & Its Applications, 5e
Prepared by (c)2001-2004 Michael P. Frank
Modified by (c) 2004-2005 Haluk Bingöl
‹#›/92Module #1 – Logic
More Equivalence Laws
•Distributive: pÚ(qÙr) Û (pÚq)Ù(pÚr)
pÙ(qÚr) Û (pÙq)Ú(pÙr)
•De Morgan’s:
¬(pÙq) Û ¬p Ú ¬q
¬(pÚq) Û ¬p Ù ¬q
•Trivial tautology/contradiction:
p Ú ¬p Û T p Ù ¬p Û F
Topic #1.1 – Propositional Logic: Equivalences
Augustus
De Morgan
(1806-1871)
Based on Rosen, Discrete Mathematics & Its Applications, 5e
Prepared by (c)2001-2004 Michael P. Frank
Modified by (c) 2004-2005 Haluk Bingöl
‹#›/92Module #1 – Logic
De Morgan’s law
p q pÚq pÙq
F F F F
F T T F
T F T F
T T T T
Not (p or q): ¬(pÚq) Û ¬p Ù ¬q
Not (p and q): ¬(pÙq) Û ¬p Ú ¬q
or
and or d or
ad or
pqtpnpnpvnq 5
T T F F d N T S T T
or and FT T T
FF T T
or and
Summary of basic equivalences
Defining Operators via Equivalences - Using equivalences, we can define operators in
terms of other operators. - Exclusive or: pÅq Û (pÚq)Ù¬(pÙq)
pÅq Û (pÙ¬q)Ú(qÙ¬p) - Implication: p®q Û ¬p Ú q
- Biconditional: p«q Û (p®q) Ù (q®p)
p«q Û ¬(pÅq)
Topic #1.1 – Propositional Logic: Equivalences
p q p®q
F F T
F T T
T F F
T T T
Logical equivalences for conditional
statements
Tables 7-8, Sec1.3 Rosen
Example 1 for logical equiv.
•
Example 2 for logical equiv.
Example 3 – an involved calculation - Check using a symbolic derivation whether
(p Ù ¬q) ® (p Å r) Û ¬p Ú q Ú ¬r. - (p Ù ¬q) ® (p Å r)
- Û ¬(p Ù ¬q) Ú (p Å r) [Expand definition of ®]
- Û ¬(p Ù ¬q) Ú ((p Ú r) Ù ¬(p Ù r)) [Expand defn. of Å]
- Û (¬p Ú q) Ú ((p Ú r) Ù ¬(p Ù r)) [DeMorgan’s Law]
- cont.
Topic #1.1 – Propositional Logic: Equivalences
Example Continued… - Û (¬p Ú q) Ú ((p Ú r) Ù ¬(p Ù r))
- Û (q Ú ¬p) Ú ((p Ú r) Ù ¬(p Ù r)) [Ú commutes]
- Û q Ú (¬p Ú ((p Ú r) Ù ¬(p Ù r))) [Ú associative]
- Û q Ú (((¬p Ú (p Ú r)) Ù (¬p Ú ¬(p Ù r))) [distrib. Ú over Ù]
Û q Ú (((¬p Ú p) Ú r) Ù (¬p Ú ¬(p Ù r))) [assoc.]
Û q Ú ((T Ú r) Ù (¬p Ú ¬(p Ù r))) [trivail taut.]
Û q Ú (T Ù (¬p Ú ¬(p Ù r))) [domination]
Û q Ú (¬p Ú ¬(p Ù r)) [identity]
cont.
Topic #1.1 – Propositional Logic: Equivalences
End of Long Example
Û q Ú (¬p Ú ¬(p Ù r))
Û q Ú (¬p Ú (¬p Ú ¬r)) [DeMorgan’s]
Û q Ú ((¬p Ú ¬p) Ú ¬r) [Assoc.] - Û q Ú (¬p Ú ¬r) [Idempotent]
- Û (q Ú ¬p) Ú ¬r [Assoc.]
Û ¬p Ú q Ú ¬r [Commut.]
Q.E.D.
Remark. Q.E.D. (quod erat demonstrandum)
Topic #1.1 – Propositional Logic: Equivalences
(Which was to be shown.)
Review: Propositional Logic - Atomic propositions: p, q, r, …
- Boolean operators: ¬ Ù Ú Å ® «
- Compound propositions: s :º (p Ù ¬q) Ú r
- Equivalences: pÙ¬q Û ¬(p ® q)
- Proving equivalences using:
- Truth tables.
- Symbolic derivations. p Û q Û r …
Topic #1 – Propositional Logic
Foundations of logic
