Let's prove existence first. For every $a=(a_1,\dots,a_n)\in \{0,1\}^n$, consider the polynomial function $i_a(x_1,\dots,x_n)=(1-a_1-x_1+2a_1x_1)\cdots (1-a_n-x_n+2a_nx_n)$. One can check that $i_a(x)=1$ if and only if $x=a$ on $\{0,1\}^n$. Now for any function $f:\{0,1\}^n\to F$, we may interpolate $f$ by the following multilinear polynomial $\sum_{a\in \{0,1\}^n} f(a)\cdot i_a(x_1,\dots,x_n)$.

Now let's show uniqueness. The space of all functions $F^{\{0,1\}^n}$ forms a $2^n$ dimensional vector space over $F$. It suffices to prove that the set of all $2^n$ multilinear monomials are $F$-linearly independent. From the existence proof, we see that the set of all multilinear monomials span $F^{\{0,1\}^n}$, since the dimension equals the size of the spanning set, linear independence follows. $\Box$

Let $\frac{p(x)}{q(x)}$ be such that $\rdeg(f)$ is attained. We have $p(x)=f(x)\cdot q(x)$, and hence $p(x)-q(x)=(1-f(x))\cdot q(x)=\bar f(x)\cdot q(x)$. Since $q(x)$ is nonzero, $\rdeg(f)\geq \deg(p(x)-q(x))\geq \ndeg(f)$, and this shows that $\rdeg(f)\geq \max(\ndeg(f),\ndeg(\bar f))$.

For the reverse inequality, let $p(x),q(x)$ be such that they attain $\ndeg(f),\ndeg(\bar f)$ respectively. We may assume without loss of generality that $\deg(p+q)=\max(\deg(p),\deg(q))$, as by multiplying a large enough constant to one of $p,q$ (recall that the underlying field is $\RR$), we can guarantee that the monomials do not cancel in the sum. Now we have $\frac{p(x)}{p(x)+q(x)}=f(x)$ for all $x$. Since if $f(x)=1$, then $\frac{p(x)}{p(x)+q(x)}=\frac{p(x)}{p(x)+0}=1$, and if $f(x)=0$, then $\frac{p(x)}{p(x)+q(x)}=\frac{0}{0+q(x)}=0$. This shows that $\max(\ndeg(f),\ndeg(\bar f))=\max(\deg(p),\deg(p+q))=\max(\deg(p),\deg(q)) \geq \rdeg(f)$, as desired. $\Box$

Denote the support of $f$ by $\supp_n(f)=\{x\in \{0,1\}^n:f(x)=1\}$. We may rewrite the inequality as $$\ndeg(f)\geq n-\log_2 (|\supp_n(f)|).$$ We prove by induction on $n$. For the base case $n=1$, there are exactly $3$ non-zero boolean functions. It's easy to check that the non-constant functions must have non-zero non-deterministic degree, and the constant $1$ function has non-deterministic degree $0$. This proves the base case.

For the inductive step, let $n\geq 2$, and let $p(x)\in \RR[x_1,\dots,x_n]$ be such that $p$ is a non-deterministic representation of $f$. For each $i=1,\dots,n$. For $i=1,\dots,n$ and $b=0,1$, let $f_{i,b}$ denote the function we obtain by setting the $i$th variable of $f$ to $b$, and similarly define for $p_{i,b}$. Notice that $p_{i,b}$ is a non-deterministic representation of $f_{i,b}$. If for some $i$, neither of $f_{i,0},f_{i,1}$ is identically zero. Then by the induction hypothesis, we have $$\deg(p_{i,b})\geq \ndeg(f_{i,b})\geq n-1-\log_2(|\supp_{n-1}(f_{i,b})|)=n-\log_2(2\cdot |\supp_{n-1}(f_{i,b})|).$$ Since $|\supp_{n-1}(f_{i,0})|+|\supp_{n-1}(f_{i,1})|=|\supp_n(f)|$, we have $2\cdot |\supp_{n-1}(f_{i,b})|\leq |\supp_n(f)|$ for some $b\in \{0,1\}$. Therefore $$\ndeg(f)=\deg(p)\geq \deg(p_{i,b})\geq n-\log_2(2\cdot |\supp_{n-1}(f_{i,b})|)\geq n-\log_2(|\supp_n(f)|).$$ It remains to handle the case when for all $i$, there exists $b_i\in \{0,1\}$ such that $f_{i,b_i}=0$. For each $a=(a_1,\dots,a_n)\in \{0,1\}^n$, if $a_i=b_i$ for some $i$, then we must have that $f(a_1,\dots,a_n)=f_{i,b_i}(a_1,\dots,a_{i-1},a_{i+1},\dots,a_n)=0$. From this, we see that the only $x$ that satisfies $f(x)=1$ is $x=\bar b=(1-b_1,\dots,1-b_n)$. Therefore $\supp(f)=\{(1-b_1,\dots,1-b_n)\}$, and its non-deterministic representation always has the form $c\cdot i_{\bar b}(x_1,\dots,x_n)$ for some non-zero constant $c\in \RR$. Since $\deg(c\cdot i_{\bar b})=n$, we get $$\ndeg(f)=n\geq n-\log_2(|\supp_n(f)|),$$ as desired. By induction, this holds for all $n\geq 1$. $\Box$