Assignment 1 Logic Answers

Course: Discrete Structures Assignment 1 Answers 1st Term, 2018- 2019
Department: Computer Science & IT Instructor: Dr. Belal Al-Fuhaidi

‫ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ‬
Logic and Proofs
1- State the converse, contrapositive, and inverse of each of these conditional
statements. Then convert these statements to propositions logic?
a) If it snows today, I will ski tomorrow.
b) I come to class whenever there is going to be a quiz.
Answers:
a) One form of the converse that reads well in English is "I will ski tomorrow only if it snows today."
We could state the contrapositive as ''If I don't ski tomorrow, then it will not have snowed today."
The inverse is "If it does not snow today, then I will not ski tomorrow."
b) The proposition as stated can be rendered "If there is going to be a quiz, then I will come to class."
The converse is "If I come to class, then there will be a quiz." (Or, perhaps even better, "I come to
class only if there's going to be a quiz.")
The contrapositive is "If I don't come to class, then there won't be a quiz."
The inverse is "If there is not going to be a quiz, then I don't come to class.''
2- Use the laws in lecture notes to show that ￢(p ∨ q) ∨ (￢p ∧ q) ≡ ￢p∨￢q.
Answer: (￢p∧￢q) ∨ (￢p ∧q) = ￢p ∧ (￢q ∨q)
= ￢p ∧ T = ￢p .
3- Construct a truth table for each of these compound propositions.
a) (p ∨ q)∧￢r b) (p ↔ q) ∨ (￢q ↔ r)
Answers:
a) (p ∨ q)∧￢r )
p Q r ￢r (p ∨ q) (p∨q) ∧￢r
T T T F T F
T T F T T T
T F T F T F
T F F T T T
b) F T T F T F (p ↔ q) ∨ (￢q ↔ r)
T (p ↔ q) T (￢q ↔ r) (p ↔ q) ∨ (￢q ↔ r)
p q r ￢q
F T F T
T FT F T T FF F T F F T
T T F F T T T
T FF F T F TT F F F T T
T F F T F F F
F T T F F F F
F T F F F T T
F F T T T T T
F F F T T F T
4- Find the output of each of these combinatorial circuits.
Answers: a) Y=￢(p ∧ (q ∨ ￢r) ).

b) Y=(￢p ∧￢q) ∨( p ∧ r).
5- Construct a combinatorial circuit using inverters, OR gates, and AND gates that
produces the output (p ∧￢r) ∨ (￢q ∧ r) from input bits p, q, and r.
Answer: p
r
r
6- Use a truth table to verify the distributive law: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r).
Answer:
p q r (q ∨ r) (p ∧ q) (p ∧ r) p ∧ (q ∨ r) (p ∧ q) ∨ (p ∧ r)
T T T T T T T T
T T F T T F T T
T F T T F T T T
T F F F F F F F
F T T T F F F F
F T F T F F F F
F F T T F F F F
F F F F F F F F
7- Show that each of these conditional statements is a tautology by using truth tables.
a) [(p → q) ∧ (q → r)] → (p → r)
Answers:
a) [(p → q) ∧ (q → r)] → (p → r)=A

p q r (p → q) (q → r) (p → r) [(p → q) ∧ A
(q → r)]
T T T T T T T T
T T F T F F F T
T F T F T T F T
T F F F T F F T
F T T T T T T T
F T F T F T F T
F F T T T T T T
F F F T T T T T
[(p → q) ∧ (q → r)] → (p → r) is a tautology.
8- Show that (p → q) ∧ (p → r) and p → (q ∧ r) are logically equivalent, using truth

table and logical equivalence laws.
Answer:
p q r (p → q) (p → r) (q ∧ r) (p → q) ∧ (p → r) p → (q ∧ r)
T T T T T T T T
T T F T F F F F
T F T F T F F F
T F F F F F F F
F T T T T T T T
F T F T T F T T
F F T T T F T T
F F F T T F T T
Using Equivalent Laws:
(p → q) ∧ (p → r)= (￢p ∨q) ∧ (￢p ∨r) (using conditional equivalent )
(￢p ∨q) ∧ (￢p ∨r) = ￢p ∨(q ∧ r) (using distributive law)
￢p ∨(q ∧ r) = p → (q ∧ r) (using conditional equivalent )
9- Translate these statements into English, where C(x) is “x is a comedian” and F(x) is
“x is funny” and the domain consists of all people.
a) ∀x(C(x) → F(x)) b) ∀x(C(x) ∧ F(x))
c) ∃x(C(x) → F(x)) d) ∃x(C(x) ∧ F(x))
Answers:
a) In English, this is most simply stated, "Every comedian is funny."
b) In English, this is most simply stated, "Every person is a funny comedian."
c) In English, this might be rendered, "There exists a person such that ifs/he is a comedian,
then s/he is funny."
d) In English, this might be rendered, ''There exists a funny comedian" or "Some comedians
are funny" or "Some funny people are comedians."
10- Determine the truth value of each of these statements if the domain consists of all
integers.
a) ∀n(n + 1 > n) True b) ∃n(2n = 3n) True
c) ∃n(n = −n) True d) ∀n(3n ≤ 4n) False
11- Suppose that the domain of the propositional function P(x) consists of the integers 0,
1, 2, 3, and 4. Write out each of these propositions using disjunctions, conjunctions,
and negations.
a) ∃xP(x) b) ∀xP(x) c) ∃x￢P(x)
d) ∀x￢P(x) e) ￢∃xP(x) f ) ￢∀xP(x)
Answers:
a) ∃x P(x)=p(0) ∨ p(1) ∨ p(2) ∨ p(3) ∨ p(4).
b) ∀x P(x)= p(0) ∧ p(1) ∧ p(2) ∧ p(3) ∧ p(4).
c) ∃x ￢P(x)= ￢( p(0) ∧ p(1) ∧ p(2) ∧ p(3) ∧ p(4)).
d) ∀x ￢P(x)= ￢(p(0) ∨ p(1) ∨ p(2) ∨ p(3) ∨ p(4)).
e) ￢∃x P(x)= ￢(p(0) ∨ p(1) ∨ p(2) ∨ p(3) ∨ p(4)).
f ) ￢∀x P(x)= ￢( p(0) ∧ p(1) ∧ p(2) ∧ p(3) ∧ p(4)).
12- Translate in two ways each of these statements into logical expressions using
predicates, quantifiers, and logical connectives. First, let the domain consist of the
students in your class and second, let it consist of all people.
a) Someone in your class can speak Hindi.
b) Everyone in your class is friendly.
c) There is a person in your class who was not born in California.
d) A student in your class has been in a movie.
e) No student in your class has taken a course in logic programming.
Answers:
a) Let H ( x) be "x can speak Hindi." Then we have ∃x H ( x) the first way, or ∃x ( C ( x) /\
H ( x)) the second way.
b) Let F(x) be "x is friendly." Then we have ∀x F(x) the first way, or ∀x(C(x) →F(x)) the
second way.
c) Let B(x) be "x was born in California." Then we have ∃x-B(x) the first way,
or ∃x(C(x) /\ -B(x)) the second way.
d) Let M(x) be "x has been in a movie." Then we have ∃xM(x) the first way, or ∃x(C(x) /\
M(x)) the second way.
e) This is saying that everyone has failed to take the course. So the answer here is ∀x -L(x)
the first way, or ∀x(C(x) → -L(x)) the second way, where L(x) is "x has taken a course in
logic programming."
13- What rule of inference is used in each of these arguments?
a) Alice is a mathematics major. Therefore, Alice is either a mathematics major or a
computer science major.
b) Jerry is a mathematics major and a computer science major. Therefore, Jerry is a
mathematics major.
c) If it is rainy, then the pool will be closed. It is rainy. Therefore, the pool is closed.
d) If it snows today, the university will close. The university is not closed today.
Therefore, it did not snow today.
e) If I go swimming, then I will stay in the sun too long. If I stay in the sun too long,
then I will sunburn. Therefore, if I go swimming, then I will sunburn.
Answers:
a) This is the addition rule. We are concluding from p that p V q must be true, where p
is "Alice is mathematics major" and q is ''Alice is a computer science major."
b) This is the simplification rule. We are concluding from p A q that p must be true,
where p is "Jerry is a mathematics major" and q is "Jerry is a computer science major."
c) This is modus ponens. We are concluding from p → q and p that q must be true,
where p is "it is rainy" and q is ''the pool will be closed.''
d) This is modus tollens. We are concluding from p → q and -q that -p must be true,
where p is "it will snow today'' and q is ''the university will close today."
e) This is hypothetical syllogism. We are concluding from p → q and q → r that p → r
must be true, where p is "I will go swimming," q is ''I will stay in the sun too long," and
r is "I will sunburn."
14- Find the argument form for the following argument and determine whether it is valid.
Can we conclude that the conclusion is true if the premises are true? Use truth table.
If George does not have eight legs, then he is not a spider.
George is a spider.
‫ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ‬
∴ George has eight legs.
Answer:
￢p → ￢q , q ⊣ p = (￢p → ￢q) ∧ q →p
Let: (￢p → ￢q) ∧ q →p==A

P q ￢p ￢q ￢p → ￢q (￢p → ￢q) ∧ q A
T T F F T T T
T F F T T F T
F T T F F F T
F F T T T F T
(￢p → ￢q) ∧ q →p is tautology, then this argument is valid.
15- Test the validity of the following argument using truth table:
If I study, then I will not fail mathematics.
If I do not play basketball, then I will study.
But I failed mathematics.
‫ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ‬
Therefore I must have played basketball.
Answer:
p → ￢q , ￢r → p, q ⊣ r = (((p → ￢q) ∧ (￢r → p)) ∧ q) → r

let: (((p → ￢q) ∧ (￢r → p)) ∧ q) → r ==A
let: [(p → ￢q) ∧ (￢r → p)]==B
p q R ￢q ￢r (p →￢q) (￢r →p) B B∧q A

T T T F F F T F F T
T T F F T F T F F T
T F T T F T T T F T
T F F T T T T T F T
F T T F F T T T T T
F T F F T T F F F T
F F T T F T T T F T
F F F T T T F F T T
( [(p → ￢q) ∧ (￢r → p)] ∧ q )→ r is tautology, then this argument is valid.
16- Use rules of inference to show that the hypotheses

“Randy works hard,” “If Randy works hard, then he is a dull boy,” and “If Randy is
a dull boy, then he will not get the job” imply the conclusion “Randy will not get the
job.”
Answer:
Let w be the proposition "Randy works hard," let d be the proposition "Randy is a dull boy," and
let j be the proposition "Randy will get the job." We are given premises w, w → d, and
d → ￢j. We want to conclude ￢j. We set up the proof in two columns.
Step Reason
1. w Hypothesis
2. w→d Hypothesis
3. d Modus ponens using (2) and (3)
Hypothesis
4. d→￢j
Modus ponens using (3) and (4)
5. ￢j
17- Prove the following argument is valid using truth table: p →￢q, r → q, r ⊣ ￢p.
Answer:
p →￢q, r → q, r ⊣ ￢p = ( ((p →￢q) ∧ (r → q)) ∧ r) →￢p
p q r ￢q ￢p p →￢q r→ (p →￢q) ∧ (p →￢q) ∧ ( ((p →￢q) ∧

q (r → q) (r → q) ∧ r (r → q)) ∧ r) ￢
p
T T T F F F T F F T
T T F F F F T F F T
T F T T F T F F F T
T F F T F T T T F T
F T T F T T T T T T
F T F F T T T T F T
F F T T T T F F F T
F F F T T T T T F T
p →￢q, r → q, r ⊣ ￢p is tautology, therefore the argument is valid.

Assignment 1 Logic Answers

Uploaded by

Copyright:

Available Formats

Assignment 1 Logic Answers

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Assignment 1 Logic Answers

Uploaded by

Copyright:

Available Formats

Course: Discrete Structures Assignment 1 Answers 1st Term, 2018- 2019

Department: Computer Science & IT Instructor: Dr. Belal Al-Fuhaidi

b) I come to class whenever there is going to be a quiz.

3- Construct a truth table for each of these compound propositions.

4- Find the output of each of these combinatorial circuits.

Answers: a) Y=￢(p ∧ (q ∨ ￢r) ).

a) [(p → q) ∧ (q → r)] → (p → r)=A

[(p → q) ∧ (q → r)] → (p → r) is a tautology.

8- Show that (p → q) ∧ (p → r) and p → (q ∧ r) are logically equivalent, using truth

Let: (￢p → ￢q) ∧ q →p==A

(￢p → ￢q) ∧ q →p is tautology, then this argument is valid.

p → ￢q , ￢r → p, q ⊣ r = (((p → ￢q) ∧ (￢r → p)) ∧ q) → r

p q R ￢q ￢r (p →￢q) (￢r →p) B B∧q A

( [(p → ￢q) ∧ (￢r → p)] ∧ q )→ r is tautology, then this argument is valid.

16- Use rules of inference to show that the hypotheses

p q r ￢q ￢p p →￢q r→ (p →￢q) ∧ (p →￢q) ∧ ( ((p →￢q) ∧

p →￢q, r → q, r ⊣ ￢p is tautology, therefore the argument is valid.

You might also like