Wa2-sols

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