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
1answer
11 views

Boolean Algebra simplifcation

I have an expression I need to simplify for a class assignment, yet I simply can not figure out how to apply the rules in this case. Can someone put me on the right direction? w’x’y’z + w’xy’z + wxy’...
0
votes
0answers
16 views

Fourier Analysis for Derandomization of Functions

I was wondering if there was an extension to Fourier Analysis on Boolean Functions. Specifically, it's well known that for any boolean function $$f: \{-1,1\}^{n} \rightarrow [-1,1] $$ we can decompose ...
1
vote
0answers
14 views

Help with Boolean algebra

Consider a system with $n$ units where each unit is either working or failing. $x_j=1$ represents the condition that $j$-th unit is working. Suppose each unit is working with independent probability $...
0
votes
0answers
15 views

Clarity on Boolean Algebra and Rings

I'm trying to wrap my head around Abstract Algebra, Boolean rings, and it's a little difficult. So I understand the ring (I believe it's a ring) <ℤ ,x, +, -, 0, 1 > is normal integer arithmetic ...
1
vote
1answer
38 views

Prove universal gate math

I tried to deal with this question: $$F(a,b,c,d) = (a'+b'+c')\oplus bcd$$ While I asked to prove that F with the constant '$0$' is universal gate. I know that to prove that some function is ...
1
vote
1answer
21 views

How can I find a DNF and Minimal Form for this boolean expression?

$Q(x,y,z)=(y′\vee z′ \vee 0\vee x′)\wedge1\wedge(z\vee x′\vee 0\vee y\vee z)′\wedge(z′\vee x\vee y\vee z′)$ I'm not supposed to use tables but only proprieties like De Morgan ecc. EDIT: So I ...
1
vote
3answers
66 views

How to simplify using algebra laws

Simplify the following by using algebra laws. (i) X’.Y’ + X.Y.Z. + X’.Y + X.Y My attempt: X’.Y’ + Y(X.Y.Z + X'Y + X.Y) X’.Y’ + (X.Z + X' + X) X’(X’.Y’ + X') + X.Z + X Y’ + X' + X.Z + X Y’ + X' +...
0
votes
1answer
13 views

How can I show a set B with 8 elements and two operations (huntington axioms)

How can I show a set B with 8 elements and two operations, such that the axioms of huntington for boolean algebra holds? I found it with set of 2 elemtnts. but can't understand how to start with 8 ...
-2
votes
1answer
34 views

De Morgan's Law Operation order

I have the following boolean logic: $$ \overline {\overline {\overline {B+C+D} + \overline {DA}} + \overline {\overline {\overline {A+E} + \overline { B}} + \overline {E}}} $$ I am trying to simplify ...
-1
votes
1answer
31 views

XOR equation with multiplication arrangment

How can I move all the X to one side so the equation will become x=y XOR <somthing>... $$\begin{align} &2x \oplus y = x \end{align}$$ ...
2
votes
1answer
39 views

Simplify semi-boolean expression

I'm trying to simplify the following expression: (A == B) OR ( (A > B) AND (A < C) ) Given that B <= C, this is my ...
0
votes
1answer
38 views

Naive question about 3 sets intersection point

I have three intersecting in at least one point sets $A$, $B$, $C$ with arbitary finite countable cardinality. The known facts are: $$ |A|, |B|, |C| $$ $$ |A \cap B| $$ $$ |B \cap C| $$ $$ |C \cap A|...
1
vote
1answer
44 views

On boolean algebras as rings, modules and/or R-algebras

After trying to make sense of first order logic from an algebraic point of view I started to read about boolean algebras (similar to the explanations given here: wikipedia on boolean algebras. I also ...
0
votes
0answers
26 views

Partition of complete boolean algebra induces partition on elements

Given a complete boolean algebra B, and two partitions W and T of B, why is it true that W induces a partition on every element of T? (And is this true more generally - does W induce a partition on ...
3
votes
5answers
147 views

$f(x) = 0$ when $x$ is $0$, and $1$ otherwise

I've been trying to create a function that will return $0$ when $x$ is $0$, and for any other $x$ value it should return $1$. I've searched for a pre-existing function online too and wasn't able to ...
2
votes
1answer
47 views

Is there a way to reduce a set of linear inequalities representing a set of vectors in $\{0,1\}^n$?

Given a fixed number $r$, such that a vector $v_i \in \{1,0\}^n$ has exactly $r$ ones and $n-r$ zeroes, and a number of inequalities, (say $I$ is this set of inequalities) representing a set $J$ of ...
0
votes
1answer
39 views

Why is Boolean a lattice?

I've had minimal exposure to lattice theory but I must answer this question due to a project I'm working in. If anyone could answer this question in the simplest explanation possible with examples ...
0
votes
0answers
27 views

Complexity of some contact circuit

How to prove that for every boolean function $f$ of $n$ variables there exists a (1, 2)-contact circuit $\Sigma_f$ (i.e. with one input and two outputs), implementing boolean function system $(f, \...
1
vote
1answer
16 views

Stuck on boolean algebra problem

Could someone please explain me why $x.y+x.z+y'.z$ Is equal to $x.y+y'.z$? I just can't simplificate it..
1
vote
1answer
35 views

Prove that $\lambda(f) = o(2^n)$ for almost all boolean functions

How to prove that $\lambda(f) = o(2^n)$ for almost all boolean functions $f$ of $n$ variables? Here $\lambda(f)$ denotes minimal length (i.e. count of terms) of all possible disjunctive normal forms (...
1
vote
0answers
24 views

Lower bound of DNF terms count for some symmetric boolean function

Consider boolean function $s_n^{[r,\,n - r]}\colon \{0,1\}^n\rightarrow\{0,1\}$ defined as follows: $$ s_n^{[r,\,n - r]}(x_1, ..., x_n) = 1 \iff |\{x_i: x_i = 1\}| \in [r,\,n - r] $$ (in other words,...
0
votes
1answer
17 views

Monomorphism between finite Boolean algebras

Let $A$ be a finite Boolean algebra. If I define a monomorphism (i.e. an injective homomorphism) from $A$ to another finite Boolean algebra $B$ of the same similarity type. Is this monomorphism an ...
1
vote
0answers
24 views

Isolate $A$ from $A\oplus(129^3A)$

I've been working through the following problem and I'm really stuck Starting with the following three equations: $$ a= (129A \oplus C)\mod 256 \\ b= (129B \oplus A) \mod 256\\ c= (129C \oplus B) \...
0
votes
2answers
32 views

Stuck in Boolean Algebra equation

I have this equation in Boolean Algebra: $x*y*z+x'*y*z+x*y'*z+x*y*z' = y*z+x*z+x*y$ I got this: $= yz(x+x')+xy'z+xyz'$ $= yz+xy'z+xyz'$ And from here I tried multiple things but it goes wrong ...
1
vote
2answers
35 views

Having trouble with simplifying in Boolean algebra

I want to solve this problem: $$(x . y . z + x . y + x)$$ Which turns into this when you group $x$ $$x . ( yz + y + 1 ) $$ What I don't understand is why is there a "1" at the end? ...
-1
votes
1answer
41 views

Using the laws of logic (algebraic version) to show the following equivalences [closed]

I have some questions about algebra and discrete, with using law of logic. I am not sure how to prove the equivalences. Can someone please show me how this works and show the equivalence using the ...
2
votes
1answer
52 views

How can I prove that $(a + b )\oplus(a + c)$ is not possible to simplify. Or is it?

I was trying to simplify the following expression $(a + b )\oplus(a + c)$, where $+$ is just a simple addition of two numbers and $\oplus$ is a binary xor operation. By simplifying I mean exanding or ...
2
votes
2answers
27 views

Logic Puzzle (Valid and Invalid Arguments)

I have been given a logic puzzle and I am having a tough time figuring out how to set it up and solve. Here is the puzzle: a) The Statement "If Dr. Jones did not commit the murder then neither Ms. ...
2
votes
3answers
72 views

Logical limitations of Proofs by Contradiction

In general proofs by contradiction go as follows: Given an arbitrary hypothesis, $\ p \implies q$, we assume $\left(p\implies q\right) = T$, and then we show that by assuming the hypothesis to be ...
4
votes
2answers
141 views

How to deal with an 8 variable Karnaugh map

I'm reaching back into my high school days trying to remember one of the rules about Karnaugh Maps. I have an 8 variable input, and I remember that I should try and make the selections a big as ...
0
votes
1answer
44 views

Is there a blackboard bold letter for the set of Boolean numbers? [duplicate]

Is there a symbol (e.g. $\mathbb{B}$) for the special set of Boolean numbers or values; ${0,1}$ or ${True,False}$?
0
votes
1answer
43 views

Galois field of order 2 constituting a Boolean algebra

We know that the the set $\{0,1\}$ constitutes a Boolean Algebra over the usual $OR$ and $AND$ operations. However, because of the lack of an additive inverse for $1$ this does not produce a Galois ...
1
vote
1answer
35 views

A proof of maximality of an antichain in a complete Boolean algebra

Suppose $(\mathbf{B},\leqslant)$ is a complete Boolean algebra and let $|\mathbf{B}|=|\gamma|$. Let $C=\langle c_\alpha\mid \alpha<\gamma\rangle$ be a maximal descending chain without a lower bound:...
0
votes
1answer
19 views

Boolean Expression Simplifying explanation

Currently have worked xz' + x'y + (yz)' Down to z' + x'y + y' Is this its simplest form? METHOD: xz' + x'y + (yz)' -> De-Morgan on (yz)' xz' + x'y + y' + z' -> Commutative xz' + z' + x'y + y' -> ...
3
votes
0answers
27 views

Do DeMorgan's laws hold for pseudo-complement in Bi-Heyting Algebra?

A textbook says in Heyting Algebra, The pseudo-complement of an element $a$ is denoted as $a^{\ast}$. One of the DeMorgan's law $\left(\vee a_{i}\right)^{\ast}=\wedge a_{i}^{\ast}$ holds ...
1
vote
2answers
34 views

boolean algebra reduction question

hi im having a lot of trouble proving this boolean expression. Im getting many differing answers so I assume I must be going about it in the wrong way. To explain, I'm trying to negate the whole LHS ...
17
votes
2answers
2k views

Why are Boolean Algebras called “Algebras”?

Boolean algebras aren't algebras (to the best of my understanding). So why are they called algebras? Wouldn't it make more sense to call them a "Boolean system" or a "Boology" or something else like ...
1
vote
0answers
19 views

General rules for transforming boolean equations?

Are there general or restricted rules for transforming between equivalent boolean equations? A concrete problem that I have is given the following equation: ...
-1
votes
1answer
31 views

Help with Simplifying boolean algebra, not sure if i have done it correctly.

I have no idea how to do boolean algebra, First question is x'y + x(x + y') I need to first draw a circuit diagram(logic gate) and then simplify it and draw a simplified logic gate. As of now I ...
0
votes
0answers
8 views

Correct definition of the co-occurrence graph of a pseudo-Boolean function

In section 4.6 of Pseudo-Boolean Optimization, Boros and Hammer have defined the co-occurrence graph of a pseudo-Boolean function as follows. If a pseudo-Boolean function $f : \mathbb{B}^n \mapsto ...
0
votes
1answer
23 views

Is a boolean algebra closed under countable disjunction/conjunction?

I'm just curious if the properties in a sigma algebra is also satisfied in a boolean algebra. In a boolean algebra, the two operators are closed under finite operations, but can we say they are closed ...
0
votes
1answer
32 views

Comparing entropies $H((f(X,Y), g(X,Y)))$ and $H ((f(X,Y),g(X,Z)))$

Let X,Y,Z be three independent uniform distributions on $\{0,1\}^n$; $f, g:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}$ be two boolean functions. Is it true that $$H((f(X,Y), g(X,Y)))\leq H ((f(X,Y),...
1
vote
1answer
38 views

how to construct a boolean algebra out of a set of well formed formulas?

Given a set of well formed formulas of a first order language (with equality, constants, variables, non-logical symbols, etc), is it possible to use it as some kind of base to construct a (possible ...
1
vote
1answer
45 views

What is the name of a “basis” in Boolean algebras

So, a basis in linear algebra is the smallest set which generates a particular vector space. (More formally, a subset of the vector space which is linearly independent and spans the vector space) Is ...
0
votes
1answer
25 views

What is wrong with my Boolean expression?

I've got the following expression: A*!B*(!B*C+!C*A*(D+B*!A+D*A*B+C*!D)) After translating it to Wolfram's understandable language I got this: ...
2
votes
0answers
28 views

Is every quotient algebra of a Boolean algebra isomorphic to a subalgebra?

Is every (non-trivial) quotient of a Boolean algebra isomorphic to a subalgebra of that Boolean algebra? And conversely is every subalgebra isomorphic to a quotient algebra?
0
votes
1answer
30 views

What is this product called?

Let $X$ be a finite set and let $2^X$ be its power set. Let $Z$ be some ring (e.g. the complex numbers; it doesn't matter). Suppose $f:2^X\to Z$ and $g:2^X\to Z$ are two functions from $2^X$ to $Z$. ...
1
vote
1answer
132 views

Can $P(\omega)$ be superatomic?

A Boolean algebra is superatomic if its every subalgebra has an atom. I'm trying to determine whether $P(\omega)$, i.e. the power set algebra of the set of all natural numbers (finite ordinals) $\...
0
votes
1answer
17 views

Confirmation of an answer of a question on Boolean Algebra

Here are the solution I have worked out. Is it correct? Given $C + BC'$: $C + B' + C'$ $C + (B'+C')'$ $C + B + C$ $C (C + B + C)$. Is the answer (2)?
0
votes
0answers
21 views

How to find standard product of sums?

I have came across an exercise in book to find the standard product of sums with the following function: F(A,B,C,D,E,F) = (A + BC'+ CD) (B' + EF) Here's my approach to solve it: Step 1: [ (A + B) (...