No label defined (Q4520903)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1544631
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1544631

      Statements

      18 December 2000
      0 references
      Post classes
      0 references
      Boolean functions
      0 references
      truth functions
      0 references
      Galois connection
      0 references
      Boolean predicates
      0 references
      poset of closed classes
      0 references
      Galois-closed classes
      0 references
      function vectors
      0 references
      closures
      0 references
      0 references
      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.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references