Section: Examples of Propositions With Different Syntactic Forms but the Same Boolean Function

Example 1

If $x$ is a Boolean variable then the disjunctions. Different Syntax | Same Semantics for a given interpretation $I$ | Same Boolean functions :------------- |:------------- |:------------- $x\neq$ |$I\models x\Leftrightarrow$ |$f_x=$ $x\vee x\neq$ |$I\models x\vee x\Leftrightarrow$ |$f_{x\vee x}=$ $x\vee x\vee x\neq$ |$I\models x\vee x\vee x\Leftrightarrow$ |$f_{x\vee x\vee x}=$ $x\vee x\vee x\vee x\neq$ |$I\models x\vee x\vee x\vee x\Leftrightarrow$ |$f_{x\vee x\vee x\vee x}=$ $\ldots$|$\ldots$|$\ldots$

are syntactically different Boolean terms (propositions), but they still have the same semantics. Therefore, by definition of Boolean functions, they constitute the same Boolean function.

Example 2

The same Boolean function might even be represented by propositions containing more than one variable. Let $x$ and $y$ be Boolean variables, Consider the propositions $\phi=x$ and $\psi=(x\wedge y)\vee y$. These propositions have the same truth tables, depending on the semantics of $x$ and $y$:

$[[x]]_I$| $[[y]]_I$| $[[\phi]]_I$| $[[\psi]]_I$ $1$| $1$| $1$| $1$ $0$| $1$| $0$| $0$ $1$| $0$| $1$| $1$ $0$| $0$| $0$| $0$

Therefore, the functions $f_\phi$ and $f_\psi$ are, in fact, the same Boolean function.

Definitions: 1

Thank you to the contributors under CC BY-SA 4.0!




  1. Mendelson Elliott: "Theory and Problems of Boolean Algebra and Switching Circuits", McGraw-Hill Book Company, 1982
  2. Hoffmann, Dirk: "Theoretische Informatik, 3. Auflage", Hanser, 2015