Homework #1 Solution

Section 1.3







Problem 14




Let C = {1, 2, 3, 4} and D = {a, b, c, d}. Define a function G: C → D by the following arrow diagram:







a. Write the domain and co-domain of G.




The domain of function G is set C = {1, 2, 3, 4} and the co-domain of function

G is the set D = {a, b, c, d}.




b. Find G(1), G(2), G(3), and G(4).




G(1) = c, G(2) = c, G(3) = c, and G(4) = c. Therefore, G(1) = G(2) = G(3) = G(4).







Problem 15




Let X = {2, 4, 5} and Y = {1, 2, 4, 6}. Which of the following arrow diagrams determine functions from X to Y ?

Part C






















The diagram in Part C is not a function because, 4 in the domain(X) is related to both 1 and 2 in the co-domain(Y).

Part D










The diagram in Part D is a function since, every element in the domain(X) is related to an element in the co-domain(Y). Likewise, no single element in the domain(X) is related to two different elements in the co-domain(Y);










Section 2.1







Problem 39







Imagine that num orders and num instock are particular values, such as might occur during execution of a computer program. Write a negation for the follow- ing statement.

(num orders < 50 and num instock 300) or (50 ≤ num orders < 75 and

num instock 500)




The logical form of this statement is (p ∧ q) ∨ (r ∧ s). It’s negation has the form of ∼((p ∧ q) ∨ (r ∧ s)) ≡ ∼(p ∧ q) ∧ ∼(r ∧ s) ≡ (∼p ∨ ∼q) ∧ (∼r ∨ ∼s).




Therefore, the negation of the statement is:

(num orders ≥ 50 or num instock ≤ 300) and (50 num orders ≥ 75 or

num instock ≤ 500)




Problem 42




Use a truth table to establish if the statement is a tautology or a contradiction. ((∼p ∧ q ) ∧ (q ∧ r )) ∧ ∼q

Let, T = true, F = false.










p
q
r
∼p
∼q
∼p ∧ q
q ∧ r
(∼p ∧ q) ∧ (q ∧ r)
((∼p ∧ q ) ∧ (q ∧ r )) ∧ ∼q
T

T T T F F F F
T

T F F T T F F
T

F T F T F T F
F

F F F T T T T
F

F T T F F T T
F

F F F T T F F
T

F F F T F F F
F

F F F T F F F
F

F F F F F F F






Since the truth values in the last column are all F’s (((∼p ∧ q ) ∧ (q ∧ r )) ∧

∼q) is a contradiction.







Problem 45







Determine whether the statements in (a) and (b) are logically equivalent.




a. Bob is majoring in both math and computer science, and Ann is majoring in math but Ann is not majoring in both math and computer science.




b. It is not the case that both Bob and Ann are majoring in both math and computer science, but it is the case that Ann is majoring in math and Bob is majoring in both math and computer science.




Let,




p = Bob is ma joring in both Math and Computer Science




q = Ann is ma joring in Math




r = Ann is ma joring in Math and Computer Science.




Then the sentences in (a) and (b) are symbolized as (p ∧ q) ∧ ∼r for (a) and

∼(p ∧ r) ∧ (q ∧ p) for (b).




Note: ∼(p ∧ r ) ≡ (∼p ∨ ∼r) by DeMorgan’s Laws




Let, T = true, F = false.










p
q
r
∼p
∼r
∼p ∨ ∼r
q ∧ p
(∼p ∨ ∼r) ∧ (q ∧ p)
p ∧ q
(p ∧ q) ∧ ∼r
T

T T T F F F F
T

T F F T T F F
T

F T F T F T F
F

F F F T T T T
F

T F T F T F T
F

T F T T T T T
T

T F F F F F F
F

T F F F F F F
T

T F F F F F F
F

T F F F F F F



Since the truth-table values for statement (a) and statement (b) are the same throughout the column as indicated by the bold values in the table, the two statements are logically equivalent:




((p ∧ q) ∧ ∼r) ≡ ∼(p ∧ r) ∧ (q ∧ p)







Problem 46




The symbol L was introduced to denote ”exclusive or”, so p L q ≡ (p ∨ q) ∧

∼(p ∧ q). Hence the truth table for exclusive or is as follows:




Let, T = true, F = false.







p
q
p L q
T

T F F
T

F T F
F

T T F



a. Find simpler statement forms that are logically equivalent to p L p and (p

L p) L p.




Let, T = true, F = false.







p
p L p
(p L p) L p
T

F
F

F
T

F



Using the table above, we can conclude that p L p is a contradiction since two

true values or two false values always equate to a false.
















Likewise, ((p L p) L p) ≡ p, since true-false equates to true and false-false

equates to false and those are the same truth values that p has in the table.

b. Is (p L q) L r ≡ p L (q L r)? Justify your answer. Let, T = true, F = false.







p
q
r
p L q
q L r
(p L q) L r
p L (q L r)
T

T T T F F F F
T

T F F T T F F
T

F T F T F T F
F

F T T T T F F
F

T T F F T T F
T

F F T F T T F
T

F F T F T T F









Since both columns (in bold) for the statement on each side have the same truth-table values, they are equivalent statements and therefore, (p L q) L r

≡ p L (q L r) is true.

c. Is (p L q) ∧ r ≡ (p ∧ r ) L (q ∧ r)? Justify your answer. Let, T = true, F = false.







p
q
r
p L q
p ∧ r
q ∧ r
(p L q) ∧ r
(p ∧ r) L (q ∧ r)
T

T T T F F F F
T

T F F T T F F
T

F T F T F T F
F

F T T T T F F
T

F T F F F F F
T

F F F T F F F
F

F T F T F F F
F

F T F T F F F









Since both columns (in bold) for the statement on each side have the same truth-table values, they are equivalent statements and therefore, (p L q) ∧ r

≡ (p ∧ r ) L (q ∧ r) is true.




Section 2.2







Problem 11







Construct a truth-table for the following statement: (p → (q → r)) ↔ ((p ∧ q) → r)

Let, T = true, F = false.










p
q
r
q → r
p ∧ q
p → (q → r)
(p ∧ q) → r
(p → (q → r)) ↔ ((p ∧ q) → r)
T

T T T F F F F
T

T F F T T F F
T

F T F T F T F
T

F T T T F T T
T

T F F F F F F
T

F T T T T T T
T

F T T T T T T
T

T T T T T T T






The last column which represents the final values of the entire statement has truth-table values corresponding to all true values, which is considered a tau- tology.










Section 2.3







Problem 9







Use truth tables to determine whether the argument form is valid or invalid. Indicate which columns represent the premises and which represent the con- clusion, and include a sentence explaining how the truth table supports your answer.




p ∧ q → ∼r p ∨ ∼q

∼q → p

∴ ∼r




Let, T = true, F = false.
















p
q
r
∼r
∼q
p ∧ q
(p ∧ q) → ∼r
p ∨ ∼q
∼q → p
T

T T T F F F F
T

T F F T T F F
T

F T F T F T F
F

T F T F T F T
F

F T T F F T T
T

T F F F F F F
F

T T T T T T T
T

T T T F F T T
T

T T T T T F F






The above argument is invalid due to the truth-table above.

The premises are represented by the last three columns and the critical rows, where all values are true, are labeled in bold font.

The conclusion is represented by ”∼r” and is in the fourth column. The values

part of the critical row are also in bold. However, there is a single false value that is both bold and italicized to showcase that this value is what proves that the argument is invalid.







Problem 28







Use symbols to write the logical form of each argument. If the argument is valid, identify the rule of inference that guarantees its validity. Otherwise, state whether the converse or the inverse error is made.




If there are as many rational numbers as there are irrational numbers, then the set of all irrational numbers is infinite.

The set of all irrational numbers is infinite.

∴ There are as many rational numbers as there are irrational numbers.




Let,

p = There are as many rational numbers as there are irrational numbers. q = the set of all irrational numbers is infinite.




The form of the argument is:

p → q q

∴ p




The argument is invalid since a converse error is made. This can be observed by making a truth-table:




Let, T = true, F = false.
















p
q
p → q
T

T F F
T

F T F
T

F T T






The values for the truth-table are represented above. The premises are the second and third column and the critical rows are labeled in bold font. The conclusion is ”p” and it is located in the first column. There is a single value that is false for the conclusion in the third row and that is what makes this argument invalid.







Problem 30







Use symbols to write the logical form of each argument. If the argument is valid, identify the rule of inference that guarantees its validity. Otherwise, state whether the converse or the inverse error is made.




If this computer program is correct, then it produces the correct output when run with the test data my teacher gave me.

This computer program produces the correct output when run with the test data my teacher gave me.

∴ This computer program is correct.




Let,

p = This computer program is correct.

q = This computer program produces the correct output when run with the test data my teacher gave me.




The form of the argument is:

p → q q

∴ p




Similar to the previous question, the argument is invalid since a converse error is made. This can be observed by making a truth-table:




Let, T = true, F = false.







p
q
p → q
T

T F F
T

F T F
T
F

T
T















The values for the truth-table are represented above. The premises are the second and third column and the critical rows are labeled in bold font. The conclusion is ”p” and it is located in the first column. There is a single value that is false for the conclusion in the third row and that is what makes this argument invalid.







Problem 44







A set of premises and a conclusion are given. Use the valid argument forms to deduce the conclusion from the premises, giving a reason for each step.

a. p → q

b. r ∨ s

c. ∼s → ∼t d. ∼q ∨ s

e. ∼s

f. ∼p ∧ r → u g. w ∨ t

h. ∴ u ∧ w

The correct order is given below:







1
c. ∼s → ∼t

e. ∼ s

(1) ∴ ∼t
by modus ponens
2
g. w ∨ t

(1) ∼t

(2) ∴w
by elimination
3
d. ∼q ∨ s

e. ∼s

(3) ∴ ∼q
by elimination
4
a. p → q

(3) ∼q

(4) ∴ ∼p
by modus tollens
5
b. r ∨ s

e. ∼s

(5) ∴ r
by elimination
6
(4) ∼p

(5) r

(6) ∴ ∼p ∧ r
by conjunction
7
f. ∼p ∧ r → u

(6) ∼p ∧ r

(7) ∴ u
by modus ponens
8
(7) u

(2) w

h. ∴ u ∧ w
by conjunction