Write multiple quantifier statement as psuedocode

Question

I want to write an algorithm for determining the truth value of: "for all $x \in D$, $\exists y \in E$ such that $x$ and $y$ satisfy $P(x,y)$"

and

"$\exists x \in D$ such that $\forall y \in E$, $x$ and $y$ satisfy $P(x,y)$"

in pseudo-code, for generic D, E, P(x,y), for the benefit of computer science students' understanding.

Answer 1

You first need an interpretation of the predicates $D$, $E$ and $P$ in some structure $\mathcal{M}$.

My answer assumes that :

• $\mathcal{M}$ is finite, and its support represented by an (informatic) enumerable $M$
• The predicates $D,E,P$ are represented by boolean-valued functions.

The function satisfies_formula1 bellow will return True if the formula $\forall x \in D, \ \exists y \in E, \ P(x,y)$ holds, false otherwise. The function satisfies_formula2 does the same for the formula $\exists x \in D, \ \forall y \in E, \ P(x,y)$.

def satisfies_formula1():
    for x in M:
        if D(x):
            found_y = False  #this answers "did we find y in E such that P(x,y) holds?"
            for y in M:
                if E(y) and P(x,y):
                    found_y = True
            if not found_y:
                return False
    return True

def satisfies_formula2():
    for x in M: 
        if D(x):
            all_y_ok = True  #innocent untill proven guilty
            for y in M:
                if E(y) and not P(x,y):
                    all_y_ok = False
            if all_y_ok:
                return True