# Tagged Questions

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

17 views

### strict partial orders that guarantee monotonic orientation functions

Given a strict partial ordered set $>$ over a set $V$. Consider its directed acyclic graph $G=(V,E)$ where $(v,u)\in E$ if $u> v$ and there is no $w$ s.t. $u> w$ and $w>v$ Consider the ...
33 views

### Complete atomic boolean subalgebras of power set boolean algebra

Let $I$ be a set and $P(I)$ its power set. I want to prove: Set $E(I)$ of all equivalence relations on set $I$ and set $A(I)$ of all complete atomic subalgebras (i.e. subalgebras that are atomic and ...
17 views

### How many minimized forms can a boolean expression have with 4 variables?

I have this theoretical question I can't get my head around. Assuming I have a function (any function) with 4 variables, and I draw a Karnaugh Map in order to extract the most simplified expression ...
27 views

### How to prove that $f(w,x,y,z)=∑(4,5,13)$ isn't universal?

I know that: $f_{min}=w'xy'+xy'z$. In order to show that operator isn't universal, you can show that there is no way to get $NOT$ by the operator. However, in this question there are four ...
53 views

### Basic prove that boolean function is self-dual

I'm tring to prove this function: $$f(x,y,z) = x'y'z'+x'yz+xyz'+xy'z$$ is self-dual, I've tried some basic manipulations like using double not on the function with de-morgan rules but got no ...
41 views

### Have I simplified this Min-term Correctly?

I have got two different solutions and I would like to know if they are correct, I would be very grateful if you could let me know if they are correct or what I can do to correct them. Solution 1 <...
25 views

### Boolean algebra how simplify products of sum Form

How Solve it to minimum number of literals i can't understand basic properties to simplify this expression $(A̅ +C)(A̅ +C̅ )(C+D)(B̅ +D)(A+B+C̅ D)(A+B̅ +C)$ explain me to understand concepts of ...
34 views

### How to convert $((x\land y)\lor(z\land u))\land((x\land\neg z)\lor (\neg y \lor u))\land((y\land z)\lor(x\land u))$ to the disjunctive normal form?

Is there a faster way than doing a gigantic truth table? I tried some transformation but didn't find a way to simplify the problem.
53 views

### What are universal abstract $\sigma$-algebras on $\sigma$-frames?

In this paper, the authors make the following definitions: An (abstract) $\sigma$-algebra is a boolean algebra with countable joins. A $\sigma$-frame is a bounded lattice with countable joins, where ...
44 views

### Finding solution to matrix equation over GF(2) with minimal true variables

I am looking for a general way to find a solution to a system of equations in GF(2) such that the solution has the least amount of true variables. After Gaussian elimination I get a matrix like such: ...
31 views

### Describe which partial orderings yield boolean algebras

I thougt about propositional logic and boolean algebras and how propositional logic is (at least from one point of view) not really about $\land,\lor,\neg,...$ but about boolean operators, i.e. n-ary ...
35 views

### Boolean Expression - ((a'.b)'+c')' + (a'+(b'.c)')'

I'm trying out one of the exercise, but not sure whether did I get the answer right, is the answer for the following output is 'C'? Kindly help to simplified it, as I'm not sure about it, still trying ...
26 views

### don't understand something in boolean algebra solution

I asked a question earlier and got the solution https://gyazo.com/372f0352b7d8aeb180586ac5218dd1bc I understand it all apart from this part AB(C⊕D)+D′(AB′+A′B) ...
49 views

### definition of projection operation for boolean functions

A boolean function $f$ over a set $A$ is a subset $X\subseteq A$ and $F$ is a set of boolean functions. I am trying to check whether $F$ is closed under projection. And I really do not know what ...
31 views

### Hochschild cohomology of a boolean ring

I can't find any papers studying the Hochschild cohomology ring $H^*(B,B)$, where $B$ is a boolean ring, so I was wondering if this is known.
31 views

### Which form of the function is simpler?

I'm simplifying function in Boolean algebra. Which form is simpler: $AB' + C'D + A'BC$ OR $DA' + C'D + AB'$ Second form has less letters but overlays itself at more spots. Which one is simpler?
30 views

### Finding the smallest decision tree of a Boolean function

From Computational Complexity: A Moden Approach, A decision tree is a model of computation used to study the number of bits of an input that need to be examined in order to compute some ...
36 views

### simplyfying boolean algebra

I need some help simplyfying a boolean algebra expression. (~abc*~d) + (a*~b*~c*~d) + (a*~bc~d) +(ab~cd) + (abc~d) I have managed to simplify to (~c*~D)(~a+~b)+(ab)(~c~d)+(a*~bc~d) but after this step ...
15 views

17 views

### group with infinity variables

Can a group contain infinity amount of same variables like $\{0,1,0,1,0,1,...\}$? I have been asked to prove or disprove that there is a group that contains infinity variables that follows the ...
19 views

### Simplify the boolean expression

Kindly help in Simplifying Y = BCD + BC'D. I have been trying to simplify the expression for sometime now, using the the 10 rules but cannot simplify fully.
20 views

### How to perform binary transformations?

One of the steps in Binary Index Tree algorithm is to find a node's parent which is done by un-setting the rightmost SET bit. For example: if a node has index 1010 than it's parent is 1000. To apply ...
19 views

### Simplify boolean algebra : (w'x+yz')((xz+w)(y+xz'))'

(w'x+yz')((xz+w)(y+xz'))' I gotten the answer w'xy'z+wyz' however the answer sheet was w'xz' +w'xy'z+w'yz' can anyone confirm?
26 views

### Proof writing involving Boolean algebra: AB' + AC + BC

How? AB' + AC + BC ≡ AB' + BC RS ≡ AB' + AC + BC ≡(AB' + A)(C + BC) ≡ AC Am I missing something? Thanks.
32 views

### Proof writing involving Boolean algebra: AB'+ AC + BC + D'C + DB'C'

Hello guys so I'm a bit skeptical about a problem: Given: AB'+ AC + BC + D'C + DB'C' how is the given equivalent to AB' + BC + D'C + DB'C'? If so what rule to simply from AB'+ AC + BC + D'C + DB'...
55 views

### Can't simplify this boolean expression

I'm trying to simplify this boolean expression: $$(AB)+(A'C)+(BC)$$ I'm told by every calculator online that this would be logically equivalent: $(AB)+(A'C)$ But so far, following the rules of ...
26 views

156 views

### Proof that {xor,not} is not functionally complete

I am trying to figure out the formal proof that set of {xor, not} is not a functional complete system. Firstly I tried to build it by structural induction and show that any formula created by using ...