definition of projection operation for boolean functions

457 Views Asked by At

A boolean function $f$ over a set $A$ is a subset $X\subseteq A$ and $F$ is a set of boolean functions.

I am trying to check whether $F$ is closed under projection. And I really do not know what projection here means. It is easy to check whether $F$ is closed under intersection, I get any two functions $f_i,f_j\in F$ and check whether $f_i\cap f_ j$ (i.e., the intersection of the two subsets) belongs to $F$ or not.

For projection, how should it be defined and what closed under projection means?

1

There are 1 best solutions below

2
On

This answer makes sense when $F$ is a subset of ${\cal P}({\cal P}(A))$, so that the elements of $F$ are "boolean functions", subsets of ${\cal P}(A)$, or alternatively functions $\{0,1\}^A\to\{0,1\}$. You stated that $F$ is a set of subsets of $A$, however, which is incompatible with this assumption. My only guess in this case is that the projections are the sets $f_a=\{a\}$ for $a\in A$, but this terminology is not as well-motivated.

The projections are the sets $f_a=\{x\subseteq A\mid a\in x\}$, and "$F$ is closed under projection" means $f_a\in F$ for all $a\in A$.

To understand where the terminology comes from, consider an arbitrary boolean lattice, on three generators $x,y,z$ for concreteness. Here the elements include things like $x\land y$, $(x\lor z)\land \lnot y$, etc. These can also be thought of as functions $\{0,1\}^3\to\{0,1\}$, where we assign a value from $\{0,1\}$ to each of $x,y,z$ and evaluate the ANDs and ORs in the expression. In this context, the projection $p_1$ that selects the first coordinate from $v\in\{0,1\}^3$ is a boolean function, whose expression is just $x$. Similarly, the other projection functions are $y$ and $z$.

Now consider what this means if we instead have the boolean lattice being ${\cal P}(A)$ with union and complement as the operations. The function $p_i$ can be written explicitly as $p_i(v)=v_i$, and if we replace $v_i$ with $i\in v$ (where $v$ is now a subset of $A$) we get $v\in p_i\leftrightarrow i\in v$, which can be expressed as a class abstraction as $f_a=\{x\subseteq A\mid a\in x\}$.