6.1. Solutions Propositional Logic#
Solutions to Section 2.1
Solution to Exercise (1†)
\(p\) |
\(q\) |
\(p \vee q\) |
|---|---|---|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
\(p\) |
\(q\) |
\(p \wedge q\) |
|---|---|---|
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
\(p\) |
\(\lnot p\) |
|---|---|
0 |
1 |
1 |
0 |
Solution to Exercise (2†)
\(p\)
\(q\)
\(\overbrace{p\rightarrow q}^\text{A}\)
\(\overbrace{p\wedge (A)}^\text{B}\)
\((B)\rightarrow q\)
0
0
1
0
1
0
1
1
0
1
1
0
0
0
1
1
1
1
1
1
Since the proposition is always true, the proposition is a tautology.
\(p\)
\(q\)
\(r\)
\(\overbrace{p\rightarrow q}^\text{A}\)
\(\overbrace{q \rightarrow r}^\text{B}\)
\(\overbrace{(A)\wedge (B)}^\text{C}\)
\(\overbrace{p \rightarrow r}^\text{D}\)
\((C) \rightarrow (D)\)
0
0
0
1
1
1
1
1
0
0
1
1
1
1
1
1
0
1
0
1
0
0
1
1
0
1
1
1
1
1
1
1
1
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
1
1
0
1
0
0
0
1
1
1
1
1
1
1
1
1
Since the proposition is always true, the proposition is a tautology.
\(p\)
\(p\wedge \lnot p\)
0
0
1
0
Since the proposition is always false, the proposition is a contradiction.
\(p\)
\(q\)
\(\overbrace{p\vee q}^\text{A}\)
\(\overbrace{p\wedge q}^\text{B}\)
\((A)\rightarrow (B)\)
0
0
0
0
1
0
1
1
0
0
1
0
1
0
0
1
1
1
1
1
Since the proposition is sometimes true and sometimes false, the proposition is a contingency.
\(p\)
\(p\vee \lnot p\)
0
1
1
1
Since the proposition is always true, the proposition is a tautology.
\(p\)
\(q\)
\(\overbrace{p\wedge q}^\text{A}\)
\(\overbrace{p\vee q}^\text{B}\)
\((A)\rightarrow (B)\)
0
0
0
0
1
0
1
0
1
1
1
0
0
1
1
1
1
1
1
1
Since the proposition is always true, the proposition is a tautology.
Solution to Exercise (3†)
We will compare the truth tables of the subquestions to that of \(p \leftrightarrow q\):
\(p\) |
\(q\) |
\(p \leftrightarrow q\) |
|---|---|---|
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
\(p\)
\(q\)
\(\overbrace{p \rightarrow q}^\text{A}\)
\(\overbrace{q \rightarrow p}^\text{B}\)
\(A \wedge B\)
0
0
1
1
1
0
1
1
0
0
1
0
0
1
0
1
1
1
1
1
\(p\)
\(q\)
\(\overbrace{\lnot p}^\text{A}\)
\(\overbrace{\lnot q}^\text{B}\)
\(A \leftrightarrow B\)
0
0
1
1
1
0
1
1
0
0
1
0
0
1
0
1
1
0
0
1
\(p\)
\(q\)
\(\overbrace{p \rightarrow q}^\text{A}\)
\(\overbrace{\lnot p}^\text{B}\)
\(\overbrace{\lnot q}^\text{C}\)
\(\overbrace{B \rightarrow C}^\text{D}\)
\(A \wedge D\)
0
0
1
1
1
1
1
0
1
1
1
0
0
0
1
0
0
0
1
1
0
1
1
1
0
0
1
1
\(p\)
\(q\)
\(\overbrace{p \oplus q}^\text{A}\)
\(\lnot A\)
0
0
0
1
0
1
1
0
1
0
1
0
1
1
0
1
Solution to Exercise (4†)
\(p\) |
\(q\) |
\(r\) |
\(\overbrace{p\rightarrow q}^\text{A}\) |
\(\overbrace{A \rightarrow r}^\text{B}\) |
\(\overbrace{q \rightarrow r}^\text{C}\) |
\(\overbrace{p \rightarrow C}^\text{D}\) |
|---|---|---|---|---|---|---|
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Since the truth tables for the expressions (columns B and D) are different, they are not equivalent. As our counterexample take for instance: \(p=q=r=0\). Thus \(\rightarrow\) is not associative. \ What about \(\leftrightarrow\)?
Solution to Exercise (5†)
\(p \vee q\)
\(\lnot p \rightarrow q\)
Solution to Exercise (6†)
The four propositions are:
Galileo was not falsely accused and the Earth is the centre of the universe.
If the Earth moves then the Earth is not the centre of the universe.
The Earth moves if and only if the Earth is not the centre of the universe.
If the Earth moves the Galileo was falsely accused, but if the Earth is the centre of the universe then Galileo was not falsely accused.
Solution to Exercise (7†)
Converse If Sinterklaas brings you toys, you are good.
Contrapositive If Sinterklaas does not bring you toys, you are not good.
Converse If you need extra postage, then the package weighs more than one kilo.
Contrapositive If you do not need extra postage, then the package does not weigh more than one kilo.
Converse If I don’t eat courgette, I have a choice.
Contrapositive If I eat courgette, I don’t have a choice.
Solution to Exercise (8†)
The only card that satisfies this is the ten of hearts.
An ordinary deck has 4 cards that satisfy the condition of being a ten, and 13 cards that satisfy the condition of being a heart, the ten of hearts has been counted twice. So the total the amount of cards that satisfy all conditions is 16.
All cards that are not a ten will satisfy this condition, as well as the cards that are a ten and a heart, which is only the ten of hearts. So only three cards do not satisfy this condition, which are the ten of diamonds, ten of spades, and ten of clubs.
It’s easier to reason about the cards that do not satisfy the condition. All cards that are a ten and not a heart do not satisfy the condition, as well as all cards that are a heart and not a ten. There are 3 cards that are a ten and not a heart (ten of diamonds, ten of spades, and ten of clubs). There are 12 cards that are a heart and not a ten. So the total amount of cards that do not satisfy this condition is 15, which means that there are 37 cards that satisfy the condition.
Solution to Exercise (9†)
A \(\ast\) is used to indicate the step at which we can stop rewriting, as the equation will use \(\downarrow\) or other operators shown previously.
- \[\begin{split} \begin{align*} \lnot p & \equiv (\lnot p \wedge \lnot p)\\ & \equiv \lnot (p \vee p)\\ & \equiv p \downarrow p \end{align*}\end{split}\]
- \[\begin{split} \begin{align*} p \wedge q & \equiv \lnot (\lnot p \vee \lnot q)\\ & \equiv \lnot p \downarrow \lnot q \tag{$\ast$}\\ & \equiv (p \downarrow p) \downarrow (q \downarrow q) \end{align*}\end{split}\]
- \[\begin{split} \begin{align*} p \vee q & \equiv \lnot \lnot (p \vee q)\\ & \equiv \lnot (p \downarrow q) \tag{$\ast$}\\ & \equiv (p \downarrow q) \downarrow (p \downarrow q) \end{align*}\end{split}\]
- \[\begin{split} \begin{align*} p \rightarrow q & \equiv \lnot p \vee q \tag{$\ast$}\\ & \equiv (\lnot p \downarrow q) \downarrow (\lnot p \downarrow q) \\ & \equiv ((p \downarrow p) \downarrow q) \downarrow ((p \downarrow p) \downarrow q) \end{align*}\end{split}\]
- \[\begin{split} \begin{align*} p \leftrightarrow q & \equiv (p \rightarrow q) \wedge (q \rightarrow p) \tag{$\ast$}\\ & \equiv (((p \downarrow p) \downarrow q) \downarrow ((p \downarrow p) \downarrow q)) \wedge (((q \downarrow q) \downarrow p) \downarrow ((q \downarrow q) \downarrow q)) \\ & \equiv (((((p \downarrow p) \downarrow q) \downarrow ((p \downarrow p) \downarrow q)) \downarrow (((p \downarrow p) \downarrow q) \downarrow ((p \downarrow p) \downarrow q))) \notag\\ & \quad \downarrow ((((q \downarrow q) \downarrow p) \downarrow ((q \downarrow q) \downarrow p)) \downarrow (((q \downarrow q) \downarrow p) \downarrow ((q \downarrow q) \downarrow p)))) \end{align*}\end{split}\]
- \[\begin{split} \begin{align*} p \oplus q & \equiv (p \wedge \lnot q) \vee (\lnot p \wedge q) \tag{$\ast$}\\ & \equiv (p \wedge (q \downarrow q)) \vee ((p \downarrow p) \wedge q)\\ & \equiv ((p \downarrow p) \downarrow ((q \downarrow q) \downarrow (q \downarrow q))) \vee (((p \downarrow p) \downarrow (p \downarrow p)) \downarrow (q \downarrow q))\\ & \equiv ((((p \downarrow p) \downarrow ((q \downarrow q) \downarrow (q \downarrow q))) \downarrow (((p \downarrow p) \downarrow (p \downarrow p)) \downarrow (q \downarrow q))) \notag\\ & \quad \downarrow (((p \downarrow p) \downarrow ((q \downarrow q) \downarrow (q \downarrow q))) \downarrow (((p \downarrow p) \downarrow (p \downarrow p)) \downarrow (q \downarrow q)))) \end{align*}\end{split}\]
Solution to Exercise (10†)
A truth table for a formula containing two unique atoms will have 4 rows. Each of these 4 rows could have either a \(0\) or a \(1\) as result. Which means that there will be \(2^4\) unique truth tables for a formula containing 2 unique atoms.
\(p\)
\(q\)
\(p \wedge \lnot p\)
\(p \wedge q\)
\(p \wedge \lnot q\)
\(p\)
\(\lnot p \wedge q\)
\(q\)
\(\lnot(p \leftrightarrow q)\)
\(p \vee q\)
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
1
1
1
1
0
0
0
1
1
0
0
1
1
1
1
0
1
0
1
0
1
0
1
\(p\)
\(q\)
\(\lnot p \wedge \lnot q\)
\(p \leftrightarrow q\)
\(\lnot q\)
\(q \rightarrow p\)
\(\lnot p\)
\(p \rightarrow q\)
\(\lnot p \vee \lnot q \)
\(p \vee \lnot p\)
0
0
1
1
1
1
1
1
1
1
0
1
0
0
0
0
1
1
1
1
1
0
0
0
1
1
0
0
1
1
1
1
0
1
0
1
0
1
0
1
Given that we can create a formula for each of the possible truth table using these 5 operators. Furthermore, we know that there are only \(2^{2^{n}}\) possible truth tables, where \(n\) is the number of unique atoms. Given that every one of these truth tables has a corresponding formula using only the 5 operators, which we denote as \(f_i\), where \(1 \leq i \leq 2^{2^{n}} - 1\). Now take a formula, \(f'\), that uses the same unique atoms, but not necessarily the same operators from the set of 5 operators stated in the description. The truth table for the formula \(f'\) will be equal to one of the \(2^{2^{n}}\) possible truth tables, which also means that there is a \(f_i\) that is equivalent to \(f'\), so we can rewrite \(f'\)