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

3
votes
3answers
276 views

The completion of a Boolean algebra is unique up to isomorphism

Jech defines a completion of a Boolean algebra $B$ to be a complete Boolean algebra $C$ such that $B$ is a dense subalgebra of $C$. I am trying to prove that given two completions $C$ and $D$ of $B$, ...
1
vote
1answer
263 views

Simplifying a boolean expression

Can someone help me simplify this boolean expression? $$(a+b+c+d)(a'+b'+c'+d')$$ so if I use the distributive property, I'll get: ...
4
votes
1answer
192 views

Question about Boolean algebra and ultrafilters

In the following $B$ denotes a Boolean algebra and $\bar{x}$ is the complement of $x$. In my notes there is the following theorem: If $U \subset B$ is an ultrafilter on $B$ then for every $x \in B$ ...
0
votes
2answers
190 views

Can Boolean function's value be computed by using a rewrite system?

Suppose there is a function in e.g. CNF form. For example: $$ (A \vee B) \wedge (\neg B \vee C \vee \neg D) \wedge (D \vee \neg E) $$ For given A,B,C,D,E values it is possible to compute the value ...
1
vote
2answers
48 views

In a Boolean algebra B and $Y\subseteq B$, $p$ is an upper bound for $Y$ but not the supremum. Is $q<p$ for some other upper bound $q$?

I don't think that this is the case. I am reading over one of my professor's proof, and he seems to use this fact. Here is the proof: Let $B$ be a Boolean algebra, and suppose that $X$ is a dense ...
1
vote
1answer
421 views

Expanding this boolean expression

Can this Boolean expression: $$A*\overline{A*B}$$ be expanded to give: $$A*\overline{A} * A*\overline{B}$$ Although that appears to reduce to zero? I know $A(\overline{A+B})$ can be expanded to ...
0
votes
3answers
4k views

De Morgan's Theorems

Could someone give me an algebraical demonstration of the De Morgan's Theorems? I already know the graphic demonstration with the truth table, but I need to understand the algebraical way. EDIT I ...
0
votes
1answer
366 views

Simplify boolean expression

$(xy’+z)’\cdot((xz)’+y')$ $$\begin{align*} (xy’+z)’\cdot ((xz)’+y’) &=(x'+yz’)\cdot (x’+z’+y’)\\ &=x’x’ + x’z’ + x’y’ + yz’x’ + yz’z’ + yz’y’\\ &=x’ + x’z’ + x’y’ + yz’x’ + ...
0
votes
2answers
1k views

What do these terms mean: commutative, associative, distributive

I am reading a book, and I am trying to understand what the writer really mean by the following terms. I would like to understand what these words mean in relation to the examples. In regular ...
5
votes
1answer
412 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
116 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
149 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
88 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
72 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
153 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
4k 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
1k 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
204 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
437 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
3answers
178 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
263 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
90 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
118 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
1k 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
12k 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
68 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
845 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
319 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
176 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
79 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
159 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
138 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
346 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
199 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
824 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
443 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
144 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 ...
1
vote
0answers
119 views

boolean algebra how can i prove a theorem

In a set of lattice in boolean algebra how can i prove this: $$x \cdot (y+z) \ge (x\cdot y) +(x\cdot z)$$
0
votes
1answer
70 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: ...
2
votes
3answers
5k 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
286 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
179 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
84 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
157 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
771 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
90 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 ...