School

University of Waterloo **We aren't endorsed by this school

Course

MATH 135

Subject

Mathematics

Date

Nov 13, 2023

Type

Other

Pages

8

Uploaded by CountWhale2493 on coursehero.com

MATH 135 Fall 2023: Solutions to Written Assignment 2 (WA2)
Due at 5 PM EDT on Friday, September 22nd, 2023
Covers the contents of Weeks 1-2
Q1.
(4 marks) Let
P
,
Q
and
R
be statement variables.
(a) Using a truth table, prove or disprove the following:
P
⇒
(
Q
⇒
R
)
≡
(
P
∧
Q
)
⇒
R
(b) Using a truth table, prove or disprove the following:
P
⇒
(
Q
⇒
R
)
≡
(
P
⇒
Q
)
⇒
R
Solution(s).
(a) As the following truth table demonstrates, the two logical expressions are logically equiva-
lent.
P
Q
R
Q
⇒
R
P
⇒
(
Q
⇒
R
)
P
∧
Q
(
P
∧
Q
)
⇒
R
T
T
T
T
T
T
T
T
T
F
F
F
T
F
T
F
T
T
T
F
T
T
F
F
T
T
F
T
F
T
T
T
T
F
T
F
T
F
F
T
F
T
F
F
T
T
T
F
T
F
F
F
T
T
F
T
(b) Notice that, if
P
is false (F),
Q
is false (F) and
R
is false (F), then the two logical expressions
have different truth values.
P
Q
R
Q
⇒
R
P
⇒
(
Q
⇒
R
)
P
⇒
Q
(
P
⇒
Q
)
⇒
R
F
F
F
T
T
T
F
Is this the only configuration when the two logical expressions have different
truth values?
Copyright 2023, University of Waterloo
Read more about Intellectual Property and Copyright

Q2.
(4 marks) In WA1Q2 you learned about two big open problems in mathematics concerning
perfect numbers. We used these problems to practice expressing mathematical statements, as
well as their negations, in symbolic form. In this question you are asked, once again, to practice
writing down mathematical statements in symbolic form.
This time though the only domain
that you are allowed to use is
N
. You are also allowed to use
s
(
n
) to denote the sum of positive
divisors of
n
that are strictly less than
n
, as well as the logical symbols '
∨
', '
∧
', '
⇒
' or '
⇔
'.
(a) (1 mark) Consider the following mathematical statement:
There are infinitely many perfect numbers.
Express this mathematical statement in symbolic form, without using words.
The only
domain that you are allowed to use is
N
.
(b) Express the negation of the statement that you provided as an answer to Part (a) in symbolic
form, without using words or the negation symbol, '
¬
'. The only domain that you are allowed
to use is
N
.
(c) (1 mark) Consider the following mathematical statement:
Every perfect number is even.
Express this mathematical statement in symbolic form, without using words.
The only
domain that you are allowed to use is
N
.
(d) (1 mark) Express the negation of the statement that you provided as the answer to Part (c)
in symbolic form, without using words or the negation symbol, '
¬
'. The only domain that
you are allowed to use is
N
.
Solution(s).
(a) The mathematical statement
There are infinitely many perfect numbers
can be expressed symbolically as
∀
n
∈
N
,
∃
t
∈
N
,
(
s
(
t
) =
t
)
∧
(
t > n
)
.
(b) The negation of the statement
There are infinitely many perfect numbers
can be determined as follows:
¬
(
∀
n
∈
N
,
∃
t
∈
N
,
(
s
(
t
) =
t
)
∧
(
t > n
))
≡ ∃
n
∈
N
,
¬
(
∃
t
∈
N
,
(
s
(
t
) =
t
)
∧
(
t > n
))
≡ ∃
n
∈
N
,
∀
t
∈
N
,
¬
((
s
(
t
) =
t
)
∧
(
t > n
))
De Morgan's Laws
→ ≡ ∃
n
∈
N
,
∀
t
∈
N
,
(
s
(
t
)
̸
=
t
)
∨
(
t
≤
n
)
.
Copyright 2023, University of Waterloo
Read more about Intellectual Property and Copyright

(c) (1 mark) We can express the mathematical statement
Every perfect number is even
in symbolic form as
∀
n
∈
N
,
(
s
(
n
) =
n
)
⇒
(
∃
k
∈
Z
,
n
= 2
k
)
.
This is also equivalent to saying that every perfect number is not odd, which can be expressed
symbolically as
∀
n
∈
N
,
(
s
(
n
) =
n
)
⇒
(
∀
k
∈
Z
,
n
̸
= 2
k
+ 1)
.
Other alternatives include
∀
n
∈
N
,
∃
k
∈
Z
,
(
s
(
n
) =
n
)
⇒
(
n
= 2
k
)
,
∀
n
∈
N
,
(
s
(
n
) =
n
)
⇒
n
2
∈
Z
,
and
∀
n
∈
N
,
(
s
(
n
) =
n
)
⇒
n
+ 1
2
/
∈
Z
.
Of course, this list is not exhaustive.
(d) Depending on which approach you took in Part (c), the negation of the mathematical
statement
Every perfect number is even
can be expressed as
¬
(
∀
n
∈
N
,
(
s
(
n
) =
n
)
⇒
(
∃
k
∈
Z
, n
= 2
k
))
≡ ∃
n
∈
N
,
¬
((
s
(
n
) =
n
)
⇒
(
∃
k
∈
Z
, n
= 2
k
))
Implication written as disjunction
→ ≡ ∃
n
∈
N
,
¬
(
¬
(
s
(
n
) =
n
)
∨
(
∃
k
∈
Z
, n
= 2
k
))
De Morgan's Laws
→ ≡ ∃
n
∈
N
,
¬
(
¬
(
s
(
n
) =
n
))
∧ ¬
(
∃
k
∈
Z
, n
= 2
k
)
Double negation
→ ≡ ∃
n
∈
N
,
(
s
(
n
) =
n
)
∧
(
∀
k
∈
Z
,
¬
(
n
= 2
k
))
≡ ∃
n
∈
N
,
(
s
(
n
) =
n
)
∧
(
∀
k
∈
Z
, n
̸
= 2
k
)
or as
¬
(
∀
n
∈
N
,
(
s
(
n
) =
n
)
⇒
(
∀
k
∈
Z
, n
̸
= 2
k
+ 1))
≡ ∃
n
∈
N
,
¬
((
s
(
n
) =
n
)
⇒
(
∀
k
∈
Z
, n
̸
= 2
k
+ 1))
Implication written as disjunction
→ ≡ ∃
n
∈
N
,
¬
(
¬
(
s
(
n
) =
n
)
∨
(
∀
k
∈
Z
, n
̸
= 2
k
+ 1))
De Morgan's Laws
→ ≡ ∃
n
∈
N
,
¬
(
¬
(
s
(
n
) =
n
))
∧ ¬
(
∀
k
∈
Z
, n
̸
= 2
k
+ 1)
Double negation
→ ≡ ∃
n
∈
N
,
(
s
(
n
) =
n
)
∧
(
∃
k
∈
Z
,
¬
(
n
̸
= 2
k
+ 1))
≡ ∃
n
∈
N
,
(
s
(
n
) =
n
)
∧
(
∃
k
∈
Z
, n
= 2
k
+ 1)
Copyright 2023, University of Waterloo
Read more about Intellectual Property and Copyright