# Question on Predicates and Quantifiers

I am reading from "Discrete Mathematics and Its applications" by Kenneth H. Rosen, 7th edition. Consider the highlighted part in the following example taken from the same book:

Question Use predicates and quantifiers to express the system specifications “Every mail message larger than one megabyte will be compressed” and “If a user is active, at least one network link will be available.”

Solution: Let S(m, y) be “Mail message m is larger than y megabytes,” where the variable x has the domain of all mail messages and the variable y is a positive real number, and let C(m) denote “Mail message m will be compressed.” Then the specification “Every mail message larger than one megabyte will be compressed” can be represented as ∀m(S(m, 1) → C(m)). Remember the rules of precedence for quantifiers and logical connectives! Let A(u) represent “User u is active,” where the variable u has the domain of all users, let S(n, x) denote “Network link n is in state x,” where n has the domain of all network links and x has the domain of all possible states for a network link. Then the specification “If a user is active, at least one network link will be available” can be represented by

∃uA(u) → ∃nS(n, available).

"Existential quantifier" ∃u is used here, So I think, it should be ∃uA(u)∧ ∃nS(n, available) in place of ∃uA(u) → ∃nS(n, available).

Generally, we use 'implication' with 'universal quantifier' as shown in ∀m(S(m, 1) → C(m)).

Please correct me, if I am wrong.

• Can you replace the image by text? – Yuval Filmus Sep 12 '17 at 13:19
• Updated, let me know if i need to make any other changes. – Manu Thakur Sep 12 '17 at 13:23

The meaning of $$\exists u A(u) \land \exists n S(n,\text{available})$$ is "there exists an active user, and there exists a network link which is available". The conditioning is missing here.
If $P = \exists u A(u)$ and $Q = \exists n S(n,\text{available})$, then we are trying to model "if $P$ then $Q$", whose formal form is $P \rightarrow Q$, whereas your answer is $P \land Q$.
In particular, if there doesn't exist an active user, then $P \land Q$ is always false, whereas $P \to Q$ is always true.
• It can be true or false. The difference between what you wrote and the correct answer is exactly the difference between $P \land Q$ and $P \rightarrow Q$. – Yuval Filmus Sep 12 '17 at 13:27
• The phrase "If P then Q" has exactly the same semantics as $P\to Q$. – Yuval Filmus Sep 12 '17 at 13:33