# Questions tagged [boolean-algebra]

Boolean algebras are structures which behave similar to a power set with complement, intersection and union. Use this tag for questions about Boolean algebras as structures, or about functions defined from/to Boolean algebras. For Boolean logic use the tag propositional-calculus.

2,214 questions
225 views

### Boolean algebra probability not coming out right

Assuming A,B,C,D are mutually independent. $P[(A\cup\overline{B}\cup C)\cap(A\cup C \cup \overline{D})]$ I get $(P(A) + 1 - P(B) + P(C))(P(A) + P(C) + 1 - P(D))$ But when I plug in the numbers, I ...
295 views

### Simple functions and axiom of choice

The question I have is more of a curiosity, and that is why I decided to post here instead of Mathoverflow. Before posing the question, let me set up some background. Background: Let $\Omega$ be a ...
152 views

### Low degree approximation of the polynomial extension of the logical-or function

Let $x\in\{0,1\}^n$ be a binary vector of dimension $n$, and let $OR(x)$ be the "logical or" function (i.e., returns $1$ if at least one of the coordinates is $1$ and otherwise returns $0$). Consider ...
222 views

### Extending the logical-or function to a low degree polynomial over a finite field

Let $x\in\{0,1\}^n$ be a binary vector of dimension $n$, and let $OR(x)$ be the "logical or" function (i.e., returns $1$ if at least one of the coordinates is $1$ and otherwise returns $0$). Is there ...
6k views

### All finite boolean algebras have an even number of elements?

This seems obvious but I wanted to check, since I don't see it mentioned anywhere. If we define a boolean algebra as having at least two elements, then that algebra has a minimal element (0) and a ...
31k views

### Boolean algebra question: Converting between sum-of-products and product-of-sums

NOTE: $b'$ means $b$ not I'm trying to convert $ab'd + ab'cf$ to product of sums form My professor gave us the following hint: "Invert the equation, reduce it to sum-of-products, then ...
76 views

### Search the OR of negation between boolean algebra

I have this formula $$(a\cdot b)+(\neg a\cdot \neg b)$$ At first I thought this kind of $a+\neg a = 1$ so the answer is 1, but then I realized $(\neg a\cdot \neg b) \neq \neg (a\cdot b)$. I try to do ...
217 views

### What's a structure where $a-a = 1$ and $a\cdot a^{-1} = 0$?

I'm trying to specify a structure that has the basic features of a Boolean algebra but not necessarily restricted to binary sets. However, I observed that I almost have a field except that adding/...
2k views

### Sum of Products (Boolean Algebra)

I am having real trouble getting to the corrects answers when asked to simply Sum of products expressions. For instance: Determine whether the left and right hand sides represent the same function:...
348 views

### Karnaugh Map for an expression with two terms

When I have an expression such as: $f(x_1,x_2,x_3)= \sum m(1,4,7)+ D(2,5)$ What do I do with the part D(2,5)? Do I make a second k-map just for that term and OR(+) it to the expression or should I ...
219 views

### Can $A+\bar{A}\bar{B}+BC$ get any simpler?

I've simplified this Boolean formula quite a bit. Can it get any simpler? My definition of simple in this case is using the least amount of operators (and, or) Title is "A or (negative A and negative ...
95 views

3k views

### How many presentable boolean functions with n attributes are linear separable?

The aim is to find a formula for the question. For $n=2$ i get $2^{2^n}=16$ possible functions. This is the solution for a boolean function with 2 attributes: ...
I am reading this document. What is the meaning of $[n]$ ? Is it power set of $\{1,2,3...n\}$?
Suppose that we have two varieties of algebras $A$ and $B$, whose operators all have arities less than some regular cardinal, and such that every $B$-algebra (please correct me if this is not the ...