MATH 250 - INTRODUCTION TO
DISCRETE MATHEMATICS - Logic
and Propositional Calculus
Question Bank - Set 2
Liberty University
Question 1
Question
Let p,q, and rbe propositions. Show that the proposition (p→q)∧(q→r)→
(p→r) is a tautology using truth tables.
Solution
To show that the proposition is a tautology, we need to show that its truth table
evaluates to true for all possible truth values of p,q, and r.
Step 1: Create the truth table for (p→q)∧(q→r)→(p→r).
p q r p →q q →r(p→q)∧(q→r)p→r(p→q)∧(q→r)→(p→r)
T T T T T T T T
T T F T F F F T
T F T F T F T T
T F F F T F F T
F T T T T T T T
F T F T F F T T
F F T T T T T T
F F F T T T T T
Step 2: Analyze the truth table.
Since the final column evaluates to true for all rows, the proposition (p→
q)∧(q→r)→(p→r) is a tautology. Thus, the proposition is always true
regardless of the truth values of p,q, and r.
Question 2
Question
Let pand qbe propositions. Prove that (p→q)∧(q→p) is logically equivalent
to (p∧q)∨(¬p∧ ¬q).
Solution
To prove the logical equivalence of the given expressions, we will show that they
have the same Truth Table.
Step 1: Construct the Truth Table for (p→q)∧(q→p).
p q p →q q →p(p→q)∧(q→p)
T T T T T
T F F T F
F T T F F
F F T T T
Step 2: Construct the Truth Table for (p∧q)∨(¬p∧ ¬q).
p q p ∧q¬p¬q(¬p∧ ¬q)
(p∧q)∨(¬p∧ ¬q)
T T T F F F
T
T F F F T F
F
F T F T F F
F
F F F T T T
T
Step 3: Conclusion
From the truth tables, we can see that both (p→q)∧(q→p) and (p∧
q)∨(¬p∧ ¬q) have the same truth values for all possible combinations of truth
values of pand q. Therefore, we have proved that they are logically equivalent.
Question 3
Question
Let p,q, and rbe propositions. Show whether the following argument is valid
or not using propositional logic:
If pthen q.
If qthen r.
Therefore, if pthen r.
2
Solution
To determine the validity of the argument, we will use the method of direct
proof in propositional logic.
Step 1: Assume p→qis true and q→ris true.
Given: p→qand q→r.
To prove: p→r.
Step 2: Based on the given information, we can write the implications in
terms of logic operators: - p→qis equivalent to ¬p∨q. - q→ris equivalent
to ¬q∨r.
Step 3: Construct the truth table for ¬p∨qand ¬q∨r:
p q r ¬p∨q¬q∨r(¬p∨q)∧(¬q∨r)
T T T T T T
T T F T F F
T F T F T F
T F F F T F
F T T T T T
F T F T F F
F F T T T T
F F F T T T
Since the last column is not always true, the argument is invalid.
Therefore, the argument ”If pthen q, if qthen r, therefore if pthen r” is
not valid in general.
Question 4
Question
Let pand qbe propositions. Show that the statement (p⇒q)⇒pis a tautology
using truth tables.
Solution
To show that (p⇒q)⇒pis a tautology, we need to show that the statement
is true for all possible truth values of pand q.
Step 1: Create a truth table for (p⇒q)⇒p:
p q (p⇒q) (p⇒q)⇒p
T T T T
T F F T
F T T F
F F T T
Step 2: Verify that (p⇒q)⇒pis true for all rows: From the truth
table, we can see that (p⇒q)⇒pis true for all possible truth values of pand
q, making it a tautology.
3
Question 5
Question
Let p, q be propositions. Show that the statement (p→q)∧(q→p) is logically
equivalent to p↔q.
Solution
To show that (p→q)∧(q→p) is logically equivalent to p↔q, we need to
show that they have the same truth values for all possible truth values of pand
q. We can do this by constructing truth tables for both propositions.
Step 1: Construct a truth table for (p→q)∧(q→p)
p q p →q q →p(p→q)∧(q→p)
T T T T T
T F F T F
F T T F F
F F T T T
Step 2: Construct a truth table for p↔q
The logical biconditional p↔qis true if pand qhave the same truth value,
otherwise it is false.
p q p ↔q
T T T
T F F
F T F
F F T
Step 3: Conclusion
Comparing the truth tables for (p→q)∧(q→p) and p↔q, we can see
that they have the same truth values for all possible truth values of pand q.
Therefore, (p→q)∧(q→p) is logically equivalent to p↔q.
Question 6
Question
Let p,q, and rbe propositional variables. Show that the statement (p∧q)→r
is logically equivalent to ¬p∨ ¬q∨r.
Solution
To show that the statements (p∧q)→rand ¬p∨ ¬q∨rare logically equivalent,
we will use logical equivalences to transform one statement into the other.
Step 1: Start with the statement (p∧q)→r.
(p∧q)→r
4
Step 2: Use the definition of the conditional p→q≡ ¬p∨q.
¬(p∧q)∨r
Step 3: Use De Morgan’s Law: ¬(p∧q)≡ ¬p∨ ¬q.
(¬p∨ ¬q)∨r
Step 4: Associative property: a∨(b∨c)≡(a∨b)∨c.
¬p∨(¬q∨r)
Step 5: Associative property again.
¬p∨ ¬q∨r
Therefore, we have shown that (p∧q)→ris logically equivalent to ¬p∨¬q∨r.
Question 7
Question
Let p,q, and rbe propositions. Determine whether the statement (p∧q)→r
is logically equivalent to ¬p∨(¬q∨r).
Solution
To determine if the two statements are logically equivalent, we can use a truth
table to analyze all possible truth values of p,q, and r.
p q r p ∧q(p∧q)→r¬p¬q∨r¬p∨(¬q∨r)
T T T T T F T T
T T F T F F F F
T F T F T F T T
T F F F T F T T
F T T F T T T T
F T F F T T T T
F F T F T T T T
F F F F T T T T
Since the truth values of (p∧q)→rand ¬p∨(¬q∨r) are the same for all
possible truth values of p,q, and r, we can conclude that the two statements
are logically equivalent.
Question 8
Question
Let pand qbe propositions. Show that the following proposition is a tautology:
(p→q)∨(q→p)
5
Solution
To show that the given proposition is a tautology, we can either use a truth
table to check all possible truth values, or we can use logical equivalences to
simplify the expression and show that it simplifies to true for all possible truth
values of pand q.
Using logical equivalences, let’s simplify the given proposition:
(Negation)
Therefore, (p→q)∨(q→p) simplifies to true, which means it is a tautology.
Question 9
Question
Let p,q, and rbe propositions. Prove or disprove the following logical equiva-
lence: (p∧q)→r≡p→(q→r).
Solution
To prove or disprove the logical equivalence (p∧q)→r≡p→(q→r), we will
construct truth tables for both expressions and compare them.
Step 1: Construct the truth table for (p∧q)→r
p q r (p∧q) (p∧q)→r
T T T T T
T T F T F
T F T F T
T F F F T
F T T F T
F T F F T
F F T F T
F F F F T
6
Step 2: Construct the truth table for p→(q→r)
p q r (q→r)p→(q→r)
T T T T T
T T F T T
T F T T T
T F F T T
F T T T T
F T F F T
F F T T T
F F F T T
Step 3: Compare the truth tables By comparing the truth tables for
(p∧q)→rand p→(q→r), we see that they are not equivalent. In the second
row, (p∧q)→rhas a truth value of Fwhile p→(q→r) has a truth value of
T, indicating a mismatch.
Therefore, we have disproved the logical equivalence (p∧q)→r≡p→(q→
r).
Question 10
Question
Let p,q, and rbe propositions. Prove or disprove the following statement:
(p→q)∧(q→r)→(p→r).
Solution
To prove or disprove the statement, we will use the truth table method.
Step 1: Create a Truth Table We will create a truth table with columns
for p,q,r, (p→q), (q→r), and (p→r). There are 8 possible truth value
combinations for p,q, and r.
p q r p →q q →r p →r
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F
Step 2: Fill in Compound Propositional Statements We will fill in
the columns for (p→q), (q→r), and (p→r) based on the truth values of p,
q, and r.
7
p q r p →q q →r p →r
T T T T T T
T T F T F F
T F T F T T
T F F F T F
F T T T T T
F T F T F T
F F T T T T
F F F T T T
Step 3: Analyze the Last Column Looking at the truth values of p→r
in the last column of the truth table, we can see that it doesn’t always match the
value of (p→q)∧(q→r). Therefore, the statement (p→q)∧(q→r)→(p→r)
is disproved.
Question 11
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using a truth table.
Solution
To show that the given compound proposition is a tautology, we will construct
a truth table to examine all possible truth values of p,q, and r.
p q r p →q q →r(p→q)∧(q→r) (p→r)
T T T T T T T
T T F T F F F
T F T F T F T
T F F F T F F
F T T T T T T
F T F T F F T
F F T T T T T
F F F T T T T
Since the final column of the truth table is always true, the compound propo-
sition (p→q)∧(q→r)→(p→r) is a tautology.
Question 12
Question
Let prepresent the statement ”It is sunny,” qrepresent the statement ”It is
raining,” and rrepresent the statement ”It is Monday.” Translate the following
8
statement into a logical expression:
”If it is not Monday, then either it is sunny or it is raining.”
Solution
To translate the given statement into a logical expression, we need to consider
the logical operators involved and their corresponding symbols in propositional
calculus.
Let’s break down the given statement: - ”It is not Monday” can be repre-
sented as ¬r. - ”Either it is sunny or it is raining” can be represented as (p∨q)
(translated using the inclusive or operator).
Therefore, the translation of the given statement into a logical expression is
¬r→(p∨q).
So, ”If it is not Monday, then either it is sunny or it is raining” can be
represented as ¬r→(p∨q).
Question 13
Question
Let pand qbe propositions. Show that the proposition (p→q)→(¬p∨q) is
a tautology using truth tables.
Solution
To show that (p→q)→(¬p∨q) is a tautology, we need to show that the
proposition is true for all possible truth values of pand q.
p q p →q¬p¬p∨q(p→q)→(¬p∨q)
T T T F T T
T F F F F T
F T T T T T
F F T T T T
As shown in the truth table, the final column evaluates to true for all possible
truth values of pand q. Therefore, (p→q)→(¬p∨q) is a tautology.
Question 14
Question
Let p,q, and rbe propositions. Determine whether the following statement is
a tautology, contradiction, or contingent:
(p∧q)→ ¬p∨(p∧r)
9
Solution
To determine whether the given statement is a tautology, contradiction, or con-
tingent, we will construct a truth table for all possible truth values of p,q, and
rand evaluate the truth value of the given statement for each combination of
truth values.
p q r (p∧q)¬p∨(p∧r) (p∧q)→ ¬p∨(p∧r)
T T T T T T
T T F T T T
T F T F F T
T F F F F T
F T T F T T
F T F F T T
F F T F T T
F F F F T T
From the truth table, we can see that the given statement evaluates to
true for all possible truth values of p,q, and r. Therefore, the statement is a
tautology.
Question 15
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will use a truth
table to analyze all possible truth values of p,q, and r.
p q r p →q q →r(p→q)∧(q→r)p→r(p→q)∧(q→r)→(p→r)
T T T T T T T T
T T F T F F F T
T F T F T F T T
T F F F T F F T
F T T T T T T T
F T F T F F T T
F F T T T T T T
F F F T T T T T
Since the final column of the truth table is always true, we conclude that
(p→q)∧(q→r)→(p→r) is a tautology.
10
Question 16
Question
Let p,q, and rbe propositions. Show that the proposition (p∧q)∨(q∧r)∨(r∧p)
is logically equivalent to (p∨q)∧(q∨r)∧(r∨p).
Solution
To show that (p∧q)∨(q∧r)∨(r∧p) is logically equivalent to (p∨q)∧(q∨r)∧(r∨p),
we can use basic laws of logic and propositional calculus.
Step 1: Show (p∧q)∨(q∧r)∨(r∧p)⇒(p∨q)∧(q∨r)∧(r∨p):
Starting with (p∧q)∨(q∧r)∨(r∧p), we can distribute the ∨over ∧using
the distributive law:
(p∧q)∨(q∧r)∨(r∧p)≡(p∨q)∧(p∨r)∧(q∨r)
Next, we can rearrange the terms in the right-hand side to match the form
of (p∨q)∧(q∨r)∧(r∨p):
(p∧q)∨(q∧r)∨(r∧p)⇒(p∨q)∧(q∨r)∧(r∨p)
Step 2: Show (p∨q)∧(q∨r)∧(r∨p)⇒(p∧q)∨(q∧r)∨(r∧p):
Starting with (p∨q)∧(q∨r)∧(r∨p), we can distribute the ∧over ∨using
the distributive law:
(p∨q)∧(q∨r)∧(r∨p)≡(p∧q)∨(p∧r)∨(q∧r)
Next, we can rearrange the terms in the right-hand side to match the form
of (p∧q)∨(q∧r)∨(r∧p):
(p∨q)∧(q∨r)∧(r∨p)⇒(p∧q)∨(q∧r)∨(r∧p)
Therefore, we have shown that (p∧q)∨(q∧r)∨(r∧p) is logically equivalent
to (p∨q)∧(q∨r)∧(r∨p).
Question 17
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using propositional calculus.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will use a direct
proof technique by assuming the hypothesis is false and reaching a contradiction.
11
Step 1: Write the implication as a conjunction: We start by writing
the given implication as a conjunction of implications:
(p→q)∧(q→r)→(p→r)≡ ¬((p→q)∧(q→r)) ∨(p→r)
Step 2: Apply De Morgan’s Law: Using De Morgan’s Law, we can
rewrite the negated conjunction as a disjunction of negations:
¬((p→q)∧(q→r)) ≡ ¬(p→q)∨ ¬(q→r)
Step 3: Apply the Conditional Connective: We rewrite the negations
of implications using the definition of the conditional connective:
¬(p→q)∨ ¬(q→r)≡ ¬(¬p∨q)∨ ¬(¬q∨r)
Step 4: Apply Double Negation and De Morgan’s Law: We simplify
the negations and use De Morgan’s Law to expand the expression:
¬(¬p∨q)∨ ¬(¬q∨r)≡(p∧ ¬q)∨(q∧ ¬r)
Step 5: Apply Distributive Law: Using the Distributive Law, we can
simplify the expression further:
(p∧ ¬q)∨(q∧ ¬r)≡(p∨q)∧(p∨ ¬r)∧(¬q∨q)∧(¬q∨ ¬r)
Step 6: Eliminate Contradictions: We notice that (¬q∨q) and (¬q∨¬r)
are contradictions, so the conjunction simplifies to:
(p∨ ¬r)∧(p∨q)
Step 7: Apply the Definition of Implication: Finally, we use the
definition of implication to rewrite the simplified conjunction:
(p∨ ¬r)∧(p∨q)≡p→r
Since we ended up with p→r, which is logically equivalent to the original
expression, we have shown that (p→q)∧(q→r)→(p→r) is a tautology.
Question 18
Question
Let p,q, and rbe propositions. Show that (p∧q)→ris logically equivalent to
p→(q→r).
12
Solution
To show that (p∧q)→ris logically equivalent to p→(q→r), we need to
show that the two propositions have the same truth values for all possible truth
values of p,q, and r.
Step 1: Truth Table for (p∧q)→r
p q r (p∧q) (p∧q)→r p →(q→r)
T T T T T T
T T F T F F
T F T F T T
T F F F T T
F T T F T T
F T F F T T
F F T F T T
F F F F T T
Since the truth values of (p∧q)→rand p→(q→r) are the same for all
possible truth values of p,q, and r, we can conclude that (p∧q)→ris logically
equivalent to p→(q→r).
Question 19
Question
Let p,q, and rbe propositions. Prove or disprove the following statement:
(p∧q)∨r≡(p∨r)∧(q∨r)
Solution
To prove or disprove the given statement, we can use truth tables to compare
the truth values of both sides of the equivalence.
Step 1: Create a truth table for (p∧q)∨rand (p∨r)∧(q∨r).
We consider all possible combinations of truth values for p,q, and r:
p q r p ∧q(p∧q)∨r p ∨r q ∨r(p∨r)∧(q∨r)
T T T T T T T T
T T F T T T T T
T F T F T T T T
T F F F F T F F
F T T F T T T T
F T F F F F T F
F F T F T T T T
F F F F F F F F
Step 2: Compare the truth values of both sides.
13
From the truth table, we can see that the truth values of (p∧q)∨rand
(p∨r)∧(q∨r) are not always the same, so the statement is disproved.
Therefore, we have shown that (p∧q)∨r≡ (p∨r)∧(q∨r) for all possible
truth values of p,q, and r.
Question 20
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(q∧r)⇒(p∨r) is a
tautology using propositional calculus.
Solution
To show that the implication (p∧q)∨(q∧r)⇒(p∨r) is a tautology, we will
use a logical equivalency.
Step 1: Apply the distributive law for disjunction over conjunction to obtain
the following:
(p∧q)∨(q∧r)⇒(p∨r)
≡¬[(p∧q)∨(q∧r)] ∨(p∨r) (Implication as disjunction)
≡¬(p∧q)∧ ¬(q∧r)∨(p∨r) (De Morgan’s Law)
≡(¬p∨ ¬q)∧(¬q∨ ¬r)∨(p∨r) (De Morgan’s Law)
Step 2: Apply the distributive law for conjunction over disjunction to obtain
the following:
(¬p∨ ¬q)∧(¬q∨ ¬r)∨(p∨r)
≡[(¬p∨ ¬q)∧(¬q∨ ¬r)] ∨[(¬p∨ ¬q)∧(p∨r)] (Distributive Law)
≡[(¬p∧ ¬q)∨(¬p∧ ¬r)] ∨[(¬q∧ ¬q)∨(p∧r)] (Distributive Law)
≡(¬p∧ ¬q)∨(¬p∧ ¬r)∨(¬q∧ ¬q)∨(p∧r) (Associative Law)
≡¬p∧(¬q∨ ¬r)∨F∨(p∧r) (Negation Law)
≡¬p∧ ¬(q∧r)∨(p∧r) (Negated Disjunction)
Step 3: Apply the distributive law for disjunction over conjunction to obtain
the following:
¬p∧ ¬(q∧r)∨(p∧r)
≡¬p∨(p∧r)∧ ¬(q∧r) (Distributive Law)
≡(¬p∨p)∧(¬p∨r)∧(¬q∨ ¬r) (Distribution)
≡T∧(¬p∨r)∧(¬q∨ ¬r) (Negation Law)
≡(¬p∨r)∧(¬q∨ ¬r) (Identity Law)
≡(¬p∨r)∧ ¬(q∧r) (De Morgan’s Law)
≡¬[(p∧q)∨(q∧r)] ∨(p∨r) (Implication as Disjunction)
≡(p∧q)∨(q∧r)⇒(p∨r) (Implication as Disjunction)
14
Therefore, we have shown that the implication (p∧q)∨(q∧r)⇒(p∨r) is
a tautology.
Question 21
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we can use
logical equivalence laws and truth tables.
Step 1: Write the truth tables for both propositions
The truth table for (p∧q)∨(p∧r) is:
p q r p ∧q p ∧r(p∧q)∨(p∧r)
T T T T T T
T T F T F T
T F T F T T
T F F F F F
F T T F F F
F T F F F F
F F T F F F
F F F F F F
The truth table for p∧(q∨r) is:
p q r q ∨r p ∧(q∨r)
T T T T T
T T F T T
T F T T T
T F F F F
F T T T F
F T F T F
F F T T F
F F F F F
Step 2: Compare the truth values in both truth tables
By comparing the truth values in both truth tables, we observe that the truth
values for (p∧q)∨(p∧r) and p∧(q∨r) are the same for all possible combinations
of truth values of p,q, and r. Hence, we can conclude that (p∧q)∨(p∧r) is
logically equivalent to p∧(q∨r).
15
Question 22
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using propositional calculus.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will use a truth
table to demonstrate that the compound proposition is true for all possible truth
values of p,q, and r.
p q r p →q q →r(p→q)∧(q→r)p→r
T T T T T T T
T T F T F F F
T F T F T F T
T F F F T F F
F T T T T T T
F T F T F F T
F F T T T T T
F F F T T T T
As seen in the truth table, the final column is always true regardless of the
truth values of p,q, and r. Therefore, (p→q)∧(q→r)→(p→r) is a
tautology.
Question 23
Question
Let pand qbe propositions. Prove that (p→q)∨(q→p) is a tautology.
Solution
To prove that (p→q)∨(q→p) is a tautology, we can use a truth table to show
that the statement is true for all possible truth values of pand q.
p q p →q q →p(p→q)∨(q→p)
T T T T T
T F F T T
F T T F T
F F T T T
Since the final column of the truth table is always true, we can conclude that
(p→q)∨(q→p) is a tautology.
16
Question 24
Question
Let p,q, and rbe propositions. Prove or disprove the statement: (p→q)∧(q→
r)→(p→r).
Solution
To prove or disprove the statement (p→q)∧(q→r)→(p→r), we will
construct a truth table to analyze all possible truth values of p,q, and r.
p q r p →q q →r(p→q)∧(q→r)p→r
T T T T T T T
T T F T F F F
T F T F T F T
T F F F T F F
F T T T T T T
F T F T F F T
F F T T T T T
F F F T T T T
From the truth table, we see that there are instances where (p→q)∧(q→r)
is true while p→ris false. Therefore, the statement (p→q)∧(q→r)→(p→
r) is disproved.
Question 25
Question
Let pbe the proposition ”I will pass the exam” and qbe the proposition ”I will
study hard”. Express the statement ”If I pass the exam, then I studied hard”
using pand qusing logical connectives.
Solution
To express the statement ”If I pass the exam, then I studied hard” using pand
q, we can use the logical connective ”implies”, denoted by →. The statement
can be written as p→q.
Therefore, the expression for the statement is: p→q.
Question 26
Question
Let prepresent the statement ”I will go to the beach” and qrepresent the
statement ”I will go swimming.” Write the following compound statement in
17
symbolic form: ”I will go to the beach if and only if I will go swimming.”
Solution
To express the compound statement ”I will go to the beach if and only if I will
go swimming” in symbolic form, we can use the biconditional connective ↔,
which means ”if and only if”.
Let: p= ”I will go to the beach”
q= ”I will go swimming”
The compound statement can be represented as: p↔q
Therefore, the symbolic form of the given compound statement is ”p↔q”.
Question 27
Question
Let p,q, and rbe propositions. Prove the following logical equivalence: (p−→
q)∧(q−→ r)≡(p∧q)−→ r.
Solution
To prove the logical equivalence (p−→ q)∧(q−→ r)≡(p∧q)−→ r, we will
show that both sides are logically equivalent by constructing truth tables for
each side and demonstrating they have the same truth values for all possible
combinations of truth values for p,q, and r.
Step 1: Create a truth table for (p−→ q)∧(q−→ r)
p q r p −→ q q −→ r(p−→ q)∧(q−→ r)
T T T T T T
T T F T F F
T F T F T F
T F F F T F
F T T T T T
F T F T F F
F F T T T T
F F F T T T
Step 2: Create a truth table for (p∧q)−→ r
18
p q r p ∧q(p∧q)−→ r
T T T T T
T T F T F
T F T F T
T F F F T
F T T F T
F T F F T
F F T F T
F F F F T
Step 3: Conclusion
Comparing the truth tables for (p−→ q)∧(q−→ r) and (p∧q)−→ r, we
can see that the two statements are logically equivalent as their truth values
match for all possible combinations of truth values for p,q, and r. Therefore,
we have proved the logical equivalence (p−→ q)∧(q−→ r)≡(p∧q)−→ r.
Question 28
Question
Let p,q, and rbe propositions. Show that (p⇒q)∧(q⇒r)⇒(p⇒r) is a
tautology using a truth table.
Solution
To show that (p⇒q)∧(q⇒r)⇒(p⇒r) is a tautology, we will construct a
truth table for the proposition.
Step 1: Construct the truth table for (p⇒q)∧(q⇒r)⇒(p⇒r).
p q r p ⇒q q ⇒r(p⇒q)∧(q⇒r)p⇒r(p⇒q)∧(q⇒r)⇒(p⇒r)
T T T T T T T T
T T F T F F F T
T F T F T F T T
T F F F T F F T
F T T T T T T T
F T F T F F T T
F F T T T T T T
F F F T T T T T
Since the final column has all ”T” values, we have shown that (p⇒q)∧(q⇒
r)⇒(p⇒r) is a tautology.
19
Question 29
Question
Let p,q, and rbe propositions where:
p: ”It is raining.”
q: ”The streets are wet.”
r: ”There are traffic jams.”
Translate the following statement into propositional logic: ”If it is raining
and the streets are wet, then there are traffic jams.”
Solution
To express the given statement in propositional logic, we need to define the
logical operators and their corresponding meanings:
∧: ”and”
→: ”if...then”
Let’s define p,q, and rin terms of the given propositions:
p: ”It is raining.”
q: ”The streets are wet.”
r: ”There are traffic jams.”
Now, we can translate the statement into propositional logic form:
(p∧q)→r
Question 30
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using logical equivalences.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we need to show that
the statement is always true regardless of the truth values of p,q, and r. We
will use logical equivalences to simplify the expression.
Identity Laws
Therefore, (p→q)∧(q→r)→(p→r) is a tautology.
20
Question 31
Question
Let pand qbe propositions. Prove or disprove the following statement: (p→
q)∧(¬p→ ¬q)→(p↔q).
Solution
To prove or disprove the statement (p→q)∧(¬p→ ¬q)→(p↔q), we can
construct a truth table to analyze all possible truth values of pand q.
p q p →q¬p¬q¬p→ ¬q p ↔q(p→q)∧(¬p→ ¬q)→(p↔q)
T T T F F T T T
T F F F T T F T
F T T T F F F T
F F T T T T T F
The truth table shows that the statement is false when pis false and qis
false. Therefore, the statement (p→q)∧(¬p→ ¬q)→(p↔q) is disproved.
Question 32
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we must show
that the truth values of both expressions are the same for all possible truth
values of p,q, and r. We can do this by constructing truth tables for both
expressions.
Step 1: Construct a truth table for (p∧q)∨(p∧r)
p q r p ∧q p ∧r(p∧q)∨(p∧r)
T T T T T T
T T F T F T
T F T F T T
T F F F F F
F T T F F F
F T F F F F
F F T F F F
F F F F F F
21
Step 2: Construct a truth table for p∧(q∨r)
p q r q ∨r p ∧(q∨r)
T T T T T
T T F T T
T F T T T
T F F F F
F T T T F
F T F T F
F F T T F
F F F F F
Step 3: Conclusion From the truth tables, we can see that both (p∧q)∨
(p∧r) and p∧(q∨r) have the same truth values for all possible truth values of
p,q, and r. Therefore, we have shown that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Question 33
Question
Let p,q, and rbe propositions. Show that (p∧q)→ris logically equivalent to
(p→r)∨(q→r).
Solution
To show that (p∧q)→ris logically equivalent to (p→r)∨(q→r), we will
construct truth tables for both propositions and show that they have the same
truth values.
p q r (p∧q) (p∧q)→r(p→r) (q→r)
T T T T T T T
T T F T F F F
T F T F T T T
T F F F T F T
F T T F T T T
F T F F T T F
F F T F T T T
F F F F T T T
From the truth table above, we can see that (p∧q)→rhas the same
truth values as (p→r)∨(q→r) for all combinations of truth values for p,
q, and r. Therefore, we have shown that (p∧q)→ris logically equivalent to
(p→r)∨(q→r).
22
Question 34
Question
Let p,q, and rbe propositions. Show that the proposition (p→q)∧(q→r)→
(p→r) is a tautology.
Solution
Step 1: To show that (p→q)∧(q→r)→(p→r) is a tautology, we can
construct a truth table to check all possible truth values of p,q, and r.
p q r p →q q →r(p→q)∧(q→r)p→r(p→q)∧(q→r)→(p→r)
T T T T T T T T
T T F T F F F T
T F T F T F T T
T F F F T F F T
F T T T T T T T
F T F T F F T T
F F T T T T T T
F F F T T T T T
Step 2: From the truth table, we can see that the last column, which repre-
sents (p→q)∧(q→r)→(p→r), is always true. Therefore, the proposition
(p→q)∧(q→r)→(p→r) is a tautology.
Question 35
Question
Let p,q, and rbe propositions. Prove the following statement using laws of
logic and propositional calculus:
(p→q)∧(q→r)→(p→r)
Solution
To prove the statement (p→q)∧(q→r)→(p→r), we will use the rules of
logic and propositional calculus.
23
Question 2
Question
Let pand qbe propositions. Prove that (p→q)∧(q→p) is logically equivalent
to (p∧q)∨(¬p∧ ¬q).
Solution
To prove the logical equivalence of the given expressions, we will show that they
have the same Truth Table.
Step 1: Construct the Truth Table for (p→q)∧(q→p).
p q p →q q →p(p→q)∧(q→p)
T T T T T
T F F T F
F T T F F
F F T T T
Step 2: Construct the Truth Table for (p∧q)∨(¬p∧ ¬q).
p q p ∧q¬p¬q(¬p∧ ¬q)
(p∧q)∨(¬p∧ ¬q)
T T T F F F
T
T F F F T F
F
F T F T F F
F
F F F T T T
T
Step 3: Conclusion
From the truth tables, we can see that both (p→q)∧(q→p) and (p∧
q)∨(¬p∧ ¬q) have the same truth values for all possible combinations of truth
values of pand q. Therefore, we have proved that they are logically equivalent.
Question 3
Question
Let p,q, and rbe propositions. Show whether the following argument is valid
or not using propositional logic:
If pthen q.
If qthen r.
Therefore, if pthen r.
2
Solution
To determine the validity of the argument, we will use the method of direct
proof in propositional logic.
Step 1: Assume p→qis true and q→ris true.
Given: p→qand q→r.
To prove: p→r.
Step 2: Based on the given information, we can write the implications in
terms of logic operators: - p→qis equivalent to ¬p∨q. - q→ris equivalent
to ¬q∨r.
Step 3: Construct the truth table for ¬p∨qand ¬q∨r:
p q r ¬p∨q¬q∨r(¬p∨q)∧(¬q∨r)
T T T T T T
T T F T F F
T F T F T F
T F F F T F
F T T T T T
F T F T F F
F F T T T T
F F F T T T
Since the last column is not always true, the argument is invalid.
Therefore, the argument ”If pthen q, if qthen r, therefore if pthen r” is
not valid in general.
Question 4
Question
Let pand qbe propositions. Show that the statement (p⇒q)⇒pis a tautology
using truth tables.
Solution
To show that (p⇒q)⇒pis a tautology, we need to show that the statement
is true for all possible truth values of pand q.
Step 1: Create a truth table for (p⇒q)⇒p:
p q (p⇒q) (p⇒q)⇒p
T T T T
T F F T
F T T F
F F T T
Step 2: Verify that (p⇒q)⇒pis true for all rows: From the truth
table, we can see that (p⇒q)⇒pis true for all possible truth values of pand
q, making it a tautology.
3
Question 5
Question
Let p, q be propositions. Show that the statement (p→q)∧(q→p) is logically
equivalent to p↔q.
Solution
To show that (p→q)∧(q→p) is logically equivalent to p↔q, we need to
show that they have the same truth values for all possible truth values of pand
q. We can do this by constructing truth tables for both propositions.
Step 1: Construct a truth table for (p→q)∧(q→p)
p q p →q q →p(p→q)∧(q→p)
T T T T T
T F F T F
F T T F F
F F T T T
Step 2: Construct a truth table for p↔q
The logical biconditional p↔qis true if pand qhave the same truth value,
otherwise it is false.
p q p ↔q
T T T
T F F
F T F
F F T
Step 3: Conclusion
Comparing the truth tables for (p→q)∧(q→p) and p↔q, we can see
that they have the same truth values for all possible truth values of pand q.
Therefore, (p→q)∧(q→p) is logically equivalent to p↔q.
Question 6
Question
Let p,q, and rbe propositional variables. Show that the statement (p∧q)→r
is logically equivalent to ¬p∨ ¬q∨r.
Solution
To show that the statements (p∧q)→rand ¬p∨ ¬q∨rare logically equivalent,
we will use logical equivalences to transform one statement into the other.
Step 1: Start with the statement (p∧q)→r.
(p∧q)→r
4
Step 2: Use the definition of the conditional p→q≡ ¬p∨q.
¬(p∧q)∨r
Step 3: Use De Morgan’s Law: ¬(p∧q)≡ ¬p∨ ¬q.
(¬p∨ ¬q)∨r
Step 4: Associative property: a∨(b∨c)≡(a∨b)∨c.
¬p∨(¬q∨r)
Step 5: Associative property again.
¬p∨ ¬q∨r
Therefore, we have shown that (p∧q)→ris logically equivalent to ¬p∨¬q∨r.
Question 7
Question
Let p,q, and rbe propositions. Determine whether the statement (p∧q)→r
is logically equivalent to ¬p∨(¬q∨r).
Solution
To determine if the two statements are logically equivalent, we can use a truth
table to analyze all possible truth values of p,q, and r.
p q r p ∧q(p∧q)→r¬p¬q∨r¬p∨(¬q∨r)
T T T T T F T T
T T F T F F F F
T F T F T F T T
T F F F T F T T
F T T F T T T T
F T F F T T T T
F F T F T T T T
F F F F T T T T
Since the truth values of (p∧q)→rand ¬p∨(¬q∨r) are the same for all
possible truth values of p,q, and r, we can conclude that the two statements
are logically equivalent.
Question 8
Question
Let pand qbe propositions. Show that the following proposition is a tautology:
(p→q)∨(q→p)
5
Solution
To show that the given proposition is a tautology, we can either use a truth
table to check all possible truth values, or we can use logical equivalences to
simplify the expression and show that it simplifies to true for all possible truth
values of pand q.
Using logical equivalences, let’s simplify the given proposition:
(Negation)
Therefore, (p→q)∨(q→p) simplifies to true, which means it is a tautology.
Question 9
Question
Let p,q, and rbe propositions. Prove or disprove the following logical equiva-
lence: (p∧q)→r≡p→(q→r).
Solution
To prove or disprove the logical equivalence (p∧q)→r≡p→(q→r), we will
construct truth tables for both expressions and compare them.
Step 1: Construct the truth table for (p∧q)→r
p q r (p∧q) (p∧q)→r
T T T T T
T T F T F
T F T F T
T F F F T
F T T F T
F T F F T
F F T F T
F F F F T
6
Step 2: Construct the truth table for p→(q→r)
p q r (q→r)p→(q→r)
T T T T T
T T F T T
T F T T T
T F F T T
F T T T T
F T F F T
F F T T T
F F F T T
Step 3: Compare the truth tables By comparing the truth tables for
(p∧q)→rand p→(q→r), we see that they are not equivalent. In the second
row, (p∧q)→rhas a truth value of Fwhile p→(q→r) has a truth value of
T, indicating a mismatch.
Therefore, we have disproved the logical equivalence (p∧q)→r≡p→(q→
r).
Question 10
Question
Let p,q, and rbe propositions. Prove or disprove the following statement:
(p→q)∧(q→r)→(p→r).
Solution
To prove or disprove the statement, we will use the truth table method.
Step 1: Create a Truth Table We will create a truth table with columns
for p,q,r, (p→q), (q→r), and (p→r). There are 8 possible truth value
combinations for p,q, and r.
p q r p →q q →r p →r
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F
Step 2: Fill in Compound Propositional Statements We will fill in
the columns for (p→q), (q→r), and (p→r) based on the truth values of p,
q, and r.
7
p q r p →q q →r p →r
T T T T T T
T T F T F F
T F T F T T
T F F F T F
F T T T T T
F T F T F T
F F T T T T
F F F T T T
Step 3: Analyze the Last Column Looking at the truth values of p→r
in the last column of the truth table, we can see that it doesn’t always match the
value of (p→q)∧(q→r). Therefore, the statement (p→q)∧(q→r)→(p→r)
is disproved.
Question 11
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using a truth table.
Solution
To show that the given compound proposition is a tautology, we will construct
a truth table to examine all possible truth values of p,q, and r.
p q r p →q q →r(p→q)∧(q→r) (p→r)
T T T T T T T
T T F T F F F
T F T F T F T
T F F F T F F
F T T T T T T
F T F T F F T
F F T T T T T
F F F T T T T
Since the final column of the truth table is always true, the compound propo-
sition (p→q)∧(q→r)→(p→r) is a tautology.
Question 12
Question
Let prepresent the statement ”It is sunny,” qrepresent the statement ”It is
raining,” and rrepresent the statement ”It is Monday.” Translate the following
8
statement into a logical expression:
”If it is not Monday, then either it is sunny or it is raining.”
Solution
To translate the given statement into a logical expression, we need to consider
the logical operators involved and their corresponding symbols in propositional
calculus.
Let’s break down the given statement: - ”It is not Monday” can be repre-
sented as ¬r. - ”Either it is sunny or it is raining” can be represented as (p∨q)
(translated using the inclusive or operator).
Therefore, the translation of the given statement into a logical expression is
¬r→(p∨q).
So, ”If it is not Monday, then either it is sunny or it is raining” can be
represented as ¬r→(p∨q).
Question 13
Question
Let pand qbe propositions. Show that the proposition (p→q)→(¬p∨q) is
a tautology using truth tables.
Solution
To show that (p→q)→(¬p∨q) is a tautology, we need to show that the
proposition is true for all possible truth values of pand q.
p q p →q¬p¬p∨q(p→q)→(¬p∨q)
T T T F T T
T F F F F T
F T T T T T
F F T T T T
As shown in the truth table, the final column evaluates to true for all possible
truth values of pand q. Therefore, (p→q)→(¬p∨q) is a tautology.
Question 14
Question
Let p,q, and rbe propositions. Determine whether the following statement is
a tautology, contradiction, or contingent:
(p∧q)→ ¬p∨(p∧r)
9
Solution
To determine whether the given statement is a tautology, contradiction, or con-
tingent, we will construct a truth table for all possible truth values of p,q, and
rand evaluate the truth value of the given statement for each combination of
truth values.
p q r (p∧q)¬p∨(p∧r) (p∧q)→ ¬p∨(p∧r)
T T T T T T
T T F T T T
T F T F F T
T F F F F T
F T T F T T
F T F F T T
F F T F T T
F F F F T T
From the truth table, we can see that the given statement evaluates to
true for all possible truth values of p,q, and r. Therefore, the statement is a
tautology.
Question 15
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will use a truth
table to analyze all possible truth values of p,q, and r.
p q r p →q q →r(p→q)∧(q→r)p→r(p→q)∧(q→r)→(p→r)
T T T T T T T T
T T F T F F F T
T F T F T F T T
T F F F T F F T
F T T T T T T T
F T F T F F T T
F F T T T T T T
F F F T T T T T
Since the final column of the truth table is always true, we conclude that
(p→q)∧(q→r)→(p→r) is a tautology.
10
Question 16
Question
Let p,q, and rbe propositions. Show that the proposition (p∧q)∨(q∧r)∨(r∧p)
is logically equivalent to (p∨q)∧(q∨r)∧(r∨p).
Solution
To show that (p∧q)∨(q∧r)∨(r∧p) is logically equivalent to (p∨q)∧(q∨r)∧(r∨p),
we can use basic laws of logic and propositional calculus.
Step 1: Show (p∧q)∨(q∧r)∨(r∧p)⇒(p∨q)∧(q∨r)∧(r∨p):
Starting with (p∧q)∨(q∧r)∨(r∧p), we can distribute the ∨over ∧using
the distributive law:
(p∧q)∨(q∧r)∨(r∧p)≡(p∨q)∧(p∨r)∧(q∨r)
Next, we can rearrange the terms in the right-hand side to match the form
of (p∨q)∧(q∨r)∧(r∨p):
(p∧q)∨(q∧r)∨(r∧p)⇒(p∨q)∧(q∨r)∧(r∨p)
Step 2: Show (p∨q)∧(q∨r)∧(r∨p)⇒(p∧q)∨(q∧r)∨(r∧p):
Starting with (p∨q)∧(q∨r)∧(r∨p), we can distribute the ∧over ∨using
the distributive law:
(p∨q)∧(q∨r)∧(r∨p)≡(p∧q)∨(p∧r)∨(q∧r)
Next, we can rearrange the terms in the right-hand side to match the form
of (p∧q)∨(q∧r)∨(r∧p):
(p∨q)∧(q∨r)∧(r∨p)⇒(p∧q)∨(q∧r)∨(r∧p)
Therefore, we have shown that (p∧q)∨(q∧r)∨(r∧p) is logically equivalent
to (p∨q)∧(q∨r)∧(r∨p).
Question 17
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using propositional calculus.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will use a direct
proof technique by assuming the hypothesis is false and reaching a contradiction.
11
Step 1: Write the implication as a conjunction: We start by writing
the given implication as a conjunction of implications:
(p→q)∧(q→r)→(p→r)≡ ¬((p→q)∧(q→r)) ∨(p→r)
Step 2: Apply De Morgan’s Law: Using De Morgan’s Law, we can
rewrite the negated conjunction as a disjunction of negations:
¬((p→q)∧(q→r)) ≡ ¬(p→q)∨ ¬(q→r)
Step 3: Apply the Conditional Connective: We rewrite the negations
of implications using the definition of the conditional connective:
¬(p→q)∨ ¬(q→r)≡ ¬(¬p∨q)∨ ¬(¬q∨r)
Step 4: Apply Double Negation and De Morgan’s Law: We simplify
the negations and use De Morgan’s Law to expand the expression:
¬(¬p∨q)∨ ¬(¬q∨r)≡(p∧ ¬q)∨(q∧ ¬r)
Step 5: Apply Distributive Law: Using the Distributive Law, we can
simplify the expression further:
(p∧ ¬q)∨(q∧ ¬r)≡(p∨q)∧(p∨ ¬r)∧(¬q∨q)∧(¬q∨ ¬r)
Step 6: Eliminate Contradictions: We notice that (¬q∨q) and (¬q∨¬r)
are contradictions, so the conjunction simplifies to:
(p∨ ¬r)∧(p∨q)
Step 7: Apply the Definition of Implication: Finally, we use the
definition of implication to rewrite the simplified conjunction:
(p∨ ¬r)∧(p∨q)≡p→r
Since we ended up with p→r, which is logically equivalent to the original
expression, we have shown that (p→q)∧(q→r)→(p→r) is a tautology.
Question 18
Question
Let p,q, and rbe propositions. Show that (p∧q)→ris logically equivalent to
p→(q→r).
12
Solution
To show that (p∧q)→ris logically equivalent to p→(q→r), we need to
show that the two propositions have the same truth values for all possible truth
values of p,q, and r.
Step 1: Truth Table for (p∧q)→r
p q r (p∧q) (p∧q)→r p →(q→r)
T T T T T T
T T F T F F
T F T F T T
T F F F T T
F T T F T T
F T F F T T
F F T F T T
F F F F T T
Since the truth values of (p∧q)→rand p→(q→r) are the same for all
possible truth values of p,q, and r, we can conclude that (p∧q)→ris logically
equivalent to p→(q→r).
Question 19
Question
Let p,q, and rbe propositions. Prove or disprove the following statement:
(p∧q)∨r≡(p∨r)∧(q∨r)
Solution
To prove or disprove the given statement, we can use truth tables to compare
the truth values of both sides of the equivalence.
Step 1: Create a truth table for (p∧q)∨rand (p∨r)∧(q∨r).
We consider all possible combinations of truth values for p,q, and r:
p q r p ∧q(p∧q)∨r p ∨r q ∨r(p∨r)∧(q∨r)
T T T T T T T T
T T F T T T T T
T F T F T T T T
T F F F F T F F
F T T F T T T T
F T F F F F T F
F F T F T T T T
F F F F F F F F
Step 2: Compare the truth values of both sides.
13
From the truth table, we can see that the truth values of (p∧q)∨rand
(p∨r)∧(q∨r) are not always the same, so the statement is disproved.
Therefore, we have shown that (p∧q)∨r≡ (p∨r)∧(q∨r) for all possible
truth values of p,q, and r.
Question 20
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(q∧r)⇒(p∨r) is a
tautology using propositional calculus.
Solution
To show that the implication (p∧q)∨(q∧r)⇒(p∨r) is a tautology, we will
use a logical equivalency.
Step 1: Apply the distributive law for disjunction over conjunction to obtain
the following:
(p∧q)∨(q∧r)⇒(p∨r)
≡¬[(p∧q)∨(q∧r)] ∨(p∨r) (Implication as disjunction)
≡¬(p∧q)∧ ¬(q∧r)∨(p∨r) (De Morgan’s Law)
≡(¬p∨ ¬q)∧(¬q∨ ¬r)∨(p∨r) (De Morgan’s Law)
Step 2: Apply the distributive law for conjunction over disjunction to obtain
the following:
(¬p∨ ¬q)∧(¬q∨ ¬r)∨(p∨r)
≡[(¬p∨ ¬q)∧(¬q∨ ¬r)] ∨[(¬p∨ ¬q)∧(p∨r)] (Distributive Law)
≡[(¬p∧ ¬q)∨(¬p∧ ¬r)] ∨[(¬q∧ ¬q)∨(p∧r)] (Distributive Law)
≡(¬p∧ ¬q)∨(¬p∧ ¬r)∨(¬q∧ ¬q)∨(p∧r) (Associative Law)
≡¬p∧(¬q∨ ¬r)∨F∨(p∧r) (Negation Law)
≡¬p∧ ¬(q∧r)∨(p∧r) (Negated Disjunction)
Step 3: Apply the distributive law for disjunction over conjunction to obtain
the following:
¬p∧ ¬(q∧r)∨(p∧r)
≡¬p∨(p∧r)∧ ¬(q∧r) (Distributive Law)
≡(¬p∨p)∧(¬p∨r)∧(¬q∨ ¬r) (Distribution)
≡T∧(¬p∨r)∧(¬q∨ ¬r) (Negation Law)
≡(¬p∨r)∧(¬q∨ ¬r) (Identity Law)
≡(¬p∨r)∧ ¬(q∧r) (De Morgan’s Law)
≡¬[(p∧q)∨(q∧r)] ∨(p∨r) (Implication as Disjunction)
≡(p∧q)∨(q∧r)⇒(p∨r) (Implication as Disjunction)
14
Therefore, we have shown that the implication (p∧q)∨(q∧r)⇒(p∨r) is
a tautology.
Question 21
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we can use
logical equivalence laws and truth tables.
Step 1: Write the truth tables for both propositions
The truth table for (p∧q)∨(p∧r) is:
p q r p ∧q p ∧r(p∧q)∨(p∧r)
T T T T T T
T T F T F T
T F T F T T
T F F F F F
F T T F F F
F T F F F F
F F T F F F
F F F F F F
The truth table for p∧(q∨r) is:
p q r q ∨r p ∧(q∨r)
T T T T T
T T F T T
T F T T T
T F F F F
F T T T F
F T F T F
F F T T F
F F F F F
Step 2: Compare the truth values in both truth tables
By comparing the truth values in both truth tables, we observe that the truth
values for (p∧q)∨(p∧r) and p∧(q∨r) are the same for all possible combinations
of truth values of p,q, and r. Hence, we can conclude that (p∧q)∨(p∧r) is
logically equivalent to p∧(q∨r).
15
Question 22
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using propositional calculus.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will use a truth
table to demonstrate that the compound proposition is true for all possible truth
values of p,q, and r.
p q r p →q q →r(p→q)∧(q→r)p→r
T T T T T T T
T T F T F F F
T F T F T F T
T F F F T F F
F T T T T T T
F T F T F F T
F F T T T T T
F F F T T T T
As seen in the truth table, the final column is always true regardless of the
truth values of p,q, and r. Therefore, (p→q)∧(q→r)→(p→r) is a
tautology.
Question 23
Question
Let pand qbe propositions. Prove that (p→q)∨(q→p) is a tautology.
Solution
To prove that (p→q)∨(q→p) is a tautology, we can use a truth table to show
that the statement is true for all possible truth values of pand q.
p q p →q q →p(p→q)∨(q→p)
T T T T T
T F F T T
F T T F T
F F T T T
Since the final column of the truth table is always true, we can conclude that
(p→q)∨(q→p) is a tautology.
16
Question 24
Question
Let p,q, and rbe propositions. Prove or disprove the statement: (p→q)∧(q→
r)→(p→r).
Solution
To prove or disprove the statement (p→q)∧(q→r)→(p→r), we will
construct a truth table to analyze all possible truth values of p,q, and r.
p q r p →q q →r(p→q)∧(q→r)p→r
T T T T T T T
T T F T F F F
T F T F T F T
T F F F T F F
F T T T T T T
F T F T F F T
F F T T T T T
F F F T T T T
From the truth table, we see that there are instances where (p→q)∧(q→r)
is true while p→ris false. Therefore, the statement (p→q)∧(q→r)→(p→
r) is disproved.
Question 25
Question
Let pbe the proposition ”I will pass the exam” and qbe the proposition ”I will
study hard”. Express the statement ”If I pass the exam, then I studied hard”
using pand qusing logical connectives.
Solution
To express the statement ”If I pass the exam, then I studied hard” using pand
q, we can use the logical connective ”implies”, denoted by →. The statement
can be written as p→q.
Therefore, the expression for the statement is: p→q.
Question 26
Question
Let prepresent the statement ”I will go to the beach” and qrepresent the
statement ”I will go swimming.” Write the following compound statement in
17
symbolic form: ”I will go to the beach if and only if I will go swimming.”
Solution
To express the compound statement ”I will go to the beach if and only if I will
go swimming” in symbolic form, we can use the biconditional connective ↔,
which means ”if and only if”.
Let: p= ”I will go to the beach”
q= ”I will go swimming”
The compound statement can be represented as: p↔q
Therefore, the symbolic form of the given compound statement is ”p↔q”.
Question 27
Question
Let p,q, and rbe propositions. Prove the following logical equivalence: (p−→
q)∧(q−→ r)≡(p∧q)−→ r.
Solution
To prove the logical equivalence (p−→ q)∧(q−→ r)≡(p∧q)−→ r, we will
show that both sides are logically equivalent by constructing truth tables for
each side and demonstrating they have the same truth values for all possible
combinations of truth values for p,q, and r.
Step 1: Create a truth table for (p−→ q)∧(q−→ r)
p q r p −→ q q −→ r(p−→ q)∧(q−→ r)
T T T T T T
T T F T F F
T F T F T F
T F F F T F
F T T T T T
F T F T F F
F F T T T T
F F F T T T
Step 2: Create a truth table for (p∧q)−→ r
18
p q r p ∧q(p∧q)−→ r
T T T T T
T T F T F
T F T F T
T F F F T
F T T F T
F T F F T
F F T F T
F F F F T
Step 3: Conclusion
Comparing the truth tables for (p−→ q)∧(q−→ r) and (p∧q)−→ r, we
can see that the two statements are logically equivalent as their truth values
match for all possible combinations of truth values for p,q, and r. Therefore,
we have proved the logical equivalence (p−→ q)∧(q−→ r)≡(p∧q)−→ r.
Question 28
Question
Let p,q, and rbe propositions. Show that (p⇒q)∧(q⇒r)⇒(p⇒r) is a
tautology using a truth table.
Solution
To show that (p⇒q)∧(q⇒r)⇒(p⇒r) is a tautology, we will construct a
truth table for the proposition.
Step 1: Construct the truth table for (p⇒q)∧(q⇒r)⇒(p⇒r).
p q r p ⇒q q ⇒r(p⇒q)∧(q⇒r)p⇒r(p⇒q)∧(q⇒r)⇒(p⇒r)
T T T T T T T T
T T F T F F F T
T F T F T F T T
T F F F T F F T
F T T T T T T T
F T F T F F T T
F F T T T T T T
F F F T T T T T
Since the final column has all ”T” values, we have shown that (p⇒q)∧(q⇒
r)⇒(p⇒r) is a tautology.
19
Question 29
Question
Let p,q, and rbe propositions where:
p: ”It is raining.”
q: ”The streets are wet.”
r: ”There are traffic jams.”
Translate the following statement into propositional logic: ”If it is raining
and the streets are wet, then there are traffic jams.”
Solution
To express the given statement in propositional logic, we need to define the
logical operators and their corresponding meanings:
∧: ”and”
→: ”if...then”
Let’s define p,q, and rin terms of the given propositions:
p: ”It is raining.”
q: ”The streets are wet.”
r: ”There are traffic jams.”
Now, we can translate the statement into propositional logic form:
(p∧q)→r
Question 30
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using logical equivalences.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we need to show that
the statement is always true regardless of the truth values of p,q, and r. We
will use logical equivalences to simplify the expression.
Identity Laws
Therefore, (p→q)∧(q→r)→(p→r) is a tautology.
20
Question 31
Question
Let pand qbe propositions. Prove or disprove the following statement: (p→
q)∧(¬p→ ¬q)→(p↔q).
Solution
To prove or disprove the statement (p→q)∧(¬p→ ¬q)→(p↔q), we can
construct a truth table to analyze all possible truth values of pand q.
p q p →q¬p¬q¬p→ ¬q p ↔q(p→q)∧(¬p→ ¬q)→(p↔q)
T T T F F T T T
T F F F T T F T
F T T T F F F T
F F T T T T T F
The truth table shows that the statement is false when pis false and qis
false. Therefore, the statement (p→q)∧(¬p→ ¬q)→(p↔q) is disproved.
Question 32
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we must show
that the truth values of both expressions are the same for all possible truth
values of p,q, and r. We can do this by constructing truth tables for both
expressions.
Step 1: Construct a truth table for (p∧q)∨(p∧r)
p q r p ∧q p ∧r(p∧q)∨(p∧r)
T T T T T T
T T F T F T
T F T F T T
T F F F F F
F T T F F F
F T F F F F
F F T F F F
F F F F F F
21
Step 2: Construct a truth table for p∧(q∨r)
p q r q ∨r p ∧(q∨r)
T T T T T
T T F T T
T F T T T
T F F F F
F T T T F
F T F T F
F F T T F
F F F F F
Step 3: Conclusion From the truth tables, we can see that both (p∧q)∨
(p∧r) and p∧(q∨r) have the same truth values for all possible truth values of
p,q, and r. Therefore, we have shown that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Question 33
Question
Let p,q, and rbe propositions. Show that (p∧q)→ris logically equivalent to
(p→r)∨(q→r).
Solution
To show that (p∧q)→ris logically equivalent to (p→r)∨(q→r), we will
construct truth tables for both propositions and show that they have the same
truth values.
p q r (p∧q) (p∧q)→r(p→r) (q→r)
T T T T T T T
T T F T F F F
T F T F T T T
T F F F T F T
F T T F T T T
F T F F T T F
F F T F T T T
F F F F T T T
From the truth table above, we can see that (p∧q)→rhas the same
truth values as (p→r)∨(q→r) for all combinations of truth values for p,
q, and r. Therefore, we have shown that (p∧q)→ris logically equivalent to
(p→r)∨(q→r).
22
Question 34
Question
Let p,q, and rbe propositions. Show that the proposition (p→q)∧(q→r)→
(p→r) is a tautology.
Solution
Step 1: To show that (p→q)∧(q→r)→(p→r) is a tautology, we can
construct a truth table to check all possible truth values of p,q, and r.
p q r p →q q →r(p→q)∧(q→r)p→r(p→q)∧(q→r)→(p→r)
T T T T T T T T
T T F T F F F T
T F T F T F T T
T F F F T F F T
F T T T T T T T
F T F T F F T T
F F T T T T T T
F F F T T T T T
Step 2: From the truth table, we can see that the last column, which repre-
sents (p→q)∧(q→r)→(p→r), is always true. Therefore, the proposition
(p→q)∧(q→r)→(p→r) is a tautology.
Question 35
Question
Let p,q, and rbe propositions. Prove the following statement using laws of
logic and propositional calculus:
(p→q)∧(q→r)→(p→r)
Solution
To prove the statement (p→q)∧(q→r)→(p→r), we will use the rules of
logic and propositional calculus.
23
Question 2
Question
Let pand qbe propositions. Prove that (p→q)∧(q→p) is logically equivalent
to (p∧q)∨(¬p∧ ¬q).
Solution
To prove the logical equivalence of the given expressions, we will show that they
have the same Truth Table.
Step 1: Construct the Truth Table for (p→q)∧(q→p).
p q p →q q →p(p→q)∧(q→p)
T T T T T
T F F T F
F T T F F
F F T T T
Step 2: Construct the Truth Table for (p∧q)∨(¬p∧ ¬q).
p q p ∧q¬p¬q(¬p∧ ¬q)
(p∧q)∨(¬p∧ ¬q)
T T T F F F
T
T F F F T F
F
F T F T F F
F
F F F T T T
T
Step 3: Conclusion
From the truth tables, we can see that both (p→q)∧(q→p) and (p∧
q)∨(¬p∧ ¬q) have the same truth values for all possible combinations of truth
values of pand q. Therefore, we have proved that they are logically equivalent.
Question 3
Question
Let p,q, and rbe propositions. Show whether the following argument is valid
or not using propositional logic:
If pthen q.
If qthen r.
Therefore, if pthen r.
2
Solution
To determine the validity of the argument, we will use the method of direct
proof in propositional logic.
Step 1: Assume p→qis true and q→ris true.
Given: p→qand q→r.
To prove: p→r.
Step 2: Based on the given information, we can write the implications in
terms of logic operators: - p→qis equivalent to ¬p∨q. - q→ris equivalent
to ¬q∨r.
Step 3: Construct the truth table for ¬p∨qand ¬q∨r:
p q r ¬p∨q¬q∨r(¬p∨q)∧(¬q∨r)
T T T T T T
T T F T F F
T F T F T F
T F F F T F
F T T T T T
F T F T F F
F F T T T T
F F F T T T
Since the last column is not always true, the argument is invalid.
Therefore, the argument ”If pthen q, if qthen r, therefore if pthen r” is
not valid in general.
Question 4
Question
Let pand qbe propositions. Show that the statement (p⇒q)⇒pis a tautology
using truth tables.
Solution
To show that (p⇒q)⇒pis a tautology, we need to show that the statement
is true for all possible truth values of pand q.
Step 1: Create a truth table for (p⇒q)⇒p:
p q (p⇒q) (p⇒q)⇒p
T T T T
T F F T
F T T F
F F T T
Step 2: Verify that (p⇒q)⇒pis true for all rows: From the truth
table, we can see that (p⇒q)⇒pis true for all possible truth values of pand
q, making it a tautology.
3
Question 5
Question
Let p, q be propositions. Show that the statement (p→q)∧(q→p) is logically
equivalent to p↔q.
Solution
To show that (p→q)∧(q→p) is logically equivalent to p↔q, we need to
show that they have the same truth values for all possible truth values of pand
q. We can do this by constructing truth tables for both propositions.
Step 1: Construct a truth table for (p→q)∧(q→p)
p q p →q q →p(p→q)∧(q→p)
T T T T T
T F F T F
F T T F F
F F T T T
Step 2: Construct a truth table for p↔q
The logical biconditional p↔qis true if pand qhave the same truth value,
otherwise it is false.
p q p ↔q
T T T
T F F
F T F
F F T
Step 3: Conclusion
Comparing the truth tables for (p→q)∧(q→p) and p↔q, we can see
that they have the same truth values for all possible truth values of pand q.
Therefore, (p→q)∧(q→p) is logically equivalent to p↔q.
Question 6
Question
Let p,q, and rbe propositional variables. Show that the statement (p∧q)→r
is logically equivalent to ¬p∨ ¬q∨r.
Solution
To show that the statements (p∧q)→rand ¬p∨ ¬q∨rare logically equivalent,
we will use logical equivalences to transform one statement into the other.
Step 1: Start with the statement (p∧q)→r.
(p∧q)→r
4
Step 2: Use the definition of the conditional p→q≡ ¬p∨q.
¬(p∧q)∨r
Step 3: Use De Morgan’s Law: ¬(p∧q)≡ ¬p∨ ¬q.
(¬p∨ ¬q)∨r
Step 4: Associative property: a∨(b∨c)≡(a∨b)∨c.
¬p∨(¬q∨r)
Step 5: Associative property again.
¬p∨ ¬q∨r
Therefore, we have shown that (p∧q)→ris logically equivalent to ¬p∨¬q∨r.
Question 7
Question
Let p,q, and rbe propositions. Determine whether the statement (p∧q)→r
is logically equivalent to ¬p∨(¬q∨r).
Solution
To determine if the two statements are logically equivalent, we can use a truth
table to analyze all possible truth values of p,q, and r.
p q r p ∧q(p∧q)→r¬p¬q∨r¬p∨(¬q∨r)
T T T T T F T T
T T F T F F F F
T F T F T F T T
T F F F T F T T
F T T F T T T T
F T F F T T T T
F F T F T T T T
F F F F T T T T
Since the truth values of (p∧q)→rand ¬p∨(¬q∨r) are the same for all
possible truth values of p,q, and r, we can conclude that the two statements
are logically equivalent.
Question 8
Question
Let pand qbe propositions. Show that the following proposition is a tautology:
(p→q)∨(q→p)
5
Solution
To show that the given proposition is a tautology, we can either use a truth
table to check all possible truth values, or we can use logical equivalences to
simplify the expression and show that it simplifies to true for all possible truth
values of pand q.
Using logical equivalences, let’s simplify the given proposition:
(Negation)
Therefore, (p→q)∨(q→p) simplifies to true, which means it is a tautology.
Question 9
Question
Let p,q, and rbe propositions. Prove or disprove the following logical equiva-
lence: (p∧q)→r≡p→(q→r).
Solution
To prove or disprove the logical equivalence (p∧q)→r≡p→(q→r), we will
construct truth tables for both expressions and compare them.
Step 1: Construct the truth table for (p∧q)→r
p q r (p∧q) (p∧q)→r
T T T T T
T T F T F
T F T F T
T F F F T
F T T F T
F T F F T
F F T F T
F F F F T
6
Step 2: Construct the truth table for p→(q→r)
p q r (q→r)p→(q→r)
T T T T T
T T F T T
T F T T T
T F F T T
F T T T T
F T F F T
F F T T T
F F F T T
Step 3: Compare the truth tables By comparing the truth tables for
(p∧q)→rand p→(q→r), we see that they are not equivalent. In the second
row, (p∧q)→rhas a truth value of Fwhile p→(q→r) has a truth value of
T, indicating a mismatch.
Therefore, we have disproved the logical equivalence (p∧q)→r≡p→(q→
r).
Question 10
Question
Let p,q, and rbe propositions. Prove or disprove the following statement:
(p→q)∧(q→r)→(p→r).
Solution
To prove or disprove the statement, we will use the truth table method.
Step 1: Create a Truth Table We will create a truth table with columns
for p,q,r, (p→q), (q→r), and (p→r). There are 8 possible truth value
combinations for p,q, and r.
p q r p →q q →r p →r
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F
Step 2: Fill in Compound Propositional Statements We will fill in
the columns for (p→q), (q→r), and (p→r) based on the truth values of p,
q, and r.
7
p q r p →q q →r p →r
T T T T T T
T T F T F F
T F T F T T
T F F F T F
F T T T T T
F T F T F T
F F T T T T
F F F T T T
Step 3: Analyze the Last Column Looking at the truth values of p→r
in the last column of the truth table, we can see that it doesn’t always match the
value of (p→q)∧(q→r). Therefore, the statement (p→q)∧(q→r)→(p→r)
is disproved.
Question 11
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using a truth table.
Solution
To show that the given compound proposition is a tautology, we will construct
a truth table to examine all possible truth values of p,q, and r.
p q r p →q q →r(p→q)∧(q→r) (p→r)
T T T T T T T
T T F T F F F
T F T F T F T
T F F F T F F
F T T T T T T
F T F T F F T
F F T T T T T
F F F T T T T
Since the final column of the truth table is always true, the compound propo-
sition (p→q)∧(q→r)→(p→r) is a tautology.
Question 12
Question
Let prepresent the statement ”It is sunny,” qrepresent the statement ”It is
raining,” and rrepresent the statement ”It is Monday.” Translate the following
8
statement into a logical expression:
”If it is not Monday, then either it is sunny or it is raining.”
Solution
To translate the given statement into a logical expression, we need to consider
the logical operators involved and their corresponding symbols in propositional
calculus.
Let’s break down the given statement: - ”It is not Monday” can be repre-
sented as ¬r. - ”Either it is sunny or it is raining” can be represented as (p∨q)
(translated using the inclusive or operator).
Therefore, the translation of the given statement into a logical expression is
¬r→(p∨q).
So, ”If it is not Monday, then either it is sunny or it is raining” can be
represented as ¬r→(p∨q).
Question 13
Question
Let pand qbe propositions. Show that the proposition (p→q)→(¬p∨q) is
a tautology using truth tables.
Solution
To show that (p→q)→(¬p∨q) is a tautology, we need to show that the
proposition is true for all possible truth values of pand q.
p q p →q¬p¬p∨q(p→q)→(¬p∨q)
T T T F T T
T F F F F T
F T T T T T
F F T T T T
As shown in the truth table, the final column evaluates to true for all possible
truth values of pand q. Therefore, (p→q)→(¬p∨q) is a tautology.
Question 14
Question
Let p,q, and rbe propositions. Determine whether the following statement is
a tautology, contradiction, or contingent:
(p∧q)→ ¬p∨(p∧r)
9
Solution
To determine whether the given statement is a tautology, contradiction, or con-
tingent, we will construct a truth table for all possible truth values of p,q, and
rand evaluate the truth value of the given statement for each combination of
truth values.
p q r (p∧q)¬p∨(p∧r) (p∧q)→ ¬p∨(p∧r)
T T T T T T
T T F T T T
T F T F F T
T F F F F T
F T T F T T
F T F F T T
F F T F T T
F F F F T T
From the truth table, we can see that the given statement evaluates to
true for all possible truth values of p,q, and r. Therefore, the statement is a
tautology.
Question 15
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will use a truth
table to analyze all possible truth values of p,q, and r.
p q r p →q q →r(p→q)∧(q→r)p→r(p→q)∧(q→r)→(p→r)
T T T T T T T T
T T F T F F F T
T F T F T F T T
T F F F T F F T
F T T T T T T T
F T F T F F T T
F F T T T T T T
F F F T T T T T
Since the final column of the truth table is always true, we conclude that
(p→q)∧(q→r)→(p→r) is a tautology.
10
Question 16
Question
Let p,q, and rbe propositions. Show that the proposition (p∧q)∨(q∧r)∨(r∧p)
is logically equivalent to (p∨q)∧(q∨r)∧(r∨p).
Solution
To show that (p∧q)∨(q∧r)∨(r∧p) is logically equivalent to (p∨q)∧(q∨r)∧(r∨p),
we can use basic laws of logic and propositional calculus.
Step 1: Show (p∧q)∨(q∧r)∨(r∧p)⇒(p∨q)∧(q∨r)∧(r∨p):
Starting with (p∧q)∨(q∧r)∨(r∧p), we can distribute the ∨over ∧using
the distributive law:
(p∧q)∨(q∧r)∨(r∧p)≡(p∨q)∧(p∨r)∧(q∨r)
Next, we can rearrange the terms in the right-hand side to match the form
of (p∨q)∧(q∨r)∧(r∨p):
(p∧q)∨(q∧r)∨(r∧p)⇒(p∨q)∧(q∨r)∧(r∨p)
Step 2: Show (p∨q)∧(q∨r)∧(r∨p)⇒(p∧q)∨(q∧r)∨(r∧p):
Starting with (p∨q)∧(q∨r)∧(r∨p), we can distribute the ∧over ∨using
the distributive law:
(p∨q)∧(q∨r)∧(r∨p)≡(p∧q)∨(p∧r)∨(q∧r)
Next, we can rearrange the terms in the right-hand side to match the form
of (p∧q)∨(q∧r)∨(r∧p):
(p∨q)∧(q∨r)∧(r∨p)⇒(p∧q)∨(q∧r)∨(r∧p)
Therefore, we have shown that (p∧q)∨(q∧r)∨(r∧p) is logically equivalent
to (p∨q)∧(q∨r)∧(r∨p).
Question 17
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using propositional calculus.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will use a direct
proof technique by assuming the hypothesis is false and reaching a contradiction.
11
Step 1: Write the implication as a conjunction: We start by writing
the given implication as a conjunction of implications:
(p→q)∧(q→r)→(p→r)≡ ¬((p→q)∧(q→r)) ∨(p→r)
Step 2: Apply De Morgan’s Law: Using De Morgan’s Law, we can
rewrite the negated conjunction as a disjunction of negations:
¬((p→q)∧(q→r)) ≡ ¬(p→q)∨ ¬(q→r)
Step 3: Apply the Conditional Connective: We rewrite the negations
of implications using the definition of the conditional connective:
¬(p→q)∨ ¬(q→r)≡ ¬(¬p∨q)∨ ¬(¬q∨r)
Step 4: Apply Double Negation and De Morgan’s Law: We simplify
the negations and use De Morgan’s Law to expand the expression:
¬(¬p∨q)∨ ¬(¬q∨r)≡(p∧ ¬q)∨(q∧ ¬r)
Step 5: Apply Distributive Law: Using the Distributive Law, we can
simplify the expression further:
(p∧ ¬q)∨(q∧ ¬r)≡(p∨q)∧(p∨ ¬r)∧(¬q∨q)∧(¬q∨ ¬r)
Step 6: Eliminate Contradictions: We notice that (¬q∨q) and (¬q∨¬r)
are contradictions, so the conjunction simplifies to:
(p∨ ¬r)∧(p∨q)
Step 7: Apply the Definition of Implication: Finally, we use the
definition of implication to rewrite the simplified conjunction:
(p∨ ¬r)∧(p∨q)≡p→r
Since we ended up with p→r, which is logically equivalent to the original
expression, we have shown that (p→q)∧(q→r)→(p→r) is a tautology.
Question 18
Question
Let p,q, and rbe propositions. Show that (p∧q)→ris logically equivalent to
p→(q→r).
12
Solution
To show that (p∧q)→ris logically equivalent to p→(q→r), we need to
show that the two propositions have the same truth values for all possible truth
values of p,q, and r.
Step 1: Truth Table for (p∧q)→r
p q r (p∧q) (p∧q)→r p →(q→r)
T T T T T T
T T F T F F
T F T F T T
T F F F T T
F T T F T T
F T F F T T
F F T F T T
F F F F T T
Since the truth values of (p∧q)→rand p→(q→r) are the same for all
possible truth values of p,q, and r, we can conclude that (p∧q)→ris logically
equivalent to p→(q→r).
Question 19
Question
Let p,q, and rbe propositions. Prove or disprove the following statement:
(p∧q)∨r≡(p∨r)∧(q∨r)
Solution
To prove or disprove the given statement, we can use truth tables to compare
the truth values of both sides of the equivalence.
Step 1: Create a truth table for (p∧q)∨rand (p∨r)∧(q∨r).
We consider all possible combinations of truth values for p,q, and r:
p q r p ∧q(p∧q)∨r p ∨r q ∨r(p∨r)∧(q∨r)
T T T T T T T T
T T F T T T T T
T F T F T T T T
T F F F F T F F
F T T F T T T T
F T F F F F T F
F F T F T T T T
F F F F F F F F
Step 2: Compare the truth values of both sides.
13
From the truth table, we can see that the truth values of (p∧q)∨rand
(p∨r)∧(q∨r) are not always the same, so the statement is disproved.
Therefore, we have shown that (p∧q)∨r≡ (p∨r)∧(q∨r) for all possible
truth values of p,q, and r.
Question 20
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(q∧r)⇒(p∨r) is a
tautology using propositional calculus.
Solution
To show that the implication (p∧q)∨(q∧r)⇒(p∨r) is a tautology, we will
use a logical equivalency.
Step 1: Apply the distributive law for disjunction over conjunction to obtain
the following:
(p∧q)∨(q∧r)⇒(p∨r)
≡¬[(p∧q)∨(q∧r)] ∨(p∨r) (Implication as disjunction)
≡¬(p∧q)∧ ¬(q∧r)∨(p∨r) (De Morgan’s Law)
≡(¬p∨ ¬q)∧(¬q∨ ¬r)∨(p∨r) (De Morgan’s Law)
Step 2: Apply the distributive law for conjunction over disjunction to obtain
the following:
(¬p∨ ¬q)∧(¬q∨ ¬r)∨(p∨r)
≡[(¬p∨ ¬q)∧(¬q∨ ¬r)] ∨[(¬p∨ ¬q)∧(p∨r)] (Distributive Law)
≡[(¬p∧ ¬q)∨(¬p∧ ¬r)] ∨[(¬q∧ ¬q)∨(p∧r)] (Distributive Law)
≡(¬p∧ ¬q)∨(¬p∧ ¬r)∨(¬q∧ ¬q)∨(p∧r) (Associative Law)
≡¬p∧(¬q∨ ¬r)∨F∨(p∧r) (Negation Law)
≡¬p∧ ¬(q∧r)∨(p∧r) (Negated Disjunction)
Step 3: Apply the distributive law for disjunction over conjunction to obtain
the following:
¬p∧ ¬(q∧r)∨(p∧r)
≡¬p∨(p∧r)∧ ¬(q∧r) (Distributive Law)
≡(¬p∨p)∧(¬p∨r)∧(¬q∨ ¬r) (Distribution)
≡T∧(¬p∨r)∧(¬q∨ ¬r) (Negation Law)
≡(¬p∨r)∧(¬q∨ ¬r) (Identity Law)
≡(¬p∨r)∧ ¬(q∧r) (De Morgan’s Law)
≡¬[(p∧q)∨(q∧r)] ∨(p∨r) (Implication as Disjunction)
≡(p∧q)∨(q∧r)⇒(p∨r) (Implication as Disjunction)
14
Therefore, we have shown that the implication (p∧q)∨(q∧r)⇒(p∨r) is
a tautology.
Question 21
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we can use
logical equivalence laws and truth tables.
Step 1: Write the truth tables for both propositions
The truth table for (p∧q)∨(p∧r) is:
p q r p ∧q p ∧r(p∧q)∨(p∧r)
T T T T T T
T T F T F T
T F T F T T
T F F F F F
F T T F F F
F T F F F F
F F T F F F
F F F F F F
The truth table for p∧(q∨r) is:
p q r q ∨r p ∧(q∨r)
T T T T T
T T F T T
T F T T T
T F F F F
F T T T F
F T F T F
F F T T F
F F F F F
Step 2: Compare the truth values in both truth tables
By comparing the truth values in both truth tables, we observe that the truth
values for (p∧q)∨(p∧r) and p∧(q∨r) are the same for all possible combinations
of truth values of p,q, and r. Hence, we can conclude that (p∧q)∨(p∧r) is
logically equivalent to p∧(q∨r).
15
Question 22
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using propositional calculus.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will use a truth
table to demonstrate that the compound proposition is true for all possible truth
values of p,q, and r.
p q r p →q q →r(p→q)∧(q→r)p→r
T T T T T T T
T T F T F F F
T F T F T F T
T F F F T F F
F T T T T T T
F T F T F F T
F F T T T T T
F F F T T T T
As seen in the truth table, the final column is always true regardless of the
truth values of p,q, and r. Therefore, (p→q)∧(q→r)→(p→r) is a
tautology.
Question 23
Question
Let pand qbe propositions. Prove that (p→q)∨(q→p) is a tautology.
Solution
To prove that (p→q)∨(q→p) is a tautology, we can use a truth table to show
that the statement is true for all possible truth values of pand q.
p q p →q q →p(p→q)∨(q→p)
T T T T T
T F F T T
F T T F T
F F T T T
Since the final column of the truth table is always true, we can conclude that
(p→q)∨(q→p) is a tautology.
16
Question 24
Question
Let p,q, and rbe propositions. Prove or disprove the statement: (p→q)∧(q→
r)→(p→r).
Solution
To prove or disprove the statement (p→q)∧(q→r)→(p→r), we will
construct a truth table to analyze all possible truth values of p,q, and r.
p q r p →q q →r(p→q)∧(q→r)p→r
T T T T T T T
T T F T F F F
T F T F T F T
T F F F T F F
F T T T T T T
F T F T F F T
F F T T T T T
F F F T T T T
From the truth table, we see that there are instances where (p→q)∧(q→r)
is true while p→ris false. Therefore, the statement (p→q)∧(q→r)→(p→
r) is disproved.
Question 25
Question
Let pbe the proposition ”I will pass the exam” and qbe the proposition ”I will
study hard”. Express the statement ”If I pass the exam, then I studied hard”
using pand qusing logical connectives.
Solution
To express the statement ”If I pass the exam, then I studied hard” using pand
q, we can use the logical connective ”implies”, denoted by →. The statement
can be written as p→q.
Therefore, the expression for the statement is: p→q.
Question 26
Question
Let prepresent the statement ”I will go to the beach” and qrepresent the
statement ”I will go swimming.” Write the following compound statement in
17
symbolic form: ”I will go to the beach if and only if I will go swimming.”
Solution
To express the compound statement ”I will go to the beach if and only if I will
go swimming” in symbolic form, we can use the biconditional connective ↔,
which means ”if and only if”.
Let: p= ”I will go to the beach”
q= ”I will go swimming”
The compound statement can be represented as: p↔q
Therefore, the symbolic form of the given compound statement is ”p↔q”.
Question 27
Question
Let p,q, and rbe propositions. Prove the following logical equivalence: (p−→
q)∧(q−→ r)≡(p∧q)−→ r.
Solution
To prove the logical equivalence (p−→ q)∧(q−→ r)≡(p∧q)−→ r, we will
show that both sides are logically equivalent by constructing truth tables for
each side and demonstrating they have the same truth values for all possible
combinations of truth values for p,q, and r.
Step 1: Create a truth table for (p−→ q)∧(q−→ r)
p q r p −→ q q −→ r(p−→ q)∧(q−→ r)
T T T T T T
T T F T F F
T F T F T F
T F F F T F
F T T T T T
F T F T F F
F F T T T T
F F F T T T
Step 2: Create a truth table for (p∧q)−→ r
18
p q r p ∧q(p∧q)−→ r
T T T T T
T T F T F
T F T F T
T F F F T
F T T F T
F T F F T
F F T F T
F F F F T
Step 3: Conclusion
Comparing the truth tables for (p−→ q)∧(q−→ r) and (p∧q)−→ r, we
can see that the two statements are logically equivalent as their truth values
match for all possible combinations of truth values for p,q, and r. Therefore,
we have proved the logical equivalence (p−→ q)∧(q−→ r)≡(p∧q)−→ r.
Question 28
Question
Let p,q, and rbe propositions. Show that (p⇒q)∧(q⇒r)⇒(p⇒r) is a
tautology using a truth table.
Solution
To show that (p⇒q)∧(q⇒r)⇒(p⇒r) is a tautology, we will construct a
truth table for the proposition.
Step 1: Construct the truth table for (p⇒q)∧(q⇒r)⇒(p⇒r).
p q r p ⇒q q ⇒r(p⇒q)∧(q⇒r)p⇒r(p⇒q)∧(q⇒r)⇒(p⇒r)
T T T T T T T T
T T F T F F F T
T F T F T F T T
T F F F T F F T
F T T T T T T T
F T F T F F T T
F F T T T T T T
F F F T T T T T
Since the final column has all ”T” values, we have shown that (p⇒q)∧(q⇒
r)⇒(p⇒r) is a tautology.
19
Question 29
Question
Let p,q, and rbe propositions where:
p: ”It is raining.”
q: ”The streets are wet.”
r: ”There are traffic jams.”
Translate the following statement into propositional logic: ”If it is raining
and the streets are wet, then there are traffic jams.”
Solution
To express the given statement in propositional logic, we need to define the
logical operators and their corresponding meanings:
∧: ”and”
→: ”if...then”
Let’s define p,q, and rin terms of the given propositions:
p: ”It is raining.”
q: ”The streets are wet.”
r: ”There are traffic jams.”
Now, we can translate the statement into propositional logic form:
(p∧q)→r
Question 30
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using logical equivalences.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we need to show that
the statement is always true regardless of the truth values of p,q, and r. We
will use logical equivalences to simplify the expression.
Identity Laws
Therefore, (p→q)∧(q→r)→(p→r) is a tautology.
20
Question 31
Question
Let pand qbe propositions. Prove or disprove the following statement: (p→
q)∧(¬p→ ¬q)→(p↔q).
Solution
To prove or disprove the statement (p→q)∧(¬p→ ¬q)→(p↔q), we can
construct a truth table to analyze all possible truth values of pand q.
p q p →q¬p¬q¬p→ ¬q p ↔q(p→q)∧(¬p→ ¬q)→(p↔q)
T T T F F T T T
T F F F T T F T
F T T T F F F T
F F T T T T T F
The truth table shows that the statement is false when pis false and qis
false. Therefore, the statement (p→q)∧(¬p→ ¬q)→(p↔q) is disproved.
Question 32
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we must show
that the truth values of both expressions are the same for all possible truth
values of p,q, and r. We can do this by constructing truth tables for both
expressions.
Step 1: Construct a truth table for (p∧q)∨(p∧r)
p q r p ∧q p ∧r(p∧q)∨(p∧r)
T T T T T T
T T F T F T
T F T F T T
T F F F F F
F T T F F F
F T F F F F
F F T F F F
F F F F F F
21
Step 2: Construct a truth table for p∧(q∨r)
p q r q ∨r p ∧(q∨r)
T T T T T
T T F T T
T F T T T
T F F F F
F T T T F
F T F T F
F F T T F
F F F F F
Step 3: Conclusion From the truth tables, we can see that both (p∧q)∨
(p∧r) and p∧(q∨r) have the same truth values for all possible truth values of
p,q, and r. Therefore, we have shown that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Question 33
Question
Let p,q, and rbe propositions. Show that (p∧q)→ris logically equivalent to
(p→r)∨(q→r).
Solution
To show that (p∧q)→ris logically equivalent to (p→r)∨(q→r), we will
construct truth tables for both propositions and show that they have the same
truth values.
p q r (p∧q) (p∧q)→r(p→r) (q→r)
T T T T T T T
T T F T F F F
T F T F T T T
T F F F T F T
F T T F T T T
F T F F T T F
F F T F T T T
F F F F T T T
From the truth table above, we can see that (p∧q)→rhas the same
truth values as (p→r)∨(q→r) for all combinations of truth values for p,
q, and r. Therefore, we have shown that (p∧q)→ris logically equivalent to
(p→r)∨(q→r).
22
Question 34
Question
Let p,q, and rbe propositions. Show that the proposition (p→q)∧(q→r)→
(p→r) is a tautology.
Solution
Step 1: To show that (p→q)∧(q→r)→(p→r) is a tautology, we can
construct a truth table to check all possible truth values of p,q, and r.
p q r p →q q →r(p→q)∧(q→r)p→r(p→q)∧(q→r)→(p→r)
T T T T T T T T
T T F T F F F T
T F T F T F T T
T F F F T F F T
F T T T T T T T
F T F T F F T T
F F T T T T T T
F F F T T T T T
Step 2: From the truth table, we can see that the last column, which repre-
sents (p→q)∧(q→r)→(p→r), is always true. Therefore, the proposition
(p→q)∧(q→r)→(p→r) is a tautology.
Question 35
Question
Let p,q, and rbe propositions. Prove the following statement using laws of
logic and propositional calculus:
(p→q)∧(q→r)→(p→r)
Solution
To prove the statement (p→q)∧(q→r)→(p→r), we will use the rules of
logic and propositional calculus.
23
Step 1: Write the truth table for the given statement.
p q r (p→q) (q→r) (p→r) (p→q)∧(q→r)→(p→r)
T T T T T T T
T T F T F F T
T F T F T T T
T F F F T F T
F T T T T T T
F T F T F T T
F F T T T T T
F F F T T T T
Step 2: Analyze the truth table to verify the statement. The statement
(p→q)∧(q→r)→(p→r) is true for all combinations of truth values of p,q,
and r. Hence, the statement is a tautology, and the proof is complete.
24
