scientific article; zbMATH DE number 1544631
Tihs book presents several Russian contributions to the study of Post classes of Boolean functions. Recall that this term designates those classes of truth functions that are closed with respect to superpositions. A new approach to the determination of the partially ordered set (with respect to inclusion) of all these classes is provided in Chapter 1, and for each class a finite basis is displayed. Chapter 2 studies classes of predicates over \(\{0,1\}\), closed with respect to \(\&\), \(\exists x_i\) and replacement of variables. A (Boolean) function \(f\) of \(n\) variables is said to preserve a (Boolean) predicate \(\rho\) of \(k\) variables provided \[ \rho(x_{11},\dots, x_{k1})\& \cdots \& \rho(x_{1n},\dots, x_{kn})\Rightarrow \rho(f(x_{11},\dots, x_{1n}),\dots, f(x_{k1},\dots, x_{kn})). \] For every set \(R\) of predicates, \(\text{Pol}(R)\) denotes the set of those functions which preserve \(\rho\) for all \(\rho\in R\). For every set \(F\) of functions, \(\text{Inv}(F)\) denotes the set of those predicates which are preserved by all \(f\in F\). Then Inv and Pol establish a contravariant Galois connection between the powerset of the set of all Boolean functions and the powerset of the set of all Boolean predicates. The Galois-closed classes \(F= \text{Pol}(\text{Inv}(F))\) are exactly those closed classes \(F\) which contain all the projections, that is, all closed classes except the three minimal classes of the poset of closed classes. The Galois-closed classes \(R= \text{Inv}(\text{Pol}(R))\) are exactly those closed classes \(R\) which contain all the diagonals (the diagonal of an equivalence relation \(\varepsilon\) on the set \(\{1,\dots,k\}\) is the predicate \(i\varepsilon j\Rightarrow x_i= x_j\)). The chapter also provides a characterization of those closed classes which can be written in the form \(\text{Pol}(R)\) where \(R\) is a finite set of predicates, as well as an explicit list of them. Chapter 3 extends the previous theory to classes of function vectors \((f_1,\dots, f_m)\). Chapter 4 introduces three new closures for classes of Boolean functions, called parametric closure, positive closure and \(S\)-closure. There are 25 parametric-closed classes and a characterization of parametric completeness is provided. There are 6 positive-closed classes and 15 \(S\)-closed classes. Reviewer's remarks: 1) In order to define the closed classes under investigation, the author unncessarily passes through formal expressions which are carelessly defined. 2) The terms ``Galois theory and ``Post algebra are used in a sense which is not the conventional one: the latter correspond to the MSC Classification sections 12F10 and 03G20, respectively.
- scientific article; zbMATH DE number 51303
- Characterizations of closed classes of Boolean functions in terms of forbidden subfunctions and Post classes
- Post classes characterized by functional terms
- Positively closed classes of partial Boolean functions
- On composition-closed classes of Boolean functions
- Orders of discriminator classes in multivalued logic
- Mixed id-expansion of multivalued logic functions
- Closed classes containing a homogeneous function class
- On orders of closed classes containing a homogeneous switching function
- Post classes characterized by functional terms
- Galois correspondence related to extension of charges on \(\sigma\)-class of subset of a finite set
- Infinitely generated classes of 01-functions of three-valued logic
- Closure operators with positive connectives and quantifiers
- Characterizations of closed classes of Boolean functions in terms of forbidden subfunctions and Post classes
- Positively closed classes of partial Boolean functions
- To the problem of expressibility in the algebra of partial Boolean functions
- Parametric closed classes of hyperfunctions on two-element set
- Closed classes of Boolean functions. 2nd ed.
- scientific article; zbMATH DE number 4214083 (Why is no real title available?)
- scientific article; zbMATH DE number 3906400 (Why is no real title available?)
- scientific article; zbMATH DE number 3924776 (Why is no real title available?)
- scientific article; zbMATH DE number 51303 (Why is no real title available?)
- On superstructure of class of k-valued quasiuniform functions
- Schaefer classes, Post classes and Galois connections
- On the structure of equationally closed classes
- Equational closure
- On the structure of partially ordered sets of Boolean degrees
- The algebraic structure of the densification and the sparsification tasks for CSPs
- Reduction theorems in the social choice theory
- Logical extensions of the parametric closure operator
- On positive completeness and positively closed sets of multifunctions of rank 2
- Mutual generation of the choice and majority functions
- Existence of finite bases in closed classes of Boolean functions
- On the lattice of \(ES_I\)-closed classes of multifunctions on two-elements set
- On the enumeration closure operator in multivalued logic
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4520903)