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

2
votes
1answer
93 views

the quotient boolean algebra of $P(\kappa)$ over the nonstationary ideal

Let $\kappa$ be a regular cardinal. Then the quotient boolean algebra over the nonstationary ideal, $P(\kappa)/I_{NS}$ is $\kappa^+$-complete. Specifically, any $S \subseteq P(\kappa)/I_{NS}$ of ...
0
votes
1answer
151 views

Two question on ternary Cantor set & Jordan content

Is it true that all subsets of the Cantor set have Jordan content zero? What is the definition of countably generated Boolean algebra? Does the Boolean algebra of subsets $[0,1]$ which ...
2
votes
2answers
59 views

Boolean simplification expression

In words my problem is NOT(p AND q) AND (NOT p OR q) AND (p OR p). I have rewritten it in symbols ¬(p ∧ q) ∧ (¬p ∨ q) ∧ (p ∨ p) I got this far: (¬p ∨ ¬q) ∧(¬p ∨ q) ∧ p Any help please?
2
votes
2answers
307 views

Is my answer for this truth table & boolean expression correct?

I was given the following boolean diagram: I had to come out with the truth table and the simplified expression. I need help to check if my answers are correct below.
1
vote
1answer
11 views

Converting to complements

Let's say I wanted to convert the ands and positive variables to their complements and ors. Would this be correct? $$DE=$$ $$(DE)''=$$ $$(D'+E')'$$ Or another example: $$D'E=$$ $$(D'E)''$$ Can ...
2
votes
0answers
143 views

Back-and-Forth Argument vs. “One-Way” Argument

The wikipedia article on the Back and Forth Argument claims at the end: If we iterated only step $(1)$, rather than going back and forth, then in some cases the resulting function from A to B ...
1
vote
1answer
58 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
45 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
40 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
45 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
446 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
25 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
395 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
49 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
182 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
281 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
48 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
31 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
76 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
146 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
176 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
427 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
872 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
69 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
56 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 ...
1
vote
1answer
93 views

non-atomic complete Boolean lattice

Is there a Boolean complete lattice that is not atomic?
1
vote
2answers
468 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
28 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 ...
0
votes
1answer
283 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
35 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
38 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
49 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
2k 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 ...
0
votes
1answer
179 views

Logic boolean algebra problem

so I have to prove that these equations : are equivalent?
0
votes
1answer
43 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
87 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
62 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
145 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
51 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
85 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
90 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
89 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
24 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
45 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
227 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
35 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
79 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 ...