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

0
votes
0answers
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 ...
3
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
0
votes
3answers
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 ...
0
votes
1answer
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 <...
0
votes
1answer
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 ...
1
vote
2answers
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.
3
votes
0answers
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 ...
1
vote
0answers
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: ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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) ...
0
votes
1answer
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 ...
1
vote
0answers
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.
0
votes
1answer
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?
0
votes
0answers
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 ...
-1
votes
1answer
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 ...
0
votes
0answers
15 views

Understanding the intuition behind Boolean Difference

Consider the boolean function below $F = a + b.c$ Evaluating function $F$ at $a = 0$ and $a = 1$ $F_{a=0} = b.c$ $F_{a=1} = 1$ $\frac{dF}{da} = F_{a=0} \oplus F_{a=1}$ = $\bar ...
1
vote
2answers
34 views

Minimizing basic boolean function

$==============================$ Given the function $f(x,y,z) = y'z'+x'y+x'yz+xyz'$ (where ' means the NOT operator), I need to transfer this function to its basics. The possible answers are: $x'y+y'...
0
votes
0answers
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 ...
0
votes
1answer
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.
1
vote
0answers
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 ...
0
votes
1answer
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?
1
vote
1answer
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.
0
votes
1answer
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'...
1
vote
4answers
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 ...
0
votes
1answer
26 views

Use Boolean algebra properties to prove the given equality.

Use Boolean algebra properties to prove the given equality.. How do I do this? $\bar{x}yz + \bar{y} + \bar{z} = \bar{x} + \bar{y} + \bar{z}$ I know $x + \bar{x}y = x + y$ I also know: $\bar{x}yz +...
2
votes
1answer
22 views

Equivalent definitions of Boolean Algebras

Assume that my definition of a Boolean algebras is the following one: I have a set $B$ with two binary operations $\vee$ and $\wedge$ which both satisfy the commutative, associative and distributive ...
1
vote
2answers
57 views

How to prove D70 = {1, 2, 5, 7, 10, 14, 35, 70} is a Boolean algebra

Prove that the set $D_{70}$ = {1, 2, 5, 7, 10, 14, 35, 70} of positive factors is a Boolean algebra under the operation (+), (.), (') defined by $$x + y = lcm(x, y)$$ $$x . y = gcd(x, y)$$ $$x' = \...
1
vote
2answers
36 views

Boolean SOP Expression Simplification: $F(a,b,c,d) = (a+d)(a'b+c'd)(ac+bd)'$

my answer that I have gotten is $b'c'd + a' b d'$ however, the answer given to me was b'c'd can someone tell me whether I am correct
1
vote
1answer
31 views

Simplify 4-term Boolean Algebra expression

How do I get from this: $F = AB' + AC' + AD + C'D'$ to this: $F = AB' + AD + C'D'$ Not sure how the $AC'$ disappeared.
0
votes
1answer
86 views

Simplify boolean expression $AB + A\bar B+ ABC $

Simplify $AB + A\bar B+ ABC $ I've been trying to simplify for a good while now. I'm using only the 10 rules but cannot find a way to simplify fully.
1
vote
1answer
42 views

How to Solve this Boolean Equations?

I have a Boolean Equations, described as below, $$\neg \mathbf{x} = \mathbf{M}\cdot \neg(\mathbf{M} \cdot \mathbf{x})$$ in which $\mathbf{M}$ is an $n\times n$ Boolean matrix, and $\mathbf{x}$ is an $...
1
vote
2answers
37 views

Tensor product of boolean rings

Is there an example of a Boolean ring $B$ such that the $B$-bimodule map $\mu:B\otimes_\mathbb{Z}B\rightarrow B,$ defined by $\mu(x\otimes y)=xy$, does not split? (To split means that there is a $B$-...
0
votes
1answer
38 views

Simplifying $ (A + B)' \cdot (C + D + F)' + (A + B)$

Firstly, please forgive me for my lack of experience in boolean algebra - I have not touched it in years. Also, as this is a coursework assignment I am only hoping for a little nudge in a right ...
1
vote
1answer
74 views

How to read Hasse diagrams and how they can describe a Boolean Algebra?

Consider a Hasse Diagram for a Boolean Algebra of Order 3 Just by using the diagram and defined Boolean Algebra System as : $\langle B, \vee ,\ \cdot \ , \bar{\ \ } \ ,0, 1 \rangle$ and for any 3 ...
4
votes
2answers
125 views

Power set representation of a boolean ring/algebra

Let $R$ be a finite boolean ring. It's known that there's a boolean algebra/ring isomorphism $R\cong \mathcal P(\mathsf{Bool}(R,\mathbb Z_2))$. I'm trying to get a feel for this. The subsets of $\...
0
votes
2answers
38 views

Simplifying boolean algebra expression that contains XOR

How can i simplify followed boolean algebra expression; Normally i express as simplify without XOR also this expresion contains both XOR and multiple variables. (((A + B)' * C') ⊕ ((A' + B') * C')' ) ...
1
vote
2answers
56 views

prove $(p → r) ∨ ( q → r)$ logically equivalent to the statement $(p∧q) → r$

I came across this problem, it asks to use logical equivalences (see image), show that $(p → r) ∨ (q → r)$ logically equivalent to the statement $(p ∧ q) → r$ (aka definition of biconditional) After ...
0
votes
0answers
20 views

Why aren't these two expressions equivalent by use of DeMorgan's Laws?

This has thoroughly confused me. According to DeMorgan, the following expressions are equivalent. $$ '(A*B) = 'A +'B $$ However, I have come across the following expression: $$ '('A+B*C) $$ By using ...
0
votes
0answers
70 views

How to Solve Boolean Matrix System?

I have a Boolean Matrix System (BMS) as described below $$Ax=c$$ where $A$ is a $n\times n$ Boolean matrix (i.e., all entries are either 0 or 1), $c$ and $x$ are two $n$-dimensional Boolean column ...
3
votes
2answers
39 views

Functional separation of regular open sets of a topological space

Let $\langle X,\mathscr{O}\rangle$ be a topological space. We say that disjoint $A,B\in 2^X$ are functionally separated iff there exists a continuous function $f\colon X\to [0,1]$ such that: if $x\...
1
vote
1answer
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 ...
0
votes
1answer
147 views

How to create an AND , OR , XOR and NOT gates with a fredkin gate?

Ok so I am studying for an exam which is about logic gates and circuits , etc .The problem I have is with these two questions that are in the picture , it says build an AND , OR and NOT gate using ...
0
votes
2answers
51 views

How to test CNF for satisfiability?

If we have a conjunctive linked expression where only the following clauses are allowed: $A_i, \quad \neg A_i, \quad A_i \vee \neg A_j, \quad \neg A_i \vee A_j$ Example: $A_1 \wedge (A_2 \vee \neg ...
0
votes
0answers
21 views

Number of possible unate functions possible

An unate function f is one which is constant or can be represented by an SOP using either complemented or uncomplemented literals for each variable. My question is : How many such unate functions in ...
0
votes
2answers
59 views

lambda calculus, definition of true and false

Are the following lambda-calculus definitions axiomatic? true: $\lambda xy.x$ false: $\lambda xy.y$ Is the definition truly arbitrary? In my impression, it looks like we could just swap the ...
0
votes
1answer
44 views

Correspondence between ideals and congruences of Boolean algebras

I'm trying to prove that $con(B) \simeq I(B)$ where $B$ is a Boolean algebra and $con(B)$ is the lattice of congruences on $B$ and $I(B)$ is the lattice of ideals on $B$ I found a map s.t. for a ...
0
votes
1answer
27 views

Express logic and with +,-,*

How can a logic and be expressed using only the arithmetic operators $+,-,*$ on $\{0,1\}$, taking $1 = $ True? To be precise: What function that uses only $+,-,*$ is $1$ when both arguments are $1$ ...