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
2answers
87 views

Why is $a \implies b$ is true when $a$ is false [duplicate]

I understand that: $True \implies True$, is true. $True \implies False$, is False. But why is it that $False \implies True$, is True. and $False \implies False$, is True. If $a$ is false I ...
3
votes
2answers
118 views

Intuition for orthogonality in $\{0, 1\}^n$

In the beginning of [Kanerva 1988] a boolean algebra over $$ \{0, 1\}^n $$ with bitwise OR and AND is introduced. Example for bitwise OR: $$101 + 001 = 101$$ Example for bitwise AND: $$101 * 001 = ...
0
votes
1answer
31 views

Adjust the result of a boolean expression

I need to solve this in boolean algebra: $$B(A+(B'+ A)')$$ Here is my attempt: $$B(A+(B'+ A)')=B(A+(BA'))=B((AA')+(AB))=B(0+AB)=B(AB),$$ and the result should be just $B$. Should I just decide ...
2
votes
0answers
21 views

Expressing associativity as a Boolean SAT problem

Suppose we have a binary operation $B: S \times S \to S$ on a finite set $S$. We can encode $B$ as an array of $|S|^3$ Boolean values by setting $$ B_{ijk} \equiv \text{True} \quad \text{ iff } \quad ...
0
votes
0answers
35 views

Separation in Boolean algebras

I am looking for a separation-like result for Boolean algebras which is intuitively clear to me. Suppose that $B$ is a Boolean algebra whose set of positive elements $B^+$ does not have countable ...
0
votes
1answer
23 views

Number of self dual functions and number of inputs for which self dual function is 1

I came across this slides which states following two theorems: Theorem There are $2^{2^{n-1}}$ different self-dual functions of $n$ variables. Theorem Let $f$ be a self-dual function of $n$ ...
0
votes
1answer
29 views

PIT implies: In a boolean lattice, every filter can be enlarged to a maximal one

I am working through this proof of Herrlich's Axiom of Choice: $(1)\Rightarrow(2)$: How do you define the quotient lattice $B$ modulo a Filter? And why is the preimage of the maximal filter ...
0
votes
0answers
22 views

Finding the principal disjunctive normal form (PDNF) of a Boolean expression

Find the principal disjunctive normal form (PDNF) of a Boolean expression $$((p\wedge q) \rightarrow r)\vee((p\wedge q)\rightarrow \neg r).$$ I tried by expanding it but I am stuck with the ...
1
vote
1answer
32 views

Boolean Algebra Product of Sums

I have a question to solve the following expression and get it in terms of product of sums (AB' + A'B)C And I tried taking the compliment of this ...
0
votes
1answer
25 views

Design a circuit for a light fixture

Design a circuit for a light fixture controlled by four switches, where flipping one of the switches turns the light on when it is off and turns it off when it is on and please explain your answer
1
vote
2answers
40 views

Basic boolean prove

I need to prove that given $$ f_1 = c + a'd' + bd' \quad\text{and}\quad f_2 = a'b'd' + a'bd' + ab'c + abd' $$ that $f_1 = f_2$. How do I manipulate $f_2$ to be exactly like $f_1$? I have tried a lot ...
-2
votes
1answer
63 views

How can i simplyfy this boolean equation?

Please help me simplify this formula by using boolean algebra rules: $F= x_1'x_2'x_3'x_4'+x_1'x_2'x_3x_4+x_1'x_2x_3'x_4'+x_1'x_2x_3x_4'+x_1x_2'x_3x_4.$ I know that the answer should be: ...
1
vote
1answer
59 views

Questions about Boolean logic

Is there a systematic way to show that a set of Boolean operators is complete? Or is it more of an art than a science? Similarly, is there a systematic way to convert any Boolean expression in terms ...
1
vote
1answer
78 views

How to solve for a variable in xor equation?

I am very new to algebra with bitwise operators. If i have 5x ^ 7x ^ 9x = 22 is it possible for me to solve for x (if so how is it done)? Do normal algebra techniques hold (factoring out x etc.?) I ...
4
votes
1answer
36 views

How do I derive logical statements simply?

For example if I want to show the equation for $x \rightarrow y$, using truth tables it is the same as: $$(\neg x \wedge \neg y) \lor (\neg x \wedge y) \lor (x \wedge y)$$ Is there a methodical way ...
0
votes
1answer
26 views

how to draw a truth table for following logical expression?

It's a question in my assignment, which I don't really understand it. However, there is an example here. e.g. A computer uses the following logical expression to control a finger print scanner. ...
2
votes
1answer
52 views

A generalized Boolean algebra gives rise to an implication algebra

A generalized Boolean algebra $G$ is relatively complemented distributive lattice with largest element 1. That is, an element $a\in G$ has a complement in any interval $[x\,,\,1]$ that contains ...
0
votes
0answers
15 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
28 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
15 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
25 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
37 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
25 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
23 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
47 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
35 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
25 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
37 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
17 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
34 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
12 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}$ = ...
0
votes
0answers
16 views

How would I simplify CW= ABAR.B.CBAR.DBAR and what steps should i take to get there?

I have the minterm CW = ABAR.B.CBAR.DBAR and have been asked to simplify using Boolean algebra it as far as I can. Any help?
0
votes
2answers
18 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 it's basics. The possible answers are: $x'y+y'z'$ $xy+z'$ $x'y'+z'$ $x'y+z'$ ...
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
12 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
14 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
17 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
24 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
26 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 + ...
1
vote
4answers
41 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
23 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
20 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
39 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
34 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
29 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.