Transcript p q

Review I
Rosen 1.1-1.5, 3.1
Know your definitions!
Definition 1. Negation of p
Let p be a proposition.
The statement “It is not
the case that p” is also a
proposition, called the
“negation of p” or ¬p
(read “not p”)
p = The sky is blue.
p = It is not the case that
the sky is blue.
p = The sky is not blue.
Table 1.
The Truth Table for the
Negation of a Proposition
p
¬p
T
F
F
T
Definition 2. Conjunction of p
and q
Let p and q be
propositions. The
proposition “p and q,”
denoted by pq is true
when both p and q are
true and is false
otherwise. This is called
the conjunction of p and
q.
Table 2. The Truth Table for
the Conjunction of two
propositions
p
q
pq
T
T
F
F
T
F
T
F
T
F
F
F
Definition 3. Disjunction of p and
q
Table 3. The Truth Table for
the Disjunction of two
propositions
p
q
pq
T
T
F
F
T
F
T
F
T
T
T
F
Let p and q be propositions.
The proposition “p or q,”
denoted by pq, is the
proposition that is false
when p and q are both false
and true otherwise.
Definition 4. Exclusive or of p
and q
Table 4. The Truth Table for
the Exclusive OR of two
propositions
p
q
pq
T
T
F
F
T
F
T
F
F
T
T
F
Let p and q be
propositions. 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.
Definition 5. Implication pq
Let p and q be propositions. The
implication pq is the
proposition that is false when p
is true and q is false, and true
otherwise. In this implication p
is called the hypothesis (or
antecedent or premise) and q is
called the conclusion (or
consequence).
Table 5. The Truth Table for
the Implication of pq.
p
q
pq
T
T
F
F
T
F
T
F
T
F
T
T
Implications
•
•
•
•
•
•
•
•
If p, then q
p implies q
if p,q
p only if q
p is sufficient for q
q if p
q whenever p
q is necessary for p
• Not the same as the ifthen construct used in
programming
languages such as If p
then S
Implications
How can both p and q be false, and pq be true?
•Think of p as a “contract” and q as its “obligation” that is
only carried out if the contract is valid.
•Example: “If you make more than $25,000, then you must
file a tax return.” This says nothing about someone who
makes less than $25,000. So the implication is true no
matter what someone making less than $25,000 does.
•Another example:
p: Bill Gates is poor.
q: Pigs can fly.
pq is always true because Bill Gates is not poor. Another
way of saying the implication is
“Pigs can fly whenever Bill Gates is poor” which is true
since neither p nor q is true.
Related Implications
Converse of
pq
is
qp
Contrapositive
p  q is the
proposition
q  p
of
Definition 6. Biconditional
Table 6. The Truth Table for
the biconditional pq.
p
q
pq
T
T
F
F
T
F
T
F
T
F
F
T
Let p and q be propositions.
The biconditional pq is
the proposition that is true
when p and q have the
same truth values and is
false otherwise. “p if and
only if q, p is necessary and
sufficient for q”
Logical Equivalence
• An important technique in proofs is to replace a
statement with another statement that is “logically
equivalent.”
• Tautology: compound proposition that is always true
regardless of the truth values of the propositions in it.
• Contradiction: Compound proposition that is always
false regardless of the truth values of the propositions
in it.
Logically Equivalent
• Compound propositions P and Q are
logically equivalent if PQ is a tautology.
In other words, P and Q have the same truth
values for all combinations of truth values
of simple propositions.
• This is denoted: PQ (or by P Q)

Example: DeMorgans
• Prove that (pq)  (p  q)
(pq) p q (p  q)
p q
(pq)
TT
TF
FT
FF
T
F
F
F
F
T
F
F
T
F
T
F
F
T
T
T
F
T
F
T
List of Logical Equivalences
pT  p;
pF  p
Identity Laws
pT  T;
pF  F
Domination Laws
pp  p;
pp  p
Idempotent Laws
(p)  p
Double Negation Law
pq  qp; pq  qp
Commutative Laws
(pq) r  p (qr); (pq)  r  p  (qr)
Associative Laws
List of Equivalences
p(qr)  (pq)(pr)
p(qr)  (pq)(pr)
Distribution Laws
(pq)(p  q)
(pq)(p  q)
De Morgan’s Laws
p  p  T
p  p  F
(pq)  (p  q)
Misc. , Table 6
Or Tautology
And Contradiction
Implication Equivalence
pq(pq)  (qp)
Biconditional Equivalence
Prove: (pq)  q  pq
(pq)  q
 q  (pq)
 (qp)  (q q)
 (qp)  T
 qp
 pq
Left-Hand Statement
Commutative
Distributive
Or Tautology (Misc. T6)
Identity
Commutative
Begin with exactly the left-hand side statement
End with exactly what is on the right
Justify EVERY step with a logical equivalence
Prove: (pq)  q  pq
(pq)  q
Left-Hand Statement
 q  (pq)
Commutative
(qp)  (q q) Distributive
Why did we need this step?
Our logical equivalence specified that  is distributive on the
right. This does not guarantee distribution on the left!
Ex.: Matrix multiplication is not always commutative
(Note that whether or not  is distributive on the left is not the
point here.)
Prove or Disprove
p  q  p  q ???
To prove that something is not true it is enough to
provide one counter-example. (Something that is
true must be true in every case.)
p q pq
pq
F T T
F
The statements are not logically equivalent
Method to construct DNF
• Construct a truth table for the proposition.
• Use the rows of the truth table where the proposition is
True to construct minterms
– If the variable is true, use the propositional variable in the minterm
– If a variable is false, use the negation of the variable in the
minterm
• Connect the minterms with ’s.
How to find the DNF of (p q)r
p
q
r
(p q) r
(p q)r
T
T
T
T
F
F
T
T
F
T
T
T
T
F
T
T
F
F
T
F
F
T
T
T
F
T
T
T
F
F
F
T
F
T
T
T
F
F
T
F
F
T
F
F
F
F
T
T
There are five sets of input that make the statement true.
Therefore there are five minterms.
p
q
r
(p q) r
(p q)r
T
T
T
T
F
F
T
T
F
T
T
T
T
F
T
T
F
F
T
F
F
T
T
T
F
T
T
T
F
F
F
T
F
T
T
T
F
F
T
F
F
T
F
F
F
F
T
T
From the truth table we can set up the DNF
(p q)r  (pqr)  (pqr)  (pqr) 
(pqr)  (pqr)
Quantifiers
Universe of Discourse, U: The domain of a variable in
a propositional function.
Universal Quantification of P(x) is the
proposition:“P(x) is true for all values of x in U.”
Existential Quantification of P(x) is the proposition:
“There exists an element, x, in U such that P(x) is
true.”
Universal Quantification of P(x)
xP(x)
“for all x P(x)”
“for every x P(x)”
Defined as:
P(x0)  P(x1)  P(x2)  P(x3)  . . . for all xi in U
Example:
Let P(x) denote x2  x
If U is x such that 0 < x < 1 then xP(x) is false.
If U is x such that 1 < x then xP(x) is true.
Existential Quantification of P(x)
xP(x)
“there is an x such that P(x)”
“there is at least one x such that P(x)”
“there exists at least one x such that P(x)”
Defined as:
P(x0)  P(x1)  P(x2)  P(x3)  . . . for all xi in U
Example:
Let P(x) denote x2  x
If U is x such that 0 < x  1 then xP(x) is true.
If U is x such that x < 1 then xP(x) is true.
Quantifiers
xP(x)
•True when P(x) is true for every x.
•False if there is an x for which P(x) is false.
xP(x)
•True if there exists an x for which P(x) is true.
•False if P(x) is false for every x.
Negation (it is not the case)
xP(x) equivalent to xP(x)
•True when P(x) is false for every x
•False if there is an x for which P(x) is true.
 xP(x) is equivalent to xP(x)
•True if there exists an x for which P(x) is false.
•False if P(x) is true for every x.
Quantification of Two Variables
(read left to right)
xyP(x,y) or yxP(x,y)
•True when P(x,y) is true for every pair x,y.
•False if there is a pair x,y for which P(x,y) is false.
xyP(x,y) or yxP(x,y)
True if there is a pair x,y for which P(x,y) is true.
False if P(x,y) is false for every pair x,y.
Quantification of Two Variables
xyP(x,y)
•True when for every x there is a y for which P(x,y) is true.
(in this case y can depend on x)
•False if there is an x such that P(x,y) is false for every y.
yxP(x,y)
•True if there is a y for which P(x,y) is true for every x.
(i.e., true for a particular y regardless (or independent) of x)
•False if for every y there is an x for which P(x,y) is false.
Note that order matters here
In particular, if yxP(x,y) is true, then xyP(x,y) is true.
However, if xyP(x,y) is true, it is not necessary that yxP(x,y)
is true.
Basic Number Theory Definitions
from Chapters 1.6, 2
•
•
•
•
•
Z = Set of all Integers
Z+ = Set of all Positive Integers
N = Set of Natural Numbers (Z+ and Zero)
R = Set of Real Numbers
Addition and multiplication on integers
produce integers. (a,b  Z)  [(a+b)  Z] 
[(ab)  Z]
 = “such that”
Number Theory Defs (cont.)
n is even is defined as k  Z  n = 2k
n is odd is defined as k  Z  n = 2k+1
x is rational is defined as a,b  Z  x = a/b, b0
x is irrational is defined as a,b  Z  x = a/b,
b0 or a,b  Z, x  a/b, b0
• p  Z+ is prime means that the only positive
factors of p are p and 1. If p is not prime we say it
is composite.
•
•
•
•
Methods of Proof
p q (Example: if n is even, then n2 is even)
• Direct proof: Assume p is true and use a series of
previously proven statements to show that q is true.
• Indirect proof: Show q p is true (contrapositive),
using any proof technique (usually direct proof).
• Proof by contradiction: Assume negation of what you are
trying to prove (pq). Show that this leads to a
contradiction.
Direct Proof
Prove: nZ, if n is even, then n2 is even.
Tabular-style proof:
n is even
hypothesis
n=2k for some kZ
definition of even
n2 = 4k2
algebra
n2 = 2(2k2) which is
algebra and mult of
2*(an integer)
integers gives integers
n2 is even
definition of even
Same Direct Proof
Prove: nZ, if n is even, then n2 is even.
Sentence-style proof:
Assume that n is even. Thus, we know that n
= 2k for some integer k. It follows that n2
= 4k2 = 2(2k2). Therefore n2 is even since it
is 2 times 2k2, which is an integer.
Structure of a Direct Proof
Prove: nZ, if n is even, then n2 is even.
Proof:
Assume that n is even. Thus, we know that n = 2k
for some integer k. It follows that n2 = 4k2 =
2(2k2). Therefore n2 is even since it is 2 times 2k2
which is an integer.
Another example
Prove: n,mZ, if n and m are odd, then their product is
odd.
Proof:
Assume that n and m are odd. Thus, we know that n = 2k+1
for some integer k and m=2r+1 for some integer r. It
follows that nm = (2k+1)(2r+1) = 4kr+2k+2r+1 =
2(2kr+k+r)+1. Therefore nm is odd since it is 2 times
(2kr+k+r), which is an integer, plus 1.
Example of an Indirect Proof
Prove: If n3 is even, then n is even.
Proof: The contrapositive of “If n3 is even, then n is even” is “If n
is odd, then n3 is odd.” If the contrapositive is true then the
original statement must be true.
Assume n is odd. Then kZ  n = 2k+1. It follows that n3 =
(2k+1)3 = 8k3+8k2+4k+1 = 2(4k3+4k2+2k)+1. (4k3+4k2+2k) is
an integer. Therefore n3 is 1 plus an even integer. Therefore n3 is
odd.
Assumption, Definition, Arithmetic, Conclusion
Discussion of Indirect Proof
Could we do a direct proof of If n3 is even,
then n is even?
Assume n3 is even . . . then what?
We don’t have a rule about how to take n3 apart!
Example: Proof by Contradiction
Prove: The sum of an irrational number and a
rational number is irrational.
Proof: Let q be an irrational number and r be a
rational number. Assume that their sum is
rational, i.e., q+r=s where s is a rational
number. Then q = s-r. But we proved in a
previous lecture that the sum of two rational
numbers must be rational, so we have an irrational
number on the left equal to a rational number on
the right. This is a contradiction. Therefore q+r
can’t be rational and must be irrational.
Structure of Proof by Contradiction
• Basic idea is to assume that the opposite of what you are
trying to prove is true and show that it results in a
violation of one of your initial assumptions.
• In the previous proof we showed that assuming that the
sum of a rational number and an irrational number is
rational and showed that it resulted in the impossible
conclusion that a number could be rational and irrational
at the same time. (It can be put in a form that implies n 
n is true, which is a contradiction.)
Using Cases
Prove: n Z, n3 + n is even.
Separate into cases based on whether n is even or
odd. Prove each separately using direct proof.
Proof: We can divide this problem into two
cases. n can be even or n can be odd.
Case 1: n is even. Then kZ  n = 2k.
n3+n = 8k3 + 2k = 2(4k3+k) which is even since
4k3+k must be an integer.
Cases (cont.)
Case 2: n is odd. Then kZ  n = 2k+1.
n3 + n = (8k3 +12k2 + 6k + 1) + (2k + 1) =
2(4k3 + 6k2 + 4k + 1) which is even since
4k3 + 6k2 + 4k + 1 must be an integer.
Therefore n Z, n3 + n is even
Proof?
Prove if n3 is even then n is even.
Proof: Assume n3 is even.
Then kZ  n3 = 8k3 for some integer k. It follows
that n = 38k3 = 2k. Therefore n is even.
Statement is true but argument is false.
Argument assumes that n is even in making the
claim n3=8k3, rather than n3 = 2k. This is circular
reasoning.
Prove or Disprove
•
•
•
•
•
•
If m and n are even integers, then mn is divisible by 4.
The sum of two odd integers is odd.
The sum of two odd integers is even.
If n is a positive integer, then n is even iff 3n2+8 is even.
n2 + n + 1 is a prime number whenever n is a positive integer.
n2 + n + 1 is a prime number whenever n is a prime number.
• |x| + |y|  |x + y| when x,y  R.
• 3 is irrational.