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.

1
vote
2answers
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 ...
6
votes
1answer
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 ...
1
vote
2answers
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 ...
2
votes
1answer
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 ...
7
votes
2answers
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 ...
1
vote
1answer
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 ...
0
votes
2answers
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 ...
3
votes
1answer
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/...
3
votes
2answers
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:...
1
vote
2answers
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 ...
2
votes
2answers
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 ...
0
votes
1answer
95 views

If $B$ is a finite boolean alebgra and $a_1,\ldots,a_k$ are the atoms of $B$: $\forall i$ $a_ix=a_i x$, why is $x=a_1+\ldots +a_k$

Let $B$ be a finite boolean algebra. Define for $a,b\in B$ $a\leq b$ if $ab=a$ If $x\in B$ and $a_1,\dots,a_k$ are the atoms of B (e.g. $a\neq 0$ and if $b\in B$ such that $0\leq b \leq a$ then $b=...
3
votes
3answers
216 views

The sum of a polynomial over a boolean affine subcube

Let $P:\mathbb{Z}_2^n\to\mathbb{Z}_2$ be a polynomial of degree $k$ over the boolean cube. An affine subcube inside $\mathbb{Z}_2^n$ is defined by a basis of $k+1$ linearly independent vectors and an ...
1
vote
1answer
78 views

The fraction of k-juntas with low influences in all of the coordinates

Let $f:\{-1,1\}^n\to\{-1,1\}$ be a boolean function. Define the influence of the $i$'th coordinate of $f$ as follows: $$\operatorname{Inf}_i(f)=\Pr_{x}[f(x)\neq f(\hat x_i)]$$ where $x$ is uniformly ...
0
votes
1answer
181 views

Boolean Algebra / Digital Logic

I am trying to figure out how to simply a canonical sum of products expression that is from this expression: $$ f_1(x_1,x_2,x_3) = \sum m (2,3,4,6,7) $$ where m is canonical minterms I got: $$ \...
2
votes
2answers
728 views

Proof that the ring-sum expansion of a binary function is unique

I am trying to understand a proof that the ring-sum expansion of a binary function is unique. The proof is as follows. Proof. By induction on the number of inputs $n$. For $n=1$, $f(x)=0$ or $f(x)=...
4
votes
1answer
359 views

A Boolean function with total influence 1 must be a dictatorship

Let $f:\{-1,1\}^n\to\{-1,1\}$ be a boolean function. Define the influence of the $i$'th coordinate of $f$ as follows: $$\operatorname{Inf}_i(f)=\Pr_{x}[f(x)\neq f(\hat x_i)]$$ where $x$ is uniformly ...
3
votes
2answers
87 views

Parity is the only function with maximal influences

Let $f:\{-1,1\}^n\to\{-1,1\}$ be a boolean function. Define the influence of the $i$'th coordinate of $f$ as follows: $$\operatorname{Inf}_i(f)=\Pr_{x}[f(x)\neq f(\hat x_i)]$$ where $x$ is uniformly ...
2
votes
1answer
5k views

How to prove that any x in a complemented distributive lattice cannot have two complements?

How can I prove the following statement? In a complemented lattice, if there exist two complements for any x then the lattice is not distributive. I thought of showing that, in a complemented and ...
2
votes
2answers
636 views

Prove something using the Algebraic Foundation of the Boolean Algebra

When asked to prove a specific equation for a boolean algebra by using the "Algebraic Foundation of Algebra Boole" (I don't know how accurate that translation is. In greek I found it as "αλγεβρική ...
1
vote
1answer
725 views

Lattices - How to prove a simple inequality?

Lattices are kind of new to me and I'm not yet familiar with all of their properties so excuse me if what I'm asking here is extremely basic or easy. How can I prove the following inequality for a ...
0
votes
1answer
82 views

What is name of “random boolean” algebra with set containing 0, random, and 1?

I imagine an algebra on the set of three values with an addition operation like this: ...
4
votes
4answers
29k views

Can someone explain consensus theorem for boolean algebra

In boolean algebra, below is the consensus theorem $$X⋅Y + X'⋅Z + Y⋅Z = X⋅Y + X'⋅Z$$ $$(X+Y)⋅(X'+Z)⋅(Y+Z) = (X+Y)⋅(X'+Z)$$ I don't really understand it? Can I simplify it to $$X&#...
0
votes
3answers
834 views

Equality in Boolean Algebra

Say, $$A = C \lor (C\land D) = C \land(1\lor D) = C$$ $$A = C \lor (C\land D) = (C\lor D)\land(C\lor C) = C\land(C\lor D)$$ Now, the part I don't understand here is if we equate we get: $$C \land (...
4
votes
0answers
271 views

Can the reduced product construction generate boolean-valued models?

In model theory, the reduced product construction contains a collection of structures or models, a set $I$ that indexes the collection, and a filter $U$ on $I$. Ultraproducts are a special case of ...
0
votes
1answer
112 views

Interior algebras: an element need not be distinct from its interior?

There is a Wikipedia article about interior algebras. An interior algebra is a Boolean algebra with an additional unary operator, the interior operator, satisfying certain additional axioms. The ...
6
votes
2answers
297 views

Axioms for atomless Boolean algebras

I'm embarrassed to be asking, but: "Write down a set of axioms for the theory of atomless Boolean algebras." This is Exercise 1.14 in Chapter 9 of "Models and Ultraproducts" by Bell and Slomson. I'm ...
11
votes
2answers
2k views

Examples of topologies in which all open sets are regular?

An open subset U of a space X is regular if it equals the interior of its closure, as we learn from the Wikipedia glossary of topology. Furthermore, the regular open subsets of a space (any space) ...
2
votes
1answer
109 views

Topological terminology: name for complement of closure

In "Introduction to Boolean Algebras" the authors introduce a symbol for the complement of the closure of P, where P is a set in a topological space (Ch. 9, p. 60). This is in the context of ...
0
votes
3answers
358 views

Minimize Boolean function

I have got some silly task, but I am quite confused. Need to minimize function. $$f(x_1,x_2,x_3,x_4)=x_1x_2+x_1x_3+x_1x_4+x_2x_3+x_2x_4.$$ Thanks. Sorry for my English. Minimize Boolean function
6
votes
2answers
517 views

Boolean algebras without atoms

Why is the theory of Boolean algebras without atoms $\omega$-categoric?
19
votes
6answers
69k views

Is XOR a combination of AND and NOT operators?

I'm not sure whether this is the best place to ask this, but is the XOR binary operator a combination of AND+NOT operators?
2
votes
1answer
299 views

Mathematica fails with boolean simplification with exponents

I have a truly simple inequality, which I want to prove using Mathematica: $$ a^x \geq 1 ,\quad \quad with \quad 1\leq a \quad and \quad 1\leq x \quad a,x \in R$$ This is obviously true. When I try ...
4
votes
3answers
3k views

boolean algebra simplification

a) $(\lnot(P \land Q)) \lor (Q \land R)$ b) $(P \lor Q) \land \lnot(Q)$ How do I simplify these 2 expression?
1
vote
1answer
5k views

Degree of boolean functions

How can we compute the degree of boolean function? I encountered with this,while solving a problem given in my assignment module which is, How many different boolean functions of degree 1 and 2 ...
3
votes
1answer
230 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 ...
2
votes
1answer
419 views

Working with Conditions or Assumptions in Mathematica with boolean operators

I have the following code: $Assumptions = {x > 0} b[x_] := x^2 b'[x] > 0 In my (very basic) understanding of Mathematica, this should give me me the Output ...
1
vote
1answer
165 views

If you have a boolean function with only “true” and “don't care” (no false) outcomes, how would you write the equation?

In my homework I came across a situation where I had a Karnaugh map that only contained don't cares and trues. Since there are no false outputs possible, it seems like the equation would just be f(x,y,...
1
vote
1answer
1k views

Boolean Expression Orders of Operation

Using DeMorgan's Law, write an expression for the complement of F if F(w, x, y, z) = xyz'(y'z + x)' + (w'yz + x') F' = (xyz'(y'z + x)' + (w'yz + x'))' = (xyz'(y'z + x)')' * (w'yz + x')' = ( (xyz')...
4
votes
1answer
16k views

Can (x'y' + xy) be simplified?

I started with (AB' + A'B)' and ended up with (A'B' + AB). Is this all the farther I can go? I feel like this is always going to be true, but I'm not sure how to prove it algebraically.
1
vote
1answer
128 views

Boolean simplication

I'm trying to simplify the following booleans: $$Y=[\overline{ \overline{(A+B)} \quad \overline{(C+D)}}]$$ My solution is: $$Y=[\overline{ \overline{(A+B)} \quad\overline{(C+D)}}]$$ $$ = [\overline{...
1
vote
2answers
413 views

Proving a statement by contradiction

Not sure if many of you speak binary, but the question is to prove that 2n bits are sufficient to store the product of two unsigned n-bit numbers (i.e., there will be no overflow). I've thought of a ...
32
votes
1answer
2k views

Universal binary operation and finite fields (ring)

Take Boolean Algebra for instance, the underlying finite field/ring $0, 1, \{AND, OR\}$ is equivalent to $ 0, 1, \{NAND\} $ or $ 0, 1, \{ NOR \}$ where NAND and NOR are considered as universal gates. ...
0
votes
1answer
71 views

Can someone explain how this question is reduced using basic postulates

I'm looking at some class examples on basic postulates and I can't figure out how the 2nd part is reduced (see below). Could someone explain it to me? eq: ...
5
votes
2answers
8k views

Determining don't-care values in a Karnaugh Map

I'm having a hard time understanding how to find the don't-care values in a Karnaugh map. What does it even mean? If I have a boolean function, say $f(a,b,c,d)=a'bc+abc'+bc'd+a'bc'd$, how would I ...
2
votes
0answers
240 views

bent and hyper-bent boolean functions

Is the AND logic function considered to be a bent function. If so, how would you make a hyper-bent function using logic gates? Thanks!
7
votes
1answer
64k views

Question on essential prime implicants

I am having some trouble understand essential prime implicants. So if a minterm is not covered by another overlapping rectangle, then that is an EPI. However, if we make a K-map for $f(x,y,z)=xy+xz&#...
1
vote
1answer
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: ...
2
votes
2answers
429 views

What does [n] mean here?

I am reading this document. What is the meaning of $[n]$ ? Is it power set of $\{1,2,3...n\}$?
1
vote
1answer
174 views

Can nonisomorphic algebras generate isomorphic relatively free algebras?

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 ...