Logic and Set Notation
Solved Problems
Example 1.
Prove De Morgan's Laws: \[\neg \left( {p \land q} \right) \equiv \left( {\neg p} \right) \lor \left( {\neg q} \right),\] \[\neg \left( {p \lor q} \right) \equiv \left( {\neg p} \right) \land \left( {\neg q} \right).\]
Solution.
We verify the \(1\text{st}\) De Morgan's Law using truth table.
First we write all possible combinations of the propositions \(p\) and \(q.\) The negations of \(p\) and \(q\) are their opposite values. The expression \(p \land q\) is conjunction of \(p\) and \(q.\) Then we determine the negation of conjunction \(\neg \left({p \land q}\right)\). The expression \(\left( {\neg p} \right) \lor \left( {\neg q} \right)\) is disjunction of \(\neg p\) and \(\neg q.\)
We see that the last two columns of the truth table are the same. This proves the \(1\text{st}\) De Morgan's Law.
Similarly, we can verify the \(2\text{nd}\) De Morgan's Law:
Example 2.
Show that the statement \[s = \left( {p \lor \neg q} \right) \lor \left( {\neg p \land q} \right)\] is a tautology.
Solution.
A tautology is defined as a proposition which is always true. So we make a truth table for the statement and check its truth values.
The values of \(p,\) \(q,\) \(\neg p,\) and \(\neg q\) are easy to fill in. The next column \({p \lor \neg q}\) means disjunction of \(p\) and \(\neg q.\) Then we find conjunction \({\neg p \land q}.\) The final statement \(s\) is disjunction of two previous propositions.
We see that all \(4\) values in the last column are true. Hence, the statement \(s = \left( {p \lor \neg q} \right) \lor \left( {\neg p \land q} \right)\) is a tautology.
Example 3.
Show that the statement \[r = (\neg p \land q) \land (p \leftrightarrow q)\] is a contradiction.
Solution.
A contradiction is a statement that is always false. Let's construct a truth table to make sure that the statement \(r\) has only false values.
The first expression \(\neg p \land q\) is conjunction of \(\neg p\) and \(q.\) The second expression \(p \leftrightarrow q\) is the biconditional of \(p\) and \(q\). The final operation is conjunction of two previous propositions.
The last column contains only false values. Hence, the proposition \(r = (\neg p \land q) \land (p \leftrightarrow q)\) is a contradiction.
Example 4.
Prove the distributive law \[p \lor \left( {q \land r} \right) \equiv \left( {p \lor q} \right) \land \left( {p \lor r} \right).\]
Solution.
We construct a truth table to make sure that the left hand and right hand sides of the statement are equivalent.
Let's denote
and find the truth values of \(s1\) and \(s2.\)
Applying conjunction and disjunction operations we get the following table:
The last two columns of the table are identical. This means that
Example 5.
Let \(G\left( {x,y} \right)\) be the predicate "\(x\) goes to the gym \(y\) times a week." Write the following propositions in predicate notation:
- Nick goes to the gym \(4\) times a week.
- Nicole goes to the gym \(2\) or \(3\) times a week.
- Max goes to the gym 2 times a week, but not every week.
- Amy sometimes goes to the gym.
- Some people go to the gym every day.
- Hardly anyone goes to the gym 15 times a week.
Solution.
- Nick goes to the gym \(4\) times a week.
\[G\left( {Nick,4} \right)\]
- Nicole goes to the gym \(2\) or \(3\) times a week.
\[G\left( {Nicole,2} \right) \lor G\left( {Nicole,3} \right)\]
- Max goes to the gym 2 times a week, but not every week.
\[G\left( {Max,2} \right) \lor G\left( {Max,0} \right)\]
- Amy sometimes goes to the gym.
\[\exists y G\left( {Amy,y} \right)\]
- Some people go to the gym every day.
\[\exists x G\left( {x,7} \right)\]
- Hardly anyone goes to the gym 15 times a week.
\[\neg \exists x G\left( {x,15} \right)\]
Example 6.
Suppose \(x\) is a student, \(y\) is a math course, and \(M\left( {x,y} \right)\) is the predicate "\(x\) will take \(y\)". Translate the following sentences into predicate notation:
- Every student will take Calculus.
- Every student will take a math course.
- Lora will take Calculus and Linear Algebra.
- There is a course that everybody will take.
- There is a course that nobody will take.
- Tom will take all math courses except Topology.
Solution.
- Every student will take Calculus.
\[\forall x M\left( {x,Calculus} \right)\]
- Every student will take a math course.
\[\forall x\exists yM\left( {x,y} \right)\]
- Lora will take Calculus and Linear Algebra.
\[M\left( {Lora,Calculus} \right) \land M\left( {Lora,Linear Algebra} \right)\]
- There is a course that everybody will take.
\[\exists y\forall xM\left( {x,y} \right)\]
- There is a course that nobody will take.
\[\exists y\forall x\neg M\left( {x,y} \right)\]
- Tom will take all math courses except Topology.
\[\forall yM\left( {Tom,y} \right) \land \neg M\left( {Tom, Topology} \right)\]
Example 7.
Describe the following sets using set builder notation:
- \(\left\{ { - 27, - 8, - 1,0,1,8,27} \right\}\)
- \(\left\{ {\frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{5}{6}} \right\}\)
- \(\left\{ {5,8,13,21,34,55} \right\}\)
Solution.
- The set \(\left\{ { - 27, - 8, - 1,0,1,8,27} \right\}\) contains integers from \(x = -3\) to \(x = 3\) cubed.
\[\left\{ {x \in \mathbb{Z}\,|\,{x^3} \text{ and } - 3 \le x \le 3} \right\}\]
- The set \(\left\{ {\frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{5}{6}} \right\}\) contains fractions where the denominator is greater than its numerator by \(1\) and the numerator ranges from \(1\) to \(5.\)
\[\left\{ {x \in \mathbb{N}\,|\,\frac{x}{{x + 1}} \text{ and } 1 \le x \le 5} \right\}\]
- The set \(\left\{ {5,8,13,21,34,55} \right\}\) is a portion of the Fibonacci sequence \({F_n}\) from \(n = 6\) to \(n = 11.\)
\[\left\{ {x \in \mathbb{N}\,|\,x \in {F_n}, \text{ where } n \in \mathbb{N} \text{ and } 6 \le n \le 11} \right\}\]