Course Site for Comp 283
Here are the practice problems to prepare you for the quiz! I will try and cover as many as possible, but please come to the review session with requests! We can also review problems from the lessons, but I encourage you to use office hours for this as well!
Prove \(a \leftrightarrow b \equiv (a \rightarrow b) \land (b \rightarrow a)\) using a truth table.
True or False: You can prove compound propositions \(X\) and \(Y\) are logically equivalent by showing \(X \leftrightarrow Y\) is a tautology. Explain your answer. (Hint, try this for the equivalence \(p \rightarrow q \equiv \neg p \lor q\))
True or False: \(((a \lor b) \oplus \neg b) \lor \texttt{True}\) always evaluates to \(\texttt{True}\) regardless of the values of \(a\) and \(b\). Explain your answer.
For this problem, let:
Express the following using predicate logic:
4.1. No penny is a euro.
4.2. There are coin purses of different sizes.
4.3. There is a coin purse for every coin.
4.4. No coin is without a coin purse. (Extra question: can there be an empty coin purse?)
4.5 There does not exist a purse without a coin. (Use \(IN\) for this, not \(q(c)\).)
4.6. A coin purse with a euro must contain at least two coins.
Let the relation \(R \subseteq \mathbb{N} \times \mathbb{N}\) be defined such that \(R = \{(x,y) \mid x,y \in \mathbb{N} \land x + y = 10 \}\).
Justify your answers for the following using the formal definition of a symmetric relation given in class. If your answer is no, provide a counter example.
5.1 Is \(R\) symmetric?
5.2 Is \(R\) reflexive?
5.3 Is \(R\) transitive?
Since the last two columns are equivalent, this shows that \(a \leftrightarrow b\) and \((a \to b) \land (b \to a)\) are equivalent for all possible values of \(a\) and \(b\) and therefore logically equivalent.
True!
Let’s try this for \(X = p \rightarrow q\) and \(Y =\neg p \lor q\)
\[\begin{array}{|c|c|c|c|c|c|} \hline & & & X & Y & X \leftrightarrow Y \\ \hline p & q & \neg p & p \to q & \neg p \lor q & \big(p \to q \big) \leftrightarrow \big( \neg p \lor q \big) \\ \hline T & T & F & T & T & T \\ T & F & F & F & F & T \\ F & T & T & T & T & T \\ F & F & T & T & T & T \\ \hline \end{array}\]As you can see, if two columns (in this case \(X\) and \(Y\)) are equal (aka logically equivalent), then \(X \leftrightarrow Y\) will always evaluate to \(\texttt{True}\) (aka it’s a tautology)!
This is True. You can demonstrate this with a truth table, but you can also just reason that any X that is “or”ed with a \(\texttt{True}\), will always be \(\texttt{True}\).
In other words, for any compound proposition \(X\), \(X \lor \texttt{True} = \texttt{True}\).
There can be multiple correct answers for these statements, so please feel free to run them by us in the review session or on EdStem!
“For all coins, if a coin is a penny, then it is not a euro.”
\[\forall x \in S, p(x) \to \neg e(x)\]
“There does not exist a coin that is both a penny and a euro.”
\[\neg \exists x \in S, p(x) \land e(x)\]
“It is not the case that all coin purses are the same size.”
\[\neg \big( \forall c_1, c_2 \in C, q(c_1) = q(c_2) \big)\]
“There exist coin purses of different sizes.”
\[\exists c_1, c_2 \in C, q(c_1) \neq q(c_2)\]
“For every coin, there exists a coin purse that that coin is in.”
\[\forall x \in S, \exists c \in C, IN(x,c)\]
“There does not exist a coin that isn’t in a purse.”
This is just the same statement as above. We can transform it by adding a double negation.
\[\neg \neg \big(\forall x \in S, \exists c \in C, IN(x,c)\big)\]
\[\equiv \neg \exists x \in S, \forall c \in C, \neg IN(x,c)\]
“There does not exist a purse that has no coins.”
\[\neg \exists c \in C, \forall x \in S, \neg IN(x,c)\]
“For all coin purses, if there is a coin in the purse that is a euro, then the purse must contain at least 2 coins.”
\[\forall x \in S, c \in C, \big(IN(x,c) \land e(x)\big) \to q(c) \geq 2\]
For each of these questions, you want to plug the relation in to the definiton.
Definition: \(R\) is symmetric iff \(\forall x,y \in A, (x R y \implies y R x)\)
Now, we substitute \(A\) with \(\mathbb{N}\) and substitute \(x R y\) with \(x + y = 10\).
\(R\) is symmetric iff \(\forall x,y \in \mathbb{N}, (x + y = 10 \implies y + x = 10)\)
We know that this is true because x + y = y + x!
You can test it by plugging in values… if 1 + 9 = 10 and 9 + 1 = 10.
So yes, \(R\) is symmetric.
Definition: \(R\) is reflexive iff \(\forall x \in A, x R x\).
Now, we substitute \(A\) with \(\mathbb{N}\) and substitute \(x R y\) with \(x + y = 10\).
\(R\) is reflexive iff \(\forall x \in \mathbb{N}, x + x = 10\).
Here, we can come up with a counter example. We can choose \(x = 3\) The number \(3\) is in \(\mathbb{N}\), however \(3 + 3 \neq 10\).
Therefore, no R is not reflexive.
Definition: \(R\) is transitive iff \(\forall x,y,z \in A, (x R y \land y R z) \implies x R z\)
Now, we substitute \(A\) with \(\mathbb{N}\) and substitute \(x R y\) with \(x + y = 10\).
\(R\) is transitive iff \(\forall x,y,z \in \mathbb{N}, (x + y = 10 \land y + z = 10) \implies x + z = 10\)
Here, we can come up with a counter example. We can choose \(x=2\), \(y=8\), \(z=2\).
\(x + y = 10\) and \(y + z = 10\) however \(x + z \neq 10\).
So, no \(R\) is not transitive.