  For a finite set $\cal F$ of polynomials over fixed finite prime field of
size $p$ containing all polynomials $x^2 - x$ a Nullstellensatz proof of the
unsolvability of the system $$
  f = 0\ ,\ \mbox{ all } f \in {\cal F} $$ in the field is a linear combination
$\sum_{f \in {\cal F}} \ h_f \cdot f$ that equals to $1$ in the ring of
polynomails. The measure of complexity of such a proof is its degree: $\max_f
deg(h_f f)$.
  We study the problem to establish degree lower bounds for some {\em extended}
NS proof systems: these systems prove the unsolvability of $\cal F$ by proving
the unsolvability of a bigger set ${\cal F}\cup {\cal E}$, where set $\cal E$
may use new variables $r$ and contains all polynomials $r^p - r$, and satisfies
the following soundness condition: -- - Any $0,1$-assignment $\overline a$ to
variables $\overline x$ can be appended by an assignment $\overline b$ to
variables $\overline r$ such that for all $g \in {\cal E}$ it holds that
$g(\overline a, \overline b) = 0$.
  We define a notion of pseudo-solutions of $\cal F$ and prove that the
existence of pseudo-solutions with suitable parameters implies lower bounds for
two extended NS proof systems ENS and UENS defined in Buss et al. (1996/97).
Further we give a combinatorial example of $\cal F$ and candidate
pseudo-solutions based on the pigeonhole principle.
