GAP Manual: 29. Boolean Lists

This chapter describes boolean lists. A boolean list is a list that has no holes and contains only boolean values, i.e., true and false. In function names we call boolean lists blist for brevity.

Boolean lists can be used in various ways, but maybe the most important application is their use for the description of subsets of finite sets. Suppose set is a finite set, represented as a list. Then a subset sub of set is represented by a boolean list blist of the same length as set such that blist[i] is true if set[i] is in sub and false otherwise.

This package contains functions to switch between the representations of subsets of a finite set either as sets or as boolean lists (see BlistList, ListBlist), to test if a list is a boolean list (see IsBlist), and to count the number of true entries in a boolean list (see SizeBlist).

Next there are functions for the standard set operations for the subsets represented by boolean lists (see IsSubsetBlist, UnionBlist, IntersectionBlist, and DifferenceBlist). There are also the corresponding destructive procedures that change their first argument (see UniteBlist, IntersectBlist, and SubtractBlist). Note that there is no function to add or delete a single element to a subset represented by a boolean list, because this can be achieved by assigning true or false to the corresponding position in the boolean list (see List Assignment).

Since boolean lists are just a special case of lists, all the operations and functions for lists, can be used for boolean lists just as well (see Lists). For example Position (see Position) can be used to find the true entries in a boolean list, allowing you to loop over the elements of the subset represented by the boolean list.

There is also a section about internal details (see More about Boolean Lists).

This chapter contains the following sections: