This is a  question  about generalizations of the twin primes conjecture.

I would like to know a counterexample, or a proof, for the following couple of related arithmetical sentences. The first is 

$(\forall p) Prime(p) \Rightarrow (\exists n)(\exists q)(Prime (q) \wedge (p = 2^n + q))$

More informally, if $p$ is prime, then $p$ can be written as the sum of a smaller prime $q$ and a power of $2$. The second is 

$(\forall q) Prime(q) \Rightarrow (\exists n)(\exists p)  (Prime(p) \wedge (p = 2^n + q))$

More informally, if $q$ is prime, then there exists a number $n$  such that the sum  of  $q$  and the  $n$-th power of $2$ is a  prime number.