Rob Arthan rda at lemma-one.com
Sat Sep 24 09:13:31 EDT 2011

```On 23 Sep 2011, at 21:20, Taylor Dupuy wrote:

> There is an interesting way to view contradictions in Propositional logic via arithmetization:
>
> 1. Convert propositions, with propositional variables X1,X2,... into polynomials over FF_2=ZZ/ 2 ZZ with indeterminates x1, x2, ...
> X & Y <-> xy
> X or Y <-> xy + x +y
> !X <-> x+1
> True <-> 1
> False <-> 0
>
> 2. Satisfiability of a proposition is equivalent existence of solutions of polynomial equations in FF_2. If P(X1,X2,...,Xn) is a proposition and p(x1,x2,...,xn) is its associated polynomial the P is satisfiable if and only if p=1 admits a solution over FF_2. For example the proposition X & !X is clearly not satisfiable which corresponds to the fact that x(x+1)=1 or x^2+x +1 =0 has no solutions over FF_2.
>
> One would think then that a canonical way to extend truth values in propostional logic would be to allow values in FF_2[x]/(x^2+x+1) (or the relevant extension for an unsatisfiable proposition) and carry the truth tables back over to logic via (1). I've never heard of a theory but have always wondered if its already been developed and what it would look like.

It is an interesting idea to look for multi-valued logics with the truth values ranging over finite FF_2 algebras, but for the example you suggest, it would have to be quite an unusual logic. A very weak requirement is a notion of logical strength, i.e., a partial ordering on truth values such that a <= a & a, for every a. In your example, you can't have that, since with y = (x+1), you have x & x = x^2 = y and y & y = y^2 = x, giving x <= y <= x, but x /= y. Something similar goes wrong for the algebras you get if you replace x^2 + x + 1 by any of the other three quadratic polynomials over FF_2.

Regards,

Rob.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20110924/5e85a3bb/attachment.html>
```