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

1
vote
1answer
63 views

boolean algebra simplyfing

I need to solve these expressions with boolean algebra: $$Z = a'bc+ab'c+abc'+abc\mbox{ AND }Z = a'(b+db'c')+a'b'(d'c'+c)$$ Every advice is more then welcome. Thanks
0
votes
1answer
50 views

Can I factor out or statements on the other side of an equation in boolean?

I have this boolean equation: X'Y'+XY+X'Y=X'+Y I want to prove it. Now I was wondering if I can rearrange this equation, if I could, so I can factor out the ...
0
votes
1answer
44 views

Simplify a Boolean Expression

I have to simplify this w′x′y′z + wx'yz' + w'xyz' I keep getting different answers depending on whether I start on the left or the right of the expression Any advice or help would be appreciated. ...
1
vote
1answer
47 views

A problem with a boolean function.

This is one of my assignment problem and I almost finished others. This question confused me for quite a long time and now I get nothing about that. I did understand what is an increasing function ...
1
vote
1answer
538 views

Examples of boolean functions in conjunctive normal form

Give an $n$-variable Boolean function $f(x_1; x_2; \cdots ; x_n)$ in conjunctive normal form so that $f$ is $1$, respectively, (a) If at least one of the $n$ variables is $1$; (b) If at most one of ...
2
votes
1answer
31 views

Boolean matrices and Algebra

Let us consider, a set of binary rectangular matrices of finite dimensions, call the set as $T$. The cardinality of the set $T$ is $2^{mn}$ where each matrix are of order m cross n. Suppose $S$ is a ...
1
vote
1answer
679 views

convert circuit to nor only gates

for an assignment I need to convert a circuit to NOR gates only circuit. (A+B)C + D I know that morgan's theorem states: (a) (A+B)'=A'B' (b) (AB)'=A'+B' I've seen online how to convert some ...
0
votes
2answers
53 views

Boolean Logic - Why doesn't the Associativity Law work in this scenario?

By the associativity law, shouldn't the statement below be true? I understand that the truth tables are different but where exactly does the associativity law apply then if this is False? ...
1
vote
2answers
230 views

Boolean Simplification (ABCD)' + ((CD)'(B+D)'

I have to simplify (ABCD)' + ((CD)'(B+D)' function using boolean algebra. I simplified it using a truth table and got ...
0
votes
3answers
434 views

Using rules of inference (Leibniz) to prove theorems.

Leibniz: If $A \equiv B$ is a theorem, then so is $C[p:= A] \equiv C[p:= B]$. Note: p is "fresh" means p doesn't occur in $A, B, C$. I am trying to understand how to use Leibniz rule of inference for ...
1
vote
1answer
55 views

Boolean equation simplification

This is the problem: XY’ + XYZ + XY'Z= X + Y'Z And so far I have this, XY’ + XYZ + XY'Z= X + Y'Z X(Y’ + YZ + Y’Z) Factor out X X(Y’ + Z + Y’Z) De Morgan Any tips on how to proceed? I know ...
0
votes
1answer
34 views

need help simplifying boolean algebra exrpressions

Can someone walk me through simplifying the following expression? $$a\lnot b\lnot s + ab \lnot s + \lnot abs + abs$$ help and advice is appreciated!
0
votes
2answers
98 views

Quotient of boolean algebra by an ideal

The homomorphism theorem states that every boolean ideal $I$ of a boolean algebra $A$ is the kernel of a boolean isomorphism. I'm reading a paper where the author presents a short proof of this ...
0
votes
3answers
47 views

Simplify this Logic Function?

Have a Hardware Lab to do, and I need to reduce the following function before I actually hook it up to the Logic Trainer. (not ac) + (abc) + (a not c) Or: $\lnot (a \land c) \lor (a \land b ...
1
vote
1answer
267 views

Simplification of a Boolean Expression

I want to simplify this expression: ACD' + E(A+C)(A'+D') + A'C . The result must be a product of sums, where every sum should be consisted of just two variables. For example (A+B)(C+A)(Z+Y) ... ...
0
votes
2answers
53 views

simplify the boolean expression

I'm fairly new too boolean algebra. I've tried simplifying this equation but I'm not quite sure if I've done it correctly. Simplify to 1 literal, (X + Y + Y'Z)(Y + X)(Y + X') My attempt: ...
1
vote
2answers
250 views

Prove $(A \backslash B)'\backslash (B \backslash A) = B \backslash A$

Let $A$ and $B$ be subsets of some universal set. Prove that $(A \backslash B)'\backslash (B \backslash A) = B \backslash A$ Given: Definition 3.3.1 states that $A$ and $B$ are sets. The complement ...
-1
votes
4answers
541 views

Prove $A \subseteq B \cap C$ if and only if $A \subseteq B$ and $A \subseteq C$

Prove the following for any sets $A,B$ and $C$. This is actually two sets that I'm trying the prove. The title character restriction wouldn't allow me to post both at the same time. a. $A \subseteq ...
1
vote
2answers
2k views

Exercise regarding boolean algebra?

We need to simplify $AC+A'B'C$ $Y=A'B' +A'B C'+(A+C')'$ For (1) I wrote $C(A+A'B')$ but the result must be $AC+ B'C$. How do I get that to happen? I tried to simplify (2) using deMorgan but no ...
3
votes
1answer
74 views

On proving that $\mathcal{P}(\omega)/Finite$ is atomless

As I mentioned elsewhere, I'm working on Schimmerling's A Course on Set Theory. One of the nice features of the book (for me, anyway) is the addition of some interesting exercises on Boolean algebras. ...
0
votes
1answer
77 views

boolean algebra question here very short?

We have the Boolean expression Y=A'BC' + ABC'+A'BC Simplify it. Now, this is what I did Y=BC'(A'+A) +A'BC. Now using idempotence ...
2
votes
1answer
118 views

non-atomic complete Boolean lattice

Is there a Boolean complete lattice that is not atomic?
2
votes
2answers
644 views

Verify a Tautology without a truth table.

Verify that the following are tautologies. Do not make truth tables. a. $\lnot(\lnot) P \leftrightarrow P$ The first question is just a double negation law. So, if I have to take the left side and ...
0
votes
1answer
35 views

Strongly continuous measure [reduced]

Let us first give our definitions: the word CHARGE means finitely additive measure strongly continuous finitely additive measure is nonatomic, but not conversely. Here is the example: how ...
1
vote
1answer
391 views

Zhegalkin polynomial Boolean algebra

I have to find the Zhegalkin polynomial of $ (x\rightarrow y)\rightarrow z $. Please tell me if this is right: my polynomial is of this kind $ a_{0} + a_{1}x + a_{2}y + a_{3}z + a_{4}xy + a_{5}yz + ...
0
votes
1answer
36 views

Silly Question (monotonic) (updated)

suppose we have a measure $\mu$ on an algebra $B$, and $E,F\in B$ I know, if $E\subseteq F$, then $\mu(E)\leq\mu(F)$. Does the converse true, when $0<\mu(E)\leq\mu(F)$ ($\mu$ is nonatomic).
1
vote
3answers
78 views

Prove the following $f_{(A \cup B)}(x)=f_A(x)+f_B(x)-f_A(x)\cdot f_B(x)$

There is option to prove the following with truth table? $$f_{(A \cup B)}(x)=f_A(x)+f_B(x)-f_A(x)\cdot f_B(x)$$ I would like to get some hints how to do it in formal way(not truth table) thanks!
0
votes
1answer
42 views

Boolean Law that proves theorem

What Boolean Law proves the following theorem: (a && b) || (b && c) || (a && c) = (a || b) && (b || c) && (a || c) I made ...
1
vote
1answer
50 views

One implication (on Measure)

Please be noted that charges are finitely additive measures and measure are countably additive ones. Theorem 2.1. Let $\mu$ be a charge on a Boolean algebra $B$. Each of the following conditions ...
1
vote
2answers
4k views

Find DNF and CNF of an expression

I want to find the DNF and CNF of the following expression $$ x \oplus y \oplus z $$ I tried by using $$x \oplus y = (\neg x\wedge y) \vee (x\wedge \neg y)$$ but it got all messy. I also ...
1
vote
1answer
308 views

Logic boolean algebra problem

so I have to prove that these equations : are equivalent?
0
votes
1answer
57 views

Must complete atomless Boolean algebras of the same cardinality be isomorphic?

More generally: must complete Boolean algebras of the same cardinality and with the same cardinality of atoms be isomorphic?
2
votes
2answers
99 views

Boolean algebra simplification problem

I can't solve this equation: $$(xy + x'yz)(xz + x'y') = xyz$$ After applying distribution I got this: $$xyz + yz + x'z = xyz$$ I can't find the answer and have been thinking for hours now.
1
vote
1answer
65 views

Simplifying This Boolean Expression? (A Little Rusty)

I have the Boolean expression: F = A'B'C'D + A'BC'D' + ABC + AB'C'D' + ABCD'. Note that the ' indicates the negation of the variable by my convention. I am trying to show that F = BC + A'C' + B'D' is ...
5
votes
3answers
163 views

Can Boolean ring without unit be embedded into a boolean ring?

While going through a book (Lectures on Boolean algebra, Halmos) I got struck at the following question : Prove that every Boolean ring without a unit can be embedded in a Boolean ring with a unit. ...
0
votes
3answers
56 views

Boolean Algebra simplification, just cant get it

I have this question that I need some help with, I just can't get to grips with simplifying. I'm looking at the rules and such but I just can't see where to apply them. Can someone show me the ...
1
vote
0answers
115 views

Expansion of subsets of a hamming ball in hypercube

Consider a hypercube graph $G_n = (V,E)$ in n dimensions. Let $H_{1/2} \subset V$ be the set which represents the hamming ball of radius $n/2$. That is for every $v \in H_{1/2}$ the hamming weight of ...
2
votes
2answers
107 views

How to simplify $A(\overline BC+B)$

How do I go from $A(\overline BC+B)$ to $A(B+C)$? What definition should I use to get the final answer? Would like an explanation and proof so I can learn rather than just memorise.
0
votes
2answers
100 views

Solution to ax+b=c in a Boolean algebra

I have a question. In another forum, a user asked if there is a solution to ax+b=c in a Boolean algebra, where "ax+b=c" is "$(A \wedge X) \vee B = C$". The idea is that, in a Boolean ring, this ...
-1
votes
1answer
25 views

is this boolean algebra transformation correct

I have the following expression: (A=1 or A=2) or (B=1 or B=2) and try to transfer it to: (A=1 or A=2 or B=1 or B=2) Are these two expressions equal?
1
vote
1answer
55 views

How can this boolean algebra equation be solved?

(7EFEFEFF + A) ^ (A ^ FFFFFFFF) = 81010100 How can it be solved for the value A? where '+' means plus '^' is bitwise XOR EDIT: Forgot to mention. A is a ...
3
votes
1answer
243 views

Solving special boolean equation set

I have boolean equation sets that look like this (where ^ means xor): eq 1: x1^x3^x5^x6^x9^x10^x11^x13^x17^x18 = 0 eq 2: 1^x1^x3^x10^x12^x17 = 0 eq 3: 1^x2^x3^x5^x8^x10^x14^x16 = 0 ...
1
vote
0answers
38 views

“Optimal Disjoint Decomposition” of a Boolean Lattice Subset?

I am looking for the name (and, possibly, an efficient solution) of the following problem: Given a Boolean lattice $(L, \sqcap, \sqcup)$ with least element $0$, and a finite subset $X \subseteq L$, ...
0
votes
1answer
91 views

2-Colorable & Decision Problem

Consider the following decision problem. Given $m$ subsets $A_{1}, \dots , A_{m} \subset \{1 , \dots , n \}$. Does there exist a subset $S \subset \{ 1, \dots ,n \}$ such that the cardinality of the ...
0
votes
1answer
66 views

Atomic Boolean Algebras that are not canonical

I define a Boolean Algebra B to be canonical iff it is isomorphic to the powerset of some set S. (under union, intersection, and complement, of course). Any Boolean Algebra that is both atomic and ...
1
vote
1answer
220 views

3-Colorability Graph Questions

I know that a boolean formula for 3-colorability is : $ \wedge_{i \in Vertices}(\bar{b_{i,1}} \vee \bar{b_{i,2}}) \wedge_{\left(i < j \right)\in Edges} ((b_{i,1} \bigoplus b_{j,1}) \vee (b_{i,2} ...
3
votes
2answers
130 views

Example of a function between boolean lattices that preserves $(\top,\bot,\wedge,\vee)$ but not complements.

Its easy to find boolean lattices $A$ and $B$ together with a function $f : A \rightarrow B$ such that $f$ preserves both top and bottom elements, as well as binary meets, but not complements. ...
0
votes
4answers
95 views

Simplifying this boolean function

How can I completely simplify this equation using algebraic simplification rules? $$x'y'z + x'yz + xyz$$
0
votes
1answer
5k views

Simplify Boolean Product of Sums Function

I've got a product of sums expression: F=(A'+B+C')&(A+D')(C+D') I need to show it as a sum of products and then simplify it. Right now I got: F=(A'&D')+(A&B&C)+(B&D')+(C&D') ...
0
votes
1answer
48 views

Boolean function on $\{0,1\}^n$ comprising just binary AND and OR gates

Let $f:\{0,1\}^n\to\{0,1\}$ be a boolean function computed by logical circuit comprising just binary AND and binary OR gates (assume that the circuit doesn't have any feedback). Let ...