ハードコア述語
は g のハードコア述語である。ここで、 ⟨ ⋅ , ⋅ ⟩ {\displaystyle \langle \cdot ,\cdot \rangle } をベクトル空間 ( Z / 2 Z ) n {\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}} 上の標準的な内積とすると、 b ( x , r ) = ⟨ x , r ⟩ {\displaystyle b(x,r)=\langle x,r\rangle } である。f(x) から g(x, r) を 1/2 以上に無視できない確率で計算できるアルゴリズムが存在するならば、x そのものを効率よく求めることができる。同様の構成により、 log  ( | x | ) {\displaystyle \log(|x|)} ビットの出力を持つハードコア関数を構成することができる。