SATISFIABLE BUT NOT VALID! The formula evaluates to False under the truth assignment M=T and Q=F, so it is not valid. The formula evaluates to True under any truth assignment where M=F, so it is satisfiable.
SATISFIABLE BUT NOT VALID! The formula evaluates to False under the truth assignment P=T, Q=T, M=T, so it is not valid. The formula evaluates to True under any truth assignment where M=F, so it is satisfiable.
VALID! Can be verified using a truth table.
SATISFIABLE BUT NOT VALID! The formula evaluates to False under the truth assignment P=T and Q=F, so it is not valid. The formula evaluates to True under any truth assignment where Q=T, so it is satisfiable.
SATISFIABLE BUT NOT VALID! The formula evaluates to False under the truth assignment P=T and Q=T, so it is not valid. The formula evaluates to True under the truth assignment P=F and Q=F, so it is satisfiable.
SATISFIABLE BUT NOT VALID! The formula evaluates to False under the truth assignment P=T, Q=T, M=F, so it is not valid. The formula evaluates to True under any truth assignment where P=Q=F, so it is satisfiable.
SATISFIABLE BUT NOT VALID! The formula evaluates to False under the truth assignment P=T and Q=F, so it is not valid. The formula evaluates to True under the truth assignment P=Q=T, so it is satisfiable.
VALID! When \(P=Q\), the hypothesis of the implication is false, so the entire formula evaluates to True. When \( P \neq Q\), one of \(\textrm{ NOT } P\) or \(\textrm{ NOT } Q\) must be true, so the conclusion of the implication is True, and the entire formula evaluates to True.
SATISFIABLE BUT NOT VALID! The formula evaluates to False under the truth assignment P=T, Q=F, M=F, so it is not valid. The formula evaluates to True under any truth assignment where P=Q, so it is satisfiable.
For the following questions:
Let L = 'file system is locked'
Let Q = 'new messages are queued'
Let B = 'new messages are sent to the message buffer'
Let N = 'system functioning normally'
\(\textrm{ NOT } L \textrm{ IMPLIES } Q\)
\(\textrm{ NOT } L \textrm{ IMPLIES } B\)
\((\textrm{ NOT } L) \textrm{ IFF } N\)
\(\textrm{ NOT } Q \textrm{ IMPLIES } B\)
\(\textrm{ NOT } B\)
To satisfy (e), we must set B=F. But, this means that the implications of (b) and (d) have false conclusions, so we must ensure that their hypotheses are false; namely, we must set L=T and Q=T. Note that (a) is now satisfied. Finally, to satisfy (c), note that \(\textrm{ NOT } L\) evaluates to False under our truth assignment, so we must set N=F. Therefore, all 5 specifications are simultaneously true under the truth assignment L=T, Q=T, B=F, N=F.
Consider the following truth table:
| A | B | C | A XOR B | (A XOR B) XOR C | NOT[(A XOR B) XOR C] |
| T | T | T | F | T | F |
| T | T | F | F | F | T |
| T | F | T | T | F | T |
| T | F | F | T | T | F |
| F | T | T | T | F | T |
| F | T | F | T | T | F |
| F | F | T | F | T | F |
| F | F | F | F | F | T |
NOT VALID! Let \(D = \mathbb{N}\), and, for all \(x \in D\), let \(P(x) = `x \textrm{ is even}'\). Then, the hypothesis is true since \(x=2\) is even. However, the conclusion is false since \(y=3\) is not even.
NOT VALID! Let \(D = \mathbb{Z}\), and, for all \(x \in D\), let \(P(x) = `x \textrm{ is negative}'\), and let \(Q(x) = `x \textrm{ is greater than 1}'\). Then, the hypothesis is true because \(x=-1\) is a negative integer and \(y=2\) is an integer greater than 1. However, the conclusion is false since there does not exist a negative integer greater than 1.
VALID! Suppose that there exist \(x,y \in D\) such that \(P(x,y)\) is true. Then, we can choose \(z=y\) and \(w=x\), which makes \(P(w,z)\) true. Therefore, whenever the hypothesis of the implication is true, so is the conclusion.
NOT VALID! Let \(D = \mathbb{N}\), and, for all \(x,y \in D\), let \(Q(x,y) = `x \leq y'\). Then, the hypothesis is true since, for each natural number \(x\), choosing \(y=x+1\) satisfies the predicate. However, the conclusion states that there exists \(z \in D\) such that, for all \(w \in D\), \(w \leq z\) is true. This is false, since, for any \(z \in \mathbb{N}\), setting \(w = z+1\) makes the predicate \(Q(w,z)\) false.
VALID! Suppose that there exists an \(x \in D\) such that, for all \(y \in D\), \(R(x,y)\) is true. Then, for all \(z \in D\), it must be the case that \(R(x,z)\) is true. Namely, choosing \(w = x\) makes \(R(w,z)\) true for all choices for \(z\). Therefore, the conclusion is true.
NOT VALID! Let \(D = \mathbb{N}\), and, for all \(x,y \in D\), let \(P(x,y) = `x*y \textrm{ is even}'\). Then, the hypothesis is true since, for each \(x \in \mathbb{N}\), setting \(y = x+1\) makes the predicate \(P(x,y)\) true (because either \(x\) or \(x+1\) is even, so their product is even). However, for \(z=3\), the predicate \(P(z,z)\) is false, since \(z*z = 9\). Therefore, \(z=3\) is a counterexample that shows that the conclusion is false.
True for the domains \(\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{R}\). In all cases, for any value of \(x \in D\), \(2x\) is also in \(D\). Therefore, choosing \(y = 2x\) makes the predicate \(`2x-y=0'\) true.
False for the domains \(\mathbb{N},\mathbb{Z}\), true for the domains \(\mathbb{Q},\mathbb{R}\). In the first two cases, \(x=3\) is a counterexample. In the remaining cases, choose \(y = x/2\).
True for the domains \(\mathbb{N},\mathbb{Z}\), false for the domains \(\mathbb{Q},\mathbb{R}\). In the first two cases, \(x < 10\) implies that \(x \leq 9\), so \(y < x\) implies that \(y < 9\). In the remaining cases, choosing \(x = 9.9\) and \(y=9.8\) yields a counterexample.
False for the domain \(\mathbb{N}\), true for the domains \(\mathbb{Z},\mathbb{Q},\mathbb{R}\). In the first case, \(x=100\) is a counterexample, since, for all \(z \in \mathbb{N}\), \(y+z \geq y > x = 100\). In the remaining cases, set \(z = 100 - y\).
False for the domains \(\mathbb{N},\mathbb{Z},\mathbb{Q}\), true for the domain \(\mathbb{R}\). In the first 3 cases, it is because \(\sqrt{2}\) is an irrational number (which we will prove in an upcoming lecture.) However, \(\sqrt{2}\) is a real number, therefore, for the domain \(\mathbb{R}\), picking \(x = \sqrt{2}\) makes the predicate true.
True for the domains \(\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{R}\), since they are all closed under multiplication.
False for the domains \(\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{R}\). In \(\mathbb{N}\), \(y=3\) is a counterexample. In \(\mathbb{Z},\mathbb{Q},\mathbb{R}\), \(y=-1\) is a counterexample. The formula is true when \(D=\mathbb{C}\) because \(\mathbb{C}\) is an algebraically closed field.
False for the domains \(\mathbb{N},\mathbb{Z}\), true for the domains \(\mathbb{Q},\mathbb{R}\). For the first two cases, \(x = 2\) is a counterexample. The formula is true for the remaining domains, since they are all fields (which will not be proven in this course).
False for the domains \(\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{R}\). If it were true, then, from the first equation, we would get that \(x = 2-2y\). Substituting into the second equation, we get \(2(2-2y)+4y=5\), which implies that \(4=5\), which is impossible. This is an example of a proof by contradiction, which you will learn more about soon!
For the next question:
Let \(D\) be a set of people
For all \(x \in D\), let \(G(x) = \)`\(x \textrm{ is a girl}\)'
For all \(x \in D\), let \(B(x) = \)`\(x \textrm{ is a boy}\)'
For all \(x,y \in D\), let \(S(x,y) = \)`\(x \textrm{ is a sibling of } y\)'
It is true. In English, the statement says "Every girl is not the sibling of anyone whose siblings are all boys".
Rename nested quantified variables so that they use different symbols. In this case, we change the occurrences of x that are existentially quantified to u. \[ (\forall x \in D. [\forall z \in C.[(\exists u \in D. S(z,u)) \textrm{ IMPLIES } P(x,y,z)]]) \textrm{ AND } M(z) \] Rename quantified variables that also appear free. In this case, the final occurrence of z is free and the rest are quantified. \[ (\forall x \in D. [\forall v \in C.[(\exists u \in D. S(v,u)) \textrm{ IMPLIES } P(x,y,v)]]) \textrm{ AND } M(z) \] Move \(\textrm{AND } M(z)\) inside the quantifier \(\forall v \in C\): \[ \forall x \in D.\forall v \in C.([(\exists u \in D. S(v,u)) \textrm{ IMPLIES } P(x,y,v)] \textrm{ AND } M(z)) \] Move \(\textrm{IMPLIES } P(x,y,v)\) inside the quantifier \(\exists u \in D\) and change \(\exists u \in D\) to \(\forall u \in D\): \[ \forall x \in D.\forall v \in C.([\forall u \in D. (S(v,u) \textrm{ IMPLIES } P(x,y,v))] \textrm{ AND } M(z)) \] Move \(\textrm{AND } M(z)\) inside the quantifier \(\forall u \in D\): \[ \forall x \in D.\forall v \in C.\forall u \in D. ([S(v,u) \textrm{ IMPLIES } P(x,y,v)] \textrm{ AND } M(z)) \]