MATH 250 - INTRODUCTION TO
DISCRETE MATHEMATICS - Logic
and Propositional Calculus
Question Bank - Set 3
Liberty University
Question 1
Question
Let pand qbe propositions. Show that (p→q)∨(q→p) is a tautology.
Solution
To show that (p→q)∨(q→p) is a tautology, we construct a truth table and
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 evaluates to Tfor all possible truth values of pand
q, (p→q)∨(q→p) is a tautology.
Question 2
Question
Let p,q, and rbe propositional variables. Show whether the following argument
is valid or invalid using propositional calculus:
”If it is not raining, then the picnic will be canceled. If the picnic is canceled,
then we will have a movie night. Therefore, if it is not raining, then we will
have a movie night.”
Solution
To determine the validity of the argument, we will use propositional logic to
symbolize the statements and then apply the rules of inference.
Let: - p: It is raining. - q: The picnic will be canceled. - r: We will have a
movie night.
The argument can be represented as: - (¬p→q) - (q→r) - ∴(¬p→r)
We will now prove whether the conclusion logically follows from the premises.
Step 1: Apply Modus Ponens to (¬p→q) and (q→r).
By Modus Ponens, if we have statements of the form (a→b) and (b→c),
we can infer (a→c).
Step 2: Apply Modus Ponens.
Given: - (¬p→q) - (q→r)
Since the form of these statements allows for the use of Modus Ponens, we
can conclude: - ∴(¬p→r)
Since the conclusion follows logically from the premises, the argument is
valid.
Question 3
Question
Let p, q, and r be propositions. Show whether the statement (p∧q)∨(p∧r)
is logically equivalent to p∧(q∨r) using the laws of logic and propositional
calculus.
Solution
To determine whether (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we
can use the laws of logic to simplify both statements and then compare them.
Step 1: Apply the distributive law: Apply the distributive law to
(p∧q)∨(p∧r):
(p∧q)∨(p∧r) = p∧(q∨r)
Step 2: Justify the logical equivalence: Since we have shown that
(p∧q)∨(p∧r) simplifies to p∧(q∨r), we can conclude that the two statements
are logically equivalent.
Question 4
Question
Let prepresent the statement ”Karen will go to the concert” and qrepresent the
statement ”Jim will go to the movie.” Write the following statement in symbolic
form: ”Karen will go to the concert and Jim will not go to the movie.”
2
Solution
To represent the statement ”Karen will go to the concert and Jim will not go
to the movie” symbolically, we need to use logical connectives. The logical
connective for ”and” is represented by ∧and the negation of a statement is
represented by ¬.
Therefore, the symbolic form of the given statement is:
p∧ ¬q
Question 5
Question
Let pand qbe propositions. Show that (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 the truth values of the two compound propositions are the same for
all possible truth values of pand q.
Step 1: Construct truth tables for (p→q)∧(q→p) and (p↔q).
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
The truth table for (p↔q) is:
p q p ↔q
T T T
T F F
F T F
F F T
Step 2: Compare the truth values of the two compound propositions in the
truth tables.
By comparing the truth tables, we see that the truth values of (p→q)∧(q→
p) and (p↔q) are the same for all possible truth values of pand q. Therefore,
we can conclude that (p→q)∧(q→p) is logically equivalent to (p↔q).
3
Question 6
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 logical
equivalence rules and logical inference rules.
Step 1: Apply the definition of implication Recall that a→bis
equivalent to ¬a∨b.
So, the given expression becomes: (¬p∨q)∧(¬q∨r)→(¬p∨r).
Step 2: Use the definition of implication in the disjunction By the
distribution property of ∧over ∨, we have: (¬p∧¬q)∨(¬p∧r)∨(q∧¬q)∨(q∧r)→
(¬p∨r).
Step 3: Simplify the expression using tautologies -¬p∧ ¬qsimplifies
to ¬(p∨q), which is always false. - q∧ ¬qis always false. - (¬p∧r)∨(q∧r)
simplifies to (¬p∨q)∧r.
So, (¬p∨r)→(¬p∨r).
Step 4: Use the principle of explosion Since p∨ ¬pis always true, the
expression simplifies to ⊤→⊤, which is a tautology.
Therefore, (p→q)∧(q→r)→(p→r) is a tautology.
Question 7
Question
Let p,q, and rbe propositional variables representing the statements ”It is
raining”, ”The streets are wet”, and ”The grass is wet”, respectively. Consider
the compound proposition:
[(p∧q)∨(¬p∧r)] →(q∨r).
Determine whether this compound proposition is a tautology, contradiction,
or contingency. Justify your answer.
Solution
Step 1: We will construct a truth table for the compound proposition to deter-
mine its logical value for all possible truth values of p,q, and r.
4
p q r (p∧q) (¬p∧r) [(p∧q)∨(¬p∧r)] (q∨r) [(p∧q)∨(¬p∧r)] →(q∨r)
T T T T F T T T
T T F T F T T T
T F T F T T T T
T F F F F F F T
F T T F F F T T
F T F F F F T T
F F T F T T T T
F F F F F F F T
Step 2: Analyzing the truth table, we see that the compound proposition
evaluates to true for all possible combinations of truth values of p,q, and r.
This means that the compound proposition is a tautology.
Hence, the compound proposition [(p∧q)∨(¬p∧r)] →(q∨r) is a tautology.
Question 8
Question
Let p,q, and rbe propositions. Determine whether the following argument is
valid: ”If p=⇒qand q=⇒r, then p=⇒r.”
Solution
To determine the validity of the argument, we can use the rules of propositional
logic to analyze the statements given.
Step 1: Write the given statements in symbolic form: - p=⇒q-q=⇒r
Step 2: Use the definition of implication to break down the statements: -
For p=⇒q:¬p∨q- For q=⇒r:¬q∨r
Step 3: Combine the two statements to form a conclusion: - We need to
check if (¬p∨q)∧(¬q∨r) logically implies ¬p∨r
Step 4: Apply the rule of transitivity to rewrite the conclusion: - ¬p∨r
Step 5: Now, check if ¬p∨rlogically follows from (¬p∨q)∧(¬q∨r) by
constructing a truth table:
p q r ¬p∨q¬q∨r(¬p∨q)∧(¬q∨r)¬p∨r
T T T T T T T
T T F T F F T
T F T F T F T
T F F F T F T
F T T T T T T
F T F T F F T
F F T T T T T
F F F T T T T
5
Step 6: From the truth table, we see that ¬p∨ris always true when
(¬p∨q)∧(¬q∨r) is true. Thus, the argument ”If p=⇒qand q=⇒r, then
p=⇒r” is valid.
Question 9
Question
Let pand qbe propositions. Show that the statement (p⇒q)∧(q⇒p) is
logically equivalent to (p∧q)∨(¬p∧ ¬q).
Solution
To show that the statement (p⇒q)∧(q⇒p) is logically equivalent to (p∧
q)∨(¬p∧ ¬q), we will construct truth tables for both statements and show that
they have the same truth values for all possible truth values of pand q.
Step 1: 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: 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 above, we can see that the statements (p⇒q)∧(q⇒p)
and (p∧q)∨(¬p∧ ¬q) have the same truth values for all possible truth values
of pand q. Therefore, they are logically equivalent.
6
Question 10
Question
Let p,q, and rbe propositional variables representing the following statements:
-p: The weather is rainy. - q: The roads are slippery. - r: There are accidents
on the roads.
Translate the following compound proposition into English: (p∧q)→r.
Solution
To translate the compound proposition (p∧q)→rinto English, we need to
consider the individual components and their logical connectives.
Step 1: Determine the meaning of each propositional variable: - p: The
weather is rainy. - q: The roads are slippery. - r: There are accidents on the
roads.
Step 2: Express the compound proposition in English: (p∧q)→rcan be
translated as ”If the weather is rainy and the roads are slippery, then there are
accidents on the roads.”
Therefore, the compound proposition (p∧q)→rcan be expressed in English
as ”If the weather is rainy and the roads are slippery, then there are accidents
on the roads.”
Question 11
Question
Let p,q, and rbe propositions. Use Propositional Logic to show that (p∧q)∨
(p∧r) is logically equivalent to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we need to
show that the truth values of the two propositions are always the same.
Step 1: Construct a truth table for both propositions.
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
7
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 of both propositions.
From the truth tables, we can see that the columns for (p∧q)∨(p∧r) and
p∧(q∨r) are identical. Therefore, (p∧q)∨(p∧r) is indeed logically equivalent
to p∧(q∨r).
Question 12
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 construct a
truth table and verify that the expression evaluates to true for all possible truth
values of p,q, and r.
Step 1: Construct the truth table for the given proposition.
p q r p ⇒q q ⇒r p ⇒r(p⇒q)∧(q⇒r)⇒(p⇒r)
T T T T T T T
T T F T F F T
T F T F T T T
T F F F T F T
F T T T T T T
F T F T F T T
F F T T T T T
F F F T T T T
Step 2: Analyze the truth table. In the last column of the truth table, we
can see that the proposition (p⇒q)∧(q⇒r)⇒(p⇒r) evaluates to true for
all possible truth values of p,q, and r. Therefore, (p⇒q)∧(q⇒r)⇒(p⇒r)
is a tautology.
8
Question 13
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using a truth table.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will construct a
truth table for all possible truth values of p,q, and r.
p q r p →q q →r(p→q)∧(q→r)p→r(p→q)∧(q→r)→(p→r)
T T T T T T T T
T T F T F F F T
T F T F T F T T
T F F F T F F T
F T T T T T T T
F T F T F F T T
F F T T T T T T
F F F T T T T T
Since the final column of the truth table is always true, we can conclude that
the proposition (p→q)∧(q→r)→(p→r) is a tautology.
Question 14
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 given statement, we can use a truth table to check all
possible truth values for p,q, and r. If the statement is always true, we can
prove it; otherwise, it is disproved.
9
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 last column of the truth table is always true, we can conclude that
the statement is true for all truth values of p,q, and r. Thus, we have proved
that (p→q)∧(q→r)→(p→r) is a valid statement in propositional logic.
Question 15
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we will construct
truth tables for both expressions and compare the results.
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
Step 2: Construct a truth table for p∧(q∨r).
10
p q r q ∨r p ∧(q∨r)
T T T T T
T T F T T
T F T T T
T F F F F
F T T T F
F T F T F
F F T T F
F F F F F
Step 3: Compare the truth tables.
From the truth tables, we can see that both expressions have the same
truth values for each combination of truth values of p,q, and r. Therefore,
(p∧q)∨(p∧r) is logically equivalent to p∧(q∨r).
Question 16
Question
Let p,q, and rbe propositions. Prove the logical equivalence (p∧q) =⇒r≡
(p=⇒r)∨(q=⇒r).
Solution
To prove the logical equivalence (p∧q) =⇒r≡(p=⇒r)∨(q=⇒r), we
will use a series of logical equivalences.
Step 1: Start by writing the definitions of the implications involved:
(p∧q) =⇒r≡ ¬(p∧q)∨r
(p=⇒r)∨(q=⇒r)
Step 2: Apply De Morgan’s Laws to the first expression:
¬(p∧q)∨r≡(¬p∨ ¬q)∨r
Step 3: Use the Distributive Law to expand the OR operator:
(¬p∨ ¬q)∨r≡(¬p∨r)∨(¬q∨r)
Step 4: Rearrange the terms:
(¬p∨r)∨(¬q∨r)≡(p=⇒r)∨(q=⇒r)
Therefore, we have shown that (p∧q) =⇒r≡(p=⇒r)∨(q=⇒r), as
desired.
11
Question 17
Question
Let p, q, and r be propositional variables. Given the statement:
(p→q)∧(q→r)→(p→r)
Determine whether the statement is a tautology, a contradiction, or neither.
Solution
Step 1: Use logical equivalences to simplify the given statement:
(p→q)∧(q→r)→(p→r)
(¬p∨q)∧(¬q∨r)→(¬p∨r)
(¬p∨q∨ ¬q∨r)→(¬p∨r)
(¬p∨r)→(¬p∨r)
¬(¬p∨r)∨(¬p∨r)
(p∧ ¬r)∨(¬p∨r)
(p∨ ¬p)∧(p∨r)∧(¬r∨ ¬p)∧(¬r∨r)
Step 2: Analyze the truth values of the compound statements:
p q r p ∨ ¬p p ∨r¬r∨ ¬p
¬r∨r
T T T T T F
T
T T F T T F
F
T F T T T F
T
T F F T T T
T
F T T T T F
T
F T F T T F
F
F F T T T F
T
F F F T F T
T
Step 3: Since there is a row in which the statement is false (the row where
pis true, qis false, and ris false), the statement is not a tautology.
Therefore, the statement is neither a tautology nor a contradiction.
12
Question 18
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we will
demonstrate the equivalence using a truth table.
p q r p ∧q p ∧r(p∧q)∨(p∧r)q∨r p ∧(q∨r)
T T T T T T T T
T T F T F T T T
T F T F T T T T
T F F F F F F F
F T T F F F T F
F T F F F F T F
F F T F F F T F
F F F F F F F F
As shown in the truth table, the columns for (p∧q)∨(p∧r) and p∧(q∨r)
are identical. Hence, the propositions (p∧q)∨(p∧r) and p∧(q∨r) are logically
equivalent.
Question 19
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 simplify
the proposition using logical equivalences until we reach a tautology (always
true statement).
Step 1: Apply the definition of the conditional statement to rewrite the
given expression as a conjunction:
(p→q)∧(q→r)→(p→r)≡ ¬[(p→q)∧(q→r)] ∨(p→r)
Step 2: Use De Morgan’s laws to simplify the negated conjunction:
¬[(p→q)∧(q→r)] ∨(p→r)≡[¬(p→q)∨ ¬(q→r)] ∨(p→r)
13
Step 3: Apply the definition of the conditional statement to the negations:
[¬(p→q)∨ ¬(q→r)] ∨(p→r)≡[(p∧ ¬q)∨(q∧ ¬r)] ∨(p→r)
Step 4: Distribute the disjunction over the conjunction:
(p∧ ¬q)∨(q∧ ¬r)∨(p→r)
Step 5: Use the distributive law again to simplify:
(p∧ ¬q)∨(q∧ ¬r)∨(p→r)≡(p∨q∨p→r)∧(¬q∨q∨p→r)∧(¬r∨q∨p→r)
Step 6: Apply the definition of the conditional statement to simplify the
disjunctions:
(p∨q∨p→r)∧(¬q∨q∨p→r)∧(¬r∨q∨p→r)≡(T∨T∨r)∧(¬q∨T∨r)∧(¬r∨q∨r)
Step 7: Further simplify the expression:
(T∨T∨r)∧(¬q∨T∨r)∧(¬r∨q∨r)≡T∧T∧T≡T
Since we have arrived at a tautology (always true statement), we can con-
clude that (p→q)∧(q→r)→(p→r) is a tautology.
Question 20
Question
Let p,q, and rbe propositional variables representing the following statements:
p: ”It is sunny.” q: ”It is warm.” r: ”It is a weekend.”
Express the following statement using propositional variables: ”It is not
sunny and warm on weekends.”
Solution
To express the given statement using propositional variables, we can break it
down into smaller parts: - It is not sunny: ¬p- It is warm: q- It is a weekend:
r
Now, we want to express ”It is not sunny and warm on weekends” using the
propositional variables p,q, and r.
The statement can be written as: ¬p∧q∧r.
Therefore, the expression for ”It is not sunny and warm on weekends” using
propositional variables is ¬p∧q∧r.
Question 21
Question
Let p,q, and rbe propositional variables. Show that the statement (p→
q)∧(q→r)→(p→r) is a tautology using truth tables.
14
Solution
To show that the statement (p→q)∧(q→r)→(p→r) is a tautology, we will
construct a truth table to evaluate all possible truth values of p,q, and r.
p q r p →q q →r p →r(p→q)∧(q→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 T F T
T F F F T F F T
F T T T T T T T
F T F T F T F T
F F T T T T T T
F F F T T T T T
Since the final column is all true values, we conclude that the statement
(p→q)∧(q→r)→(p→r) is a tautology.
Question 22
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r)⇔p∧(q∨r).
Solution
To show the equivalence (p∧q)∨(p∧r)⇔p∧(q∨r), we will prove both
directions separately.
Step 1: Show that (p∧q)∨(p∧r)⇒p∧(q∨r).
Assume that (p∧q)∨(p∧r) is true. We need to show that p∧(q∨r) is also
true.
From (p∧q)∨(p∧r), we can infer by distribution that p∧(q∨r).
Therefore, (p∧q)∨(p∧r)⇒p∧(q∨r).
Step 2: Show that p∧(q∨r)⇒(p∧q)∨(p∧r).
Assume that p∧(q∨r) is true. We need to show that (p∧q)∨(p∧r) is also
true.
From p∧(q∨r), we can infer by distribution that (p∧q)∨(p∧r).
Therefore, p∧(q∨r)⇒(p∧q)∨(p∧r).
Since we have shown both directions, we conclude that (p∧q)∨(p∧r)⇔
p∧(q∨r).
15
Question 23
Question
Let p,q, and rbe propositions. Prove the following logical equivalence: (p→
(q→r)) ≡((p∧q)→r).
Solution
To prove the logical equivalence (p→(q→r)) ≡((p∧q)→r), we will show
that both sides imply each other using logical equivalences and properties of
propositional logic.
Step 1: We will start by simplifying the left-hand side of the equivalence:
(p→(q→r)) ≡(¬p∨(q→r))
≡(¬p∨ ¬q∨r)
Step 2: Next, we will simplify the right-hand side of the equivalence:
((p∧q)→r)≡(¬(p∧q)∨r)
≡((¬p∨ ¬q)∨r)
≡(¬p∨ ¬q∨r)
Step 3: Since both sides simplify to the same expression, we have shown
that
(p→(q→r)) ≡((p∧q)→r).
Therefore, the logical equivalence is proven.
Question 24
Question
Let p,q, and rbe propositions. Determine whether the statement (p∨q)∧(¬p∨r)
is logically equivalent to q∨r.
Solution
To determine whether (p∨q)∧(¬p∨r) is logically equivalent to q∨r, we can
use truth tables.
Step 1: Create a Truth Table
We will create a truth table with columns for p,q,r, (p∨q), (¬p∨r), and
(p∨q)∧(¬p∨r), as well as a column for q∨r.
16
p q r p ∨q¬p∨r(p∨q)∧(¬p∨r)q∨r
T T T
T T F
T F T
T F F
F T T
F T F
F F T
FFF
Step 2: Fill in the Truth Table
Fill in the truth table by evaluating the propositions (p∨q), (¬p∨r), (p∨
q)∧(¬p∨r), and q∨rfor each combination of truth values of p,q, and r.
p q r p ∨q¬p∨r(p∨q)∧(¬p∨r)q∨r
T T T T T T T
T T F T F F T
T F T T T T T
T F F T T T F
F T T T T T T
F T F T T T T
F F T F T F T
F F F F T F F
Step 3: Conclusion
From the truth table, we can see that the statement (p∨q)∧(¬p∨r) is not
logically equivalent to q∨rsince the final columns have different truth values
for some rows.
Question 25
Question
Let p,q, and rbe propositional variables. Determine whether the following
statement is a tautology, a contradiction, or contingent:
(p∧q)→((p∨q)∧(¬p∨ ¬q)) →(p↔q)
Solution
To determine whether the given statement is a tautology, a contradiction, or
contingent, we can use truth tables.
Step 1: Construct truth table for the given statement
17
p q r p ∧q p ∨q¬p¬q¬p∨ ¬q p ↔qStatement
T T T T T F F F T T
T T F T T F F F T T
T F T F T F T T F T
T F F F T F T T F T
F T T F T T F T F T
F T F F T T F T F T
F F T F F T T T T T
F F F F F T T T T T
Step 2: Analyze the truth values of the statement
From the truth table, we can see that the statement is contingent because
it is neither a tautology (always true) nor a contradiction (always false).
Question 26
Question
Let p,q, and rbe propositions. Show whether the following argument is valid
or invalid using propositional calculus:
p→(q∧r)
(p∨q)→r
q
∴r
Solution
To determine the validity of the argument, we will construct a truth table.
p q r p →(q∧r) (p∨q)→r q p ∨q∴r
T T T T T T T T
T T F F F T T F
T F T T T F T T
T F F F F F T F
F T T T T T T T
F T F T F T T F
F F T T T F F T
F F F T T F F T
In the last column, ∴ris false when pis true, qis false, and ris true. Since
there is a row where all the premises are true but the conclusion is false, the
argument is invalid.
18
Question 27
Question
Let p,q,rbe propositions, where
p: ”It is raining.”
q: ”The grass is wet.”
r: ”The sun is shining.”
Express the following statement using propositions p,q, and r: ”If it is not
raining and the sun is shining, then the grass is not wet.”
Solution
To express the given statement using propositions p,q, and r, we need to con-
sider the logical connectives involved.
Step 1: Identify the components of the statement. Let’s break down
the original statement: ”If it is not raining and the sun is shining, then the grass
is not wet.” This can be represented as:
(¬p∧r)→ ¬q
Step 2: Explain the components. -¬prepresents ”It is not raining.” - r
represents ”The sun is shining.” - qrepresents ”The grass is wet.” - ∧represents
the logical operation AND. - →represents the logical operation IMPLIES.
Step 3: State the final representation. Therefore, the given statement
”If it is not raining and the sun is shining, then the grass is not wet” can be
expressed as:
(¬p∧r)→ ¬q
Question 28
Question
Let p,q, and rbe propositions. Show whether the following argument is valid
or invalid:
If pthen q.
If qthen r.
Therefore, if pthen r.
Solution
To determine the validity of the argument, we will use the rules of implication
in propositional logic.
19
Step 1: Write down the given premises and conclusion in symbolic form:
Given premises:
(p→q) Premise 1
(q→r) Premise 2
Desired conclusion:
(p→r)
Step 2: Apply the Transitivity of Implication: Since we are given p→q
and q→r, we can apply the transitivity of implication to derive p→r.
Step 3: Transitivity of Implication: If statement A implies statement B,
and statement B implies statement C, then statement A implies statement C.
Step 4: Apply the transitivity of implication to prove the validity of the
argument: From Premise 1: p→q
From Premise 2: q→r
Using the transitivity of implication, we have:
p→q→r
Simplifying this gives us:
p→r
Therefore, the argument is valid as we have successfully shown that if pthen
q, and if qthen r, then if pthen r.
Question 29
Question
Let p, q, and rbe propositions. Determine whether the argument below is valid:
If (p→q)∧(q→r), then (p→r)
Solution
To determine the validity of the argument, we need to check if the conclusion,
(p→r), follows from the premises, (p→q)∧(q→r).
Step 1: Let’s analyze the premises using the truth table method.
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
20
Step 2: From the truth table, we see that (p→q)∧(q→r) is not a tautology.
Specifically, when pis true, qis true, and ris false, the premises are true but
the conclusion is false.
Step 3: Since the premises do not guarantee the truth of the conclusion in
all cases, the argument is not valid.
Therefore, the argument ”If (p→q)∧(q→r), then (p→r)” is not valid.
Question 30
Question
Let p,q, and rbe propositions. Prove or disprove the following statement using
propositional logic: (p→q)∧(q→r)→(p→r).
Solution
To prove the statement (p→q)∧(q→r)→(p→r), we will evaluate the truth
values of each proposition in different scenarios.
Step 1: Construct a truth table
First, let’s construct a truth table for the given compound proposition.
p q r p →q q →r(p→q)∧(q→r)
p→r
T T T T T T
T
T T F T F F
F
T F T F T F
T
T F F F T F
F
F T T T T T
T
F T F T F F
T
F F T T T T
T
F F F T T T
T
Step 2: Analyze the truth values
From the truth table, we can see that the statement (p→q)∧(q→r)→
(p→r) is FALSE when pis true, qis true, and ris false.
Step 3: Conclusion
21
Therefore, we have shown that the statement (p→q)∧(q→r)→(p→r)
is not always true, as there exists a scenario where the statement is false. Thus,
the statement is disproved.
Question 31
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 (p→q)∧(q→r)→(p→r) is a tautology, we
need to show that its truth table only contains T (true) values.
p q r p →q q →r(p→q)∧(q→r)p→r(p→q)∧(q→r)→(p→r)
F F F T T T T T
F F T T T T T T
F T F T F F T T
F T T T T T T T
T F F F T F F T
T F T F T F T T
T T F T F F F T
T T T T T T T T
Since the final column of the truth table consists only of T (true) values, we
can conclude that the proposition (p→q)∧(q→r)→(p→r) is a tautology.
Question 32
Question
Given the following premises:
p→(q∨r)
¬r→s
s→ ¬p
Prove that ¬qholds true.
22
Solution
Step 1: Assume ¬qis false, i.e., qis true.
Using the premise p→(q∨r) :
If pis true, then qor ris true.
Since qis true, rmust be false to satisfy p→(q∨r).
Step 2: Consider ¬r→sand ¬q≡ ¬(q∨r).
From ¬r→sand ¬q≡ ¬(q∨r),
Since ris false, qcannot be true since ¬qholds true.
So, ¬qmust be true.
Step 3: Conclusion
Therefore, based on our assumption that qis true, we have reached a contradiction.
Thus, our initial assumption was incorrect, and ¬qmust be true.
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
use a truth table to verify that they have the same truth values for all possible
truth values of p,q, and r.
p q r p ∧q(p∧q)→r p →r q →r
T T T T T T T
T T F T F F F
T F T F T T T
T F F F T F T
F T T F T T T
F T F F T T F
F F T F T T T
F F F F T T T
From the truth table, we see that for all possible truth values of p,q, and r,
(p∧q)→rand (p→r)∨(q→r) have the same truth values. Therefore, we
have shown that (p∧q)→ris logically equivalent to (p→r)∨(q→r).
23
Question 34
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 demonstrate that the compound proposition is true for all possible truth
values of p,q, and r.
Step 1: Create the Truth Table
p q r p →q q →r p →r(p→q)∧(q→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 T F T
T F F F T F F T
F T T T T T T T
F T F T F T F T
F F T T T T T T
F F F T T T T T
Step 2: Analyze the Truth Table
From the truth table, we see that the final column is true for all possible
truth values of p,q, and r. Thus, (p→q)∧(q→r)→(p→r) is a tautology.
Question 35
Question
Let p,q, and rbe propositional variables. Determine whether the following
statement is a tautology, a contradiction, or neither:
(p→q)∧(q→r)∧(r→p)
Justify your answer.
Solution
To determine whether the given statement is a tautology, we will construct a
truth table to evaluate all possible truth values of p,q, and r.
Step 1: Create a truth table to evaluate the truth values of (p→q), (q→r),
(r→p), and the given statement (p→q)∧(q→r)∧(r→p).
24
Solution
To determine the validity of the argument, we will use propositional logic to
symbolize the statements and then apply the rules of inference.
Let: - p: It is raining. - q: The picnic will be canceled. - r: We will have a
movie night.
The argument can be represented as: - (¬p→q) - (q→r) - ∴(¬p→r)
We will now prove whether the conclusion logically follows from the premises.
Step 1: Apply Modus Ponens to (¬p→q) and (q→r).
By Modus Ponens, if we have statements of the form (a→b) and (b→c),
we can infer (a→c).
Step 2: Apply Modus Ponens.
Given: - (¬p→q) - (q→r)
Since the form of these statements allows for the use of Modus Ponens, we
can conclude: - ∴(¬p→r)
Since the conclusion follows logically from the premises, the argument is
valid.
Question 3
Question
Let p, q, and r be propositions. Show whether the statement (p∧q)∨(p∧r)
is logically equivalent to p∧(q∨r) using the laws of logic and propositional
calculus.
Solution
To determine whether (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we
can use the laws of logic to simplify both statements and then compare them.
Step 1: Apply the distributive law: Apply the distributive law to
(p∧q)∨(p∧r):
(p∧q)∨(p∧r) = p∧(q∨r)
Step 2: Justify the logical equivalence: Since we have shown that
(p∧q)∨(p∧r) simplifies to p∧(q∨r), we can conclude that the two statements
are logically equivalent.
Question 4
Question
Let prepresent the statement ”Karen will go to the concert” and qrepresent the
statement ”Jim will go to the movie.” Write the following statement in symbolic
form: ”Karen will go to the concert and Jim will not go to the movie.”
2
Solution
To represent the statement ”Karen will go to the concert and Jim will not go
to the movie” symbolically, we need to use logical connectives. The logical
connective for ”and” is represented by ∧and the negation of a statement is
represented by ¬.
Therefore, the symbolic form of the given statement is:
p∧ ¬q
Question 5
Question
Let pand qbe propositions. Show that (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 the truth values of the two compound propositions are the same for
all possible truth values of pand q.
Step 1: Construct truth tables for (p→q)∧(q→p) and (p↔q).
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
The truth table for (p↔q) is:
p q p ↔q
T T T
T F F
F T F
F F T
Step 2: Compare the truth values of the two compound propositions in the
truth tables.
By comparing the truth tables, we see that the truth values of (p→q)∧(q→
p) and (p↔q) are the same for all possible truth values of pand q. Therefore,
we can conclude that (p→q)∧(q→p) is logically equivalent to (p↔q).
3
Question 6
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 logical
equivalence rules and logical inference rules.
Step 1: Apply the definition of implication Recall that a→bis
equivalent to ¬a∨b.
So, the given expression becomes: (¬p∨q)∧(¬q∨r)→(¬p∨r).
Step 2: Use the definition of implication in the disjunction By the
distribution property of ∧over ∨, we have: (¬p∧¬q)∨(¬p∧r)∨(q∧¬q)∨(q∧r)→
(¬p∨r).
Step 3: Simplify the expression using tautologies -¬p∧ ¬qsimplifies
to ¬(p∨q), which is always false. - q∧ ¬qis always false. - (¬p∧r)∨(q∧r)
simplifies to (¬p∨q)∧r.
So, (¬p∨r)→(¬p∨r).
Step 4: Use the principle of explosion Since p∨ ¬pis always true, the
expression simplifies to ⊤→⊤, which is a tautology.
Therefore, (p→q)∧(q→r)→(p→r) is a tautology.
Question 7
Question
Let p,q, and rbe propositional variables representing the statements ”It is
raining”, ”The streets are wet”, and ”The grass is wet”, respectively. Consider
the compound proposition:
[(p∧q)∨(¬p∧r)] →(q∨r).
Determine whether this compound proposition is a tautology, contradiction,
or contingency. Justify your answer.
Solution
Step 1: We will construct a truth table for the compound proposition to deter-
mine its logical value for all possible truth values of p,q, and r.
4
p q r (p∧q) (¬p∧r) [(p∧q)∨(¬p∧r)] (q∨r) [(p∧q)∨(¬p∧r)] →(q∨r)
T T T T F T T T
T T F T F T T T
T F T F T T T T
T F F F F F F T
F T T F F F T T
F T F F F F T T
F F T F T T T T
F F F F F F F T
Step 2: Analyzing the truth table, we see that the compound proposition
evaluates to true for all possible combinations of truth values of p,q, and r.
This means that the compound proposition is a tautology.
Hence, the compound proposition [(p∧q)∨(¬p∧r)] →(q∨r) is a tautology.
Question 8
Question
Let p,q, and rbe propositions. Determine whether the following argument is
valid: ”If p=⇒qand q=⇒r, then p=⇒r.”
Solution
To determine the validity of the argument, we can use the rules of propositional
logic to analyze the statements given.
Step 1: Write the given statements in symbolic form: - p=⇒q-q=⇒r
Step 2: Use the definition of implication to break down the statements: -
For p=⇒q:¬p∨q- For q=⇒r:¬q∨r
Step 3: Combine the two statements to form a conclusion: - We need to
check if (¬p∨q)∧(¬q∨r) logically implies ¬p∨r
Step 4: Apply the rule of transitivity to rewrite the conclusion: - ¬p∨r
Step 5: Now, check if ¬p∨rlogically follows from (¬p∨q)∧(¬q∨r) by
constructing a truth table:
p q r ¬p∨q¬q∨r(¬p∨q)∧(¬q∨r)¬p∨r
T T T T T T T
T T F T F F T
T F T F T F T
T F F F T F T
F T T T T T T
F T F T F F T
F F T T T T T
F F F T T T T
5
Step 6: From the truth table, we see that ¬p∨ris always true when
(¬p∨q)∧(¬q∨r) is true. Thus, the argument ”If p=⇒qand q=⇒r, then
p=⇒r” is valid.
Question 9
Question
Let pand qbe propositions. Show that the statement (p⇒q)∧(q⇒p) is
logically equivalent to (p∧q)∨(¬p∧ ¬q).
Solution
To show that the statement (p⇒q)∧(q⇒p) is logically equivalent to (p∧
q)∨(¬p∧ ¬q), we will construct truth tables for both statements and show that
they have the same truth values for all possible truth values of pand q.
Step 1: 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: 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 above, we can see that the statements (p⇒q)∧(q⇒p)
and (p∧q)∨(¬p∧ ¬q) have the same truth values for all possible truth values
of pand q. Therefore, they are logically equivalent.
6
Question 10
Question
Let p,q, and rbe propositional variables representing the following statements:
-p: The weather is rainy. - q: The roads are slippery. - r: There are accidents
on the roads.
Translate the following compound proposition into English: (p∧q)→r.
Solution
To translate the compound proposition (p∧q)→rinto English, we need to
consider the individual components and their logical connectives.
Step 1: Determine the meaning of each propositional variable: - p: The
weather is rainy. - q: The roads are slippery. - r: There are accidents on the
roads.
Step 2: Express the compound proposition in English: (p∧q)→rcan be
translated as ”If the weather is rainy and the roads are slippery, then there are
accidents on the roads.”
Therefore, the compound proposition (p∧q)→rcan be expressed in English
as ”If the weather is rainy and the roads are slippery, then there are accidents
on the roads.”
Question 11
Question
Let p,q, and rbe propositions. Use Propositional Logic to show that (p∧q)∨
(p∧r) is logically equivalent to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we need to
show that the truth values of the two propositions are always the same.
Step 1: Construct a truth table for both propositions.
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
7
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 of both propositions.
From the truth tables, we can see that the columns for (p∧q)∨(p∧r) and
p∧(q∨r) are identical. Therefore, (p∧q)∨(p∧r) is indeed logically equivalent
to p∧(q∨r).
Question 12
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 construct a
truth table and verify that the expression evaluates to true for all possible truth
values of p,q, and r.
Step 1: Construct the truth table for the given proposition.
p q r p ⇒q q ⇒r p ⇒r(p⇒q)∧(q⇒r)⇒(p⇒r)
T T T T T T T
T T F T F F T
T F T F T T T
T F F F T F T
F T T T T T T
F T F T F T T
F F T T T T T
F F F T T T T
Step 2: Analyze the truth table. In the last column of the truth table, we
can see that the proposition (p⇒q)∧(q⇒r)⇒(p⇒r) evaluates to true for
all possible truth values of p,q, and r. Therefore, (p⇒q)∧(q⇒r)⇒(p⇒r)
is a tautology.
8
Question 13
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using a truth table.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will construct a
truth table for all possible truth values of p,q, and r.
p q r p →q q →r(p→q)∧(q→r)p→r(p→q)∧(q→r)→(p→r)
T T T T T T T T
T T F T F F F T
T F T F T F T T
T F F F T F F T
F T T T T T T T
F T F T F F T T
F F T T T T T T
F F F T T T T T
Since the final column of the truth table is always true, we can conclude that
the proposition (p→q)∧(q→r)→(p→r) is a tautology.
Question 14
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 given statement, we can use a truth table to check all
possible truth values for p,q, and r. If the statement is always true, we can
prove it; otherwise, it is disproved.
9
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 last column of the truth table is always true, we can conclude that
the statement is true for all truth values of p,q, and r. Thus, we have proved
that (p→q)∧(q→r)→(p→r) is a valid statement in propositional logic.
Question 15
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we will construct
truth tables for both expressions and compare the results.
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
Step 2: Construct a truth table for p∧(q∨r).
10
p q r q ∨r p ∧(q∨r)
T T T T T
T T F T T
T F T T T
T F F F F
F T T T F
F T F T F
F F T T F
F F F F F
Step 3: Compare the truth tables.
From the truth tables, we can see that both expressions have the same
truth values for each combination of truth values of p,q, and r. Therefore,
(p∧q)∨(p∧r) is logically equivalent to p∧(q∨r).
Question 16
Question
Let p,q, and rbe propositions. Prove the logical equivalence (p∧q) =⇒r≡
(p=⇒r)∨(q=⇒r).
Solution
To prove the logical equivalence (p∧q) =⇒r≡(p=⇒r)∨(q=⇒r), we
will use a series of logical equivalences.
Step 1: Start by writing the definitions of the implications involved:
(p∧q) =⇒r≡ ¬(p∧q)∨r
(p=⇒r)∨(q=⇒r)
Step 2: Apply De Morgan’s Laws to the first expression:
¬(p∧q)∨r≡(¬p∨ ¬q)∨r
Step 3: Use the Distributive Law to expand the OR operator:
(¬p∨ ¬q)∨r≡(¬p∨r)∨(¬q∨r)
Step 4: Rearrange the terms:
(¬p∨r)∨(¬q∨r)≡(p=⇒r)∨(q=⇒r)
Therefore, we have shown that (p∧q) =⇒r≡(p=⇒r)∨(q=⇒r), as
desired.
11
Question 17
Question
Let p, q, and r be propositional variables. Given the statement:
(p→q)∧(q→r)→(p→r)
Determine whether the statement is a tautology, a contradiction, or neither.
Solution
Step 1: Use logical equivalences to simplify the given statement:
(p→q)∧(q→r)→(p→r)
(¬p∨q)∧(¬q∨r)→(¬p∨r)
(¬p∨q∨ ¬q∨r)→(¬p∨r)
(¬p∨r)→(¬p∨r)
¬(¬p∨r)∨(¬p∨r)
(p∧ ¬r)∨(¬p∨r)
(p∨ ¬p)∧(p∨r)∧(¬r∨ ¬p)∧(¬r∨r)
Step 2: Analyze the truth values of the compound statements:
p q r p ∨ ¬p p ∨r¬r∨ ¬p
¬r∨r
T T T T T F
T
T T F T T F
F
T F T T T F
T
T F F T T T
T
F T T T T F
T
F T F T T F
F
F F T T T F
T
F F F T F T
T
Step 3: Since there is a row in which the statement is false (the row where
pis true, qis false, and ris false), the statement is not a tautology.
Therefore, the statement is neither a tautology nor a contradiction.
12
Question 18
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we will
demonstrate the equivalence using a truth table.
p q r p ∧q p ∧r(p∧q)∨(p∧r)q∨r p ∧(q∨r)
T T T T T T T T
T T F T F T T T
T F T F T T T T
T F F F F F F F
F T T F F F T F
F T F F F F T F
F F T F F F T F
F F F F F F F F
As shown in the truth table, the columns for (p∧q)∨(p∧r) and p∧(q∨r)
are identical. Hence, the propositions (p∧q)∨(p∧r) and p∧(q∨r) are logically
equivalent.
Question 19
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 simplify
the proposition using logical equivalences until we reach a tautology (always
true statement).
Step 1: Apply the definition of the conditional statement to rewrite the
given expression as a conjunction:
(p→q)∧(q→r)→(p→r)≡ ¬[(p→q)∧(q→r)] ∨(p→r)
Step 2: Use De Morgan’s laws to simplify the negated conjunction:
¬[(p→q)∧(q→r)] ∨(p→r)≡[¬(p→q)∨ ¬(q→r)] ∨(p→r)
13
Step 3: Apply the definition of the conditional statement to the negations:
[¬(p→q)∨ ¬(q→r)] ∨(p→r)≡[(p∧ ¬q)∨(q∧ ¬r)] ∨(p→r)
Step 4: Distribute the disjunction over the conjunction:
(p∧ ¬q)∨(q∧ ¬r)∨(p→r)
Step 5: Use the distributive law again to simplify:
(p∧ ¬q)∨(q∧ ¬r)∨(p→r)≡(p∨q∨p→r)∧(¬q∨q∨p→r)∧(¬r∨q∨p→r)
Step 6: Apply the definition of the conditional statement to simplify the
disjunctions:
(p∨q∨p→r)∧(¬q∨q∨p→r)∧(¬r∨q∨p→r)≡(T∨T∨r)∧(¬q∨T∨r)∧(¬r∨q∨r)
Step 7: Further simplify the expression:
(T∨T∨r)∧(¬q∨T∨r)∧(¬r∨q∨r)≡T∧T∧T≡T
Since we have arrived at a tautology (always true statement), we can con-
clude that (p→q)∧(q→r)→(p→r) is a tautology.
Question 20
Question
Let p,q, and rbe propositional variables representing the following statements:
p: ”It is sunny.” q: ”It is warm.” r: ”It is a weekend.”
Express the following statement using propositional variables: ”It is not
sunny and warm on weekends.”
Solution
To express the given statement using propositional variables, we can break it
down into smaller parts: - It is not sunny: ¬p- It is warm: q- It is a weekend:
r
Now, we want to express ”It is not sunny and warm on weekends” using the
propositional variables p,q, and r.
The statement can be written as: ¬p∧q∧r.
Therefore, the expression for ”It is not sunny and warm on weekends” using
propositional variables is ¬p∧q∧r.
Question 21
Question
Let p,q, and rbe propositional variables. Show that the statement (p→
q)∧(q→r)→(p→r) is a tautology using truth tables.
14
Solution
To show that the statement (p→q)∧(q→r)→(p→r) is a tautology, we will
construct a truth table to evaluate all possible truth values of p,q, and r.
p q r p →q q →r p →r(p→q)∧(q→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 T F T
T F F F T F F T
F T T T T T T T
F T F T F T F T
F F T T T T T T
F F F T T T T T
Since the final column is all true values, we conclude that the statement
(p→q)∧(q→r)→(p→r) is a tautology.
Question 22
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r)⇔p∧(q∨r).
Solution
To show the equivalence (p∧q)∨(p∧r)⇔p∧(q∨r), we will prove both
directions separately.
Step 1: Show that (p∧q)∨(p∧r)⇒p∧(q∨r).
Assume that (p∧q)∨(p∧r) is true. We need to show that p∧(q∨r) is also
true.
From (p∧q)∨(p∧r), we can infer by distribution that p∧(q∨r).
Therefore, (p∧q)∨(p∧r)⇒p∧(q∨r).
Step 2: Show that p∧(q∨r)⇒(p∧q)∨(p∧r).
Assume that p∧(q∨r) is true. We need to show that (p∧q)∨(p∧r) is also
true.
From p∧(q∨r), we can infer by distribution that (p∧q)∨(p∧r).
Therefore, p∧(q∨r)⇒(p∧q)∨(p∧r).
Since we have shown both directions, we conclude that (p∧q)∨(p∧r)⇔
p∧(q∨r).
15
Question 23
Question
Let p,q, and rbe propositions. Prove the following logical equivalence: (p→
(q→r)) ≡((p∧q)→r).
Solution
To prove the logical equivalence (p→(q→r)) ≡((p∧q)→r), we will show
that both sides imply each other using logical equivalences and properties of
propositional logic.
Step 1: We will start by simplifying the left-hand side of the equivalence:
(p→(q→r)) ≡(¬p∨(q→r))
≡(¬p∨ ¬q∨r)
Step 2: Next, we will simplify the right-hand side of the equivalence:
((p∧q)→r)≡(¬(p∧q)∨r)
≡((¬p∨ ¬q)∨r)
≡(¬p∨ ¬q∨r)
Step 3: Since both sides simplify to the same expression, we have shown
that
(p→(q→r)) ≡((p∧q)→r).
Therefore, the logical equivalence is proven.
Question 24
Question
Let p,q, and rbe propositions. Determine whether the statement (p∨q)∧(¬p∨r)
is logically equivalent to q∨r.
Solution
To determine whether (p∨q)∧(¬p∨r) is logically equivalent to q∨r, we can
use truth tables.
Step 1: Create a Truth Table
We will create a truth table with columns for p,q,r, (p∨q), (¬p∨r), and
(p∨q)∧(¬p∨r), as well as a column for q∨r.
16
p q r p ∨q¬p∨r(p∨q)∧(¬p∨r)q∨r
T T T
T T F
T F T
T F F
F T T
F T F
F F T
FFF
Step 2: Fill in the Truth Table
Fill in the truth table by evaluating the propositions (p∨q), (¬p∨r), (p∨
q)∧(¬p∨r), and q∨rfor each combination of truth values of p,q, and r.
p q r p ∨q¬p∨r(p∨q)∧(¬p∨r)q∨r
T T T T T T T
T T F T F F T
T F T T T T T
T F F T T T F
F T T T T T T
F T F T T T T
F F T F T F T
F F F F T F F
Step 3: Conclusion
From the truth table, we can see that the statement (p∨q)∧(¬p∨r) is not
logically equivalent to q∨rsince the final columns have different truth values
for some rows.
Question 25
Question
Let p,q, and rbe propositional variables. Determine whether the following
statement is a tautology, a contradiction, or contingent:
(p∧q)→((p∨q)∧(¬p∨ ¬q)) →(p↔q)
Solution
To determine whether the given statement is a tautology, a contradiction, or
contingent, we can use truth tables.
Step 1: Construct truth table for the given statement
17
p q r p ∧q p ∨q¬p¬q¬p∨ ¬q p ↔qStatement
T T T T T F F F T T
T T F T T F F F T T
T F T F T F T T F T
T F F F T F T T F T
F T T F T T F T F T
F T F F T T F T F T
F F T F F T T T T T
F F F F F T T T T T
Step 2: Analyze the truth values of the statement
From the truth table, we can see that the statement is contingent because
it is neither a tautology (always true) nor a contradiction (always false).
Question 26
Question
Let p,q, and rbe propositions. Show whether the following argument is valid
or invalid using propositional calculus:
p→(q∧r)
(p∨q)→r
q
∴r
Solution
To determine the validity of the argument, we will construct a truth table.
p q r p →(q∧r) (p∨q)→r q p ∨q∴r
T T T T T T T T
T T F F F T T F
T F T T T F T T
T F F F F F T F
F T T T T T T T
F T F T F T T F
F F T T T F F T
F F F T T F F T
In the last column, ∴ris false when pis true, qis false, and ris true. Since
there is a row where all the premises are true but the conclusion is false, the
argument is invalid.
18
Question 27
Question
Let p,q,rbe propositions, where
p: ”It is raining.”
q: ”The grass is wet.”
r: ”The sun is shining.”
Express the following statement using propositions p,q, and r: ”If it is not
raining and the sun is shining, then the grass is not wet.”
Solution
To express the given statement using propositions p,q, and r, we need to con-
sider the logical connectives involved.
Step 1: Identify the components of the statement. Let’s break down
the original statement: ”If it is not raining and the sun is shining, then the grass
is not wet.” This can be represented as:
(¬p∧r)→ ¬q
Step 2: Explain the components. -¬prepresents ”It is not raining.” - r
represents ”The sun is shining.” - qrepresents ”The grass is wet.” - ∧represents
the logical operation AND. - →represents the logical operation IMPLIES.
Step 3: State the final representation. Therefore, the given statement
”If it is not raining and the sun is shining, then the grass is not wet” can be
expressed as:
(¬p∧r)→ ¬q
Question 28
Question
Let p,q, and rbe propositions. Show whether the following argument is valid
or invalid:
If pthen q.
If qthen r.
Therefore, if pthen r.
Solution
To determine the validity of the argument, we will use the rules of implication
in propositional logic.
19
Step 1: Write down the given premises and conclusion in symbolic form:
Given premises:
(p→q) Premise 1
(q→r) Premise 2
Desired conclusion:
(p→r)
Step 2: Apply the Transitivity of Implication: Since we are given p→q
and q→r, we can apply the transitivity of implication to derive p→r.
Step 3: Transitivity of Implication: If statement A implies statement B,
and statement B implies statement C, then statement A implies statement C.
Step 4: Apply the transitivity of implication to prove the validity of the
argument: From Premise 1: p→q
From Premise 2: q→r
Using the transitivity of implication, we have:
p→q→r
Simplifying this gives us:
p→r
Therefore, the argument is valid as we have successfully shown that if pthen
q, and if qthen r, then if pthen r.
Question 29
Question
Let p, q, and rbe propositions. Determine whether the argument below is valid:
If (p→q)∧(q→r), then (p→r)
Solution
To determine the validity of the argument, we need to check if the conclusion,
(p→r), follows from the premises, (p→q)∧(q→r).
Step 1: Let’s analyze the premises using the truth table method.
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
20
Step 2: From the truth table, we see that (p→q)∧(q→r) is not a tautology.
Specifically, when pis true, qis true, and ris false, the premises are true but
the conclusion is false.
Step 3: Since the premises do not guarantee the truth of the conclusion in
all cases, the argument is not valid.
Therefore, the argument ”If (p→q)∧(q→r), then (p→r)” is not valid.
Question 30
Question
Let p,q, and rbe propositions. Prove or disprove the following statement using
propositional logic: (p→q)∧(q→r)→(p→r).
Solution
To prove the statement (p→q)∧(q→r)→(p→r), we will evaluate the truth
values of each proposition in different scenarios.
Step 1: Construct a truth table
First, let’s construct a truth table for the given compound proposition.
p q r p →q q →r(p→q)∧(q→r)
p→r
T T T T T T
T
T T F T F F
F
T F T F T F
T
T F F F T F
F
F T T T T T
T
F T F T F F
T
F F T T T T
T
F F F T T T
T
Step 2: Analyze the truth values
From the truth table, we can see that the statement (p→q)∧(q→r)→
(p→r) is FALSE when pis true, qis true, and ris false.
Step 3: Conclusion
21
Therefore, we have shown that the statement (p→q)∧(q→r)→(p→r)
is not always true, as there exists a scenario where the statement is false. Thus,
the statement is disproved.
Question 31
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 (p→q)∧(q→r)→(p→r) is a tautology, we
need to show that its truth table only contains T (true) values.
p q r p →q q →r(p→q)∧(q→r)p→r(p→q)∧(q→r)→(p→r)
F F F T T T T T
F F T T T T T T
F T F T F F T T
F T T T T T T T
T F F F T F F T
T F T F T F T T
T T F T F F F T
T T T T T T T T
Since the final column of the truth table consists only of T (true) values, we
can conclude that the proposition (p→q)∧(q→r)→(p→r) is a tautology.
Question 32
Question
Given the following premises:
p→(q∨r)
¬r→s
s→ ¬p
Prove that ¬qholds true.
22
Solution
Step 1: Assume ¬qis false, i.e., qis true.
Using the premise p→(q∨r) :
If pis true, then qor ris true.
Since qis true, rmust be false to satisfy p→(q∨r).
Step 2: Consider ¬r→sand ¬q≡ ¬(q∨r).
From ¬r→sand ¬q≡ ¬(q∨r),
Since ris false, qcannot be true since ¬qholds true.
So, ¬qmust be true.
Step 3: Conclusion
Therefore, based on our assumption that qis true, we have reached a contradiction.
Thus, our initial assumption was incorrect, and ¬qmust be true.
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
use a truth table to verify that they have the same truth values for all possible
truth values of p,q, and r.
p q r p ∧q(p∧q)→r p →r q →r
T T T T T T T
T T F T F F F
T F T F T T T
T F F F T F T
F T T F T T T
F T F F T T F
F F T F T T T
F F F F T T T
From the truth table, we see that for all possible truth values of p,q, and r,
(p∧q)→rand (p→r)∨(q→r) have the same truth values. Therefore, we
have shown that (p∧q)→ris logically equivalent to (p→r)∨(q→r).
23
Question 34
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 demonstrate that the compound proposition is true for all possible truth
values of p,q, and r.
Step 1: Create the Truth Table
p q r p →q q →r p →r(p→q)∧(q→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 T F T
T F F F T F F T
F T T T T T T T
F T F T F T F T
F F T T T T T T
F F F T T T T T
Step 2: Analyze the Truth Table
From the truth table, we see that the final column is true for all possible
truth values of p,q, and r. Thus, (p→q)∧(q→r)→(p→r) is a tautology.
Question 35
Question
Let p,q, and rbe propositional variables. Determine whether the following
statement is a tautology, a contradiction, or neither:
(p→q)∧(q→r)∧(r→p)
Justify your answer.
Solution
To determine whether the given statement is a tautology, we will construct a
truth table to evaluate all possible truth values of p,q, and r.
Step 1: Create a truth table to evaluate the truth values of (p→q), (q→r),
(r→p), and the given statement (p→q)∧(q→r)∧(r→p).
24
Solution
To determine the validity of the argument, we will use propositional logic to
symbolize the statements and then apply the rules of inference.
Let: - p: It is raining. - q: The picnic will be canceled. - r: We will have a
movie night.
The argument can be represented as: - (¬p→q) - (q→r) - ∴(¬p→r)
We will now prove whether the conclusion logically follows from the premises.
Step 1: Apply Modus Ponens to (¬p→q) and (q→r).
By Modus Ponens, if we have statements of the form (a→b) and (b→c),
we can infer (a→c).
Step 2: Apply Modus Ponens.
Given: - (¬p→q) - (q→r)
Since the form of these statements allows for the use of Modus Ponens, we
can conclude: - ∴(¬p→r)
Since the conclusion follows logically from the premises, the argument is
valid.
Question 3
Question
Let p, q, and r be propositions. Show whether the statement (p∧q)∨(p∧r)
is logically equivalent to p∧(q∨r) using the laws of logic and propositional
calculus.
Solution
To determine whether (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we
can use the laws of logic to simplify both statements and then compare them.
Step 1: Apply the distributive law: Apply the distributive law to
(p∧q)∨(p∧r):
(p∧q)∨(p∧r) = p∧(q∨r)
Step 2: Justify the logical equivalence: Since we have shown that
(p∧q)∨(p∧r) simplifies to p∧(q∨r), we can conclude that the two statements
are logically equivalent.
Question 4
Question
Let prepresent the statement ”Karen will go to the concert” and qrepresent the
statement ”Jim will go to the movie.” Write the following statement in symbolic
form: ”Karen will go to the concert and Jim will not go to the movie.”
2
Solution
To represent the statement ”Karen will go to the concert and Jim will not go
to the movie” symbolically, we need to use logical connectives. The logical
connective for ”and” is represented by ∧and the negation of a statement is
represented by ¬.
Therefore, the symbolic form of the given statement is:
p∧ ¬q
Question 5
Question
Let pand qbe propositions. Show that (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 the truth values of the two compound propositions are the same for
all possible truth values of pand q.
Step 1: Construct truth tables for (p→q)∧(q→p) and (p↔q).
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
The truth table for (p↔q) is:
p q p ↔q
T T T
T F F
F T F
F F T
Step 2: Compare the truth values of the two compound propositions in the
truth tables.
By comparing the truth tables, we see that the truth values of (p→q)∧(q→
p) and (p↔q) are the same for all possible truth values of pand q. Therefore,
we can conclude that (p→q)∧(q→p) is logically equivalent to (p↔q).
3
Question 6
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 logical
equivalence rules and logical inference rules.
Step 1: Apply the definition of implication Recall that a→bis
equivalent to ¬a∨b.
So, the given expression becomes: (¬p∨q)∧(¬q∨r)→(¬p∨r).
Step 2: Use the definition of implication in the disjunction By the
distribution property of ∧over ∨, we have: (¬p∧¬q)∨(¬p∧r)∨(q∧¬q)∨(q∧r)→
(¬p∨r).
Step 3: Simplify the expression using tautologies -¬p∧ ¬qsimplifies
to ¬(p∨q), which is always false. - q∧ ¬qis always false. - (¬p∧r)∨(q∧r)
simplifies to (¬p∨q)∧r.
So, (¬p∨r)→(¬p∨r).
Step 4: Use the principle of explosion Since p∨ ¬pis always true, the
expression simplifies to ⊤→⊤, which is a tautology.
Therefore, (p→q)∧(q→r)→(p→r) is a tautology.
Question 7
Question
Let p,q, and rbe propositional variables representing the statements ”It is
raining”, ”The streets are wet”, and ”The grass is wet”, respectively. Consider
the compound proposition:
[(p∧q)∨(¬p∧r)] →(q∨r).
Determine whether this compound proposition is a tautology, contradiction,
or contingency. Justify your answer.
Solution
Step 1: We will construct a truth table for the compound proposition to deter-
mine its logical value for all possible truth values of p,q, and r.
4
p q r (p∧q) (¬p∧r) [(p∧q)∨(¬p∧r)] (q∨r) [(p∧q)∨(¬p∧r)] →(q∨r)
T T T T F T T T
T T F T F T T T
T F T F T T T T
T F F F F F F T
F T T F F F T T
F T F F F F T T
F F T F T T T T
F F F F F F F T
Step 2: Analyzing the truth table, we see that the compound proposition
evaluates to true for all possible combinations of truth values of p,q, and r.
This means that the compound proposition is a tautology.
Hence, the compound proposition [(p∧q)∨(¬p∧r)] →(q∨r) is a tautology.
Question 8
Question
Let p,q, and rbe propositions. Determine whether the following argument is
valid: ”If p=⇒qand q=⇒r, then p=⇒r.”
Solution
To determine the validity of the argument, we can use the rules of propositional
logic to analyze the statements given.
Step 1: Write the given statements in symbolic form: - p=⇒q-q=⇒r
Step 2: Use the definition of implication to break down the statements: -
For p=⇒q:¬p∨q- For q=⇒r:¬q∨r
Step 3: Combine the two statements to form a conclusion: - We need to
check if (¬p∨q)∧(¬q∨r) logically implies ¬p∨r
Step 4: Apply the rule of transitivity to rewrite the conclusion: - ¬p∨r
Step 5: Now, check if ¬p∨rlogically follows from (¬p∨q)∧(¬q∨r) by
constructing a truth table:
p q r ¬p∨q¬q∨r(¬p∨q)∧(¬q∨r)¬p∨r
T T T T T T T
T T F T F F T
T F T F T F T
T F F F T F T
F T T T T T T
F T F T F F T
F F T T T T T
F F F T T T T
5
Step 6: From the truth table, we see that ¬p∨ris always true when
(¬p∨q)∧(¬q∨r) is true. Thus, the argument ”If p=⇒qand q=⇒r, then
p=⇒r” is valid.
Question 9
Question
Let pand qbe propositions. Show that the statement (p⇒q)∧(q⇒p) is
logically equivalent to (p∧q)∨(¬p∧ ¬q).
Solution
To show that the statement (p⇒q)∧(q⇒p) is logically equivalent to (p∧
q)∨(¬p∧ ¬q), we will construct truth tables for both statements and show that
they have the same truth values for all possible truth values of pand q.
Step 1: 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: 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 above, we can see that the statements (p⇒q)∧(q⇒p)
and (p∧q)∨(¬p∧ ¬q) have the same truth values for all possible truth values
of pand q. Therefore, they are logically equivalent.
6
Question 10
Question
Let p,q, and rbe propositional variables representing the following statements:
-p: The weather is rainy. - q: The roads are slippery. - r: There are accidents
on the roads.
Translate the following compound proposition into English: (p∧q)→r.
Solution
To translate the compound proposition (p∧q)→rinto English, we need to
consider the individual components and their logical connectives.
Step 1: Determine the meaning of each propositional variable: - p: The
weather is rainy. - q: The roads are slippery. - r: There are accidents on the
roads.
Step 2: Express the compound proposition in English: (p∧q)→rcan be
translated as ”If the weather is rainy and the roads are slippery, then there are
accidents on the roads.”
Therefore, the compound proposition (p∧q)→rcan be expressed in English
as ”If the weather is rainy and the roads are slippery, then there are accidents
on the roads.”
Question 11
Question
Let p,q, and rbe propositions. Use Propositional Logic to show that (p∧q)∨
(p∧r) is logically equivalent to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we need to
show that the truth values of the two propositions are always the same.
Step 1: Construct a truth table for both propositions.
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
7
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 of both propositions.
From the truth tables, we can see that the columns for (p∧q)∨(p∧r) and
p∧(q∨r) are identical. Therefore, (p∧q)∨(p∧r) is indeed logically equivalent
to p∧(q∨r).
Question 12
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 construct a
truth table and verify that the expression evaluates to true for all possible truth
values of p,q, and r.
Step 1: Construct the truth table for the given proposition.
p q r p ⇒q q ⇒r p ⇒r(p⇒q)∧(q⇒r)⇒(p⇒r)
T T T T T T T
T T F T F F T
T F T F T T T
T F F F T F T
F T T T T T T
F T F T F T T
F F T T T T T
F F F T T T T
Step 2: Analyze the truth table. In the last column of the truth table, we
can see that the proposition (p⇒q)∧(q⇒r)⇒(p⇒r) evaluates to true for
all possible truth values of p,q, and r. Therefore, (p⇒q)∧(q⇒r)⇒(p⇒r)
is a tautology.
8
Question 13
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using a truth table.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will construct a
truth table for all possible truth values of p,q, and r.
p q r p →q q →r(p→q)∧(q→r)p→r(p→q)∧(q→r)→(p→r)
T T T T T T T T
T T F T F F F T
T F T F T F T T
T F F F T F F T
F T T T T T T T
F T F T F F T T
F F T T T T T T
F F F T T T T T
Since the final column of the truth table is always true, we can conclude that
the proposition (p→q)∧(q→r)→(p→r) is a tautology.
Question 14
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 given statement, we can use a truth table to check all
possible truth values for p,q, and r. If the statement is always true, we can
prove it; otherwise, it is disproved.
9
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 last column of the truth table is always true, we can conclude that
the statement is true for all truth values of p,q, and r. Thus, we have proved
that (p→q)∧(q→r)→(p→r) is a valid statement in propositional logic.
Question 15
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we will construct
truth tables for both expressions and compare the results.
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
Step 2: Construct a truth table for p∧(q∨r).
10
p q r q ∨r p ∧(q∨r)
T T T T T
T T F T T
T F T T T
T F F F F
F T T T F
F T F T F
F F T T F
F F F F F
Step 3: Compare the truth tables.
From the truth tables, we can see that both expressions have the same
truth values for each combination of truth values of p,q, and r. Therefore,
(p∧q)∨(p∧r) is logically equivalent to p∧(q∨r).
Question 16
Question
Let p,q, and rbe propositions. Prove the logical equivalence (p∧q) =⇒r≡
(p=⇒r)∨(q=⇒r).
Solution
To prove the logical equivalence (p∧q) =⇒r≡(p=⇒r)∨(q=⇒r), we
will use a series of logical equivalences.
Step 1: Start by writing the definitions of the implications involved:
(p∧q) =⇒r≡ ¬(p∧q)∨r
(p=⇒r)∨(q=⇒r)
Step 2: Apply De Morgan’s Laws to the first expression:
¬(p∧q)∨r≡(¬p∨ ¬q)∨r
Step 3: Use the Distributive Law to expand the OR operator:
(¬p∨ ¬q)∨r≡(¬p∨r)∨(¬q∨r)
Step 4: Rearrange the terms:
(¬p∨r)∨(¬q∨r)≡(p=⇒r)∨(q=⇒r)
Therefore, we have shown that (p∧q) =⇒r≡(p=⇒r)∨(q=⇒r), as
desired.
11
Question 17
Question
Let p, q, and r be propositional variables. Given the statement:
(p→q)∧(q→r)→(p→r)
Determine whether the statement is a tautology, a contradiction, or neither.
Solution
Step 1: Use logical equivalences to simplify the given statement:
(p→q)∧(q→r)→(p→r)
(¬p∨q)∧(¬q∨r)→(¬p∨r)
(¬p∨q∨ ¬q∨r)→(¬p∨r)
(¬p∨r)→(¬p∨r)
¬(¬p∨r)∨(¬p∨r)
(p∧ ¬r)∨(¬p∨r)
(p∨ ¬p)∧(p∨r)∧(¬r∨ ¬p)∧(¬r∨r)
Step 2: Analyze the truth values of the compound statements:
p q r p ∨ ¬p p ∨r¬r∨ ¬p
¬r∨r
T T T T T F
T
T T F T T F
F
T F T T T F
T
T F F T T T
T
F T T T T F
T
F T F T T F
F
F F T T T F
T
F F F T F T
T
Step 3: Since there is a row in which the statement is false (the row where
pis true, qis false, and ris false), the statement is not a tautology.
Therefore, the statement is neither a tautology nor a contradiction.
12
Question 18
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we will
demonstrate the equivalence using a truth table.
p q r p ∧q p ∧r(p∧q)∨(p∧r)q∨r p ∧(q∨r)
T T T T T T T T
T T F T F T T T
T F T F T T T T
T F F F F F F F
F T T F F F T F
F T F F F F T F
F F T F F F T F
F F F F F F F F
As shown in the truth table, the columns for (p∧q)∨(p∧r) and p∧(q∨r)
are identical. Hence, the propositions (p∧q)∨(p∧r) and p∧(q∨r) are logically
equivalent.
Question 19
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 simplify
the proposition using logical equivalences until we reach a tautology (always
true statement).
Step 1: Apply the definition of the conditional statement to rewrite the
given expression as a conjunction:
(p→q)∧(q→r)→(p→r)≡ ¬[(p→q)∧(q→r)] ∨(p→r)
Step 2: Use De Morgan’s laws to simplify the negated conjunction:
¬[(p→q)∧(q→r)] ∨(p→r)≡[¬(p→q)∨ ¬(q→r)] ∨(p→r)
13
Step 3: Apply the definition of the conditional statement to the negations:
[¬(p→q)∨ ¬(q→r)] ∨(p→r)≡[(p∧ ¬q)∨(q∧ ¬r)] ∨(p→r)
Step 4: Distribute the disjunction over the conjunction:
(p∧ ¬q)∨(q∧ ¬r)∨(p→r)
Step 5: Use the distributive law again to simplify:
(p∧ ¬q)∨(q∧ ¬r)∨(p→r)≡(p∨q∨p→r)∧(¬q∨q∨p→r)∧(¬r∨q∨p→r)
Step 6: Apply the definition of the conditional statement to simplify the
disjunctions:
(p∨q∨p→r)∧(¬q∨q∨p→r)∧(¬r∨q∨p→r)≡(T∨T∨r)∧(¬q∨T∨r)∧(¬r∨q∨r)
Step 7: Further simplify the expression:
(T∨T∨r)∧(¬q∨T∨r)∧(¬r∨q∨r)≡T∧T∧T≡T
Since we have arrived at a tautology (always true statement), we can con-
clude that (p→q)∧(q→r)→(p→r) is a tautology.
Question 20
Question
Let p,q, and rbe propositional variables representing the following statements:
p: ”It is sunny.” q: ”It is warm.” r: ”It is a weekend.”
Express the following statement using propositional variables: ”It is not
sunny and warm on weekends.”
Solution
To express the given statement using propositional variables, we can break it
down into smaller parts: - It is not sunny: ¬p- It is warm: q- It is a weekend:
r
Now, we want to express ”It is not sunny and warm on weekends” using the
propositional variables p,q, and r.
The statement can be written as: ¬p∧q∧r.
Therefore, the expression for ”It is not sunny and warm on weekends” using
propositional variables is ¬p∧q∧r.
Question 21
Question
Let p,q, and rbe propositional variables. Show that the statement (p→
q)∧(q→r)→(p→r) is a tautology using truth tables.
14
Solution
To show that the statement (p→q)∧(q→r)→(p→r) is a tautology, we will
construct a truth table to evaluate all possible truth values of p,q, and r.
p q r p →q q →r p →r(p→q)∧(q→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 T F T
T F F F T F F T
F T T T T T T T
F T F T F T F T
F F T T T T T T
F F F T T T T T
Since the final column is all true values, we conclude that the statement
(p→q)∧(q→r)→(p→r) is a tautology.
Question 22
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r)⇔p∧(q∨r).
Solution
To show the equivalence (p∧q)∨(p∧r)⇔p∧(q∨r), we will prove both
directions separately.
Step 1: Show that (p∧q)∨(p∧r)⇒p∧(q∨r).
Assume that (p∧q)∨(p∧r) is true. We need to show that p∧(q∨r) is also
true.
From (p∧q)∨(p∧r), we can infer by distribution that p∧(q∨r).
Therefore, (p∧q)∨(p∧r)⇒p∧(q∨r).
Step 2: Show that p∧(q∨r)⇒(p∧q)∨(p∧r).
Assume that p∧(q∨r) is true. We need to show that (p∧q)∨(p∧r) is also
true.
From p∧(q∨r), we can infer by distribution that (p∧q)∨(p∧r).
Therefore, p∧(q∨r)⇒(p∧q)∨(p∧r).
Since we have shown both directions, we conclude that (p∧q)∨(p∧r)⇔
p∧(q∨r).
15
Question 23
Question
Let p,q, and rbe propositions. Prove the following logical equivalence: (p→
(q→r)) ≡((p∧q)→r).
Solution
To prove the logical equivalence (p→(q→r)) ≡((p∧q)→r), we will show
that both sides imply each other using logical equivalences and properties of
propositional logic.
Step 1: We will start by simplifying the left-hand side of the equivalence:
(p→(q→r)) ≡(¬p∨(q→r))
≡(¬p∨ ¬q∨r)
Step 2: Next, we will simplify the right-hand side of the equivalence:
((p∧q)→r)≡(¬(p∧q)∨r)
≡((¬p∨ ¬q)∨r)
≡(¬p∨ ¬q∨r)
Step 3: Since both sides simplify to the same expression, we have shown
that
(p→(q→r)) ≡((p∧q)→r).
Therefore, the logical equivalence is proven.
Question 24
Question
Let p,q, and rbe propositions. Determine whether the statement (p∨q)∧(¬p∨r)
is logically equivalent to q∨r.
Solution
To determine whether (p∨q)∧(¬p∨r) is logically equivalent to q∨r, we can
use truth tables.
Step 1: Create a Truth Table
We will create a truth table with columns for p,q,r, (p∨q), (¬p∨r), and
(p∨q)∧(¬p∨r), as well as a column for q∨r.
16
p q r p ∨q¬p∨r(p∨q)∧(¬p∨r)q∨r
T T T
T T F
T F T
T F F
F T T
F T F
F F T
FFF
Step 2: Fill in the Truth Table
Fill in the truth table by evaluating the propositions (p∨q), (¬p∨r), (p∨
q)∧(¬p∨r), and q∨rfor each combination of truth values of p,q, and r.
p q r p ∨q¬p∨r(p∨q)∧(¬p∨r)q∨r
T T T T T T T
T T F T F F T
T F T T T T T
T F F T T T F
F T T T T T T
F T F T T T T
F F T F T F T
F F F F T F F
Step 3: Conclusion
From the truth table, we can see that the statement (p∨q)∧(¬p∨r) is not
logically equivalent to q∨rsince the final columns have different truth values
for some rows.
Question 25
Question
Let p,q, and rbe propositional variables. Determine whether the following
statement is a tautology, a contradiction, or contingent:
(p∧q)→((p∨q)∧(¬p∨ ¬q)) →(p↔q)
Solution
To determine whether the given statement is a tautology, a contradiction, or
contingent, we can use truth tables.
Step 1: Construct truth table for the given statement
17
p q r p ∧q p ∨q¬p¬q¬p∨ ¬q p ↔qStatement
T T T T T F F F T T
T T F T T F F F T T
T F T F T F T T F T
T F F F T F T T F T
F T T F T T F T F T
F T F F T T F T F T
F F T F F T T T T T
F F F F F T T T T T
Step 2: Analyze the truth values of the statement
From the truth table, we can see that the statement is contingent because
it is neither a tautology (always true) nor a contradiction (always false).
Question 26
Question
Let p,q, and rbe propositions. Show whether the following argument is valid
or invalid using propositional calculus:
p→(q∧r)
(p∨q)→r
q
∴r
Solution
To determine the validity of the argument, we will construct a truth table.
p q r p →(q∧r) (p∨q)→r q p ∨q∴r
T T T T T T T T
T T F F F T T F
T F T T T F T T
T F F F F F T F
F T T T T T T T
F T F T F T T F
F F T T T F F T
F F F T T F F T
In the last column, ∴ris false when pis true, qis false, and ris true. Since
there is a row where all the premises are true but the conclusion is false, the
argument is invalid.
18
Question 27
Question
Let p,q,rbe propositions, where
p: ”It is raining.”
q: ”The grass is wet.”
r: ”The sun is shining.”
Express the following statement using propositions p,q, and r: ”If it is not
raining and the sun is shining, then the grass is not wet.”
Solution
To express the given statement using propositions p,q, and r, we need to con-
sider the logical connectives involved.
Step 1: Identify the components of the statement. Let’s break down
the original statement: ”If it is not raining and the sun is shining, then the grass
is not wet.” This can be represented as:
(¬p∧r)→ ¬q
Step 2: Explain the components. -¬prepresents ”It is not raining.” - r
represents ”The sun is shining.” - qrepresents ”The grass is wet.” - ∧represents
the logical operation AND. - →represents the logical operation IMPLIES.
Step 3: State the final representation. Therefore, the given statement
”If it is not raining and the sun is shining, then the grass is not wet” can be
expressed as:
(¬p∧r)→ ¬q
Question 28
Question
Let p,q, and rbe propositions. Show whether the following argument is valid
or invalid:
If pthen q.
If qthen r.
Therefore, if pthen r.
Solution
To determine the validity of the argument, we will use the rules of implication
in propositional logic.
19
Step 1: Write down the given premises and conclusion in symbolic form:
Given premises:
(p→q) Premise 1
(q→r) Premise 2
Desired conclusion:
(p→r)
Step 2: Apply the Transitivity of Implication: Since we are given p→q
and q→r, we can apply the transitivity of implication to derive p→r.
Step 3: Transitivity of Implication: If statement A implies statement B,
and statement B implies statement C, then statement A implies statement C.
Step 4: Apply the transitivity of implication to prove the validity of the
argument: From Premise 1: p→q
From Premise 2: q→r
Using the transitivity of implication, we have:
p→q→r
Simplifying this gives us:
p→r
Therefore, the argument is valid as we have successfully shown that if pthen
q, and if qthen r, then if pthen r.
Question 29
Question
Let p, q, and rbe propositions. Determine whether the argument below is valid:
If (p→q)∧(q→r), then (p→r)
Solution
To determine the validity of the argument, we need to check if the conclusion,
(p→r), follows from the premises, (p→q)∧(q→r).
Step 1: Let’s analyze the premises using the truth table method.
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
20
Step 2: From the truth table, we see that (p→q)∧(q→r) is not a tautology.
Specifically, when pis true, qis true, and ris false, the premises are true but
the conclusion is false.
Step 3: Since the premises do not guarantee the truth of the conclusion in
all cases, the argument is not valid.
Therefore, the argument ”If (p→q)∧(q→r), then (p→r)” is not valid.
Question 30
Question
Let p,q, and rbe propositions. Prove or disprove the following statement using
propositional logic: (p→q)∧(q→r)→(p→r).
Solution
To prove the statement (p→q)∧(q→r)→(p→r), we will evaluate the truth
values of each proposition in different scenarios.
Step 1: Construct a truth table
First, let’s construct a truth table for the given compound proposition.
p q r p →q q →r(p→q)∧(q→r)
p→r
T T T T T T
T
T T F T F F
F
T F T F T F
T
T F F F T F
F
F T T T T T
T
F T F T F F
T
F F T T T T
T
F F F T T T
T
Step 2: Analyze the truth values
From the truth table, we can see that the statement (p→q)∧(q→r)→
(p→r) is FALSE when pis true, qis true, and ris false.
Step 3: Conclusion
21
Therefore, we have shown that the statement (p→q)∧(q→r)→(p→r)
is not always true, as there exists a scenario where the statement is false. Thus,
the statement is disproved.
Question 31
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 (p→q)∧(q→r)→(p→r) is a tautology, we
need to show that its truth table only contains T (true) values.
p q r p →q q →r(p→q)∧(q→r)p→r(p→q)∧(q→r)→(p→r)
F F F T T T T T
F F T T T T T T
F T F T F F T T
F T T T T T T T
T F F F T F F T
T F T F T F T T
T T F T F F F T
T T T T T T T T
Since the final column of the truth table consists only of T (true) values, we
can conclude that the proposition (p→q)∧(q→r)→(p→r) is a tautology.
Question 32
Question
Given the following premises:
p→(q∨r)
¬r→s
s→ ¬p
Prove that ¬qholds true.
22
Solution
Step 1: Assume ¬qis false, i.e., qis true.
Using the premise p→(q∨r) :
If pis true, then qor ris true.
Since qis true, rmust be false to satisfy p→(q∨r).
Step 2: Consider ¬r→sand ¬q≡ ¬(q∨r).
From ¬r→sand ¬q≡ ¬(q∨r),
Since ris false, qcannot be true since ¬qholds true.
So, ¬qmust be true.
Step 3: Conclusion
Therefore, based on our assumption that qis true, we have reached a contradiction.
Thus, our initial assumption was incorrect, and ¬qmust be true.
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
use a truth table to verify that they have the same truth values for all possible
truth values of p,q, and r.
p q r p ∧q(p∧q)→r p →r q →r
T T T T T T T
T T F T F F F
T F T F T T T
T F F F T F T
F T T F T T T
F T F F T T F
F F T F T T T
F F F F T T T
From the truth table, we see that for all possible truth values of p,q, and r,
(p∧q)→rand (p→r)∨(q→r) have the same truth values. Therefore, we
have shown that (p∧q)→ris logically equivalent to (p→r)∨(q→r).
23
Question 34
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 demonstrate that the compound proposition is true for all possible truth
values of p,q, and r.
Step 1: Create the Truth Table
p q r p →q q →r p →r(p→q)∧(q→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 T F T
T F F F T F F T
F T T T T T T T
F T F T F T F T
F F T T T T T T
F F F T T T T T
Step 2: Analyze the Truth Table
From the truth table, we see that the final column is true for all possible
truth values of p,q, and r. Thus, (p→q)∧(q→r)→(p→r) is a tautology.
Question 35
Question
Let p,q, and rbe propositional variables. Determine whether the following
statement is a tautology, a contradiction, or neither:
(p→q)∧(q→r)∧(r→p)
Justify your answer.
Solution
To determine whether the given statement is a tautology, we will construct a
truth table to evaluate all possible truth values of p,q, and r.
Step 1: Create a truth table to evaluate the truth values of (p→q), (q→r),
(r→p), and the given statement (p→q)∧(q→r)∧(r→p).
24
p q r p →q q →r r →p(p→q)∧(q→r)∧(r→p)
T T T T T T T
T T F T F T F
T F T F T T F
T F F F T T F
F T T T T F F
F T F T F T F
F F T T T T T
F F F T T T T
Step 2: Analyze the truth table to determine the nature of the given state-
ment.
From the truth table, we can see that the given statement (p→q)∧(q→
r)∧(r→p) is only true when all of the propositional variables p,q, and rare
false. In all other cases, the statement is false.
Step 3: Conclusion
Since the given statement is only true in one case (when all propositional
variables are false) and false in all other cases, it is neither a tautology (always
true) nor a contradiction (always false).
25
