A set F of Boolean functions is said to be functionally complete if every Boolean function is definable by combining functions in F. Post clarified when a set of Boolean functions is functionally complete (with respect to classical semantics). In this paper, by extending Post’s theorem, we clarify when a set of Boolean functions is functionally complete with respect to Kripke semantics.

The problem of enumerating the types of Boolean functions under the group of variable permutations and complementations was first stated by Jevons in the 1870s. but not solved in a satisfactory way until the work of Pólya in 1940. This paper explains the details of Pólya's solution, and also the history of the problem from the 1870s to the 1970s.

We describe sets of partial Boolean functions being closed under the operations of superposition. For any class A of total functions we define the set ????(A) consisting of all partial classes which contain precisely the functions of A as total functions. The cardinalities of such sets ????(A) can be finite or infinite. We state some general results on ????(A). In particular, we describe all 30 closed sets of partial Boolean functions which contain all monotone and zero-preserving total (...) class='Hi'>Boolean functions. (shrink)

Using Koszmider's strongly unbounded functions, we show the following consistency result: Suppose that κ, λ are infinite cardinals such that κ++ + ≤ λ, κ<κ = κ and 2κ = κ+, and η is an ordinal with κ+ ≤ η < κ++ and cf = κ+. Then, in some cardinal-preserving generic extension there is a superatomic Boolean algebra equation image such that equation image, equation image for every α < η and equation image. Especially, equation image and equation image (...) can be cardinal sequences of superatomic Boolean algebras. (shrink)

Boolean games are a logical setting for representing strategic games in a succinct way, taking advantage of the expressive power and conciseness of propositional logic. A Boolean game consists of a set of players, each of which controls a set of propositional variables and has a specific goal expressed by a propositional formula. We show here that Boolean games are a very simple setting, yet sophisticated enough, for analysing the formation of coalitions. Due to the fact that (...) players have dichotomous preferences, the following notion emerges naturally: a coalition in a Boolean game is efficient if it has the power to guarantee that all goals of the members of the coalition are satisfied. We study the properties of efficient coalitions. (shrink)

We show: The Boolean Prime Ideal theorem BPI is equivalent to each one of the statements: “For every family (Xi=(Xi,Ti))i∈I of compact spaces, for every family G={⋃{πi−1(Fij):i∈Qj}:j∈J} of basic closed sets of the product X=∏i∈IXi with the fip there is a family of subbasic closed sets H (H⊂{πi−1(F):i∈I,Fc∈Ti}) with the fip such that for every j∈J,H∩{πi−1(Fij):q∈Qj}≠⌀”. “For every compact Loeb space Y (the family of all non empty closed subsets of Y has a choice function) and for every (...) set X the product YX is compact”. AC fin (: the axiom of choice restricted to families of finite sets) implies “every well ordered product of cofinite topologies is compact” and “every well ordered basic open cover of a product of cofinite topologies has a finite subcover”. CAC fin (: the axiom of choice restricted to countable families of finite sets) iff “every countable product of cofinite topologies is compact”. BPI(ω) (: every filter of ℘(ω) extends to an ultrafilter) is equivalent to the proposition “for every compact Loeb space Y having a base of size ≤|R| and for every set X of size ≤|R| the product YX is compact”. (shrink)

The use of Boolean algebra in logic, switching and automata theory, coding and other technically oriented areas is well known. The role of this paper is to show that Boolean algebra can be instrumental in taking economic decisions.By a pseudo-Boolean function, a real-valued function with bivalent (0–1) variables will be understood. The symbols 0 and 1 will stay both for their logical meaning and their arithmetical value.The basic problems which arise frequently in connection with pseudo- (...) class='Hi'>Boolean functions are: (1) solution of systems of equations and/or inequalities involving only pseudo-Boolean functions, (2) problems of determining the maximum or the minimum of a free pseudo-Boolean function, or of a pseudo-Boolean function whose variables are subject to constraints; (3) problems of finding the minimax or the maximin of a pseudo-Boolean function.The basic problems outlined above are exemplified on the case of a company wishing to locate a number of service stations, which - under different assumptions - lead to the above formulated models. (shrink)

We study the extension 123) of the theory S21 by instances of the dual weak pigeonhole principle for p-time functions, dWPHPx2x. We propose a natural framework for formalization of randomized algorithms in bounded arithmetic, and use it to provide a strengthening of Wilkie's witnessing theorem for S21+dWPHP. We construct a propositional proof system WF , which captures the Π1b-consequences of S21+dWPHP. We also show that WF p-simulates the Unstructured Extended Nullstellensatz proof system of Buss et al. 256). We prove that (...) dWPHP is equivalent to a statement asserting the existence of a family of Boolean functions with exponential circuit complexity. Building on this result, we formalize the Nisan–Wigderson construction in a conservative extension of S21+dWPHP. (shrink)

Equational Boolean Relation Theory concerns the Boolean equations between sets and their forward images under multivariate functions. We study a particular instance of equational BRT involving two multivariate functions on the natural numbers and three infinite sets of natural numbers. We prove this instance from certain large cardinal axioms going far beyond the usual axioms of mathematics as formalized by ZFC. We show that this particular instance cannot be proved in ZFC, even with the addition of slightly weaker (...) large cardinal axioms, assuming the latter are consistent. (shrink)

The no-no paradox and its generalizations (called no-no type) are self-referential statements whose paradoxicality arises from the impossibility of symmetric truth-value assignments imposed by syntactical symmetry. Their syntactic symmetry can be characterized by permutation groups. This paper addresses whether any permutation group can be represented by a no-no type paradox, in the sense that the symmetry of the paradox is precisely characterized by the group. By introducing the notion of invariance preorder for binary sequences, we extend the algebraic techniques from (...) research on the representability of the permutation groups by Boolean functions. We prove that for $$n\ge 4$$, the alternating group $$A_n$$ and the symmetric group $$S_n$$ have the same invariance preorder. Consequently, we establish the main result of this paper: for any $$n\ge 4$$, the alternating group $$A_n$$ cannot be represented by any Boolean system of self-referential statements — and _a fortiori_, by any no-no type paradox. With the information of the invariance preorder for $$S_n$$, we give a systematic construction of both Boolean paradoxes and no-no type paradoxes with maximal symmetry. Our results reveal a profound connection between algebraic symmetry and semantic pathology. (shrink)

In conventional generalization of the main results of classical measure theory to Stone algebra valued measures, the values that measures and functions can take are Booleanized, while the classical notion of a σ-field is retained. The main purpose of this paper is to show by abundace of illustrations that if we agree to Booleanize the notion of a σ-field as well, then all the glorious legacy of classical measure theory is preserved completely.