### slides

```CSE 20
DISCRETE MATH
Prof. Shachar Lovett
http://cseweb.ucsd.edu/classes/wi15/cse20-a/
Clicker
frequency:
CA
Todays topics
• Section 3.5 in Jenkyns, Stephenson
that contains them
• Draw the truth table:
(p ∧ ¬p)  q
A.
p
q
(p ∧ ¬p)
F
F
F
F
T
F
C.
T
F
F
D.
T
T
F
E.
B.
F,F,F,F
T,T,T,T
F,T,F,T
F,F,T,T
None/more/other
that contains them
• Draw the truth table:
(p ∧ ¬p)  q
A.
p
q
(p ∧ ¬p)
F
F
F
T
F
T
F
T
C.
T
F
F
T
D.
T
T
F
T
E.
B.
F,F,F,F
T,T,T,T
F,T,F,T
F,F,T,T
None/more/other
• Here’s the scary part: it doesn’t matter what q is!
• q=“All irrational numbers are integers.”
• q=“The Beatles were a terrible band.”
• q=“Dividing by zero is totally fine!”
• All these can be “proved” true in a system that contains a
• Thm.
[write theorem]
Assume not. That is, suppose that [theorem] (Don’t just
write (theorem). For example,  changes to , use
DeMorgan’s law if needed, etc.)
“… [p] … so [p]. But [p], a contradiction”]
Conclusion: So the assumed assumption is false and
the theorem is true. QED.
Example 1
• Thm. There is no integer that is both even and odd.
• Assume not. That is, suppose that…
A. All integers are both odd and even
B. All integers are not even or not odd.
C. There is an integer n that is both odd and even.
D. There is an integer n that is neither even nor odd.
E. Other/none/more than one
• Theorem: “there is no integer that is both even and odd”
• ~∃ ∈   ∈  ∧  ∈
• ∀ ∈  ~( ∈  ∧  ∈ )
• Negation: ∃ ∈  ( ∈  ∧  ∈ )
• “There is an integer n that is both even and odd”
Example 1
• Thm. There is no integer that is both even and odd.
Assume not. That is, suppose there exists an integer n
that is both even and odd.
Try by yourself first
Example 1: proof
• Thm. There is no integer that is both even and odd.
Assume towards contradiction that there exists an integer n that
is both even and odd.
Since n is even: ∃ ∈ ,  = 2.
Since n is odd: ∃ ∈ ,  = 2 + 1.
So, 2 = 2 + 1, which gives 2  −  = 1 and  −  = 1/2,
which is impossible as a,b are integers, hence their difference is
also an integer (we are using an axiom: the integers are closed
under differentiation). We reached a contradiction.
Conclusion: There is no integer that is both even and odd.
Example 2
• A number x is rational if  = / for integers  and b ≠ 0.
• E.g. 3=3/1, 1/2, -3/4, 0=0/1
• A number is irrational if it is not rational
• E.g
2
(proved in textbook)
• Theorem: If x2 is irrational then x is irrational.
Example 2
• Theorem: If x2 is irrational then x is irrational.
Assume that
A. There exists x where both x,x2 are rational
B. There exists x where both x,x2 are irrational
C. There exists x where x is rational and x2 irrational
D. There exists x where x is irrational and x2 rational
E. None/other/more than one
Example 2
• Theorem: If x2 is irrational then x is irrational.
Assume towards contradiction that there exists x where x is
rational and x2 irrational.
Try by yourself first
Example 2: proof
• Theorem: If x2 is irrational then x is irrational.
Assume towards contradiction that there exists x where x is
rational and x2 irrational.
Since x is rational, x=a/b where a,b are integers, with b0.
Squaring both sides gives x2=a2/b2. As both a2,b2 are
integers, b20, we get that x2 is rational. This is a
contradiction to our assumption that x2 is irrational. Hence,
x must be irrational. QED
Example 3
6 is irrational
• Theorem:
THIS ONE IS MORE TRICKY.
TRY BY YOURSELF FIRST IN GROUPS.
Example 3: proof (contd)
6 is irrational
• Theorem:
We will use the following lemma (=mini theorem):
Lemma: product of odd integers is an odd integer.
Proof of Lemma:
Let x,y be odd integers. So  = 2 + 1, = 2 + 1 where
,  ∈ . Then  = 2 + 1 2 + 1 = 2 2 +  +  +
1 is an odd integer. QED (of lemma).
Example 3: proof (contd)
• Lemma: product of odd integers is an odd integer.
6 is irrational
• Theorem:

Assume towards contradiction that 6 = with ,  ∈ ,  ≠
0. We choose c,d without any common divisor.
Squaring gives  2 = 62 . First, note that c must be even,
otherwise if c is odd then (by lemma)  2 is odd, but 62 is
even. So, d must be odd (otherwise c,d both divisible by 2).
Let  = 2,  ∈  . Then 42 = 6 2 , which implies 22 =
32 . However, 22 is even but 3 2 is odd (by lemma).
We reached a contradiction. Hence 6 is irrational.
Example 4
2 + 3 is irrational
• Theorem:
Example 4: proof
2 + 3 is irrational
• Theorem:
Assume towards contradiction that 2 + 3 is rational.
So, 2 + 3 = / with ,  ∈ ,  ≠ 0.
Squaring gives
So, 6 =
1 2
2 2
2
2
=
−5 =
2+ 3
2 −52
2 2
2
=5+2 6
is rational, which we just
showed is false.
We reached a contradiction. Hence, 2 + 3 is irrational.
Next class
• Proof by induction
• Read section 3.6 in Jenkyns, Stephenson
```