Proof that a function constructed from a PRP is, or is not a PRF? Let $E$ be a family of Pseudo-Random Permutations of $b$ bits, with $E_K$ indistinguishable from random permutation with effort less than $O(2^b)$, easily computable as well as the inverse permutation, e.g. as instantiated by AES-192 for $b=128$. Let $E_A$ and $E_B$ be two public members of this family.

For an $E_K$ in $E$, let $F_K$ and $G_K$ be the functions
$$F_K:x\mapsto F_K(x)=E_K(E_A(x))\oplus E_K(E_B(x))$$
$$G_K:x\mapsto G_K(x)=E_K(E_A(x)\lor1)\oplus E_K(E_B(x)\land\overline{1})$$
where $\lor1$ (resp. $\land\overline{1}$) sets (respectively clears) the rightmost bit, and $\oplus$ is exclusive-OR.

Question: Are $F$ and $G$ families of Pseudo-Random Functions indistinguishable from random function with effort less than $O(2^b)$ ?

Note: formerly, I thought of an attack on $F$ by considering a cycle in $x\mapsto E^{-1}_B(E_A(x))$; but thinking about it, that attack is $O(2^b)$.
Here are two different ways to break $G$.

Attack 1. $G$ is unlikely to be a secure PRF, at least against non-uniform adversaries.  In particular: there is likely to exist a fast attack (though it might take $2^b$ steps of computation to find the attack).

The idea of the attack: With high probability, there exists $x,x'$ such that $E_A(x)\wedge 1 = E_A(x') \wedge 1$ and $E_B(x)\vee \overline{1} = E_B(x') \vee \overline{1}$.  This immediately yields a distinguishing attack on $G$, since (regardless of $K$) we are guaranteed that $G_K(x)= G_K(x')$, something that should happen with just $1/2^b$ probability (not with probability 1).

I don't know how to efficiently find $x,x'$.  I can see how to find such a pair in about $2^b$ steps of computation.  Basically, pick a random $b$-bit value $y$, then compute $E_A^{-1}(y)$ and $E_A^{-1}(y) \oplus 1$; this gives a candidate pair $x,x'$, and you can then check whether $E_B(x)\vee \overline{1} = E_B(x') \vee \overline{1}$ holds.  The latter holds with probability $1/2^{b-1}$, so you'll probably have to try about $2^{b-1}$ different values of $y$ before success.  Nonetheless, even though the attack is hard to find, once you know the attack, the attack requires only 2 oracle queries and minimal computation.  This suffices to demonstrate that $G$ is not a secure PRF, at least under standard definitions of security.

Attack 2. I'll show an attack on $G$ that has about the same complexity as the best attack I can find on $F$.  In both cases, the attack requires about $2^b$ steps of precomputation just to find the attack, but then once the attack is known, it takes a lot less than $2^b$ steps to distinguish $G$ (or $F$) from a random function.

My attack on $G$ is an adaptation of my attack on $F$, so let me start by spelling out the attack on $F$ that I have in mind.  Define the permutation $\pi$ by $\pi(y)=E_B(E_A^{-1}(y))$.  The precomputation is as follows: find a short cycle of $\pi$, say $y_0,y_1,y_2,\dots,y_k$ (where $y_k=y_0$ and $y_{i+1}=\pi(y_i)$ for each $i$).  Define $x_i=E_A^{-1}(y_i)$.  Then we are guaranteed that $F_K(x_1)\oplus F_K(x_2) \oplus \dots \oplus F_K(x_k) = 0$.  This gives a distinguishing attack on $F$ that requires $k$ oracle queries and trivial work.  Since $\pi$ is effectively a random permutation, we should be able to find a short cycle in $\pi$: it is very likely that a short cycle will exist.

How long does it take to find the attack on $F$?  I can't see how to do it much faster than $2^b$ steps of computation.

Now here's the attack on $G$.  First, we're going to construct a new function $H$, as follows: $H_K(x) = G_K(x) \oplus G_K(x')$, where $x' = E_A^{-1}(E_A(x) \oplus 1)$.  Notice that, if you have an oracle for $G$, you can extract an oracle for $H$.  Also, expanding the definition of $H$ yields $H_K(x) = E_K(E_B(x) \wedge \overline{1}) \oplus E_K(E_B(E_A^{-1}(E_A(x) \oplus 1)) \wedge \overline{1})$.  By analogy to the attack on $F$, let's define a permutation $\sigma$ by $\sigma(y) = E_B(x') \wedge \overline{1}$ where $x=E_B^{-1}(y)$, i.e., $\sigma(y) = E_B(E_A^{-1}(E_A(E_B^{-1}(y)) \oplus 1)) \wedge \overline{1}$.  During precomputation, find a short cycle of $\sigma$, say $y_0,y_1,y_2,\dots,y_k$, and define $x_i=E_B^{-1}(y_i)$.  Then we are guaranteed that $H_K(x_1)\oplus \dots \oplus H_K(x_k)=0$.  This in turn implies a relation on $G$, where the xor of $2k$ $G$-outputs is guaranteed to be zero (regardless of $K$).  Thus, any short cycle in $\sigma$ yields a distinguishing attack on $G$.  The distinguishing attack itself is very fast (assuming $k$ is small).

How long does it take to find the attack on $G$?  I can't see how to do it much faster than $2^b$ steps of computation---in other words, about the same complexity as finding the attack on $F$.

This provides an alternate way to break $G$.