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
44 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
257 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
23 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
154 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
47 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
140 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
155 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
46 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
28 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
60 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
46 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
78 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
50 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
108 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
252 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
257 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 ...
2
votes
1answer
58 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
39 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
58 views

non-atomic complete Boolean lattice

Is there a Boolean complete lattice that is not atomic?
0
votes
0answers
31 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.
1
vote
2answers
336 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
23 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
92 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
33 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
72 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
30 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
45 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 ...
0
votes
2answers
278 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
85 views

Logic boolean algebra problem

so I have to prove that these equations : are equivalent?
0
votes
1answer
33 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
65 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
54 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
48 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 ...
5
votes
3answers
119 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
47 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
52 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
71 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
61 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
21 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
39 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
205 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
67 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
37 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
165 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
75 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
76 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
190 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') ...