Tag Info

3

Yes, you are right. Having $x \leftrightarrow (x \rightarrow z)$ one can deduce that $x\equiv 1$ and $z \equiv 1$. In the paper you cite (the link is to another one btw.), rule 6 allows only to deduce that $x\equiv 1$ holds. But then you have the triplet $(1,1,z)$ and you can apply rule 4 $\frac{(x,1,z)}{x/z}$ to deduce $z\equiv x$, i.e., $z \equiv 1$ holds, ...

1

5 = 0101 ~5 = 1010 2 = 0010 2 & ~5 = 0010 = 2 Meanwhile, when you work with logical operators, you work with booleans so you can't plug in a random integer and expect it to have a meaningful result. It's probable that the behaviour of the python interpreter or C compiler is to only look at the first bit of the integer. In C logical is &&, ||, ...

2

You can learn more about CNF on wikipedia. In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals [...] So this rules out all formulas in your example that do not satisfy this condition. As for the rest of your question, draw the truth ...

0

If you have a proof that $(P=NP)\Leftrightarrow (P\not= NP)$ then $P=NP$ is proveable is equivalent to $P\not= NP$ is provable. This would mean that neither $P=NP$ nor $P\not= NP$ is provable. But if there would be a proof, that $P=NP$ is not provable then it would be proven that one cannot find an efficient algorithm for SAT or any other $NP$-complete ...

1

If P=NP implies P≠NP, then P≠NP (unconditionally). Similarly, if P≠NP implies P=NP, then P=NP. If both are true, then both P≠NP and P=NP, and so the axioms of mathematics are inconsistent. Most (but not all) mathematicians consider this quite unlikely.

Top 50 recent answers are included