Skip to main content
added 2 characters in body
Source Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

There is no need to simplify the formula, you just evaluate it recursively according to the definition of the boolean operators in use.

Let $\varphi$ a boolean formula and $a$$a : X_\varphi \to \{0,1\}$ an assignment of all variables. Then, denote with $\varphi(a)$ the result of replacing all variables that occur in $\varphi$ with the corresponding values from $a$. This is clearly possible in time $O(|\langle\varphi\rangle|)$, if $\langle . \rangle$ is a reasonable encoding of formulae.

Now we define the evaluation function $\operatorname{eval}$$\operatorname{eval}_a$ on variable-free boolean expressions in the following way:

$\qquad \begin{align} \operatorname{eval}(\text{true}) &= 1 \\ \operatorname{eval}(\text{false}) &= 0 \\ \operatorname{eval}(\lnot \varphi) &= 1 - \operatorname{eval}(\varphi) \\ \operatorname{eval}(\varphi \land \psi) &= \operatorname{eval}(\varphi) \cdot \operatorname{eval}(\psi) \\ \operatorname{eval}(\varphi \lor \psi) &= \max(\operatorname{eval}(\varphi), \operatorname{eval}(\psi)) \\ & \vdots \end{align}$$\qquad \begin{align} \operatorname{eval}_a(\text{true}) &= 1 \\ \operatorname{eval}_a(\text{false}) &= 0 \\ \operatorname{eval}_a(x) &= a(x) \\ \operatorname{eval}_a(\lnot \varphi) &= 1 - \operatorname{eval}_a(\varphi) \\ \operatorname{eval}_a(\varphi \land \psi) &= \operatorname{eval}_a(\varphi) \cdot \operatorname{eval}_a(\psi) \\ \operatorname{eval}_a(\varphi \lor \psi) &= \max(\operatorname{eval}_a(\varphi), \operatorname{eval}_a(\psi)) \\ & \vdots \end{align}$

Clearly, $\operatorname{eval}(\varphi(a)) = 1$$\operatorname{eval}_a(\varphi) = 1$ if and only if $\varphi(a) \mathop{|\!\!\!==\!\!\!|} \text{true}$; if$a(\varphi) \mathop{|\!\!\!==\!\!\!|} \text{true}$ (here, $a$ is continued on $\varphi$ in a syntactical manner: it replaces all variable occurrences $x$ in $\varphi$ with $a(x)$). If in doubt, perform a structural induction along the inductive definition of boolean formulae. Furthermore, $\operatorname{eval}$$\operatorname{eval}_a$ performs about one operation per operator, and literal; thus it runs in time $O(|\langle \varphi \rangle|)$.

There is no need to simplify the formula, you just evaluate it recursively according to the definition of the boolean operators in use.

Let $\varphi$ a boolean formula and $a$ an assignment of all variables. Then, denote with $\varphi(a)$ the result of replacing all variables in $\varphi$ with the corresponding values from $a$. This is clearly possible in time $O(|\langle\varphi\rangle|)$, if $\langle . \rangle$ is a reasonable encoding of formulae.

Now we define the evaluation function $\operatorname{eval}$ on variable-free boolean expressions in the following way:

$\qquad \begin{align} \operatorname{eval}(\text{true}) &= 1 \\ \operatorname{eval}(\text{false}) &= 0 \\ \operatorname{eval}(\lnot \varphi) &= 1 - \operatorname{eval}(\varphi) \\ \operatorname{eval}(\varphi \land \psi) &= \operatorname{eval}(\varphi) \cdot \operatorname{eval}(\psi) \\ \operatorname{eval}(\varphi \lor \psi) &= \max(\operatorname{eval}(\varphi), \operatorname{eval}(\psi)) \\ & \vdots \end{align}$

Clearly, $\operatorname{eval}(\varphi(a)) = 1$ if and only if $\varphi(a) \mathop{|\!\!\!==\!\!\!|} \text{true}$; if in doubt, perform a structural induction along the inductive definition of boolean formulae. Furthermore, $\operatorname{eval}$ performs about one operation per operator, thus it runs in time $O(|\langle \varphi \rangle|)$.

There is no need to simplify the formula, you just evaluate it recursively according to the definition of the boolean operators in use.

Let $\varphi$ a boolean formula and $a : X_\varphi \to \{0,1\}$ an assignment of all variables that occur in $\varphi$. Now we define the evaluation function $\operatorname{eval}_a$ on variable-free boolean expressions in the following way:

$\qquad \begin{align} \operatorname{eval}_a(\text{true}) &= 1 \\ \operatorname{eval}_a(\text{false}) &= 0 \\ \operatorname{eval}_a(x) &= a(x) \\ \operatorname{eval}_a(\lnot \varphi) &= 1 - \operatorname{eval}_a(\varphi) \\ \operatorname{eval}_a(\varphi \land \psi) &= \operatorname{eval}_a(\varphi) \cdot \operatorname{eval}_a(\psi) \\ \operatorname{eval}_a(\varphi \lor \psi) &= \max(\operatorname{eval}_a(\varphi), \operatorname{eval}_a(\psi)) \\ & \vdots \end{align}$

Clearly, $\operatorname{eval}_a(\varphi) = 1$ if and only if $a(\varphi) \mathop{|\!\!\!==\!\!\!|} \text{true}$ (here, $a$ is continued on $\varphi$ in a syntactical manner: it replaces all variable occurrences $x$ in $\varphi$ with $a(x)$). If in doubt, perform a structural induction along the inductive definition of boolean formulae. Furthermore, $\operatorname{eval}_a$ performs about one operation per operator and literal; thus it runs in time $O(|\langle \varphi \rangle|)$.

Source Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

There is no need to simplify the formula, you just evaluate it recursively according to the definition of the boolean operators in use.

Let $\varphi$ a boolean formula and $a$ an assignment of all variables. Then, denote with $\varphi(a)$ the result of replacing all variables in $\varphi$ with the corresponding values from $a$. This is clearly possible in time $O(|\langle\varphi\rangle|)$, if $\langle . \rangle$ is a reasonable encoding of formulae.

Now we define the evaluation function $\operatorname{eval}$ on variable-free boolean expressions in the following way:

$\qquad \begin{align} \operatorname{eval}(\text{true}) &= 1 \\ \operatorname{eval}(\text{false}) &= 0 \\ \operatorname{eval}(\lnot \varphi) &= 1 - \operatorname{eval}(\varphi) \\ \operatorname{eval}(\varphi \land \psi) &= \operatorname{eval}(\varphi) \cdot \operatorname{eval}(\psi) \\ \operatorname{eval}(\varphi \lor \psi) &= \max(\operatorname{eval}(\varphi), \operatorname{eval}(\psi)) \\ & \vdots \end{align}$

Clearly, $\operatorname{eval}(\varphi(a)) = 1$ if and only if $\varphi(a) \mathop{|\!\!\!==\!\!\!|} \text{true}$; if in doubt, perform a structural induction along the inductive definition of boolean formulae. Furthermore, $\operatorname{eval}$ performs about one operation per operator, thus it runs in time $O(|\langle \varphi \rangle|)$.