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
46 views

non-atomic complete Boolean lattice

Is there a Boolean complete lattice that is not atomic?
0
votes
0answers
26 views

A set with a property in a Boolean lattice.

Are there a Boolean lattice $(X,\le)$, $A\subseteq X$ and $b\in X$, such that $\sup A$ exists but $\sup\{a\wedge b|a\in A\}$ does not exist.
2
votes
2answers
263 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
21 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
0answers
39 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
31 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
68 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
27 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
35 views

One implication (on Measure)

Please be noted that charges are finitely additive measures and measure are countably additive ones. for charges $ (i)\Rightarrow (ii) \Rightarrow (iii)$, and they are equivalent for measures. ...
0
votes
2answers
112 views

DNF and CNF logic problem

So i want to find the DNF and CNF of : $ 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 and stuff, I also plotted it in ...
0
votes
1answer
59 views

Logic boolean algebra problem

so I have to prove that these equations : are equivalent?
0
votes
0answers
20 views

Dual functions in boolean algebra

Are all the properties satisfied by a Boolean function satisfied by its dual also(for example if a+b=c+d,then is ab=cd,this is just a simple demonstration, but it does it hold for even some complex ...
0
votes
1answer
26 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?
1
vote
2answers
47 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
46 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 ...
0
votes
0answers
39 views

Proving functional completeness

Assume given a Boolean Function $f(a,b,c)$ and you're asked if it's functional complete, this, as far as I know, means that by applying $\left \{ x,y,1,0\right \}$ to the function you can get $\left ...
2
votes
2answers
65 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
41 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 ...
0
votes
0answers
35 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
61 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
53 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
19 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
36 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
194 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
27 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$, ...
-1
votes
2answers
24 views

Simplify this Boolean Expression X + (~x) * y [closed]

Need help on this Homework. Don't know how to start
0
votes
0answers
10 views

Finding a boolean expression. [duplicate]

My question is following. Suppose that we have a boolean formula which is conjunction of $\sum_{3 \leq i \leq 15} m_i$ clauses. The clauses consist of $m_3$ disjunctions of length 3, $m_4$ ...
0
votes
1answer
59 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
34 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
144 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} ...
2
votes
1answer
49 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
0answers
43 views

Explain why the description defines a Boolean algebra.

Here is the exercise I am trying to figure out. Let A = {a,b} and list the four elements of the power set P(A). We consider the operations + to be $\cup$, . to be $\cap$, and complement to be set ...
0
votes
4answers
67 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
68 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
31 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 ...
0
votes
1answer
60 views

Truth table to prove statements

A, B and C. When questioned A says ''If B did not do it, then it was C." B says ''A and C did it together or C did it alone". C says ''We all did it together." How would i be able to put these into ...
0
votes
0answers
11 views

Every boolean algebra is the Lindenbaum algebra of a suitable theory

Can you suggest me a book/article/lecture notes where I can find informations about the topic: Lindenbaum Algebra and Boolean algebra? My purpose is to prove (or to sketch the proof of) the title ...
0
votes
1answer
29 views

Write $p \rightarrow \lnot q$ in CNF form with only and ,or and brackets

Write $p \rightarrow \lnot q$ in CNF form with only and, or, and/or brackets How on earth would I even do this? Completely lost! Any help appreciated.
0
votes
1answer
30 views

Boolean algebra (ISO)

Let $\mathfrak{A}$ be a Boolean algebra and $E$ be an element in $\mathfrak{A}$. The set of all subelements of $E$ forms a Boolean algebra, denoted by $\mathfrak{A}_E$. Suppose that $I$ be the ...
0
votes
1answer
43 views

Boolean formula vs boolean function.

Is there a technical difference between boolean formulas and boolean functions?
0
votes
0answers
38 views

How to simplify the boolean expression: $BCD+AC'D+A'BCD'+AB'D' +AB'C'D$

I have tried to simplify: $$BCD+AC'D+A'BCD'+AB'D' +AB'C'D $$ using logic rules, as well as multisim software, the last one says that the answer is $A'BC+AB'D'+AC'D+BCD$ Thanks.
0
votes
0answers
15 views

Translate Inequality to 2-SAT

How to translate Inequality, such as $A<B$ to $2-SAT$. I had an idea comparing the bits of the number but I failed implementing it.
1
vote
2answers
57 views

How to simplify this using boolean algebra?

My paper is due tomorrow and there is only the last exercise left for me to do. However, I don't have any sufficient notes or examples on how to simplify it. Any help would be appreciated! A'B'C' + ...
0
votes
1answer
21 views

Explain one statement about Stone Space

In this page Stone Space This is no clear for me "The points in S(B) are the ultrafilters on B, or equivalently the homomorphisms from B to the two-element Boolean algebra" I think I means every ...
1
vote
1answer
45 views

What is the underlying math in this relation?

Suppose we have the constraint $$.7x_1+.4x_2+.5x_3<1,$$ $$x_1,x_2,x_3\in\{0,1\}$$ Then we can convert it to a Boolean expression with binary variables of the form $$(\neg x_{1}\wedge\neg ...
2
votes
1answer
57 views

Can the obvious “product” of complete atomistic Boolean algebras be realized as a categorial product?

Let $X$ and $Y$ denote sets, and $\eta_X,\eta_Y : X,Y \rightarrow X+Y$ denote the natural injections to the disjoint union. Then intuitively, the "product" of the Boolean algebras $2^X$ and $2^Y$ ...
-1
votes
1answer
35 views

Boolean Algebra help [closed]

Establish the validity of the equivalence by using the Boolean properties attached. Only work on the left side. State the letter of the property you use at each step. $$(x\lor y)'\lor(x\land ...
1
vote
1answer
29 views

Convert a Boolean expression to a linear expression?

Suppose we have a Boolean expression $$(\neg x_{1}\wedge\neg x_{2})\vee\left(\neg x_{1}\wedge\neg x_{3}\right),$$ which we need to be true. Is there a method to convert this to a linear expression of ...
0
votes
1answer
78 views

How can I get a product-of-sums from this sum-of-products?

I have this function: $$f(A,B,C,D) = A'B' + CD' + ABC + A'B'CD' + ABCD'$$ I used a Karnaugh map to minimize the function to: $$Minimum SOP = A'B' + C D' + A B C$$ How can I turn this into a ...
0
votes
0answers
237 views

How to convert this Boolean expression to a NAND-only version using De Morgan's law?

I have a short Boolean expression which I have to convert to a NAND-only circuit, using De Morgan's theorem: a¬⊕(b∨c), i.e a XNOR (b OR c) I have started by applying the theorem to "(b∨c)", which ...