This proof aims to show that any formula for a monotonous boolean function containing a not gate can be reduced. It is most likely flawed, for if not it would show that $\mathrm{P}\neq\mathrm{NP}$ ( at least I believe so, because it implies that the super-polynomial lower bound in circuit size for monotonous circuits solving $k$-clique would apply to any circuit solving $k$-clique, which would thereby not be in P/Poly so not in P ). So where is the flaw in my reasoning ? I can't seem to find it.Given a boolean function $f$ that takes $n$ arguments in $\{0,1\},$ we define $$\newcommand{\verif}{\mathrm{verif}} \verif(f,x_p)=\{(x_1, \ldots, x_{p-1}, x_{p+1}, \ldots, x_n) \in \{0,1\} ^ {n-1} | f(x_1, \ldots, x_{p-1}, 1, x_{p+1}, \ldots, x_n) = 1 \}$$ and $$\newcommand{\nverif}{\mathrm{nverif}}\nverif(f, x_p) = \{(x_1, \ldots, x_{p-1}, x_{p+1}, \ldots, x_n) \in \{0,1\} ^ {n-1} | f(x_1, \ldots, x_{p-1}, 0, x_{p+1}, \ldots, x_n) = 1 \}.$$We then define $\newcommand{\diff}{\mathrm{diff}}\diff(f,x_p)=\nverif(f,x_p) \setminus \verif(f,x_p)$.One notices that $diff(f_{1} \land f_{2}, x_{p}) = ( diff(f_{1}, x_{p}) \cap nverif(f_{2},x_{p}))\cup(diff(f_{2}, x_{p})\cap nverif(f_{1},x_{p}))$,and$diff(f_{1} \lor f_{2}, x_{p}) = ( diff(f_{1}, x_{p}) \cap c(verif(f_{2},x_{p})) ) \cup ( diff(f_{2}, x_{p}) \cap c(verif(f_{1},x_{p})))$ where c(A) denotes the complimentary of A.Let there be a formula for a monotonous boolean function g that contains a negative litteral x_{p}, and nots only on litterals. We first want to show that this means there is a sub-formula $g'=(g_{1} \land g_{2})$ or $g'=(g_{1} \lor g_{2})$ so that $diff(g',x_{p]})=\emptyset$ and $diff(g_{1},x_{p})\neq\emptyset$ ( and contains litteral $not(x_{p})$).Suppose this weren't the case. We notice that there exists a sub-formula $l=not(x_{p})$, so for which $diff(l,x_{p})\neq\emptyset$. We recursively notice this means its parent formula ( considering the formula as a tree ) p also verifies $diff(p,x_{p})\neq\emptyset$, up to the entire formula g. This is a contradiction with the fact g is monotonous since in an interpretation from $diff(g,x_{p})$, passing the value of $x_{p}$ from 0 to 1 makes the output go from 1 to 0.If $g'=(g_{1} \land g_{2})$, we deduce from the previous statements that  $diff(g_{1}, x_{p}) \cap nverif(g_{2},x_{p}) )=\emptyset$, so given any element $(x_{1}, ..., x_{n})$ of $diff(g_{1},x_{p})$, it is not in $nverif(g_{2},x_{p})$ so $g_{2}(x_{1}, ..., x_{p-1}, 0, x_{p+1}, ..., x_{n})=0$ and $g_{1}(x_{1}, ..., x_{p-1}, 1, x_{p+1}, ..., x_{n})=0$. This means we can replace the litteral $not(x_{p})$ by false, since it decreases the value of g1, and thereby g', only if there exists $(x_{1}, ... x_{n})$ so that  $g_{1}(x_{1}, ..., x_{p-1}, 0, x_{p+1}, ..., x_{n})=1$, and $g_{1}(x_{1}, ..., x_{p-1}, 1, x_{p+1}, ..., x_{n})=0$, so that element is in $diff(g_{1},x_{p})$, which means $g_{2}(x_{1}, ..., x_{n})$ is false no matter what : there is no impact on the value of g'.If $g'=(g_{1} \lor g_{2})$, we deduce from the previous statements that  $diff(g_{1}, x_{p}) \cap c(verif(g_{2},x_{p})) )=\emptyset$, so given any element $(x_{1}, ..., x_{n})$ of $diff(g_{1},x_{p})$, it is in $verif(g_{2},x_{p})$ so $g_{2}(x_{1}, ..., x_{p-1}, 1, x_{p+1}, ..., x_{n})=1$ and $g_{1}(x_{1}, ..., x_{p-1}, 0, x_{p+1}, ..., x_{n})=1$. This means we can replace the litteral $not(x_{p})$ by true, since it decreases the value of $g_{1}$, and thereby g', only if there exists $(x_{1}, ... x_{n})$ so that  $g_{1}(x_{1}, ..., x_{p-1}, 0, x_{p+1}, ..., x_{n})=1$, and $g_{1}(x_{1}, ..., x_{p-1}, 1, x_{p+1}, ..., x_{n})=0$, so that element is in $diff(g_{1},x_{p})$, which means $g_{2}(x_{1}, ..., x_{n})$ is true no matter what : there is no impact on the value of g'.This shows we can, in any case, replace the literal by either true or false, and then simplify the formula accordingly (at least one gate not and one gate and or or is removed ). Hence, any minimal sized formula for a monotonous boolean function can not contain a not gate. As for the formula containing nots only on litterals, it is easy get such a form using the De Morgan laws.
Does this prove $P\neq NP$
complexity theory;circuits;boolean algebra