Boolean algebras are structures which behave similar to a power set with complement, intersection and union. Questions regarding Boolean algebras as structures, or regarding functions defined from/to Boolean algebras fit into this tag very nicely. For Boolean logic use the tag propositional logic

learn more… | top users | synonyms

6
votes
1answer
477 views

What are the algebras of the double powerset monad?

Let $\mathscr{P} : \textbf{Set} \to \textbf{Set}^\textrm{op}$ be the (contravariant) powerset functor, taking a set $X$ to its powerset $\mathscr{P}(X)$ and a map $f : X \to Y$ to the inverse image ...
0
votes
1answer
125 views

Boolean algebra-Modular lattice

Let $L=\{a,b,c,d,e,f\}$; $P(L)$ is the set of all partitions of $L$, and $\le$ is the order relation on $P(L)$ defined as: if $r$ and $t$ are relations, then $r\le t$ iff every block in $r$ is a ...
2
votes
0answers
51 views

Name for this type of space over a boolean algebra?

The structure has two carrier sets $E$ and $A$, operators $({}^*, \wedge)$ over $E$, and a ternary "decision" operator $D:E \times A \times A \to A$, written infix $(p?a:b)$, whose intended meaning is ...
1
vote
1answer
154 views

Find an optimal 4-tuple which satisfies a boolean expression

(I have post a question with bounty for several days (Find a best 4-tuple which fulfils a variable boolean formula), but unfortunately got no answer yet. Here I simplify it to a smaller problem and ...
0
votes
1answer
108 views

Decompose boolean function of multiple variables into multiple functions of one variable

say I have a function $$f(x, y) : bool$$ of two variables x and y - whose type can be anything - returning either true or false. I would like to create two functions of one variable each $g(x)$, ...
0
votes
1answer
74 views

BOOL algebra : simplifications

I have this expression : (A && B) || (A && C) || (B && C) I don't understand which steps I need to to to get this expression : (A && B) || (C && (A XOR B))
0
votes
1answer
156 views

Find a best 4-tuple which fulfils a variable boolean formula

I am looking for an algorithm... I have a kind of boolean formulae which contain $\wedge$, $\vee$, $+$ as arithmetic operator, relational operators ($<, >, \ldots)$, 4 integer constants $c_0, ...
0
votes
1answer
5k views

How to simplify in boolean algebra

I have some homework I can't seem to figure out. The assignment causing problems is devided into two parts; The first is to determine the inverse formula for a given formula (so the S = F'). The ...
1
vote
1answer
2k views

Parity Checking and truth tables

I have a question that I am very confused about. Parity Checking. Produce a truth table for a parity checking circuit that is based on $4$ input data bits, an input parity bit and a single ...
0
votes
2answers
216 views

Trouble with boolean algebra as used in logic

I'm having trouble knowing how to continue on with this problem, I don't know what to turn the equivalent sign into and I cant really continue with that side, can anyone help me out? Do I just say ...
2
votes
1answer
514 views

Determining the result of Boolean shape operations on closed Bézier shapes

Given two closed shapes made up of Bézier curves (and/or straight lines), I'm looking for an efficient way of calculating the resulting shape of the following Boolean operations: union difference ...
1
vote
2answers
184 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
271 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
96 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
123 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 ...
3
votes
2answers
2k 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
14k 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, ...
0
votes
2answers
69 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
202 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 ...
3
votes
2answers
1k 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 ...
1
vote
2answers
323 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
183 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
81 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 ...
3
votes
3answers
172 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
67 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
146 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: $$ ...
1
vote
2answers
397 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 ...
4
votes
1answer
223 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
75 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 ...
1
vote
1answer
1k 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 ...
2
votes
2answers
497 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
158 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
73 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: ...
3
votes
3answers
6k 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 ...
0
votes
3answers
376 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 ...
1
vote
0answers
198 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 reduced ...
0
votes
1answer
90 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
171 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 ...
8
votes
1answer
889 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
93 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
283 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
203 views

Boolean algebras without atoms

Why is the theory of Boolean algebras without atoms $\omega$-categoric?
11
votes
7answers
9k 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
271 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 ...
3
votes
3answers
962 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
1k 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
199 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
339 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
155 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 ...
1
vote
1answer
660 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')' = ( ...