Friday, February 8, 2013

Polarity in Propositional Logic

The polarity of a Boolean variable in a formula is recursively defined,

  • $p$ occurs positively in $p$ itself.
  • If $p$ occurs positively in $\phi$, then $\neg p$ occurs negatively in $\phi$, vice versa.
  • If $p \wedge q$ or $p \vee q$ occur positively in $\phi$, then $p$ and $q$ occurs positively in $\phi$, and negatively for the negative occurrence.
  • If $p \rightarrow q$ occurs positively in $\phi$, then $p$ negatively, $q$ positively. (i.e. $\neg p \vee q $)
  • If $p \leftrightarrow q$ occurs in $\phi$, then $p$ and $q$ occur both negatively and positively in $\phi$.

Example:

$$B_1 \vee B_2 \vee B_3 \vee B_4$$

$B_1 \vee ( \cdots)$ occurs positively in itself. $B_1$ occurs positively since the former disjunction occurs positively. The same for all the other variables.

1 comment: