Answer Key
Logic and Propositional Calculus Question Bank Set 1
-
University:
Liberty University -
Course:
MATH 250 | Introduction to Discrete Mathematics Academic year:
2024
-
Views:
430
Pages:
70
Author:
Jesly V.
MATH 250 - INTRODUCTION TO
DISCRETE MATHEMATICS - Logic
and Propositional Calculus
Question Bank - Set 1
Liberty University
Question 1
Question
Let p, q, and r be propositional variables. Determine whether the following
statement is a tautology, a contradiction, or neither: (p → q)∧(q → r)∧(r → p).
Solution
To determine whether (p → q)∧(q → r)∧(r → p) is a tautology, a contradiction,
or neither, we can construct a truth table for the statement.
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
r→p
T
T
T
T
F
T
T
T
(p → q) ∧ (q → r) ∧ (r → p)
T
F
F
F
F
F
T
T
The truth table shows that the statement (p → q) ∧ (q → r) ∧ (r → p) is
only true when p and q are both false, q and r are both true, or p, q, and r are
all true. Therefore, the statement is neither a tautology nor a contradiction. Question 2
Question
Let p, q, and r be propositions. Show that (p ∧ q) ∨ (p ∧ r) is equivalent to
p ∧ (q ∨ r) using logical equivalences.
Solution
To show that (p ∧ q) ∨ (p ∧ r) is equivalent to p ∧ (q ∨ r), we will use logical
equivalences step by step.
Step 1: Apply Distribution Law (∧ over ∨) to (p ∧ q) ∨ (p ∧ r).
(p ∧ q) ∨ (p ∧ r) ≡ p ∧ (q ∨ r)
Therefore, (p ∧ q) ∨ (p ∧ r) is equivalent to p ∧ (q ∨ r) by using logical
equivalences.
Question 3
Question
Let p and q be propositional variables. Show that the proposition (p → q) ↔
(¬p ∨ q) is a tautology using truth tables.
Solution
To show that a proposition is a tautology, we need to show that it is true for all
possible truth values of its propositional variables.
p
T
T
F
F
q
T
F
T
F
¬p
F
F
T
T
¬p ∨ q
T
F
T
T
p→q
T
F
T
T
(p → q) ↔ (¬p ∨ q)
T
T
T
T
Step 1: Construct a truth table showing the truth values of p, q, ¬p,
¬p ∨ q, p → q, and (p → q) ↔ (¬p ∨ q).
Step 2: Fill in the truth values of ¬p, ¬p∨q, p → q, and (p → q) ↔ (¬p∨q)
based on the truth values of p and q.
Step 3: Verify that the final column in the truth table, which represents
the proposition (p → q) ↔ (¬p ∨ q), is true for all possible combinations
of truth values of p and q.
Since the final column of the truth table consists of all ”T” values, we
conclude that the proposition (p → q) ↔ (¬p ∨ q) is a tautology.
2 Question 4
Question
Let p, q, r be propositions. Prove or disprove the following inference:
(p → q) ∧ (q → r) ⇒ (p → r)
Solution
To prove or disprove the given inference, we will consider both cases.
Case 1: Assume (p → q) ∧ (q → r) is true, but (p → r) is false.
In this case: - If (p → q) is true, then either p is false or q is true. - If (q → r)
is true, then either q is false or r is true.
Since we are assuming (p → r) is false, this means if p is true, then r must
be false.
Therefore, the assumption that (p → r) is false contradicts the given premises
(p → q) ∧ (q → r). Thus, in this case, the inference holds.
Case 2: Assume (p → r) is true, but (p → q) ∧ (q → r) is false.
In this case: - If (p → r) is true, then either p is false or r is true.
Since we are assuming (p → q) ∧ (q → r) is false, this means that either p is
true and q is false, or q is true and r is false.
However, the assumption that (p → r) is true contradicts the given premises
(p → q) ∧ (q → r).
Therefore, in both cases, the inference (p → q) ∧ (q → r) ⇒ (p → r) holds
true.
Question 5
Question
Let p, q, and r be propositions. Show that (p ∧ q) ∨ (p ∧ r) is logically equivalent
to p ∧ (q ∨ r).
Solution
To show that (p ∧ q) ∨ (p ∧ r) is logically equivalent to p ∧ (q ∨ r), we can use
the laws of logic to simplify both expressions and show that they are the same.
Step 1: Apply distribution using the distributive law (a ∧ b) ∨ (a ∧ c) ≡
a ∧ (b ∨ c).
(p ∧ q) ∨ (p ∧ r) ≡ p ∧ (q ∨ r)
Therefore, (p ∧ q) ∨ (p ∧ r) is indeed logically equivalent to p ∧ (q ∨ r).
3 Question 6
Question
Let p, q, and r be propositional variables. Determine whether the following
argument is valid:
(p ∧ q) → r,
p → (q ∧ r) ⊨ p → r
Solution
To determine whether the argument is valid, we will use the method of natural
deduction to show that the conclusion p → r can be derived from the premises
(p ∧ q) → r and p → (q ∧ r).
Step 1: Assume the premise (p ∧ q) → r and p → (q ∧ r).
Step 2: Using the premise p → (q ∧ r), we can conclude that p → q and
p → r by the property of implication.
Step 3: From p → q and p, we can derive q using the property of modus
ponens.
Step 4: Now, we can apply the premise (p∧q) → r to show that (p∧q) → r.
Step 5: Combining (p ∧ q) → r with p ∧ q, we can derive r using modus
ponens.
Step 6: Since we have shown that r follows from p∧q, and we have previously
shown that q follows from p, we can conclude that r follows from p.
Step 7: Therefore, we have proved that p → r can be derived from the
premises (p ∧ q) → r and p → (q ∧ r).
Since we have successfully derived the conclusion from the premises, the
argument is valid.
Question 7
Question
Let p, q, and r be propositions. Show that the given statement is a tautology:
(p ⇒ q) ∨ (q ⇒ r) ∨ (r ⇒ p).
Solution
To show that the given statement is a tautology, we can use truth tables to
verify that the statement is true for all possible truth values of p, q, and r.
4 Step 1: Create the truth table for (p ⇒ q) ∨ (q ⇒ r) ∨ (r ⇒ p)
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p⇒q
T
T
F
F
T
T
T
T
q⇒r
T
F
T
T
T
F
T
T
r⇒p
T
T
T
T
F
T
T
T
(p ⇒ q) ∨ (q ⇒ r) ∨ (r ⇒ p)
T
T
T
T
T
T
T
T
Since the final column is always true (T ), the given statement (p ⇒ q)∨(q ⇒
r) ∨ (r ⇒ p) is a tautology.
Question 8
Question
Let p, q, r be propositional variables. Determine if the following argument is
valid:
Premise 1: (p ∧ q) → r
Premise 2: p
Conclusion: r
Solution
To determine whether the argument is valid, we will use the method of proof by
contradiction, assuming that the premises are true and the conclusion is false.
Step 1: Assume the conclusion ¬r and the premises are true.
Let’s assume that the conclusion ¬r is true, and the premises (p ∧ q) → r
and p are true.
Step 2: Use the premises to derive a contradiction.
From premise 2, we have p, and from premise 1, we have (p ∧ q) → r.
Step 3: Using Modus Ponens, we have:
(p ∧ q) → r
p
∴q→r
Step 4: Using Modus Ponens again, we have:
q→r
5 p
∴r
Step 5: Contradiction
We have derived r from our assumptions that ¬r, leading to a contradiction.
Hence, our assumption is false.
Conclusion: The argument is valid, and the conclusion r follows logically
from the premises.
Question 9
Question
Let p, q, and r be propositions. Show that the following statement is a tautology:
(p → q) ∧ (q → r) → (p → r)
Solution
To show that the given statement is a tautology, we will construct a truth table
to verify if the statement holds for all possible truth values of p, q, and r.
Step 1: Create a truth table for the given statement
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
p→r
T
F
T
F
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
T
T
T
T
T
Step 2: Analyze the truth table
From the truth table, we can see that the statement (p → q) ∧ (q → r) →
(p → r) evaluates to true for all possible truth values of p, q, and r. Thus, we
have shown that the given statement is a tautology.
Question 10
Question
Let p and q be propositions such that the compound proposition (p∧q)∨(¬p∧¬q)
is false. Determine whether the proposition ¬p ∨ ¬q is true or false.
6 Solution
To determine whether the proposition ¬p ∨ ¬q is true or false, we will first
analyze the truth values of the compound proposition (p ∧ q) ∨ (¬p ∧ ¬q).
Step 1: Find the truth values of (p ∧ q) and (¬p ∧ ¬q).
Since the compound proposition (p ∧ q) ∨ (¬p ∧ ¬q) is false, either (p ∧ q) or
(¬p ∧ ¬q) or both must be false.
Step 2: Determine the truth values of p and q by analyzing (p ∧ q)
and (¬p ∧ ¬q).
If (p∧q) is false, then either p is false or q is false or both are false. Similarly,
if (¬p ∧ ¬q) is false, then either ¬p is false (meaning p is true) or ¬q is false
(meaning q is true) or both are false.
We summarize the possibilities in the truth table below:
p
¬p ∧ ¬q
T
F
T
T
F
T
F
T
q
(p ∧ q) ∨ (¬p ∧ ¬q)
T
F
F
T
T
T
F
F
p∧q
¬p
¬q
T
F
F
F
F
T
F
T
F
F
T
T
From the truth table, we see that either p is true and q is false, or p is false
and q is true for the compound proposition (p ∧ q) ∨ (¬p ∧ ¬q) to be false.
Step 3: Using the values from Step 2, determine the truth value
of ¬p ∨ ¬q.
If p is true and q is false, then ¬p is false and ¬q is true. Therefore, ¬p ∨ ¬q
is true.
If p is false and q is true, then both ¬p and ¬q are true. Therefore, ¬p ∨ ¬q
is true.
Hence, the proposition ¬p ∨ ¬q is true.
Question 11
Question
Let p, q, and r be propositions. Prove or disprove the following statement by
either providing a truth table or a counterexample:
(p ∧ q) → r ≡ (p → r) ∨ (q → r)
7 Solution
We will prove the equivalence of the given statement by constructing a truth
table for both sides and comparing the truth values.
Step 1: Create a truth table for (p ∧ q) → r and (p → r) ∨ (q → r).
p
(p → r) ∨ (q → r)
T
T
T
F
T
T
T
T
F
T
F
T
F
T
F
T
q
r
p∧q
(p ∧ q) → r
p→r
q→r
T
T
T
T
T
T
T
F
T
F
F
F
F
T
F
T
T
T
F
F
F
T
F
T
T
T
F
T
T
T
T
F
F
T
T
F
F
T
F
T
T
T
F
F
F
T
T
T
Step 2: Analyze the truth values of both sides. From the truth table,
we can see that both sides of the equivalence have the same truth values for all
possible truth values of p, q, and r.
Thus, we have proved that (p ∧ q) → r ≡ (p → r) ∨ (q → r).
Question 12
Question
Consider the following proposition:
(P → Q) ∧ (Q → R) ∧ (R → P ).
Determine whether the proposition is a tautology, a contradiction, or contingent. Justify your answer.
Solution
To determine whether the proposition (P → Q) ∧ (Q → R) ∧ (R → P ) is a
tautology, a contradiction, or contingent, we need to analyze all possible truth
values for P , Q, and R.
Step 1: List all possible truth values We will construct a truth table
to consider all possible combinations of truth values for P , Q, and R:
8 P
(P → Q) ∧ (Q → R) ∧ (R → P )
T
T
T
F
T
F
T
F
F
F
F
F
F
T
F
T
Q
R
P →Q
Q→R
R→P
T
T
T
T
T
T
F
T
F
T
F
T
F
T
T
F
F
F
T
T
T
T
T
T
F
T
F
T
F
T
F
T
T
T
T
F
F
T
T
T
Step 2: Interpret the truth values From the truth table, we can see
that the proposition (P → Q) ∧ (Q → R) ∧ (R → P ) is false for some truth
value combinations (i.e., when P is true and Q is false, or when P is false and
Q is true).
Step 3: Conclusion Since the proposition is not true for all possible truth
values, it is neither a tautology nor a contradiction. Therefore, the proposition
is contingent.
Question 13
Question
Let p, q, and r be propositions. Use logical equivalences to show that (p ∧ q) ∨
(¬p ∧ r) is logically equivalent to (p ∨ r) ∧ (q ∨ r).
Solution
To prove that (p ∧ q) ∨ (¬p ∧ r) is logically equivalent to (p ∨ r) ∧ (q ∨ r), we will
apply various logical equivalences step by step.
Step 1: Apply Distribution Law: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Step 2: Apply De Morgan’s Law: ¬p ≡ p → False
Step 3: Apply Distribution Law again: (p ∧ q) ∨ (p ∧ r) ≡ p ∧ (q ∨ r)
Step 4: Applying the associative law of logical OR: p∧(q∨r) ≡ (p∧q)∨(p∧r)
Since we have shown that both expressions are equivalent through a series of
logical equivalences, we have proved that (p ∧ q) ∨ (¬p ∧ r) is logically equivalent
to (p ∨ r) ∧ (q ∨ r).
9 Question 14
Question
Let p, q, and r be propositions. Show that the proposition (p ∧ q) ∨ (p ∧ r) is
logically equivalent to p ∧ (q ∨ r) using truth tables.
Solution
To show that two propositions are logically equivalent, we need to show that
they have the same truth values for all possible truth values of their component
propositions. We will use a truth table to compare the truth values of (p ∧ q) ∨
(p ∧ r) and p ∧ (q ∨ r).
Step 1: Create a truth table for (p ∧ q) ∨ (p ∧ r).
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
p∧q
T
T
F
F
F
F
F
F
r
T
F
T
F
T
F
T
F
p∧r
T
F
T
F
F
F
F
F
(p ∧ q) ∨ (p ∧ r)
T
T
T
F
F
F
F
F
Step 2: Create a truth table for p ∧ (q ∨ r).
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
q∨r
T
T
T
F
T
T
T
F
p ∧ (q ∨ r)
T
T
T
F
F
F
F
F
Step 3: Compare the truth values of the two propositions.
From the truth tables, we can see that both propositions 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 15
Question
Let p, q, and r be propositions such that (p → q) ∧ (q → r) → p. Show that
this proposition is a tautology using a truth table.
10 Solution
To show that the proposition (p → q) ∧ (q → r) → p is a tautology, we will
construct a truth table for all possible truth values of p, q, and r.
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
(p → q)
T
T
F
F
T
T
T
T
r
T
F
T
F
T
F
T
F
(q → r)
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
(p → q) ∧ (q → r) → p
T
T
T
T
T
T
T
T
In the above truth table, the column (p → q) ∧ (q → r) → p is always
true regardless of the truth values of p, q, and r. This means that the original
proposition is a tautology.
Question 16
Question
Let p and q be propositions. Show that the proposition (p → q) → (¬q → ¬p)
is a tautology using a truth table.
Solution
To show that the proposition (p → q) → (¬q → ¬p) is a tautology, we will
create a truth table to check all possible truth values of p and q.
p
T
T
F
F
q
T
F
T
F
¬p
F
F
T
T
¬q
F
T
F
T
(p → q)
T
F
T
T
(¬q → ¬p)
T
F
T
T
(p → q) → (¬q → ¬p)
T
T
T
T
Since the final column of the truth table is always true (T), the proposition
(p → q) → (¬q → ¬p) is a tautology.
11 Question 17
Question
Let p, q, and r be propositions. Show that (p ∨ q) ∧ (p ∨ r) is logically equivalent
to p ∨ (q ∧ r).
Solution
To show that (p ∨ q) ∧ (p ∨ r) is logically equivalent to p ∨ (q ∧ r), we need to
show that the truth values of these two compound propositions are the same
for all possible truth values of p, q, and r.
Step 1: Construct truth tables for both compound propositions.
First, let’s construct a truth table for (p ∨ q) ∧ (p ∨ r):
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
p∨q
T
T
T
T
T
T
F
F
r
T
F
T
F
T
F
T
F
p∨r
T
T
T
T
T
F
T
F
(p ∨ q) ∧ (p ∨ r)
T
T
T
T
T
F
F
F
Next, let’s construct a truth table for p ∨ (q ∧ r):
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
q∧r
T
F
F
F
T
F
F
F
p ∨ (q ∧ r)
T
T
T
T
T
F
F
F
Step 2: Compare the truth values of both compound propositions.
From the truth tables, we can see that the truth values of both compound
propositions are the same for all possible truth values of p, q, and r. Therefore,
we can conclude that (p ∨ q) ∧ (p ∨ r) is logically equivalent to p ∨ (q ∧ r).
12 Question 18
Question
Let p, q, and r be propositions such that:
(p → q) → r
¬r → (q → ¬p)
¬q
Determine the truth value of p.
Solution
1. We are given that ¬q. We will use this to find the truth value of q. 2. Since
¬q, then q is false. 3. By the second statement, ¬r → (q → ¬p), and since q
is false, we can simplify this to ¬r. 4. Therefore, r is false. 5. Finally, by the
first statement (p → q) → r, we know that (p → q) implies r. Since r is false,
(p → q) must also be false. 6. Since q is false, the only way for (p → q) to be
false is for p to be true. 7. Hence, the truth value of p is true.
Question 19
Question
Let p, q, and r be propositional variables. Show that the following statement is
a tautology:
(p ∧ q → r) → (p → (q → r))
Solution
To show that the given statement is a tautology, we will use a truth table to
check all possible truth values of p, q, and r.
Step 1: Create a truth table for the given statement.
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∧q
T
T
F
F
F
F
F
F
p∧q →r
T
F
T
T
T
T
T
T
q→r
T
F
T
T
T
F
T
T
p → (q → r)
T
T
T
T
T
T
T
T
Step 2: Analyze the truth table. From the truth table, we can see that
the last column, which represents the given statement, is true for all possible
13 truth values of p, q, and r. Since the statement is true for all possible truth
values of p, q, and r, we conclude that the statement is a tautology.
Question 20
Question
Let p, q, and r be propositional variables with the following premises:
(p → q) ∧ (q → r)
¬r
Determine whether the conclusion ¬p follows using propositional calculus
rules.
Solution
To determine if ¬p follows from the given premises, we will construct a proof
by contradiction.
Step 1: Assume p is true.
Step 2: Use the first premise (p → q) ∧ (q → r) to deduce q from p → q.
Since p is true and (p → q) is true, it follows that q is also true.
Step 3: Use the second premise ¬r to deduce ¬q from q → r.
Since r is false (due to ¬r), q → r is false. Therefore, q must also be false.
Step 4: From Steps 2 and 3, we have arrived at a contradiction: q is both
true and false.
Therefore, our assumption that p is true must be false.
Step 5: Conclude that ¬p follows from the given premises.
Hence, the conclusion ¬p follows using propositional calculus rules.
Question 21
Question
Let p, q, and r be propositions such that p → (q ∧ r) is false. Determine the
truth values of p, q, and r.
Solution
To determine the truth values of p, q, and r, we will consider the truth table
for the implication p → (q ∧ r). The truth table for an implication is as follows:
p
T
T
F
F
p→q
T
F
T
T
q
T
F
T
F
14 Given that p → (q ∧ r) is false, we observe that the only way this can occur
is when p is true and q ∧ r is false.
Step 1: Assigning values to p, q, and r based on the truth table
Since p must be true and q ∧ r must be false in order for p → (q ∧ r) to be false,
we have: - p = true - q ∧ r = false
Using the truth table for conjunction (∧), we find that q ∧ r is false only
when q and r are both false.
Step 2: Assigning values to q and r Therefore, we have: - q = false r = false
In conclusion, the truth values of p, q, and r are: - p is true - q is false - r
is false
Question 22
Question
Let p, q, and r be propositions. Show that (p ⇒ q) ∨ (q ⇒ r) is logically
equivalent to (p ∧ q) ⇒ r.
Solution
To show that (p ⇒ q) ∨ (q ⇒ r) is logically equivalent to (p ∧ q) ⇒ r, we will
construct truth tables for both statements and show that they have the same
truth values for all possible truth values of p, q, and r.
Step 1: Truth table for (p ⇒ q) ∨ (q ⇒ r)
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p⇒q
T
T
F
F
T
T
T
T
q⇒r
T
F
T
T
T
F
T
T
(p ⇒ q) ∨ (q ⇒ r)
T
T
T
T
T
T
T
T
Step 2: Truth table for (p ∧ q) ⇒ r
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∧q
T
T
F
F
F
F
F
F
15
(p ∧ q) ⇒ r
T
F
T
T
T
T
T
T Step 3: Conclusion From the truth tables above, we can see that (p ⇒
q) ∨ (q ⇒ r) and (p ∧ q) ⇒ r have the same truth values for all possible truth
values of p, q, and r. Therefore, (p ⇒ q) ∨ (q ⇒ r) is logically equivalent to
(p ∧ q) ⇒ r.
Question 23
Question
Let p, q, and r be propositional variables. Show that the following proposition
is a tautology:
(p ∧ q) → (p ∨ r)
Solution
To show that the proposition (p ∧ q) → (p ∨ r) is a tautology, we can use a truth
table to prove that the proposition is true for all possible truth values of p, q,
and r.
Step 1: Create the truth table for the proposition (p ∧ q) → (p ∨ r).
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∧q
T
T
F
F
F
F
F
F
p∨r
T
T
T
T
T
F
T
F
(p ∧ q) → (p ∨ r)
T
T
T
T
T
T
T
T
Since the last column of the truth table is always true, we can conclude that
the proposition (p ∧ q) → (p ∨ r) is a tautology.
Question 24
Question
Let p, q, and r be propositions. Show that the proposition (p ∧ q) ∨ (p ∧ r) is
logically equivalent to p ∧ (q ∨ r).
Solution
To show that two propositions are logically equivalent, we need to show that
they have the same truth value for all possible truth values of their component
propositions. We can do this by creating truth tables for both propositions and
checking if they are the same.
16 Step 1: Create a truth table for (p ∧ q) ∨ (p ∧ r).
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
p∧q
T
T
F
F
F
F
F
F
r
T
F
T
F
T
F
T
F
p∧r
T
F
T
F
F
F
F
F
(p ∧ q) ∨ (p ∧ r)
T
T
T
F
F
F
F
F
Step 2: Create a truth table for p ∧ (q ∨ r).
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
q∨r
T
T
T
F
T
T
T
F
p ∧ (q ∨ r)
T
T
T
F
F
F
F
F
Step 3: Compare the two truth tables. After comparing the truth
values of both propositions, we can see that (p ∧ q) ∨ (p ∧ r) and p ∧ (q ∨ r)
have the same truth values for all possible combinations of p, q, and r. Hence,
(p ∧ q) ∨ (p ∧ r) is logically equivalent to p ∧ (q ∨ r).
Question 25
Question
Let p and q be propositions. Show that the statement (p → q) ∧ (q → p) is
logically equivalent to p ↔ q.
Solution
To show that (p → q) ∧ (q → p) is logically equivalent to p ↔ q, we need to
show that they have the same truth values for all possible truth values of p and
q.
Step 1: Construct the truth table for (p → q) ∧ (q → p).
p
T
T
F
F
q
T
F
T
F
p→q
T
F
T
T
q→p
T
T
F
T
17
(p → q) ∧ (q → p)
T
F
F
T Step 2: Construct the truth table for p ↔ q.
p
T
T
F
F
p↔q
T
F
F
T
q
T
F
T
F
Step 3: Compare the truth tables for (p → q) ∧ (q → p) and p ↔ q.
From the truth tables, we observe that both (p → q) ∧ (q → p) and p ↔ q
have the same truth values for all combinations of p and q. Hence, we can
conclude that (p → q) ∧ (q → p) is logically equivalent to p ↔ q.
Question 26
Question
Let p, q, and r be propositions. Show that (p ∧ q) ∨ (p ∧ r) is logically equivalent
to p ∧ (q ∨ r).
Solution
To show that (p ∧ q) ∨ (p ∧ r) is logically equivalent to p ∧ (q ∨ r), we can perform
a series of logical equivalences using the basic laws of propositional logic.
Step 1: Apply the Distributive Law
(p ∧ q) ∨ (p ∧ r)
= p ∧ (q ∨ r)
Step 2: Commutativity of ∨
p ∧ (q ∨ r)
= p ∧ (r ∨ q)
Step 3: Commutativity of ∧
p ∧ (r ∨ q)
= (r ∨ q) ∧ p
Step 4: Apply the Distributive Law (Reverse)
(r ∨ q) ∧ p
= (p ∧ r) ∨ (p ∧ q)
Therefore, (p ∧ q) ∨ (p ∧ r) is logically equivalent to p ∧ (q ∨ r).
18 Question 27
Question
Let p and q be propositions. Show that (p → q) ∨ (q → p) is a tautology.
Solution
To show that (p → q) ∨ (q → p) is a tautology, we will construct a truth table
to check all possible combinations of truth values for p and q.
p
T
T
F
F
q
T
F
T
F
p→q
T
F
T
T
q→p
T
T
F
T
(p → q) ∨ (q → p)
T
T
T
T
Since the final column consists of all true values, we can conclude that (p →
q) ∨ (q → p) is a tautology.
Question 28
Question
Let p, q, and r be propositional variables. Determine whether the following
argument is valid:
(p ∧ q) ⇒ r, p ⇒ q, ¬r
¬p
Solution
To determine the validity of the argument, we will use the method of proof by
contradiction. We will assume that the premises are true and the conclusion is
false, and then derive a contradiction.
Step 1: Assume the premises are true and the conclusion is false:
1. (p ∧ q) ⇒ r
(Premise)
2. p ⇒ q
(Premise)
3. ¬r
(Premise)
4. ¬p
(Assumption for contradiction)
Step 2: Use premises (1) and (2) to derive r:
5. p
(Assumption)
6. q
(Modus Ponens on 2 and 5)
7. p ∧ q
8. r
(Conjunction of 5 and 6)
(Modus Ponens on 1 and 7)
19 Step 3: Derive a contradiction:
9. r
(From Step 8)
10. ¬r
(From 3)
11. False
(Contradiction from 9 and 10)
Since assuming ¬p led to a contradiction, the argument is valid.
Question 29
Question
Let p, q, and r be 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 can use truth
tables.
Step 1: Create a truth table for the given proposition
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
p→r
T
F
T
F
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
T
T
T
T
T
Step 2: Analyze the truth table Since the final column of the truth
table consists only of true values, we can conclude that the proposition (p →
q) ∧ (q → r) → (p → r) is a tautology.
Question 30
Question
Let p, q, and r be propositions. Determine whether the following argument is
valid:
”If p then q. If q then r. Therefore, if p then r.”
20 Solution
To determine the validity of the argument, we can use the rules of implication in propositional logic. Specifically, we will use the transitive property of
implication.
Step 1: Express the given statements as logical implications:
Statement 1: ”If p then q” can be expressed as p → q.
Statement 2: ”If q then r” can be expressed as q → r.
Conclusion: ”If p then r” can be expressed as p → r.
Step 2: Apply the transitive property of implication. According to the
transitive property of implication, if p → q and q → r are true, then p → r is
also true.
Step 3: Use truth tables to check the validity of the argument:
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
p→r
T
F
T
F
T
T
T
T
Step 4: Conclusion From the truth table, we see that the statement p → r
is not always true when p → q and q → r are true. Therefore, the argument is
not always valid.
Question 31
Question
Let p, q, and r be propositions. Show that (p → q) ∧ (q → r) → (p → r) is a
tautology using a truth table.
Solution
To show that (p → q) ∧ (q → r) → (p → r) is a tautology, we will construct a
truth table for all possible truth values of p, q, and r, and show that the final
column is always true.
21 p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
p→r
T
F
T
F
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
T
T
T
T
T
As shown in the truth table, the final column is always true regardless of
the truth values of p, q, and r. Therefore, (p → q) ∧ (q → r) → (p → r) is a
tautology.
Question 32
Question
Use natural deduction to prove the following statement: (p → q) ∧ (q → r) ⊢
p→r
Solution
To prove (p → q) ∧ (q → r) ⊢ p → r using natural deduction, we will assume
(p → q) ∧ (q → r) as a premise and derive p → r.
Step 1: Assume (p → q) ∧ (q → r) as a premise.
Step 2: Using conjunction elimination, separate the conjuncts (p → q) and
(q → r).
1. (p → q) ∧ (q → r) Premise
2. p → q
Conjunction Elimination from (1)
3. q → r
Conjunction Elimination from (1)
Step 3: Assume p.
Step 4: Using modus ponens with p → q and p, derive q.
4. p
5. p → q
6. q
Assumption
Reiteration from (2)
Modus Ponens from (5) and (4)
Step 5: Using modus ponens with q → r and q, derive r.
7. q
8. q → r
9. r
Reiteration from (6)
Reiteration from (3)
Modus Ponens from (8) and (7)
Step 6: Since we derived r under assumption p, we can infer p → r.
22 10. p → r (from 3, 4-9)
Therefore, we have shown that (p → q) ∧ (q → r) ⊢ p → r using natural
deduction.
Question 33
Question
Let p, q, and r be propositions. Show that the proposition (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 truth
tables to verify that the compound proposition is true for all possible truth
values of p, q, and r.
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r) p → r
T
T
F
F
F
T
F
F
T
T
F
T
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
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 34
Question
Let p, q, r be propositional variables where: p: It is sunny today. q: It is cold
today. r: It is snowing today.
Consider the proposition: If it is sunny today, then it is not cold or it is
snowing. Write this proposition in terms of p, q, and r using logical connectives
(negation, conjunction, disjunction, implication).
23 Solution
Step 1: The given proposition can be written as follows:
p → (¬q ∨ r)
Therefore, the proposition ”If it is sunny today, then it is not cold or it is
snowing” can be represented in terms of p, q, and r using the logical connectives
of negation, disjunction, and implication.
Question 35
Question
Prove or disprove the following statement: ”If it is not raining or it is not cold,
then John will go for a run.”
Solution
To prove or disprove the statement, we will analyze the given proposition in
terms of logic and propositional calculus.
Let P denote the proposition ”It is raining”, Q denote the proposition ”It
is cold”, and R denote the proposition ”John will go for a run”.
The given statement can be written as: (¬P ∨ ¬Q) → R. This can be
translated into words as ”If it is not raining or it is not cold, then John will go
for a run.”
To prove or disprove this statement, we will construct a truth table for the
given proposition and check if the implication holds in all cases.
P
T
T
F
F
Q
T
F
T
F
¬P ∨ ¬Q
F
T
T
T
R
T
T
T
T
(¬P ∨ ¬Q) → R
T
T
T
T
Since the truth table shows that the implication holds in all cases, we can
conclude that the statement ”If it is not raining or it is not cold, then John will
go for a run” is true.
24 Question 2
Question
Let p, q, and r be propositions. Show that (p ∧ q) ∨ (p ∧ r) is equivalent to
p ∧ (q ∨ r) using logical equivalences.
Solution
To show that (p ∧ q) ∨ (p ∧ r) is equivalent to p ∧ (q ∨ r), we will use logical
equivalences step by step.
Step 1: Apply Distribution Law (∧ over ∨) to (p ∧ q) ∨ (p ∧ r).
(p ∧ q) ∨ (p ∧ r) ≡ p ∧ (q ∨ r)
Therefore, (p ∧ q) ∨ (p ∧ r) is equivalent to p ∧ (q ∨ r) by using logical
equivalences.
Question 3
Question
Let p and q be propositional variables. Show that the proposition (p → q) ↔
(¬p ∨ q) is a tautology using truth tables.
Solution
To show that a proposition is a tautology, we need to show that it is true for all
possible truth values of its propositional variables.
p
T
T
F
F
q
T
F
T
F
¬p
F
F
T
T
¬p ∨ q
T
F
T
T
p→q
T
F
T
T
(p → q) ↔ (¬p ∨ q)
T
T
T
T
Step 1: Construct a truth table showing the truth values of p, q, ¬p,
¬p ∨ q, p → q, and (p → q) ↔ (¬p ∨ q).
Step 2: Fill in the truth values of ¬p, ¬p∨q, p → q, and (p → q) ↔ (¬p∨q)
based on the truth values of p and q.
Step 3: Verify that the final column in the truth table, which represents
the proposition (p → q) ↔ (¬p ∨ q), is true for all possible combinations
of truth values of p and q.
Since the final column of the truth table consists of all ”T” values, we
conclude that the proposition (p → q) ↔ (¬p ∨ q) is a tautology.
2 Question 4
Question
Let p, q, r be propositions. Prove or disprove the following inference:
(p → q) ∧ (q → r) ⇒ (p → r)
Solution
To prove or disprove the given inference, we will consider both cases.
Case 1: Assume (p → q) ∧ (q → r) is true, but (p → r) is false.
In this case: - If (p → q) is true, then either p is false or q is true. - If (q → r)
is true, then either q is false or r is true.
Since we are assuming (p → r) is false, this means if p is true, then r must
be false.
Therefore, the assumption that (p → r) is false contradicts the given premises
(p → q) ∧ (q → r). Thus, in this case, the inference holds.
Case 2: Assume (p → r) is true, but (p → q) ∧ (q → r) is false.
In this case: - If (p → r) is true, then either p is false or r is true.
Since we are assuming (p → q) ∧ (q → r) is false, this means that either p is
true and q is false, or q is true and r is false.
However, the assumption that (p → r) is true contradicts the given premises
(p → q) ∧ (q → r).
Therefore, in both cases, the inference (p → q) ∧ (q → r) ⇒ (p → r) holds
true.
Question 5
Question
Let p, q, and r be propositions. Show that (p ∧ q) ∨ (p ∧ r) is logically equivalent
to p ∧ (q ∨ r).
Solution
To show that (p ∧ q) ∨ (p ∧ r) is logically equivalent to p ∧ (q ∨ r), we can use
the laws of logic to simplify both expressions and show that they are the same.
Step 1: Apply distribution using the distributive law (a ∧ b) ∨ (a ∧ c) ≡
a ∧ (b ∨ c).
(p ∧ q) ∨ (p ∧ r) ≡ p ∧ (q ∨ r)
Therefore, (p ∧ q) ∨ (p ∧ r) is indeed logically equivalent to p ∧ (q ∨ r).
3 Question 6
Question
Let p, q, and r be propositional variables. Determine whether the following
argument is valid:
(p ∧ q) → r,
p → (q ∧ r) ⊨ p → r
Solution
To determine whether the argument is valid, we will use the method of natural
deduction to show that the conclusion p → r can be derived from the premises
(p ∧ q) → r and p → (q ∧ r).
Step 1: Assume the premise (p ∧ q) → r and p → (q ∧ r).
Step 2: Using the premise p → (q ∧ r), we can conclude that p → q and
p → r by the property of implication.
Step 3: From p → q and p, we can derive q using the property of modus
ponens.
Step 4: Now, we can apply the premise (p∧q) → r to show that (p∧q) → r.
Step 5: Combining (p ∧ q) → r with p ∧ q, we can derive r using modus
ponens.
Step 6: Since we have shown that r follows from p∧q, and we have previously
shown that q follows from p, we can conclude that r follows from p.
Step 7: Therefore, we have proved that p → r can be derived from the
premises (p ∧ q) → r and p → (q ∧ r).
Since we have successfully derived the conclusion from the premises, the
argument is valid.
Question 7
Question
Let p, q, and r be propositions. Show that the given statement is a tautology:
(p ⇒ q) ∨ (q ⇒ r) ∨ (r ⇒ p).
Solution
To show that the given statement is a tautology, we can use truth tables to
verify that the statement is true for all possible truth values of p, q, and r.
4 Step 1: Create the truth table for (p ⇒ q) ∨ (q ⇒ r) ∨ (r ⇒ p)
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p⇒q
T
T
F
F
T
T
T
T
q⇒r
T
F
T
T
T
F
T
T
r⇒p
T
T
T
T
F
T
T
T
(p ⇒ q) ∨ (q ⇒ r) ∨ (r ⇒ p)
T
T
T
T
T
T
T
T
Since the final column is always true (T ), the given statement (p ⇒ q)∨(q ⇒
r) ∨ (r ⇒ p) is a tautology.
Question 8
Question
Let p, q, r be propositional variables. Determine if the following argument is
valid:
Premise 1: (p ∧ q) → r
Premise 2: p
Conclusion: r
Solution
To determine whether the argument is valid, we will use the method of proof by
contradiction, assuming that the premises are true and the conclusion is false.
Step 1: Assume the conclusion ¬r and the premises are true.
Let’s assume that the conclusion ¬r is true, and the premises (p ∧ q) → r
and p are true.
Step 2: Use the premises to derive a contradiction.
From premise 2, we have p, and from premise 1, we have (p ∧ q) → r.
Step 3: Using Modus Ponens, we have:
(p ∧ q) → r
p
∴q→r
Step 4: Using Modus Ponens again, we have:
q→r
5 p
∴r
Step 5: Contradiction
We have derived r from our assumptions that ¬r, leading to a contradiction.
Hence, our assumption is false.
Conclusion: The argument is valid, and the conclusion r follows logically
from the premises.
Question 9
Question
Let p, q, and r be propositions. Show that the following statement is a tautology:
(p → q) ∧ (q → r) → (p → r)
Solution
To show that the given statement is a tautology, we will construct a truth table
to verify if the statement holds for all possible truth values of p, q, and r.
Step 1: Create a truth table for the given statement
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
p→r
T
F
T
F
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
T
T
T
T
T
Step 2: Analyze the truth table
From the truth table, we can see that the statement (p → q) ∧ (q → r) →
(p → r) evaluates to true for all possible truth values of p, q, and r. Thus, we
have shown that the given statement is a tautology.
Question 10
Question
Let p and q be propositions such that the compound proposition (p∧q)∨(¬p∧¬q)
is false. Determine whether the proposition ¬p ∨ ¬q is true or false.
6 Solution
To determine whether the proposition ¬p ∨ ¬q is true or false, we will first
analyze the truth values of the compound proposition (p ∧ q) ∨ (¬p ∧ ¬q).
Step 1: Find the truth values of (p ∧ q) and (¬p ∧ ¬q).
Since the compound proposition (p ∧ q) ∨ (¬p ∧ ¬q) is false, either (p ∧ q) or
(¬p ∧ ¬q) or both must be false.
Step 2: Determine the truth values of p and q by analyzing (p ∧ q)
and (¬p ∧ ¬q).
If (p∧q) is false, then either p is false or q is false or both are false. Similarly,
if (¬p ∧ ¬q) is false, then either ¬p is false (meaning p is true) or ¬q is false
(meaning q is true) or both are false.
We summarize the possibilities in the truth table below:
p
¬p ∧ ¬q
T
F
T
T
F
T
F
T
q
(p ∧ q) ∨ (¬p ∧ ¬q)
T
F
F
T
T
T
F
F
p∧q
¬p
¬q
T
F
F
F
F
T
F
T
F
F
T
T
From the truth table, we see that either p is true and q is false, or p is false
and q is true for the compound proposition (p ∧ q) ∨ (¬p ∧ ¬q) to be false.
Step 3: Using the values from Step 2, determine the truth value
of ¬p ∨ ¬q.
If p is true and q is false, then ¬p is false and ¬q is true. Therefore, ¬p ∨ ¬q
is true.
If p is false and q is true, then both ¬p and ¬q are true. Therefore, ¬p ∨ ¬q
is true.
Hence, the proposition ¬p ∨ ¬q is true.
Question 11
Question
Let p, q, and r be propositions. Prove or disprove the following statement by
either providing a truth table or a counterexample:
(p ∧ q) → r ≡ (p → r) ∨ (q → r)
7 Solution
We will prove the equivalence of the given statement by constructing a truth
table for both sides and comparing the truth values.
Step 1: Create a truth table for (p ∧ q) → r and (p → r) ∨ (q → r).
p
(p → r) ∨ (q → r)
T
T
T
F
T
T
T
T
F
T
F
T
F
T
F
T
q
r
p∧q
(p ∧ q) → r
p→r
q→r
T
T
T
T
T
T
T
F
T
F
F
F
F
T
F
T
T
T
F
F
F
T
F
T
T
T
F
T
T
T
T
F
F
T
T
F
F
T
F
T
T
T
F
F
F
T
T
T
Step 2: Analyze the truth values of both sides. From the truth table,
we can see that both sides of the equivalence have the same truth values for all
possible truth values of p, q, and r.
Thus, we have proved that (p ∧ q) → r ≡ (p → r) ∨ (q → r).
Question 12
Question
Consider the following proposition:
(P → Q) ∧ (Q → R) ∧ (R → P ).
Determine whether the proposition is a tautology, a contradiction, or contingent. Justify your answer.
Solution
To determine whether the proposition (P → Q) ∧ (Q → R) ∧ (R → P ) is a
tautology, a contradiction, or contingent, we need to analyze all possible truth
values for P , Q, and R.
Step 1: List all possible truth values We will construct a truth table
to consider all possible combinations of truth values for P , Q, and R:
8 P
(P → Q) ∧ (Q → R) ∧ (R → P )
T
T
T
F
T
F
T
F
F
F
F
F
F
T
F
T
Q
R
P →Q
Q→R
R→P
T
T
T
T
T
T
F
T
F
T
F
T
F
T
T
F
F
F
T
T
T
T
T
T
F
T
F
T
F
T
F
T
T
T
T
F
F
T
T
T
Step 2: Interpret the truth values From the truth table, we can see
that the proposition (P → Q) ∧ (Q → R) ∧ (R → P ) is false for some truth
value combinations (i.e., when P is true and Q is false, or when P is false and
Q is true).
Step 3: Conclusion Since the proposition is not true for all possible truth
values, it is neither a tautology nor a contradiction. Therefore, the proposition
is contingent.
Question 13
Question
Let p, q, and r be propositions. Use logical equivalences to show that (p ∧ q) ∨
(¬p ∧ r) is logically equivalent to (p ∨ r) ∧ (q ∨ r).
Solution
To prove that (p ∧ q) ∨ (¬p ∧ r) is logically equivalent to (p ∨ r) ∧ (q ∨ r), we will
apply various logical equivalences step by step.
Step 1: Apply Distribution Law: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Step 2: Apply De Morgan’s Law: ¬p ≡ p → False
Step 3: Apply Distribution Law again: (p ∧ q) ∨ (p ∧ r) ≡ p ∧ (q ∨ r)
Step 4: Applying the associative law of logical OR: p∧(q∨r) ≡ (p∧q)∨(p∧r)
Since we have shown that both expressions are equivalent through a series of
logical equivalences, we have proved that (p ∧ q) ∨ (¬p ∧ r) is logically equivalent
to (p ∨ r) ∧ (q ∨ r).
9 Question 14
Question
Let p, q, and r be propositions. Show that the proposition (p ∧ q) ∨ (p ∧ r) is
logically equivalent to p ∧ (q ∨ r) using truth tables.
Solution
To show that two propositions are logically equivalent, we need to show that
they have the same truth values for all possible truth values of their component
propositions. We will use a truth table to compare the truth values of (p ∧ q) ∨
(p ∧ r) and p ∧ (q ∨ r).
Step 1: Create a truth table for (p ∧ q) ∨ (p ∧ r).
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
p∧q
T
T
F
F
F
F
F
F
r
T
F
T
F
T
F
T
F
p∧r
T
F
T
F
F
F
F
F
(p ∧ q) ∨ (p ∧ r)
T
T
T
F
F
F
F
F
Step 2: Create a truth table for p ∧ (q ∨ r).
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
q∨r
T
T
T
F
T
T
T
F
p ∧ (q ∨ r)
T
T
T
F
F
F
F
F
Step 3: Compare the truth values of the two propositions.
From the truth tables, we can see that both propositions 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 15
Question
Let p, q, and r be propositions such that (p → q) ∧ (q → r) → p. Show that
this proposition is a tautology using a truth table.
10 Solution
To show that the proposition (p → q) ∧ (q → r) → p is a tautology, we will
construct a truth table for all possible truth values of p, q, and r.
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
(p → q)
T
T
F
F
T
T
T
T
r
T
F
T
F
T
F
T
F
(q → r)
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
(p → q) ∧ (q → r) → p
T
T
T
T
T
T
T
T
In the above truth table, the column (p → q) ∧ (q → r) → p is always
true regardless of the truth values of p, q, and r. This means that the original
proposition is a tautology.
Question 16
Question
Let p and q be propositions. Show that the proposition (p → q) → (¬q → ¬p)
is a tautology using a truth table.
Solution
To show that the proposition (p → q) → (¬q → ¬p) is a tautology, we will
create a truth table to check all possible truth values of p and q.
p
T
T
F
F
q
T
F
T
F
¬p
F
F
T
T
¬q
F
T
F
T
(p → q)
T
F
T
T
(¬q → ¬p)
T
F
T
T
(p → q) → (¬q → ¬p)
T
T
T
T
Since the final column of the truth table is always true (T), the proposition
(p → q) → (¬q → ¬p) is a tautology.
11 Question 17
Question
Let p, q, and r be propositions. Show that (p ∨ q) ∧ (p ∨ r) is logically equivalent
to p ∨ (q ∧ r).
Solution
To show that (p ∨ q) ∧ (p ∨ r) is logically equivalent to p ∨ (q ∧ r), we need to
show that the truth values of these two compound propositions are the same
for all possible truth values of p, q, and r.
Step 1: Construct truth tables for both compound propositions.
First, let’s construct a truth table for (p ∨ q) ∧ (p ∨ r):
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
p∨q
T
T
T
T
T
T
F
F
r
T
F
T
F
T
F
T
F
p∨r
T
T
T
T
T
F
T
F
(p ∨ q) ∧ (p ∨ r)
T
T
T
T
T
F
F
F
Next, let’s construct a truth table for p ∨ (q ∧ r):
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
q∧r
T
F
F
F
T
F
F
F
p ∨ (q ∧ r)
T
T
T
T
T
F
F
F
Step 2: Compare the truth values of both compound propositions.
From the truth tables, we can see that the truth values of both compound
propositions are the same for all possible truth values of p, q, and r. Therefore,
we can conclude that (p ∨ q) ∧ (p ∨ r) is logically equivalent to p ∨ (q ∧ r).
12 Question 18
Question
Let p, q, and r be propositions such that:
(p → q) → r
¬r → (q → ¬p)
¬q
Determine the truth value of p.
Solution
1. We are given that ¬q. We will use this to find the truth value of q. 2. Since
¬q, then q is false. 3. By the second statement, ¬r → (q → ¬p), and since q
is false, we can simplify this to ¬r. 4. Therefore, r is false. 5. Finally, by the
first statement (p → q) → r, we know that (p → q) implies r. Since r is false,
(p → q) must also be false. 6. Since q is false, the only way for (p → q) to be
false is for p to be true. 7. Hence, the truth value of p is true.
Question 19
Question
Let p, q, and r be propositional variables. Show that the following statement is
a tautology:
(p ∧ q → r) → (p → (q → r))
Solution
To show that the given statement is a tautology, we will use a truth table to
check all possible truth values of p, q, and r.
Step 1: Create a truth table for the given statement.
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∧q
T
T
F
F
F
F
F
F
p∧q →r
T
F
T
T
T
T
T
T
q→r
T
F
T
T
T
F
T
T
p → (q → r)
T
T
T
T
T
T
T
T
Step 2: Analyze the truth table. From the truth table, we can see that
the last column, which represents the given statement, is true for all possible
13 truth values of p, q, and r. Since the statement is true for all possible truth
values of p, q, and r, we conclude that the statement is a tautology.
Question 20
Question
Let p, q, and r be propositional variables with the following premises:
(p → q) ∧ (q → r)
¬r
Determine whether the conclusion ¬p follows using propositional calculus
rules.
Solution
To determine if ¬p follows from the given premises, we will construct a proof
by contradiction.
Step 1: Assume p is true.
Step 2: Use the first premise (p → q) ∧ (q → r) to deduce q from p → q.
Since p is true and (p → q) is true, it follows that q is also true.
Step 3: Use the second premise ¬r to deduce ¬q from q → r.
Since r is false (due to ¬r), q → r is false. Therefore, q must also be false.
Step 4: From Steps 2 and 3, we have arrived at a contradiction: q is both
true and false.
Therefore, our assumption that p is true must be false.
Step 5: Conclude that ¬p follows from the given premises.
Hence, the conclusion ¬p follows using propositional calculus rules.
Question 21
Question
Let p, q, and r be propositions such that p → (q ∧ r) is false. Determine the
truth values of p, q, and r.
Solution
To determine the truth values of p, q, and r, we will consider the truth table
for the implication p → (q ∧ r). The truth table for an implication is as follows:
p
T
T
F
F
p→q
T
F
T
T
q
T
F
T
F
14 Given that p → (q ∧ r) is false, we observe that the only way this can occur
is when p is true and q ∧ r is false.
Step 1: Assigning values to p, q, and r based on the truth table
Since p must be true and q ∧ r must be false in order for p → (q ∧ r) to be false,
we have: - p = true - q ∧ r = false
Using the truth table for conjunction (∧), we find that q ∧ r is false only
when q and r are both false.
Step 2: Assigning values to q and r Therefore, we have: - q = false r = false
In conclusion, the truth values of p, q, and r are: - p is true - q is false - r
is false
Question 22
Question
Let p, q, and r be propositions. Show that (p ⇒ q) ∨ (q ⇒ r) is logically
equivalent to (p ∧ q) ⇒ r.
Solution
To show that (p ⇒ q) ∨ (q ⇒ r) is logically equivalent to (p ∧ q) ⇒ r, we will
construct truth tables for both statements and show that they have the same
truth values for all possible truth values of p, q, and r.
Step 1: Truth table for (p ⇒ q) ∨ (q ⇒ r)
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p⇒q
T
T
F
F
T
T
T
T
q⇒r
T
F
T
T
T
F
T
T
(p ⇒ q) ∨ (q ⇒ r)
T
T
T
T
T
T
T
T
Step 2: Truth table for (p ∧ q) ⇒ r
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∧q
T
T
F
F
F
F
F
F
15
(p ∧ q) ⇒ r
T
F
T
T
T
T
T
T Step 3: Conclusion From the truth tables above, we can see that (p ⇒
q) ∨ (q ⇒ r) and (p ∧ q) ⇒ r have the same truth values for all possible truth
values of p, q, and r. Therefore, (p ⇒ q) ∨ (q ⇒ r) is logically equivalent to
(p ∧ q) ⇒ r.
Question 23
Question
Let p, q, and r be propositional variables. Show that the following proposition
is a tautology:
(p ∧ q) → (p ∨ r)
Solution
To show that the proposition (p ∧ q) → (p ∨ r) is a tautology, we can use a truth
table to prove that the proposition is true for all possible truth values of p, q,
and r.
Step 1: Create the truth table for the proposition (p ∧ q) → (p ∨ r).
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∧q
T
T
F
F
F
F
F
F
p∨r
T
T
T
T
T
F
T
F
(p ∧ q) → (p ∨ r)
T
T
T
T
T
T
T
T
Since the last column of the truth table is always true, we can conclude that
the proposition (p ∧ q) → (p ∨ r) is a tautology.
Question 24
Question
Let p, q, and r be propositions. Show that the proposition (p ∧ q) ∨ (p ∧ r) is
logically equivalent to p ∧ (q ∨ r).
Solution
To show that two propositions are logically equivalent, we need to show that
they have the same truth value for all possible truth values of their component
propositions. We can do this by creating truth tables for both propositions and
checking if they are the same.
16 Step 1: Create a truth table for (p ∧ q) ∨ (p ∧ r).
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
p∧q
T
T
F
F
F
F
F
F
r
T
F
T
F
T
F
T
F
p∧r
T
F
T
F
F
F
F
F
(p ∧ q) ∨ (p ∧ r)
T
T
T
F
F
F
F
F
Step 2: Create a truth table for p ∧ (q ∨ r).
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
q∨r
T
T
T
F
T
T
T
F
p ∧ (q ∨ r)
T
T
T
F
F
F
F
F
Step 3: Compare the two truth tables. After comparing the truth
values of both propositions, we can see that (p ∧ q) ∨ (p ∧ r) and p ∧ (q ∨ r)
have the same truth values for all possible combinations of p, q, and r. Hence,
(p ∧ q) ∨ (p ∧ r) is logically equivalent to p ∧ (q ∨ r).
Question 25
Question
Let p and q be propositions. Show that the statement (p → q) ∧ (q → p) is
logically equivalent to p ↔ q.
Solution
To show that (p → q) ∧ (q → p) is logically equivalent to p ↔ q, we need to
show that they have the same truth values for all possible truth values of p and
q.
Step 1: Construct the truth table for (p → q) ∧ (q → p).
p
T
T
F
F
q
T
F
T
F
p→q
T
F
T
T
q→p
T
T
F
T
17
(p → q) ∧ (q → p)
T
F
F
T Step 2: Construct the truth table for p ↔ q.
p
T
T
F
F
p↔q
T
F
F
T
q
T
F
T
F
Step 3: Compare the truth tables for (p → q) ∧ (q → p) and p ↔ q.
From the truth tables, we observe that both (p → q) ∧ (q → p) and p ↔ q
have the same truth values for all combinations of p and q. Hence, we can
conclude that (p → q) ∧ (q → p) is logically equivalent to p ↔ q.
Question 26
Question
Let p, q, and r be propositions. Show that (p ∧ q) ∨ (p ∧ r) is logically equivalent
to p ∧ (q ∨ r).
Solution
To show that (p ∧ q) ∨ (p ∧ r) is logically equivalent to p ∧ (q ∨ r), we can perform
a series of logical equivalences using the basic laws of propositional logic.
Step 1: Apply the Distributive Law
(p ∧ q) ∨ (p ∧ r)
= p ∧ (q ∨ r)
Step 2: Commutativity of ∨
p ∧ (q ∨ r)
= p ∧ (r ∨ q)
Step 3: Commutativity of ∧
p ∧ (r ∨ q)
= (r ∨ q) ∧ p
Step 4: Apply the Distributive Law (Reverse)
(r ∨ q) ∧ p
= (p ∧ r) ∨ (p ∧ q)
Therefore, (p ∧ q) ∨ (p ∧ r) is logically equivalent to p ∧ (q ∨ r).
18 Question 27
Question
Let p and q be propositions. Show that (p → q) ∨ (q → p) is a tautology.
Solution
To show that (p → q) ∨ (q → p) is a tautology, we will construct a truth table
to check all possible combinations of truth values for p and q.
p
T
T
F
F
q
T
F
T
F
p→q
T
F
T
T
q→p
T
T
F
T
(p → q) ∨ (q → p)
T
T
T
T
Since the final column consists of all true values, we can conclude that (p →
q) ∨ (q → p) is a tautology.
Question 28
Question
Let p, q, and r be propositional variables. Determine whether the following
argument is valid:
(p ∧ q) ⇒ r, p ⇒ q, ¬r
¬p
Solution
To determine the validity of the argument, we will use the method of proof by
contradiction. We will assume that the premises are true and the conclusion is
false, and then derive a contradiction.
Step 1: Assume the premises are true and the conclusion is false:
1. (p ∧ q) ⇒ r
(Premise)
2. p ⇒ q
(Premise)
3. ¬r
(Premise)
4. ¬p
(Assumption for contradiction)
Step 2: Use premises (1) and (2) to derive r:
5. p
(Assumption)
6. q
(Modus Ponens on 2 and 5)
7. p ∧ q
8. r
(Conjunction of 5 and 6)
(Modus Ponens on 1 and 7)
19 Step 3: Derive a contradiction:
9. r
(From Step 8)
10. ¬r
(From 3)
11. False
(Contradiction from 9 and 10)
Since assuming ¬p led to a contradiction, the argument is valid.
Question 29
Question
Let p, q, and r be 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 can use truth
tables.
Step 1: Create a truth table for the given proposition
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
p→r
T
F
T
F
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
T
T
T
T
T
Step 2: Analyze the truth table Since the final column of the truth
table consists only of true values, we can conclude that the proposition (p →
q) ∧ (q → r) → (p → r) is a tautology.
Question 30
Question
Let p, q, and r be propositions. Determine whether the following argument is
valid:
”If p then q. If q then r. Therefore, if p then r.”
20 Solution
To determine the validity of the argument, we can use the rules of implication in propositional logic. Specifically, we will use the transitive property of
implication.
Step 1: Express the given statements as logical implications:
Statement 1: ”If p then q” can be expressed as p → q.
Statement 2: ”If q then r” can be expressed as q → r.
Conclusion: ”If p then r” can be expressed as p → r.
Step 2: Apply the transitive property of implication. According to the
transitive property of implication, if p → q and q → r are true, then p → r is
also true.
Step 3: Use truth tables to check the validity of the argument:
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
p→r
T
F
T
F
T
T
T
T
Step 4: Conclusion From the truth table, we see that the statement p → r
is not always true when p → q and q → r are true. Therefore, the argument is
not always valid.
Question 31
Question
Let p, q, and r be propositions. Show that (p → q) ∧ (q → r) → (p → r) is a
tautology using a truth table.
Solution
To show that (p → q) ∧ (q → r) → (p → r) is a tautology, we will construct a
truth table for all possible truth values of p, q, and r, and show that the final
column is always true.
21 p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
p→r
T
F
T
F
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
T
T
T
T
T
As shown in the truth table, the final column is always true regardless of
the truth values of p, q, and r. Therefore, (p → q) ∧ (q → r) → (p → r) is a
tautology.
Question 32
Question
Use natural deduction to prove the following statement: (p → q) ∧ (q → r) ⊢
p→r
Solution
To prove (p → q) ∧ (q → r) ⊢ p → r using natural deduction, we will assume
(p → q) ∧ (q → r) as a premise and derive p → r.
Step 1: Assume (p → q) ∧ (q → r) as a premise.
Step 2: Using conjunction elimination, separate the conjuncts (p → q) and
(q → r).
1. (p → q) ∧ (q → r) Premise
2. p → q
Conjunction Elimination from (1)
3. q → r
Conjunction Elimination from (1)
Step 3: Assume p.
Step 4: Using modus ponens with p → q and p, derive q.
4. p
5. p → q
6. q
Assumption
Reiteration from (2)
Modus Ponens from (5) and (4)
Step 5: Using modus ponens with q → r and q, derive r.
7. q
8. q → r
9. r
Reiteration from (6)
Reiteration from (3)
Modus Ponens from (8) and (7)
Step 6: Since we derived r under assumption p, we can infer p → r.
22 10. p → r (from 3, 4-9)
Therefore, we have shown that (p → q) ∧ (q → r) ⊢ p → r using natural
deduction.
Question 33
Question
Let p, q, and r be propositions. Show that the proposition (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 truth
tables to verify that the compound proposition is true for all possible truth
values of p, q, and r.
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r) p → r
T
T
F
F
F
T
F
F
T
T
F
T
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
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 34
Question
Let p, q, r be propositional variables where: p: It is sunny today. q: It is cold
today. r: It is snowing today.
Consider the proposition: If it is sunny today, then it is not cold or it is
snowing. Write this proposition in terms of p, q, and r using logical connectives
(negation, conjunction, disjunction, implication).
23 Solution
Step 1: The given proposition can be written as follows:
p → (¬q ∨ r)
Therefore, the proposition ”If it is sunny today, then it is not cold or it is
snowing” can be represented in terms of p, q, and r using the logical connectives
of negation, disjunction, and implication.
Question 35
Question
Prove or disprove the following statement: ”If it is not raining or it is not cold,
then John will go for a run.”
Solution
To prove or disprove the statement, we will analyze the given proposition in
terms of logic and propositional calculus.
Let P denote the proposition ”It is raining”, Q denote the proposition ”It
is cold”, and R denote the proposition ”John will go for a run”.
The given statement can be written as: (¬P ∨ ¬Q) → R. This can be
translated into words as ”If it is not raining or it is not cold, then John will go
for a run.”
To prove or disprove this statement, we will construct a truth table for the
given proposition and check if the implication holds in all cases.
P
T
T
F
F
Q
T
F
T
F
¬P ∨ ¬Q
F
T
T
T
R
T
T
T
T
(¬P ∨ ¬Q) → R
T
T
T
T
Since the truth table shows that the implication holds in all cases, we can
conclude that the statement ”If it is not raining or it is not cold, then John will
go for a run” is true.
24 Question 2
Question
Let p, q, and r be propositions. Show that (p ∧ q) ∨ (p ∧ r) is equivalent to
p ∧ (q ∨ r) using logical equivalences.
Solution
To show that (p ∧ q) ∨ (p ∧ r) is equivalent to p ∧ (q ∨ r), we will use logical
equivalences step by step.
Step 1: Apply Distribution Law (∧ over ∨) to (p ∧ q) ∨ (p ∧ r).
(p ∧ q) ∨ (p ∧ r) ≡ p ∧ (q ∨ r)
Therefore, (p ∧ q) ∨ (p ∧ r) is equivalent to p ∧ (q ∨ r) by using logical
equivalences.
Question 3
Question
Let p and q be propositional variables. Show that the proposition (p → q) ↔
(¬p ∨ q) is a tautology using truth tables.
Solution
To show that a proposition is a tautology, we need to show that it is true for all
possible truth values of its propositional variables.
p
T
T
F
F
q
T
F
T
F
¬p
F
F
T
T
¬p ∨ q
T
F
T
T
p→q
T
F
T
T
(p → q) ↔ (¬p ∨ q)
T
T
T
T
Step 1: Construct a truth table showing the truth values of p, q, ¬p,
¬p ∨ q, p → q, and (p → q) ↔ (¬p ∨ q).
Step 2: Fill in the truth values of ¬p, ¬p∨q, p → q, and (p → q) ↔ (¬p∨q)
based on the truth values of p and q.
Step 3: Verify that the final column in the truth table, which represents
the proposition (p → q) ↔ (¬p ∨ q), is true for all possible combinations
of truth values of p and q.
Since the final column of the truth table consists of all ”T” values, we
conclude that the proposition (p → q) ↔ (¬p ∨ q) is a tautology.
2 Question 4
Question
Let p, q, r be propositions. Prove or disprove the following inference:
(p → q) ∧ (q → r) ⇒ (p → r)
Solution
To prove or disprove the given inference, we will consider both cases.
Case 1: Assume (p → q) ∧ (q → r) is true, but (p → r) is false.
In this case: - If (p → q) is true, then either p is false or q is true. - If (q → r)
is true, then either q is false or r is true.
Since we are assuming (p → r) is false, this means if p is true, then r must
be false.
Therefore, the assumption that (p → r) is false contradicts the given premises
(p → q) ∧ (q → r). Thus, in this case, the inference holds.
Case 2: Assume (p → r) is true, but (p → q) ∧ (q → r) is false.
In this case: - If (p → r) is true, then either p is false or r is true.
Since we are assuming (p → q) ∧ (q → r) is false, this means that either p is
true and q is false, or q is true and r is false.
However, the assumption that (p → r) is true contradicts the given premises
(p → q) ∧ (q → r).
Therefore, in both cases, the inference (p → q) ∧ (q → r) ⇒ (p → r) holds
true.
Question 5
Question
Let p, q, and r be propositions. Show that (p ∧ q) ∨ (p ∧ r) is logically equivalent
to p ∧ (q ∨ r).
Solution
To show that (p ∧ q) ∨ (p ∧ r) is logically equivalent to p ∧ (q ∨ r), we can use
the laws of logic to simplify both expressions and show that they are the same.
Step 1: Apply distribution using the distributive law (a ∧ b) ∨ (a ∧ c) ≡
a ∧ (b ∨ c).
(p ∧ q) ∨ (p ∧ r) ≡ p ∧ (q ∨ r)
Therefore, (p ∧ q) ∨ (p ∧ r) is indeed logically equivalent to p ∧ (q ∨ r).
3 Question 6
Question
Let p, q, and r be propositional variables. Determine whether the following
argument is valid:
(p ∧ q) → r,
p → (q ∧ r) ⊨ p → r
Solution
To determine whether the argument is valid, we will use the method of natural
deduction to show that the conclusion p → r can be derived from the premises
(p ∧ q) → r and p → (q ∧ r).
Step 1: Assume the premise (p ∧ q) → r and p → (q ∧ r).
Step 2: Using the premise p → (q ∧ r), we can conclude that p → q and
p → r by the property of implication.
Step 3: From p → q and p, we can derive q using the property of modus
ponens.
Step 4: Now, we can apply the premise (p∧q) → r to show that (p∧q) → r.
Step 5: Combining (p ∧ q) → r with p ∧ q, we can derive r using modus
ponens.
Step 6: Since we have shown that r follows from p∧q, and we have previously
shown that q follows from p, we can conclude that r follows from p.
Step 7: Therefore, we have proved that p → r can be derived from the
premises (p ∧ q) → r and p → (q ∧ r).
Since we have successfully derived the conclusion from the premises, the
argument is valid.
Question 7
Question
Let p, q, and r be propositions. Show that the given statement is a tautology:
(p ⇒ q) ∨ (q ⇒ r) ∨ (r ⇒ p).
Solution
To show that the given statement is a tautology, we can use truth tables to
verify that the statement is true for all possible truth values of p, q, and r.
4 Step 1: Create the truth table for (p ⇒ q) ∨ (q ⇒ r) ∨ (r ⇒ p)
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p⇒q
T
T
F
F
T
T
T
T
q⇒r
T
F
T
T
T
F
T
T
r⇒p
T
T
T
T
F
T
T
T
(p ⇒ q) ∨ (q ⇒ r) ∨ (r ⇒ p)
T
T
T
T
T
T
T
T
Since the final column is always true (T ), the given statement (p ⇒ q)∨(q ⇒
r) ∨ (r ⇒ p) is a tautology.
Question 8
Question
Let p, q, r be propositional variables. Determine if the following argument is
valid:
Premise 1: (p ∧ q) → r
Premise 2: p
Conclusion: r
Solution
To determine whether the argument is valid, we will use the method of proof by
contradiction, assuming that the premises are true and the conclusion is false.
Step 1: Assume the conclusion ¬r and the premises are true.
Let’s assume that the conclusion ¬r is true, and the premises (p ∧ q) → r
and p are true.
Step 2: Use the premises to derive a contradiction.
From premise 2, we have p, and from premise 1, we have (p ∧ q) → r.
Step 3: Using Modus Ponens, we have:
(p ∧ q) → r
p
∴q→r
Step 4: Using Modus Ponens again, we have:
q→r
5 p
∴r
Step 5: Contradiction
We have derived r from our assumptions that ¬r, leading to a contradiction.
Hence, our assumption is false.
Conclusion: The argument is valid, and the conclusion r follows logically
from the premises.
Question 9
Question
Let p, q, and r be propositions. Show that the following statement is a tautology:
(p → q) ∧ (q → r) → (p → r)
Solution
To show that the given statement is a tautology, we will construct a truth table
to verify if the statement holds for all possible truth values of p, q, and r.
Step 1: Create a truth table for the given statement
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
p→r
T
F
T
F
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
T
T
T
T
T
Step 2: Analyze the truth table
From the truth table, we can see that the statement (p → q) ∧ (q → r) →
(p → r) evaluates to true for all possible truth values of p, q, and r. Thus, we
have shown that the given statement is a tautology.
Question 10
Question
Let p and q be propositions such that the compound proposition (p∧q)∨(¬p∧¬q)
is false. Determine whether the proposition ¬p ∨ ¬q is true or false.
6 Solution
To determine whether the proposition ¬p ∨ ¬q is true or false, we will first
analyze the truth values of the compound proposition (p ∧ q) ∨ (¬p ∧ ¬q).
Step 1: Find the truth values of (p ∧ q) and (¬p ∧ ¬q).
Since the compound proposition (p ∧ q) ∨ (¬p ∧ ¬q) is false, either (p ∧ q) or
(¬p ∧ ¬q) or both must be false.
Step 2: Determine the truth values of p and q by analyzing (p ∧ q)
and (¬p ∧ ¬q).
If (p∧q) is false, then either p is false or q is false or both are false. Similarly,
if (¬p ∧ ¬q) is false, then either ¬p is false (meaning p is true) or ¬q is false
(meaning q is true) or both are false.
We summarize the possibilities in the truth table below:
p
¬p ∧ ¬q
T
F
T
T
F
T
F
T
q
(p ∧ q) ∨ (¬p ∧ ¬q)
T
F
F
T
T
T
F
F
p∧q
¬p
¬q
T
F
F
F
F
T
F
T
F
F
T
T
From the truth table, we see that either p is true and q is false, or p is false
and q is true for the compound proposition (p ∧ q) ∨ (¬p ∧ ¬q) to be false.
Step 3: Using the values from Step 2, determine the truth value
of ¬p ∨ ¬q.
If p is true and q is false, then ¬p is false and ¬q is true. Therefore, ¬p ∨ ¬q
is true.
If p is false and q is true, then both ¬p and ¬q are true. Therefore, ¬p ∨ ¬q
is true.
Hence, the proposition ¬p ∨ ¬q is true.
Question 11
Question
Let p, q, and r be propositions. Prove or disprove the following statement by
either providing a truth table or a counterexample:
(p ∧ q) → r ≡ (p → r) ∨ (q → r)
7 Solution
We will prove the equivalence of the given statement by constructing a truth
table for both sides and comparing the truth values.
Step 1: Create a truth table for (p ∧ q) → r and (p → r) ∨ (q → r).
p
(p → r) ∨ (q → r)
T
T
T
F
T
T
T
T
F
T
F
T
F
T
F
T
q
r
p∧q
(p ∧ q) → r
p→r
q→r
T
T
T
T
T
T
T
F
T
F
F
F
F
T
F
T
T
T
F
F
F
T
F
T
T
T
F
T
T
T
T
F
F
T
T
F
F
T
F
T
T
T
F
F
F
T
T
T
Step 2: Analyze the truth values of both sides. From the truth table,
we can see that both sides of the equivalence have the same truth values for all
possible truth values of p, q, and r.
Thus, we have proved that (p ∧ q) → r ≡ (p → r) ∨ (q → r).
Question 12
Question
Consider the following proposition:
(P → Q) ∧ (Q → R) ∧ (R → P ).
Determine whether the proposition is a tautology, a contradiction, or contingent. Justify your answer.
Solution
To determine whether the proposition (P → Q) ∧ (Q → R) ∧ (R → P ) is a
tautology, a contradiction, or contingent, we need to analyze all possible truth
values for P , Q, and R.
Step 1: List all possible truth values We will construct a truth table
to consider all possible combinations of truth values for P , Q, and R:
8 P
(P → Q) ∧ (Q → R) ∧ (R → P )
T
T
T
F
T
F
T
F
F
F
F
F
F
T
F
T
Q
R
P →Q
Q→R
R→P
T
T
T
T
T
T
F
T
F
T
F
T
F
T
T
F
F
F
T
T
T
T
T
T
F
T
F
T
F
T
F
T
T
T
T
F
F
T
T
T
Step 2: Interpret the truth values From the truth table, we can see
that the proposition (P → Q) ∧ (Q → R) ∧ (R → P ) is false for some truth
value combinations (i.e., when P is true and Q is false, or when P is false and
Q is true).
Step 3: Conclusion Since the proposition is not true for all possible truth
values, it is neither a tautology nor a contradiction. Therefore, the proposition
is contingent.
Question 13
Question
Let p, q, and r be propositions. Use logical equivalences to show that (p ∧ q) ∨
(¬p ∧ r) is logically equivalent to (p ∨ r) ∧ (q ∨ r).
Solution
To prove that (p ∧ q) ∨ (¬p ∧ r) is logically equivalent to (p ∨ r) ∧ (q ∨ r), we will
apply various logical equivalences step by step.
Step 1: Apply Distribution Law: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Step 2: Apply De Morgan’s Law: ¬p ≡ p → False
Step 3: Apply Distribution Law again: (p ∧ q) ∨ (p ∧ r) ≡ p ∧ (q ∨ r)
Step 4: Applying the associative law of logical OR: p∧(q∨r) ≡ (p∧q)∨(p∧r)
Since we have shown that both expressions are equivalent through a series of
logical equivalences, we have proved that (p ∧ q) ∨ (¬p ∧ r) is logically equivalent
to (p ∨ r) ∧ (q ∨ r).
9 Question 14
Question
Let p, q, and r be propositions. Show that the proposition (p ∧ q) ∨ (p ∧ r) is
logically equivalent to p ∧ (q ∨ r) using truth tables.
Solution
To show that two propositions are logically equivalent, we need to show that
they have the same truth values for all possible truth values of their component
propositions. We will use a truth table to compare the truth values of (p ∧ q) ∨
(p ∧ r) and p ∧ (q ∨ r).
Step 1: Create a truth table for (p ∧ q) ∨ (p ∧ r).
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
p∧q
T
T
F
F
F
F
F
F
r
T
F
T
F
T
F
T
F
p∧r
T
F
T
F
F
F
F
F
(p ∧ q) ∨ (p ∧ r)
T
T
T
F
F
F
F
F
Step 2: Create a truth table for p ∧ (q ∨ r).
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
q∨r
T
T
T
F
T
T
T
F
p ∧ (q ∨ r)
T
T
T
F
F
F
F
F
Step 3: Compare the truth values of the two propositions.
From the truth tables, we can see that both propositions 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 15
Question
Let p, q, and r be propositions such that (p → q) ∧ (q → r) → p. Show that
this proposition is a tautology using a truth table.
10 Solution
To show that the proposition (p → q) ∧ (q → r) → p is a tautology, we will
construct a truth table for all possible truth values of p, q, and r.
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
(p → q)
T
T
F
F
T
T
T
T
r
T
F
T
F
T
F
T
F
(q → r)
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r)
T
F
F
F
T
F
T
T
(p → q) ∧ (q → r) → p
T
T
T
T
T
T
T
T
In the above truth table, the column (p → q) ∧ (q → r) → p is always
true regardless of the truth values of p, q, and r. This means that the original
proposition is a tautology.
Question 16
Question
Let p and q be propositions. Show that the proposition (p → q) → (¬q → ¬p)
is a tautology using a truth table.
Solution
To show that the proposition (p → q) → (¬q → ¬p) is a tautology, we will
create a truth table to check all possible truth values of p and q.
p
T
T
F
F
q
T
F
T
F
¬p
F
F
T
T
¬q
F
T
F
T
(p → q)
T
F
T
T
(¬q → ¬p)
T
F
T
T
(p → q) → (¬q → ¬p)
T
T
T
T
Since the final column of the truth table is always true (T), the proposition
(p → q) → (¬q → ¬p) is a tautology.
11 Question 17
Question
Let p, q, and r be propositions. Show that (p ∨ q) ∧ (p ∨ r) is logically equivalent
to p ∨ (q ∧ r).
Solution
To show that (p ∨ q) ∧ (p ∨ r) is logically equivalent to p ∨ (q ∧ r), we need to
show that the truth values of these two compound propositions are the same
for all possible truth values of p, q, and r.
Step 1: Construct truth tables for both compound propositions.
First, let’s construct a truth table for (p ∨ q) ∧ (p ∨ r):
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
p∨q
T
T
T
T
T
T
F
F
r
T
F
T
F
T
F
T
F
p∨r
T
T
T
T
T
F
T
F
(p ∨ q) ∧ (p ∨ r)
T
T
T
T
T
F
F
F
Next, let’s construct a truth table for p ∨ (q ∧ r):
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
q∧r
T
F
F
F
T
F
F
F
p ∨ (q ∧ r)
T
T
T
T
T
F
F
F
Step 2: Compare the truth values of both compound propositions.
From the truth tables, we can see that the truth values of both compound
propositions are the same for all possible truth values of p, q, and r. Therefore,
we can conclude that (p ∨ q) ∧ (p ∨ r) is logically equivalent to p ∨ (q ∧ r).
12 Question 18
Question
Let p, q, and r be propositions such that:
(p → q) → r
¬r → (q → ¬p)
¬q
Determine the truth value of p.
Solution
1. We are given that ¬q. We will use this to find the truth value of q. 2. Since
¬q, then q is false. 3. By the second statement, ¬r → (q → ¬p), and since q
is false, we can simplify this to ¬r. 4. Therefore, r is false. 5. Finally, by the
first statement (p → q) → r, we know that (p → q) implies r. Since r is false,
(p → q) must also be false. 6. Since q is false, the only way for (p → q) to be
false is for p to be true. 7. Hence, the truth value of p is true.
Question 19
Question
Let p, q, and r be propositional variables. Show that the following statement is
a tautology:
(p ∧ q → r) → (p → (q → r))
Solution
To show that the given statement is a tautology, we will use a truth table to
check all possible truth values of p, q, and r.
Step 1: Create a truth table for the given statement.
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∧q
T
T
F
F
F
F
F
F
p∧q →r
T
F
T
T
T
T
T
T
q→r
T
F
T
T
T
F
T
T
p → (q → r)
T
T
T
T
T
T
T
T
Step 2: Analyze the truth table. From the truth table, we can see that
the last column, which represents the given statement, is true for all possible
13 truth values of p, q, and r. Since the statement is true for all possible truth
values of p, q, and r, we conclude that the statement is a tautology.
Question 20
Question
Let p, q, and r be propositional variables with the following premises:
(p → q) ∧ (q → r)
¬r
Determine whether the conclusion ¬p follows using propositional calculus
rules.
Solution
To determine if ¬p follows from the given premises, we will construct a proof
by contradiction.
Step 1: Assume p is true.
Step 2: Use the first premise (p → q) ∧ (q → r) to deduce q from p → q.
Since p is true and (p → q) is true, it follows that q is also true.
Step 3: Use the second premise ¬r to deduce ¬q from q → r.
Since r is false (due to ¬r), q → r is false. Therefore, q must also be false.
Step 4: From Steps 2 and 3, we have arrived at a contradiction: q is both
true and false.
Therefore, our assumption that p is true must be false.
Step 5: Conclude that ¬p follows from the given premises.
Hence, the conclusion ¬p follows using propositional calculus rules.
Question 21
Question
Let p, q, and r be propositions such that p → (q ∧ r) is false. Determine the
truth values of p, q, and r.
Solution
To determine the truth values of p, q, and r, we will consider the truth table
for the implication p → (q ∧ r). The truth table for an implication is as follows:
p
T
T
F
F
p→q
T
F
T
T
q
T
F
T
F
14 Given that p → (q ∧ r) is false, we observe that the only way this can occur
is when p is true and q ∧ r is false.
Step 1: Assigning values to p, q, and r based on the truth table
Since p must be true and q ∧ r must be false in order for p → (q ∧ r) to be false,
we have: - p = true - q ∧ r = false
Using the truth table for conjunction (∧), we find that q ∧ r is false only
when q and r are both false.
Step 2: Assigning values to q and r Therefore, we have: - q = false r = false
In conclusion, the truth values of p, q, and r are: - p is true - q is false - r
is false
Question 22
Question
Let p, q, and r be propositions. Show that (p ⇒ q) ∨ (q ⇒ r) is logically
equivalent to (p ∧ q) ⇒ r.
Solution
To show that (p ⇒ q) ∨ (q ⇒ r) is logically equivalent to (p ∧ q) ⇒ r, we will
construct truth tables for both statements and show that they have the same
truth values for all possible truth values of p, q, and r.
Step 1: Truth table for (p ⇒ q) ∨ (q ⇒ r)
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p⇒q
T
T
F
F
T
T
T
T
q⇒r
T
F
T
T
T
F
T
T
(p ⇒ q) ∨ (q ⇒ r)
T
T
T
T
T
T
T
T
Step 2: Truth table for (p ∧ q) ⇒ r
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∧q
T
T
F
F
F
F
F
F
15
(p ∧ q) ⇒ r
T
F
T
T
T
T
T
T Step 3: Conclusion From the truth tables above, we can see that (p ⇒
q) ∨ (q ⇒ r) and (p ∧ q) ⇒ r have the same truth values for all possible truth
values of p, q, and r. Therefore, (p ⇒ q) ∨ (q ⇒ r) is logically equivalent to
(p ∧ q) ⇒ r.
Question 23
Question
Let p, q, and r be propositional variables. Show that the following proposition
is a tautology:
(p ∧ q) → (p ∨ r)
Solution
To show that the proposition (p ∧ q) → (p ∨ r) is a tautology, we can use a truth
table to prove that the proposition is true for all possible truth values of p, q,
and r.
Step 1: Create the truth table for the proposition (p ∧ q) → (p ∨ r).
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p∧q
T
T
F
F
F
F
F
F
p∨r
T
T
T
T
T
F
T
F
(p ∧ q) → (p ∨ r)
T
T
T
T
T
T
T
T
Since the last column of the truth table is always true, we can conclude that
the proposition (p ∧ q) → (p ∨ r) is a tautology.
Question 24
Question
Let p, q, and r be propositions. Show that the proposition (p ∧ q) ∨ (p ∧ r) is
logically equivalent to p ∧ (q ∨ r).
Solution
To show that two propositions are logically equivalent, we need to show that
they have the same truth value for all possible truth values of their component
propositions. We can do this by creating truth tables for both propositions and
checking if they are the same.
16 Step 1: Create a truth table for (p ∧ q) ∨ (p ∧ r).
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
p∧q
T
T
F
F
F
F
F
F
r
T
F
T
F
T
F
T
F
p∧r
T
F
T
F
F
F
F
F
(p ∧ q) ∨ (p ∧ r)
T
T
T
F
F
F
F
F
Step 2: Create a truth table for p ∧ (q ∨ r).
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
q∨r
T
T
T
F
T
T
T
F
p ∧ (q ∨ r)
T
T
T
F
F
F
F
F
Step 3: Compare the two truth tables. After comparing the truth
values of both propositions, we can see that (p ∧ q) ∨ (p ∧ r) and p ∧ (q ∨ r)
have the same truth values for all possible combinations of p, q, and r. Hence,
(p ∧ q) ∨ (p ∧ r) is logically equivalent to p ∧ (q ∨ r).
Question 25
Question
Let p and q be propositions. Show that the statement (p → q) ∧ (q → p) is
logically equivalent to p ↔ q.
Solution
To show that (p → q) ∧ (q → p) is logically equivalent to p ↔ q, we need to
show that they have the same truth values for all possible truth values of p and
q.
Step 1: Construct the truth table for (p → q) ∧ (q → p).
p
T
T
F
F
q
T
F
T
F
p→q
T
F
T
T
q→p
T
T
F
T
17
(p → q) ∧ (q → p)
T
F
F
T Step 2: Construct the truth table for p ↔ q.
p
T
T
F
F
p↔q
T
F
F
T
q
T
F
T
F
Step 3: Compare the truth tables for (p → q) ∧ (q → p) and p ↔ q.
From the truth tables, we observe that both (p → q) ∧ (q → p) and p ↔ q
have the same truth values for all combinations of p and q. Hence, we can
conclude that (p → q) ∧ (q → p) is logically equivalent to p ↔ q.
Question 26
Question
Let p, q, and r be propositions. Show that (p ∧ q) ∨ (p ∧ r) is logically equivalent
to p ∧ (q ∨ r).
Solution
To show that (p ∧ q) ∨ (p ∧ r) is logically equivalent to p ∧ (q ∨ r), we can perform
a series of logical equivalences using the basic laws of propositional logic.
Step 1: Apply the Distributive Law
(p ∧ q) ∨ (p ∧ r)
= p ∧ (q ∨ r)
Step 2: Commutativity of ∨
p ∧ (q ∨ r)
= p ∧ (r ∨ q)
Step 3: Commutativity of ∧
p ∧ (r ∨ q)
= (r ∨ q) ∧ p
Step 4: Apply the Distributive Law (Reverse)
(r ∨ q) ∧ p
= (p ∧ r) ∨ (p ∧ q)
Therefore, (p ∧ q) ∨ (p ∧ r) is logically equivalent to p ∧ (q ∨ r).
18 Question 27
Question
Let p and q be propositions. Show that (p → q) ∨ (q → p) is a tautology.
Solution
To show that (p → q) ∨ (q → p) is a tautology, we will construct a truth table
to check all possible combinations of truth values for p and q.
p
T
T
F
F
q
T
F
T
F
p→q
T
F
T
T
q→p
T
T
F
T
(p → q) ∨ (q → p)
T
T
T
T
Since the final column consists of all true values, we can conclude that (p →
q) ∨ (q → p) is a tautology.
Question 28
Question
Let p, q, and r be propositional variables. Determine whether the following
argument is valid:
(p ∧ q) ⇒ r, p ⇒ q, ¬r
¬p
Solution
To determine the validity of the argument, we will use the method of proof by
contradiction. We will assume that the premises are true and the conclusion is
false, and then derive a contradiction.
Step 1: Assume the premises are true and the conclusion is false:
1. (p ∧ q) ⇒ r
(Premise)
2. p ⇒ q
(Premise)
3. ¬r
(Premise)
4. ¬p
(Assumption for contradiction)
Step 2: Use premises (1) and (2) to derive r:
5. p
(Assumption)
6. q
(Modus Ponens on 2 and 5)
7. p ∧ q
8. r
(Conjunction of 5 and 6)
(Modus Ponens on 1 and 7)
19 Step 3: Derive a contradiction:
9. r
(From Step 8)
10. ¬r
(From 3)
11. False
(Contradiction from 9 and 10)
Since assuming ¬p led to a contradiction, the argument is valid.
Question 29
Question
Let p, q, and r be 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 can use truth
tables.
Step 1: Create a truth table for the given proposition
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
p→r
T
F
T
F
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
T
T
T
T
T
Step 2: Analyze the truth table Since the final column of the truth
table consists only of true values, we can conclude that the proposition (p →
q) ∧ (q → r) → (p → r) is a tautology.
Question 30
Question
Let p, q, and r be propositions. Determine whether the following argument is
valid:
”If p then q. If q then r. Therefore, if p then r.”
20 Solution
To determine the validity of the argument, we can use the rules of implication in propositional logic. Specifically, we will use the transitive property of
implication.
Step 1: Express the given statements as logical implications:
Statement 1: ”If p then q” can be expressed as p → q.
Statement 2: ”If q then r” can be expressed as q → r.
Conclusion: ”If p then r” can be expressed as p → r.
Step 2: Apply the transitive property of implication. According to the
transitive property of implication, if p → q and q → r are true, then p → r is
also true.
Step 3: Use truth tables to check the validity of the argument:
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
p→r
T
F
T
F
T
T
T
T
Step 4: Conclusion From the truth table, we see that the statement p → r
is not always true when p → q and q → r are true. Therefore, the argument is
not always valid.
Question 31
Question
Let p, q, and r be propositions. Show that (p → q) ∧ (q → r) → (p → r) is a
tautology using a truth table.
Solution
To show that (p → q) ∧ (q → r) → (p → r) is a tautology, we will construct a
truth table for all possible truth values of p, q, and r, and show that the final
column is always true.
21 p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
p→r
T
F
T
F
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
T
T
T
T
T
As shown in the truth table, the final column is always true regardless of
the truth values of p, q, and r. Therefore, (p → q) ∧ (q → r) → (p → r) is a
tautology.
Question 32
Question
Use natural deduction to prove the following statement: (p → q) ∧ (q → r) ⊢
p→r
Solution
To prove (p → q) ∧ (q → r) ⊢ p → r using natural deduction, we will assume
(p → q) ∧ (q → r) as a premise and derive p → r.
Step 1: Assume (p → q) ∧ (q → r) as a premise.
Step 2: Using conjunction elimination, separate the conjuncts (p → q) and
(q → r).
1. (p → q) ∧ (q → r) Premise
2. p → q
Conjunction Elimination from (1)
3. q → r
Conjunction Elimination from (1)
Step 3: Assume p.
Step 4: Using modus ponens with p → q and p, derive q.
4. p
5. p → q
6. q
Assumption
Reiteration from (2)
Modus Ponens from (5) and (4)
Step 5: Using modus ponens with q → r and q, derive r.
7. q
8. q → r
9. r
Reiteration from (6)
Reiteration from (3)
Modus Ponens from (8) and (7)
Step 6: Since we derived r under assumption p, we can infer p → r.
22 10. p → r (from 3, 4-9)
Therefore, we have shown that (p → q) ∧ (q → r) ⊢ p → r using natural
deduction.
Question 33
Question
Let p, q, and r be propositions. Show that the proposition (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 truth
tables to verify that the compound proposition is true for all possible truth
values of p, q, and r.
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p→q
T
T
F
F
T
T
T
T
q→r
T
F
T
T
T
F
T
T
(p → q) ∧ (q → r) p → r
T
T
F
F
F
T
F
F
T
T
F
T
T
T
T
T
(p → q) ∧ (q → r) → (p → r)
T
T
T
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 34
Question
Let p, q, r be propositional variables where: p: It is sunny today. q: It is cold
today. r: It is snowing today.
Consider the proposition: If it is sunny today, then it is not cold or it is
snowing. Write this proposition in terms of p, q, and r using logical connectives
(negation, conjunction, disjunction, implication).
23 Solution
Step 1: The given proposition can be written as follows:
p → (¬q ∨ r)
Therefore, the proposition ”If it is sunny today, then it is not cold or it is
snowing” can be represented in terms of p, q, and r using the logical connectives
of negation, disjunction, and implication.
Question 35
Question
Prove or disprove the following statement: ”If it is not raining or it is not cold,
then John will go for a run.”
Solution
To prove or disprove the statement, we will analyze the given proposition in
terms of logic and propositional calculus.
Let P denote the proposition ”It is raining”, Q denote the proposition ”It
is cold”, and R denote the proposition ”John will go for a run”.
The given statement can be written as: (¬P ∨ ¬Q) → R. This can be
translated into words as ”If it is not raining or it is not cold, then John will go
for a run.”
To prove or disprove this statement, we will construct a truth table for the
given proposition and check if the implication holds in all cases.
P
T
T
F
F
Q
T
F
T
F
¬P ∨ ¬Q
F
T
T
T
R
T
T
T
T
(¬P ∨ ¬Q) → R
T
T
T
T
Since the truth table shows that the implication holds in all cases, we can
conclude that the statement ”If it is not raining or it is not cold, then John will
go for a run” is true.
24
Related Documents
- 2.1 Exponents Laws - Notes [Teacher]
- A Guide to Understanding Variables and Equations
- Trigonometric Limit Theorem: Applications in Calculations
- 1.4 Quadratics - Max or Min - Worksheet 1 [Answers]
- 1.3 Radicals - Worksheet 1 [Answers]
- 1.4 Quadratics - Max or Min - Notes [Teacher]
- 1.6 Quadratics - Roots - Notes [Teacher]
- 1.6 Quadratics - Roots - Worksheet 1 [Answers]
- 1.7 Quadratics - Linear Systems - Notes [Teacher]
- 1.7 Quadratics - Linear Systems - Worksheet 1 [Answers]
- 1.1 Functions, Domain, & Range - Notes [Teacher]
- Maximum and Minimum in Function Graphs: Determination and Understanding
- Graph Analysis: Functions, Domain, Range
- Mapping Functions of Two Variables Using Maple 13
- Matrix Multiplication in Linear Algebra
- 1.3 Radicals - Notes [Teacher]
- 1.0 Factoring - Notes
- 1.0 Factoring - Worksheet 1 [Questions + Answers]
- An Detailed Guide to Understanding Real Numbers
- 1.2 Function Notation - Textbook [Questions + Answers]
Logic and Propositional Calculus Question Bank Set 1
of 70
Recommended Documents
⏰ Deadline pressure?
Get your assignment done in just 3 hours. Quick, easy, and available 24/7.
Report
Tell us what’s wrong with it:
Thanks, got it!
We will moderate it soon!
Free up your schedule!
Our EduBirdie Experts Are Here for You 24/7! Just fill out a form and let us know how we can assist you.
Take 5 seconds to unlock
Enter your email below and get instant access to your document