1
vote
0answers
13 views

Arrow's Impossibility Theorem Using Boolean Algebra

I am currently working on a research project which involves using Boolean matrices for the proof of Arrow's Impossibility Theorem and various other lemmas and results related to quasi ordered sets. In ...
0
votes
1answer
18 views

Number of non-increasing boolean functions of $n$ booleans, up to permutations.

How many non-increasing boolean functions of $n$ boolean variables are there? I don't want to count functions that ignore some of their inputs. If two or more functions differ only by permuting their ...
0
votes
0answers
11 views

Every boolean algebra is the Lindenbaum algebra of a suitable theory

Can you suggest me a book/article/lecture notes where I can find informations about the topic: Lindenbaum Algebra and Boolean algebra? My purpose is to prove (or to sketch the proof of) the title ...
3
votes
2answers
191 views

Is it possible to derive all the other boolean functions by taking other primitives different of $NAND$?

I was reading the TECS book (The Elements of Computing Systems), in the book, we start to build the other logical gates with a single primitive logical gate, the $NAND$ gate. With it, we could easily ...
2
votes
1answer
124 views

Boolean circuits and digraphs

It is well known that connecting NAND gates allows the construction of arbitrary circuits. Furthermore, a NAND gate can be represented as a digraph with four vertices (in order, the two inputs, the ...
1
vote
1answer
92 views

Localizations of the Boolean Ring P(X)

Given a set $X$, we can construct the Boolean ring whose elements are the power set of $X$. The multiplication therein is intersection, and the addition is symmetric difference. I am interested in ...
0
votes
0answers
94 views

Standard references for boolean algebra?

I'm wondering what books are considered standard references these days, for boolean algebra. I have: Givant & Halmos, Introduction to Boolean Algebras (2010); Sikorsi, Boolean Algebras (3rd ed., ...
3
votes
1answer
196 views

What is the “Boolean algebra fragment of RA”?

The Wikipedia article on Relation Algebra notes that this is a formal system which has essentially the same expressive power as the three-variable fragment of first-order logic. Peano Arithmetic can ...