MATH 250 - INTRODUCTION TO
DISCRETE MATHEMATICS - Logic
and Propositional Calculus
Question Bank - Set 4
Liberty University
Question 1
Question
Let p,q, and rbe propositions such that:
(p∧q)∨(¬p∧r)→(p∧ ¬r)
Write the negation of the proposition above using De Morgan’s laws.
Solution
To find the negation of the given proposition, we will first apply De Morgan’s
laws to simplify the original proposition.
Step 1: Apply De Morgan’s Law
Using De Morgan’s law: ¬(A∧B)≡ ¬A∨ ¬Band ¬(A∨B)≡ ¬A∧ ¬B, we
rewrite the original proposition as:
¬((p∧q)∨(¬p∧r)) ∨(p∧ ¬r)
Step 2: Distribute the Negation
Distributing the negation inside the brackets:
(¬(p∧q)∧ ¬(¬p∧r)) ∨(p∧ ¬r)
Step 3: Apply De Morgan’s Law Again
Applying De Morgan’s law to the remaining negations:
((¬p∨ ¬q)∧(p∨ ¬r)) ∨(p∧ ¬r)
Step 4: Simplify the Expression
Simplifying further, we get:
(¬p∨ ¬q∧p∨ ¬r)∨(p∧ ¬r)
Step 5: Apply Distribution of ∨over ∧
Applying the distribution of ∨over ∧:
(¬p∨(¬q∧p)∨ ¬r)∨(p∧ ¬r)
Step 6: Apply Associative Property of ∨
Rearranging the terms using the associative property of ∨to make it clear for
the negation:
(¬p∨p∧ ¬q∨ ¬r)∨(p∧ ¬r)
Step 7: Negate the Entire Proposition
Finally, we negate the entire expression:
¬((¬p∨p∧ ¬q∨ ¬r)∨(p∧ ¬r))
Therefore, the negation of the original proposition using De Morgan’s laws
is:
(¬p∧p∧ ¬q∧r)∧(¬p∨ ¬¬r)
Question 2
Question
Let pand qbe propositional variables. Show that ¬(p∧q)≡(¬p∨ ¬q) using
logical equivalences.
Solution
To show that ¬(p∧q)≡(¬p∨¬q), we will use the laws of logic and propositional
calculus to manipulate the expressions on both sides of the equivalence.
Step 1: Apply De Morgan’s Law to the left side of the equivalence,
¬(p∧q) = ¬p∨ ¬q.
Therefore, ¬(p∧q)≡(¬p∨ ¬q) by De Morgan’s Law.
Thus, we have shown that ¬(p∧q)≡(¬p∨ ¬q).
Question 3
Question
Let p,q, and rbe propositions. Show that the statement (p→q)∧(r→ ¬q)→
(p∧r)→ ¬qis a tautology.
2
Solution
To show that the given statement is a tautology, we will use a truth table to
verify that the statement is true for all possible truth values of p,q, and r.
p q r p →q r → ¬q(p→q)∧(r→ ¬q) (p∧r)¬q
[(p→q)∧(r→ ¬q)] →[(p∧r)→ ¬q]
T T T T F F T F
T
T T F T F F F F
T
T F T F T F T T
T
T F F F T F F T
T
F T T T F F F F
T
F T F T F F F F
T
F F T T T T F T
T
F F F T T T F T
T
Since the final column contains all True values, we can conclude that the
statement (p→q)∧(r→ ¬q)→(p∧r)→ ¬qis a tautology.
Question 4
Question
Let prepresent the statement ”It is raining” and qrepresent the statement ”I
am indoors.” Convert the following statement into symbolic form: ”It is not
raining and I am indoors.”
Solution
To convert the statement ”It is not raining and I am indoors” into symbolic
form, we will use logical connectives.
Step 1: Identify the statements and their corresponding symbols: Let p
represent ”It is raining” and qrepresent ”I am indoors.”
Step 2: Express the given statement using logical connectives: The given
statement ”It is not raining and I am indoors” can be represented as the con-
junction of the negation of pand q, which can be written as ¬p∧q.
Step 3: Write the symbolic form of the statement: Therefore, the symbolic
form of the statement ”It is not raining and I am indoors” is ¬p∧q.
3
Question 5
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 given proposition is a tautology, we can use the laws of logic
and reasoning to simplify and ultimately prove its validity.
Step 1: Apply the definition of implication for the compound propositions.
(p→q)∧(q→r)→(p→r)≡(¬p∨q)∧(¬q∨r)→(¬p∨r)
Step 2: Use the definition of implication to write the compound statement
in disjunctive normal form (DNF).
(¬(¬p∨q)∨ ¬(¬q∨r)) ∨(¬p∨r)≡(p∧ ¬q)∨(q∧r)∨(¬p∨r)
Step 3: Construct a truth table to determine when the compound statement
is true.
p q r (p∧ ¬q) (q∧r) (¬p∨r) (p∧ ¬q)∨(q∧r)∨(¬p∨r)
T T T F T T T
T T F F F T T
T F T T F T T
T F F T F T T
F T T F T T T
F T F F F T T
F F T F F T T
F F F F F T T
Since the last column of the truth table consists only of T (true), we conclude
that the original proposition (p→q)∧(q→r)→(p→r) is a tautology.
Question 6
Question
Let p,q, and rbe propositions. Show that the following two statements are
logically equivalent:
(p∧q)∨rand (p∨r)∧(q∨r)
4
Solution
To show that the two statements are logically equivalent, we will first use logical
equivalences to simplify both statements and then show that they are the same.
Step 1: Simplify (p∧q)∨r
(p∧q)∨r≡(p∨r)∧(q∨r) Distributive Law
Therefore, (p∧q)∨rsimplifies to (p∨r)∧(q∨r).
Since we have shown that both statements simplify to the same expression,
we can conclude that (p∧q)∨ris logically equivalent to (p∨r)∧(q∨r).
Question 7
Question
Let p,q, and rbe propositions. Show that the proposition (p→q)→[(q→
r)→(p→r)] is a tautology using a truth table.
Solution
To show that (p→q)→[(q→r)→(p→r)] is a tautology, we will construct
a truth table and show that the proposition is true for all possible truth values
of p,q, and r.
p q r p →q q →r(p→q)→(q→r)p→r[(p→q)→(q→r)] →(p→r)
T T T T T T T T
T T F T F F F T
T F T F T T T T
T F F F T T 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
From the truth table, we can see that the final column evaluating (p→q)→
[(q→r)→(p→r)] is always true regardless of the truth values of p,q, and r.
Therefore, the proposition is a tautology.
Question 8
Question
Let p,q, and rbe propositional variables. Given the compound proposition
(p∧q)→r, show that this proposition is logically equivalent to ¬p∨ ¬q∨r
using logical equivalences.
5
Solution
To show that (p∧q)→ris logically equivalent to ¬p∨ ¬q∨r, we will use logical
equivalences to simplify and manipulate the expressions.
Step 1: Use the definition of the conditional (→):
(p∧q)→r≡ ¬(p∧q)∨r
≡(¬p∨ ¬q)∨r
≡ ¬p∨ ¬q∨r
Therefore, (p∧q)→ris logically equivalent to ¬p∨ ¬q∨r.
Question 9
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using propositional calculus laws and truth tables.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will construct a
truth table to demonstrate that the compound proposition is always true.
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)
T T T T T T T
T T F T F F F
T F T F T F T
T F F F T F F
F T T T T T T
F T F T F F T
F F T T T T T
F F F T T T T
Step 2: Analyze the truth table
The truth table shows that the column for (p→q)∧(q→r)→(p→r) is
always true (T) for all possible truth values of p,q, and r. Therefore, we can
conclude that (p→q)∧(q→r)→(p→r) is a tautology.
Question 10
Question
Let pand qbe propositional variables. Determine whether the following argu-
ment is valid or not:
(p→q)∧(q→p)→(p∧q)
6
Solution
To determine the validity of the given argument, we can use the method of truth
tables.
Step 1: Construct the truth table for the argument.
p q (p→q) (q→p) (p→q)∧(q→p)p∧q(p→q)∧(q→p)→(p∧q)
T T T T T T T
T F F T F F T
F T T F F F T
F F T T T F F
Step 2: Analyze the truth values in the last column. The truth
values in the last column indicate that the argument is not valid. In the last
row, when pis false and qis false, the premise is true but the conclusion is false.
This means that it is possible for the premise to be true while the conclusion is
false. Hence, the argument is not valid.
Question 11
Question
Let p,q, and rbe propositional variables. Show that (p→q)↔[(p∧q)∨(¬p∧
¬q)] is a tautology.
Solution
To show that the given statement is a tautology, we will use a truth table to
evaluate all possible truth values for p,q,r, and the entire statement.
p q (p→q) (p∧q) (¬p) (¬q) [(p∧q)∨(¬p∧ ¬q)] (p→q)↔[(p∧q)∨(¬p∧ ¬q)]
T T T T F F T T
T F F F F T T T
F T T F T F T T
F F T F T T T T
Since the final column is all true values, we have shown that the given
statement is a tautology.
Question 12
Question
Let p,q, and rbe propositions. Show that the proposition (p→q)→(q→
r)→(p→r) is a tautology using propositional logic laws.
7
Solution
To show that the proposition is a tautology, we will use logical equivalences to
simplify the expression step by step.
Step 1: Use the material implication law: a→b≡ ¬a∨b
¬[(p→q)→(q→r)] ∨(p→r)
Step 2: Apply material implication law again and simplify using De Mor-
gan’s law: ¬(a→b)≡a∧ ¬b
[(p∧ ¬q)∨(q∧ ¬r)] ∨(p→r)
Step 3: Use the distributive law: a∨(b∧c)≡(a∨b)∧(a∨c)
((p∧ ¬q)∨p)∧((p∧ ¬q)∨ ¬r)
Step 4: Simplify each part of the expression:
(p∨(p∧ ¬q)) ∧(p∨(¬r∧p))
(p∨p)∧(p∨ ¬r)
p∧(p∨ ¬r)
p
Since pis a proposition, and the expression reduces to p, we have shown that
(p→q)→(q→r)→(p→r) is a tautology.
Question 13
Question
Let p,q, and rbe propositional variables with the following premises: 1. ¬p→
(q∨r) 2. q→r3. ¬rDetermine whether the conclusion ¬qcan be inferred
from the premises.
Solution
1. We begin by assuming the premises are true and aim to show whether ¬q
can be logically deduced. 2. From premise 3, ¬r, we can deduce r→ ⊥, where
⊥represents a contradiction. 3. According to premise 2, if qis true, then ris
true. Combining this with r→ ⊥, we have q→ ⊥. 4. Rewriting q→ ⊥ as ¬q,
we obtain our conclusion: ¬q. 5. Therefore, the conclusion ¬qcan be logically
deduced from the premises provided.
8
Question 14
Question
Let pand qbe propositions. Show that (p→q)→(¬q→ ¬p) is a tautology
using truth tables.
Solution
To show that (p→q)→(¬q→ ¬p) is a tautology, we will construct a truth
table and verify that the output column is always true.
p q ¬p¬q p →q¬q→ ¬p(p→q)→(¬q→ ¬p)
T T F F T T T
T F F T F F T
F T T F T T T
F F T T T T T
Therefore, the final column of the truth table is always true, indicating that
the statement (p→q)→(¬q→ ¬p) is a tautology.
Question 15
Question
Let p,q, and rbe propositional variables. Show that the statement (p∧q)∨
[(p∧r)→(q∧r)] is a tautology.
Solution
To show that the given statement is a tautology, we will use a truth table to
demonstrate that the statement is true for all possible truth values of p,q, and
r.
p q r (p∧q) (p∧r) (q∧r) (p∧r)→(q∧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 F F T
F T T F F T T
F T F F F F T
F F T F F F T
F F F F F F T
Since the final column is always true (T), the statement (p∧q)∨[(p∧r)→
(q∧r)] is a tautology.
9
Question 16
Question
Let p,q, and rbe propositions. Show that the statement ¬((p→q)∧(q→
r)) ↔(p∧ ¬r) is a tautology using propositional logic laws and truth tables.
Solution
To show that the given statement is a tautology, we need to show that the
statement is true for all possible truth values of p,q, and r. We can do this by
constructing a truth table for the statement.
p q r p →q q →r(p→q)∧(q→r)¬((p→q)∧(q→r)) p∧ ¬r
T T T T T T F F
T T F T F F T T
T F T F T F T F
T F F F T F T T
F T T T T T F F
F T F T F F T T
F F T T T T F F
F F F T T T F F
As shown in the truth table, the statement ¬((p→q)∧(q→r)) ↔(p∧ ¬r)
is always true regardless of the truth values of p,q, and r. Therefore, the
statement is a tautology.
Question 17
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we will construct
truth tables for both expressions and show that they have the same truth values
for all possible truth values of p,q, and r.
Step 1: Construct the truth table for (p∧q)∨(p∧r).
10
p q r p ∧q p ∧r(p∧q)∨(p∧r)
T T T T T T
T T F T F T
T F T F T T
T F F F F F
F T T F F F
F T F F F F
F F T F F F
F F F F F F
Step 2: Construct the truth table for p∧(q∨r).
p q r q ∨r p ∧(q∨r)
T T T T T
T T F T T
T F T T T
T F F F F
F T T T F
F T F T F
F F T T F
F F F F F
Step 3: Conclusion
Comparing the truth tables for (p∧q)∨(p∧r) and p∧(q∨r), we see that
the two expressions have the same truth values for all possible truth values of
p,q, and r. Therefore, (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r).
Question 18
Question
Let p,q, and rbe propositional variables. Determine whether the following
argument is valid:
((p→q)∧(q→r)) →(p→r)
Solution
To determine the validity of the argument, we will use the method of proof
by contradiction. We will assume that the argument is invalid and derive a
contradiction.
Step 1: Assume that the argument is invalid, so the premise ((p→q)∧(q→
r)) is true while the conclusion (p→r) is false.
Step 2: From the premise, we know that both (p→q) and (q→r) are
true. This means that if pis true, then qis true, and if qis true, then ris true.
Step 3: Since (p→q) is true, we have two cases:
11
Case 1: pis true and qis true.
Case 2: pis false.
Step 4: In Case 1, we have qis true. Since (q→r) is also true, this implies
ris true. Therefore, in this case, pimplies r.
Step 5: In Case 2, pis false, and the implication (p→r) is vacuously true.
This contradicts our assumption that (p→r) is false.
Step 6: Since assuming the argument is invalid led to a contradiction, the
argument is indeed valid.
Therefore, ((p→q)∧(q→r)) →(p→r) is a valid argument.
Question 19
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using logical equivalence laws.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will manipulate
the expression using logical equivalence laws until we reach a known tautology
form (e.g., p∨ ¬p).
Step 1: Apply the definition of the conditional
(p→q)∧(q→r)→(p→r)
≡(¬p∨q)∧(¬q∨r)→(¬p∨r)
Step 2: Apply the definition of implication
≡ ¬[(¬p∨q)∧(¬q∨r)] ∨(¬p∨r)
≡ ¬[¬(¬p∨q)∨ ¬(¬q∨r)] ∨(¬p∨r)
≡ ¬[(p∧ ¬q)∨(q∧ ¬r)] ∨(¬p∨r)
Step 3: De Morgan’s Law
≡ ¬(p∧ ¬q)∧ ¬(q∧ ¬r)∨(¬p∨r)
≡(¬p∨q)∧(¬q∨r)∨(¬p∨r)
Step 4: Apply distribution
≡[¬p∨q∨(¬p∨r)] ∧[¬p∨r∨(¬q∨r)]
≡ ¬p∨q∨r∧ ¬p∨r∨ ¬q∨r
12
Step 5: Apply associativity and commutativity
≡(¬p∨ ¬p∨r∨q)∧(¬p∨ ¬q∨r∨r)
≡(¬p∨r∨q)∧(¬p∨ ¬q∨r)
Step 6: Apply absorption
≡ ¬p∨r∨q
≡ ¬p∨q∨r
≡p→r
Therefore, (p→q)∧(q→r)→(p→r) is a tautology.
Question 20
Question
Let p,q, and rbe propositional variables. Show that the following statement is
a tautology:
(p→(q→r)) →((p→q)→(p→r))
Solution
To show that the statement is a tautology, we’ll use a truth table to evaluate
all possible truth values of p,q, and r.
Step 1: Create the truth table.
p q r q →r p →(q→r)p→q p →r(p→q)→(p→r)
T T T T T T T T
T T F F F T F T
T F T T T F T T
T F F T T F F T
F T T T T T T T
F T F F T T T T
F F T T T T T T
F F F T T T T T
Since the final column is always true, the original statement is a tautology.
Question 21
Question
Let p, q, and rbe statements. Determine whether the following argument is
logically valid:
(p→q)∧(q→r)→(p→r)
13
Solution
To determine whether the given argument is logically valid, we will systemati-
cally analyze the truth values of the statements involved.
Step 1: Construct a truth table for (p→q)∧(q→r)→(p→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
Step 2: Analyze the truth values of the statement (p→q)∧(q→r)→
(p→r).
From the truth table, we see that there are cases where the statement (p→
q)∧(q→r)→(p→r) is false. Therefore, the given argument is not logically
valid since there are cases where the conclusion does not necessarily follow from
the premises.
Question 22
Question
Let p,q, and rbe propositions such that (p→q)∧(q→r)∧(r→p). Determine
whether the propositions p,q, and rare all true, all false, or some combination
of true and false.
Solution
Given: (p→q)∧(q→r)∧(r→p)
Step 1: Consider the truth value possibilities for p,q, and r.
Let’s construct a truth table for the given propositions:
14
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 F F
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 only combination of truth values
for p,q, and rthat satisfies (p→q)∧(q→r)∧(r→p) is when p=False,q=
False, and r=True.
Therefore, the propositions p,q, and rare in the combination of False,
False,True.
Question 23
Question
Let p, q, r be propositions. Use only the logical connectives ∧(AND), ∨(OR),
and ¬(NOT) to simplify the following compound proposition:
(p∧q)∨(p∧ ¬q)∨(¬p∧q)∨(¬p∧ ¬q)∨r
Solution
To simplify the compound proposition, we can use several logical equivalences
and properties.
Step 1: Distributive Law
p∧q=p∧(q∨ ¬q) = (p∧q)∨(p∧ ¬q)
Similarly, we can express ¬p∧qas the disjunction of its components:
¬p∧q= (¬p∧q)∨(¬p∧ ¬q)
Step 2: Combining Like Terms Applying Step 1, we can rewrite the
given compound proposition:
(p∧q)∨(p∧ ¬q)∨(¬p∧q)∨(¬p∧ ¬q)∨r
= (p∧q)∨(¬p∧q)∨(p∧ ¬q)∨(¬p∧ ¬q)∨r
Now, we can combine like terms:
(p∧q)∨(¬p∧q)∨(p∧ ¬q)∨(¬p∧ ¬q) = p∨ ¬p
15
We also have p∨ ¬p= True by the Law of Excluded Middle.
Step 3: Final Simplification Therefore, the compound proposition sim-
plifies to:
True ∨r= True
So, the simplified form of the given compound proposition is True .
Question 24
Question
Let p,q, and rbe propositional variables. Prove that (p⇒q)∧(q⇒r)⇒(p⇒
r) using propositional calculus laws.
Solution
To prove (p⇒q)∧(q⇒r)⇒(p⇒r), we need to show that the proposition is
a tautology. We can use propositional calculus laws to derive its truth.
Step 1: Write the given proposition in terms of basic connectives:
(p⇒q)∧(q⇒r)⇒(p⇒r)
Step 2: Apply the definition of the implication to rewrite the proposition:
(¬p∨q)∧(¬q∨r)⇒(¬p∨r)
Step 3: Use the distributive law to expand the expression:
¬p∨q⇒(¬q∨r)∧ ¬p∨r
Step 4: Apply the definition of the implication again to get:
¬(¬p∨q)∨(¬q∨r)∧ ¬p∨r
Step 5: Use De Morgan’s laws to simplify the expression:
(p∧ ¬q)∨(¬q∨r)∧ ¬p∨r
Step 6: Distribute the disjunction over the conjunction:
(p∧ ¬q∨ ¬q)∨(p∧ ¬q∨r)∧ ¬p∨r
Step 7: Simplify the intermediate steps further:
(p∨ ¬q)∨(p∧ ¬q∨r)∧ ¬p∨r
Step 8: Apply the absorption law to simplify the expression:
p∨ ¬q∨ ¬p∨r
Step 9: Apply the law of excluded middle to simplify the expression further:
True
Since we have obtained a tautology True, we can conclude that (p⇒q)∧(q⇒
r)⇒(p⇒r) is a valid proposition.
16
Question 25
Question
Let prepresent the statement ”It is raining” and qrepresent the statement ”It
is cloudy.” Write the statement ”If it is not raining or it is cloudy, then it is not
both raining and cloudy” using pand q, and then determine its truth value.
Solution
1. Let prepresent the statement ”It is raining” and qrepresent the statement
”It is cloudy.” The given statement can be written as:
(¬p∨q)→ ¬(p∧q)
2. We can create a truth table to determine the truth value of this statement:
p q ¬p¬(p∧q)¬p∨q(¬p∨q)→ ¬(p∧q)
T T F F T T
T F F T F T
F T T T T T
F F T T T T
3. From the truth table, we can see that the statement ”If it is not raining
or it is cloudy, then it is not both raining and cloudy” is true for all possible
truth values of pand q.
Question 26
Question
Let p,q, and rbe propositions. Use truth tables to determine whether the
following argument is valid: ”If pthen q, and if qthen r, therefore if pthen r.”
Solution
To determine the validity of the argument, we need to construct truth tables
for the propositions p,q,r, and the implications involved.
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 T T
T F F F T T 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
17
The truth table shows that the argument is not valid because there is a row
where the premise is true (all columns before the arrow) and the conclusion
(last column) is false. Specifically, when pis true, qis false, and ris true, the
conclusion is false even though both premises are true. Therefore, the argument
”If pthen q, and if qthen r, therefore if pthen r” is not valid.
Question 27
Question
Let p,q, and rbe propositional variables. 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 will use logical
equivalences to simplify the expression.
Step 1: Apply distribution and associative properties
(p∨q)∧(q∨r)→(p∨r)
≡ ¬((p∨q)∧(q∨r)) ∨(p∨r) Definition of implication
≡(¬(p∨q)∨ ¬(q∨r)) ∨(p∨r) De Morgan’s laws
≡((¬p∧ ¬q)∨(¬q∧ ¬r)) ∨(p∨r) De Morgan’s laws
≡((¬p∧ ¬q)∨(¬q∧ ¬r)) ∨(p∨r) Commutative properties of ∨and ∧
≡((¬p∨ ¬q)∧(¬p∨ ¬r)) ∨(p∨r) Distribution
≡(¬p∨ ¬q∨(p∨r)) ∧(¬p∨ ¬r∨(p∨r)) Distribution
≡(¬p∨ ¬q∨p∨r)∧(¬p∨ ¬r∨p∨r) Commutative properties of ∨
≡(T∨r)∧(T∨r) Negation law
≡T∧TDomination law
≡TIdentity law (T represents True)
Therefore, (p∨q)∧(q∨r)→(p∨r) is a tautology.
Question 28
Question
Let p, q, r be statements such that p→(q∧r) is true. Determine whether the
statement ¬p∨ ¬q∨ ¬ris true or false.
Solution
Step 1: We are given that p→(q∧r) is true. We will use the truth table
method to determine the truth value of ¬p∨ ¬q∨ ¬r.
18
Step 2: Let’s construct the truth table for p→(q∧r):
p q r q ∧r p →(q∧r)
T T T T T
T T F F F
T F T F F
T F F F F
F T T T T
F T F F T
F F T F T
F F F F T
Step 3: Since p→(q∧r) is true in only the rows where the premise is false
or the conclusion is true, we see that it is true in the last three rows of the truth
table.
Step 4: Now, let’s analyze the statement ¬p∨ ¬q∨ ¬r. We will negate each
statement and then take the disjunction.
¬p:{TTFFFFFF}
¬q:{TTTTFFFF}
¬r:{TTTTTFTF}
Step 5: Now, we will calculate the disjunction of ¬p, ¬q, ¬r:
¬p¬q¬r¬p∨ ¬q∨ ¬r
F F F F
F F T T
F T F T
F T T T
T F F T
T F T T
T T F T
T T T T
Step 6: Therefore, the statement ¬p∨ ¬q∨ ¬ris true in all cases except
when p=T,q=F, and r=F.
Question 29
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology.
19
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will use a truth
table to verify that the compound proposition is true for all possible truth values
of p,q, and r.
p q r p →q q →r p →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 of the truth table is always true, we conclude that
(p→q)∧(q→r)→(p→r) is a tautology.
Question 30
Question
Let p,q, and rbe propositions. Prove or disprove the following statement: If
(p→(q→r)) ∧ ¬r, then (p∧ ¬q).
Solution
To prove or disprove the statement, we will construct a truth table for the given
propositions and analyze the truth values.
p q r (q→r) (p→(q→r)) ¬r(p→(q→r)) ∧ ¬r p ∧ ¬q
T T T T T F F F
T T F F F T F F
T F T T T F F F
T F F T T T T T
F T T T T F F F
F T F F T T F F
F F T T T F F F
F F F T T T T F
From the truth table, we can see that there is a row where (p→(q→r))∧¬r
is true but p∧ ¬qis false. Therefore, the statement ”If (p→(q→r)) ∧ ¬r, then
(p∧ ¬q)” is disproved.
20
Question 31
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using truth tables.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will construct a
truth table for these propositions.
Step 1: Construct a truth table for (p→q)∧(q→r)→(p→r).
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 2: Evaluate the truth values for (p→q)∧(q→r)→(p→r).
In the truth table, we see that the final column is always true (T). Thus,
(p→q)∧(q→r)→(p→r) is a tautology, as the expression is true for all
possible truth values of p,q, and r.
Question 32
Question
Let p,q, and rbe propositions. Show whether the following argument is valid
or invalid using propositional calculus:
”If pimplies q, and qimplies r, then pimplies r.”
Solution
To determine the validity of the argument, we will use the rules of propositional
calculus to analyze the given propositions.
Step 1: Express the given argument in propositional logic. Let’s denote: -
prepresents the proposition ”It is raining.” - qrepresents the proposition ”The
ground is wet.” - rrepresents the proposition ”The flowers are blooming.”
The argument can be represented as: If p→qand q→r, then p→r.
Step 2: Verify the logical implication p→rassuming p→qand q→rare
true.
The statement p→rcan be verified using the following truth tables:
21
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
Since the truth table shows that p→ris not always true when p→qand
q→rare true simultaneously, the argument is not valid.
Question 33
Question
Let p,q, and rbe propositions. Consider the logical expression (p∧q)→r.
Determine whether the expression is a tautology, a contradiction, or neither.
Solution
To determine whether the logical expression (p∧q)→ris a tautology, a contra-
diction, or neither, we will construct a truth table for all possible truth values
of p,q, and 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
22
Since there is at least one row in the truth table where the logical expression
(p∧q)→revaluates to false, the expression is not a tautology. Also, since
there is at least one row where the expression evaluates to true, the expression
is not a contradiction. Therefore, the logical expression (p∧q)→ris neither a
tautology nor a contradiction.
Question 34
Question
Given the following premises: P→(Q∨R)
Q→S
R→T
T→U
¬U
Prove that ¬P.
Solution
1. We will prove the conclusion ¬Pby assuming the opposite, P, and deriving
a contradiction.
2. Assume Pis true.
3. From the first premise P→(Q∨R) and our assumption P, we can
conclude Q∨Rby modus ponens.
4. From Q∨Rand the second premise Q→S, we have two cases:
Case 1: Qis true.
Case 2: Ris true.
5. In case 1 (Qis true), we have Sby modus ponens with the second premise.
6. From case 2 (Ris true) and the third premise R→T, we have Tby
modus ponens.
7. From Tand the fourth premise T→U, we have Uby modus ponens.
8. However, we also have ¬Uas given in the premises, which leads to a
contradiction.
9. This contradiction arises from assuming Pto be true.
10. Therefore, our assumption that Pis true must be false, leading to the
conclusion that ¬Pis true.
Question 35
Question
Let p,q, and rbe propositional variables. Show that the following statement is
a tautology:
[(p→q)∧(q→r)] →(p→r)
23
Step 4: Simplify the Expression
Simplifying further, we get:
(¬p∨ ¬q∧p∨ ¬r)∨(p∧ ¬r)
Step 5: Apply Distribution of ∨over ∧
Applying the distribution of ∨over ∧:
(¬p∨(¬q∧p)∨ ¬r)∨(p∧ ¬r)
Step 6: Apply Associative Property of ∨
Rearranging the terms using the associative property of ∨to make it clear for
the negation:
(¬p∨p∧ ¬q∨ ¬r)∨(p∧ ¬r)
Step 7: Negate the Entire Proposition
Finally, we negate the entire expression:
¬((¬p∨p∧ ¬q∨ ¬r)∨(p∧ ¬r))
Therefore, the negation of the original proposition using De Morgan’s laws
is:
(¬p∧p∧ ¬q∧r)∧(¬p∨ ¬¬r)
Question 2
Question
Let pand qbe propositional variables. Show that ¬(p∧q)≡(¬p∨ ¬q) using
logical equivalences.
Solution
To show that ¬(p∧q)≡(¬p∨¬q), we will use the laws of logic and propositional
calculus to manipulate the expressions on both sides of the equivalence.
Step 1: Apply De Morgan’s Law to the left side of the equivalence,
¬(p∧q) = ¬p∨ ¬q.
Therefore, ¬(p∧q)≡(¬p∨ ¬q) by De Morgan’s Law.
Thus, we have shown that ¬(p∧q)≡(¬p∨ ¬q).
Question 3
Question
Let p,q, and rbe propositions. Show that the statement (p→q)∧(r→ ¬q)→
(p∧r)→ ¬qis a tautology.
2
Solution
To show that the given statement is a tautology, we will use a truth table to
verify that the statement is true for all possible truth values of p,q, and r.
p q r p →q r → ¬q(p→q)∧(r→ ¬q) (p∧r)¬q
[(p→q)∧(r→ ¬q)] →[(p∧r)→ ¬q]
T T T T F F T F
T
T T F T F F F F
T
T F T F T F T T
T
T F F F T F F T
T
F T T T F F F F
T
F T F T F F F F
T
F F T T T T F T
T
F F F T T T F T
T
Since the final column contains all True values, we can conclude that the
statement (p→q)∧(r→ ¬q)→(p∧r)→ ¬qis a tautology.
Question 4
Question
Let prepresent the statement ”It is raining” and qrepresent the statement ”I
am indoors.” Convert the following statement into symbolic form: ”It is not
raining and I am indoors.”
Solution
To convert the statement ”It is not raining and I am indoors” into symbolic
form, we will use logical connectives.
Step 1: Identify the statements and their corresponding symbols: Let p
represent ”It is raining” and qrepresent ”I am indoors.”
Step 2: Express the given statement using logical connectives: The given
statement ”It is not raining and I am indoors” can be represented as the con-
junction of the negation of pand q, which can be written as ¬p∧q.
Step 3: Write the symbolic form of the statement: Therefore, the symbolic
form of the statement ”It is not raining and I am indoors” is ¬p∧q.
3
Question 5
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 given proposition is a tautology, we can use the laws of logic
and reasoning to simplify and ultimately prove its validity.
Step 1: Apply the definition of implication for the compound propositions.
(p→q)∧(q→r)→(p→r)≡(¬p∨q)∧(¬q∨r)→(¬p∨r)
Step 2: Use the definition of implication to write the compound statement
in disjunctive normal form (DNF).
(¬(¬p∨q)∨ ¬(¬q∨r)) ∨(¬p∨r)≡(p∧ ¬q)∨(q∧r)∨(¬p∨r)
Step 3: Construct a truth table to determine when the compound statement
is true.
p q r (p∧ ¬q) (q∧r) (¬p∨r) (p∧ ¬q)∨(q∧r)∨(¬p∨r)
T T T F T T T
T T F F F T T
T F T T F T T
T F F T F T T
F T T F T T T
F T F F F T T
F F T F F T T
F F F F F T T
Since the last column of the truth table consists only of T (true), we conclude
that the original proposition (p→q)∧(q→r)→(p→r) is a tautology.
Question 6
Question
Let p,q, and rbe propositions. Show that the following two statements are
logically equivalent:
(p∧q)∨rand (p∨r)∧(q∨r)
4
Solution
To show that the two statements are logically equivalent, we will first use logical
equivalences to simplify both statements and then show that they are the same.
Step 1: Simplify (p∧q)∨r
(p∧q)∨r≡(p∨r)∧(q∨r) Distributive Law
Therefore, (p∧q)∨rsimplifies to (p∨r)∧(q∨r).
Since we have shown that both statements simplify to the same expression,
we can conclude that (p∧q)∨ris logically equivalent to (p∨r)∧(q∨r).
Question 7
Question
Let p,q, and rbe propositions. Show that the proposition (p→q)→[(q→
r)→(p→r)] is a tautology using a truth table.
Solution
To show that (p→q)→[(q→r)→(p→r)] is a tautology, we will construct
a truth table and show that the proposition is true for all possible truth values
of p,q, and r.
p q r p →q q →r(p→q)→(q→r)p→r[(p→q)→(q→r)] →(p→r)
T T T T T T T T
T T F T F F F T
T F T F T T T T
T F F F T T 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
From the truth table, we can see that the final column evaluating (p→q)→
[(q→r)→(p→r)] is always true regardless of the truth values of p,q, and r.
Therefore, the proposition is a tautology.
Question 8
Question
Let p,q, and rbe propositional variables. Given the compound proposition
(p∧q)→r, show that this proposition is logically equivalent to ¬p∨ ¬q∨r
using logical equivalences.
5
Solution
To show that (p∧q)→ris logically equivalent to ¬p∨ ¬q∨r, we will use logical
equivalences to simplify and manipulate the expressions.
Step 1: Use the definition of the conditional (→):
(p∧q)→r≡ ¬(p∧q)∨r
≡(¬p∨ ¬q)∨r
≡ ¬p∨ ¬q∨r
Therefore, (p∧q)→ris logically equivalent to ¬p∨ ¬q∨r.
Question 9
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using propositional calculus laws and truth tables.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will construct a
truth table to demonstrate that the compound proposition is always true.
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)
T T T T T T T
T T F T F F F
T F T F T F T
T F F F T F F
F T T T T T T
F T F T F F T
F F T T T T T
F F F T T T T
Step 2: Analyze the truth table
The truth table shows that the column for (p→q)∧(q→r)→(p→r) is
always true (T) for all possible truth values of p,q, and r. Therefore, we can
conclude that (p→q)∧(q→r)→(p→r) is a tautology.
Question 10
Question
Let pand qbe propositional variables. Determine whether the following argu-
ment is valid or not:
(p→q)∧(q→p)→(p∧q)
6
Solution
To determine the validity of the given argument, we can use the method of truth
tables.
Step 1: Construct the truth table for the argument.
p q (p→q) (q→p) (p→q)∧(q→p)p∧q(p→q)∧(q→p)→(p∧q)
T T T T T T T
T F F T F F T
F T T F F F T
F F T T T F F
Step 2: Analyze the truth values in the last column. The truth
values in the last column indicate that the argument is not valid. In the last
row, when pis false and qis false, the premise is true but the conclusion is false.
This means that it is possible for the premise to be true while the conclusion is
false. Hence, the argument is not valid.
Question 11
Question
Let p,q, and rbe propositional variables. Show that (p→q)↔[(p∧q)∨(¬p∧
¬q)] is a tautology.
Solution
To show that the given statement is a tautology, we will use a truth table to
evaluate all possible truth values for p,q,r, and the entire statement.
p q (p→q) (p∧q) (¬p) (¬q) [(p∧q)∨(¬p∧ ¬q)] (p→q)↔[(p∧q)∨(¬p∧ ¬q)]
T T T T F F T T
T F F F F T T T
F T T F T F T T
F F T F T T T T
Since the final column is all true values, we have shown that the given
statement is a tautology.
Question 12
Question
Let p,q, and rbe propositions. Show that the proposition (p→q)→(q→
r)→(p→r) is a tautology using propositional logic laws.
7
Solution
To show that the proposition is a tautology, we will use logical equivalences to
simplify the expression step by step.
Step 1: Use the material implication law: a→b≡ ¬a∨b
¬[(p→q)→(q→r)] ∨(p→r)
Step 2: Apply material implication law again and simplify using De Mor-
gan’s law: ¬(a→b)≡a∧ ¬b
[(p∧ ¬q)∨(q∧ ¬r)] ∨(p→r)
Step 3: Use the distributive law: a∨(b∧c)≡(a∨b)∧(a∨c)
((p∧ ¬q)∨p)∧((p∧ ¬q)∨ ¬r)
Step 4: Simplify each part of the expression:
(p∨(p∧ ¬q)) ∧(p∨(¬r∧p))
(p∨p)∧(p∨ ¬r)
p∧(p∨ ¬r)
p
Since pis a proposition, and the expression reduces to p, we have shown that
(p→q)→(q→r)→(p→r) is a tautology.
Question 13
Question
Let p,q, and rbe propositional variables with the following premises: 1. ¬p→
(q∨r) 2. q→r3. ¬rDetermine whether the conclusion ¬qcan be inferred
from the premises.
Solution
1. We begin by assuming the premises are true and aim to show whether ¬q
can be logically deduced. 2. From premise 3, ¬r, we can deduce r→ ⊥, where
⊥represents a contradiction. 3. According to premise 2, if qis true, then ris
true. Combining this with r→ ⊥, we have q→ ⊥. 4. Rewriting q→ ⊥ as ¬q,
we obtain our conclusion: ¬q. 5. Therefore, the conclusion ¬qcan be logically
deduced from the premises provided.
8
Question 14
Question
Let pand qbe propositions. Show that (p→q)→(¬q→ ¬p) is a tautology
using truth tables.
Solution
To show that (p→q)→(¬q→ ¬p) is a tautology, we will construct a truth
table and verify that the output column is always true.
p q ¬p¬q p →q¬q→ ¬p(p→q)→(¬q→ ¬p)
T T F F T T T
T F F T F F T
F T T F T T T
F F T T T T T
Therefore, the final column of the truth table is always true, indicating that
the statement (p→q)→(¬q→ ¬p) is a tautology.
Question 15
Question
Let p,q, and rbe propositional variables. Show that the statement (p∧q)∨
[(p∧r)→(q∧r)] is a tautology.
Solution
To show that the given statement is a tautology, we will use a truth table to
demonstrate that the statement is true for all possible truth values of p,q, and
r.
p q r (p∧q) (p∧r) (q∧r) (p∧r)→(q∧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 F F T
F T T F F T T
F T F F F F T
F F T F F F T
F F F F F F T
Since the final column is always true (T), the statement (p∧q)∨[(p∧r)→
(q∧r)] is a tautology.
9
Question 16
Question
Let p,q, and rbe propositions. Show that the statement ¬((p→q)∧(q→
r)) ↔(p∧ ¬r) is a tautology using propositional logic laws and truth tables.
Solution
To show that the given statement is a tautology, we need to show that the
statement is true for all possible truth values of p,q, and r. We can do this by
constructing a truth table for the statement.
p q r p →q q →r(p→q)∧(q→r)¬((p→q)∧(q→r)) p∧ ¬r
T T T T T T F F
T T F T F F T T
T F T F T F T F
T F F F T F T T
F T T T T T F F
F T F T F F T T
F F T T T T F F
F F F T T T F F
As shown in the truth table, the statement ¬((p→q)∧(q→r)) ↔(p∧ ¬r)
is always true regardless of the truth values of p,q, and r. Therefore, the
statement is a tautology.
Question 17
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we will construct
truth tables for both expressions and show that they have the same truth values
for all possible truth values of p,q, and r.
Step 1: Construct the truth table for (p∧q)∨(p∧r).
10
p q r p ∧q p ∧r(p∧q)∨(p∧r)
T T T T T T
T T F T F T
T F T F T T
T F F F F F
F T T F F F
F T F F F F
F F T F F F
F F F F F F
Step 2: Construct the truth table for p∧(q∨r).
p q r q ∨r p ∧(q∨r)
T T T T T
T T F T T
T F T T T
T F F F F
F T T T F
F T F T F
F F T T F
F F F F F
Step 3: Conclusion
Comparing the truth tables for (p∧q)∨(p∧r) and p∧(q∨r), we see that
the two expressions have the same truth values for all possible truth values of
p,q, and r. Therefore, (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r).
Question 18
Question
Let p,q, and rbe propositional variables. Determine whether the following
argument is valid:
((p→q)∧(q→r)) →(p→r)
Solution
To determine the validity of the argument, we will use the method of proof
by contradiction. We will assume that the argument is invalid and derive a
contradiction.
Step 1: Assume that the argument is invalid, so the premise ((p→q)∧(q→
r)) is true while the conclusion (p→r) is false.
Step 2: From the premise, we know that both (p→q) and (q→r) are
true. This means that if pis true, then qis true, and if qis true, then ris true.
Step 3: Since (p→q) is true, we have two cases:
11
Case 1: pis true and qis true.
Case 2: pis false.
Step 4: In Case 1, we have qis true. Since (q→r) is also true, this implies
ris true. Therefore, in this case, pimplies r.
Step 5: In Case 2, pis false, and the implication (p→r) is vacuously true.
This contradicts our assumption that (p→r) is false.
Step 6: Since assuming the argument is invalid led to a contradiction, the
argument is indeed valid.
Therefore, ((p→q)∧(q→r)) →(p→r) is a valid argument.
Question 19
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using logical equivalence laws.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will manipulate
the expression using logical equivalence laws until we reach a known tautology
form (e.g., p∨ ¬p).
Step 1: Apply the definition of the conditional
(p→q)∧(q→r)→(p→r)
≡(¬p∨q)∧(¬q∨r)→(¬p∨r)
Step 2: Apply the definition of implication
≡ ¬[(¬p∨q)∧(¬q∨r)] ∨(¬p∨r)
≡ ¬[¬(¬p∨q)∨ ¬(¬q∨r)] ∨(¬p∨r)
≡ ¬[(p∧ ¬q)∨(q∧ ¬r)] ∨(¬p∨r)
Step 3: De Morgan’s Law
≡ ¬(p∧ ¬q)∧ ¬(q∧ ¬r)∨(¬p∨r)
≡(¬p∨q)∧(¬q∨r)∨(¬p∨r)
Step 4: Apply distribution
≡[¬p∨q∨(¬p∨r)] ∧[¬p∨r∨(¬q∨r)]
≡ ¬p∨q∨r∧ ¬p∨r∨ ¬q∨r
12
Step 5: Apply associativity and commutativity
≡(¬p∨ ¬p∨r∨q)∧(¬p∨ ¬q∨r∨r)
≡(¬p∨r∨q)∧(¬p∨ ¬q∨r)
Step 6: Apply absorption
≡ ¬p∨r∨q
≡ ¬p∨q∨r
≡p→r
Therefore, (p→q)∧(q→r)→(p→r) is a tautology.
Question 20
Question
Let p,q, and rbe propositional variables. Show that the following statement is
a tautology:
(p→(q→r)) →((p→q)→(p→r))
Solution
To show that the statement is a tautology, we’ll use a truth table to evaluate
all possible truth values of p,q, and r.
Step 1: Create the truth table.
p q r q →r p →(q→r)p→q p →r(p→q)→(p→r)
T T T T T T T T
T T F F F T F T
T F T T T F T T
T F F T T F F T
F T T T T T T T
F T F F T T T T
F F T T T T T T
F F F T T T T T
Since the final column is always true, the original statement is a tautology.
Question 21
Question
Let p, q, and rbe statements. Determine whether the following argument is
logically valid:
(p→q)∧(q→r)→(p→r)
13
Solution
To determine whether the given argument is logically valid, we will systemati-
cally analyze the truth values of the statements involved.
Step 1: Construct a truth table for (p→q)∧(q→r)→(p→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
Step 2: Analyze the truth values of the statement (p→q)∧(q→r)→
(p→r).
From the truth table, we see that there are cases where the statement (p→
q)∧(q→r)→(p→r) is false. Therefore, the given argument is not logically
valid since there are cases where the conclusion does not necessarily follow from
the premises.
Question 22
Question
Let p,q, and rbe propositions such that (p→q)∧(q→r)∧(r→p). Determine
whether the propositions p,q, and rare all true, all false, or some combination
of true and false.
Solution
Given: (p→q)∧(q→r)∧(r→p)
Step 1: Consider the truth value possibilities for p,q, and r.
Let’s construct a truth table for the given propositions:
14
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 F F
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 only combination of truth values
for p,q, and rthat satisfies (p→q)∧(q→r)∧(r→p) is when p=False,q=
False, and r=True.
Therefore, the propositions p,q, and rare in the combination of False,
False,True.
Question 23
Question
Let p, q, r be propositions. Use only the logical connectives ∧(AND), ∨(OR),
and ¬(NOT) to simplify the following compound proposition:
(p∧q)∨(p∧ ¬q)∨(¬p∧q)∨(¬p∧ ¬q)∨r
Solution
To simplify the compound proposition, we can use several logical equivalences
and properties.
Step 1: Distributive Law
p∧q=p∧(q∨ ¬q) = (p∧q)∨(p∧ ¬q)
Similarly, we can express ¬p∧qas the disjunction of its components:
¬p∧q= (¬p∧q)∨(¬p∧ ¬q)
Step 2: Combining Like Terms Applying Step 1, we can rewrite the
given compound proposition:
(p∧q)∨(p∧ ¬q)∨(¬p∧q)∨(¬p∧ ¬q)∨r
= (p∧q)∨(¬p∧q)∨(p∧ ¬q)∨(¬p∧ ¬q)∨r
Now, we can combine like terms:
(p∧q)∨(¬p∧q)∨(p∧ ¬q)∨(¬p∧ ¬q) = p∨ ¬p
15
We also have p∨ ¬p= True by the Law of Excluded Middle.
Step 3: Final Simplification Therefore, the compound proposition sim-
plifies to:
True ∨r= True
So, the simplified form of the given compound proposition is True .
Question 24
Question
Let p,q, and rbe propositional variables. Prove that (p⇒q)∧(q⇒r)⇒(p⇒
r) using propositional calculus laws.
Solution
To prove (p⇒q)∧(q⇒r)⇒(p⇒r), we need to show that the proposition is
a tautology. We can use propositional calculus laws to derive its truth.
Step 1: Write the given proposition in terms of basic connectives:
(p⇒q)∧(q⇒r)⇒(p⇒r)
Step 2: Apply the definition of the implication to rewrite the proposition:
(¬p∨q)∧(¬q∨r)⇒(¬p∨r)
Step 3: Use the distributive law to expand the expression:
¬p∨q⇒(¬q∨r)∧ ¬p∨r
Step 4: Apply the definition of the implication again to get:
¬(¬p∨q)∨(¬q∨r)∧ ¬p∨r
Step 5: Use De Morgan’s laws to simplify the expression:
(p∧ ¬q)∨(¬q∨r)∧ ¬p∨r
Step 6: Distribute the disjunction over the conjunction:
(p∧ ¬q∨ ¬q)∨(p∧ ¬q∨r)∧ ¬p∨r
Step 7: Simplify the intermediate steps further:
(p∨ ¬q)∨(p∧ ¬q∨r)∧ ¬p∨r
Step 8: Apply the absorption law to simplify the expression:
p∨ ¬q∨ ¬p∨r
Step 9: Apply the law of excluded middle to simplify the expression further:
True
Since we have obtained a tautology True, we can conclude that (p⇒q)∧(q⇒
r)⇒(p⇒r) is a valid proposition.
16
Question 25
Question
Let prepresent the statement ”It is raining” and qrepresent the statement ”It
is cloudy.” Write the statement ”If it is not raining or it is cloudy, then it is not
both raining and cloudy” using pand q, and then determine its truth value.
Solution
1. Let prepresent the statement ”It is raining” and qrepresent the statement
”It is cloudy.” The given statement can be written as:
(¬p∨q)→ ¬(p∧q)
2. We can create a truth table to determine the truth value of this statement:
p q ¬p¬(p∧q)¬p∨q(¬p∨q)→ ¬(p∧q)
T T F F T T
T F F T F T
F T T T T T
F F T T T T
3. From the truth table, we can see that the statement ”If it is not raining
or it is cloudy, then it is not both raining and cloudy” is true for all possible
truth values of pand q.
Question 26
Question
Let p,q, and rbe propositions. Use truth tables to determine whether the
following argument is valid: ”If pthen q, and if qthen r, therefore if pthen r.”
Solution
To determine the validity of the argument, we need to construct truth tables
for the propositions p,q,r, and the implications involved.
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 T T
T F F F T T 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
17
The truth table shows that the argument is not valid because there is a row
where the premise is true (all columns before the arrow) and the conclusion
(last column) is false. Specifically, when pis true, qis false, and ris true, the
conclusion is false even though both premises are true. Therefore, the argument
”If pthen q, and if qthen r, therefore if pthen r” is not valid.
Question 27
Question
Let p,q, and rbe propositional variables. 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 will use logical
equivalences to simplify the expression.
Step 1: Apply distribution and associative properties
(p∨q)∧(q∨r)→(p∨r)
≡ ¬((p∨q)∧(q∨r)) ∨(p∨r) Definition of implication
≡(¬(p∨q)∨ ¬(q∨r)) ∨(p∨r) De Morgan’s laws
≡((¬p∧ ¬q)∨(¬q∧ ¬r)) ∨(p∨r) De Morgan’s laws
≡((¬p∧ ¬q)∨(¬q∧ ¬r)) ∨(p∨r) Commutative properties of ∨and ∧
≡((¬p∨ ¬q)∧(¬p∨ ¬r)) ∨(p∨r) Distribution
≡(¬p∨ ¬q∨(p∨r)) ∧(¬p∨ ¬r∨(p∨r)) Distribution
≡(¬p∨ ¬q∨p∨r)∧(¬p∨ ¬r∨p∨r) Commutative properties of ∨
≡(T∨r)∧(T∨r) Negation law
≡T∧TDomination law
≡TIdentity law (T represents True)
Therefore, (p∨q)∧(q∨r)→(p∨r) is a tautology.
Question 28
Question
Let p, q, r be statements such that p→(q∧r) is true. Determine whether the
statement ¬p∨ ¬q∨ ¬ris true or false.
Solution
Step 1: We are given that p→(q∧r) is true. We will use the truth table
method to determine the truth value of ¬p∨ ¬q∨ ¬r.
18
Step 2: Let’s construct the truth table for p→(q∧r):
p q r q ∧r p →(q∧r)
T T T T T
T T F F F
T F T F F
T F F F F
F T T T T
F T F F T
F F T F T
F F F F T
Step 3: Since p→(q∧r) is true in only the rows where the premise is false
or the conclusion is true, we see that it is true in the last three rows of the truth
table.
Step 4: Now, let’s analyze the statement ¬p∨ ¬q∨ ¬r. We will negate each
statement and then take the disjunction.
¬p:{TTFFFFFF}
¬q:{TTTTFFFF}
¬r:{TTTTTFTF}
Step 5: Now, we will calculate the disjunction of ¬p, ¬q, ¬r:
¬p¬q¬r¬p∨ ¬q∨ ¬r
F F F F
F F T T
F T F T
F T T T
T F F T
T F T T
T T F T
T T T T
Step 6: Therefore, the statement ¬p∨ ¬q∨ ¬ris true in all cases except
when p=T,q=F, and r=F.
Question 29
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology.
19
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will use a truth
table to verify that the compound proposition is true for all possible truth values
of p,q, and r.
p q r p →q q →r p →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 of the truth table is always true, we conclude that
(p→q)∧(q→r)→(p→r) is a tautology.
Question 30
Question
Let p,q, and rbe propositions. Prove or disprove the following statement: If
(p→(q→r)) ∧ ¬r, then (p∧ ¬q).
Solution
To prove or disprove the statement, we will construct a truth table for the given
propositions and analyze the truth values.
p q r (q→r) (p→(q→r)) ¬r(p→(q→r)) ∧ ¬r p ∧ ¬q
T T T T T F F F
T T F F F T F F
T F T T T F F F
T F F T T T T T
F T T T T F F F
F T F F T T F F
F F T T T F F F
F F F T T T T F
From the truth table, we can see that there is a row where (p→(q→r))∧¬r
is true but p∧ ¬qis false. Therefore, the statement ”If (p→(q→r)) ∧ ¬r, then
(p∧ ¬q)” is disproved.
20
Question 31
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using truth tables.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will construct a
truth table for these propositions.
Step 1: Construct a truth table for (p→q)∧(q→r)→(p→r).
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 2: Evaluate the truth values for (p→q)∧(q→r)→(p→r).
In the truth table, we see that the final column is always true (T). Thus,
(p→q)∧(q→r)→(p→r) is a tautology, as the expression is true for all
possible truth values of p,q, and r.
Question 32
Question
Let p,q, and rbe propositions. Show whether the following argument is valid
or invalid using propositional calculus:
”If pimplies q, and qimplies r, then pimplies r.”
Solution
To determine the validity of the argument, we will use the rules of propositional
calculus to analyze the given propositions.
Step 1: Express the given argument in propositional logic. Let’s denote: -
prepresents the proposition ”It is raining.” - qrepresents the proposition ”The
ground is wet.” - rrepresents the proposition ”The flowers are blooming.”
The argument can be represented as: If p→qand q→r, then p→r.
Step 2: Verify the logical implication p→rassuming p→qand q→rare
true.
The statement p→rcan be verified using the following truth tables:
21
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
Since the truth table shows that p→ris not always true when p→qand
q→rare true simultaneously, the argument is not valid.
Question 33
Question
Let p,q, and rbe propositions. Consider the logical expression (p∧q)→r.
Determine whether the expression is a tautology, a contradiction, or neither.
Solution
To determine whether the logical expression (p∧q)→ris a tautology, a contra-
diction, or neither, we will construct a truth table for all possible truth values
of p,q, and 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
22
Since there is at least one row in the truth table where the logical expression
(p∧q)→revaluates to false, the expression is not a tautology. Also, since
there is at least one row where the expression evaluates to true, the expression
is not a contradiction. Therefore, the logical expression (p∧q)→ris neither a
tautology nor a contradiction.
Question 34
Question
Given the following premises: P→(Q∨R)
Q→S
R→T
T→U
¬U
Prove that ¬P.
Solution
1. We will prove the conclusion ¬Pby assuming the opposite, P, and deriving
a contradiction.
2. Assume Pis true.
3. From the first premise P→(Q∨R) and our assumption P, we can
conclude Q∨Rby modus ponens.
4. From Q∨Rand the second premise Q→S, we have two cases:
Case 1: Qis true.
Case 2: Ris true.
5. In case 1 (Qis true), we have Sby modus ponens with the second premise.
6. From case 2 (Ris true) and the third premise R→T, we have Tby
modus ponens.
7. From Tand the fourth premise T→U, we have Uby modus ponens.
8. However, we also have ¬Uas given in the premises, which leads to a
contradiction.
9. This contradiction arises from assuming Pto be true.
10. Therefore, our assumption that Pis true must be false, leading to the
conclusion that ¬Pis true.
Question 35
Question
Let p,q, and rbe propositional variables. Show that the following statement is
a tautology:
[(p→q)∧(q→r)] →(p→r)
23
Step 4: Simplify the Expression
Simplifying further, we get:
(¬p∨ ¬q∧p∨ ¬r)∨(p∧ ¬r)
Step 5: Apply Distribution of ∨over ∧
Applying the distribution of ∨over ∧:
(¬p∨(¬q∧p)∨ ¬r)∨(p∧ ¬r)
Step 6: Apply Associative Property of ∨
Rearranging the terms using the associative property of ∨to make it clear for
the negation:
(¬p∨p∧ ¬q∨ ¬r)∨(p∧ ¬r)
Step 7: Negate the Entire Proposition
Finally, we negate the entire expression:
¬((¬p∨p∧ ¬q∨ ¬r)∨(p∧ ¬r))
Therefore, the negation of the original proposition using De Morgan’s laws
is:
(¬p∧p∧ ¬q∧r)∧(¬p∨ ¬¬r)
Question 2
Question
Let pand qbe propositional variables. Show that ¬(p∧q)≡(¬p∨ ¬q) using
logical equivalences.
Solution
To show that ¬(p∧q)≡(¬p∨¬q), we will use the laws of logic and propositional
calculus to manipulate the expressions on both sides of the equivalence.
Step 1: Apply De Morgan’s Law to the left side of the equivalence,
¬(p∧q) = ¬p∨ ¬q.
Therefore, ¬(p∧q)≡(¬p∨ ¬q) by De Morgan’s Law.
Thus, we have shown that ¬(p∧q)≡(¬p∨ ¬q).
Question 3
Question
Let p,q, and rbe propositions. Show that the statement (p→q)∧(r→ ¬q)→
(p∧r)→ ¬qis a tautology.
2
Solution
To show that the given statement is a tautology, we will use a truth table to
verify that the statement is true for all possible truth values of p,q, and r.
p q r p →q r → ¬q(p→q)∧(r→ ¬q) (p∧r)¬q
[(p→q)∧(r→ ¬q)] →[(p∧r)→ ¬q]
T T T T F F T F
T
T T F T F F F F
T
T F T F T F T T
T
T F F F T F F T
T
F T T T F F F F
T
F T F T F F F F
T
F F T T T T F T
T
F F F T T T F T
T
Since the final column contains all True values, we can conclude that the
statement (p→q)∧(r→ ¬q)→(p∧r)→ ¬qis a tautology.
Question 4
Question
Let prepresent the statement ”It is raining” and qrepresent the statement ”I
am indoors.” Convert the following statement into symbolic form: ”It is not
raining and I am indoors.”
Solution
To convert the statement ”It is not raining and I am indoors” into symbolic
form, we will use logical connectives.
Step 1: Identify the statements and their corresponding symbols: Let p
represent ”It is raining” and qrepresent ”I am indoors.”
Step 2: Express the given statement using logical connectives: The given
statement ”It is not raining and I am indoors” can be represented as the con-
junction of the negation of pand q, which can be written as ¬p∧q.
Step 3: Write the symbolic form of the statement: Therefore, the symbolic
form of the statement ”It is not raining and I am indoors” is ¬p∧q.
3
Question 5
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 given proposition is a tautology, we can use the laws of logic
and reasoning to simplify and ultimately prove its validity.
Step 1: Apply the definition of implication for the compound propositions.
(p→q)∧(q→r)→(p→r)≡(¬p∨q)∧(¬q∨r)→(¬p∨r)
Step 2: Use the definition of implication to write the compound statement
in disjunctive normal form (DNF).
(¬(¬p∨q)∨ ¬(¬q∨r)) ∨(¬p∨r)≡(p∧ ¬q)∨(q∧r)∨(¬p∨r)
Step 3: Construct a truth table to determine when the compound statement
is true.
p q r (p∧ ¬q) (q∧r) (¬p∨r) (p∧ ¬q)∨(q∧r)∨(¬p∨r)
T T T F T T T
T T F F F T T
T F T T F T T
T F F T F T T
F T T F T T T
F T F F F T T
F F T F F T T
F F F F F T T
Since the last column of the truth table consists only of T (true), we conclude
that the original proposition (p→q)∧(q→r)→(p→r) is a tautology.
Question 6
Question
Let p,q, and rbe propositions. Show that the following two statements are
logically equivalent:
(p∧q)∨rand (p∨r)∧(q∨r)
4
Solution
To show that the two statements are logically equivalent, we will first use logical
equivalences to simplify both statements and then show that they are the same.
Step 1: Simplify (p∧q)∨r
(p∧q)∨r≡(p∨r)∧(q∨r) Distributive Law
Therefore, (p∧q)∨rsimplifies to (p∨r)∧(q∨r).
Since we have shown that both statements simplify to the same expression,
we can conclude that (p∧q)∨ris logically equivalent to (p∨r)∧(q∨r).
Question 7
Question
Let p,q, and rbe propositions. Show that the proposition (p→q)→[(q→
r)→(p→r)] is a tautology using a truth table.
Solution
To show that (p→q)→[(q→r)→(p→r)] is a tautology, we will construct
a truth table and show that the proposition is true for all possible truth values
of p,q, and r.
p q r p →q q →r(p→q)→(q→r)p→r[(p→q)→(q→r)] →(p→r)
T T T T T T T T
T T F T F F F T
T F T F T T T T
T F F F T T 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
From the truth table, we can see that the final column evaluating (p→q)→
[(q→r)→(p→r)] is always true regardless of the truth values of p,q, and r.
Therefore, the proposition is a tautology.
Question 8
Question
Let p,q, and rbe propositional variables. Given the compound proposition
(p∧q)→r, show that this proposition is logically equivalent to ¬p∨ ¬q∨r
using logical equivalences.
5
Solution
To show that (p∧q)→ris logically equivalent to ¬p∨ ¬q∨r, we will use logical
equivalences to simplify and manipulate the expressions.
Step 1: Use the definition of the conditional (→):
(p∧q)→r≡ ¬(p∧q)∨r
≡(¬p∨ ¬q)∨r
≡ ¬p∨ ¬q∨r
Therefore, (p∧q)→ris logically equivalent to ¬p∨ ¬q∨r.
Question 9
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using propositional calculus laws and truth tables.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will construct a
truth table to demonstrate that the compound proposition is always true.
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)
T T T T T T T
T T F T F F F
T F T F T F T
T F F F T F F
F T T T T T T
F T F T F F T
F F T T T T T
F F F T T T T
Step 2: Analyze the truth table
The truth table shows that the column for (p→q)∧(q→r)→(p→r) is
always true (T) for all possible truth values of p,q, and r. Therefore, we can
conclude that (p→q)∧(q→r)→(p→r) is a tautology.
Question 10
Question
Let pand qbe propositional variables. Determine whether the following argu-
ment is valid or not:
(p→q)∧(q→p)→(p∧q)
6
Solution
To determine the validity of the given argument, we can use the method of truth
tables.
Step 1: Construct the truth table for the argument.
p q (p→q) (q→p) (p→q)∧(q→p)p∧q(p→q)∧(q→p)→(p∧q)
T T T T T T T
T F F T F F T
F T T F F F T
F F T T T F F
Step 2: Analyze the truth values in the last column. The truth
values in the last column indicate that the argument is not valid. In the last
row, when pis false and qis false, the premise is true but the conclusion is false.
This means that it is possible for the premise to be true while the conclusion is
false. Hence, the argument is not valid.
Question 11
Question
Let p,q, and rbe propositional variables. Show that (p→q)↔[(p∧q)∨(¬p∧
¬q)] is a tautology.
Solution
To show that the given statement is a tautology, we will use a truth table to
evaluate all possible truth values for p,q,r, and the entire statement.
p q (p→q) (p∧q) (¬p) (¬q) [(p∧q)∨(¬p∧ ¬q)] (p→q)↔[(p∧q)∨(¬p∧ ¬q)]
T T T T F F T T
T F F F F T T T
F T T F T F T T
F F T F T T T T
Since the final column is all true values, we have shown that the given
statement is a tautology.
Question 12
Question
Let p,q, and rbe propositions. Show that the proposition (p→q)→(q→
r)→(p→r) is a tautology using propositional logic laws.
7
Solution
To show that the proposition is a tautology, we will use logical equivalences to
simplify the expression step by step.
Step 1: Use the material implication law: a→b≡ ¬a∨b
¬[(p→q)→(q→r)] ∨(p→r)
Step 2: Apply material implication law again and simplify using De Mor-
gan’s law: ¬(a→b)≡a∧ ¬b
[(p∧ ¬q)∨(q∧ ¬r)] ∨(p→r)
Step 3: Use the distributive law: a∨(b∧c)≡(a∨b)∧(a∨c)
((p∧ ¬q)∨p)∧((p∧ ¬q)∨ ¬r)
Step 4: Simplify each part of the expression:
(p∨(p∧ ¬q)) ∧(p∨(¬r∧p))
(p∨p)∧(p∨ ¬r)
p∧(p∨ ¬r)
p
Since pis a proposition, and the expression reduces to p, we have shown that
(p→q)→(q→r)→(p→r) is a tautology.
Question 13
Question
Let p,q, and rbe propositional variables with the following premises: 1. ¬p→
(q∨r) 2. q→r3. ¬rDetermine whether the conclusion ¬qcan be inferred
from the premises.
Solution
1. We begin by assuming the premises are true and aim to show whether ¬q
can be logically deduced. 2. From premise 3, ¬r, we can deduce r→ ⊥, where
⊥represents a contradiction. 3. According to premise 2, if qis true, then ris
true. Combining this with r→ ⊥, we have q→ ⊥. 4. Rewriting q→ ⊥ as ¬q,
we obtain our conclusion: ¬q. 5. Therefore, the conclusion ¬qcan be logically
deduced from the premises provided.
8
Question 14
Question
Let pand qbe propositions. Show that (p→q)→(¬q→ ¬p) is a tautology
using truth tables.
Solution
To show that (p→q)→(¬q→ ¬p) is a tautology, we will construct a truth
table and verify that the output column is always true.
p q ¬p¬q p →q¬q→ ¬p(p→q)→(¬q→ ¬p)
T T F F T T T
T F F T F F T
F T T F T T T
F F T T T T T
Therefore, the final column of the truth table is always true, indicating that
the statement (p→q)→(¬q→ ¬p) is a tautology.
Question 15
Question
Let p,q, and rbe propositional variables. Show that the statement (p∧q)∨
[(p∧r)→(q∧r)] is a tautology.
Solution
To show that the given statement is a tautology, we will use a truth table to
demonstrate that the statement is true for all possible truth values of p,q, and
r.
p q r (p∧q) (p∧r) (q∧r) (p∧r)→(q∧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 F F T
F T T F F T T
F T F F F F T
F F T F F F T
F F F F F F T
Since the final column is always true (T), the statement (p∧q)∨[(p∧r)→
(q∧r)] is a tautology.
9
Question 16
Question
Let p,q, and rbe propositions. Show that the statement ¬((p→q)∧(q→
r)) ↔(p∧ ¬r) is a tautology using propositional logic laws and truth tables.
Solution
To show that the given statement is a tautology, we need to show that the
statement is true for all possible truth values of p,q, and r. We can do this by
constructing a truth table for the statement.
p q r p →q q →r(p→q)∧(q→r)¬((p→q)∧(q→r)) p∧ ¬r
T T T T T T F F
T T F T F F T T
T F T F T F T F
T F F F T F T T
F T T T T T F F
F T F T F F T T
F F T T T T F F
F F F T T T F F
As shown in the truth table, the statement ¬((p→q)∧(q→r)) ↔(p∧ ¬r)
is always true regardless of the truth values of p,q, and r. Therefore, the
statement is a tautology.
Question 17
Question
Let p,q, and rbe propositions. Show that (p∧q)∨(p∧r) is logically equivalent
to p∧(q∨r).
Solution
To show that (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r), we will construct
truth tables for both expressions and show that they have the same truth values
for all possible truth values of p,q, and r.
Step 1: Construct the truth table for (p∧q)∨(p∧r).
10
p q r p ∧q p ∧r(p∧q)∨(p∧r)
T T T T T T
T T F T F T
T F T F T T
T F F F F F
F T T F F F
F T F F F F
F F T F F F
F F F F F F
Step 2: Construct the truth table for p∧(q∨r).
p q r q ∨r p ∧(q∨r)
T T T T T
T T F T T
T F T T T
T F F F F
F T T T F
F T F T F
F F T T F
F F F F F
Step 3: Conclusion
Comparing the truth tables for (p∧q)∨(p∧r) and p∧(q∨r), we see that
the two expressions have the same truth values for all possible truth values of
p,q, and r. Therefore, (p∧q)∨(p∧r) is logically equivalent to p∧(q∨r).
Question 18
Question
Let p,q, and rbe propositional variables. Determine whether the following
argument is valid:
((p→q)∧(q→r)) →(p→r)
Solution
To determine the validity of the argument, we will use the method of proof
by contradiction. We will assume that the argument is invalid and derive a
contradiction.
Step 1: Assume that the argument is invalid, so the premise ((p→q)∧(q→
r)) is true while the conclusion (p→r) is false.
Step 2: From the premise, we know that both (p→q) and (q→r) are
true. This means that if pis true, then qis true, and if qis true, then ris true.
Step 3: Since (p→q) is true, we have two cases:
11
Case 1: pis true and qis true.
Case 2: pis false.
Step 4: In Case 1, we have qis true. Since (q→r) is also true, this implies
ris true. Therefore, in this case, pimplies r.
Step 5: In Case 2, pis false, and the implication (p→r) is vacuously true.
This contradicts our assumption that (p→r) is false.
Step 6: Since assuming the argument is invalid led to a contradiction, the
argument is indeed valid.
Therefore, ((p→q)∧(q→r)) →(p→r) is a valid argument.
Question 19
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using logical equivalence laws.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will manipulate
the expression using logical equivalence laws until we reach a known tautology
form (e.g., p∨ ¬p).
Step 1: Apply the definition of the conditional
(p→q)∧(q→r)→(p→r)
≡(¬p∨q)∧(¬q∨r)→(¬p∨r)
Step 2: Apply the definition of implication
≡ ¬[(¬p∨q)∧(¬q∨r)] ∨(¬p∨r)
≡ ¬[¬(¬p∨q)∨ ¬(¬q∨r)] ∨(¬p∨r)
≡ ¬[(p∧ ¬q)∨(q∧ ¬r)] ∨(¬p∨r)
Step 3: De Morgan’s Law
≡ ¬(p∧ ¬q)∧ ¬(q∧ ¬r)∨(¬p∨r)
≡(¬p∨q)∧(¬q∨r)∨(¬p∨r)
Step 4: Apply distribution
≡[¬p∨q∨(¬p∨r)] ∧[¬p∨r∨(¬q∨r)]
≡ ¬p∨q∨r∧ ¬p∨r∨ ¬q∨r
12
Step 5: Apply associativity and commutativity
≡(¬p∨ ¬p∨r∨q)∧(¬p∨ ¬q∨r∨r)
≡(¬p∨r∨q)∧(¬p∨ ¬q∨r)
Step 6: Apply absorption
≡ ¬p∨r∨q
≡ ¬p∨q∨r
≡p→r
Therefore, (p→q)∧(q→r)→(p→r) is a tautology.
Question 20
Question
Let p,q, and rbe propositional variables. Show that the following statement is
a tautology:
(p→(q→r)) →((p→q)→(p→r))
Solution
To show that the statement is a tautology, we’ll use a truth table to evaluate
all possible truth values of p,q, and r.
Step 1: Create the truth table.
p q r q →r p →(q→r)p→q p →r(p→q)→(p→r)
T T T T T T T T
T T F F F T F T
T F T T T F T T
T F F T T F F T
F T T T T T T T
F T F F T T T T
F F T T T T T T
F F F T T T T T
Since the final column is always true, the original statement is a tautology.
Question 21
Question
Let p, q, and rbe statements. Determine whether the following argument is
logically valid:
(p→q)∧(q→r)→(p→r)
13
Solution
To determine whether the given argument is logically valid, we will systemati-
cally analyze the truth values of the statements involved.
Step 1: Construct a truth table for (p→q)∧(q→r)→(p→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
Step 2: Analyze the truth values of the statement (p→q)∧(q→r)→
(p→r).
From the truth table, we see that there are cases where the statement (p→
q)∧(q→r)→(p→r) is false. Therefore, the given argument is not logically
valid since there are cases where the conclusion does not necessarily follow from
the premises.
Question 22
Question
Let p,q, and rbe propositions such that (p→q)∧(q→r)∧(r→p). Determine
whether the propositions p,q, and rare all true, all false, or some combination
of true and false.
Solution
Given: (p→q)∧(q→r)∧(r→p)
Step 1: Consider the truth value possibilities for p,q, and r.
Let’s construct a truth table for the given propositions:
14
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 F F
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 only combination of truth values
for p,q, and rthat satisfies (p→q)∧(q→r)∧(r→p) is when p=False,q=
False, and r=True.
Therefore, the propositions p,q, and rare in the combination of False,
False,True.
Question 23
Question
Let p, q, r be propositions. Use only the logical connectives ∧(AND), ∨(OR),
and ¬(NOT) to simplify the following compound proposition:
(p∧q)∨(p∧ ¬q)∨(¬p∧q)∨(¬p∧ ¬q)∨r
Solution
To simplify the compound proposition, we can use several logical equivalences
and properties.
Step 1: Distributive Law
p∧q=p∧(q∨ ¬q) = (p∧q)∨(p∧ ¬q)
Similarly, we can express ¬p∧qas the disjunction of its components:
¬p∧q= (¬p∧q)∨(¬p∧ ¬q)
Step 2: Combining Like Terms Applying Step 1, we can rewrite the
given compound proposition:
(p∧q)∨(p∧ ¬q)∨(¬p∧q)∨(¬p∧ ¬q)∨r
= (p∧q)∨(¬p∧q)∨(p∧ ¬q)∨(¬p∧ ¬q)∨r
Now, we can combine like terms:
(p∧q)∨(¬p∧q)∨(p∧ ¬q)∨(¬p∧ ¬q) = p∨ ¬p
15
We also have p∨ ¬p= True by the Law of Excluded Middle.
Step 3: Final Simplification Therefore, the compound proposition sim-
plifies to:
True ∨r= True
So, the simplified form of the given compound proposition is True .
Question 24
Question
Let p,q, and rbe propositional variables. Prove that (p⇒q)∧(q⇒r)⇒(p⇒
r) using propositional calculus laws.
Solution
To prove (p⇒q)∧(q⇒r)⇒(p⇒r), we need to show that the proposition is
a tautology. We can use propositional calculus laws to derive its truth.
Step 1: Write the given proposition in terms of basic connectives:
(p⇒q)∧(q⇒r)⇒(p⇒r)
Step 2: Apply the definition of the implication to rewrite the proposition:
(¬p∨q)∧(¬q∨r)⇒(¬p∨r)
Step 3: Use the distributive law to expand the expression:
¬p∨q⇒(¬q∨r)∧ ¬p∨r
Step 4: Apply the definition of the implication again to get:
¬(¬p∨q)∨(¬q∨r)∧ ¬p∨r
Step 5: Use De Morgan’s laws to simplify the expression:
(p∧ ¬q)∨(¬q∨r)∧ ¬p∨r
Step 6: Distribute the disjunction over the conjunction:
(p∧ ¬q∨ ¬q)∨(p∧ ¬q∨r)∧ ¬p∨r
Step 7: Simplify the intermediate steps further:
(p∨ ¬q)∨(p∧ ¬q∨r)∧ ¬p∨r
Step 8: Apply the absorption law to simplify the expression:
p∨ ¬q∨ ¬p∨r
Step 9: Apply the law of excluded middle to simplify the expression further:
True
Since we have obtained a tautology True, we can conclude that (p⇒q)∧(q⇒
r)⇒(p⇒r) is a valid proposition.
16
Question 25
Question
Let prepresent the statement ”It is raining” and qrepresent the statement ”It
is cloudy.” Write the statement ”If it is not raining or it is cloudy, then it is not
both raining and cloudy” using pand q, and then determine its truth value.
Solution
1. Let prepresent the statement ”It is raining” and qrepresent the statement
”It is cloudy.” The given statement can be written as:
(¬p∨q)→ ¬(p∧q)
2. We can create a truth table to determine the truth value of this statement:
p q ¬p¬(p∧q)¬p∨q(¬p∨q)→ ¬(p∧q)
T T F F T T
T F F T F T
F T T T T T
F F T T T T
3. From the truth table, we can see that the statement ”If it is not raining
or it is cloudy, then it is not both raining and cloudy” is true for all possible
truth values of pand q.
Question 26
Question
Let p,q, and rbe propositions. Use truth tables to determine whether the
following argument is valid: ”If pthen q, and if qthen r, therefore if pthen r.”
Solution
To determine the validity of the argument, we need to construct truth tables
for the propositions p,q,r, and the implications involved.
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 T T
T F F F T T 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
17
The truth table shows that the argument is not valid because there is a row
where the premise is true (all columns before the arrow) and the conclusion
(last column) is false. Specifically, when pis true, qis false, and ris true, the
conclusion is false even though both premises are true. Therefore, the argument
”If pthen q, and if qthen r, therefore if pthen r” is not valid.
Question 27
Question
Let p,q, and rbe propositional variables. 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 will use logical
equivalences to simplify the expression.
Step 1: Apply distribution and associative properties
(p∨q)∧(q∨r)→(p∨r)
≡ ¬((p∨q)∧(q∨r)) ∨(p∨r) Definition of implication
≡(¬(p∨q)∨ ¬(q∨r)) ∨(p∨r) De Morgan’s laws
≡((¬p∧ ¬q)∨(¬q∧ ¬r)) ∨(p∨r) De Morgan’s laws
≡((¬p∧ ¬q)∨(¬q∧ ¬r)) ∨(p∨r) Commutative properties of ∨and ∧
≡((¬p∨ ¬q)∧(¬p∨ ¬r)) ∨(p∨r) Distribution
≡(¬p∨ ¬q∨(p∨r)) ∧(¬p∨ ¬r∨(p∨r)) Distribution
≡(¬p∨ ¬q∨p∨r)∧(¬p∨ ¬r∨p∨r) Commutative properties of ∨
≡(T∨r)∧(T∨r) Negation law
≡T∧TDomination law
≡TIdentity law (T represents True)
Therefore, (p∨q)∧(q∨r)→(p∨r) is a tautology.
Question 28
Question
Let p, q, r be statements such that p→(q∧r) is true. Determine whether the
statement ¬p∨ ¬q∨ ¬ris true or false.
Solution
Step 1: We are given that p→(q∧r) is true. We will use the truth table
method to determine the truth value of ¬p∨ ¬q∨ ¬r.
18
Step 2: Let’s construct the truth table for p→(q∧r):
p q r q ∧r p →(q∧r)
T T T T T
T T F F F
T F T F F
T F F F F
F T T T T
F T F F T
F F T F T
F F F F T
Step 3: Since p→(q∧r) is true in only the rows where the premise is false
or the conclusion is true, we see that it is true in the last three rows of the truth
table.
Step 4: Now, let’s analyze the statement ¬p∨ ¬q∨ ¬r. We will negate each
statement and then take the disjunction.
¬p:{TTFFFFFF}
¬q:{TTTTFFFF}
¬r:{TTTTTFTF}
Step 5: Now, we will calculate the disjunction of ¬p, ¬q, ¬r:
¬p¬q¬r¬p∨ ¬q∨ ¬r
F F F F
F F T T
F T F T
F T T T
T F F T
T F T T
T T F T
T T T T
Step 6: Therefore, the statement ¬p∨ ¬q∨ ¬ris true in all cases except
when p=T,q=F, and r=F.
Question 29
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology.
19
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will use a truth
table to verify that the compound proposition is true for all possible truth values
of p,q, and r.
p q r p →q q →r p →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 of the truth table is always true, we conclude that
(p→q)∧(q→r)→(p→r) is a tautology.
Question 30
Question
Let p,q, and rbe propositions. Prove or disprove the following statement: If
(p→(q→r)) ∧ ¬r, then (p∧ ¬q).
Solution
To prove or disprove the statement, we will construct a truth table for the given
propositions and analyze the truth values.
p q r (q→r) (p→(q→r)) ¬r(p→(q→r)) ∧ ¬r p ∧ ¬q
T T T T T F F F
T T F F F T F F
T F T T T F F F
T F F T T T T T
F T T T T F F F
F T F F T T F F
F F T T T F F F
F F F T T T T F
From the truth table, we can see that there is a row where (p→(q→r))∧¬r
is true but p∧ ¬qis false. Therefore, the statement ”If (p→(q→r)) ∧ ¬r, then
(p∧ ¬q)” is disproved.
20
Question 31
Question
Let p,q, and rbe propositions. Show that (p→q)∧(q→r)→(p→r) is a
tautology using truth tables.
Solution
To show that (p→q)∧(q→r)→(p→r) is a tautology, we will construct a
truth table for these propositions.
Step 1: Construct a truth table for (p→q)∧(q→r)→(p→r).
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 2: Evaluate the truth values for (p→q)∧(q→r)→(p→r).
In the truth table, we see that the final column is always true (T). Thus,
(p→q)∧(q→r)→(p→r) is a tautology, as the expression is true for all
possible truth values of p,q, and r.
Question 32
Question
Let p,q, and rbe propositions. Show whether the following argument is valid
or invalid using propositional calculus:
”If pimplies q, and qimplies r, then pimplies r.”
Solution
To determine the validity of the argument, we will use the rules of propositional
calculus to analyze the given propositions.
Step 1: Express the given argument in propositional logic. Let’s denote: -
prepresents the proposition ”It is raining.” - qrepresents the proposition ”The
ground is wet.” - rrepresents the proposition ”The flowers are blooming.”
The argument can be represented as: If p→qand q→r, then p→r.
Step 2: Verify the logical implication p→rassuming p→qand q→rare
true.
The statement p→rcan be verified using the following truth tables:
21
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
Since the truth table shows that p→ris not always true when p→qand
q→rare true simultaneously, the argument is not valid.
Question 33
Question
Let p,q, and rbe propositions. Consider the logical expression (p∧q)→r.
Determine whether the expression is a tautology, a contradiction, or neither.
Solution
To determine whether the logical expression (p∧q)→ris a tautology, a contra-
diction, or neither, we will construct a truth table for all possible truth values
of p,q, and 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
22
Since there is at least one row in the truth table where the logical expression
(p∧q)→revaluates to false, the expression is not a tautology. Also, since
there is at least one row where the expression evaluates to true, the expression
is not a contradiction. Therefore, the logical expression (p∧q)→ris neither a
tautology nor a contradiction.
Question 34
Question
Given the following premises: P→(Q∨R)
Q→S
R→T
T→U
¬U
Prove that ¬P.
Solution
1. We will prove the conclusion ¬Pby assuming the opposite, P, and deriving
a contradiction.
2. Assume Pis true.
3. From the first premise P→(Q∨R) and our assumption P, we can
conclude Q∨Rby modus ponens.
4. From Q∨Rand the second premise Q→S, we have two cases:
Case 1: Qis true.
Case 2: Ris true.
5. In case 1 (Qis true), we have Sby modus ponens with the second premise.
6. From case 2 (Ris true) and the third premise R→T, we have Tby
modus ponens.
7. From Tand the fourth premise T→U, we have Uby modus ponens.
8. However, we also have ¬Uas given in the premises, which leads to a
contradiction.
9. This contradiction arises from assuming Pto be true.
10. Therefore, our assumption that Pis true must be false, leading to the
conclusion that ¬Pis true.
Question 35
Question
Let p,q, and rbe propositional variables. Show that the following statement is
a tautology:
[(p→q)∧(q→r)] →(p→r)
23
Solution
To prove that a statement is a tautology, we need to show that it is true for all
possible truth values of its propositional variables. We will use a truth table to
demonstrate this.
Step 1: Create a truth table for the statement. We will consider all
possible truth values of p,q, and r, and evaluate the given statement [(p→
q)∧(q→r)] →(p→r).
p q r p →q 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
Step 2: Analyze the truth table. From the truth table, we see that
the final column is always true, regardless of the truth values of p,q, and r.
Therefore, the statement [(p→q)∧(q→r)] →(p→r) is a tautology.
24
