Exercises – Long Day#
Exercise 1: Propositions#
Let \(P\) and \(Q\) be logical propositions.
We now form three new propositions:
\(u:\) “At least one of the propositions \(P\) and \(Q\) is true.”
\(v:\) “Exactly one of the propositions \(P\) and \(Q\) is false.”
\(w:\) “\(P\) is true and \(Q\) is false.”
Question a#
Write out the truth tables for the logical propositions \(u\), \(v\), and \(w\).
Hint
As in Example 1.2.1 in the textbook one can start by writing out a truth table in which all combinations of the truth values of the “atomic” logical expressions that are involved in the proposition are stated. In this case there are two such expressions, those being \(P\) and \(Q\). Therefore, begin by writing out the following truth table:
\(P\) |
\(Q\) |
\(...\) |
|---|---|---|
\(\mathrm T\) |
\(\mathrm T\) |
|
\(\mathrm T\) |
\(\mathrm F\) |
|
\(\mathrm F\) |
\(\mathrm T\) |
|
\(\mathrm F\) |
\(\mathrm F\) |
Now add new columns and fill in the values for each of the given propositions \(u\), \(v\), and \(w\).
Answer
The truth table for \(u\) is:
\(P\) |
\(Q\) |
\(u\) |
|---|---|---|
\(\mathrm T\) |
\(\mathrm T\) |
\(\mathrm T\) |
\(\mathrm T\) |
\(\mathrm F\) |
\(\mathrm T\) |
\(\mathrm F\) |
\(\mathrm T\) |
\(\mathrm T\) |
\(\mathrm F\) |
\(\mathrm F\) |
\(\mathrm F\) |
Likewise we can obtain the truth tables for \(v\) and \(w\).
Question b#
Now let \(P\) and \(Q\) denote the logical propositions:
\(P\): “6 is an odd number” and \(Q\): “3<7”.
Use your tables from the previous Question to determine the truth values of the three propositions \(u\), \(v\), and \(w\).
Answer
\(u\): \(\mathrm T\) (that is, true), \(v\): \(\mathrm T\) and \(w\): \(\mathrm F\) (that is, false).
Question c#
Which of the logical propositions \(P \wedge Q\) and \(P \vee Q\) are logically equivalent to \(u\)?
Hint
See the text just before Theorem 1.3.1 in the textbook if you are in doubt about what it means for two logical propositions to be logically equivalent.
Exercise 2: Or#
In propositional logic we use the symbol \(\vee\), pronounced “or”.
Let \(P\) and \(Q\) be propositions.
Question a#
Write out the truth table for \(P \vee Q.\)
Hint
See Definition 1.2.2 in the textbook.
Question b#
Write out the truth table for \((P \vee Q) \wedge \neg(P \wedge Q)\).
Hint
If you are in doubt about how to construct a truth table for a more complicated expression like \((P \vee Q) \wedge \neg(P \wedge Q)\), then you can find inspiration in Example 1.2.2 in the textbook.
Question c#
Give examples of the use of the word “or” in everyday speech and analyse whether this meaning of the word “or” is the same as in Question a or as in Question b.
Answer
In everyday speech “\(P\) or \(Q\)” often means the same as the logical expression from Question b and not the same as the mathematical “or” from Question a. An example is: “I have a lecture on mathematics tomorrow or the day after tomorrow.” The mathematical “or” allows for the possibility that you are having a lecture on mathematics both tomorrow and the day after tomorrow, but when saying the sentence in words that is rarely what is meant.
This meaning of “or” from everyday speech is in logics called “exclusive or”, often denoted in short by “xor”.
Exercise 3: Truth Tables#
Let \(P\), \(Q\), and \(R\) be logical propositions.
Question a#
Write out the truth table for the logical propositions: \(P \wedge ( Q \vee R)\).
Hint
Follow an approach as the one in Example 1.2.1 in the textbook.
Question b#
Write out the truth table for the logical proposition: \((P \wedge Q) \vee R\).
Question c#
Are the logical propositions \(P \wedge ( Q \vee R)\) and \((P \wedge Q) \vee R\) logically equivalent?
Answer
No.
Exercise 4: Negation#
Let \(P\) and \(Q\) be logical propositions.
Question a#
Write out the truth table for the logical proposition: \(\neg P\).
Question b#
Write out the truth table for the logical proposition: \(\neg (P \wedge Q)\).
Question c#
Write out the truth table for the logical proposition: \(\neg P \vee \neg Q\).
Question d#
Are the logical propositions \(\neg (P \wedge Q)\) and \(\neg P \vee \neg Q\) logically equivalent?
Answer
Yes.
Question e#
We now wish to find a logical equivalence that applies to \(\neg (P \vee Q)\). Instead of repeating the truth table approach as above, then use the previous answer but with the logical propositions \(\neg P\) and \(\neg Q\) to derive a logically equivalent expression for \(\neg (P \vee Q)\).
Hint
If we use the answer from Question d with the logical propositions \(\neg P\) and \(\neg Q\), then we find out that \(\neg (\neg P \wedge \neg Q)\) and \(\neg(\neg P) \vee \neg(\neg Q)\) are logically equivalent. Now simplify the expression \(\neg(\neg P) \vee \neg(\neg Q)\).
Answer
\(\neg (P \vee Q)\) is logically equivalent to \(\neg P \wedge \neg Q\). The equivalences you have shown in Questions d and e here are called De Morgan’s laws, see Theorem 1.3.2 in the textbook.
Exercise 5: Negation in Everyday Speech#
Question a#
Let \(P\) be the proposition “The sun is shining” and \(Q\) the proposition “I am in a bad mood”. Explain what the below propositions mean in everyday speech:
\(\neg P\)
\(P \vee \neg Q\)
\(\neg P \wedge \neg Q\)
\(P \Rightarrow \neg Q\)
\((\neg P \wedge \neg Q) \Rightarrow (\neg P)\)
Answer
In everyday speech, \(P \Rightarrow \neg Q\) means “If the sun is shining, then I am not in a bad mood”. Note that there are more possible formulations, for example: “When the sun is shining, then I am in a good mood”.
Exercise 6: Implication#
Question a#
Which of the below expressions are logically equivalent to \(P \Rightarrow Q\)?
\(Q \Rightarrow P\)
\(\neg P \Rightarrow \neg Q\)
\(\neg Q \Rightarrow P\)
\(\neg Q \Rightarrow \neg P\)
Question b#
Show that the proposition \(P \Leftrightarrow Q\) is logically equivalent to \(\neg P \Leftrightarrow \neg Q\). Try to challenge yourself by showing this without using truth tables and instead using the above result along with a fitting theorem from our textbook.
Exercise 7: Contraposition#
An integer \(a\) is called even if \(a=2b\) for some integer \(b\). Likewise, an integer \(a\) is called odd if one can write \(a=1+2c\) for some integer \(c\).
Claim: Let \(a\) be an integer. If \(a^2\) is even, then \(a\) is even as well.
The purpose of this exercise is to confirm this claim using propositional logic.
Question a#
The above statement contains an implication. Formulate logical propositions \(P\) and \(Q\) such that the implication in the statement can be written as \(P \Rightarrow Q\).
Answer
\(P\) is the proposition that “\(a^2\) is even”, whereas \(Q\) is the proposition that “\(a\) is even”. With these choices the proposition “If \(a^2\) is even then \(a\) is even as well” can be written as “\(P \Rightarrow Q\).”
Question b#
With \(P\) and \(Q\) as in Question a, describe in words the logical proposition \(\neg Q \Rightarrow \neg P\).
Hint
“An integer is not even” is equivalent to saying “An integer is odd”.
Answer
“If \(a\) is odd, then \(a^2\) is odd as well.”
Question c#
From Exercise 6 we know that the logical propositions \(P \Rightarrow Q\) and \(\neg Q \Rightarrow \neg P\) are logically equivalent. Therefore we can show the claim in this exercise by showing that the proposition “If \(a\) is odd then \(a^2\) is odd” is true for any integer \(a\). Show this proposition.
Hint
If \(a\) is odd, then it applies that \(a=1+2b\) for some integer \(b\). What can we now say about \(a^2\)?
Exercise 8: The NAND Operator#
The logical operator \(\uparrow\), also called NAND, has the following truth table:
\(A\) |
\(B\) |
\(A \uparrow B\) |
|---|---|---|
\(\mathrm T\) |
\(\mathrm T\) |
\(\mathrm F\) |
\(\mathrm T\) |
\(\mathrm F\) |
\(\mathrm T\) |
\(\mathrm F\) |
\(\mathrm T\) |
\(\mathrm T\) |
\(\mathrm F\) |
\(\mathrm F\) |
\(\mathrm T\) |
A NAND operator can be interpreted as a component in an electrical network that takes two input currents \(A\) and \(B\), that each might be on (current is flowing) or off (current is not flowing), and produces an output current. If \(A\) has the value \(\mathrm T\) (respectively \(\mathrm F\)) then, in the electrical network, this can be interpreted as saying that \(A\) is on (respectively off). The truth values of \(B\) and the output \(A \uparrow B\) have similar interpretations. In the context of electrical networks the NAND operator is called a NAND gate. It is drawn as an electrical component on an electrical network schematic with a symbol as follows:
Also other logical operators such as the \(\neg\), \(\wedge\), and \(\vee\) can be interpreted as gates within electrical networks (see the Wikipedia page “Logic gate” if you wish to read more).
Question a#
Show that the two logical propositions \(A \uparrow B\) and \(\neg (A \wedge B)\) are logically equivalent. This explains the name NAND, which simply is an abbreviation of “not and”.
Question b#
Justify that the following electrical component has the same effect as \(\neg A\) by showing that the two logical propositions \(A \uparrow A\) and \(\neg A\) are logically equivalent.
Question c#
Justify that the following electrical network consisting of two logic gates has the same effect as \(A \wedge B\).
Hint
Show that the two logical propositions \(A \wedge B\) and \((A \uparrow B)\uparrow(A \uparrow B)\) are logically equivalent.
Question d#
Draw an electrical network with two input currents \(A\) and \(B\) that only uses NAND gates and that has the same effect as \(A \vee B\).
Answer
Exercise 9: Proof by Contradiction#
Consider the second-degree equation \(x^2+bx+c=0\) where \(b,c \in \Bbb{Z}\). As is well-known from highschool, such equation has a discriminant expressed as \(D=b^2-4c.\) Let \(P\) be the proposition that \(D\) can never take a value of \(2\) for \(b,c \in \Bbb{Z}\).
Question a#
What does the logical proposition \(\neg P\) tell about the discriminant \(D\)?
Hint
\(\neg P\) is the negation of the proposition that \(D\) can never take a value of \(2\) for \(b,c \in \Bbb{Z}\). Try rewriting this into a simpler sentence.
Answer
\(\neg P\) is the proposition that \(D=2\) for some integers \(b\) and \(c\).
Question b#
Show that the proposition \(P\) is true using a proof by contradiction.
Hint
A proof by contradiction of a proposition \(P\) is based on Equation (1.23) from Theorem 1.3.4 in the textbook. Assume therefore that \(\neg P\) is true and try to find a contradiction.
Exercise 10: Riddle#
Question a#
Try solving Example 1.5.2 in the textbook on your own. Alternatively, read and understand Example 1.5.2.