Answer Key
Logic and Propositional Calculus Question Bank Set 5
-
University:
Liberty University -
Course:
MATH 250 | Introduction to Discrete Mathematics Academic year:
2024
-
Views:
168
Pages:
132
Author:
Jesly V.
MATH 250 - INTRODUCTION TO
DISCRETE MATHEMATICS - Logic
and Propositional Calculus
Question Bank - Set 5
Liberty University
Question 1
Question
Let p, q, and r be 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 ∨ r is always true for any values of p, q, and r, the original
statement is a tautology.
Question 2
Question
Let p, q, and r be propositions. Show that the proposition (p → q) → r is
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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p → q)
T
T
F
F
T
T
T
T
(p → q) → r
T
F
T
T
T
F
T
F
Step 2: Create the truth table for p → (q → r).
2 p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
q→r
T
F
T
T
T
T
T
T
p → (q → r)
T
T
T
T
T
T
T
T
Step 3: Conclusion
By comparing the output columns of the truth tables for (p → q) → r and
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) → r is logically equivalent to p → (q → r).
Question 3
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
p→r
T
F
T
F
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
T
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) =⇒ ¬r is 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) =⇒ ¬r is a logical consequence. Since (p ∧ q) ∧ ¬r
does not appear in the CNF format of the given constraints, the proposition
(p ∧ q) =⇒ ¬r is not a logical consequence.
Question 5
Question
Let p, q, and r be propositions. Determine whether the following logical equivalence 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p → q) → r
T
F
T
F
T
T
T
T
Step 2: Construct the truth table for p → (q → r):
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p → (q → r)
T
F
T
T
T
T
T
T
Step 3: Compare the two truth tables: From the truth tables, we
can see that the two logical expressions (p → q) → r and 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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p → q)
T
T
F
F
T
T
T
T
(q → r)
T
F
T
T
T
F
T
T
(p → r)
T
F
T
F
T
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 r be 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: q Negation
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 r be propositions. Suppose the proposition (p ⇒ q) ⇒ r is 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) ⇒ r is false to determine the truth values of
p, q, and r. If (p ⇒ q) ⇒ r is false, this means that (p ⇒ q) is true while r is
false. Since the implication (p ⇒ q) is true and r is false, then p must be true
while q can 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 p is
true, this implies that q ⇒ r is true. If q is true, then r must also be true in
order for q ⇒ r to be true. Therefore, the truth values of p, q, and r are: p is
true, q is true, and r is false.
Question 9
Question
Let p, q, and r be 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)
≡¬p ∧ r ∨ (q ∧ ¬q)
≡¬p ∧ r ∨ F
[Simplify]
[Contradiction]
≡¬p ∧ r
[Identity]
≡p → r
[Implication rule]
7
[Distribution] 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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
r→p
T
T
T
T
F
T
T
T
(p → q) ∨ (q → r) ∨ (r → p)
T
T
T
T
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 r be propositions with the following truth values: p is false, q is
true, r is 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: p is false, q is true,
r is false.
Therefore, p ∧ q is false ∧ true = false, and ¬r is ¬ 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) ∨ ¬r is f alse .
Question 12
Question
Prove the following statement or provide a counterexample:
For all integers a and b, if a is odd and b is even, then a2 + b is odd.
9 Solution
To prove the statement, we will use a direct proof.
Step 1: Assume a is an odd integer and b is 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 = 4k 2 + 4k + 1 = 2(2k 2 + 2k) + 1
Thus, a2 is also odd.
Step 3: Determine the sum a2 + b
a2 + b = 2(2k 2 + 2k) + 1 + 2m = 2(2k 2 + 2k + m) + 1
Since 2k 2 + 2k + m is an integer, a2 + b is odd.
Step 4: Conclusion
Therefore, for all integers a and b, if a is odd and b is even, then a2 + b is
odd.
Question 13
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
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 r be propositions. Show that (p ∧ q) → r is logically equivalent to
(p → r) ∨ (q → r).
Solution
To show that (p ∧ q) → r is 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p ∧ q) → r
T
F
T
F
T
T
T
T
Step 2: Construct the truth table for (p → r) ∨ (q → r):
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→r
T
F
T
F
T
T
T
T
q→r
T
T
T
T
T
F
T
T
(p → r) ∨ (q → r)
T
T
T
T
T
T
T
T
Step 3: Conclusion: From the truth tables, we can see that the columns
for (p ∧ q) → r and (p → r) ∨ (q → r) are identical. Therefore, we have shown
that (p ∧ q) → r is logically equivalent to (p → r) ∨ (q → r).
Question 15
Question
Let p represent ”It is raining” and q represent ”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 p represent ”It is raining” and q represent ”The roads are wet.”
Step 2: Construct the logical statement: The logical statement for the scenario ”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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∧q
T
T
F
F
F
F
F
F
p∨r
T
T
T
T
T
F
T
F
q∨r
T
T
T
F
T
T
T
F
(p ∨ r) ↔ (q ∨ r)
T
T
T
F
T
T
T
T
(p ∧ q) → [(p ∨ r) ↔ (q ∨ r)]
T
T
T
T
T
T
T
T
Since the final column has all entries as true, the given statement is a tautology.
Question 17
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
F
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
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 p and q be 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 ↔ q using 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
T
T
F
F
q
T
F
T
F
p∧q
T
F
F
F
¬p
F
F
T
T
¬q
F
T
F
T
(p ∧ q) ∨ (¬p ∧ ¬q)
T
T
T
T
p↔q
T
F
F
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 p and q. Therefore, we have shown that
(p ∧ q) ∨ (¬p ∧ ¬q) is logically equivalent to p ↔ q.
Question 19
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
p∧q
T
T
F
F
F
F
F
F
r
T
F
T
F
T
F
T
F
p∧r
T
F
T
F
F
F
F
F
(p ∧ q) ∨ (p ∧ r)
T
T
T
F
F
F
F
F
Step 2: Construct the truth table for p ∧ (q ∨ r)
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
q∨r
T
T
T
F
T
T
T
F
p ∧ (q ∨ r)
T
T
T
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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
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 r be propositions. Show algebraically that (p ∧ q) ∨ r is logically
equivalent to (p ∨ r) ∧ (q ∨ r).
Solution
To show that (p ∧ q) ∨ r is 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) ∨ r is logically equivalent to (p ∨ r) ∧ (q ∨ r).
15 Question 22
Question
Let p, q, and r be 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 r and apply the truth
table for implication (→) and conjunction (∧).
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
r→p
T
T
T
T
F
T
F
T
(p → q) ∧ (q
T ∧T
T ∧F
F ∧T
F ∧T
T ∧T
T ∧F
T ∧T
T ∧T
→ r) ∧ (r → p)
∧T =T
∧T =F
∧T =F
∧T =F
∧F =F
∧T =F
∧F =F
∧T =T
Therefore, the truth value of the proposition (p → q) ∧ (q → r) ∧ (r → p) is
false except when p is false, q is false, and r is false.
Question 23
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
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 r be propositions. Show that (p ∧ q) ∨ r is logically equivalent to
(p ∨ r) ∧ (q ∨ r) using propositional equivalences.
Solution
To show that (p ∧ q) ∨ r is 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) ∨ r is logically equivalent to (p ∨ r) ∧ (q ∨ r).
Question 27
Question
Let p, q, and r represent 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 p and q be 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 p and q.
p
T
T
F
F
q
T
F
T
F
¬p
F
F
T
T
¬p ∨ q
T
F
T
T
p→q
T
F
T
T
(p → q) ↔ (¬p ∨ q)
T
T
T
T
Step 1: Fill in the truth table columns for ¬p and ¬p ∨ q.
¬p: The negation of p.
¬p ∨ q: The disjunction (OR) of ¬p and 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 p and q, we conclude that (p → q) ↔ (¬p ∨ q) is a tautology.
19 Question 29
Question
Let p and q be the propositions ”I am happy” and ”I will go for a run”, respectively. Express the proposition ”If I am not happy, then I will not go for a run”
using p and q in propositional logic.
Solution
To express the proposition ”If I am not happy, then I will not go for a run”
using p and q, we can write it as ¬p → ¬q.
Step 1: Define the propositions: Let p be ”I am happy” and q be ”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) ∨ r is logically
equivalent to p ∨ (q ∨ r).
Solution
To determine if the statement (p ∧ q) ∨ r is 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p ∧ q)
T
T
F
F
F
F
F
F
(p ∧ q) ∨ r
T
T
T
F
T
F
T
F
Step 2: Create a truth table for p ∨ (q ∨ r):
20 p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(q ∨ r)
T
T
T
F
T
T
T
F
p ∨ (q ∨ r)
T
T
T
T
T
T
T
F
Step 3: Compare truth tables: Since the two truth tables are different,
we can conclude that (p ∧ q) ∨ r is not logically equivalent to p ∨ (q ∨ r).
Therefore, the statement (p ∧ q) ∨ r is not logically equivalent to p ∨ (q ∨ r).
Question 31
Question
Let p, q, and r be propositions. Show that (p ∧ q) ⇒ r is logically equivalent to
(p ⇒ r) ∨ (q ⇒ r).
Solution
To show that (p ∧ q) ⇒ r is 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∧q
T
T
F
F
F
F
F
F
(p ∧ q) ⇒ r
T
F
T
T
T
T
T
T
p⇒r
T
F
T
F
T
T
T
T
q⇒r
T
F
T
T
T
F
T
T
From the truth table, we can see that (p ∧ q) ⇒ r and (p ⇒ r) ∨ (q ⇒ r)
have the same truth values for all possible combinations of truth values for p,
q, and r. Therefore, (p ∧ q) ⇒ r is logically equivalent to (p ⇒ r) ∨ (q ⇒ r).
21 Question 32
Question
Let p, q, and r be 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
T
T
F
F
q
T
F
T
F
¬q
F
T
F
T
p → ¬q
F
T
T
T
p→q
T
F
T
T
(p → ¬q) → ((p → q) → p)
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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
(p ∧ q) ∨ r
T
F
T
F
T
F
T
F
r
T
F
T
F
T
F
T
F
22 Step 2: Create a truth table for [(p ∨ r) ∧ (q ∨ r)].
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∨r
T
T
T
T
T
F
T
F
q∨r
T
T
T
F
T
T
T
T
(p ∨ r) ∧ (q ∨ r)
T
T
T
F
T
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 contradiction, 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
r→p
T
T
T
T
F
T
T
T
(p → q) ∧ (q → r) ∧ (r → p)
T
F
F
F
F
F
T
T
p∧q∧r
T
F
F
F
F
F
F
F
From the truth table, we see that the compound proposition is only true
when p, q, and r are all false. Therefore, the compound proposition is a contradiction.
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 ∨ r is always true for any values of p, q, and r, the original
statement is a tautology.
Question 2
Question
Let p, q, and r be propositions. Show that the proposition (p → q) → r is
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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p → q)
T
T
F
F
T
T
T
T
(p → q) → r
T
F
T
T
T
F
T
F
Step 2: Create the truth table for p → (q → r).
2 p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
q→r
T
F
T
T
T
T
T
T
p → (q → r)
T
T
T
T
T
T
T
T
Step 3: Conclusion
By comparing the output columns of the truth tables for (p → q) → r and
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) → r is logically equivalent to p → (q → r).
Question 3
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
p→r
T
F
T
F
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
T
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) =⇒ ¬r is 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) =⇒ ¬r is a logical consequence. Since (p ∧ q) ∧ ¬r
does not appear in the CNF format of the given constraints, the proposition
(p ∧ q) =⇒ ¬r is not a logical consequence.
Question 5
Question
Let p, q, and r be propositions. Determine whether the following logical equivalence 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p → q) → r
T
F
T
F
T
T
T
T
Step 2: Construct the truth table for p → (q → r):
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p → (q → r)
T
F
T
T
T
T
T
T
Step 3: Compare the two truth tables: From the truth tables, we
can see that the two logical expressions (p → q) → r and 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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p → q)
T
T
F
F
T
T
T
T
(q → r)
T
F
T
T
T
F
T
T
(p → r)
T
F
T
F
T
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 r be 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: q Negation
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 r be propositions. Suppose the proposition (p ⇒ q) ⇒ r is 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) ⇒ r is false to determine the truth values of
p, q, and r. If (p ⇒ q) ⇒ r is false, this means that (p ⇒ q) is true while r is
false. Since the implication (p ⇒ q) is true and r is false, then p must be true
while q can 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 p is
true, this implies that q ⇒ r is true. If q is true, then r must also be true in
order for q ⇒ r to be true. Therefore, the truth values of p, q, and r are: p is
true, q is true, and r is false.
Question 9
Question
Let p, q, and r be 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)
≡¬p ∧ r ∨ (q ∧ ¬q)
≡¬p ∧ r ∨ F
[Simplify]
[Contradiction]
≡¬p ∧ r
[Identity]
≡p → r
[Implication rule]
7
[Distribution] 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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
r→p
T
T
T
T
F
T
T
T
(p → q) ∨ (q → r) ∨ (r → p)
T
T
T
T
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 r be propositions with the following truth values: p is false, q is
true, r is 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: p is false, q is true,
r is false.
Therefore, p ∧ q is false ∧ true = false, and ¬r is ¬ 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) ∨ ¬r is f alse .
Question 12
Question
Prove the following statement or provide a counterexample:
For all integers a and b, if a is odd and b is even, then a2 + b is odd.
9 Solution
To prove the statement, we will use a direct proof.
Step 1: Assume a is an odd integer and b is 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 = 4k 2 + 4k + 1 = 2(2k 2 + 2k) + 1
Thus, a2 is also odd.
Step 3: Determine the sum a2 + b
a2 + b = 2(2k 2 + 2k) + 1 + 2m = 2(2k 2 + 2k + m) + 1
Since 2k 2 + 2k + m is an integer, a2 + b is odd.
Step 4: Conclusion
Therefore, for all integers a and b, if a is odd and b is even, then a2 + b is
odd.
Question 13
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
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 r be propositions. Show that (p ∧ q) → r is logically equivalent to
(p → r) ∨ (q → r).
Solution
To show that (p ∧ q) → r is 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p ∧ q) → r
T
F
T
F
T
T
T
T
Step 2: Construct the truth table for (p → r) ∨ (q → r):
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→r
T
F
T
F
T
T
T
T
q→r
T
T
T
T
T
F
T
T
(p → r) ∨ (q → r)
T
T
T
T
T
T
T
T
Step 3: Conclusion: From the truth tables, we can see that the columns
for (p ∧ q) → r and (p → r) ∨ (q → r) are identical. Therefore, we have shown
that (p ∧ q) → r is logically equivalent to (p → r) ∨ (q → r).
Question 15
Question
Let p represent ”It is raining” and q represent ”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 p represent ”It is raining” and q represent ”The roads are wet.”
Step 2: Construct the logical statement: The logical statement for the scenario ”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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∧q
T
T
F
F
F
F
F
F
p∨r
T
T
T
T
T
F
T
F
q∨r
T
T
T
F
T
T
T
F
(p ∨ r) ↔ (q ∨ r)
T
T
T
F
T
T
T
T
(p ∧ q) → [(p ∨ r) ↔ (q ∨ r)]
T
T
T
T
T
T
T
T
Since the final column has all entries as true, the given statement is a tautology.
Question 17
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
F
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
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 p and q be 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 ↔ q using 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
T
T
F
F
q
T
F
T
F
p∧q
T
F
F
F
¬p
F
F
T
T
¬q
F
T
F
T
(p ∧ q) ∨ (¬p ∧ ¬q)
T
T
T
T
p↔q
T
F
F
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 p and q. Therefore, we have shown that
(p ∧ q) ∨ (¬p ∧ ¬q) is logically equivalent to p ↔ q.
Question 19
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
p∧q
T
T
F
F
F
F
F
F
r
T
F
T
F
T
F
T
F
p∧r
T
F
T
F
F
F
F
F
(p ∧ q) ∨ (p ∧ r)
T
T
T
F
F
F
F
F
Step 2: Construct the truth table for p ∧ (q ∨ r)
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
q∨r
T
T
T
F
T
T
T
F
p ∧ (q ∨ r)
T
T
T
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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
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 r be propositions. Show algebraically that (p ∧ q) ∨ r is logically
equivalent to (p ∨ r) ∧ (q ∨ r).
Solution
To show that (p ∧ q) ∨ r is 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) ∨ r is logically equivalent to (p ∨ r) ∧ (q ∨ r).
15 Question 22
Question
Let p, q, and r be 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 r and apply the truth
table for implication (→) and conjunction (∧).
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
r→p
T
T
T
T
F
T
F
T
(p → q) ∧ (q
T ∧T
T ∧F
F ∧T
F ∧T
T ∧T
T ∧F
T ∧T
T ∧T
→ r) ∧ (r → p)
∧T =T
∧T =F
∧T =F
∧T =F
∧F =F
∧T =F
∧F =F
∧T =T
Therefore, the truth value of the proposition (p → q) ∧ (q → r) ∧ (r → p) is
false except when p is false, q is false, and r is false.
Question 23
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
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 r be propositions. Show that (p ∧ q) ∨ r is logically equivalent to
(p ∨ r) ∧ (q ∨ r) using propositional equivalences.
Solution
To show that (p ∧ q) ∨ r is 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) ∨ r is logically equivalent to (p ∨ r) ∧ (q ∨ r).
Question 27
Question
Let p, q, and r represent 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 p and q be 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 p and q.
p
T
T
F
F
q
T
F
T
F
¬p
F
F
T
T
¬p ∨ q
T
F
T
T
p→q
T
F
T
T
(p → q) ↔ (¬p ∨ q)
T
T
T
T
Step 1: Fill in the truth table columns for ¬p and ¬p ∨ q.
¬p: The negation of p.
¬p ∨ q: The disjunction (OR) of ¬p and 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 p and q, we conclude that (p → q) ↔ (¬p ∨ q) is a tautology.
19 Question 29
Question
Let p and q be the propositions ”I am happy” and ”I will go for a run”, respectively. Express the proposition ”If I am not happy, then I will not go for a run”
using p and q in propositional logic.
Solution
To express the proposition ”If I am not happy, then I will not go for a run”
using p and q, we can write it as ¬p → ¬q.
Step 1: Define the propositions: Let p be ”I am happy” and q be ”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) ∨ r is logically
equivalent to p ∨ (q ∨ r).
Solution
To determine if the statement (p ∧ q) ∨ r is 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p ∧ q)
T
T
F
F
F
F
F
F
(p ∧ q) ∨ r
T
T
T
F
T
F
T
F
Step 2: Create a truth table for p ∨ (q ∨ r):
20 p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(q ∨ r)
T
T
T
F
T
T
T
F
p ∨ (q ∨ r)
T
T
T
T
T
T
T
F
Step 3: Compare truth tables: Since the two truth tables are different,
we can conclude that (p ∧ q) ∨ r is not logically equivalent to p ∨ (q ∨ r).
Therefore, the statement (p ∧ q) ∨ r is not logically equivalent to p ∨ (q ∨ r).
Question 31
Question
Let p, q, and r be propositions. Show that (p ∧ q) ⇒ r is logically equivalent to
(p ⇒ r) ∨ (q ⇒ r).
Solution
To show that (p ∧ q) ⇒ r is 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∧q
T
T
F
F
F
F
F
F
(p ∧ q) ⇒ r
T
F
T
T
T
T
T
T
p⇒r
T
F
T
F
T
T
T
T
q⇒r
T
F
T
T
T
F
T
T
From the truth table, we can see that (p ∧ q) ⇒ r and (p ⇒ r) ∨ (q ⇒ r)
have the same truth values for all possible combinations of truth values for p,
q, and r. Therefore, (p ∧ q) ⇒ r is logically equivalent to (p ⇒ r) ∨ (q ⇒ r).
21 Question 32
Question
Let p, q, and r be 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
T
T
F
F
q
T
F
T
F
¬q
F
T
F
T
p → ¬q
F
T
T
T
p→q
T
F
T
T
(p → ¬q) → ((p → q) → p)
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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
(p ∧ q) ∨ r
T
F
T
F
T
F
T
F
r
T
F
T
F
T
F
T
F
22 Step 2: Create a truth table for [(p ∨ r) ∧ (q ∨ r)].
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∨r
T
T
T
T
T
F
T
F
q∨r
T
T
T
F
T
T
T
T
(p ∨ r) ∧ (q ∨ r)
T
T
T
F
T
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 contradiction, 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
r→p
T
T
T
T
F
T
T
T
(p → q) ∧ (q → r) ∧ (r → p)
T
F
F
F
F
F
T
T
p∧q∧r
T
F
F
F
F
F
F
F
From the truth table, we see that the compound proposition is only true
when p, q, and r are all false. Therefore, the compound proposition is a contradiction.
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 ∨ r is always true for any values of p, q, and r, the original
statement is a tautology.
Question 2
Question
Let p, q, and r be propositions. Show that the proposition (p → q) → r is
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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p → q)
T
T
F
F
T
T
T
T
(p → q) → r
T
F
T
T
T
F
T
F
Step 2: Create the truth table for p → (q → r).
2 p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
q→r
T
F
T
T
T
T
T
T
p → (q → r)
T
T
T
T
T
T
T
T
Step 3: Conclusion
By comparing the output columns of the truth tables for (p → q) → r and
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) → r is logically equivalent to p → (q → r).
Question 3
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
p→r
T
F
T
F
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
T
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) =⇒ ¬r is 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) =⇒ ¬r is a logical consequence. Since (p ∧ q) ∧ ¬r
does not appear in the CNF format of the given constraints, the proposition
(p ∧ q) =⇒ ¬r is not a logical consequence.
Question 5
Question
Let p, q, and r be propositions. Determine whether the following logical equivalence 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p → q) → r
T
F
T
F
T
T
T
T
Step 2: Construct the truth table for p → (q → r):
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p → (q → r)
T
F
T
T
T
T
T
T
Step 3: Compare the two truth tables: From the truth tables, we
can see that the two logical expressions (p → q) → r and 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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p → q)
T
T
F
F
T
T
T
T
(q → r)
T
F
T
T
T
F
T
T
(p → r)
T
F
T
F
T
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 r be 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: q Negation
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 r be propositions. Suppose the proposition (p ⇒ q) ⇒ r is 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) ⇒ r is false to determine the truth values of
p, q, and r. If (p ⇒ q) ⇒ r is false, this means that (p ⇒ q) is true while r is
false. Since the implication (p ⇒ q) is true and r is false, then p must be true
while q can 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 p is
true, this implies that q ⇒ r is true. If q is true, then r must also be true in
order for q ⇒ r to be true. Therefore, the truth values of p, q, and r are: p is
true, q is true, and r is false.
Question 9
Question
Let p, q, and r be 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)
≡¬p ∧ r ∨ (q ∧ ¬q)
≡¬p ∧ r ∨ F
[Simplify]
[Contradiction]
≡¬p ∧ r
[Identity]
≡p → r
[Implication rule]
7
[Distribution] 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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
r→p
T
T
T
T
F
T
T
T
(p → q) ∨ (q → r) ∨ (r → p)
T
T
T
T
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 r be propositions with the following truth values: p is false, q is
true, r is 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: p is false, q is true,
r is false.
Therefore, p ∧ q is false ∧ true = false, and ¬r is ¬ 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) ∨ ¬r is f alse .
Question 12
Question
Prove the following statement or provide a counterexample:
For all integers a and b, if a is odd and b is even, then a2 + b is odd.
9 Solution
To prove the statement, we will use a direct proof.
Step 1: Assume a is an odd integer and b is 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 = 4k 2 + 4k + 1 = 2(2k 2 + 2k) + 1
Thus, a2 is also odd.
Step 3: Determine the sum a2 + b
a2 + b = 2(2k 2 + 2k) + 1 + 2m = 2(2k 2 + 2k + m) + 1
Since 2k 2 + 2k + m is an integer, a2 + b is odd.
Step 4: Conclusion
Therefore, for all integers a and b, if a is odd and b is even, then a2 + b is
odd.
Question 13
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
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 r be propositions. Show that (p ∧ q) → r is logically equivalent to
(p → r) ∨ (q → r).
Solution
To show that (p ∧ q) → r is 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p ∧ q) → r
T
F
T
F
T
T
T
T
Step 2: Construct the truth table for (p → r) ∨ (q → r):
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→r
T
F
T
F
T
T
T
T
q→r
T
T
T
T
T
F
T
T
(p → r) ∨ (q → r)
T
T
T
T
T
T
T
T
Step 3: Conclusion: From the truth tables, we can see that the columns
for (p ∧ q) → r and (p → r) ∨ (q → r) are identical. Therefore, we have shown
that (p ∧ q) → r is logically equivalent to (p → r) ∨ (q → r).
Question 15
Question
Let p represent ”It is raining” and q represent ”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 p represent ”It is raining” and q represent ”The roads are wet.”
Step 2: Construct the logical statement: The logical statement for the scenario ”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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∧q
T
T
F
F
F
F
F
F
p∨r
T
T
T
T
T
F
T
F
q∨r
T
T
T
F
T
T
T
F
(p ∨ r) ↔ (q ∨ r)
T
T
T
F
T
T
T
T
(p ∧ q) → [(p ∨ r) ↔ (q ∨ r)]
T
T
T
T
T
T
T
T
Since the final column has all entries as true, the given statement is a tautology.
Question 17
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
F
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
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 p and q be 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 ↔ q using 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
T
T
F
F
q
T
F
T
F
p∧q
T
F
F
F
¬p
F
F
T
T
¬q
F
T
F
T
(p ∧ q) ∨ (¬p ∧ ¬q)
T
T
T
T
p↔q
T
F
F
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 p and q. Therefore, we have shown that
(p ∧ q) ∨ (¬p ∧ ¬q) is logically equivalent to p ↔ q.
Question 19
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
p∧q
T
T
F
F
F
F
F
F
r
T
F
T
F
T
F
T
F
p∧r
T
F
T
F
F
F
F
F
(p ∧ q) ∨ (p ∧ r)
T
T
T
F
F
F
F
F
Step 2: Construct the truth table for p ∧ (q ∨ r)
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
q∨r
T
T
T
F
T
T
T
F
p ∧ (q ∨ r)
T
T
T
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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
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 r be propositions. Show algebraically that (p ∧ q) ∨ r is logically
equivalent to (p ∨ r) ∧ (q ∨ r).
Solution
To show that (p ∧ q) ∨ r is 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) ∨ r is logically equivalent to (p ∨ r) ∧ (q ∨ r).
15 Question 22
Question
Let p, q, and r be 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 r and apply the truth
table for implication (→) and conjunction (∧).
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
r→p
T
T
T
T
F
T
F
T
(p → q) ∧ (q
T ∧T
T ∧F
F ∧T
F ∧T
T ∧T
T ∧F
T ∧T
T ∧T
→ r) ∧ (r → p)
∧T =T
∧T =F
∧T =F
∧T =F
∧F =F
∧T =F
∧F =F
∧T =T
Therefore, the truth value of the proposition (p → q) ∧ (q → r) ∧ (r → p) is
false except when p is false, q is false, and r is false.
Question 23
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
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 r be propositions. Show that (p ∧ q) ∨ r is logically equivalent to
(p ∨ r) ∧ (q ∨ r) using propositional equivalences.
Solution
To show that (p ∧ q) ∨ r is 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) ∨ r is logically equivalent to (p ∨ r) ∧ (q ∨ r).
Question 27
Question
Let p, q, and r represent 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 p and q be 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 p and q.
p
T
T
F
F
q
T
F
T
F
¬p
F
F
T
T
¬p ∨ q
T
F
T
T
p→q
T
F
T
T
(p → q) ↔ (¬p ∨ q)
T
T
T
T
Step 1: Fill in the truth table columns for ¬p and ¬p ∨ q.
¬p: The negation of p.
¬p ∨ q: The disjunction (OR) of ¬p and 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 p and q, we conclude that (p → q) ↔ (¬p ∨ q) is a tautology.
19 Question 29
Question
Let p and q be the propositions ”I am happy” and ”I will go for a run”, respectively. Express the proposition ”If I am not happy, then I will not go for a run”
using p and q in propositional logic.
Solution
To express the proposition ”If I am not happy, then I will not go for a run”
using p and q, we can write it as ¬p → ¬q.
Step 1: Define the propositions: Let p be ”I am happy” and q be ”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) ∨ r is logically
equivalent to p ∨ (q ∨ r).
Solution
To determine if the statement (p ∧ q) ∨ r is 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p ∧ q)
T
T
F
F
F
F
F
F
(p ∧ q) ∨ r
T
T
T
F
T
F
T
F
Step 2: Create a truth table for p ∨ (q ∨ r):
20 p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(q ∨ r)
T
T
T
F
T
T
T
F
p ∨ (q ∨ r)
T
T
T
T
T
T
T
F
Step 3: Compare truth tables: Since the two truth tables are different,
we can conclude that (p ∧ q) ∨ r is not logically equivalent to p ∨ (q ∨ r).
Therefore, the statement (p ∧ q) ∨ r is not logically equivalent to p ∨ (q ∨ r).
Question 31
Question
Let p, q, and r be propositions. Show that (p ∧ q) ⇒ r is logically equivalent to
(p ⇒ r) ∨ (q ⇒ r).
Solution
To show that (p ∧ q) ⇒ r is 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∧q
T
T
F
F
F
F
F
F
(p ∧ q) ⇒ r
T
F
T
T
T
T
T
T
p⇒r
T
F
T
F
T
T
T
T
q⇒r
T
F
T
T
T
F
T
T
From the truth table, we can see that (p ∧ q) ⇒ r and (p ⇒ r) ∨ (q ⇒ r)
have the same truth values for all possible combinations of truth values for p,
q, and r. Therefore, (p ∧ q) ⇒ r is logically equivalent to (p ⇒ r) ∨ (q ⇒ r).
21 Question 32
Question
Let p, q, and r be 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
T
T
F
F
q
T
F
T
F
¬q
F
T
F
T
p → ¬q
F
T
T
T
p→q
T
F
T
T
(p → ¬q) → ((p → q) → p)
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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
(p ∧ q) ∨ r
T
F
T
F
T
F
T
F
r
T
F
T
F
T
F
T
F
22 Step 2: Create a truth table for [(p ∨ r) ∧ (q ∨ r)].
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∨r
T
T
T
T
T
F
T
F
q∨r
T
T
T
F
T
T
T
T
(p ∨ r) ∧ (q ∨ r)
T
T
T
F
T
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 contradiction, 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
r→p
T
T
T
T
F
T
T
T
(p → q) ∧ (q → r) ∧ (r → p)
T
F
F
F
F
F
T
T
p∧q∧r
T
F
F
F
F
F
F
F
From the truth table, we see that the compound proposition is only true
when p, q, and r are all false. Therefore, the compound proposition is a contradiction.
23 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) =⇒ ¬r is 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) =⇒ ¬r is a logical consequence. Since (p ∧ q) ∧ ¬r
does not appear in the CNF format of the given constraints, the proposition
(p ∧ q) =⇒ ¬r is not a logical consequence.
Question 5
Question
Let p, q, and r be propositions. Determine whether the following logical equivalence 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p → q) → r
T
F
T
F
T
T
T
T
Step 2: Construct the truth table for p → (q → r):
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p → (q → r)
T
F
T
T
T
T
T
T
Step 3: Compare the two truth tables: From the truth tables, we
can see that the two logical expressions (p → q) → r and 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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p → q)
T
T
F
F
T
T
T
T
(q → r)
T
F
T
T
T
F
T
T
(p → r)
T
F
T
F
T
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 r be 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: q Negation
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 r be propositions. Suppose the proposition (p ⇒ q) ⇒ r is 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) ⇒ r is false to determine the truth values of
p, q, and r. If (p ⇒ q) ⇒ r is false, this means that (p ⇒ q) is true while r is
false. Since the implication (p ⇒ q) is true and r is false, then p must be true
while q can 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 p is
true, this implies that q ⇒ r is true. If q is true, then r must also be true in
order for q ⇒ r to be true. Therefore, the truth values of p, q, and r are: p is
true, q is true, and r is false.
Question 9
Question
Let p, q, and r be 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)
≡¬p ∧ r ∨ (q ∧ ¬q)
≡¬p ∧ r ∨ F
[Simplify]
[Contradiction]
≡¬p ∧ r
[Identity]
≡p → r
[Implication rule]
7
[Distribution] 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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
r→p
T
T
T
T
F
T
T
T
(p → q) ∨ (q → r) ∨ (r → p)
T
T
T
T
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 r be propositions with the following truth values: p is false, q is
true, r is 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: p is false, q is true,
r is false.
Therefore, p ∧ q is false ∧ true = false, and ¬r is ¬ 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) ∨ ¬r is f alse .
Question 12
Question
Prove the following statement or provide a counterexample:
For all integers a and b, if a is odd and b is even, then a2 + b is odd.
9 Solution
To prove the statement, we will use a direct proof.
Step 1: Assume a is an odd integer and b is 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 = 4k 2 + 4k + 1 = 2(2k 2 + 2k) + 1
Thus, a2 is also odd.
Step 3: Determine the sum a2 + b
a2 + b = 2(2k 2 + 2k) + 1 + 2m = 2(2k 2 + 2k + m) + 1
Since 2k 2 + 2k + m is an integer, a2 + b is odd.
Step 4: Conclusion
Therefore, for all integers a and b, if a is odd and b is even, then a2 + b is
odd.
Question 13
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
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 r be propositions. Show that (p ∧ q) → r is logically equivalent to
(p → r) ∨ (q → r).
Solution
To show that (p ∧ q) → r is 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p ∧ q) → r
T
F
T
F
T
T
T
T
Step 2: Construct the truth table for (p → r) ∨ (q → r):
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→r
T
F
T
F
T
T
T
T
q→r
T
T
T
T
T
F
T
T
(p → r) ∨ (q → r)
T
T
T
T
T
T
T
T
Step 3: Conclusion: From the truth tables, we can see that the columns
for (p ∧ q) → r and (p → r) ∨ (q → r) are identical. Therefore, we have shown
that (p ∧ q) → r is logically equivalent to (p → r) ∨ (q → r).
Question 15
Question
Let p represent ”It is raining” and q represent ”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 p represent ”It is raining” and q represent ”The roads are wet.”
Step 2: Construct the logical statement: The logical statement for the scenario ”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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∧q
T
T
F
F
F
F
F
F
p∨r
T
T
T
T
T
F
T
F
q∨r
T
T
T
F
T
T
T
F
(p ∨ r) ↔ (q ∨ r)
T
T
T
F
T
T
T
T
(p ∧ q) → [(p ∨ r) ↔ (q ∨ r)]
T
T
T
T
T
T
T
T
Since the final column has all entries as true, the given statement is a tautology.
Question 17
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
F
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
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 p and q be 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 ↔ q using 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
T
T
F
F
q
T
F
T
F
p∧q
T
F
F
F
¬p
F
F
T
T
¬q
F
T
F
T
(p ∧ q) ∨ (¬p ∧ ¬q)
T
T
T
T
p↔q
T
F
F
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 p and q. Therefore, we have shown that
(p ∧ q) ∨ (¬p ∧ ¬q) is logically equivalent to p ↔ q.
Question 19
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
p∧q
T
T
F
F
F
F
F
F
r
T
F
T
F
T
F
T
F
p∧r
T
F
T
F
F
F
F
F
(p ∧ q) ∨ (p ∧ r)
T
T
T
F
F
F
F
F
Step 2: Construct the truth table for p ∧ (q ∨ r)
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
q∨r
T
T
T
F
T
T
T
F
p ∧ (q ∨ r)
T
T
T
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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
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 r be propositions. Show algebraically that (p ∧ q) ∨ r is logically
equivalent to (p ∨ r) ∧ (q ∨ r).
Solution
To show that (p ∧ q) ∨ r is 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) ∨ r is logically equivalent to (p ∨ r) ∧ (q ∨ r).
15 Question 22
Question
Let p, q, and r be 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 r and apply the truth
table for implication (→) and conjunction (∧).
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
r→p
T
T
T
T
F
T
F
T
(p → q) ∧ (q
T ∧T
T ∧F
F ∧T
F ∧T
T ∧T
T ∧F
T ∧T
T ∧T
→ r) ∧ (r → p)
∧T =T
∧T =F
∧T =F
∧T =F
∧F =F
∧T =F
∧F =F
∧T =T
Therefore, the truth value of the proposition (p → q) ∧ (q → r) ∧ (r → p) is
false except when p is false, q is false, and r is false.
Question 23
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
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 r be propositions. Show that (p ∧ q) ∨ r is logically equivalent to
(p ∨ r) ∧ (q ∨ r) using propositional equivalences.
Solution
To show that (p ∧ q) ∨ r is 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) ∨ r is logically equivalent to (p ∨ r) ∧ (q ∨ r).
Question 27
Question
Let p, q, and r represent 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 p and q be 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 p and q.
p
T
T
F
F
q
T
F
T
F
¬p
F
F
T
T
¬p ∨ q
T
F
T
T
p→q
T
F
T
T
(p → q) ↔ (¬p ∨ q)
T
T
T
T
Step 1: Fill in the truth table columns for ¬p and ¬p ∨ q.
¬p: The negation of p.
¬p ∨ q: The disjunction (OR) of ¬p and 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 p and q, we conclude that (p → q) ↔ (¬p ∨ q) is a tautology.
19 Question 29
Question
Let p and q be the propositions ”I am happy” and ”I will go for a run”, respectively. Express the proposition ”If I am not happy, then I will not go for a run”
using p and q in propositional logic.
Solution
To express the proposition ”If I am not happy, then I will not go for a run”
using p and q, we can write it as ¬p → ¬q.
Step 1: Define the propositions: Let p be ”I am happy” and q be ”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) ∨ r is logically
equivalent to p ∨ (q ∨ r).
Solution
To determine if the statement (p ∧ q) ∨ r is 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p ∧ q)
T
T
F
F
F
F
F
F
(p ∧ q) ∨ r
T
T
T
F
T
F
T
F
Step 2: Create a truth table for p ∨ (q ∨ r):
20 p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(q ∨ r)
T
T
T
F
T
T
T
F
p ∨ (q ∨ r)
T
T
T
T
T
T
T
F
Step 3: Compare truth tables: Since the two truth tables are different,
we can conclude that (p ∧ q) ∨ r is not logically equivalent to p ∨ (q ∨ r).
Therefore, the statement (p ∧ q) ∨ r is not logically equivalent to p ∨ (q ∨ r).
Question 31
Question
Let p, q, and r be propositions. Show that (p ∧ q) ⇒ r is logically equivalent to
(p ⇒ r) ∨ (q ⇒ r).
Solution
To show that (p ∧ q) ⇒ r is 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∧q
T
T
F
F
F
F
F
F
(p ∧ q) ⇒ r
T
F
T
T
T
T
T
T
p⇒r
T
F
T
F
T
T
T
T
q⇒r
T
F
T
T
T
F
T
T
From the truth table, we can see that (p ∧ q) ⇒ r and (p ⇒ r) ∨ (q ⇒ r)
have the same truth values for all possible combinations of truth values for p,
q, and r. Therefore, (p ∧ q) ⇒ r is logically equivalent to (p ⇒ r) ∨ (q ⇒ r).
21 Question 32
Question
Let p, q, and r be 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
T
T
F
F
q
T
F
T
F
¬q
F
T
F
T
p → ¬q
F
T
T
T
p→q
T
F
T
T
(p → ¬q) → ((p → q) → p)
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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
(p ∧ q) ∨ r
T
F
T
F
T
F
T
F
r
T
F
T
F
T
F
T
F
22 Step 2: Create a truth table for [(p ∨ r) ∧ (q ∨ r)].
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∨r
T
T
T
T
T
F
T
F
q∨r
T
T
T
F
T
T
T
T
(p ∨ r) ∧ (q ∨ r)
T
T
T
F
T
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 contradiction, 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
r→p
T
T
T
T
F
T
T
T
(p → q) ∧ (q → r) ∧ (r → p)
T
F
F
F
F
F
T
T
p∧q∧r
T
F
F
F
F
F
F
F
From the truth table, we see that the compound proposition is only true
when p, q, and r are all false. Therefore, the compound proposition is a contradiction.
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 ∨ r is always true for any values of p, q, and r, the original
statement is a tautology.
Question 2
Question
Let p, q, and r be propositions. Show that the proposition (p → q) → r is
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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p → q)
T
T
F
F
T
T
T
T
(p → q) → r
T
F
T
T
T
F
T
F
Step 2: Create the truth table for p → (q → r).
2 p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
q→r
T
F
T
T
T
T
T
T
p → (q → r)
T
T
T
T
T
T
T
T
Step 3: Conclusion
By comparing the output columns of the truth tables for (p → q) → r and
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) → r is logically equivalent to p → (q → r).
Question 3
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
p→r
T
F
T
F
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
T
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) =⇒ ¬r is 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) =⇒ ¬r is a logical consequence. Since (p ∧ q) ∧ ¬r
does not appear in the CNF format of the given constraints, the proposition
(p ∧ q) =⇒ ¬r is not a logical consequence.
Question 5
Question
Let p, q, and r be propositions. Determine whether the following logical equivalence 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p → q) → r
T
F
T
F
T
T
T
T
Step 2: Construct the truth table for p → (q → r):
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p → (q → r)
T
F
T
T
T
T
T
T
Step 3: Compare the two truth tables: From the truth tables, we
can see that the two logical expressions (p → q) → r and 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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p → q)
T
T
F
F
T
T
T
T
(q → r)
T
F
T
T
T
F
T
T
(p → r)
T
F
T
F
T
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 r be 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: q Negation
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 r be propositions. Suppose the proposition (p ⇒ q) ⇒ r is 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) ⇒ r is false to determine the truth values of
p, q, and r. If (p ⇒ q) ⇒ r is false, this means that (p ⇒ q) is true while r is
false. Since the implication (p ⇒ q) is true and r is false, then p must be true
while q can 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 p is
true, this implies that q ⇒ r is true. If q is true, then r must also be true in
order for q ⇒ r to be true. Therefore, the truth values of p, q, and r are: p is
true, q is true, and r is false.
Question 9
Question
Let p, q, and r be 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)
≡¬p ∧ r ∨ (q ∧ ¬q)
≡¬p ∧ r ∨ F
[Simplify]
[Contradiction]
≡¬p ∧ r
[Identity]
≡p → r
[Implication rule]
7
[Distribution] 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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
r→p
T
T
T
T
F
T
T
T
(p → q) ∨ (q → r) ∨ (r → p)
T
T
T
T
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 r be propositions with the following truth values: p is false, q is
true, r is 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: p is false, q is true,
r is false.
Therefore, p ∧ q is false ∧ true = false, and ¬r is ¬ 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) ∨ ¬r is f alse .
Question 12
Question
Prove the following statement or provide a counterexample:
For all integers a and b, if a is odd and b is even, then a2 + b is odd.
9 Solution
To prove the statement, we will use a direct proof.
Step 1: Assume a is an odd integer and b is 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 = 4k 2 + 4k + 1 = 2(2k 2 + 2k) + 1
Thus, a2 is also odd.
Step 3: Determine the sum a2 + b
a2 + b = 2(2k 2 + 2k) + 1 + 2m = 2(2k 2 + 2k + m) + 1
Since 2k 2 + 2k + m is an integer, a2 + b is odd.
Step 4: Conclusion
Therefore, for all integers a and b, if a is odd and b is even, then a2 + b is
odd.
Question 13
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
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 r be propositions. Show that (p ∧ q) → r is logically equivalent to
(p → r) ∨ (q → r).
Solution
To show that (p ∧ q) → r is 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p ∧ q) → r
T
F
T
F
T
T
T
T
Step 2: Construct the truth table for (p → r) ∨ (q → r):
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→r
T
F
T
F
T
T
T
T
q→r
T
T
T
T
T
F
T
T
(p → r) ∨ (q → r)
T
T
T
T
T
T
T
T
Step 3: Conclusion: From the truth tables, we can see that the columns
for (p ∧ q) → r and (p → r) ∨ (q → r) are identical. Therefore, we have shown
that (p ∧ q) → r is logically equivalent to (p → r) ∨ (q → r).
Question 15
Question
Let p represent ”It is raining” and q represent ”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 p represent ”It is raining” and q represent ”The roads are wet.”
Step 2: Construct the logical statement: The logical statement for the scenario ”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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∧q
T
T
F
F
F
F
F
F
p∨r
T
T
T
T
T
F
T
F
q∨r
T
T
T
F
T
T
T
F
(p ∨ r) ↔ (q ∨ r)
T
T
T
F
T
T
T
T
(p ∧ q) → [(p ∨ r) ↔ (q ∨ r)]
T
T
T
T
T
T
T
T
Since the final column has all entries as true, the given statement is a tautology.
Question 17
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
F
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
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 p and q be 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 ↔ q using 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
T
T
F
F
q
T
F
T
F
p∧q
T
F
F
F
¬p
F
F
T
T
¬q
F
T
F
T
(p ∧ q) ∨ (¬p ∧ ¬q)
T
T
T
T
p↔q
T
F
F
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 p and q. Therefore, we have shown that
(p ∧ q) ∨ (¬p ∧ ¬q) is logically equivalent to p ↔ q.
Question 19
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
p∧q
T
T
F
F
F
F
F
F
r
T
F
T
F
T
F
T
F
p∧r
T
F
T
F
F
F
F
F
(p ∧ q) ∨ (p ∧ r)
T
T
T
F
F
F
F
F
Step 2: Construct the truth table for p ∧ (q ∨ r)
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
q∨r
T
T
T
F
T
T
T
F
p ∧ (q ∨ r)
T
T
T
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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
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 r be propositions. Show algebraically that (p ∧ q) ∨ r is logically
equivalent to (p ∨ r) ∧ (q ∨ r).
Solution
To show that (p ∧ q) ∨ r is 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) ∨ r is logically equivalent to (p ∨ r) ∧ (q ∨ r).
15 Question 22
Question
Let p, q, and r be 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 r and apply the truth
table for implication (→) and conjunction (∧).
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
r→p
T
T
T
T
F
T
F
T
(p → q) ∧ (q
T ∧T
T ∧F
F ∧T
F ∧T
T ∧T
T ∧F
T ∧T
T ∧T
→ r) ∧ (r → p)
∧T =T
∧T =F
∧T =F
∧T =F
∧F =F
∧T =F
∧F =F
∧T =T
Therefore, the truth value of the proposition (p → q) ∧ (q → r) ∧ (r → p) is
false except when p is false, q is false, and r is false.
Question 23
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
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 r be propositions. Show that (p ∧ q) ∨ r is logically equivalent to
(p ∨ r) ∧ (q ∨ r) using propositional equivalences.
Solution
To show that (p ∧ q) ∨ r is 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) ∨ r is logically equivalent to (p ∨ r) ∧ (q ∨ r).
Question 27
Question
Let p, q, and r represent 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 p and q be 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 p and q.
p
T
T
F
F
q
T
F
T
F
¬p
F
F
T
T
¬p ∨ q
T
F
T
T
p→q
T
F
T
T
(p → q) ↔ (¬p ∨ q)
T
T
T
T
Step 1: Fill in the truth table columns for ¬p and ¬p ∨ q.
¬p: The negation of p.
¬p ∨ q: The disjunction (OR) of ¬p and 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 p and q, we conclude that (p → q) ↔ (¬p ∨ q) is a tautology.
19 Question 29
Question
Let p and q be the propositions ”I am happy” and ”I will go for a run”, respectively. Express the proposition ”If I am not happy, then I will not go for a run”
using p and q in propositional logic.
Solution
To express the proposition ”If I am not happy, then I will not go for a run”
using p and q, we can write it as ¬p → ¬q.
Step 1: Define the propositions: Let p be ”I am happy” and q be ”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) ∨ r is logically
equivalent to p ∨ (q ∨ r).
Solution
To determine if the statement (p ∧ q) ∨ r is 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p ∧ q)
T
T
F
F
F
F
F
F
(p ∧ q) ∨ r
T
T
T
F
T
F
T
F
Step 2: Create a truth table for p ∨ (q ∨ r):
20 p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(q ∨ r)
T
T
T
F
T
T
T
F
p ∨ (q ∨ r)
T
T
T
T
T
T
T
F
Step 3: Compare truth tables: Since the two truth tables are different,
we can conclude that (p ∧ q) ∨ r is not logically equivalent to p ∨ (q ∨ r).
Therefore, the statement (p ∧ q) ∨ r is not logically equivalent to p ∨ (q ∨ r).
Question 31
Question
Let p, q, and r be propositions. Show that (p ∧ q) ⇒ r is logically equivalent to
(p ⇒ r) ∨ (q ⇒ r).
Solution
To show that (p ∧ q) ⇒ r is 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∧q
T
T
F
F
F
F
F
F
(p ∧ q) ⇒ r
T
F
T
T
T
T
T
T
p⇒r
T
F
T
F
T
T
T
T
q⇒r
T
F
T
T
T
F
T
T
From the truth table, we can see that (p ∧ q) ⇒ r and (p ⇒ r) ∨ (q ⇒ r)
have the same truth values for all possible combinations of truth values for p,
q, and r. Therefore, (p ∧ q) ⇒ r is logically equivalent to (p ⇒ r) ∨ (q ⇒ r).
21 Question 32
Question
Let p, q, and r be 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
T
T
F
F
q
T
F
T
F
¬q
F
T
F
T
p → ¬q
F
T
T
T
p→q
T
F
T
T
(p → ¬q) → ((p → q) → p)
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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
(p ∧ q) ∨ r
T
F
T
F
T
F
T
F
r
T
F
T
F
T
F
T
F
22 Step 2: Create a truth table for [(p ∨ r) ∧ (q ∨ r)].
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∨r
T
T
T
T
T
F
T
F
q∨r
T
T
T
F
T
T
T
T
(p ∨ r) ∧ (q ∨ r)
T
T
T
F
T
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 contradiction, 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
r→p
T
T
T
T
F
T
T
T
(p → q) ∧ (q → r) ∧ (r → p)
T
F
F
F
F
F
T
T
p∧q∧r
T
F
F
F
F
F
F
F
From the truth table, we see that the compound proposition is only true
when p, q, and r are all false. Therefore, the compound proposition is a contradiction.
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 ∨ r is always true for any values of p, q, and r, the original
statement is a tautology.
Question 2
Question
Let p, q, and r be propositions. Show that the proposition (p → q) → r is
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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p → q)
T
T
F
F
T
T
T
T
(p → q) → r
T
F
T
T
T
F
T
F
Step 2: Create the truth table for p → (q → r).
2 p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
q→r
T
F
T
T
T
T
T
T
p → (q → r)
T
T
T
T
T
T
T
T
Step 3: Conclusion
By comparing the output columns of the truth tables for (p → q) → r and
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) → r is logically equivalent to p → (q → r).
Question 3
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
p→r
T
F
T
F
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
T
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) =⇒ ¬r is 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) =⇒ ¬r is a logical consequence. Since (p ∧ q) ∧ ¬r
does not appear in the CNF format of the given constraints, the proposition
(p ∧ q) =⇒ ¬r is not a logical consequence.
Question 5
Question
Let p, q, and r be propositions. Determine whether the following logical equivalence 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p → q) → r
T
F
T
F
T
T
T
T
Step 2: Construct the truth table for p → (q → r):
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p → (q → r)
T
F
T
T
T
T
T
T
Step 3: Compare the two truth tables: From the truth tables, we
can see that the two logical expressions (p → q) → r and 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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p → q)
T
T
F
F
T
T
T
T
(q → r)
T
F
T
T
T
F
T
T
(p → r)
T
F
T
F
T
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 r be 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: q Negation
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 r be propositions. Suppose the proposition (p ⇒ q) ⇒ r is 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) ⇒ r is false to determine the truth values of
p, q, and r. If (p ⇒ q) ⇒ r is false, this means that (p ⇒ q) is true while r is
false. Since the implication (p ⇒ q) is true and r is false, then p must be true
while q can 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 p is
true, this implies that q ⇒ r is true. If q is true, then r must also be true in
order for q ⇒ r to be true. Therefore, the truth values of p, q, and r are: p is
true, q is true, and r is false.
Question 9
Question
Let p, q, and r be 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)
≡¬p ∧ r ∨ (q ∧ ¬q)
≡¬p ∧ r ∨ F
[Simplify]
[Contradiction]
≡¬p ∧ r
[Identity]
≡p → r
[Implication rule]
7
[Distribution] 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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
r→p
T
T
T
T
F
T
T
T
(p → q) ∨ (q → r) ∨ (r → p)
T
T
T
T
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 r be propositions with the following truth values: p is false, q is
true, r is 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: p is false, q is true,
r is false.
Therefore, p ∧ q is false ∧ true = false, and ¬r is ¬ 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) ∨ ¬r is f alse .
Question 12
Question
Prove the following statement or provide a counterexample:
For all integers a and b, if a is odd and b is even, then a2 + b is odd.
9 Solution
To prove the statement, we will use a direct proof.
Step 1: Assume a is an odd integer and b is 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 = 4k 2 + 4k + 1 = 2(2k 2 + 2k) + 1
Thus, a2 is also odd.
Step 3: Determine the sum a2 + b
a2 + b = 2(2k 2 + 2k) + 1 + 2m = 2(2k 2 + 2k + m) + 1
Since 2k 2 + 2k + m is an integer, a2 + b is odd.
Step 4: Conclusion
Therefore, for all integers a and b, if a is odd and b is even, then a2 + b is
odd.
Question 13
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
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 r be propositions. Show that (p ∧ q) → r is logically equivalent to
(p → r) ∨ (q → r).
Solution
To show that (p ∧ q) → r is 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p ∧ q) → r
T
F
T
F
T
T
T
T
Step 2: Construct the truth table for (p → r) ∨ (q → r):
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→r
T
F
T
F
T
T
T
T
q→r
T
T
T
T
T
F
T
T
(p → r) ∨ (q → r)
T
T
T
T
T
T
T
T
Step 3: Conclusion: From the truth tables, we can see that the columns
for (p ∧ q) → r and (p → r) ∨ (q → r) are identical. Therefore, we have shown
that (p ∧ q) → r is logically equivalent to (p → r) ∨ (q → r).
Question 15
Question
Let p represent ”It is raining” and q represent ”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 p represent ”It is raining” and q represent ”The roads are wet.”
Step 2: Construct the logical statement: The logical statement for the scenario ”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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∧q
T
T
F
F
F
F
F
F
p∨r
T
T
T
T
T
F
T
F
q∨r
T
T
T
F
T
T
T
F
(p ∨ r) ↔ (q ∨ r)
T
T
T
F
T
T
T
T
(p ∧ q) → [(p ∨ r) ↔ (q ∨ r)]
T
T
T
T
T
T
T
T
Since the final column has all entries as true, the given statement is a tautology.
Question 17
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
F
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
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 p and q be 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 ↔ q using 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
T
T
F
F
q
T
F
T
F
p∧q
T
F
F
F
¬p
F
F
T
T
¬q
F
T
F
T
(p ∧ q) ∨ (¬p ∧ ¬q)
T
T
T
T
p↔q
T
F
F
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 p and q. Therefore, we have shown that
(p ∧ q) ∨ (¬p ∧ ¬q) is logically equivalent to p ↔ q.
Question 19
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
p∧q
T
T
F
F
F
F
F
F
r
T
F
T
F
T
F
T
F
p∧r
T
F
T
F
F
F
F
F
(p ∧ q) ∨ (p ∧ r)
T
T
T
F
F
F
F
F
Step 2: Construct the truth table for p ∧ (q ∨ r)
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
q∨r
T
T
T
F
T
T
T
F
p ∧ (q ∨ r)
T
T
T
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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
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 r be propositions. Show algebraically that (p ∧ q) ∨ r is logically
equivalent to (p ∨ r) ∧ (q ∨ r).
Solution
To show that (p ∧ q) ∨ r is 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) ∨ r is logically equivalent to (p ∨ r) ∧ (q ∨ r).
15 Question 22
Question
Let p, q, and r be 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 r and apply the truth
table for implication (→) and conjunction (∧).
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
r→p
T
T
T
T
F
T
F
T
(p → q) ∧ (q
T ∧T
T ∧F
F ∧T
F ∧T
T ∧T
T ∧F
T ∧T
T ∧T
→ r) ∧ (r → p)
∧T =T
∧T =F
∧T =F
∧T =F
∧F =F
∧T =F
∧F =F
∧T =T
Therefore, the truth value of the proposition (p → q) ∧ (q → r) ∧ (r → p) is
false except when p is false, q is false, and r is false.
Question 23
Question
Let p, q, and r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
p→r
T
F
T
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 r be propositions. Show that (p ∧ q) ∨ r is logically equivalent to
(p ∨ r) ∧ (q ∨ r) using propositional equivalences.
Solution
To show that (p ∧ q) ∨ r is 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) ∨ r is logically equivalent to (p ∨ r) ∧ (q ∨ r).
Question 27
Question
Let p, q, and r represent 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 p and q be 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 p and q.
p
T
T
F
F
q
T
F
T
F
¬p
F
F
T
T
¬p ∨ q
T
F
T
T
p→q
T
F
T
T
(p → q) ↔ (¬p ∨ q)
T
T
T
T
Step 1: Fill in the truth table columns for ¬p and ¬p ∨ q.
¬p: The negation of p.
¬p ∨ q: The disjunction (OR) of ¬p and 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 p and q, we conclude that (p → q) ↔ (¬p ∨ q) is a tautology.
19 Question 29
Question
Let p and q be the propositions ”I am happy” and ”I will go for a run”, respectively. Express the proposition ”If I am not happy, then I will not go for a run”
using p and q in propositional logic.
Solution
To express the proposition ”If I am not happy, then I will not go for a run”
using p and q, we can write it as ¬p → ¬q.
Step 1: Define the propositions: Let p be ”I am happy” and q be ”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) ∨ r is logically
equivalent to p ∨ (q ∨ r).
Solution
To determine if the statement (p ∧ q) ∨ r is 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(p ∧ q)
T
T
F
F
F
F
F
F
(p ∧ q) ∨ r
T
T
T
F
T
F
T
F
Step 2: Create a truth table for p ∨ (q ∨ r):
20 p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
(q ∨ r)
T
T
T
F
T
T
T
F
p ∨ (q ∨ r)
T
T
T
T
T
T
T
F
Step 3: Compare truth tables: Since the two truth tables are different,
we can conclude that (p ∧ q) ∨ r is not logically equivalent to p ∨ (q ∨ r).
Therefore, the statement (p ∧ q) ∨ r is not logically equivalent to p ∨ (q ∨ r).
Question 31
Question
Let p, q, and r be propositions. Show that (p ∧ q) ⇒ r is logically equivalent to
(p ⇒ r) ∨ (q ⇒ r).
Solution
To show that (p ∧ q) ⇒ r is 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∧q
T
T
F
F
F
F
F
F
(p ∧ q) ⇒ r
T
F
T
T
T
T
T
T
p⇒r
T
F
T
F
T
T
T
T
q⇒r
T
F
T
T
T
F
T
T
From the truth table, we can see that (p ∧ q) ⇒ r and (p ⇒ r) ∨ (q ⇒ r)
have the same truth values for all possible combinations of truth values for p,
q, and r. Therefore, (p ∧ q) ⇒ r is logically equivalent to (p ⇒ r) ∨ (q ⇒ r).
21 Question 32
Question
Let p, q, and r be 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
T
T
F
F
q
T
F
T
F
¬q
F
T
F
T
p → ¬q
F
T
T
T
p→q
T
F
T
T
(p → ¬q) → ((p → q) → p)
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 r be 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
(p ∧ q) ∨ r
T
F
T
F
T
F
T
F
r
T
F
T
F
T
F
T
F
22 Step 2: Create a truth table for [(p ∨ r) ∧ (q ∨ r)].
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∨r
T
T
T
T
T
F
T
F
q∨r
T
T
T
F
T
T
T
T
(p ∨ r) ∧ (q ∨ r)
T
T
T
F
T
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 contradiction, 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
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
r→p
T
T
T
T
F
T
T
T
(p → q) ∧ (q → r) ∧ (r → p)
T
F
F
F
F
F
T
T
p∧q∧r
T
F
F
F
F
F
F
F
From the truth table, we see that the compound proposition is only true
when p, q, and r are all false. Therefore, the compound proposition is a contradiction.
23 Question 35
Question
Let p, q, and r be 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 ¬r are true, but the
conclusion ¬p is false.
Step 2: According to De Morgan’s Law, ¬q and ¬r can be written as q → p
and r → p respectively.
Step 3: From p ∧ (q ∨ r) and q → p, we can infer p ∧ (q ∨ r) → p using
simplification.
Step 4: By Modus Ponens on p ∧ (q ∨ r) → p and p, we have p.
Step 5: Since we have derived p from our assumptions, this means the
assumption that ¬p is false is incorrect. Therefore, ¬p must 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
Related Documents
- 2.1 Exponents Laws - Notes [Teacher]
- A Guide to Understanding Variables and Equations
- Trigonometric Limit Theorem: Applications in Calculations
- 1.4 Quadratics - Max or Min - Worksheet 1 [Answers]
- 1.3 Radicals - Worksheet 1 [Answers]
- 1.4 Quadratics - Max or Min - Notes [Teacher]
- 1.6 Quadratics - Roots - Notes [Teacher]
- 1.6 Quadratics - Roots - Worksheet 1 [Answers]
- 1.7 Quadratics - Linear Systems - Notes [Teacher]
- 1.7 Quadratics - Linear Systems - Worksheet 1 [Answers]
- 1.1 Functions, Domain, & Range - Notes [Teacher]
- Maximum and Minimum in Function Graphs: Determination and Understanding
- Graph Analysis: Functions, Domain, Range
- Mapping Functions of Two Variables Using Maple 13
- Matrix Multiplication in Linear Algebra
- 1.3 Radicals - Notes [Teacher]
- 1.0 Factoring - Notes
- 1.0 Factoring - Worksheet 1 [Questions + Answers]
- An Detailed Guide to Understanding Real Numbers
- 1.2 Function Notation - Textbook [Questions + Answers]
Logic and Propositional Calculus Question Bank Set 5
of 132
Recommended Documents
⏰ Deadline pressure?
Get your assignment done in just 3 hours. Quick, easy, and available 24/7.
Report
Tell us what’s wrong with it:
Thanks, got it!
We will moderate it soon!
Free up your schedule!
Our EduBirdie Experts Are Here for You 24/7! Just fill out a form and let us know how we can assist you.
Take 5 seconds to unlock
Enter your email below and get instant access to your document