Transcript Document

Agenda
• Review Minggu 1:
– Partition
• Topik Minggu 2:
– Propositions
– Conditional Propositions & Logical
Equivalence
– Arguments & Rules of Inference
– Quantifiers
– Nested Quantifiers
• Latihan Soal
Review: Partition
• A partition of a set X is a set of nonempty subsets of
X such that every element x in X is in exactly one of
these subsets
 X is a disjoint union of the subsets.
• A family of sets P is a partition of X if and only if all
of the following conditions hold:
– P does not contain the empty set.
– The union of the sets in P is equal to X. (The sets
in P are said to cover X.)
– The intersection of any two distinct sets in P is
empty. (We say the elements of P are pairwise
disjoint .
•
Propositions
Propositions/Statements
• A statement (or proposition) is a sentence
that is true or false but not both.
• The truth value of a proposition is either
TRUE / T / 1 or FALSE / F / 0.
• Ex.
– two plus two equals four
• Proposition? Yes
• Truth value: true
– Jakarta is the capital of Singapore
• Proposition? Yes
• Truth value: false
Examples
• Two plus two equals five
– Proposition? Yes
– Truth value: False
• An elephant is bigger than an ant
– Proposition? Yes
– Truth value: true
• He is a university student
– Proposition? No
– Truth value: depends on who he is
• C is bigger than 10
– Proposition? No
– Truth value: unknown
• F plus G equals 9
– Proposition? No
– Truth value: unknown
Examples:
• Dimana letak kampus UMN?
– Proposition? No (pertanyaan)
• Jangan memakai sandal ke kampus
– Proposition? No (perintah)
• Mudah-mudahan jalan tidak macet
– Proposition? No (harapan)
• Indahnya bulan purnama
– Proposition? No (ketakjuban / keheranan)
Compound Propositions /
Compound Statements
• A composition of two or more propositions /
statement that is true or false but not both
• Example:
– Budi is studying at UMN, he is a university
student
• Compound statement? Yes
• Truth value : True
– Jika x = 1 dan y = 2 maka x lebih besar daripada y
• Compound Statement? Yes
• Truth value: False
Examples
• x ≤ a means x < a or x = a
• a ≤ x ≤ b means a ≤ x and x ≤ b
• 2≤x≤1
– compound statement? Yes
– Truth value: False
Formalization of (Compound) Statements
• Translating a (compound) statement to symbols
(such as x, y, z) and logical operator.
• Logical operator:
~,¬


 not
 and
 or
Examples
¬p : not p, negation of p
p  q : p and q, conjunction of p and q
p  q : p or q, disjunction of p and q
• Order of operation :
(… )
~, ¬


Example:
¬p  q = (¬p)  q
p  q  r Is it (p  q)  r or p  (q  r) ?
To be safe, use (…)
Examples
• p: Today is Friday
• Negation: ~p: Today is not Friday
• p: At least 10 inches of rain fell today in Jakarta
• Negation: ~p: Less than 10 inches of rain fell
today in Jakarta
Examples
• p = it is hot; q = it is sunny
• It is not hot but sunny
– It is not hot and it is sunny
~p  q
• It is neither hot nor sunny
– It is not hot and it is not sunny
~p  ~q
Truth Table
The list of all possible truth values of a compound
statement.
Truth Table for Negation
Truth Table for Conjunction p  q
It is hot and it is sunny
Truth Table for Disjunction p  q
It is hot or it is sunny
Truth Table for Exclusive Or
It is hot or it is sunny, but not both
Definition:
(p  q)  ~(p  q) : p  q, p XOR q,
Evaluating the Truth of more General
Compound Statements
~p  q = (~p)  q
Steps:
- Evaluate the expressions within the innermost
parentheses
- Evaluate the expressions within the next innermost
set of parentheses
- Until you have the truth values for the complete
expression.
Evaluating the Truth of more General
Compound Statements
p
T
T
F
F
q
T
F
T
F
~p
F
F
T
T
~p  q
F
F
T
F
Tautology and Contradiction
Tautology: True (for any truth values of their variables)
Contradiction: False (for any truth values of their variables)
Contoh:
Tautology
Contradiction
Notes on Programming Language
p  q = p && q
p  q = p || q
~p = !p
Conditional Propositions
&
Logical Equivalence
Conditional Proposition
Definition
• Let p and q be propositions. The conditional
proposition p  q is the proposition “if p then q”.
p is called the hypothesis (or antecedent or
premise) and q is called the conclusion (or
consequence).
• “p implies q”
“p  q”; p: hypothesis, q: conclusion.
• Conditional: the truth of statement q is
conditioned on the truth of statement p
• Example:
IF 36 is divisible by 6, THEN 36 is divisible by 3
Conditional Proposition
• IF Maria learns discrete mathematics, THEN she
will find a good job.
• p: Maria learns discrete mathematics
• q: she will find a good job.
• pq
• Under what circumstances is the above sentence
false?
• False when Maria learns discrete mathematics but
not find a good job
• IF you show up for work Monday morning, THEN
you will get the job.
• Under what circumstances is the above sentence
false?
Truth Table for Conditional Proposition
Definition
• p  q is false when p is true and q is false;
otherwise it is true.
Example:
Biconditional Proposition
Definition
• Given statement variables p and q, the
biconditional of p and q is “ p if and only if q” and
is denoted p  q. The words if and only if are
sometimes abbreviated iff.
Priority
• Logical operator:
()
~, ¬


, 
 not
 and
 or
 if-then, iff
Logical Equivalence
Definition:
• Two statement forms are called logically
equivalent if, and only if, they have
identical truth values for each possible
substitution of statements for their
statement variable.
P=pq
Q=qp
• The logical equivalence of statement
forms P and Q is denoted by writing P  Q
~(~p)  p
Are ~(p  q) and ~p  ~q logically
equivalent?
De Morgan’s Laws
Definition:
• The negation of an AND statement is logically
equivalent to the OR statement in which each
component is negated.
~(p  q)  ~p  ~q
• The negation of an OR statement is logically
equivalent to the AND statement in which each
component is negated.
~(p  q)  ~p  ~q
De Morgan’s Laws: Truth Table
De Morgan’s Laws: Exercise
Use De Morgan’s Laws to find the negation of each of
the following statements:
• Jan is rich and happy
• Carlos will bicycle or run tomorrow
• Melani walks or takes the bus to class
• Ibrahim is smart and hard working
Representation of IF-THEN as OR
• p: you do not get to work on time
• q: you are fired
• IF you do not get to work on time THEN you are
fired
• ~p: you get to work on time
• You get to work on time OR you are fired
p  q  ~p  q
Negation,
Contrapositive,
Converse,
Inverse
The Negation of a Conditional Proposition
• The negation of “IF p THEN q” is logically
equivalent to “p and not q”
~(p  q)  p  ~q
• Show the equivalence by using Morgan Law:
~(p  q)  ~(~p  q)
 ~(~p)  ~q
 p  ~q
The Negation of a Conditional Proposition
• Exercise:
Truth table for
~(p  q)  p  ~q
The Negation of a Conditional Proposition
• ~(IF my car is in the repair shop, THEN I cannot
get the class)
• My car is in the repair shop and I can get to class
• ~(IF Sara lives in Jakarta, THEN she lives in
Indonesia)
• Sara lives in Jakarta and she does not live in
Indonesia
Biconditional Proposition
• Is “ p if, and only if, q” logically equivalent with
“ if p then q “ and “if q then p” ?
p q  (p  q)  (q  p)
Biconditional Proposition: Truth Table
The Contrapositive of a Conditional Proposition
Definition
• The contrapositive of a conditional statement of
the form “IF p THEN q” is “IF ~q THEN ~p”
• The contrapositive of p  q is ~q  ~p
• Are they logically equivalent?
Construct the truth table
• A conditional statement is logically equivalent to
its contrapositive.
Contrapositive: Examples
• IF Howard can swim across the lake, THEN
Howard can swim to the island
• IF Howard cannot swim to the island, THEN
Howard cannot swim across the lake
• IF today is Easter, THEN tomorrow is Monday
• IF tomorrow is not Monday, THEN today is not
Easter
The Converse and Inverse of
a Conditional Statement
Definition
• Suppose a conditional statement of the form “IF p
THEN q” is given.
• The converse is “IF q THEN p”
• The inverse is “IF ~p THEN ~q”
Symbolically
• The converse of p  q is q  p
• The inverse of p  q is ~p  ~q
Are they logically equivalent?
Construct the truth table
Converse and Inverse: Truth Table
p
q
~p ~q p  q q  p ~p  ~q
T
T
F
F
T
T
T
T
F
F
T
F
T
T
F
T
T
F
T
F
F
F
F
T
T
T
T
T
Converse and Inverse: Examples
• IF Howard can swim across the lake, THEN
Howard can swim to the island
• Converse: IF Howard can swim to the island THEN
Howard can swim across the lake
• Inverse: IF Howard cannot swim across the lake,
THEN Howard cannot swim to the island.
• IF today is Easter, THEN tomorrow is Monday
• Converse: IF tomorrow is Monday, THEN today is
Easter
• Inverse: IF today is not Easter, THEN tomorrow is
not Monday
Arguments
&
Rules of Inference
Argument
The bug is either in module 17 or in module 81
The bug is a numerical error
Module 81 has no numerical error
Conclusion:
The bug is module 17
• Deductive reasoning: drawing a conclusion from
a sequence of propositions.
Argument
Definition
• A (deductive) argument is a sequence of
hypotheses that ends with a conclusion.
IF premise-1, ….., premise-n THEN conclusion
• An argument is valid if and only if it is impossible
for all the premises to be true and the conclusion
to be false. If the premises are all true, then the
conclusion is also true, otherwise the argument
is invalid.
Argument
premise-1
premise-2
.
.
.
premise-n
q
• The symbol , read “therefore”
Example
• If you have a current password, then you can log
onto the network
• You have a current password
• Therefore,
• You can log onto the network
pq
p
q
• Construct the truth table
p  q, p
q
Testing the Validity of an Argument
• Identify the premises and conclusion of the
argument
• Construct a truth table showing the truth
values of all the premises and the conclusion
• Find the rows (called critical rows) in which
all the premises are true
• In each critical row, determine whether the
conclusion of the argument is also true.
– If in each critical row the conclusion is also true,
then the argument form is valid
– If there is at least one critical row in which the
conclusion is false, the argument form is invalid
Valid or Invalid Argument ?
p  ( q  r)
~r
p  q
Valid or Invalid Argument ?
p  q  ~r
qpr
p  r
Modus Ponens
pq
p
q
Modus ponens: method of affirming
Modus Tolens
pq
~q
 ~p
Exercise: Construct the truth table
Modus tolens: method of denying
Modus Tolens
Example
It is below freezing now
Therefore,
It is either below freezing or raining now
p
pq
Valid argument : addition rule
Example
It is below freezing and raining now
Therefore,
It is below freezing now
pq
p
Valid argument : simplification rule
Example
If it rains today, then we will not have a barbecue
today
If we do not have a barbecue today, then we will
have a barbecue tomorrow
Therefore,
If it rains today, then we will have a barbecue
tomorrow
pq
q r
p  r
Valid argument : hypothetical syllogism
Rule of Inference and Arguments
To show whether an argument is valid, when there
are many premises in an argument:
- Construct truth table (not efficient)
- Use several rules of inference
Example
It is not sunny this afternoon and it is colder than
yesterday.
We will go swimming only if it is sunny
If we do not go swimming, then we will take a
canoe trip
If we take a canoe trip, then we will be home by
sunset
Conclusion:
We will be home by sunset
Quantifiers
How to express?
Can we express the following statements by using
propositional logic we have learned before?
“Every computer connected to the university
network is functioning properly”
“computer-1 is functioning properly”
“There is a computer on the university network
that is under attack by an intruder”
No!
Introducing Predicate Logic
Predicates
Let P(x) be a statement involving the variable x and
let D be a set.
We call P a propositional function or predicate
(with respect to D) if for each x  D, P(x) is a
proposition.
D is the domain of discourse of P.
Predicates
“x is greater than 3”
x: variable
“greater than 3”: the property that the variable can
have.
“x is greater than 3”: propositional function
(predicate) P at x or P(x)
Once a value has been assigned to x, the
statement P(x) becomes a proposition and has a
truth value.
P(x) : (x > 3)
Truth values of P(4) and P(2)?
P(4) is true, P(2) is false
Predicates
A(x) : Computer x is under attack by an intruder
Reality: comp-1 and comp-9 are under attack
A(comp-1) and A(comp-9) are true, but A(comp-5)
is false.
Q(x,y) : x2 > y2 + 6
Q(3,2)?
Q(4,3)?
Quantifiers
Quantification expresses the extent to which a
predicate is true over range of elements (domain).
Ex. all, some, many, none, few.
Predicate calculus: the area of logic that deals with
predicates and quantifiers.
Universally Quantified Statement: a predicate is true
for every element under consideration.
Existensially Quantified Statement: there is one or
more element under consideration for which the
predicate is true.
Universal Quantifiers
• Definition
“P(x) for all values of x in the domain”
Where P(x) is statement.
• Notation:
x P(x)
For all x P(x), or for every x P(x), or for any x P(x)
• Counterexample: an element of x for which P(x) is
false.
Example
•
•
•
•
P(x) : x + 1 > x
Domain: all real numbers.
What is the truth value of x P(x)?
True, because P(x) is true for all real numbers.
•
•
•
•
Q(x) : x < 2
Domain: all real numbers.
x Q(x)?
Counterexample: x = 3; x Q(x) is false.
Example
•
•
•
•
P(x) : x2 > 0
Domain: all integers.
x P(x)?
Counterexample: x = 0; x P(x) is false.
•
•
•
•
Q(x) : x2 < 10
Domain: positive integers not exceeding 4
x Q(x)?
Counterexample: x = 4; x Q(x) is false.
Existensial Quantifier
• Definition
“There exists an element x in the domain such that
P(x)”
Where P(x) is a statement.
• Notation:
x P(x)
there is an x such that P(x), or there is at least one
x such that P(x), or for some x P(x)
Existensial Quantifier
• Definition
“There exists an element x in the domain such that
P(x)”
Where P(x) is a statement.
• Notation:
x P(x)
there is an x such that P(x), or there is at least one
x such that P(x), or for some x P(x)
Example
•
•
•
•
P(x) : x > 3
Domain: all real numbers.
What is the truth value of x P(x)?
True, because P(x) is true for x = 4.
•
•
•
•
Q(x): x = x + 1
Domain: all real numbers.
x Q(x)?
False, because Q(x) is false for every real number
x.
Example
•
•
•
•
Q(x): x2 > 10
Domain: positive integer not exceeding 4.
x Q(x)?
True, because Q(x) is true for x = 4.
Summary
Statement
When True?
When False?
x P(x)
P(x) is true for
every x
x P(x)
There is an x for P(x) is false for
which P(x) is true every x
There is an x for
which P(x) is false
Negation
• “every student in your class has taken a course in
calculus”
• P(x): x has taken a course in calculus
• Domain: the students in your class
• x P(x)
• Negation:
• “there is a student in your class who has not taken
a course in calculus”
• x P(x)  x P(x)
• x Q(x)  x Q(x)
Generalized De Morgan’s Laws for Logic
Negation Equivalent
x P(x)
x P(x)
x P(x) x P(x)
When is Negation
True?
For every x, P(x) is
false
When
False?
There is an x
for which P(x)
is true
There is an x for which P(x) is true
P(x) is false
for every x
Nested Quantifiers
Nested Quantifiers
How to express:
The sum of any two positive real numbers is positive.
Variables: x, y
If x > 0 and y > 0 then x + y > 0
OR
P(x, y): (x > 0)  (y > 0)  (x + y > 0)
x y P(x, y)
Domain of discourse R x R
In words:
For every x and for every y, if x > 0 and y > 0, then x +
y>0
Nested Quantifiers
Hx y P(x, y) is true if for every x  X and y  Y,
P(x, y) is true
x y P(x, y) is false if there is at least one x  X and
at least one y  Y, P(x,y) is false 
counterexample
x y (x > 0)  (y < 0)  (x + y ≠ 0) ?
Counterexample: x = 1 and y = -1
ow to express:
In words:
For every x and for every y, if x > 0 and y > 0, then x +
y>0
Nested Quantifiers
How to express:
Everybody loves somebody.
L(x, y): x loves y
“everybody”: universal quantification
“somebody” existensial quantification
x y L(x, y)
In words:
For every person x, there exists a person y such
that x loves y
This is not a correct interpretation:
x y L(x, y)
In words:
There exists a person x such that for all y, x loves y
Nested Quantifiers
x y L(x, y) is true if for every x  X, there is at
least one y  Y for which L(x,y) is true
x y L(x, y) is false if there is at least one x  X
such that L(x, y) is false for every y  Y
x y (x + y = 0)
Domain R x R
True: for every real number x, there is at least one y
(namely y = -x) for which x + y = 0
x y (x > y)
Domain Z+ x Z+
False: there is at least one x, namely x = 1, such
that x > y is false for every positive integer y.
Nested Quantifiers
x y L(x, y) is true if there is at least one x  X
such that L(x, y) is true for every y  Y
x y L(x, y) is false if for every x  X, there is at
least one y  Y such that L(x,y) is false
x y L(x, y) is true if there is at least one x  X and
at least one every y  Y such that L(x, y) is true
x y L(x, y) is false if for every x  X and for every
y  Y, L(x,y) is false
The Generalized Morgan’s law for logic
~(x y L(x, y)) = x ~(y L(x, y))
= x  y ~L(x, y)