I have a Predicate Logic question that looks like this:
Q5. Let S and T be two sequences of Natural numbers and let P be the predicate:
$∃ i : 1 ≤ i ≤ size(S). ∀ j : 1 ≤ j ≤ size(S). ∀ k : 1 ≤ k ≤ size(T). S[i] ≥ S[j] ∧ S[i] ≤ T [k]$
Here's the list of possible answers:
A. S=[1,8,12] T=[1,8,11]
B. S=[1,8,11] T=[14]
C. S=[92,17] T=[1,8,11]
D. S=[1,19,62,34,83] T=[23,96,102]
The correct answer is B. Can someone please explain why this is? Can someone also please explain, am I correct or incorrect in assuming that S[i]≥S[j] is redundant because the values in S will also be greater than or equal to themselves?
You didn't state the actual question, but I assume the question is: for which of the following pairs of $S$ and $T$ is the predicate $P$ true?
OK, $P$ is saying that there needs to be some number from $S$ that is greater or equal to any of the numbers of $S$, and also smaller or equal to any of the numbers in $T$. So effectively this means: the highest number in $S$ needs to be smaller than the smallest number in $T$ (since being the highest number in $S$ means it is greater or equal to all numbers in $S$, and being smaller than the smallest number in $T$ means it is smaller than all numbers in $T$)
This rules out A (12 is not smaller than any number in $T$), C (92 is not smaller than any number in $T$), and $D$ (83 is not smaller than 23).
But, B is ok: 11 is smaller than 14.
And no, the $S[i]\geq S(j]$ is not redundant: you are looking for some i such that for all j: $S[i]\geq S(j]$, and that is only true when $S[i]$ is the highest number in $S$ ... if it said that for some (or for all) i there is some j such that $S[i]\geq S(j]$, then you would be right, since you can always pick j to be i, but it says that it should work for all j.