Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm working on a software problem and trying to describe it in symbolic logic so that I can get my head around it.

I have

$isnt(n) := \mathbf{F} \neq \emptyset \wedge \forall f \in \mathbf{F} : P(n,f) $

Basically, I'm checking n against all elements in F, unless F is empty.

Is there a way to simplify this so as to have no conjunctions (or disjunctions) outside of the quantifiers

share|cite|improve this question
Just today I was wondering whether it would be worthwile having a separate symbol for this. – Daan Michiels May 11 '12 at 19:14
Well, $\neg(\mathbf{F}=\emptyset\vee\exists f\in\mathbf{F}:\neg P(n,f)).$ But I don't suspect this is what you want. Can you clarify what is allowed? – Charles May 11 '12 at 19:15
In the opposite direction, $\exists f\in\mathbf{F}: P(n,f))\wedge\forall f\in\mathbf{F}: P(n,f)).$ – Charles May 11 '12 at 19:16
I'd like to remove any conjunction or disjunctions outside of the quantifier – Dancrumb May 11 '12 at 19:25
@Dancrumb: In that case the quantifier can't be $\forall$, since that's always true on an empty set. It can't be $\exists$ alone, since that can't distinguish between some cases and all cases. Can you use nested quantifiers? – Charles May 11 '12 at 19:29
up vote 2 down vote accepted

I don't understand why you're asking for what you seem to be asking for. Surely the efficient way to define the function is something like:

if $F = \emptyset$ then return false;
else for $f\in F$ do
for $f\in F$, if $P(n,f)$ = false then return false;
return true;

share|cite|improve this answer
That was my thought, and the reason I posted the || comment. But perhaps there is some reason. – Charles May 11 '12 at 20:52
Yes, I've asked for clarification, and perhaps all will become clear shortly. – Tara B May 11 '12 at 20:56
In the end, that's what I did; I created a function generator that takes in F, P and returns a function that takes n... appreciate people's efforts though! – Dancrumb May 11 '12 at 22:15
Well, it is the natural and efficient way to do it. =] – Tara B May 11 '12 at 22:18

So you can nest quantifiers, but you can't use conjunctions or disjunctions outside the quantifiers. So how about

$$ \exists f\in\mathbf{F}\ \forall g\in\mathbf{F}: P(n,f)\wedge P(n,g) $$

share|cite|improve this answer
This looks like it could make the program run a lot slower, though. – Tara B May 11 '12 at 20:33
Why $P(n,f)$? How about just $\exists f \in \textbf{F} \forall g \in \textbf{F} \thinspace \colon \thinspace P(n,g)$? – MartianInvader May 11 '12 at 20:49
@TaraB: Yes, substantially. But that seems unavoidable under the constraints, see my comments to the question. – Charles May 11 '12 at 20:51
@MartianInvader: Sure, that works too. – Charles May 11 '12 at 20:51
@MartianInvader: That's better. =] – Tara B May 11 '12 at 20:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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