Wikipedia:Reference desk/Archives/Mathematics/2019 March 2

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 2

Tseytin transformation

Let $\varphi (x)$ be a boolean fomula over the variable $x\in \{0,1\}^{n}$. We apply Tseytin transformation on $\varphi (x)$, and get another formula $\psi (x,y)$ over the variables $x\in \{0,1\}^{n},y\in \{0,1\}^{m}$.

Is it true that $\forall x.\varphi (x)\leftrightarrow (\exists y.\psi (x,y))$? David (talk) 15:40, 2 March 2019 (UTC)

To make it clear: Tseytin transformation adds new variables, and this is why the new vector variable $y$ was added. David (talk) 19:47, 2 March 2019 (UTC)

First, not my area of expertise so fair warning. The article is poorly referenced and generally not that clearly written, but a Google search turned up [1], which seems to be a draft but otherwise is more readable. (I'm sure there are other sources at least as good out there, but this one serves the purpose.) Anyway, what you've stated seems to the gist of the second part of Theorem 1. Specifically, the statement "That is, any truth assignment M_Vφ⊂V_φ is a model for φ if and only if there is a truth assignment M₁⊂{v_n,v_n+1,...,v_i} such that M_Vφ∪M₁ is a model for ψ," is, allowing for changes in notation etc., the same as what you have.

From what I've read, a Tseytin transformation can be "implemented" in different ways, meaning the way each operation is rewritten is arbitrary as long as the result is equivalent (in the appropriate sense) to the original operation. So there are many possible Tseytin transformations, but one of the defining characteristics is the property in question. --RDBury (talk) 20:46, 3 March 2019 (UTC)