MATH 250 - INTRODUCTION TO
DISCRETE MATHEMATICS - Logic
and Propositional Calculus
Question Bank - Set 1
Liberty University
Question 1
Question
Let p,q, and rbe propositional variables. Determine whether the following
statement is a tautology, a contradiction, or neither: (p→q)∧(q→r)∧(r→p).
Solution
To determine whether (p→q)∧(q→r)∧(r→p) is a tautology, a contradiction,
or neither, we can construct a truth table for the statement.
p q r p →q q →r r →p(p→q)∧(q→r)∧(r→p)
T T T T T T T
T T F T F T F
T F T F T T F
T F F F T T F
F T T T T F F
F T F T F T F
F F T T T T T
F F F T T T T
The truth table shows that the statement (p→q)∧(q→r)∧(r→p) is
only true when pand qare both false, qand rare both true, or p,q, and rare
all true. Therefore, the statement is neither a tautology nor a contradiction.
Question 2
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is equivalent to
p∧(q∨r) using logical equivalences.
Solution
To show that (p∧q)∨(p∧r) is equivalent to p∧(q∨r), we will use logical
equivalences step by step.
Step 1: Apply Distribution Law (∧over ∨) to (p∧q)∨(p∧r).
(p∧q)∨(p∧r)≡p∧(q∨r)
Therefore, (p∧q)∨(p∧r) is equivalent to p∧(q∨r) by using logical
equivalences.
Question 3
Question
Let pand qbe propositional variables. Show that the proposition (p→q)↔
(¬p∨q) is a tautology using truth tables.
Solution
To show that a proposition is a tautology, we need to show that it is true for all
possible truth values of its propositional variables.
p q ¬p¬p∨q p →q(p→q)↔(¬p∨q)
T T F T T T
T F F F F T
F T T T T T
F F T T T T
Step 1: Construct a truth table showing the truth values of p,q,¬p,
¬p∨q,p→q, and (p→q)↔(¬p∨q).
Step 2: Fill in the truth values of ¬p,¬p∨q,p→q, and (p→q)↔(¬p∨q)
based on the truth values of pand q.
Step 3: Verify that the final column in the truth table, which represents
the proposition (p→q)↔(¬p∨q), is true for all possible combinations
of truth values of pand q.
Since the final column of the truth table consists of all ”T” values, we
conclude that the proposition (p→q)↔(¬p∨q) is a tautology.
2
Question 4
Question
Let p, q, r be propositions. Prove or disprove the following inference:
(p→q)∧(q→r)⇒(p→r)
Solution
To prove or disprove the given inference, we will consider both cases.
Case 1: Assume (p→q)∧(q→r) is true, but (p→r) is false.
In this case: - If (p→q) is true, then either pis false or qis true. - If (q→r)
is true, then either qis false or ris true.
Since we are assuming (p→r) is false, this means if pis true, then rmust
be false.
Therefore, the assumption that (p→r) is false contradicts the given premises
(p→q)∧(q→r). Thus, in this case, the inference holds.
Case 2: Assume (p→r) is true, but (p→q)∧(q→r) is false.
In this case: - If (p→r) is true, then either pis false or ris true.
Since we are assuming (p→q)∧(q→r) is false, this means that either pis
true and qis false, or qis true and ris false.
However, the assumption that (p→r) is true contradicts the given premises
(p→q)∧(q→r).
Therefore, in both cases, the inference (p→q)∧(q→r)⇒(p→r) holds
true.
Question 5
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we can use
the laws of logic to simplify both expressions and show that they are the same.
Step 1: Apply distribution using the distributive law (a∧b)∨(a∧c)≡
a∧(b∨c).
(p∧q)∨(p∧r)≡p∧(q∨r)
Therefore, (p∧q)∨(p∧r) is indeed logically equivalent to p∧(q∨r).
3
Question 6
Question
Let p,q, and rbe propositional variables. Determine whether the following
argument is valid:
(p∧q)→r, p →(q∧r)⊨p→r
Solution
To determine whether the argument is valid, we will use the method of natural
deduction to show that the conclusion p→rcan be derived from the premises
(p∧q)→rand p→(q∧r).
Step 1: Assume the premise (p∧q)→rand p→(q∧r).
Step 2: Using the premise p→(q∧r), we can conclude that p→qand
p→rby the property of implication.
Step 3: From p→qand p, we can derive qusing the property of modus
ponens.
Step 4: Now, we can apply the premise (p∧q)→rto show that (p∧q)→r.
Step 5: Combining (p∧q)→rwith p∧q, we can derive rusing modus
ponens.
Step 6: Since we have shown that rfollows from p∧q, and we have previously
shown that qfollows from p, we can conclude that rfollows from p.
Step 7: Therefore, we have proved that p→rcan be derived from the
premises (p∧q)→rand p→(q∧r).
Since we have successfully derived the conclusion from the premises, the
argument is valid.
Question 7
Question
Let p,q, and rbe propositions. Show that the given statement is a tautology:
(p⇒q)∨(q⇒r)∨(r⇒p).
Solution
To show that the given statement is a tautology, we can use truth tables to
verify that the statement is true for all possible truth values of p,q, and r.
4
Step 1: Create the truth table for (p⇒q)∨(q⇒r)∨(r⇒p)
p q r p ⇒q q ⇒r r ⇒p(p⇒q)∨(q⇒r)∨(r⇒p)
T T T T T T T
T T F T F T T
T F T F T T T
T F F F T T T
F T T T T F T
F T F T F T T
F F T T T T T
F F F T T T T
Since the final column is always true (T), the given statement (p⇒q)∨(q⇒
r)∨(r⇒p) is a tautology.
Question 8
Question
Let p, q, r be propositional variables. Determine if the following argument is
valid:
Premise 1: (p∧q)→r
Premise 2: p
Conclusion: r
Solution
To determine whether the argument is valid, we will use the method of proof by
contradiction, assuming that the premises are true and the conclusion is false.
Step 1: Assume the conclusion ¬rand the premises are true.
Let’s assume that the conclusion ¬ris true, and the premises (p∧q)→r
and pare true.
Step 2: Use the premises to derive a contradiction.
From premise 2, we have p, and from premise 1, we have (p∧q)→r.
Step 3: Using Modus Ponens, we have:
(p∧q)→r
p
∴q→r
Step 4: Using Modus Ponens again, we have:
q→r
5
p
∴r
Step 5: Contradiction
We have derived rfrom our assumptions that ¬r, leading to a contradiction.
Hence, our assumption is false.
Conclusion: The argument is valid, and the conclusion rfollows logically
from the premises.
Question 9
Question
Let p,q, and rbe propositions. Show that the following statement is a tautology:
(p→q)∧(q→r)→(p→r)
Solution
To show that the given statement is a tautology, we will construct a truth table
to verify if the statement holds for all possible truth values of p,q, and r.
Step 1: Create a truth table for the given statement
p q r p →q q →r p →r(p→q)∧(q→r)→(p→r)
T T T T T T T
T T F T F F T
T F T F T T T
T F F F T F T
F T T T T T T
F T F T F T T
F F T T T T T
F F F T T T T
Step 2: Analyze the truth table
From the truth table, we can see that the statement (p→q)∧(q→r)→
(p→r) evaluates to true for all possible truth values of p,q, and r. Thus, we
have shown that the given statement is a tautology.
Question 10
Question
Let pand qbe propositions such that the compound proposition (p∧q)∨(¬p∧¬q)
is false. Determine whether the proposition ¬p∨ ¬qis true or false.
6
Solution
To determine whether the proposition ¬p∨ ¬qis true or false, we will first
analyze the truth values of the compound proposition (p∧q)∨(¬p∧ ¬q).
Step 1: Find the truth values of (p∧q)and (¬p∧ ¬q).
Since the compound proposition (p∧q)∨(¬p∧ ¬q) is false, either (p∧q) or
(¬p∧ ¬q) or both must be false.
Step 2: Determine the truth values of pand qby analyzing (p∧q)
and (¬p∧ ¬q).
If (p∧q) is false, then either pis false or qis false or both are false. Similarly,
if (¬p∧ ¬q) is false, then either ¬pis false (meaning pis true) or ¬qis false
(meaning qis true) or both are false.
We summarize the possibilities in the truth table below:
p q p ∧q¬p¬q
¬p∧ ¬q(p∧q)∨(¬p∧ ¬q)
T T T F F
F F
T F F F T
T T
F T F T F
T T
F F F T T
T F
From the truth table, we see that either pis true and qis false, or pis false
and qis true for the compound proposition (p∧q)∨(¬p∧ ¬q) to be false.
Step 3: Using the values from Step 2, determine the truth value
of ¬p∨ ¬q.
If pis true and qis false, then ¬pis false and ¬qis true. Therefore, ¬p∨ ¬q
is true.
If pis false and qis true, then both ¬pand ¬qare true. Therefore, ¬p∨ ¬q
is true.
Hence, the proposition ¬p∨ ¬qis true.
Question 11
Question
Let p,q, and rbe propositions. Prove or disprove the following statement by
either providing a truth table or a counterexample:
(p∧q)→r≡(p→r)∨(q→r)
7
Solution
We will prove the equivalence of the given statement by constructing a truth
table for both sides and comparing the truth values.
Step 1: Create a truth table for (p∧q)→rand (p→r)∨(q→r).
p q r p ∧q(p∧q)→r p →r q →r
(p→r)∨(q→r)
T T T T T T T
T
T T F T F F F
F
T F T F T T T
T
T F F F T F T
T
F T T F T T T
T
F T F F T T F
T
F F T F T T T
T
F F F F T T T
T
Step 2: Analyze the truth values of both sides. From the truth table,
we can see that both sides of the equivalence have the same truth values for all
possible truth values of p,q, and r.
Thus, we have proved that (p∧q)→r≡(p→r)∨(q→r).
Question 12
Question
Consider the following proposition:
(P→Q)∧(Q→R)∧(R→P).
Determine whether the proposition is a tautology, a contradiction, or con-
tingent. Justify your answer.
Solution
To determine whether the proposition (P→Q)∧(Q→R)∧(R→P) is a
tautology, a contradiction, or contingent, we need to analyze all possible truth
values for P,Q, and R.
Step 1: List all possible truth values We will construct a truth table
to consider all possible combinations of truth values for P,Q, and R:
8
P Q R P →Q Q →R R →P
(P→Q)∧(Q→R)∧(R→P)
T T T T T T
T
T T F T F T
F
T F T F T T
F
T F F F T T
F
F T T T T F
F
F T F T F T
F
F F T T T T
T
F F F T T T
T
Step 2: Interpret the truth values From the truth table, we can see
that the proposition (P→Q)∧(Q→R)∧(R→P) is false for some truth
value combinations (i.e., when Pis true and Qis false, or when Pis false and
Qis true).
Step 3: Conclusion Since the proposition is not true for all possible truth
values, it is neither a tautology nor a contradiction. Therefore, the proposition
is contingent.
Question 13
Question
Let p,q, and rbe propositions. Use logical equivalences to show that (p∧q)∨
(¬p∧r) is logically equivalent to (p∨r)∧(q∨r).
Solution
To prove that (p∧q)∨(¬p∧r) is logically equivalent to (p∨r)∧(q∨r), we will
apply various logical equivalences step by step.
Step 1: Apply Distribution Law: p∧(q∨r)≡(p∧q)∨(p∧r)
Step 2: Apply De Morgan’s Law: ¬p≡p→False
Step 3: Apply Distribution Law again: (p∧q)∨(p∧r)≡p∧(q∨r)
Step 4: Applying the associative law of logical OR: p∧(q∨r)≡(p∧q)∨(p∧r)
Since we have shown that both expressions are equivalent through a series of
logical equivalences, we have proved that (p∧q)∨(¬p∧r) is logically equivalent
to (p∨r)∧(q∨r).
9
Question 14
Question
Let p,q, and rbe propositions. Show that the proposition (p∧q)∨(p∧r) is
logically equivalent to p∧(q∨r) using truth tables.
Solution
To show that two propositions are logically equivalent, we need to show that
they have the same truth values for all possible truth values of their component
propositions. We will use a truth table to compare the truth values of (p∧q)∨
(p∧r) and p∧(q∨r).
Step 1: Create a truth table for (p∧q)∨(p∧r).
p q r p ∧q p ∧r(p∧q)∨(p∧r)
T T T T T T
T T F T F T
T F T F T T
T F F F F F
F T T F F F
F T F F F F
F F T F F F
F F F F F F
Step 2: Create a truth table for p∧(q∨r).
p q r q ∨r p ∧(q∨r)
T T T T T
T T F T T
T F T T T
T F F F F
F T T T F
F T F T F
F F T T F
F F F F F
Step 3: Compare the truth values of the two propositions.
From the truth tables, we can see that both propositions have the same truth
values for all possible truth values of p,q, and r. Therefore, (p∧q)∨(p∧r) is
logically equivalent to p∧(q∨r).
Question 15
Question
Let p,q, and rbe propositions such that (p→q)∧(q→r)→p. Show that
this proposition is a tautology using a truth table.
10
Solution
To show that the proposition (p→q)∧(q→r)→pis a tautology, we will
construct a truth table for all possible truth values of p,q, and r.
p q r (p→q) (q→r) (p→q)∧(q→r) (p→q)∧(q→r)→p
T T T T T T T
T T F T F F T
T F T F T F T
T F F F T F T
F T T T T T T
F T F T F F T
F F T T T T T
F F F T T T T
In the above truth table, the column (p→q)∧(q→r)→pis always
true regardless of the truth values of p,q, and r. This means that the original
proposition is a tautology.
Question 16
Question
Let pand qbe propositions. Show that the proposition (p→q)→(¬q→ ¬p)
is a tautology using a truth table.
Solution
To show that the proposition (p→q)→(¬q→ ¬p) is a tautology, we will
create a truth table to check all possible truth values of pand q.
p q ¬p¬q(p→q) (¬q→ ¬p) (p→q)→(¬q→ ¬p)
T T F F T T T
T F F T F F T
F T T F T T T
F F T T T T T
Since the final column of the truth table is always true (T), the proposition
(p→q)→(¬q→ ¬p) is a tautology.
11
Question 17
Question
Let p,q, and rbe propositions. Show that (p∨q)∧(p∨r) is logically equivalent
to p∨(q∧r).
Solution
To show that (p∨q)∧(p∨r) is logically equivalent to p∨(q∧r), we need to
show that the truth values of these two compound propositions are the same
for all possible truth values of p,q, and r.
Step 1: Construct truth tables for both compound propositions.
First, let’s construct a truth table for (p∨q)∧(p∨r):
p q r p ∨q p ∨r(p∨q)∧(p∨r)
T T T T T T
T T F T T T
T F T T T T
T F F T T T
F T T T T T
F T F T F F
F F T F T F
F F F F F F
Next, let’s construct a truth table for p∨(q∧r):
p q r q ∧r p ∨(q∧r)
T T T T T
T T F F T
T F T F T
T F F F T
F T T T T
F T F F F
F F T F F
F F F F F
Step 2: Compare the truth values of both compound propositions.
From the truth tables, we can see that the truth values of both compound
propositions are the same for all possible truth values of p,q, and r. Therefore,
we can conclude that (p∨q)∧(p∨r) is logically equivalent to p∨(q∧r).
12
Question 18
Question
Let p,q, and rbe propositions such that:
(p→q)→r
¬r→(q→ ¬p)
¬q
Determine the truth value of p.
Solution
1. We are given that ¬q. We will use this to find the truth value of q. 2. Since
¬q, then qis false. 3. By the second statement, ¬r→(q→ ¬p), and since q
is false, we can simplify this to ¬r. 4. Therefore, ris false. 5. Finally, by the
first statement (p→q)→r, we know that (p→q) implies r. Since ris false,
(p→q) must also be false. 6. Since qis false, the only way for (p→q) to be
false is for pto be true. 7. Hence, the truth value of pis true.
Question 19
Question
Let p, q, and rbe propositional variables. Show that the following statement is
a tautology:
(p∧q→r)→(p→(q→r))
Solution
To show that the given statement is a tautology, we will use a truth table to
check all possible truth values of p, q, and r.
Step 1: Create a truth table for the given statement.
p q r p ∧q p ∧q→r q →r p →(q→r)
T T T T T T T
T T F T F F T
T F T F T T T
T F F F T T T
F T T F T T T
F T F F T F T
F F T F T T T
F F F F T T T
Step 2: Analyze the truth table. From the truth table, we can see that
the last column, which represents the given statement, is true for all possible
13
truth values of p, q, and r. Since the statement is true for all possible truth
values of p, q, and r, we conclude that the statement is a tautology.
Question 20
Question
Let p,q, and rbe propositional variables with the following premises:
(p→q)∧(q→r)
¬r
Determine whether the conclusion ¬pfollows using propositional calculus
rules.
Solution
To determine if ¬pfollows from the given premises, we will construct a proof
by contradiction.
Step 1: Assume pis true.
Step 2: Use the first premise (p→q)∧(q→r) to deduce qfrom p→q.
Since pis true and (p→q) is true, it follows that qis also true.
Step 3: Use the second premise ¬rto deduce ¬qfrom q→r.
Since ris false (due to ¬r), q→ris false. Therefore, qmust also be false.
Step 4: From Steps 2 and 3, we have arrived at a contradiction: qis both
true and false.
Therefore, our assumption that pis true must be false.
Step 5: Conclude that ¬pfollows from the given premises.
Hence, the conclusion ¬pfollows using propositional calculus rules.
Question 21
Question
Let p,q, and rbe propositions such that p→(q∧r) is false. Determine the
truth values of p,q, and r.
Solution
To determine the truth values of p,q, and r, we will consider the truth table
for the implication p→(q∧r). The truth table for an implication is as follows:
p q p →q
T T T
T F F
F T T
F F T
14
Given that p→(q∧r) is false, we observe that the only way this can occur
is when pis true and q∧ris false.
Step 1: Assigning values to p,q, and rbased on the truth table
Since pmust be true and q∧rmust be false in order for p→(q∧r) to be false,
we have: - p=true -q∧r=false
Using the truth table for conjunction (∧), we find that q∧ris false only
when qand rare both false.
Step 2: Assigning values to qand rTherefore, we have: - q=false -
r=false
In conclusion, the truth values of p,q, and rare: - pis true -qis false -r
is false
Question 22
Question
Let p,q, and rbe propositions. Show that (p⇒q)∨(q⇒r) is logically
equivalent to (p∧q)⇒r.
Solution
To show that (p⇒q)∨(q⇒r) is logically equivalent to (p∧q)⇒r, we will
construct truth tables for both statements and show that they have the same
truth values for all possible truth values of p,q, and r.
Step 1: Truth table for (p⇒q)∨(q⇒r)
p q r p ⇒q q ⇒r(p⇒q)∨(q⇒r)
T T T T T T
T T F T F T
T F T F T T
T F F F T T
F T T T T T
F T F T F T
F F T T T T
F F F T T T
Step 2: Truth table for (p∧q)⇒r
p q r p ∧q(p∧q)⇒r
T T T T T
T T F T F
T F T F T
T F F F T
F T T F T
F T F F T
F F T F T
F F F F T
15
Step 3: Conclusion From the truth tables above, we can see that (p⇒
q)∨(q⇒r) and (p∧q)⇒rhave the same truth values for all possible truth
values of p,q, and r. Therefore, (p⇒q)∨(q⇒r) is logically equivalent to
(p∧q)⇒r.
Question 23
Question
Let p,q, and rbe propositional variables. Show that the following proposition
is a tautology:
(p∧q)→(p∨r)
Solution
To show that the proposition (p∧q)→(p∨r) is a tautology, we can use a truth
table to prove that the proposition is true for all possible truth values of p,q,
and r.
Step 1: Create the truth table for the proposition (p∧q)→(p∨r).
p q r p ∧q p ∨r(p∧q)→(p∨r)
T T T T T T
T T F T T T
T F T F T T
T F F F T T
F T T F T T
F T F F F T
F F T F T T
F F F F F T
Since the last column of the truth table is always true, we can conclude that
the proposition (p∧q)→(p∨r) is a tautology.
Question 24
Question
Let p,q, and rbe propositions. Show that the proposition (p∧q)∨(p∧r) is
logically equivalent to p∧(q∨r).
Solution
To show that two propositions are logically equivalent, we need to show that
they have the same truth value for all possible truth values of their component
propositions. We can do this by creating truth tables for both propositions and
checking if they are the same.
16
Step 1: Create a truth table for (p∧q)∨(p∧r).
p q r p ∧q p ∧r(p∧q)∨(p∧r)
T T T T T T
T T F T F T
T F T F T T
T F F F F F
F T T F F F
F T F F F F
F F T F F F
F F F F F F
Step 2: Create a truth table for p∧(q∨r).
p q r q ∨r p ∧(q∨r)
T T T T T
T T F T T
T F T T T
T F F F F
F T T T F
F T F T F
F F T T F
F F F F F
Step 3: Compare the two truth tables. After comparing the truth
values of both propositions, we can see that (p∧q)∨(p∧r) and p∧(q∨r)
have the same truth values for all possible combinations of p,q, and r. Hence,
(p∧q)∨(p∧r) is logically equivalent to p∧(q∨r).
Question 25
Question
Let pand qbe propositions. Show that the statement (p→q)∧(q→p) is
logically equivalent to p↔q.
Solution
To show that (p→q)∧(q→p) is logically equivalent to p↔q, we need to
show that they have the same truth values for all possible truth values of pand
q.
Step 1: Construct the truth table for (p→q)∧(q→p).
p q p →q q →p(p→q)∧(q→p)
T T T T T
T F F T F
F T T F F
F F T T T
17
Step 2: Construct the truth table for p↔q.
p q p ↔q
T T T
T F F
F T F
F F T
Step 3: Compare the truth tables for (p→q)∧(q→p) and p↔q.
From the truth tables, we observe that both (p→q)∧(q→p) and p↔q
have the same truth values for all combinations of pand q. Hence, we can
conclude that (p→q)∧(q→p) is logically equivalent to p↔q.
Question 26
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we can perform
a series of logical equivalences using the basic laws of propositional logic.
Step 1: Apply the Distributive Law
(p∧q)∨(p∧r)
=p∧(q∨r)
Step 2: Commutativity of ∨
p∧(q∨r)
=p∧(r∨q)
Step 3: Commutativity of ∧
p∧(r∨q)
= (r∨q)∧p
Step 4: Apply the Distributive Law (Reverse)
(r∨q)∧p
= (p∧r)∨(p∧q)
Therefore, (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r).
18
Question 27
Question
Let pand qbe propositions. Show that (p→q)∨(q→p) is a tautology.
Solution
To show that (p→q)∨(q→p) is a tautology, we will construct a truth table
to check all possible combinations of truth values for pand q.
p q p →q q →p(p→q)∨(q→p)
T T T T T
T F F T T
F T T F T
F F T T T
Since the final column consists of all true values, we can conclude that (p→
q)∨(q→p) is a tautology.
Question 28
Question
Let p,q, and rbe propositional variables. Determine whether the following
argument is valid:
(p∧q)⇒r, p ⇒q, ¬r
¬p
Solution
To determine the validity of the argument, we will use the method of proof by
contradiction. We will assume that the premises are true and the conclusion is
false, and then derive a contradiction.
Step 1: Assume the premises are true and the conclusion is false:
1.(p∧q)⇒r(Premise)
2. p ⇒q(Premise)
3.¬r(Premise)
4.¬p(Assumption for contradiction)
Step 2: Use premises (1) and (2) to derive r:
5. p (Assumption)
6. q (Modus Ponens on 2 and 5)
7. p ∧q(Conjunction of 5 and 6)
8. r (Modus Ponens on 1 and 7)
19
Step 3: Derive a contradiction:
9. r (From Step 8)
10.¬r(From 3)
11.False (Contradiction from 9 and 10)
Since assuming ¬pled to a contradiction, the argument is valid.
Question 29
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using propositional calculus.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we can use truth
tables.
Step 1: Create a truth table for the given proposition
p q r p →q q →r p →r(p→q)∧(q→r)→(p→r)
T T T T T T T
T T F T F F T
T F T F T T T
T F F F T F T
F T T T T T T
F T F T F T T
F F T T T T T
F F F T T T T
Step 2: Analyze the truth table Since the final column of the truth
table consists only of true values, we can conclude that the proposition (p→
q)∧(q→r)→(p→r) is a tautology.
Question 30
Question
Let p,q, and rbe propositions. Determine whether the following argument is
valid:
”If pthen q. If qthen r. Therefore, if pthen r.”
20
Solution
To determine the validity of the argument, we can use the rules of implica-
tion in propositional logic. Specifically, we will use the transitive property of
implication.
Step 1: Express the given statements as logical implications:
Statement 1: ”If pthen q” can be expressed as p→q.
Statement 2: ”If qthen r” can be expressed as q→r.
Conclusion: ”If pthen r” can be expressed as p→r.
Step 2: Apply the transitive property of implication. According to the
transitive property of implication, if p→qand q→rare true, then p→ris
also true.
Step 3: Use truth tables to check the validity of the argument:
p q r p →q q →r p →r
T T T T T T
T T F T F F
T F T F T T
T F F F T F
F T T T T T
F T F T F T
F F T T T T
F F F T T T
Step 4: Conclusion From the truth table, we see that the statement p→r
is not always true when p→qand q→rare true. Therefore, the argument is
not always valid.
Question 31
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using a truth table.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will construct a
truth table for all possible truth values of p,q, and r, and show that the final
column is always true.
21
p q r p →q q →r p →r(p→q)∧(q→r)→(p→r)
T T T T T T T
T T F T F F T
T F T F T T T
T F F F T F T
F T T T T T T
F T F T F T T
F F T T T T T
F F F T T T T
As shown in the truth table, the final column is always true regardless of
the truth values of p,q, and r. Therefore, (p→q)∧(q→r)→(p→r) is a
tautology.
Question 32
Question
Use natural deduction to prove the following statement: (p→q)∧(q→r)⊢
p→r
Solution
To prove (p→q)∧(q→r)⊢p→rusing natural deduction, we will assume
(p→q)∧(q→r) as a premise and derive p→r.
Step 1: Assume (p→q)∧(q→r) as a premise.
Step 2: Using conjunction elimination, separate the conjuncts (p→q) and
(q→r).
1.(p→q)∧(q→r) Premise
2. p →qConjunction Elimination from (1)
3. q →rConjunction Elimination from (1)
Step 3: Assume p.
Step 4: Using modus ponens with p→qand p, derive q.
4. p Assumption
5. p →qReiteration from (2)
6. q Modus Ponens from (5) and (4)
Step 5: Using modus ponens with q→rand q, derive r.
7. q Reiteration from (6)
8. q →rReiteration from (3)
9. r Modus Ponens from (8) and (7)
Step 6: Since we derived runder assumption p, we can infer p→r.
22
10. p →r(from 3, 4-9)
Therefore, we have shown that (p→q)∧(q→r)⊢p→rusing natural
deduction.
Question 33
Question
Let p,q, and rbe propositions. Show that the proposition (p→q)∧(q→r)→
(p→r) is a tautology.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will use truth
tables to verify that the compound proposition is true for all possible truth
values of p,q, and r.
p q r p →q q →r(p→q)∧(q→r)p→r(p→q)∧(q→r)→(p→r)
T T T T T T T T
T T F T F F F T
T F T F T F T T
T F F F T F F T
F T T T T T T T
F T F T F F T T
F F T T T T T T
F F F T T T T T
Since the final column of the truth table is always true, we can conclude that
the proposition (p→q)∧(q→r)→(p→r) is a tautology.
Question 34
Question
Let p, q, r be propositional variables where: p: It is sunny today. q: It is cold
today. r: It is snowing today.
Consider the proposition: If it is sunny today, then it is not cold or it is
snowing. Write this proposition in terms of p,q, and rusing logical connectives
(negation, conjunction, disjunction, implication).
23
Solution
Step 1: The given proposition can be written as follows:
p→(¬q∨r)
Therefore, the proposition ”If it is sunny today, then it is not cold or it is
snowing” can be represented in terms of p,q, and rusing the logical connectives
of negation, disjunction, and implication.
Question 35
Question
Prove or disprove the following statement: ”If it is not raining or it is not cold,
then John will go for a run.”
Solution
To prove or disprove the statement, we will analyze the given proposition in
terms of logic and propositional calculus.
Let Pdenote the proposition ”It is raining”, Qdenote the proposition ”It
is cold”, and Rdenote the proposition ”John will go for a run”.
The given statement can be written as: (¬P∨ ¬Q)→R. This can be
translated into words as ”If it is not raining or it is not cold, then John will go
for a run.”
To prove or disprove this statement, we will construct a truth table for the
given proposition and check if the implication holds in all cases.
P Q ¬P∨ ¬Q R (¬P∨ ¬Q)→R
T T F T T
T F T T T
F T T T T
F F T T T
Since the truth table shows that the implication holds in all cases, we can
conclude that the statement ”If it is not raining or it is not cold, then John will
go for a run” is true.
24
Question 2
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is equivalent to
p∧(q∨r) using logical equivalences.
Solution
To show that (p∧q)∨(p∧r) is equivalent to p∧(q∨r), we will use logical
equivalences step by step.
Step 1: Apply Distribution Law (∧over ∨) to (p∧q)∨(p∧r).
(p∧q)∨(p∧r)≡p∧(q∨r)
Therefore, (p∧q)∨(p∧r) is equivalent to p∧(q∨r) by using logical
equivalences.
Question 3
Question
Let pand qbe propositional variables. Show that the proposition (p→q)↔
(¬p∨q) is a tautology using truth tables.
Solution
To show that a proposition is a tautology, we need to show that it is true for all
possible truth values of its propositional variables.
p q ¬p¬p∨q p →q(p→q)↔(¬p∨q)
T T F T T T
T F F F F T
F T T T T T
F F T T T T
Step 1: Construct a truth table showing the truth values of p,q,¬p,
¬p∨q,p→q, and (p→q)↔(¬p∨q).
Step 2: Fill in the truth values of ¬p,¬p∨q,p→q, and (p→q)↔(¬p∨q)
based on the truth values of pand q.
Step 3: Verify that the final column in the truth table, which represents
the proposition (p→q)↔(¬p∨q), is true for all possible combinations
of truth values of pand q.
Since the final column of the truth table consists of all ”T” values, we
conclude that the proposition (p→q)↔(¬p∨q) is a tautology.
2
Question 4
Question
Let p, q, r be propositions. Prove or disprove the following inference:
(p→q)∧(q→r)⇒(p→r)
Solution
To prove or disprove the given inference, we will consider both cases.
Case 1: Assume (p→q)∧(q→r) is true, but (p→r) is false.
In this case: - If (p→q) is true, then either pis false or qis true. - If (q→r)
is true, then either qis false or ris true.
Since we are assuming (p→r) is false, this means if pis true, then rmust
be false.
Therefore, the assumption that (p→r) is false contradicts the given premises
(p→q)∧(q→r). Thus, in this case, the inference holds.
Case 2: Assume (p→r) is true, but (p→q)∧(q→r) is false.
In this case: - If (p→r) is true, then either pis false or ris true.
Since we are assuming (p→q)∧(q→r) is false, this means that either pis
true and qis false, or qis true and ris false.
However, the assumption that (p→r) is true contradicts the given premises
(p→q)∧(q→r).
Therefore, in both cases, the inference (p→q)∧(q→r)⇒(p→r) holds
true.
Question 5
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we can use
the laws of logic to simplify both expressions and show that they are the same.
Step 1: Apply distribution using the distributive law (a∧b)∨(a∧c)≡
a∧(b∨c).
(p∧q)∨(p∧r)≡p∧(q∨r)
Therefore, (p∧q)∨(p∧r) is indeed logically equivalent to p∧(q∨r).
3
Question 6
Question
Let p,q, and rbe propositional variables. Determine whether the following
argument is valid:
(p∧q)→r, p →(q∧r)⊨p→r
Solution
To determine whether the argument is valid, we will use the method of natural
deduction to show that the conclusion p→rcan be derived from the premises
(p∧q)→rand p→(q∧r).
Step 1: Assume the premise (p∧q)→rand p→(q∧r).
Step 2: Using the premise p→(q∧r), we can conclude that p→qand
p→rby the property of implication.
Step 3: From p→qand p, we can derive qusing the property of modus
ponens.
Step 4: Now, we can apply the premise (p∧q)→rto show that (p∧q)→r.
Step 5: Combining (p∧q)→rwith p∧q, we can derive rusing modus
ponens.
Step 6: Since we have shown that rfollows from p∧q, and we have previously
shown that qfollows from p, we can conclude that rfollows from p.
Step 7: Therefore, we have proved that p→rcan be derived from the
premises (p∧q)→rand p→(q∧r).
Since we have successfully derived the conclusion from the premises, the
argument is valid.
Question 7
Question
Let p,q, and rbe propositions. Show that the given statement is a tautology:
(p⇒q)∨(q⇒r)∨(r⇒p).
Solution
To show that the given statement is a tautology, we can use truth tables to
verify that the statement is true for all possible truth values of p,q, and r.
4
Step 1: Create the truth table for (p⇒q)∨(q⇒r)∨(r⇒p)
p q r p ⇒q q ⇒r r ⇒p(p⇒q)∨(q⇒r)∨(r⇒p)
T T T T T T T
T T F T F T T
T F T F T T T
T F F F T T T
F T T T T F T
F T F T F T T
F F T T T T T
F F F T T T T
Since the final column is always true (T), the given statement (p⇒q)∨(q⇒
r)∨(r⇒p) is a tautology.
Question 8
Question
Let p, q, r be propositional variables. Determine if the following argument is
valid:
Premise 1: (p∧q)→r
Premise 2: p
Conclusion: r
Solution
To determine whether the argument is valid, we will use the method of proof by
contradiction, assuming that the premises are true and the conclusion is false.
Step 1: Assume the conclusion ¬rand the premises are true.
Let’s assume that the conclusion ¬ris true, and the premises (p∧q)→r
and pare true.
Step 2: Use the premises to derive a contradiction.
From premise 2, we have p, and from premise 1, we have (p∧q)→r.
Step 3: Using Modus Ponens, we have:
(p∧q)→r
p
∴q→r
Step 4: Using Modus Ponens again, we have:
q→r
5
p
∴r
Step 5: Contradiction
We have derived rfrom our assumptions that ¬r, leading to a contradiction.
Hence, our assumption is false.
Conclusion: The argument is valid, and the conclusion rfollows logically
from the premises.
Question 9
Question
Let p,q, and rbe propositions. Show that the following statement is a tautology:
(p→q)∧(q→r)→(p→r)
Solution
To show that the given statement is a tautology, we will construct a truth table
to verify if the statement holds for all possible truth values of p,q, and r.
Step 1: Create a truth table for the given statement
p q r p →q q →r p →r(p→q)∧(q→r)→(p→r)
T T T T T T T
T T F T F F T
T F T F T T T
T F F F T F T
F T T T T T T
F T F T F T T
F F T T T T T
F F F T T T T
Step 2: Analyze the truth table
From the truth table, we can see that the statement (p→q)∧(q→r)→
(p→r) evaluates to true for all possible truth values of p,q, and r. Thus, we
have shown that the given statement is a tautology.
Question 10
Question
Let pand qbe propositions such that the compound proposition (p∧q)∨(¬p∧¬q)
is false. Determine whether the proposition ¬p∨ ¬qis true or false.
6
Solution
To determine whether the proposition ¬p∨ ¬qis true or false, we will first
analyze the truth values of the compound proposition (p∧q)∨(¬p∧ ¬q).
Step 1: Find the truth values of (p∧q)and (¬p∧ ¬q).
Since the compound proposition (p∧q)∨(¬p∧ ¬q) is false, either (p∧q) or
(¬p∧ ¬q) or both must be false.
Step 2: Determine the truth values of pand qby analyzing (p∧q)
and (¬p∧ ¬q).
If (p∧q) is false, then either pis false or qis false or both are false. Similarly,
if (¬p∧ ¬q) is false, then either ¬pis false (meaning pis true) or ¬qis false
(meaning qis true) or both are false.
We summarize the possibilities in the truth table below:
p q p ∧q¬p¬q
¬p∧ ¬q(p∧q)∨(¬p∧ ¬q)
T T T F F
F F
T F F F T
T T
F T F T F
T T
F F F T T
T F
From the truth table, we see that either pis true and qis false, or pis false
and qis true for the compound proposition (p∧q)∨(¬p∧ ¬q) to be false.
Step 3: Using the values from Step 2, determine the truth value
of ¬p∨ ¬q.
If pis true and qis false, then ¬pis false and ¬qis true. Therefore, ¬p∨ ¬q
is true.
If pis false and qis true, then both ¬pand ¬qare true. Therefore, ¬p∨ ¬q
is true.
Hence, the proposition ¬p∨ ¬qis true.
Question 11
Question
Let p,q, and rbe propositions. Prove or disprove the following statement by
either providing a truth table or a counterexample:
(p∧q)→r≡(p→r)∨(q→r)
7
Solution
We will prove the equivalence of the given statement by constructing a truth
table for both sides and comparing the truth values.
Step 1: Create a truth table for (p∧q)→rand (p→r)∨(q→r).
p q r p ∧q(p∧q)→r p →r q →r
(p→r)∨(q→r)
T T T T T T T
T
T T F T F F F
F
T F T F T T T
T
T F F F T F T
T
F T T F T T T
T
F T F F T T F
T
F F T F T T T
T
F F F F T T T
T
Step 2: Analyze the truth values of both sides. From the truth table,
we can see that both sides of the equivalence have the same truth values for all
possible truth values of p,q, and r.
Thus, we have proved that (p∧q)→r≡(p→r)∨(q→r).
Question 12
Question
Consider the following proposition:
(P→Q)∧(Q→R)∧(R→P).
Determine whether the proposition is a tautology, a contradiction, or con-
tingent. Justify your answer.
Solution
To determine whether the proposition (P→Q)∧(Q→R)∧(R→P) is a
tautology, a contradiction, or contingent, we need to analyze all possible truth
values for P,Q, and R.
Step 1: List all possible truth values We will construct a truth table
to consider all possible combinations of truth values for P,Q, and R:
8
P Q R P →Q Q →R R →P
(P→Q)∧(Q→R)∧(R→P)
T T T T T T
T
T T F T F T
F
T F T F T T
F
T F F F T T
F
F T T T T F
F
F T F T F T
F
F F T T T T
T
F F F T T T
T
Step 2: Interpret the truth values From the truth table, we can see
that the proposition (P→Q)∧(Q→R)∧(R→P) is false for some truth
value combinations (i.e., when Pis true and Qis false, or when Pis false and
Qis true).
Step 3: Conclusion Since the proposition is not true for all possible truth
values, it is neither a tautology nor a contradiction. Therefore, the proposition
is contingent.
Question 13
Question
Let p,q, and rbe propositions. Use logical equivalences to show that (p∧q)∨
(¬p∧r) is logically equivalent to (p∨r)∧(q∨r).
Solution
To prove that (p∧q)∨(¬p∧r) is logically equivalent to (p∨r)∧(q∨r), we will
apply various logical equivalences step by step.
Step 1: Apply Distribution Law: p∧(q∨r)≡(p∧q)∨(p∧r)
Step 2: Apply De Morgan’s Law: ¬p≡p→False
Step 3: Apply Distribution Law again: (p∧q)∨(p∧r)≡p∧(q∨r)
Step 4: Applying the associative law of logical OR: p∧(q∨r)≡(p∧q)∨(p∧r)
Since we have shown that both expressions are equivalent through a series of
logical equivalences, we have proved that (p∧q)∨(¬p∧r) is logically equivalent
to (p∨r)∧(q∨r).
9
Question 14
Question
Let p,q, and rbe propositions. Show that the proposition (p∧q)∨(p∧r) is
logically equivalent to p∧(q∨r) using truth tables.
Solution
To show that two propositions are logically equivalent, we need to show that
they have the same truth values for all possible truth values of their component
propositions. We will use a truth table to compare the truth values of (p∧q)∨
(p∧r) and p∧(q∨r).
Step 1: Create a truth table for (p∧q)∨(p∧r).
p q r p ∧q p ∧r(p∧q)∨(p∧r)
T T T T T T
T T F T F T
T F T F T T
T F F F F F
F T T F F F
F T F F F F
F F T F F F
F F F F F F
Step 2: Create a truth table for p∧(q∨r).
p q r q ∨r p ∧(q∨r)
T T T T T
T T F T T
T F T T T
T F F F F
F T T T F
F T F T F
F F T T F
F F F F F
Step 3: Compare the truth values of the two propositions.
From the truth tables, we can see that both propositions have the same truth
values for all possible truth values of p,q, and r. Therefore, (p∧q)∨(p∧r) is
logically equivalent to p∧(q∨r).
Question 15
Question
Let p,q, and rbe propositions such that (p→q)∧(q→r)→p. Show that
this proposition is a tautology using a truth table.
10
Solution
To show that the proposition (p→q)∧(q→r)→pis a tautology, we will
construct a truth table for all possible truth values of p,q, and r.
p q r (p→q) (q→r) (p→q)∧(q→r) (p→q)∧(q→r)→p
T T T T T T T
T T F T F F T
T F T F T F T
T F F F T F T
F T T T T T T
F T F T F F T
F F T T T T T
F F F T T T T
In the above truth table, the column (p→q)∧(q→r)→pis always
true regardless of the truth values of p,q, and r. This means that the original
proposition is a tautology.
Question 16
Question
Let pand qbe propositions. Show that the proposition (p→q)→(¬q→ ¬p)
is a tautology using a truth table.
Solution
To show that the proposition (p→q)→(¬q→ ¬p) is a tautology, we will
create a truth table to check all possible truth values of pand q.
p q ¬p¬q(p→q) (¬q→ ¬p) (p→q)→(¬q→ ¬p)
T T F F T T T
T F F T F F T
F T T F T T T
F F T T T T T
Since the final column of the truth table is always true (T), the proposition
(p→q)→(¬q→ ¬p) is a tautology.
11
Question 17
Question
Let p,q, and rbe propositions. Show that (p∨q)∧(p∨r) is logically equivalent
to p∨(q∧r).
Solution
To show that (p∨q)∧(p∨r) is logically equivalent to p∨(q∧r), we need to
show that the truth values of these two compound propositions are the same
for all possible truth values of p,q, and r.
Step 1: Construct truth tables for both compound propositions.
First, let’s construct a truth table for (p∨q)∧(p∨r):
p q r p ∨q p ∨r(p∨q)∧(p∨r)
T T T T T T
T T F T T T
T F T T T T
T F F T T T
F T T T T T
F T F T F F
F F T F T F
F F F F F F
Next, let’s construct a truth table for p∨(q∧r):
p q r q ∧r p ∨(q∧r)
T T T T T
T T F F T
T F T F T
T F F F T
F T T T T
F T F F F
F F T F F
F F F F F
Step 2: Compare the truth values of both compound propositions.
From the truth tables, we can see that the truth values of both compound
propositions are the same for all possible truth values of p,q, and r. Therefore,
we can conclude that (p∨q)∧(p∨r) is logically equivalent to p∨(q∧r).
12
Question 18
Question
Let p,q, and rbe propositions such that:
(p→q)→r
¬r→(q→ ¬p)
¬q
Determine the truth value of p.
Solution
1. We are given that ¬q. We will use this to find the truth value of q. 2. Since
¬q, then qis false. 3. By the second statement, ¬r→(q→ ¬p), and since q
is false, we can simplify this to ¬r. 4. Therefore, ris false. 5. Finally, by the
first statement (p→q)→r, we know that (p→q) implies r. Since ris false,
(p→q) must also be false. 6. Since qis false, the only way for (p→q) to be
false is for pto be true. 7. Hence, the truth value of pis true.
Question 19
Question
Let p, q, and rbe propositional variables. Show that the following statement is
a tautology:
(p∧q→r)→(p→(q→r))
Solution
To show that the given statement is a tautology, we will use a truth table to
check all possible truth values of p, q, and r.
Step 1: Create a truth table for the given statement.
p q r p ∧q p ∧q→r q →r p →(q→r)
T T T T T T T
T T F T F F T
T F T F T T T
T F F F T T T
F T T F T T T
F T F F T F T
F F T F T T T
F F F F T T T
Step 2: Analyze the truth table. From the truth table, we can see that
the last column, which represents the given statement, is true for all possible
13
truth values of p, q, and r. Since the statement is true for all possible truth
values of p, q, and r, we conclude that the statement is a tautology.
Question 20
Question
Let p,q, and rbe propositional variables with the following premises:
(p→q)∧(q→r)
¬r
Determine whether the conclusion ¬pfollows using propositional calculus
rules.
Solution
To determine if ¬pfollows from the given premises, we will construct a proof
by contradiction.
Step 1: Assume pis true.
Step 2: Use the first premise (p→q)∧(q→r) to deduce qfrom p→q.
Since pis true and (p→q) is true, it follows that qis also true.
Step 3: Use the second premise ¬rto deduce ¬qfrom q→r.
Since ris false (due to ¬r), q→ris false. Therefore, qmust also be false.
Step 4: From Steps 2 and 3, we have arrived at a contradiction: qis both
true and false.
Therefore, our assumption that pis true must be false.
Step 5: Conclude that ¬pfollows from the given premises.
Hence, the conclusion ¬pfollows using propositional calculus rules.
Question 21
Question
Let p,q, and rbe propositions such that p→(q∧r) is false. Determine the
truth values of p,q, and r.
Solution
To determine the truth values of p,q, and r, we will consider the truth table
for the implication p→(q∧r). The truth table for an implication is as follows:
p q p →q
T T T
T F F
F T T
F F T
14
Given that p→(q∧r) is false, we observe that the only way this can occur
is when pis true and q∧ris false.
Step 1: Assigning values to p,q, and rbased on the truth table
Since pmust be true and q∧rmust be false in order for p→(q∧r) to be false,
we have: - p=true -q∧r=false
Using the truth table for conjunction (∧), we find that q∧ris false only
when qand rare both false.
Step 2: Assigning values to qand rTherefore, we have: - q=false -
r=false
In conclusion, the truth values of p,q, and rare: - pis true -qis false -r
is false
Question 22
Question
Let p,q, and rbe propositions. Show that (p⇒q)∨(q⇒r) is logically
equivalent to (p∧q)⇒r.
Solution
To show that (p⇒q)∨(q⇒r) is logically equivalent to (p∧q)⇒r, we will
construct truth tables for both statements and show that they have the same
truth values for all possible truth values of p,q, and r.
Step 1: Truth table for (p⇒q)∨(q⇒r)
p q r p ⇒q q ⇒r(p⇒q)∨(q⇒r)
T T T T T T
T T F T F T
T F T F T T
T F F F T T
F T T T T T
F T F T F T
F F T T T T
F F F T T T
Step 2: Truth table for (p∧q)⇒r
p q r p ∧q(p∧q)⇒r
T T T T T
T T F T F
T F T F T
T F F F T
F T T F T
F T F F T
F F T F T
F F F F T
15
Step 3: Conclusion From the truth tables above, we can see that (p⇒
q)∨(q⇒r) and (p∧q)⇒rhave the same truth values for all possible truth
values of p,q, and r. Therefore, (p⇒q)∨(q⇒r) is logically equivalent to
(p∧q)⇒r.
Question 23
Question
Let p,q, and rbe propositional variables. Show that the following proposition
is a tautology:
(p∧q)→(p∨r)
Solution
To show that the proposition (p∧q)→(p∨r) is a tautology, we can use a truth
table to prove that the proposition is true for all possible truth values of p,q,
and r.
Step 1: Create the truth table for the proposition (p∧q)→(p∨r).
p q r p ∧q p ∨r(p∧q)→(p∨r)
T T T T T T
T T F T T T
T F T F T T
T F F F T T
F T T F T T
F T F F F T
F F T F T T
F F F F F T
Since the last column of the truth table is always true, we can conclude that
the proposition (p∧q)→(p∨r) is a tautology.
Question 24
Question
Let p,q, and rbe propositions. Show that the proposition (p∧q)∨(p∧r) is
logically equivalent to p∧(q∨r).
Solution
To show that two propositions are logically equivalent, we need to show that
they have the same truth value for all possible truth values of their component
propositions. We can do this by creating truth tables for both propositions and
checking if they are the same.
16
Step 1: Create a truth table for (p∧q)∨(p∧r).
p q r p ∧q p ∧r(p∧q)∨(p∧r)
T T T T T T
T T F T F T
T F T F T T
T F F F F F
F T T F F F
F T F F F F
F F T F F F
F F F F F F
Step 2: Create a truth table for p∧(q∨r).
p q r q ∨r p ∧(q∨r)
T T T T T
T T F T T
T F T T T
T F F F F
F T T T F
F T F T F
F F T T F
F F F F F
Step 3: Compare the two truth tables. After comparing the truth
values of both propositions, we can see that (p∧q)∨(p∧r) and p∧(q∨r)
have the same truth values for all possible combinations of p,q, and r. Hence,
(p∧q)∨(p∧r) is logically equivalent to p∧(q∨r).
Question 25
Question
Let pand qbe propositions. Show that the statement (p→q)∧(q→p) is
logically equivalent to p↔q.
Solution
To show that (p→q)∧(q→p) is logically equivalent to p↔q, we need to
show that they have the same truth values for all possible truth values of pand
q.
Step 1: Construct the truth table for (p→q)∧(q→p).
p q p →q q →p(p→q)∧(q→p)
T T T T T
T F F T F
F T T F F
F F T T T
17
Step 2: Construct the truth table for p↔q.
p q p ↔q
T T T
T F F
F T F
F F T
Step 3: Compare the truth tables for (p→q)∧(q→p) and p↔q.
From the truth tables, we observe that both (p→q)∧(q→p) and p↔q
have the same truth values for all combinations of pand q. Hence, we can
conclude that (p→q)∧(q→p) is logically equivalent to p↔q.
Question 26
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we can perform
a series of logical equivalences using the basic laws of propositional logic.
Step 1: Apply the Distributive Law
(p∧q)∨(p∧r)
=p∧(q∨r)
Step 2: Commutativity of ∨
p∧(q∨r)
=p∧(r∨q)
Step 3: Commutativity of ∧
p∧(r∨q)
= (r∨q)∧p
Step 4: Apply the Distributive Law (Reverse)
(r∨q)∧p
= (p∧r)∨(p∧q)
Therefore, (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r).
18
Question 27
Question
Let pand qbe propositions. Show that (p→q)∨(q→p) is a tautology.
Solution
To show that (p→q)∨(q→p) is a tautology, we will construct a truth table
to check all possible combinations of truth values for pand q.
p q p →q q →p(p→q)∨(q→p)
T T T T T
T F F T T
F T T F T
F F T T T
Since the final column consists of all true values, we can conclude that (p→
q)∨(q→p) is a tautology.
Question 28
Question
Let p,q, and rbe propositional variables. Determine whether the following
argument is valid:
(p∧q)⇒r, p ⇒q, ¬r
¬p
Solution
To determine the validity of the argument, we will use the method of proof by
contradiction. We will assume that the premises are true and the conclusion is
false, and then derive a contradiction.
Step 1: Assume the premises are true and the conclusion is false:
1.(p∧q)⇒r(Premise)
2. p ⇒q(Premise)
3.¬r(Premise)
4.¬p(Assumption for contradiction)
Step 2: Use premises (1) and (2) to derive r:
5. p (Assumption)
6. q (Modus Ponens on 2 and 5)
7. p ∧q(Conjunction of 5 and 6)
8. r (Modus Ponens on 1 and 7)
19
Step 3: Derive a contradiction:
9. r (From Step 8)
10.¬r(From 3)
11.False (Contradiction from 9 and 10)
Since assuming ¬pled to a contradiction, the argument is valid.
Question 29
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using propositional calculus.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we can use truth
tables.
Step 1: Create a truth table for the given proposition
p q r p →q q →r p →r(p→q)∧(q→r)→(p→r)
T T T T T T T
T T F T F F T
T F T F T T T
T F F F T F T
F T T T T T T
F T F T F T T
F F T T T T T
F F F T T T T
Step 2: Analyze the truth table Since the final column of the truth
table consists only of true values, we can conclude that the proposition (p→
q)∧(q→r)→(p→r) is a tautology.
Question 30
Question
Let p,q, and rbe propositions. Determine whether the following argument is
valid:
”If pthen q. If qthen r. Therefore, if pthen r.”
20
Solution
To determine the validity of the argument, we can use the rules of implica-
tion in propositional logic. Specifically, we will use the transitive property of
implication.
Step 1: Express the given statements as logical implications:
Statement 1: ”If pthen q” can be expressed as p→q.
Statement 2: ”If qthen r” can be expressed as q→r.
Conclusion: ”If pthen r” can be expressed as p→r.
Step 2: Apply the transitive property of implication. According to the
transitive property of implication, if p→qand q→rare true, then p→ris
also true.
Step 3: Use truth tables to check the validity of the argument:
p q r p →q q →r p →r
T T T T T T
T T F T F F
T F T F T T
T F F F T F
F T T T T T
F T F T F T
F F T T T T
F F F T T T
Step 4: Conclusion From the truth table, we see that the statement p→r
is not always true when p→qand q→rare true. Therefore, the argument is
not always valid.
Question 31
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using a truth table.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will construct a
truth table for all possible truth values of p,q, and r, and show that the final
column is always true.
21
p q r p →q q →r p →r(p→q)∧(q→r)→(p→r)
T T T T T T T
T T F T F F T
T F T F T T T
T F F F T F T
F T T T T T T
F T F T F T T
F F T T T T T
F F F T T T T
As shown in the truth table, the final column is always true regardless of
the truth values of p,q, and r. Therefore, (p→q)∧(q→r)→(p→r) is a
tautology.
Question 32
Question
Use natural deduction to prove the following statement: (p→q)∧(q→r)⊢
p→r
Solution
To prove (p→q)∧(q→r)⊢p→rusing natural deduction, we will assume
(p→q)∧(q→r) as a premise and derive p→r.
Step 1: Assume (p→q)∧(q→r) as a premise.
Step 2: Using conjunction elimination, separate the conjuncts (p→q) and
(q→r).
1.(p→q)∧(q→r) Premise
2. p →qConjunction Elimination from (1)
3. q →rConjunction Elimination from (1)
Step 3: Assume p.
Step 4: Using modus ponens with p→qand p, derive q.
4. p Assumption
5. p →qReiteration from (2)
6. q Modus Ponens from (5) and (4)
Step 5: Using modus ponens with q→rand q, derive r.
7. q Reiteration from (6)
8. q →rReiteration from (3)
9. r Modus Ponens from (8) and (7)
Step 6: Since we derived runder assumption p, we can infer p→r.
22
10. p →r(from 3, 4-9)
Therefore, we have shown that (p→q)∧(q→r)⊢p→rusing natural
deduction.
Question 33
Question
Let p,q, and rbe propositions. Show that the proposition (p→q)∧(q→r)→
(p→r) is a tautology.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will use truth
tables to verify that the compound proposition is true for all possible truth
values of p,q, and r.
p q r p →q q →r(p→q)∧(q→r)p→r(p→q)∧(q→r)→(p→r)
T T T T T T T T
T T F T F F F T
T F T F T F T T
T F F F T F F T
F T T T T T T T
F T F T F F T T
F F T T T T T T
F F F T T T T T
Since the final column of the truth table is always true, we can conclude that
the proposition (p→q)∧(q→r)→(p→r) is a tautology.
Question 34
Question
Let p, q, r be propositional variables where: p: It is sunny today. q: It is cold
today. r: It is snowing today.
Consider the proposition: If it is sunny today, then it is not cold or it is
snowing. Write this proposition in terms of p,q, and rusing logical connectives
(negation, conjunction, disjunction, implication).
23
Solution
Step 1: The given proposition can be written as follows:
p→(¬q∨r)
Therefore, the proposition ”If it is sunny today, then it is not cold or it is
snowing” can be represented in terms of p,q, and rusing the logical connectives
of negation, disjunction, and implication.
Question 35
Question
Prove or disprove the following statement: ”If it is not raining or it is not cold,
then John will go for a run.”
Solution
To prove or disprove the statement, we will analyze the given proposition in
terms of logic and propositional calculus.
Let Pdenote the proposition ”It is raining”, Qdenote the proposition ”It
is cold”, and Rdenote the proposition ”John will go for a run”.
The given statement can be written as: (¬P∨ ¬Q)→R. This can be
translated into words as ”If it is not raining or it is not cold, then John will go
for a run.”
To prove or disprove this statement, we will construct a truth table for the
given proposition and check if the implication holds in all cases.
P Q ¬P∨ ¬Q R (¬P∨ ¬Q)→R
T T F T T
T F T T T
F T T T T
F F T T T
Since the truth table shows that the implication holds in all cases, we can
conclude that the statement ”If it is not raining or it is not cold, then John will
go for a run” is true.
24
Question 2
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is equivalent to
p∧(q∨r) using logical equivalences.
Solution
To show that (p∧q)∨(p∧r) is equivalent to p∧(q∨r), we will use logical
equivalences step by step.
Step 1: Apply Distribution Law (∧over ∨) to (p∧q)∨(p∧r).
(p∧q)∨(p∧r)≡p∧(q∨r)
Therefore, (p∧q)∨(p∧r) is equivalent to p∧(q∨r) by using logical
equivalences.
Question 3
Question
Let pand qbe propositional variables. Show that the proposition (p→q)↔
(¬p∨q) is a tautology using truth tables.
Solution
To show that a proposition is a tautology, we need to show that it is true for all
possible truth values of its propositional variables.
p q ¬p¬p∨q p →q(p→q)↔(¬p∨q)
T T F T T T
T F F F F T
F T T T T T
F F T T T T
Step 1: Construct a truth table showing the truth values of p,q,¬p,
¬p∨q,p→q, and (p→q)↔(¬p∨q).
Step 2: Fill in the truth values of ¬p,¬p∨q,p→q, and (p→q)↔(¬p∨q)
based on the truth values of pand q.
Step 3: Verify that the final column in the truth table, which represents
the proposition (p→q)↔(¬p∨q), is true for all possible combinations
of truth values of pand q.
Since the final column of the truth table consists of all ”T” values, we
conclude that the proposition (p→q)↔(¬p∨q) is a tautology.
2
Question 4
Question
Let p, q, r be propositions. Prove or disprove the following inference:
(p→q)∧(q→r)⇒(p→r)
Solution
To prove or disprove the given inference, we will consider both cases.
Case 1: Assume (p→q)∧(q→r) is true, but (p→r) is false.
In this case: - If (p→q) is true, then either pis false or qis true. - If (q→r)
is true, then either qis false or ris true.
Since we are assuming (p→r) is false, this means if pis true, then rmust
be false.
Therefore, the assumption that (p→r) is false contradicts the given premises
(p→q)∧(q→r). Thus, in this case, the inference holds.
Case 2: Assume (p→r) is true, but (p→q)∧(q→r) is false.
In this case: - If (p→r) is true, then either pis false or ris true.
Since we are assuming (p→q)∧(q→r) is false, this means that either pis
true and qis false, or qis true and ris false.
However, the assumption that (p→r) is true contradicts the given premises
(p→q)∧(q→r).
Therefore, in both cases, the inference (p→q)∧(q→r)⇒(p→r) holds
true.
Question 5
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we can use
the laws of logic to simplify both expressions and show that they are the same.
Step 1: Apply distribution using the distributive law (a∧b)∨(a∧c)≡
a∧(b∨c).
(p∧q)∨(p∧r)≡p∧(q∨r)
Therefore, (p∧q)∨(p∧r) is indeed logically equivalent to p∧(q∨r).
3
Question 6
Question
Let p,q, and rbe propositional variables. Determine whether the following
argument is valid:
(p∧q)→r, p →(q∧r)⊨p→r
Solution
To determine whether the argument is valid, we will use the method of natural
deduction to show that the conclusion p→rcan be derived from the premises
(p∧q)→rand p→(q∧r).
Step 1: Assume the premise (p∧q)→rand p→(q∧r).
Step 2: Using the premise p→(q∧r), we can conclude that p→qand
p→rby the property of implication.
Step 3: From p→qand p, we can derive qusing the property of modus
ponens.
Step 4: Now, we can apply the premise (p∧q)→rto show that (p∧q)→r.
Step 5: Combining (p∧q)→rwith p∧q, we can derive rusing modus
ponens.
Step 6: Since we have shown that rfollows from p∧q, and we have previously
shown that qfollows from p, we can conclude that rfollows from p.
Step 7: Therefore, we have proved that p→rcan be derived from the
premises (p∧q)→rand p→(q∧r).
Since we have successfully derived the conclusion from the premises, the
argument is valid.
Question 7
Question
Let p,q, and rbe propositions. Show that the given statement is a tautology:
(p⇒q)∨(q⇒r)∨(r⇒p).
Solution
To show that the given statement is a tautology, we can use truth tables to
verify that the statement is true for all possible truth values of p,q, and r.
4
Step 1: Create the truth table for (p⇒q)∨(q⇒r)∨(r⇒p)
p q r p ⇒q q ⇒r r ⇒p(p⇒q)∨(q⇒r)∨(r⇒p)
T T T T T T T
T T F T F T T
T F T F T T T
T F F F T T T
F T T T T F T
F T F T F T T
F F T T T T T
F F F T T T T
Since the final column is always true (T), the given statement (p⇒q)∨(q⇒
r)∨(r⇒p) is a tautology.
Question 8
Question
Let p, q, r be propositional variables. Determine if the following argument is
valid:
Premise 1: (p∧q)→r
Premise 2: p
Conclusion: r
Solution
To determine whether the argument is valid, we will use the method of proof by
contradiction, assuming that the premises are true and the conclusion is false.
Step 1: Assume the conclusion ¬rand the premises are true.
Let’s assume that the conclusion ¬ris true, and the premises (p∧q)→r
and pare true.
Step 2: Use the premises to derive a contradiction.
From premise 2, we have p, and from premise 1, we have (p∧q)→r.
Step 3: Using Modus Ponens, we have:
(p∧q)→r
p
∴q→r
Step 4: Using Modus Ponens again, we have:
q→r
5
p
∴r
Step 5: Contradiction
We have derived rfrom our assumptions that ¬r, leading to a contradiction.
Hence, our assumption is false.
Conclusion: The argument is valid, and the conclusion rfollows logically
from the premises.
Question 9
Question
Let p,q, and rbe propositions. Show that the following statement is a tautology:
(p→q)∧(q→r)→(p→r)
Solution
To show that the given statement is a tautology, we will construct a truth table
to verify if the statement holds for all possible truth values of p,q, and r.
Step 1: Create a truth table for the given statement
p q r p →q q →r p →r(p→q)∧(q→r)→(p→r)
T T T T T T T
T T F T F F T
T F T F T T T
T F F F T F T
F T T T T T T
F T F T F T T
F F T T T T T
F F F T T T T
Step 2: Analyze the truth table
From the truth table, we can see that the statement (p→q)∧(q→r)→
(p→r) evaluates to true for all possible truth values of p,q, and r. Thus, we
have shown that the given statement is a tautology.
Question 10
Question
Let pand qbe propositions such that the compound proposition (p∧q)∨(¬p∧¬q)
is false. Determine whether the proposition ¬p∨ ¬qis true or false.
6
Solution
To determine whether the proposition ¬p∨ ¬qis true or false, we will first
analyze the truth values of the compound proposition (p∧q)∨(¬p∧ ¬q).
Step 1: Find the truth values of (p∧q)and (¬p∧ ¬q).
Since the compound proposition (p∧q)∨(¬p∧ ¬q) is false, either (p∧q) or
(¬p∧ ¬q) or both must be false.
Step 2: Determine the truth values of pand qby analyzing (p∧q)
and (¬p∧ ¬q).
If (p∧q) is false, then either pis false or qis false or both are false. Similarly,
if (¬p∧ ¬q) is false, then either ¬pis false (meaning pis true) or ¬qis false
(meaning qis true) or both are false.
We summarize the possibilities in the truth table below:
p q p ∧q¬p¬q
¬p∧ ¬q(p∧q)∨(¬p∧ ¬q)
T T T F F
F F
T F F F T
T T
F T F T F
T T
F F F T T
T F
From the truth table, we see that either pis true and qis false, or pis false
and qis true for the compound proposition (p∧q)∨(¬p∧ ¬q) to be false.
Step 3: Using the values from Step 2, determine the truth value
of ¬p∨ ¬q.
If pis true and qis false, then ¬pis false and ¬qis true. Therefore, ¬p∨ ¬q
is true.
If pis false and qis true, then both ¬pand ¬qare true. Therefore, ¬p∨ ¬q
is true.
Hence, the proposition ¬p∨ ¬qis true.
Question 11
Question
Let p,q, and rbe propositions. Prove or disprove the following statement by
either providing a truth table or a counterexample:
(p∧q)→r≡(p→r)∨(q→r)
7
Solution
We will prove the equivalence of the given statement by constructing a truth
table for both sides and comparing the truth values.
Step 1: Create a truth table for (p∧q)→rand (p→r)∨(q→r).
p q r p ∧q(p∧q)→r p →r q →r
(p→r)∨(q→r)
T T T T T T T
T
T T F T F F F
F
T F T F T T T
T
T F F F T F T
T
F T T F T T T
T
F T F F T T F
T
F F T F T T T
T
F F F F T T T
T
Step 2: Analyze the truth values of both sides. From the truth table,
we can see that both sides of the equivalence have the same truth values for all
possible truth values of p,q, and r.
Thus, we have proved that (p∧q)→r≡(p→r)∨(q→r).
Question 12
Question
Consider the following proposition:
(P→Q)∧(Q→R)∧(R→P).
Determine whether the proposition is a tautology, a contradiction, or con-
tingent. Justify your answer.
Solution
To determine whether the proposition (P→Q)∧(Q→R)∧(R→P) is a
tautology, a contradiction, or contingent, we need to analyze all possible truth
values for P,Q, and R.
Step 1: List all possible truth values We will construct a truth table
to consider all possible combinations of truth values for P,Q, and R:
8
P Q R P →Q Q →R R →P
(P→Q)∧(Q→R)∧(R→P)
T T T T T T
T
T T F T F T
F
T F T F T T
F
T F F F T T
F
F T T T T F
F
F T F T F T
F
F F T T T T
T
F F F T T T
T
Step 2: Interpret the truth values From the truth table, we can see
that the proposition (P→Q)∧(Q→R)∧(R→P) is false for some truth
value combinations (i.e., when Pis true and Qis false, or when Pis false and
Qis true).
Step 3: Conclusion Since the proposition is not true for all possible truth
values, it is neither a tautology nor a contradiction. Therefore, the proposition
is contingent.
Question 13
Question
Let p,q, and rbe propositions. Use logical equivalences to show that (p∧q)∨
(¬p∧r) is logically equivalent to (p∨r)∧(q∨r).
Solution
To prove that (p∧q)∨(¬p∧r) is logically equivalent to (p∨r)∧(q∨r), we will
apply various logical equivalences step by step.
Step 1: Apply Distribution Law: p∧(q∨r)≡(p∧q)∨(p∧r)
Step 2: Apply De Morgan’s Law: ¬p≡p→False
Step 3: Apply Distribution Law again: (p∧q)∨(p∧r)≡p∧(q∨r)
Step 4: Applying the associative law of logical OR: p∧(q∨r)≡(p∧q)∨(p∧r)
Since we have shown that both expressions are equivalent through a series of
logical equivalences, we have proved that (p∧q)∨(¬p∧r) is logically equivalent
to (p∨r)∧(q∨r).
9
Question 14
Question
Let p,q, and rbe propositions. Show that the proposition (p∧q)∨(p∧r) is
logically equivalent to p∧(q∨r) using truth tables.
Solution
To show that two propositions are logically equivalent, we need to show that
they have the same truth values for all possible truth values of their component
propositions. We will use a truth table to compare the truth values of (p∧q)∨
(p∧r) and p∧(q∨r).
Step 1: Create a truth table for (p∧q)∨(p∧r).
p q r p ∧q p ∧r(p∧q)∨(p∧r)
T T T T T T
T T F T F T
T F T F T T
T F F F F F
F T T F F F
F T F F F F
F F T F F F
F F F F F F
Step 2: Create a truth table for p∧(q∨r).
p q r q ∨r p ∧(q∨r)
T T T T T
T T F T T
T F T T T
T F F F F
F T T T F
F T F T F
F F T T F
F F F F F
Step 3: Compare the truth values of the two propositions.
From the truth tables, we can see that both propositions have the same truth
values for all possible truth values of p,q, and r. Therefore, (p∧q)∨(p∧r) is
logically equivalent to p∧(q∨r).
Question 15
Question
Let p,q, and rbe propositions such that (p→q)∧(q→r)→p. Show that
this proposition is a tautology using a truth table.
10
Solution
To show that the proposition (p→q)∧(q→r)→pis a tautology, we will
construct a truth table for all possible truth values of p,q, and r.
p q r (p→q) (q→r) (p→q)∧(q→r) (p→q)∧(q→r)→p
T T T T T T T
T T F T F F T
T F T F T F T
T F F F T F T
F T T T T T T
F T F T F F T
F F T T T T T
F F F T T T T
In the above truth table, the column (p→q)∧(q→r)→pis always
true regardless of the truth values of p,q, and r. This means that the original
proposition is a tautology.
Question 16
Question
Let pand qbe propositions. Show that the proposition (p→q)→(¬q→ ¬p)
is a tautology using a truth table.
Solution
To show that the proposition (p→q)→(¬q→ ¬p) is a tautology, we will
create a truth table to check all possible truth values of pand q.
p q ¬p¬q(p→q) (¬q→ ¬p) (p→q)→(¬q→ ¬p)
T T F F T T T
T F F T F F T
F T T F T T T
F F T T T T T
Since the final column of the truth table is always true (T), the proposition
(p→q)→(¬q→ ¬p) is a tautology.
11
Question 17
Question
Let p,q, and rbe propositions. Show that (p∨q)∧(p∨r) is logically equivalent
to p∨(q∧r).
Solution
To show that (p∨q)∧(p∨r) is logically equivalent to p∨(q∧r), we need to
show that the truth values of these two compound propositions are the same
for all possible truth values of p,q, and r.
Step 1: Construct truth tables for both compound propositions.
First, let’s construct a truth table for (p∨q)∧(p∨r):
p q r p ∨q p ∨r(p∨q)∧(p∨r)
T T T T T T
T T F T T T
T F T T T T
T F F T T T
F T T T T T
F T F T F F
F F T F T F
F F F F F F
Next, let’s construct a truth table for p∨(q∧r):
p q r q ∧r p ∨(q∧r)
T T T T T
T T F F T
T F T F T
T F F F T
F T T T T
F T F F F
F F T F F
F F F F F
Step 2: Compare the truth values of both compound propositions.
From the truth tables, we can see that the truth values of both compound
propositions are the same for all possible truth values of p,q, and r. Therefore,
we can conclude that (p∨q)∧(p∨r) is logically equivalent to p∨(q∧r).
12
Question 18
Question
Let p,q, and rbe propositions such that:
(p→q)→r
¬r→(q→ ¬p)
¬q
Determine the truth value of p.
Solution
1. We are given that ¬q. We will use this to find the truth value of q. 2. Since
¬q, then qis false. 3. By the second statement, ¬r→(q→ ¬p), and since q
is false, we can simplify this to ¬r. 4. Therefore, ris false. 5. Finally, by the
first statement (p→q)→r, we know that (p→q) implies r. Since ris false,
(p→q) must also be false. 6. Since qis false, the only way for (p→q) to be
false is for pto be true. 7. Hence, the truth value of pis true.
Question 19
Question
Let p, q, and rbe propositional variables. Show that the following statement is
a tautology:
(p∧q→r)→(p→(q→r))
Solution
To show that the given statement is a tautology, we will use a truth table to
check all possible truth values of p, q, and r.
Step 1: Create a truth table for the given statement.
p q r p ∧q p ∧q→r q →r p →(q→r)
T T T T T T T
T T F T F F T
T F T F T T T
T F F F T T T
F T T F T T T
F T F F T F T
F F T F T T T
F F F F T T T
Step 2: Analyze the truth table. From the truth table, we can see that
the last column, which represents the given statement, is true for all possible
13
truth values of p, q, and r. Since the statement is true for all possible truth
values of p, q, and r, we conclude that the statement is a tautology.
Question 20
Question
Let p,q, and rbe propositional variables with the following premises:
(p→q)∧(q→r)
¬r
Determine whether the conclusion ¬pfollows using propositional calculus
rules.
Solution
To determine if ¬pfollows from the given premises, we will construct a proof
by contradiction.
Step 1: Assume pis true.
Step 2: Use the first premise (p→q)∧(q→r) to deduce qfrom p→q.
Since pis true and (p→q) is true, it follows that qis also true.
Step 3: Use the second premise ¬rto deduce ¬qfrom q→r.
Since ris false (due to ¬r), q→ris false. Therefore, qmust also be false.
Step 4: From Steps 2 and 3, we have arrived at a contradiction: qis both
true and false.
Therefore, our assumption that pis true must be false.
Step 5: Conclude that ¬pfollows from the given premises.
Hence, the conclusion ¬pfollows using propositional calculus rules.
Question 21
Question
Let p,q, and rbe propositions such that p→(q∧r) is false. Determine the
truth values of p,q, and r.
Solution
To determine the truth values of p,q, and r, we will consider the truth table
for the implication p→(q∧r). The truth table for an implication is as follows:
p q p →q
T T T
T F F
F T T
F F T
14
Given that p→(q∧r) is false, we observe that the only way this can occur
is when pis true and q∧ris false.
Step 1: Assigning values to p,q, and rbased on the truth table
Since pmust be true and q∧rmust be false in order for p→(q∧r) to be false,
we have: - p=true -q∧r=false
Using the truth table for conjunction (∧), we find that q∧ris false only
when qand rare both false.
Step 2: Assigning values to qand rTherefore, we have: - q=false -
r=false
In conclusion, the truth values of p,q, and rare: - pis true -qis false -r
is false
Question 22
Question
Let p,q, and rbe propositions. Show that (p⇒q)∨(q⇒r) is logically
equivalent to (p∧q)⇒r.
Solution
To show that (p⇒q)∨(q⇒r) is logically equivalent to (p∧q)⇒r, we will
construct truth tables for both statements and show that they have the same
truth values for all possible truth values of p,q, and r.
Step 1: Truth table for (p⇒q)∨(q⇒r)
p q r p ⇒q q ⇒r(p⇒q)∨(q⇒r)
T T T T T T
T T F T F T
T F T F T T
T F F F T T
F T T T T T
F T F T F T
F F T T T T
F F F T T T
Step 2: Truth table for (p∧q)⇒r
p q r p ∧q(p∧q)⇒r
T T T T T
T T F T F
T F T F T
T F F F T
F T T F T
F T F F T
F F T F T
F F F F T
15
Step 3: Conclusion From the truth tables above, we can see that (p⇒
q)∨(q⇒r) and (p∧q)⇒rhave the same truth values for all possible truth
values of p,q, and r. Therefore, (p⇒q)∨(q⇒r) is logically equivalent to
(p∧q)⇒r.
Question 23
Question
Let p,q, and rbe propositional variables. Show that the following proposition
is a tautology:
(p∧q)→(p∨r)
Solution
To show that the proposition (p∧q)→(p∨r) is a tautology, we can use a truth
table to prove that the proposition is true for all possible truth values of p,q,
and r.
Step 1: Create the truth table for the proposition (p∧q)→(p∨r).
p q r p ∧q p ∨r(p∧q)→(p∨r)
T T T T T T
T T F T T T
T F T F T T
T F F F T T
F T T F T T
F T F F F T
F F T F T T
F F F F F T
Since the last column of the truth table is always true, we can conclude that
the proposition (p∧q)→(p∨r) is a tautology.
Question 24
Question
Let p,q, and rbe propositions. Show that the proposition (p∧q)∨(p∧r) is
logically equivalent to p∧(q∨r).
Solution
To show that two propositions are logically equivalent, we need to show that
they have the same truth value for all possible truth values of their component
propositions. We can do this by creating truth tables for both propositions and
checking if they are the same.
16
Step 1: Create a truth table for (p∧q)∨(p∧r).
p q r p ∧q p ∧r(p∧q)∨(p∧r)
T T T T T T
T T F T F T
T F T F T T
T F F F F F
F T T F F F
F T F F F F
F F T F F F
F F F F F F
Step 2: Create a truth table for p∧(q∨r).
p q r q ∨r p ∧(q∨r)
T T T T T
T T F T T
T F T T T
T F F F F
F T T T F
F T F T F
F F T T F
F F F F F
Step 3: Compare the two truth tables. After comparing the truth
values of both propositions, we can see that (p∧q)∨(p∧r) and p∧(q∨r)
have the same truth values for all possible combinations of p,q, and r. Hence,
(p∧q)∨(p∧r) is logically equivalent to p∧(q∨r).
Question 25
Question
Let pand qbe propositions. Show that the statement (p→q)∧(q→p) is
logically equivalent to p↔q.
Solution
To show that (p→q)∧(q→p) is logically equivalent to p↔q, we need to
show that they have the same truth values for all possible truth values of pand
q.
Step 1: Construct the truth table for (p→q)∧(q→p).
p q p →q q →p(p→q)∧(q→p)
T T T T T
T F F T F
F T T F F
F F T T T
17
Step 2: Construct the truth table for p↔q.
p q p ↔q
T T T
T F F
F T F
F F T
Step 3: Compare the truth tables for (p→q)∧(q→p) and p↔q.
From the truth tables, we observe that both (p→q)∧(q→p) and p↔q
have the same truth values for all combinations of pand q. Hence, we can
conclude that (p→q)∧(q→p) is logically equivalent to p↔q.
Question 26
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we can perform
a series of logical equivalences using the basic laws of propositional logic.
Step 1: Apply the Distributive Law
(p∧q)∨(p∧r)
=p∧(q∨r)
Step 2: Commutativity of ∨
p∧(q∨r)
=p∧(r∨q)
Step 3: Commutativity of ∧
p∧(r∨q)
= (r∨q)∧p
Step 4: Apply the Distributive Law (Reverse)
(r∨q)∧p
= (p∧r)∨(p∧q)
Therefore, (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r).
18
Question 27
Question
Let pand qbe propositions. Show that (p→q)∨(q→p) is a tautology.
Solution
To show that (p→q)∨(q→p) is a tautology, we will construct a truth table
to check all possible combinations of truth values for pand q.
p q p →q q →p(p→q)∨(q→p)
T T T T T
T F F T T
F T T F T
F F T T T
Since the final column consists of all true values, we can conclude that (p→
q)∨(q→p) is a tautology.
Question 28
Question
Let p,q, and rbe propositional variables. Determine whether the following
argument is valid:
(p∧q)⇒r, p ⇒q, ¬r
¬p
Solution
To determine the validity of the argument, we will use the method of proof by
contradiction. We will assume that the premises are true and the conclusion is
false, and then derive a contradiction.
Step 1: Assume the premises are true and the conclusion is false:
1.(p∧q)⇒r(Premise)
2. p ⇒q(Premise)
3.¬r(Premise)
4.¬p(Assumption for contradiction)
Step 2: Use premises (1) and (2) to derive r:
5. p (Assumption)
6. q (Modus Ponens on 2 and 5)
7. p ∧q(Conjunction of 5 and 6)
8. r (Modus Ponens on 1 and 7)
19
Step 3: Derive a contradiction:
9. r (From Step 8)
10.¬r(From 3)
11.False (Contradiction from 9 and 10)
Since assuming ¬pled to a contradiction, the argument is valid.
Question 29
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using propositional calculus.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we can use truth
tables.
Step 1: Create a truth table for the given proposition
p q r p →q q →r p →r(p→q)∧(q→r)→(p→r)
T T T T T T T
T T F T F F T
T F T F T T T
T F F F T F T
F T T T T T T
F T F T F T T
F F T T T T T
F F F T T T T
Step 2: Analyze the truth table Since the final column of the truth
table consists only of true values, we can conclude that the proposition (p→
q)∧(q→r)→(p→r) is a tautology.
Question 30
Question
Let p,q, and rbe propositions. Determine whether the following argument is
valid:
”If pthen q. If qthen r. Therefore, if pthen r.”
20
Solution
To determine the validity of the argument, we can use the rules of implica-
tion in propositional logic. Specifically, we will use the transitive property of
implication.
Step 1: Express the given statements as logical implications:
Statement 1: ”If pthen q” can be expressed as p→q.
Statement 2: ”If qthen r” can be expressed as q→r.
Conclusion: ”If pthen r” can be expressed as p→r.
Step 2: Apply the transitive property of implication. According to the
transitive property of implication, if p→qand q→rare true, then p→ris
also true.
Step 3: Use truth tables to check the validity of the argument:
p q r p →q q →r p →r
T T T T T T
T T F T F F
T F T F T T
T F F F T F
F T T T T T
F T F T F T
F F T T T T
F F F T T T
Step 4: Conclusion From the truth table, we see that the statement p→r
is not always true when p→qand q→rare true. Therefore, the argument is
not always valid.
Question 31
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using a truth table.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will construct a
truth table for all possible truth values of p,q, and r, and show that the final
column is always true.
21
p q r p →q q →r p →r(p→q)∧(q→r)→(p→r)
T T T T T T T
T T F T F F T
T F T F T T T
T F F F T F T
F T T T T T T
F T F T F T T
F F T T T T T
F F F T T T T
As shown in the truth table, the final column is always true regardless of
the truth values of p,q, and r. Therefore, (p→q)∧(q→r)→(p→r) is a
tautology.
Question 32
Question
Use natural deduction to prove the following statement: (p→q)∧(q→r)⊢
p→r
Solution
To prove (p→q)∧(q→r)⊢p→rusing natural deduction, we will assume
(p→q)∧(q→r) as a premise and derive p→r.
Step 1: Assume (p→q)∧(q→r) as a premise.
Step 2: Using conjunction elimination, separate the conjuncts (p→q) and
(q→r).
1.(p→q)∧(q→r) Premise
2. p →qConjunction Elimination from (1)
3. q →rConjunction Elimination from (1)
Step 3: Assume p.
Step 4: Using modus ponens with p→qand p, derive q.
4. p Assumption
5. p →qReiteration from (2)
6. q Modus Ponens from (5) and (4)
Step 5: Using modus ponens with q→rand q, derive r.
7. q Reiteration from (6)
8. q →rReiteration from (3)
9. r Modus Ponens from (8) and (7)
Step 6: Since we derived runder assumption p, we can infer p→r.
22
10. p →r(from 3, 4-9)
Therefore, we have shown that (p→q)∧(q→r)⊢p→rusing natural
deduction.
Question 33
Question
Let p,q, and rbe propositions. Show that the proposition (p→q)∧(q→r)→
(p→r) is a tautology.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will use truth
tables to verify that the compound proposition is true for all possible truth
values of p,q, and r.
p q r p →q q →r(p→q)∧(q→r)p→r(p→q)∧(q→r)→(p→r)
T T T T T T T T
T T F T F F F T
T F T F T F T T
T F F F T F F T
F T T T T T T T
F T F T F F T T
F F T T T T T T
F F F T T T T T
Since the final column of the truth table is always true, we can conclude that
the proposition (p→q)∧(q→r)→(p→r) is a tautology.
Question 34
Question
Let p, q, r be propositional variables where: p: It is sunny today. q: It is cold
today. r: It is snowing today.
Consider the proposition: If it is sunny today, then it is not cold or it is
snowing. Write this proposition in terms of p,q, and rusing logical connectives
(negation, conjunction, disjunction, implication).
23
Solution
Step 1: The given proposition can be written as follows:
p→(¬q∨r)
Therefore, the proposition ”If it is sunny today, then it is not cold or it is
snowing” can be represented in terms of p,q, and rusing the logical connectives
of negation, disjunction, and implication.
Question 35
Question
Prove or disprove the following statement: ”If it is not raining or it is not cold,
then John will go for a run.”
Solution
To prove or disprove the statement, we will analyze the given proposition in
terms of logic and propositional calculus.
Let Pdenote the proposition ”It is raining”, Qdenote the proposition ”It
is cold”, and Rdenote the proposition ”John will go for a run”.
The given statement can be written as: (¬P∨ ¬Q)→R. This can be
translated into words as ”If it is not raining or it is not cold, then John will go
for a run.”
To prove or disprove this statement, we will construct a truth table for the
given proposition and check if the implication holds in all cases.
P Q ¬P∨ ¬Q R (¬P∨ ¬Q)→R
T T F T T
T F T T T
F T T T T
F F T T T
Since the truth table shows that the implication holds in all cases, we can
conclude that the statement ”If it is not raining or it is not cold, then John will
go for a run” is true.
24
