1
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ if there is no "active user" won't still it be true? $\endgroup$ – Manu Thakur Sep 12 '17 at 13:26
  • $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Sep 12 '17 at 13:27
  • $\begingroup$ my doubt is “If a user is active, at least one network link will be available.” if there is no active user, then it should give truth value as "false" but P→Q always gives true if the premise is false. or why can't we use ∀uA(u) → ∃nS(n, available)? $\endgroup$ – Manu Thakur Sep 12 '17 at 13:32
  • $\begingroup$ The phrase "If P then Q" has exactly the same semantics as $P\to Q$. $\endgroup$ – Yuval Filmus Sep 12 '17 at 13:33
  • $\begingroup$ yes, but why did author not use "Universal Quantifier" ∀ in second part of the question like first part? $\endgroup$ – Manu Thakur Sep 12 '17 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.