MATH 250 - INTRODUCTION TO
DISCRETE MATHEMATICS - Logic
and Propositional Calculus
Question Bank - Set 5
Liberty University
Question 1
Question
Let p,q, and rbe propositions. Show that the statement (p→q)∧(q→r)→
(p→r) is a tautology using logical equivalences.
Solution
To show that the statement (p→q)∧(q→r)→(p→r) is a tautology, we will
use logical equivalences to simplify the expression.
Step 1: Apply the definition of implication (A→B)≡(¬A∨B) twice:
(p→q)∧(q→r)→(p→r)≡(¬(p→q)∨(q→r)) ∨(¬p∨r)
Step 2: Apply the definition of implication again for ¬(p→q) and (q→r):
(¬(p→q)∨(q→r)) ∨(¬p∨r)≡((¬(¬p∨q)) ∨(¬q∨r)) ∨(¬p∨r)
Step 3: Apply De Morgan’s laws and double negation:
((¬(¬p∨q)) ∨(¬q∨r)) ∨(¬p∨r)≡((p∧ ¬q)∨(¬q∨r)) ∨(¬p∨r)
Step 4: Apply distribution:
((p∧ ¬q)∨(¬q∨r)) ∨(¬p∨r)≡((p∨ ¬q)∧(¬q∨r)) ∨(¬p∨r)
Step 5: Apply distribution again:
((p∨ ¬q)∧(¬q∨r)) ∨(¬p∨r)≡((p∨ ¬q)∨(¬p∨r)) ∧((p∨ ¬q)∨r)
Step 6: Apply commutativity and association:
((p∨ ¬q)∨(¬p∨r)) ∧((p∨ ¬q)∨r)≡(p∨ ¬q∨ ¬p∨r)∧(p∨ ¬q∨r)
Step 7: Apply idempotent law:
(p∨ ¬q∨ ¬p∨r)∧(p∨ ¬q∨r)≡(p∨ ¬p∨ ¬q∨r)∧(p∨ ¬q∨r)
Step 8: Apply negation law ¬p∨p≡True:
(p∨ ¬p∨ ¬q∨r)∧(p∨ ¬q∨r)≡(True ∨ ¬q∨r)∧(p∨ ¬q∨r)
Step 9: Apply domination law True ∨A≡True:
(True ∨ ¬q∨r)∧(p∨ ¬q∨r)≡True ∧(p∨ ¬q∨r)
Step 10: Apply identity law True ∧A≡A:
True ∧(p∨ ¬q∨r)≡p∨ ¬q∨r
Since p∨ ¬q∨ris always true for any values of p,q, and r, the original
statement is a tautology.
Question 2
Question
Let p,q, and rbe propositions. Show that the proposition (p→q)→ris
logically equivalent to p→(q→r).
Solution
To show that the propositions are logically equivalent, we can construct truth
tables for both propositions and show that the output columns are the same for
all possible combinations of truth values for p,q, and r.
Step 1: Create the 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 T T
F T F T F
F F T T T
F F F T F
Step 2: Create the truth table for p→(q→r).
2
p q r q →r p →(q→r)
T T T T T
T T F F T
T F T T T
T F F T T
F T T T T
F T F T T
F F T T T
F F F T T
Step 3: Conclusion
By comparing the output columns of the truth tables for (p→q)→rand
p→(q→r), we can see that the two propositions are logically equivalent as
the output values for all possible truth value combinations are the same.
Therefore, (p→q)→ris logically equivalent to p→(q→r).
Question 3
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 and verify that the final column is always true.
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
Since the final column evaluates to true for all possible truth values of p,q,
and r, we can conclude that (p→q)∧(q→r)→(p→r) is a tautology.
3
Question 4
Question
Let p, q, r be propositions with the following constraints:
(p∧q) =⇒r
p=⇒q
r=⇒ ¬q
Determine whether the proposition (p∧q) =⇒ ¬ris a logical consequence of
the given constraints.
Solution
Step 1: Use the contrapositive of the third constraint to get ¬¬q=⇒ ¬r. This
simplifies to q=⇒ ¬r.
Step 2: Use the second constraint to get ¬p∨q.
Step 3: Use the first constraint and the results from Step 1 and Step 2 to
find (p∧q) =⇒r, which simplifies to ¬r=⇒ ¬(p∧q).
Step 4: Converting this result to CNF format, we get (p∨ ¬r)∧(q∨ ¬r).
Step 5: Combine the results from Step 3 and Step 4 to identify whether
the proposition (p∧q) =⇒ ¬ris a logical consequence. Since (p∧q)∧ ¬r
does not appear in the CNF format of the given constraints, the proposition
(p∧q) =⇒ ¬ris not a logical consequence.
Question 5
Question
Let p,q, and rbe propositions. Determine whether the following logical equiv-
alence is true or false: (p→q)→r≡p→(q→r).
Solution
We will determine the truth value of both sides of the logical equivalence by
constructing truth tables.
4
Step 1: Construct the truth table for (p→q)→r:
p q r (p→q)→r
T T T T
T T F F
T F T T
T F F F
F T T T
F T F T
F F T T
F F F T
Step 2: Construct the truth table for p→(q→r):
p q r p →(q→r)
T T T T
T T F F
T F T T
T F F T
F T T T
F T F T
F F T T
F F F T
Step 3: Compare the two truth tables: From the truth tables, we
can see that the two logical expressions (p→q)→rand p→(q→r) have
different truth values for some combinations of p,q, and r. Therefore, the logical
equivalence is false.
Question 6
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using truth tables.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will construct
a truth table for the entire expression and show that the truth values of the
compound proposition are always true.
5
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
In the truth table, we see that the final column evaluates to true for all
possible truth values of p,q, and r. Therefore, (p→q)∧(q→r)→(p→r) is
a tautology.
Question 7
Question
Let p,q, and rbe propositional variables representing the following statements:
p: It is raining. q: The grass is wet. r: The sprinklers are on.
Write the following statement in symbolic logic: ”If it is not raining and the
grass is wet, then the sprinklers are not on.”
Solution
To express the given statement in symbolic logic, we can use the logical operators
¬(negation), ∧(conjunction), and →(implication).
Step 1: Identify the components of the statement Let’s represent the
components of the statement in symbolic logic: Negation of p:¬p q:qNegation
of r:¬r
Step 2: Formulate the logical statement The given statement can be
translated into symbolic logic as:
(¬p∧q)→ ¬r
Therefore, the symbolic representation of the statement ”If it is not raining
and the grass is wet, then the sprinklers are not on.” is (¬p∧q)→ ¬r.
Question 8
Question
Let p,q, and rbe propositions. Suppose the proposition (p⇒q)⇒ris false,
and the proposition p⇒(q⇒r) is true. Determine the truth values of p,q,
and r.
6
Solution
Step 1: Use the fact that (p⇒q)⇒ris false to determine the truth values of
p,q, and r. If (p⇒q)⇒ris false, this means that (p⇒q) is true while ris
false. Since the implication (p⇒q) is true and ris false, then pmust be true
while qcan be either true or false.
Step 2: Use the fact that p⇒(q⇒r) is true to further determine the truth
values of p,q, and r. Since p⇒(q⇒r) is true and we already know that pis
true, this implies that q⇒ris true. If qis true, then rmust also be true in
order for q⇒rto be true. Therefore, the truth values of p,q, and rare: pis
true, qis true, and ris false.
Question 9
Question
Let p,q, and rbe propositions. Prove the following logical equivalence using
propositional calculus laws:
(p→q)∧(q→r)↔(p→r)
Solution
To prove (p→q)∧(q→r)↔(p→r), we can first prove that (p→q)∧(q→
r)→(p→r) and then prove (p→r)→(p→q)∧(q→r).
Step 1: Prove (p→q)∧(q→r)→(p→r)
(p→q)∧(q→r)
≡(¬p∨q)∧(¬q∨r) [Implication rule]
≡(¬p∧ ¬q)∨(¬p∧r)∨(q∧ ¬q)∨(q∧r) [Distribution]
≡¬p∧r∨(q∧ ¬q) [Simplify]
≡¬p∧r∨F[Contradiction]
≡¬p∧r[Identity]
≡p→r[Implication rule]
7
Step 2: Prove (p→r)→(p→q)∧(q→r)
p→r
≡¬p∨r[Implication rule]
Let’s prove the first part: p→q
Assume p
T hen r [From p→r]
Therefore, p→q
Let’s prove the second part: q→r
Assume q
T hen r [From p→r]
Therefore, q→r
Since p →q and q →r hold, we have p →q∧q→r
Therefore, we have shown that (p→q)∧(q→r)↔(p→r) is true using
propositional calculus laws.
Question 10
Question
Let p,q, and rbe propositions. Show that the following statement is a tautology:
(p→q)∨(q→r)∨(r→p).
Solution
To show that the given statement is a tautology, we need to show that it is true
for all possible truth values of p,q, and r. We can do this by constructing a
truth table for the statement.
Step 1: Construct a truth table for the statement.
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 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
Step 2: Analyze the truth table.
From the truth table, we see that the statement (p→q)∨(q→r)∨(r→p)
evaluates to true for all possible truth values of p,q, and r. Therefore, the
statement is a tautology.
Question 11
Question
Let p,q, and rbe propositions with the following truth values: pis false, qis
true, ris false.
Negate the proposition (p∧q)∨ ¬r.
Solution
To negate the proposition (p∧q)∨ ¬r, we will first find its truth value and then
apply the negation.
Step 1: Find the truth value of (p∧q)∨ ¬r: Given that: pis false, qis true,
ris false.
Therefore, p∧qis false ∧true = false, and ¬ris ¬false = true.
Then, we have (p∧q)∨ ¬r= false ∨true = true.
Step 2: Negate the truth value of (p∧q)∨ ¬r: The negation of true is false.
Hence, the negation of the proposition (p∧q)∨ ¬ris false .
Question 12
Question
Prove the following statement or provide a counterexample:
For all integers aand b, if ais odd and bis even, then a2+bis odd.
9
Solution
To prove the statement, we will use a direct proof.
Step 1: Assume ais an odd integer and bis an even integer.
Let a= 2k+ 1 for some integer k(by definition of odd integers) and b= 2m
for some integer m(by definition of even integers).
Step 2: Find a2
a2= (2k+ 1)2= 4k2+ 4k+ 1 = 2(2k2+ 2k)+1
Thus, a2is also odd.
Step 3: Determine the sum a2+b
a2+b= 2(2k2+ 2k)+1+2m= 2(2k2+ 2k+m)+1
Since 2k2+ 2k+mis an integer, a2+bis odd.
Step 4: Conclusion
Therefore, for all integers aand b, if ais odd and bis even, then a2+bis
odd.
Question 13
Question
Let p,q, and rbe statements. 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 need to show 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
T T T T T T T
T T F T F F F
T F T F T F T
T F F F T F F
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
Since the final column of the truth table is always true, (p→q)∧(q→r)→
(p→r) is a tautology.
10
Question 14
Question
Let p,q, and rbe propositions. Show that (p∧q)→ris logically equivalent to
(p→r)∨(q→r).
Solution
To show that (p∧q)→ris logically equivalent to (p→r)∨(q→r), we will
construct truth tables for both expressions and show that the resulting columns
match.
Step 1: Construct the truth table for (p∧q)→r:
p q r (p∧q)→r
T T T T
T T F F
T F T T
T F F F
F T T T
F T F T
F F T T
F F F T
Step 2: Construct the truth table for (p→r)∨(q→r):
p q r p →r q →r(p→r)∨(q→r)
T T T T T T
T T F F T T
T F T T 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 3: Conclusion: From the truth tables, we can see that the columns
for (p∧q)→rand (p→r)∨(q→r) are identical. Therefore, we have shown
that (p∧q)→ris logically equivalent to (p→r)∨(q→r).
Question 15
Question
Let prepresent ”It is raining” and qrepresent ”The roads are wet.” Write the
logical statement for the following scenario: ”If it is raining, then the roads are
wet.”
11
Solution
To write the logical statement for the scenario ”If it is raining, then the roads
are wet,” we need to express it using logical connectives.
Step 1: Define the propositions: Let prepresent ”It is raining” and qrepre-
sent ”The roads are wet.”
Step 2: Construct the logical statement: The logical statement for the sce-
nario ”If it is raining, then the roads are wet.” can be written as p→q.
Therefore, the logical statement for the scenario is: p→q.
Question 16
Question
Let p,q, and rbe propositions. Determine whether the following statement is
a tautology, a contradiction, or contingent:
(p∧q)→[(p∨r)↔(q∨r)]
Solution
To determine whether the given statement is a tautology, a contradiction, or
contingent, we will construct a truth table for the statement.
Step 1: Create the truth table for the statement.
p q r p ∧q p ∨r q ∨r(p∨r)↔(q∨r) (p∧q)→[(p∨r)↔(q∨r)]
T T T T T T T T
T T F T T T T T
T F T F T T T T
T F F F T F F T
F T T F T T T T
F T F F F T T T
F F T F T T T T
F F F F F F T T
Since the final column has all entries as true, the given statement is a tau-
tology.
Question 17
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using propositional calculus.
12
Solution
To show that the compound proposition is a tautology, we will construct a truth
table and verify that the resulting column under the main connective →consists
of all T’s.
Step 1: Create a truth table for the given proposition
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
Step 2: Analyze the truth values In the last column, we see that all the
truth values are T. Therefore, the compound proposition (p→q)∧(q→r)→
(p→r) is a tautology.
Question 18
Question
Let pand qbe propositions. Show that (p∧q)∨(¬p∧ ¬q) is logically equivalent
to p↔q.
Solution
To show that (p∧q)∨(¬p∧ ¬q) is logically equivalent to p↔q, we will first
simplify (p∧q)∨(¬p∧ ¬q) using logical equivalences, and then show that it is
equivalent to p↔qusing a truth table.
Step 1: Simplify (p∧q)∨(¬p∧ ¬q)
By distributive law: (p∧q)∨(¬p∧ ¬q)≡(p∨ ¬p)∧(p∨ ¬q)∧(q∨ ¬p)∧(q∨ ¬q)
By tautology: (p∨ ¬p)≡true, (q∨ ¬q)≡true
Therefore, the expression simplifies to: (p∨ ¬q)∧(q∨ ¬p).
Step 2: Construct Truth Table for ((p∧q)∨(¬p∧ ¬q)) ↔(p↔q)
p q p ∧q¬p¬q(p∧q)∨(¬p∧ ¬q)p↔q
T T T F F T T
T F F F T T F
F T F T F T F
F F F T T T T
Step 3: Analyze the Truth Table
From the truth table, we see that ((p∧q)∨(¬p∧ ¬q)) ↔(p↔q) has the same
13
truth values for all combinations of pand q. Therefore, we have shown that
(p∧q)∨(¬p∧ ¬q) is logically equivalent to p↔q.
Question 19
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 will construct
truth tables for both expressions and show that they have the same truth values
for all possible truth values of p,q, and r.
Step 1: Construct the 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: Construct the 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: Conclusion By comparing the truth values of (p∧q)∨(p∧r)
and p∧(q∨r) in the truth tables, we can see that they are indeed logically
equivalent for all possible truth values of p,q, and r. Therefore, (p∧q)∨(p∧r)
is logically equivalent to p∧(q∨r).
14
Question 20
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 to examine all possible combinations of truth values for p,q, and r.
p q r p →q q →r(p→q)∧(q→r)p→r
T T T T T T T
T T F T F F F
T F T F T F T
T F F F T F F
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 truth table, we can see that every row evaluates to true for the final
column (p→q)∧(q→r)→(p→r). Since the statement is true for all possible
truth values of p,q, and r, we can conclude that (p→q)∧(q→r)→(p→r)
is a tautology.
Question 21
Question
Let p,q, and rbe propositions. Show algebraically that (p∧q)∨ris logically
equivalent to (p∨r)∧(q∨r).
Solution
To show that (p∧q)∨ris logically equivalent to (p∨r)∧(q∨r), we need to show
that both statements have the same truth values for all possible truth values of
p,q, and r.
Step 1: Apply the distributive law on (p∧q)∨r:
(p∧q)∨r
= (p∨r)∧(q∨r)
by the distributive law of disjunction over conjunction, which states that p∨
(q∧r)≡(p∨q)∧(p∨r).
Therefore, (p∧q)∨ris logically equivalent to (p∨r)∧(q∨r).
15
Question 22
Question
Let p,q, and rbe propositions. Determine the truth value of the following
proposition: (p→q)∧(q→r)∧(r→p).
Solution
To determine the truth value of the proposition (p→q)∧(q→r)∧(r→p),
we consider the truth values of the propositions p,q, and rand apply the truth
table for implication (→) and conjunction (∧).
p q r p →q q →r r →p(p→q)∧(q→r)∧(r→p)
T T T T T T T ∧T∧T=T
T T F T F T T ∧F∧T=F
T F T F T T F ∧T∧T=F
T F F F T T F ∧T∧T=F
F T T T T F T ∧T∧F=F
F T F T F T T ∧F∧T=F
F F T T T F T ∧T∧F=F
F F F T T T T ∧T∧T=T
Therefore, the truth value of the proposition (p→q)∧(q→r)∧(r→p) is
false except when pis false, qis false, and ris false.
Question 23
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
logical equivalences to simplify the expressions and show that they are equal.
Step 1: Apply the Distributive Law on (p∧q)∨(p∧r):
(p∧q)∨(p∧r)≡p∧(q∨r)
Therefore, we have shown that the proposition (p∧q)∨(p∧r) is logically
equivalent to p∧(q∨r).
16
Question 24
Question
Prove the following logical equivalence using the laws of propositional logic:
(p∧q)∨ ¬(p∧r)≡(p∨ ¬r)∧(q∨ ¬r)
Solution
To prove the given logical equivalence, we will simplify both sides of the equation
using the laws of propositional logic until they are equivalent.
Step 1: Apply De Morgan’s Laws
(p∧q)∨ ¬(p∧r)
= (p∧q)∨(¬p∨ ¬r) (De Morgan’s Law)
Step 2: Distribute ∨over ∧
= (p∨ ¬p)∧(p∨ ¬r)∧(q∨ ¬p)∧(q∨ ¬r)
Step 3: Apply Complement Laws
=T∧(p∨ ¬r)∧(q∨ ¬p)∧(q∨ ¬r) (Complement Laws)
= (p∨ ¬r)∧(q∨ ¬p)∧(q∨ ¬r) (Identity Law)
Step 4: Apply Commutative Laws
= (p∨ ¬r)∧(q∨ ¬r)∧(q∨ ¬p)
= (p∨ ¬r)∧(q∨ ¬p)∧(q∨ ¬r) (Commutative Law)
Step 5: Applying Distributive Laws
= (p∨ ¬r)∧((q∨ ¬p)∧(q∨ ¬r))
= (p∨ ¬r)∧(q∨(¬p∧ ¬r)) (Distributive Law)
Step 6: Apply De Morgan’s Laws
= (p∨ ¬r)∧(q∨ ¬(p∨r)) (De Morgan’s Law)
Step 7: Reverse Steps Thus, we have shown that (p∧q)∨ ¬(p∧r)≡
(p∨ ¬r)∧(q∨ ¬r).
Question 25
Question
Let p, q, r be propositions. Show that (p→q)∧(q→r)→(p→r) is a tautology
using propositional calculus.
17
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will construct a
truth table and show that the output column is always true.
Step 1: Construct the truth table
p q r p →q q →r(p→q)∧(q→r)p→r
T T T T T T T
T T F T F F F
T F T F T F T
T F F F T F F
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
Step 2: Analyze the truth table
From the truth table, we can see that the column for (p→q)∧(q→r)→
(p→r) is always true. Thus, (p→q)∧(q→r)→(p→r) is a tautology.
Question 26
Question
Let p,q, and rbe propositions. Show that (p∧q)∨ris logically equivalent to
(p∨r)∧(q∨r) using propositional equivalences.
Solution
To show that (p∧q)∨ris logically equivalent to (p∨r)∧(q∨r), we need to
demonstrate that (p∧q)∨r≡(p∨r)∧(q∨r).
Step 1: Distributive law (OR over AND) By applying the distributive
law of propositional logic, we can expand (p∧q)∨r:
(p∧q)∨r= (p∨r)∧(q∨r)
Therefore, (p∧q)∨ris logically equivalent to (p∨r)∧(q∨r).
Question 27
Question
Let p,q, and rrepresent the following propositions: p: ”I will study hard”, q: ”I
will pass the exam”, and r: ”I will get an A”. Translate the following statement
into symbolic logic: ”If I study hard, then I will pass the exam and get an A.”
18
Solution
To translate the statement ”If I study hard, then I will pass the exam and get
an A” into symbolic logic, we can use implication and conjunction symbols. Let
p: ”I will study hard”, q: ”I will pass the exam”, and r: ”I will get an A”. The
given statement can be translated as: If p, then (q∧r) which can be represented
as p→(q∧r). Therefore, the symbolic logic representation of the statement is
p→(q∧r).
Question 28
Question
Let pand qbe propositions. Show that (p→q)↔(¬p∨q) is a tautology using
a truth table.
Solution
To show that (p→q)↔(¬p∨q) is a tautology, we will construct a truth table
and verify that the column for the logical equivalence evaluates to True for all
possible truth values of pand q.
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: Fill in the truth table columns for ¬pand ¬p∨q.
¬p: The negation of p.
¬p∨q: The disjunction (OR) of ¬pand q.
Step 2: Fill in the truth table column for p→q.
p→q: The conditional (IF...THEN) statement.
Step 3: Fill in the truth table column for the logical equivalence (p→q)↔
(¬p∨q).
(p→q)↔(¬p∨q): True if both sides have the same truth value, otherwise
False.
Since the column for the logical equivalence evaluates to True for all possible
truth values of pand q, we conclude that (p→q)↔(¬p∨q) is a tautology.
19
Question 29
Question
Let pand qbe the propositions ”I am happy” and ”I will go for a run”, respec-
tively. Express the proposition ”If I am not happy, then I will not go for a run”
using pand qin propositional logic.
Solution
To express the proposition ”If I am not happy, then I will not go for a run”
using pand q, we can write it as ¬p→ ¬q.
Step 1: Define the propositions: Let pbe ”I am happy” and qbe ”I will go
for a run”.
Step 2: Express the given proposition: The proposition ”If I am not happy,
then I will not go for a run” can be represented as ¬p→ ¬q.
Therefore, the proposition can be expressed as ¬p→ ¬q.
Question 30
Question
Let p, q, r be propositions. Show whether the statement (p∧q)∨ris logically
equivalent to p∨(q∨r).
Solution
To determine if the statement (p∧q)∨ris logically equivalent to p∨(q∨r), we
will construct truth tables for both statements and compare the truth values.
Step 1: Create a truth table for (p∧q)∨r:
p q r (p∧q) (p∧q)∨r
T T T T T
T T F T T
T F T F T
T F F F F
F T T F T
F T F F F
F F T F T
F F F F F
Step 2: Create a truth table for p∨(q∨r):
20
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 T
F T T T T
F T F T T
F F T T T
F F F F F
Step 3: Compare truth tables: Since the two truth tables are different,
we can conclude that (p∧q)∨ris not logically equivalent to p∨(q∨r).
Therefore, the statement (p∧q)∨ris not logically equivalent to p∨(q∨r).
Question 31
Question
Let p,q, and rbe propositions. Show that (p∧q)⇒ris logically equivalent to
(p⇒r)∨(q⇒r).
Solution
To show that (p∧q)⇒ris logically equivalent to (p⇒r)∨(q⇒r), we will
create truth tables for both statements and show that they have the same truth
values for all possible combinations of truth values for p,q, and r.
p q r p ∧q(p∧q)⇒r p ⇒r q ⇒r
T T T T T T T
T T F T F F F
T F T F T T T
T F F F T F T
F T T F T T T
F T F F T T F
F F T F T T T
F F F F T T T
From the truth table, we can see that (p∧q)⇒rand (p⇒r)∨(q⇒r)
have the same truth values for all possible combinations of truth values for p,
q, and r. Therefore, (p∧q)⇒ris logically equivalent to (p⇒r)∨(q⇒r).
21
Question 32
Question
Let p,q, and rbe propositions. Show that (p→ ¬q)→((p→q)→p) is a
tautology using a truth table.
Solution
To show that (p→ ¬q)→((p→q)→p) is a tautology, we need to show that
the compound proposition is true for all possible truth values of p,q, and r. We
will construct a truth table to demonstrate this.
p q ¬q p → ¬q p →q(p→ ¬q)→((p→q)→p)
T T F F T T
T F T T F T
F T F T T T
F F T T T T
Step 1: Fill in the columns for ¬q,p→ ¬q,p→q.
Step 2: Fill in the column for (p→ ¬q)→((p→q)→p) using the truth
values of p→ ¬q,p→q, and p.
Step 3: Identify that the final column is true for all rows in the truth table,
so (p→ ¬q)→((p→q)→p) is a tautology.
Question 33
Question
Let p,q, and rbe propositional variables. Prove or disprove the following
statement: [(p∧q)∨r]⇐⇒ [(p∨r)∧(q∨r)].
Solution
To prove or disprove the statement [(p∧q)∨r]⇐⇒ [(p∨r)∧(q∨r)], we can
show that the two sides are logically equivalent by using truth tables.
Step 1: Create a truth table for [(p∧q)∨r].
p q r (p∧q)∨r
T T T T
T T F F
T F T T
T F F F
F T T T
F T F F
F F T T
F F F F
22
Step 2: Create a truth table for [(p∨r)∧(q∨r)].
p q r p ∨r q ∨r(p∨r)∧(q∨r)
T T T T T T
T T F T T T
T F T T T T
T F F T F F
F T T T T T
F T F F T F
F F T T T T
F F F F T F
Step 3: Compare the truth values of [(p∧q)∨r]and [(p∨r)∧(q∨r)].
From the truth tables, we can see that [(p∧q)∨r] and [(p∨r)∧(q∨r)] do
not have the same truth values for all possible truth value assignments of p,q,
and r. Therefore, the statement [(p∧q)∨r]⇐⇒ [(p∨r)∧(q∨r)] is disproved.
Question 34
Question
Let p, q, r be propositional variables. Given the compound proposition:
(p→q)∧(q→r)∧(r→p)→(p∧q∧r)
Determine whether this compound proposition is a tautology, a contradic-
tion, or neither.
Solution
To determine whether the compound proposition is a tautology, a contradiction,
or neither, we will construct a truth table and check all possible truth values of
p,q, and r.
p q r p →q q →r r →p(p→q)∧(q→r)∧(r→p)p∧q∧r
T T T T T T T T
T T F T F T F F
T F T F T T F F
T F F F T T F F
F T T T T F F F
F T F T F T F F
F F T T T T T F
F F F T T T T F
From the truth table, we see that the compound proposition is only true
when p,q, and rare all false. Therefore, the compound proposition is a contra-
diction.
23
Step 6: Apply commutativity and association:
((p∨ ¬q)∨(¬p∨r)) ∧((p∨ ¬q)∨r)≡(p∨ ¬q∨ ¬p∨r)∧(p∨ ¬q∨r)
Step 7: Apply idempotent law:
(p∨ ¬q∨ ¬p∨r)∧(p∨ ¬q∨r)≡(p∨ ¬p∨ ¬q∨r)∧(p∨ ¬q∨r)
Step 8: Apply negation law ¬p∨p≡True:
(p∨ ¬p∨ ¬q∨r)∧(p∨ ¬q∨r)≡(True ∨ ¬q∨r)∧(p∨ ¬q∨r)
Step 9: Apply domination law True ∨A≡True:
(True ∨ ¬q∨r)∧(p∨ ¬q∨r)≡True ∧(p∨ ¬q∨r)
Step 10: Apply identity law True ∧A≡A:
True ∧(p∨ ¬q∨r)≡p∨ ¬q∨r
Since p∨ ¬q∨ris always true for any values of p,q, and r, the original
statement is a tautology.
Question 2
Question
Let p,q, and rbe propositions. Show that the proposition (p→q)→ris
logically equivalent to p→(q→r).
Solution
To show that the propositions are logically equivalent, we can construct truth
tables for both propositions and show that the output columns are the same for
all possible combinations of truth values for p,q, and r.
Step 1: Create the 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 T T
F T F T F
F F T T T
F F F T F
Step 2: Create the truth table for p→(q→r).
2
p q r q →r p →(q→r)
T T T T T
T T F F T
T F T T T
T F F T T
F T T T T
F T F T T
F F T T T
F F F T T
Step 3: Conclusion
By comparing the output columns of the truth tables for (p→q)→rand
p→(q→r), we can see that the two propositions are logically equivalent as
the output values for all possible truth value combinations are the same.
Therefore, (p→q)→ris logically equivalent to p→(q→r).
Question 3
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 and verify that the final column is always true.
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
Since the final column evaluates to true for all possible truth values of p,q,
and r, we can conclude that (p→q)∧(q→r)→(p→r) is a tautology.
3
Question 4
Question
Let p, q, r be propositions with the following constraints:
(p∧q) =⇒r
p=⇒q
r=⇒ ¬q
Determine whether the proposition (p∧q) =⇒ ¬ris a logical consequence of
the given constraints.
Solution
Step 1: Use the contrapositive of the third constraint to get ¬¬q=⇒ ¬r. This
simplifies to q=⇒ ¬r.
Step 2: Use the second constraint to get ¬p∨q.
Step 3: Use the first constraint and the results from Step 1 and Step 2 to
find (p∧q) =⇒r, which simplifies to ¬r=⇒ ¬(p∧q).
Step 4: Converting this result to CNF format, we get (p∨ ¬r)∧(q∨ ¬r).
Step 5: Combine the results from Step 3 and Step 4 to identify whether
the proposition (p∧q) =⇒ ¬ris a logical consequence. Since (p∧q)∧ ¬r
does not appear in the CNF format of the given constraints, the proposition
(p∧q) =⇒ ¬ris not a logical consequence.
Question 5
Question
Let p,q, and rbe propositions. Determine whether the following logical equiv-
alence is true or false: (p→q)→r≡p→(q→r).
Solution
We will determine the truth value of both sides of the logical equivalence by
constructing truth tables.
4
Step 1: Construct the truth table for (p→q)→r:
p q r (p→q)→r
T T T T
T T F F
T F T T
T F F F
F T T T
F T F T
F F T T
F F F T
Step 2: Construct the truth table for p→(q→r):
p q r p →(q→r)
T T T T
T T F F
T F T T
T F F T
F T T T
F T F T
F F T T
F F F T
Step 3: Compare the two truth tables: From the truth tables, we
can see that the two logical expressions (p→q)→rand p→(q→r) have
different truth values for some combinations of p,q, and r. Therefore, the logical
equivalence is false.
Question 6
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using truth tables.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will construct
a truth table for the entire expression and show that the truth values of the
compound proposition are always true.
5
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
In the truth table, we see that the final column evaluates to true for all
possible truth values of p,q, and r. Therefore, (p→q)∧(q→r)→(p→r) is
a tautology.
Question 7
Question
Let p,q, and rbe propositional variables representing the following statements:
p: It is raining. q: The grass is wet. r: The sprinklers are on.
Write the following statement in symbolic logic: ”If it is not raining and the
grass is wet, then the sprinklers are not on.”
Solution
To express the given statement in symbolic logic, we can use the logical operators
¬(negation), ∧(conjunction), and →(implication).
Step 1: Identify the components of the statement Let’s represent the
components of the statement in symbolic logic: Negation of p:¬p q:qNegation
of r:¬r
Step 2: Formulate the logical statement The given statement can be
translated into symbolic logic as:
(¬p∧q)→ ¬r
Therefore, the symbolic representation of the statement ”If it is not raining
and the grass is wet, then the sprinklers are not on.” is (¬p∧q)→ ¬r.
Question 8
Question
Let p,q, and rbe propositions. Suppose the proposition (p⇒q)⇒ris false,
and the proposition p⇒(q⇒r) is true. Determine the truth values of p,q,
and r.
6
Solution
Step 1: Use the fact that (p⇒q)⇒ris false to determine the truth values of
p,q, and r. If (p⇒q)⇒ris false, this means that (p⇒q) is true while ris
false. Since the implication (p⇒q) is true and ris false, then pmust be true
while qcan be either true or false.
Step 2: Use the fact that p⇒(q⇒r) is true to further determine the truth
values of p,q, and r. Since p⇒(q⇒r) is true and we already know that pis
true, this implies that q⇒ris true. If qis true, then rmust also be true in
order for q⇒rto be true. Therefore, the truth values of p,q, and rare: pis
true, qis true, and ris false.
Question 9
Question
Let p,q, and rbe propositions. Prove the following logical equivalence using
propositional calculus laws:
(p→q)∧(q→r)↔(p→r)
Solution
To prove (p→q)∧(q→r)↔(p→r), we can first prove that (p→q)∧(q→
r)→(p→r) and then prove (p→r)→(p→q)∧(q→r).
Step 1: Prove (p→q)∧(q→r)→(p→r)
(p→q)∧(q→r)
≡(¬p∨q)∧(¬q∨r) [Implication rule]
≡(¬p∧ ¬q)∨(¬p∧r)∨(q∧ ¬q)∨(q∧r) [Distribution]
≡¬p∧r∨(q∧ ¬q) [Simplify]
≡¬p∧r∨F[Contradiction]
≡¬p∧r[Identity]
≡p→r[Implication rule]
7
Step 2: Prove (p→r)→(p→q)∧(q→r)
p→r
≡¬p∨r[Implication rule]
Let’s prove the first part: p→q
Assume p
T hen r [From p→r]
Therefore, p→q
Let’s prove the second part: q→r
Assume q
T hen r [From p→r]
Therefore, q→r
Since p →q and q →r hold, we have p →q∧q→r
Therefore, we have shown that (p→q)∧(q→r)↔(p→r) is true using
propositional calculus laws.
Question 10
Question
Let p,q, and rbe propositions. Show that the following statement is a tautology:
(p→q)∨(q→r)∨(r→p).
Solution
To show that the given statement is a tautology, we need to show that it is true
for all possible truth values of p,q, and r. We can do this by constructing a
truth table for the statement.
Step 1: Construct a truth table for the statement.
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 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
Step 2: Analyze the truth table.
From the truth table, we see that the statement (p→q)∨(q→r)∨(r→p)
evaluates to true for all possible truth values of p,q, and r. Therefore, the
statement is a tautology.
Question 11
Question
Let p,q, and rbe propositions with the following truth values: pis false, qis
true, ris false.
Negate the proposition (p∧q)∨ ¬r.
Solution
To negate the proposition (p∧q)∨ ¬r, we will first find its truth value and then
apply the negation.
Step 1: Find the truth value of (p∧q)∨ ¬r: Given that: pis false, qis true,
ris false.
Therefore, p∧qis false ∧true = false, and ¬ris ¬false = true.
Then, we have (p∧q)∨ ¬r= false ∨true = true.
Step 2: Negate the truth value of (p∧q)∨ ¬r: The negation of true is false.
Hence, the negation of the proposition (p∧q)∨ ¬ris false .
Question 12
Question
Prove the following statement or provide a counterexample:
For all integers aand b, if ais odd and bis even, then a2+bis odd.
9
Solution
To prove the statement, we will use a direct proof.
Step 1: Assume ais an odd integer and bis an even integer.
Let a= 2k+ 1 for some integer k(by definition of odd integers) and b= 2m
for some integer m(by definition of even integers).
Step 2: Find a2
a2= (2k+ 1)2= 4k2+ 4k+ 1 = 2(2k2+ 2k)+1
Thus, a2is also odd.
Step 3: Determine the sum a2+b
a2+b= 2(2k2+ 2k)+1+2m= 2(2k2+ 2k+m)+1
Since 2k2+ 2k+mis an integer, a2+bis odd.
Step 4: Conclusion
Therefore, for all integers aand b, if ais odd and bis even, then a2+bis
odd.
Question 13
Question
Let p,q, and rbe statements. 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 need to show 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
T T T T T T T
T T F T F F F
T F T F T F T
T F F F T F F
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
Since the final column of the truth table is always true, (p→q)∧(q→r)→
(p→r) is a tautology.
10
Question 14
Question
Let p,q, and rbe propositions. Show that (p∧q)→ris logically equivalent to
(p→r)∨(q→r).
Solution
To show that (p∧q)→ris logically equivalent to (p→r)∨(q→r), we will
construct truth tables for both expressions and show that the resulting columns
match.
Step 1: Construct the truth table for (p∧q)→r:
p q r (p∧q)→r
T T T T
T T F F
T F T T
T F F F
F T T T
F T F T
F F T T
F F F T
Step 2: Construct the truth table for (p→r)∨(q→r):
p q r p →r q →r(p→r)∨(q→r)
T T T T T T
T T F F T T
T F T T 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 3: Conclusion: From the truth tables, we can see that the columns
for (p∧q)→rand (p→r)∨(q→r) are identical. Therefore, we have shown
that (p∧q)→ris logically equivalent to (p→r)∨(q→r).
Question 15
Question
Let prepresent ”It is raining” and qrepresent ”The roads are wet.” Write the
logical statement for the following scenario: ”If it is raining, then the roads are
wet.”
11
Solution
To write the logical statement for the scenario ”If it is raining, then the roads
are wet,” we need to express it using logical connectives.
Step 1: Define the propositions: Let prepresent ”It is raining” and qrepre-
sent ”The roads are wet.”
Step 2: Construct the logical statement: The logical statement for the sce-
nario ”If it is raining, then the roads are wet.” can be written as p→q.
Therefore, the logical statement for the scenario is: p→q.
Question 16
Question
Let p,q, and rbe propositions. Determine whether the following statement is
a tautology, a contradiction, or contingent:
(p∧q)→[(p∨r)↔(q∨r)]
Solution
To determine whether the given statement is a tautology, a contradiction, or
contingent, we will construct a truth table for the statement.
Step 1: Create the truth table for the statement.
p q r p ∧q p ∨r q ∨r(p∨r)↔(q∨r) (p∧q)→[(p∨r)↔(q∨r)]
T T T T T T T T
T T F T T T T T
T F T F T T T T
T F F F T F F T
F T T F T T T T
F T F F F T T T
F F T F T T T T
F F F F F F T T
Since the final column has all entries as true, the given statement is a tau-
tology.
Question 17
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using propositional calculus.
12
Solution
To show that the compound proposition is a tautology, we will construct a truth
table and verify that the resulting column under the main connective →consists
of all T’s.
Step 1: Create a truth table for the given proposition
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
Step 2: Analyze the truth values In the last column, we see that all the
truth values are T. Therefore, the compound proposition (p→q)∧(q→r)→
(p→r) is a tautology.
Question 18
Question
Let pand qbe propositions. Show that (p∧q)∨(¬p∧ ¬q) is logically equivalent
to p↔q.
Solution
To show that (p∧q)∨(¬p∧ ¬q) is logically equivalent to p↔q, we will first
simplify (p∧q)∨(¬p∧ ¬q) using logical equivalences, and then show that it is
equivalent to p↔qusing a truth table.
Step 1: Simplify (p∧q)∨(¬p∧ ¬q)
By distributive law: (p∧q)∨(¬p∧ ¬q)≡(p∨ ¬p)∧(p∨ ¬q)∧(q∨ ¬p)∧(q∨ ¬q)
By tautology: (p∨ ¬p)≡true, (q∨ ¬q)≡true
Therefore, the expression simplifies to: (p∨ ¬q)∧(q∨ ¬p).
Step 2: Construct Truth Table for ((p∧q)∨(¬p∧ ¬q)) ↔(p↔q)
p q p ∧q¬p¬q(p∧q)∨(¬p∧ ¬q)p↔q
T T T F F T T
T F F F T T F
F T F T F T F
F F F T T T T
Step 3: Analyze the Truth Table
From the truth table, we see that ((p∧q)∨(¬p∧ ¬q)) ↔(p↔q) has the same
13
truth values for all combinations of pand q. Therefore, we have shown that
(p∧q)∨(¬p∧ ¬q) is logically equivalent to p↔q.
Question 19
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 will construct
truth tables for both expressions and show that they have the same truth values
for all possible truth values of p,q, and r.
Step 1: Construct the 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: Construct the 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: Conclusion By comparing the truth values of (p∧q)∨(p∧r)
and p∧(q∨r) in the truth tables, we can see that they are indeed logically
equivalent for all possible truth values of p,q, and r. Therefore, (p∧q)∨(p∧r)
is logically equivalent to p∧(q∨r).
14
Question 20
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 to examine all possible combinations of truth values for p,q, and r.
p q r p →q q →r(p→q)∧(q→r)p→r
T T T T T T T
T T F T F F F
T F T F T F T
T F F F T F F
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 truth table, we can see that every row evaluates to true for the final
column (p→q)∧(q→r)→(p→r). Since the statement is true for all possible
truth values of p,q, and r, we can conclude that (p→q)∧(q→r)→(p→r)
is a tautology.
Question 21
Question
Let p,q, and rbe propositions. Show algebraically that (p∧q)∨ris logically
equivalent to (p∨r)∧(q∨r).
Solution
To show that (p∧q)∨ris logically equivalent to (p∨r)∧(q∨r), we need to show
that both statements have the same truth values for all possible truth values of
p,q, and r.
Step 1: Apply the distributive law on (p∧q)∨r:
(p∧q)∨r
= (p∨r)∧(q∨r)
by the distributive law of disjunction over conjunction, which states that p∨
(q∧r)≡(p∨q)∧(p∨r).
Therefore, (p∧q)∨ris logically equivalent to (p∨r)∧(q∨r).
15
Question 22
Question
Let p,q, and rbe propositions. Determine the truth value of the following
proposition: (p→q)∧(q→r)∧(r→p).
Solution
To determine the truth value of the proposition (p→q)∧(q→r)∧(r→p),
we consider the truth values of the propositions p,q, and rand apply the truth
table for implication (→) and conjunction (∧).
p q r p →q q →r r →p(p→q)∧(q→r)∧(r→p)
T T T T T T T ∧T∧T=T
T T F T F T T ∧F∧T=F
T F T F T T F ∧T∧T=F
T F F F T T F ∧T∧T=F
F T T T T F T ∧T∧F=F
F T F T F T T ∧F∧T=F
F F T T T F T ∧T∧F=F
F F F T T T T ∧T∧T=T
Therefore, the truth value of the proposition (p→q)∧(q→r)∧(r→p) is
false except when pis false, qis false, and ris false.
Question 23
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
logical equivalences to simplify the expressions and show that they are equal.
Step 1: Apply the Distributive Law on (p∧q)∨(p∧r):
(p∧q)∨(p∧r)≡p∧(q∨r)
Therefore, we have shown that the proposition (p∧q)∨(p∧r) is logically
equivalent to p∧(q∨r).
16
Question 24
Question
Prove the following logical equivalence using the laws of propositional logic:
(p∧q)∨ ¬(p∧r)≡(p∨ ¬r)∧(q∨ ¬r)
Solution
To prove the given logical equivalence, we will simplify both sides of the equation
using the laws of propositional logic until they are equivalent.
Step 1: Apply De Morgan’s Laws
(p∧q)∨ ¬(p∧r)
= (p∧q)∨(¬p∨ ¬r) (De Morgan’s Law)
Step 2: Distribute ∨over ∧
= (p∨ ¬p)∧(p∨ ¬r)∧(q∨ ¬p)∧(q∨ ¬r)
Step 3: Apply Complement Laws
=T∧(p∨ ¬r)∧(q∨ ¬p)∧(q∨ ¬r) (Complement Laws)
= (p∨ ¬r)∧(q∨ ¬p)∧(q∨ ¬r) (Identity Law)
Step 4: Apply Commutative Laws
= (p∨ ¬r)∧(q∨ ¬r)∧(q∨ ¬p)
= (p∨ ¬r)∧(q∨ ¬p)∧(q∨ ¬r) (Commutative Law)
Step 5: Applying Distributive Laws
= (p∨ ¬r)∧((q∨ ¬p)∧(q∨ ¬r))
= (p∨ ¬r)∧(q∨(¬p∧ ¬r)) (Distributive Law)
Step 6: Apply De Morgan’s Laws
= (p∨ ¬r)∧(q∨ ¬(p∨r)) (De Morgan’s Law)
Step 7: Reverse Steps Thus, we have shown that (p∧q)∨ ¬(p∧r)≡
(p∨ ¬r)∧(q∨ ¬r).
Question 25
Question
Let p, q, r be propositions. Show that (p→q)∧(q→r)→(p→r) is a tautology
using propositional calculus.
17
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will construct a
truth table and show that the output column is always true.
Step 1: Construct the truth table
p q r p →q q →r(p→q)∧(q→r)p→r
T T T T T T T
T T F T F F F
T F T F T F T
T F F F T F F
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
Step 2: Analyze the truth table
From the truth table, we can see that the column for (p→q)∧(q→r)→
(p→r) is always true. Thus, (p→q)∧(q→r)→(p→r) is a tautology.
Question 26
Question
Let p,q, and rbe propositions. Show that (p∧q)∨ris logically equivalent to
(p∨r)∧(q∨r) using propositional equivalences.
Solution
To show that (p∧q)∨ris logically equivalent to (p∨r)∧(q∨r), we need to
demonstrate that (p∧q)∨r≡(p∨r)∧(q∨r).
Step 1: Distributive law (OR over AND) By applying the distributive
law of propositional logic, we can expand (p∧q)∨r:
(p∧q)∨r= (p∨r)∧(q∨r)
Therefore, (p∧q)∨ris logically equivalent to (p∨r)∧(q∨r).
Question 27
Question
Let p,q, and rrepresent the following propositions: p: ”I will study hard”, q: ”I
will pass the exam”, and r: ”I will get an A”. Translate the following statement
into symbolic logic: ”If I study hard, then I will pass the exam and get an A.”
18
Solution
To translate the statement ”If I study hard, then I will pass the exam and get
an A” into symbolic logic, we can use implication and conjunction symbols. Let
p: ”I will study hard”, q: ”I will pass the exam”, and r: ”I will get an A”. The
given statement can be translated as: If p, then (q∧r) which can be represented
as p→(q∧r). Therefore, the symbolic logic representation of the statement is
p→(q∧r).
Question 28
Question
Let pand qbe propositions. Show that (p→q)↔(¬p∨q) is a tautology using
a truth table.
Solution
To show that (p→q)↔(¬p∨q) is a tautology, we will construct a truth table
and verify that the column for the logical equivalence evaluates to True for all
possible truth values of pand q.
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: Fill in the truth table columns for ¬pand ¬p∨q.
¬p: The negation of p.
¬p∨q: The disjunction (OR) of ¬pand q.
Step 2: Fill in the truth table column for p→q.
p→q: The conditional (IF...THEN) statement.
Step 3: Fill in the truth table column for the logical equivalence (p→q)↔
(¬p∨q).
(p→q)↔(¬p∨q): True if both sides have the same truth value, otherwise
False.
Since the column for the logical equivalence evaluates to True for all possible
truth values of pand q, we conclude that (p→q)↔(¬p∨q) is a tautology.
19
Question 29
Question
Let pand qbe the propositions ”I am happy” and ”I will go for a run”, respec-
tively. Express the proposition ”If I am not happy, then I will not go for a run”
using pand qin propositional logic.
Solution
To express the proposition ”If I am not happy, then I will not go for a run”
using pand q, we can write it as ¬p→ ¬q.
Step 1: Define the propositions: Let pbe ”I am happy” and qbe ”I will go
for a run”.
Step 2: Express the given proposition: The proposition ”If I am not happy,
then I will not go for a run” can be represented as ¬p→ ¬q.
Therefore, the proposition can be expressed as ¬p→ ¬q.
Question 30
Question
Let p, q, r be propositions. Show whether the statement (p∧q)∨ris logically
equivalent to p∨(q∨r).
Solution
To determine if the statement (p∧q)∨ris logically equivalent to p∨(q∨r), we
will construct truth tables for both statements and compare the truth values.
Step 1: Create a truth table for (p∧q)∨r:
p q r (p∧q) (p∧q)∨r
T T T T T
T T F T T
T F T F T
T F F F F
F T T F T
F T F F F
F F T F T
F F F F F
Step 2: Create a truth table for p∨(q∨r):
20
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 T
F T T T T
F T F T T
F F T T T
F F F F F
Step 3: Compare truth tables: Since the two truth tables are different,
we can conclude that (p∧q)∨ris not logically equivalent to p∨(q∨r).
Therefore, the statement (p∧q)∨ris not logically equivalent to p∨(q∨r).
Question 31
Question
Let p,q, and rbe propositions. Show that (p∧q)⇒ris logically equivalent to
(p⇒r)∨(q⇒r).
Solution
To show that (p∧q)⇒ris logically equivalent to (p⇒r)∨(q⇒r), we will
create truth tables for both statements and show that they have the same truth
values for all possible combinations of truth values for p,q, and r.
p q r p ∧q(p∧q)⇒r p ⇒r q ⇒r
T T T T T T T
T T F T F F F
T F T F T T T
T F F F T F T
F T T F T T T
F T F F T T F
F F T F T T T
F F F F T T T
From the truth table, we can see that (p∧q)⇒rand (p⇒r)∨(q⇒r)
have the same truth values for all possible combinations of truth values for p,
q, and r. Therefore, (p∧q)⇒ris logically equivalent to (p⇒r)∨(q⇒r).
21
Question 32
Question
Let p,q, and rbe propositions. Show that (p→ ¬q)→((p→q)→p) is a
tautology using a truth table.
Solution
To show that (p→ ¬q)→((p→q)→p) is a tautology, we need to show that
the compound proposition is true for all possible truth values of p,q, and r. We
will construct a truth table to demonstrate this.
p q ¬q p → ¬q p →q(p→ ¬q)→((p→q)→p)
T T F F T T
T F T T F T
F T F T T T
F F T T T T
Step 1: Fill in the columns for ¬q,p→ ¬q,p→q.
Step 2: Fill in the column for (p→ ¬q)→((p→q)→p) using the truth
values of p→ ¬q,p→q, and p.
Step 3: Identify that the final column is true for all rows in the truth table,
so (p→ ¬q)→((p→q)→p) is a tautology.
Question 33
Question
Let p,q, and rbe propositional variables. Prove or disprove the following
statement: [(p∧q)∨r]⇐⇒ [(p∨r)∧(q∨r)].
Solution
To prove or disprove the statement [(p∧q)∨r]⇐⇒ [(p∨r)∧(q∨r)], we can
show that the two sides are logically equivalent by using truth tables.
Step 1: Create a truth table for [(p∧q)∨r].
p q r (p∧q)∨r
T T T T
T T F F
T F T T
T F F F
F T T T
F T F F
F F T T
F F F F
22
Step 2: Create a truth table for [(p∨r)∧(q∨r)].
p q r p ∨r q ∨r(p∨r)∧(q∨r)
T T T T T T
T T F T T T
T F T T T T
T F F T F F
F T T T T T
F T F F T F
F F T T T T
F F F F T F
Step 3: Compare the truth values of [(p∧q)∨r]and [(p∨r)∧(q∨r)].
From the truth tables, we can see that [(p∧q)∨r] and [(p∨r)∧(q∨r)] do
not have the same truth values for all possible truth value assignments of p,q,
and r. Therefore, the statement [(p∧q)∨r]⇐⇒ [(p∨r)∧(q∨r)] is disproved.
Question 34
Question
Let p, q, r be propositional variables. Given the compound proposition:
(p→q)∧(q→r)∧(r→p)→(p∧q∧r)
Determine whether this compound proposition is a tautology, a contradic-
tion, or neither.
Solution
To determine whether the compound proposition is a tautology, a contradiction,
or neither, we will construct a truth table and check all possible truth values of
p,q, and r.
p q r p →q q →r r →p(p→q)∧(q→r)∧(r→p)p∧q∧r
T T T T T T T T
T T F T F T F F
T F T F T T F F
T F F F T T F F
F T T T T F F F
F T F T F T F F
F F T T T T T F
F F F T T T T F
From the truth table, we see that the compound proposition is only true
when p,q, and rare all false. Therefore, the compound proposition is a contra-
diction.
23
Step 6: Apply commutativity and association:
((p∨ ¬q)∨(¬p∨r)) ∧((p∨ ¬q)∨r)≡(p∨ ¬q∨ ¬p∨r)∧(p∨ ¬q∨r)
Step 7: Apply idempotent law:
(p∨ ¬q∨ ¬p∨r)∧(p∨ ¬q∨r)≡(p∨ ¬p∨ ¬q∨r)∧(p∨ ¬q∨r)
Step 8: Apply negation law ¬p∨p≡True:
(p∨ ¬p∨ ¬q∨r)∧(p∨ ¬q∨r)≡(True ∨ ¬q∨r)∧(p∨ ¬q∨r)
Step 9: Apply domination law True ∨A≡True:
(True ∨ ¬q∨r)∧(p∨ ¬q∨r)≡True ∧(p∨ ¬q∨r)
Step 10: Apply identity law True ∧A≡A:
True ∧(p∨ ¬q∨r)≡p∨ ¬q∨r
Since p∨ ¬q∨ris always true for any values of p,q, and r, the original
statement is a tautology.
Question 2
Question
Let p,q, and rbe propositions. Show that the proposition (p→q)→ris
logically equivalent to p→(q→r).
Solution
To show that the propositions are logically equivalent, we can construct truth
tables for both propositions and show that the output columns are the same for
all possible combinations of truth values for p,q, and r.
Step 1: Create the 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 T T
F T F T F
F F T T T
F F F T F
Step 2: Create the truth table for p→(q→r).
2
p q r q →r p →(q→r)
T T T T T
T T F F T
T F T T T
T F F T T
F T T T T
F T F T T
F F T T T
F F F T T
Step 3: Conclusion
By comparing the output columns of the truth tables for (p→q)→rand
p→(q→r), we can see that the two propositions are logically equivalent as
the output values for all possible truth value combinations are the same.
Therefore, (p→q)→ris logically equivalent to p→(q→r).
Question 3
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 and verify that the final column is always true.
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
Since the final column evaluates to true for all possible truth values of p,q,
and r, we can conclude that (p→q)∧(q→r)→(p→r) is a tautology.
3
Question 4
Question
Let p, q, r be propositions with the following constraints:
(p∧q) =⇒r
p=⇒q
r=⇒ ¬q
Determine whether the proposition (p∧q) =⇒ ¬ris a logical consequence of
the given constraints.
Solution
Step 1: Use the contrapositive of the third constraint to get ¬¬q=⇒ ¬r. This
simplifies to q=⇒ ¬r.
Step 2: Use the second constraint to get ¬p∨q.
Step 3: Use the first constraint and the results from Step 1 and Step 2 to
find (p∧q) =⇒r, which simplifies to ¬r=⇒ ¬(p∧q).
Step 4: Converting this result to CNF format, we get (p∨ ¬r)∧(q∨ ¬r).
Step 5: Combine the results from Step 3 and Step 4 to identify whether
the proposition (p∧q) =⇒ ¬ris a logical consequence. Since (p∧q)∧ ¬r
does not appear in the CNF format of the given constraints, the proposition
(p∧q) =⇒ ¬ris not a logical consequence.
Question 5
Question
Let p,q, and rbe propositions. Determine whether the following logical equiv-
alence is true or false: (p→q)→r≡p→(q→r).
Solution
We will determine the truth value of both sides of the logical equivalence by
constructing truth tables.
4
Step 1: Construct the truth table for (p→q)→r:
p q r (p→q)→r
T T T T
T T F F
T F T T
T F F F
F T T T
F T F T
F F T T
F F F T
Step 2: Construct the truth table for p→(q→r):
p q r p →(q→r)
T T T T
T T F F
T F T T
T F F T
F T T T
F T F T
F F T T
F F F T
Step 3: Compare the two truth tables: From the truth tables, we
can see that the two logical expressions (p→q)→rand p→(q→r) have
different truth values for some combinations of p,q, and r. Therefore, the logical
equivalence is false.
Question 6
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using truth tables.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will construct
a truth table for the entire expression and show that the truth values of the
compound proposition are always true.
5
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
In the truth table, we see that the final column evaluates to true for all
possible truth values of p,q, and r. Therefore, (p→q)∧(q→r)→(p→r) is
a tautology.
Question 7
Question
Let p,q, and rbe propositional variables representing the following statements:
p: It is raining. q: The grass is wet. r: The sprinklers are on.
Write the following statement in symbolic logic: ”If it is not raining and the
grass is wet, then the sprinklers are not on.”
Solution
To express the given statement in symbolic logic, we can use the logical operators
¬(negation), ∧(conjunction), and →(implication).
Step 1: Identify the components of the statement Let’s represent the
components of the statement in symbolic logic: Negation of p:¬p q:qNegation
of r:¬r
Step 2: Formulate the logical statement The given statement can be
translated into symbolic logic as:
(¬p∧q)→ ¬r
Therefore, the symbolic representation of the statement ”If it is not raining
and the grass is wet, then the sprinklers are not on.” is (¬p∧q)→ ¬r.
Question 8
Question
Let p,q, and rbe propositions. Suppose the proposition (p⇒q)⇒ris false,
and the proposition p⇒(q⇒r) is true. Determine the truth values of p,q,
and r.
6
Solution
Step 1: Use the fact that (p⇒q)⇒ris false to determine the truth values of
p,q, and r. If (p⇒q)⇒ris false, this means that (p⇒q) is true while ris
false. Since the implication (p⇒q) is true and ris false, then pmust be true
while qcan be either true or false.
Step 2: Use the fact that p⇒(q⇒r) is true to further determine the truth
values of p,q, and r. Since p⇒(q⇒r) is true and we already know that pis
true, this implies that q⇒ris true. If qis true, then rmust also be true in
order for q⇒rto be true. Therefore, the truth values of p,q, and rare: pis
true, qis true, and ris false.
Question 9
Question
Let p,q, and rbe propositions. Prove the following logical equivalence using
propositional calculus laws:
(p→q)∧(q→r)↔(p→r)
Solution
To prove (p→q)∧(q→r)↔(p→r), we can first prove that (p→q)∧(q→
r)→(p→r) and then prove (p→r)→(p→q)∧(q→r).
Step 1: Prove (p→q)∧(q→r)→(p→r)
(p→q)∧(q→r)
≡(¬p∨q)∧(¬q∨r) [Implication rule]
≡(¬p∧ ¬q)∨(¬p∧r)∨(q∧ ¬q)∨(q∧r) [Distribution]
≡¬p∧r∨(q∧ ¬q) [Simplify]
≡¬p∧r∨F[Contradiction]
≡¬p∧r[Identity]
≡p→r[Implication rule]
7
Step 2: Prove (p→r)→(p→q)∧(q→r)
p→r
≡¬p∨r[Implication rule]
Let’s prove the first part: p→q
Assume p
T hen r [From p→r]
Therefore, p→q
Let’s prove the second part: q→r
Assume q
T hen r [From p→r]
Therefore, q→r
Since p →q and q →r hold, we have p →q∧q→r
Therefore, we have shown that (p→q)∧(q→r)↔(p→r) is true using
propositional calculus laws.
Question 10
Question
Let p,q, and rbe propositions. Show that the following statement is a tautology:
(p→q)∨(q→r)∨(r→p).
Solution
To show that the given statement is a tautology, we need to show that it is true
for all possible truth values of p,q, and r. We can do this by constructing a
truth table for the statement.
Step 1: Construct a truth table for the statement.
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 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
Step 2: Analyze the truth table.
From the truth table, we see that the statement (p→q)∨(q→r)∨(r→p)
evaluates to true for all possible truth values of p,q, and r. Therefore, the
statement is a tautology.
Question 11
Question
Let p,q, and rbe propositions with the following truth values: pis false, qis
true, ris false.
Negate the proposition (p∧q)∨ ¬r.
Solution
To negate the proposition (p∧q)∨ ¬r, we will first find its truth value and then
apply the negation.
Step 1: Find the truth value of (p∧q)∨ ¬r: Given that: pis false, qis true,
ris false.
Therefore, p∧qis false ∧true = false, and ¬ris ¬false = true.
Then, we have (p∧q)∨ ¬r= false ∨true = true.
Step 2: Negate the truth value of (p∧q)∨ ¬r: The negation of true is false.
Hence, the negation of the proposition (p∧q)∨ ¬ris false .
Question 12
Question
Prove the following statement or provide a counterexample:
For all integers aand b, if ais odd and bis even, then a2+bis odd.
9
Solution
To prove the statement, we will use a direct proof.
Step 1: Assume ais an odd integer and bis an even integer.
Let a= 2k+ 1 for some integer k(by definition of odd integers) and b= 2m
for some integer m(by definition of even integers).
Step 2: Find a2
a2= (2k+ 1)2= 4k2+ 4k+ 1 = 2(2k2+ 2k)+1
Thus, a2is also odd.
Step 3: Determine the sum a2+b
a2+b= 2(2k2+ 2k)+1+2m= 2(2k2+ 2k+m)+1
Since 2k2+ 2k+mis an integer, a2+bis odd.
Step 4: Conclusion
Therefore, for all integers aand b, if ais odd and bis even, then a2+bis
odd.
Question 13
Question
Let p,q, and rbe statements. 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 need to show 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
T T T T T T T
T T F T F F F
T F T F T F T
T F F F T F F
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
Since the final column of the truth table is always true, (p→q)∧(q→r)→
(p→r) is a tautology.
10
Question 14
Question
Let p,q, and rbe propositions. Show that (p∧q)→ris logically equivalent to
(p→r)∨(q→r).
Solution
To show that (p∧q)→ris logically equivalent to (p→r)∨(q→r), we will
construct truth tables for both expressions and show that the resulting columns
match.
Step 1: Construct the truth table for (p∧q)→r:
p q r (p∧q)→r
T T T T
T T F F
T F T T
T F F F
F T T T
F T F T
F F T T
F F F T
Step 2: Construct the truth table for (p→r)∨(q→r):
p q r p →r q →r(p→r)∨(q→r)
T T T T T T
T T F F T T
T F T T 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 3: Conclusion: From the truth tables, we can see that the columns
for (p∧q)→rand (p→r)∨(q→r) are identical. Therefore, we have shown
that (p∧q)→ris logically equivalent to (p→r)∨(q→r).
Question 15
Question
Let prepresent ”It is raining” and qrepresent ”The roads are wet.” Write the
logical statement for the following scenario: ”If it is raining, then the roads are
wet.”
11
Solution
To write the logical statement for the scenario ”If it is raining, then the roads
are wet,” we need to express it using logical connectives.
Step 1: Define the propositions: Let prepresent ”It is raining” and qrepre-
sent ”The roads are wet.”
Step 2: Construct the logical statement: The logical statement for the sce-
nario ”If it is raining, then the roads are wet.” can be written as p→q.
Therefore, the logical statement for the scenario is: p→q.
Question 16
Question
Let p,q, and rbe propositions. Determine whether the following statement is
a tautology, a contradiction, or contingent:
(p∧q)→[(p∨r)↔(q∨r)]
Solution
To determine whether the given statement is a tautology, a contradiction, or
contingent, we will construct a truth table for the statement.
Step 1: Create the truth table for the statement.
p q r p ∧q p ∨r q ∨r(p∨r)↔(q∨r) (p∧q)→[(p∨r)↔(q∨r)]
T T T T T T T T
T T F T T T T T
T F T F T T T T
T F F F T F F T
F T T F T T T T
F T F F F T T T
F F T F T T T T
F F F F F F T T
Since the final column has all entries as true, the given statement is a tau-
tology.
Question 17
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using propositional calculus.
12
Solution
To show that the compound proposition is a tautology, we will construct a truth
table and verify that the resulting column under the main connective →consists
of all T’s.
Step 1: Create a truth table for the given proposition
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
Step 2: Analyze the truth values In the last column, we see that all the
truth values are T. Therefore, the compound proposition (p→q)∧(q→r)→
(p→r) is a tautology.
Question 18
Question
Let pand qbe propositions. Show that (p∧q)∨(¬p∧ ¬q) is logically equivalent
to p↔q.
Solution
To show that (p∧q)∨(¬p∧ ¬q) is logically equivalent to p↔q, we will first
simplify (p∧q)∨(¬p∧ ¬q) using logical equivalences, and then show that it is
equivalent to p↔qusing a truth table.
Step 1: Simplify (p∧q)∨(¬p∧ ¬q)
By distributive law: (p∧q)∨(¬p∧ ¬q)≡(p∨ ¬p)∧(p∨ ¬q)∧(q∨ ¬p)∧(q∨ ¬q)
By tautology: (p∨ ¬p)≡true, (q∨ ¬q)≡true
Therefore, the expression simplifies to: (p∨ ¬q)∧(q∨ ¬p).
Step 2: Construct Truth Table for ((p∧q)∨(¬p∧ ¬q)) ↔(p↔q)
p q p ∧q¬p¬q(p∧q)∨(¬p∧ ¬q)p↔q
T T T F F T T
T F F F T T F
F T F T F T F
F F F T T T T
Step 3: Analyze the Truth Table
From the truth table, we see that ((p∧q)∨(¬p∧ ¬q)) ↔(p↔q) has the same
13
truth values for all combinations of pand q. Therefore, we have shown that
(p∧q)∨(¬p∧ ¬q) is logically equivalent to p↔q.
Question 19
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 will construct
truth tables for both expressions and show that they have the same truth values
for all possible truth values of p,q, and r.
Step 1: Construct the 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: Construct the 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: Conclusion By comparing the truth values of (p∧q)∨(p∧r)
and p∧(q∨r) in the truth tables, we can see that they are indeed logically
equivalent for all possible truth values of p,q, and r. Therefore, (p∧q)∨(p∧r)
is logically equivalent to p∧(q∨r).
14
Question 20
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 to examine all possible combinations of truth values for p,q, and r.
p q r p →q q →r(p→q)∧(q→r)p→r
T T T T T T T
T T F T F F F
T F T F T F T
T F F F T F F
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 truth table, we can see that every row evaluates to true for the final
column (p→q)∧(q→r)→(p→r). Since the statement is true for all possible
truth values of p,q, and r, we can conclude that (p→q)∧(q→r)→(p→r)
is a tautology.
Question 21
Question
Let p,q, and rbe propositions. Show algebraically that (p∧q)∨ris logically
equivalent to (p∨r)∧(q∨r).
Solution
To show that (p∧q)∨ris logically equivalent to (p∨r)∧(q∨r), we need to show
that both statements have the same truth values for all possible truth values of
p,q, and r.
Step 1: Apply the distributive law on (p∧q)∨r:
(p∧q)∨r
= (p∨r)∧(q∨r)
by the distributive law of disjunction over conjunction, which states that p∨
(q∧r)≡(p∨q)∧(p∨r).
Therefore, (p∧q)∨ris logically equivalent to (p∨r)∧(q∨r).
15
Question 22
Question
Let p,q, and rbe propositions. Determine the truth value of the following
proposition: (p→q)∧(q→r)∧(r→p).
Solution
To determine the truth value of the proposition (p→q)∧(q→r)∧(r→p),
we consider the truth values of the propositions p,q, and rand apply the truth
table for implication (→) and conjunction (∧).
p q r p →q q →r r →p(p→q)∧(q→r)∧(r→p)
T T T T T T T ∧T∧T=T
T T F T F T T ∧F∧T=F
T F T F T T F ∧T∧T=F
T F F F T T F ∧T∧T=F
F T T T T F T ∧T∧F=F
F T F T F T T ∧F∧T=F
F F T T T F T ∧T∧F=F
F F F T T T T ∧T∧T=T
Therefore, the truth value of the proposition (p→q)∧(q→r)∧(r→p) is
false except when pis false, qis false, and ris false.
Question 23
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
logical equivalences to simplify the expressions and show that they are equal.
Step 1: Apply the Distributive Law on (p∧q)∨(p∧r):
(p∧q)∨(p∧r)≡p∧(q∨r)
Therefore, we have shown that the proposition (p∧q)∨(p∧r) is logically
equivalent to p∧(q∨r).
16
Question 24
Question
Prove the following logical equivalence using the laws of propositional logic:
(p∧q)∨ ¬(p∧r)≡(p∨ ¬r)∧(q∨ ¬r)
Solution
To prove the given logical equivalence, we will simplify both sides of the equation
using the laws of propositional logic until they are equivalent.
Step 1: Apply De Morgan’s Laws
(p∧q)∨ ¬(p∧r)
= (p∧q)∨(¬p∨ ¬r) (De Morgan’s Law)
Step 2: Distribute ∨over ∧
= (p∨ ¬p)∧(p∨ ¬r)∧(q∨ ¬p)∧(q∨ ¬r)
Step 3: Apply Complement Laws
=T∧(p∨ ¬r)∧(q∨ ¬p)∧(q∨ ¬r) (Complement Laws)
= (p∨ ¬r)∧(q∨ ¬p)∧(q∨ ¬r) (Identity Law)
Step 4: Apply Commutative Laws
= (p∨ ¬r)∧(q∨ ¬r)∧(q∨ ¬p)
= (p∨ ¬r)∧(q∨ ¬p)∧(q∨ ¬r) (Commutative Law)
Step 5: Applying Distributive Laws
= (p∨ ¬r)∧((q∨ ¬p)∧(q∨ ¬r))
= (p∨ ¬r)∧(q∨(¬p∧ ¬r)) (Distributive Law)
Step 6: Apply De Morgan’s Laws
= (p∨ ¬r)∧(q∨ ¬(p∨r)) (De Morgan’s Law)
Step 7: Reverse Steps Thus, we have shown that (p∧q)∨ ¬(p∧r)≡
(p∨ ¬r)∧(q∨ ¬r).
Question 25
Question
Let p, q, r be propositions. Show that (p→q)∧(q→r)→(p→r) is a tautology
using propositional calculus.
17
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will construct a
truth table and show that the output column is always true.
Step 1: Construct the truth table
p q r p →q q →r(p→q)∧(q→r)p→r
T T T T T T T
T T F T F F F
T F T F T F T
T F F F T F F
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
Step 2: Analyze the truth table
From the truth table, we can see that the column for (p→q)∧(q→r)→
(p→r) is always true. Thus, (p→q)∧(q→r)→(p→r) is a tautology.
Question 26
Question
Let p,q, and rbe propositions. Show that (p∧q)∨ris logically equivalent to
(p∨r)∧(q∨r) using propositional equivalences.
Solution
To show that (p∧q)∨ris logically equivalent to (p∨r)∧(q∨r), we need to
demonstrate that (p∧q)∨r≡(p∨r)∧(q∨r).
Step 1: Distributive law (OR over AND) By applying the distributive
law of propositional logic, we can expand (p∧q)∨r:
(p∧q)∨r= (p∨r)∧(q∨r)
Therefore, (p∧q)∨ris logically equivalent to (p∨r)∧(q∨r).
Question 27
Question
Let p,q, and rrepresent the following propositions: p: ”I will study hard”, q: ”I
will pass the exam”, and r: ”I will get an A”. Translate the following statement
into symbolic logic: ”If I study hard, then I will pass the exam and get an A.”
18
Solution
To translate the statement ”If I study hard, then I will pass the exam and get
an A” into symbolic logic, we can use implication and conjunction symbols. Let
p: ”I will study hard”, q: ”I will pass the exam”, and r: ”I will get an A”. The
given statement can be translated as: If p, then (q∧r) which can be represented
as p→(q∧r). Therefore, the symbolic logic representation of the statement is
p→(q∧r).
Question 28
Question
Let pand qbe propositions. Show that (p→q)↔(¬p∨q) is a tautology using
a truth table.
Solution
To show that (p→q)↔(¬p∨q) is a tautology, we will construct a truth table
and verify that the column for the logical equivalence evaluates to True for all
possible truth values of pand q.
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: Fill in the truth table columns for ¬pand ¬p∨q.
¬p: The negation of p.
¬p∨q: The disjunction (OR) of ¬pand q.
Step 2: Fill in the truth table column for p→q.
p→q: The conditional (IF...THEN) statement.
Step 3: Fill in the truth table column for the logical equivalence (p→q)↔
(¬p∨q).
(p→q)↔(¬p∨q): True if both sides have the same truth value, otherwise
False.
Since the column for the logical equivalence evaluates to True for all possible
truth values of pand q, we conclude that (p→q)↔(¬p∨q) is a tautology.
19
Question 29
Question
Let pand qbe the propositions ”I am happy” and ”I will go for a run”, respec-
tively. Express the proposition ”If I am not happy, then I will not go for a run”
using pand qin propositional logic.
Solution
To express the proposition ”If I am not happy, then I will not go for a run”
using pand q, we can write it as ¬p→ ¬q.
Step 1: Define the propositions: Let pbe ”I am happy” and qbe ”I will go
for a run”.
Step 2: Express the given proposition: The proposition ”If I am not happy,
then I will not go for a run” can be represented as ¬p→ ¬q.
Therefore, the proposition can be expressed as ¬p→ ¬q.
Question 30
Question
Let p, q, r be propositions. Show whether the statement (p∧q)∨ris logically
equivalent to p∨(q∨r).
Solution
To determine if the statement (p∧q)∨ris logically equivalent to p∨(q∨r), we
will construct truth tables for both statements and compare the truth values.
Step 1: Create a truth table for (p∧q)∨r:
p q r (p∧q) (p∧q)∨r
T T T T T
T T F T T
T F T F T
T F F F F
F T T F T
F T F F F
F F T F T
F F F F F
Step 2: Create a truth table for p∨(q∨r):
20
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 T
F T T T T
F T F T T
F F T T T
F F F F F
Step 3: Compare truth tables: Since the two truth tables are different,
we can conclude that (p∧q)∨ris not logically equivalent to p∨(q∨r).
Therefore, the statement (p∧q)∨ris not logically equivalent to p∨(q∨r).
Question 31
Question
Let p,q, and rbe propositions. Show that (p∧q)⇒ris logically equivalent to
(p⇒r)∨(q⇒r).
Solution
To show that (p∧q)⇒ris logically equivalent to (p⇒r)∨(q⇒r), we will
create truth tables for both statements and show that they have the same truth
values for all possible combinations of truth values for p,q, and r.
p q r p ∧q(p∧q)⇒r p ⇒r q ⇒r
T T T T T T T
T T F T F F F
T F T F T T T
T F F F T F T
F T T F T T T
F T F F T T F
F F T F T T T
F F F F T T T
From the truth table, we can see that (p∧q)⇒rand (p⇒r)∨(q⇒r)
have the same truth values for all possible combinations of truth values for p,
q, and r. Therefore, (p∧q)⇒ris logically equivalent to (p⇒r)∨(q⇒r).
21
Question 32
Question
Let p,q, and rbe propositions. Show that (p→ ¬q)→((p→q)→p) is a
tautology using a truth table.
Solution
To show that (p→ ¬q)→((p→q)→p) is a tautology, we need to show that
the compound proposition is true for all possible truth values of p,q, and r. We
will construct a truth table to demonstrate this.
p q ¬q p → ¬q p →q(p→ ¬q)→((p→q)→p)
T T F F T T
T F T T F T
F T F T T T
F F T T T T
Step 1: Fill in the columns for ¬q,p→ ¬q,p→q.
Step 2: Fill in the column for (p→ ¬q)→((p→q)→p) using the truth
values of p→ ¬q,p→q, and p.
Step 3: Identify that the final column is true for all rows in the truth table,
so (p→ ¬q)→((p→q)→p) is a tautology.
Question 33
Question
Let p,q, and rbe propositional variables. Prove or disprove the following
statement: [(p∧q)∨r]⇐⇒ [(p∨r)∧(q∨r)].
Solution
To prove or disprove the statement [(p∧q)∨r]⇐⇒ [(p∨r)∧(q∨r)], we can
show that the two sides are logically equivalent by using truth tables.
Step 1: Create a truth table for [(p∧q)∨r].
p q r (p∧q)∨r
T T T T
T T F F
T F T T
T F F F
F T T T
F T F F
F F T T
F F F F
22
Step 2: Create a truth table for [(p∨r)∧(q∨r)].
p q r p ∨r q ∨r(p∨r)∧(q∨r)
T T T T T T
T T F T T T
T F T T T T
T F F T F F
F T T T T T
F T F F T F
F F T T T T
F F F F T F
Step 3: Compare the truth values of [(p∧q)∨r]and [(p∨r)∧(q∨r)].
From the truth tables, we can see that [(p∧q)∨r] and [(p∨r)∧(q∨r)] do
not have the same truth values for all possible truth value assignments of p,q,
and r. Therefore, the statement [(p∧q)∨r]⇐⇒ [(p∨r)∧(q∨r)] is disproved.
Question 34
Question
Let p, q, r be propositional variables. Given the compound proposition:
(p→q)∧(q→r)∧(r→p)→(p∧q∧r)
Determine whether this compound proposition is a tautology, a contradic-
tion, or neither.
Solution
To determine whether the compound proposition is a tautology, a contradiction,
or neither, we will construct a truth table and check all possible truth values of
p,q, and r.
p q r p →q q →r r →p(p→q)∧(q→r)∧(r→p)p∧q∧r
T T T T T T T T
T T F T F T F F
T F T F T T F F
T F F F T T F F
F T T T T F F F
F T F T F T F F
F F T T T T T F
F F F T T T T F
From the truth table, we see that the compound proposition is only true
when p,q, and rare all false. Therefore, the compound proposition is a contra-
diction.
23
Question 35
Question
Let p,q, and rbe propositional variables. Determine whether the following
argument is valid or invalid:
p∧(q∨r),¬q, ¬r
¬p
Solution
To determine whether the argument is valid, we will use the method of proof
by contradiction.
Step 1: Assume that the premises p∧(q∨r), ¬q, and ¬rare true, but the
conclusion ¬pis false.
Step 2: According to De Morgan’s Law, ¬qand ¬rcan be written as q→p
and r→prespectively.
Step 3: From p∧(q∨r) and q→p, we can infer p∧(q∨r)→pusing
simplification.
Step 4: By Modus Ponens on p∧(q∨r)→pand p, we have p.
Step 5: Since we have derived pfrom our assumptions, this means the
assumption that ¬pis false is incorrect. Therefore, ¬pmust be true.
Step 6: Since we arrived at a valid conclusion while assuming the premises
are true and the conclusion is false, the argument is valid.
24
