How can I translate this sentence to first order logic?

35 Views Asked by At

I'm trying to describe the following sentence:

the ideal flow $F$ over graph $g$ with maximum satisfaction and minimum cost is the flow where for any other valid flow $p$ over $g$, $$\frac{\operatorname{satisfaction}(p)_g}{\operatorname{cost}(p)_g} < \frac{\operatorname{satisfaction}(F)_g}{\operatorname{cost}(F)_g} \enspace.$$

This is what I have so far but it doesn't look correct to me. I feel like there shouldn't be an implication in the beginning but I don't know what to replace it with.

$$ F \implies \forall p \in P \left(v(p, g) \land F \ne p \land \left(\frac{\operatorname{satisfaction}(F)_g}{\operatorname{cost}(F)_g} > \frac{\operatorname{satisfaction}(p)_g}{\operatorname{cost}(p)_g}\right)\right) \enspace.$$

1

There are 1 best solutions below

0
On BEST ANSWER

The formula does not need an opening implication. In fact, $F$ is a flow, not a formula that is either true or false. Hence it cannot appear all by itself on the left-hand side of an implication.

On the other hand, $F$ should be a valid flow too. Besides, there may be more than one flow that is no worse than any other flow. It's not clear from your description if in that case there are multiple ideal flows, or no ideal flow. I assume the former. In sum,

$$ \operatorname{valid}_g(F) \wedge \forall p \left(\operatorname{valid}_g(p) \rightarrow \frac{\operatorname{satisfaction}_g(p)}{\operatorname{cost}_g(p)} \leq \frac{\operatorname{satisfaction}_g(F)}{\operatorname{cost}_g(F)} \right)\enspace. $$ If you wanted to impose the uniqueness constraint, you'd write something like this: $$ \operatorname{valid}_g(F) \wedge \forall p \left(\Big(\operatorname{valid}_g(p) \wedge p \neq F \Big) \rightarrow \frac{\operatorname{satisfaction}_g(p)}{\operatorname{cost}_g(p)} < \frac{\operatorname{satisfaction}_g(F)}{\operatorname{cost}_g(F)} \right)\enspace. $$ You could also make $g$ an argument to all predicates: $\operatorname{valid}(p,g)$, $\operatorname{cost}(p,g)$, and so on, but it's advisable to stick to one style throughout.