Изменения

Перейти к: навигация, поиск

Теорема Шамира

Нет изменений в размере, 19:10, 19 мая 2010
PS ⊂ IP
* <tex>x \land y \to XY</tex>
* <tex>x \lor y \to X+Y-XY = 1-(1-X)(1-Y)</tex>
* <tex>\exists x \varphi(x) \to \sum\limits_{X=0}^{1} A_\varphi(X)</tex> (<tex>A_\varphi</tex> - формула, получившаяся после арифметизации <tex>\varphi</tex>.)
* <tex>\forall x \varphi(x) \to \prod\limits_{X=0}^{1} A_\varphi(X)</tex>
Результат этого выражения будет ненулевым в том и только в том случае, если исходная формула была истинна.
Анонимный участник

Навигация