Transcript Document

The Foundations: Logic and Proof
CS104
1
What is Discrete Structure?
 Discrete Objects
 Separated from each other (Opposite of
continuous)
 e.g., integers, people, house,
 Vs. Continuous objects: e.g., real number
 Discrete Structures
 The abstract mathematical structures used to
represent discrete objects and relationships
between the objects e.g. sets, relations, graphs
2
Why do we study Discrete Structures?
 Information is stored and manipulated by
computers in a discrete fashion. 0101101…
 As a student in computer science major, you
need to know the basic language and conceptual
foundation for all of the computer science, i.e.,
Discrete Structures!
 Discrete structure concepts are also widely
used throughout math, science, engineering,
economics, biology, etc., …
 Get training for rational thought!
3
1.1 Propositional Logic
4
•Introduction
•Propositions
•Propositional Logic
• Negation
• Connectives ( conjunction – disjunction – exclusive OR)
• Conditional statements (implication)
• Converse, Contrapositive and Inverse
• Biconditional
•Truth tables of Compound Propositions
•Precedence of Logic Operators
•Logic and Bit Operations
Introduction
 The rules of logic are used to distinguish between valid
and invalid mathematical arguments.
 Logic has many applications to computer science.
 Ex:
 Computer circuits
 Construction of computer programs
5
Propositions
 The basic building blocks of logic.
 It is a declarative sentence (a sentence that declares a
fact) that is either True or False, but not both.
1.
2.
3.
4.
6
Example 1
Riyadh is the capital of Saudi
Arabia.
Cairo is the capital of Lebanon.
1+1=2
2+2=3
All declarative sentences are
propositions
T – F –T – F
1.
2.
3.
4.
Example 2
What time is it?
Read this carefully.
x+1=2
x+y=z
Not propositions
1+2 not declarative sentences
3+4 neither true or nor false
Propositions
 We use letters to denote propositional variables that is
used to represent propositions, just as letters used to
denote numerical variables.
 The conventional letters used for propositions variables
are p, q, r, s…
 The truth value if the proposition is true  T
 The truth value if the proposition is false F
 The area of logic that deals with proposition is called the
proposition calculus or propositional logic.
7
Propositions
 There are a methods for producing new propositions
from those what we have.
 Many mathematical statement are constructed by
combining one or more propositions (compound
propositions) using logical operators.
8
Negation of a proposition
Definition1 :
Let p be a proposition. The negation of p, denoted by p,
is the statement “it is not the case that p”.
 The proposition p is read “NOT p”
 Negation construct a new proposition from a single
existing proposition.
 The truth table for the negation of a proposition.
Notice that p is a
proposition!
9
p
p
F
T
T
F
Negation of a proposition
Example 3:
Find the negation of the proposition
“Sara’s pc runs Linux” and express this in simple
English.
Solution:
Negation is: “it is not the case that Sara’s pc runs
Linux”
More simply: “Sara’s pc does not runs Linux”
10
Negation of a proposition
Example 4:
Find the negation of the proposition
“Ahmad’s smart phone has at least 32 GB of memory” and
express this in simple English.
Solution:
Negation is: “Ahmad’s smart phone does not have at least32
GB of memory”
More simply: “Ahmad’s smart phone has less than 32 GB of
memory”
11
Conjunction of propositions
Definition2 :
Let p and q be a proposition. The conjunction of p and q,
denoted by pq, is the proposition “p and q”. The
conjunction pq is true when both p and q are true, and
is false otherwise.
 Sometimes “But” is used instead of “And” in conjunction.
 The truth table for the conjunction of two proposition.
Notice that conjunction
can be between two or
more propositions
12
p
q
pq
T
T
F
F
T
F
T
F
T
F
F
F
Conjunction of propositions
Example 5:
Find the conjunction of the propositions p and q,
where p is the proposition “Ahmad’s pc has more than
16 GB free hard disk space”
and q is the proposition “The processor in Ahmad’s pc
runs faster than 1 GHz” express this in simple English.
Solution:
Ahmad’s pc has more than 16 GB free hard disk space and The
processor in Ahmad’s pc runs faster than 1 GHz.
To be true, both conditions given must be true. It is false when
one or both are false
13
Disjunction of propositions
Definition3:
Let p and q be a proposition. The disjunction of p and q,
denoted by p  q, is the proposition “p or q”. The
conjunction p  q is false when both p and q are false,
and is true otherwise.
 The truth table for the disjunction of two proposition.
Notice that disjunction
can be between two or
more propositions
14
p
q
pq
T
T
F
F
T
F
T
F
T
T
T
F
Disjunction of propositions
Example 6:
Find the disjunction of the propositions p and q,
where p is the proposition “Ahmad’s pc has more than
16 GB free hard disk space”
and q is the proposition “The processor in Ahmad’s pc
runs faster than 1 GHz” express this in simple English.
Solution:
Ahmad’s pc has more than 16 GB free hard disk space orThe
processor in Ahmad’s pc runs faster than 1 GHz.
When it will be true? False?
15
Exclusive-OR of propositions
Definition4:
Let p and q be a proposition. The exclusive or of p and q,
denoted by p ⊕ q, is the proposition that is true when
exactly one of p and q is true and is false otherwise.
 The truth table for the exclusive or of two proposition.
Notice it can be between
two or more propositions
16
p
q
p⊕q
T
T
F
F
T
F
T
F
F
T
T
F
 Note:
inclusive or : The disjunction is true when at least one of the
two propositions is true.
 E.g. “Students who have taken calculus or computer science
can take this class.” – those who take one or both classes.
exclusive or : The disjunction is true only when one of the
proposition is true.
 E.g. “Students who have taken calculus or computer science,
but not both, can take this class.” – only those who take
one of them.
17
Conditional Statement (Implication)
Definition5:
Let p and q be a proposition. The conditional statement
(implication) p  q is the proposition “if p, then q”. The
conditional statement p  q is false when p is true and q is false,
otherwise true.
 In the conditional statement p  q, p is called the hypothesis or
(antecedent or premise) and q is called the conclusion or
(consequence).
 Comes in format:
 If p, then q
 If p, q
 p is sufficient for q
 p implies q
…
18
you will find rest of them in book. Look at them!
Conditional Statement (Implication)
 The truth table for the implication
of two proposition.
p
q
p q
T
T
F
F
T
F
T
F
T
F
T
T
Ex:
“If you get 100% on the final, then you will get an A”.
Hypothesis
19
Conclusion
Conditional Statement (Implication)
Example
Hypothesis
Conclusion
If Juan has a smart phone, then 2+3 = 5
This proposition is true, because conclusion is true.
If Juan has a smart phone, then 2+3 = 6
This proposition is true, if Juan does not have a smart
phone even though 2+3=6 is false.
There are no relation between hypothesis and conclusion.
In programming we have if-then.
20
Conditional Statement (Implication)
Example 7:
Let p the statement “Maria learns discrete mathematics”
and q the statement “ Maria will find job”
express the statement p  q as a statement in
English.
Solution:
 If Maria learns discrete mathematics, then she will find job.
 Maria will find job when she learns discrete mathematics.
Rest example in book page 7
When it will be true? False?
21
Converse, Contrapositive and Inverse
 Converse:
 Ex.:
q  p is converse of p  q.
p  q: “If it is noon, then I am hungry.”
q  p: “If I am hungry, then it is noon.”
 Contrapositive:
 Ex.:
 Inverse:
 Ex.:
22
q  p is contapositive of p  q.
q  p: “If I am not hungry, then it is
not noon.”
p  q is inverse of p  q.
p  q: “If it is not noon, then I am not
hungry.”
p  q has same truth values as q  p
See
example 7
Biconditional Statement
Definition6:
Let p and q be two propositions. The biconditional statement
(bi-implication) p ↔ q is the proposition “p if and only if q”.
The biconditional statement p ↔ q is true when p and q
have the same truth values, otherwise false.
 It corresponds to English “p if and only if q”.
 The truth table of biconditional
23
p
q
p↔q
T
T
F
F
T
F
T
F
T
F
F
T
Biconditional Statement
Example10:
p: “You can take the flight”
q : “You buy a ticket”
p ↔ q:
“You can take the flight if and only if you buy a
ticket”
 True if p and q both true or both false
 False otherwise
24
Implicit Biconditional Statement
 Not always explicit in natural language.
 Often expressed using an “if, then” or “only, if ”
 Converse is implied but not stated.
Ex:
“if you finish your meal, then you can have dessert”
Means
“You can have dessert if and only if you finish your meal”
25
Truth Table of Compound Proposition
 Used to build up complicated compound positions involving any numbers
of propositional variables.
 Example: Construct the truth table of the compound proposition
(p ν ¬q) → (p Λ q).
The Truth Table of (p ν ¬q) → (p Λ q).
p
q
¬q
p ν ¬q
pΛq
(p ν ¬q) → (p Λ q)
T
T
F
F
T
F
T
F
F
T
F
T
T
T
F
T
T
F
F
F
T
F
T
F
 Q3: Construct truth table for
 (p  q) ↔ (p  q).
 (p ⊕ q) → (p ⊕ q).
26
# of raws = 2 # of variable
Precedence
 Precedence of Logical Operators:
27
Operator
Precedence
()
¬
Λ
ν
→
↔
1
2
3
4
5
6
Logic and Bit Operations
 Bit: A bit is a symbol with two possible values,
namely, 0 (zero) and 1 (one).
 A bit can be used to represent a truth value as 1 for
T and 0 for F
 Bit string: A bit string is a sequence of bits. The
length of the string is number of bits in the string.
 Example: 10101001 is a bit string of length eight
 We define the bitwise OR, AND, and XOR of two
strings of same length to be the strings that have as
their bits the OR, AND, and XOR of the
corresponding bits in the two strings, respectively.
 We use the symbols , , and ⊕ to represent bitwise
OR, AND, and XOR, respectively.
28
Logic and Bit Operations
Truth table for bitwise OR, AND, and XOR:
x
y
0
0
1
1
0
1
0
1
xy
xy
x⊕
y
0
1
1
1
0
0
0
1
0
1
1
0
Example 13
Find bitwise OR, AND, and XOR of the bit strings
0110110110 and 1100011101
29