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
2answers
1k views

Simplifying boolean function using boolean algebra

How to simplify the following expression : A'BCD + AB'CD' + AB'CD + ABC'D + ABCD' + ABCD ? It should get AC + BCD + ABD using Kmap but using boolean algebra i am stuck no matter how i try .
0
votes
2answers
209 views

Element chasing style proof applied to Boolean algebra problem

I would like to apply an element chasing style proof to the following problem: Let $P$, $Q$ and $R$ be elements of a Boolean algebra. Prove that if $$ \tag 1 P + Q = P + R$$ and $$\tag 2 P ...
2
votes
1answer
53 views

Does a complete subalgebra A of a complete boolean B algebra always intersect all dense subsets of B?

I'm trying to show that if $(B, i)$ is the (BA) completion of any partial order $P$ and $A$ is a complete subalgebra of $B$, then $i^{-1}[A]$ is a complete suborder of $P$. Pure hunch says it's ...
0
votes
1answer
87 views

Give all Boolean algebras on the finite set

Given a finite set $X=\{1,2,3\}$, are the following all the Boolean algebras? $A_1=\{\{1\},\{2\}\},$ $A_2=\{\{1\},\{3\}\},$ $A_3=\{\{2\},\{3\}\},$ $A_4=\{\{1\},\{1,2\}\},$ $A_5=\{\{1\},\{1,3\}\},$ ...
1
vote
2answers
5k views

Simplifying Boolean Function with Karnaugh Maps

Given the boolean function f(x,y,z) = xyz + xyz' + xy'z + xy'z' + x'yz + x'y'z + x'y'z' (where x' = not x) In a three variable Karnaugh Map: ...
1
vote
1answer
227 views

Transforming statements of a query language to propositional logic

I have a custom query language which expresses containment relations between variables. Containment in this context is simply an object (A) in programming language X (java/C#/python etc: a language ...
0
votes
1answer
150 views

Boolean Algebra Simplification Help, Need AND's, OR's, NOT's only

I'm having a very hard time simplifying this: A!B!C+ABC+!A!BC+!AB!C The objective here is to simplify the equation until it can be expressed in "AND"'s "OR"'s and "NOT"'s. I have to create an ...
1
vote
1answer
63 views

If X is a subset of a complete boolean algebra, must there be a finite $Y \subset X$ s.t. sup(Y) = sup(X)?

The question came up when I was trying to prove the compactness of the stone space S(B) of a complete boolean algebra B. Using only the basic facts regarding ultrafilters and boolean algebras, I ...
0
votes
2answers
90 views

Is this boolean algebra problem solvable?

My professor is of no help at all. He's foreign and is giving assignments that are written poorly, and is teaching stuff far beyond what he's supposed to be teaching at this level. Nonetheless, he's ...
1
vote
1answer
531 views

Boolean Algebra Distributive Laws

Given that $x\cdot(y+z)=(x\cdot y)+(x\cdot z)$ and $x+(y\cdot z)=(x+y)\cdot (x+z)$, what is the name for the opposite of those rules? Say I'm trying to prove the opposite, and I need to simplify from ...
1
vote
1answer
577 views

compare 3 variables in MATLAB

I am wondering how to compare 3 variables in MATLAB, because MATLAB is comparing first 2 and then result against 3rd. To illustrate with example: (-1 == -1 == -1) ans = ...
2
votes
2answers
68 views

Is there a name for the set $\{T,F\}$?

Is there a name for the set containing the two Boolean values, i.e. $\{T,F\}$? I am also thinking if $B = \{T,F\}$, and $B^n = \underbrace{B \times B\times B ... \times B}_n$, then is there a proper ...
1
vote
2answers
759 views

Boolean Simplification: (A+C)(!A+B)(B+C) = BC

How might I solve this? I can't find any problem similar to this, and I always end up with the wrong terms. If (AB) = 0 and (A+B) = 1, prove that (A+C)(!A+B)(B+C) = BC
3
votes
3answers
137 views

Boolean Algebra

There seems to be some discrepancy between my answer and the solution's. Can somebody please tell me what I have done wrong? Thanks! $$\begin{align} \left(A \lor B\right) \land \left(B \lor C\right) ...
0
votes
2answers
74 views

toggle boolean and more

Recently I used this to toggle a Boolean value, b being the current value and self.status being the result self.status = (b-1)*(b-1) This rather than use an if ...
4
votes
2answers
517 views

calculating number of boolean functions

I would just like to clarify if I am on the right track or not; I have these questions: Consider the Boolean functions $f(x,y,z)$ in three variables such that the table of values of $f$ contains ...
0
votes
2answers
226 views

is the following a Boolean Algebra?

Boolean Algebra: $$D_{30}=\{n:n\mid30\}= \{1,2,3,5,6,10,15,30\}$$ I don't know how to test that this is a boolean algbra (a BA is a distributive lattice with $T,F$ in which every element has a ...
0
votes
1answer
110 views

Proving if equations are products of XOR

I have to prove analytically to see if these equations are exclusively or. $$A⊕ A=0$$ Do I solve this by using the truth table? ...
1
vote
0answers
86 views

Generating Input Binary Combination Dynamically

this is probably right forum to post this question I am currently working on a application where there is a requirement to generate binary combination of input signals in a truth table. The signal ...
0
votes
2answers
539 views

Show that $x \wedge y = x \iff x \vee y= y$ using the following properties

Suppose $L$ is a set with binary operations $\wedge$ and $\vee$, along with the special $T$ and $F$ (for an $x,y,z \in L$) such that the following rules hold: $x\wedge T=x$; $x\vee y=T$ ...
1
vote
1answer
90 views

How to prove distributivity in Boolean Rings

A Boolean ring is a ring which all of its elements are idempotent, i.e. $a ^{2}=a$. I know that If we interpret multiplication and addition in such a ring, as meet and joint respectively, then Boolean ...
0
votes
1answer
226 views

Boolean simplification

So I am giving this expression D +B’C’ + CD’ +A B’C and I ask to simplify it When working through it I get D+B'C'+CD'+AB'C D'(A'B'+CD'+AB) D'(A'B'+A(B'+B)) D'(A'B'+AC') D'(B'+A) Am I on the right ...
0
votes
1answer
75 views

Boolean Function

A Boolean expression is given: (A B)’ + B C’ +A’ C = F. Construct the logical circuit and draw the timing diagram of the output F. I am not sure where to start.
1
vote
1answer
345 views

Boolean Simplification

I'm having some trouble getting a handle with this course. We are starting Boolean algebra and my professor wants us simplify the following: (AB)'+(A'+B')'= (AB)'+BC+A'B'C'= I am assuming the "()" ...
5
votes
1answer
101 views

Adjoint for functor involving Boolean rings

Let $R$ be a a commutative ring with a unit element, then one can associate to $R$ a Boolean ring $B(R)$, as in this text by Bergman, last line of page 594. (I guess this is a very classical thing. ...
0
votes
1answer
94 views

Linearly separate a cube

I am facing the problem of the linear separability of a three dimensional cube. Let's take the opposite vertexes of the cube as $(0, 0, 0), (1, 1, 1)$. It is possible to split it with a plane in two ...
1
vote
1answer
220 views

Terminology question; inverse vs complement in Boolean algebra

This was said at a lecture I attended: $e$ is neutral element for operation $*$ if $\forall x (x*e=x \wedge e*x = x)$. So, for example 0 is n. e. for disjunction and 1 is n. e. for ...
0
votes
1answer
61 views

Help at solving boolean function.

I`m having some difficulties solving a boolean expression (I am converting it to CNF form). The expression is: $$F = (Q_1 \to P1 \land \lnot P_2) \lor Q_1 \land P_2 \lor P_1$$ So i do not know, ...
2
votes
3answers
213 views

Non-principal ideal in Boolean ring

Does anyone know a simple example of a Boolean ring with a non-principal ideal? Every finitely generated ideal in a Boolean ring is principal, hence such an ideal cannot be finitely generated...
1
vote
1answer
663 views

Boolean Logical Algebra - Prove 4 nor gates to an xnor gate.

Need to reach the following conclusion (or maybe its the premise?) AB + A'B' = F http://upload.wikimedia.org/wikipedia/commons/thumb/f/f8/XNOR_using_NOR.svg/256px-XNOR_using_NOR.svg.png
1
vote
4answers
152 views

Infinite boolean sequence

I was given the following problem: Let $V_1, V_2, \dots$ be an infinite sequence of Boolean variables. For each natural number $n$, define a proposition $F_n$ according to the following rules: ...
1
vote
2answers
167 views

Boolean algebra spectrum

The first-order spectrum of a theory, is the set of cardinalities of its finite models. Finite models of Boolean algebras are informally n-dimensional cubes, therefore boolean algebra spectrum is the ...
-1
votes
2answers
595 views

Boolean Algebra - Truth Table

X'Y'Z' + XYZ I have the equation above (Boolean Algebra truth table), and as I know, if I get x' and the value of x is 0, the value will change to 1. But Y' with the top bar being higher, what ...
1
vote
0answers
458 views

Number of canonical expressions

There is a question: What is the number of canonical expressions that can be developed over a 3-valued boolean algebra? I was trying to solve this. Canonical expression is the combination of ...
3
votes
1answer
688 views

Boolean Algebra Manipulation/Simplification

I have come across a couple questions while doing my digital logic work. 1) Is it possible to simplify these, while keeping each a product of sums? (I'm leaning towards no--the only way I could see ...
2
votes
1answer
80 views

Which of the following representations of Karnaugh map is 'better'?

I usually come across two representations of Karnaugh maps in books and on the web as shown in the figure. The difference is whether the higher order variables are on the rows or on the columns. I ...
2
votes
1answer
136 views

Boolean circuits and digraphs

It is well known that connecting NAND gates allows the construction of arbitrary circuits. Furthermore, a NAND gate can be represented as a digraph with four vertices (in order, the two inputs, the ...
1
vote
3answers
4k views

Boolean function simplification

I'm having problems with the following expression: (A'+B)'+B(A'+AC)+ABC' And here is what I tried to simplify: ...
2
votes
1answer
190 views

Better compression for a positive DNF than via BDD

I am experimenting with compressing positive disjunctive normal form (DNF). When I use binary decision diagrams (BDDs) related algorithms I don't get very good results. For example the algorithms ...
1
vote
1answer
189 views

Three questions on chapter 7 of Jech's Set Theory

In the proof of Pospisil's Theorem (theorem 7.6) that there are $2^{2^\kappa}$ uniform ultrafilters on $\kappa \geq \omega$, the author writes : Let $\mathcal{A}$ be an independent family of subsets ...
2
votes
1answer
140 views

Complete Lattice with unique negation

Suppose i have a complete lattice (meet and join exist for any two subsets of the lattice) and for every element of the lattice, there is a unique element that is its complement (hence a Boolean ...
0
votes
1answer
63 views

Number of basis representations of Boolean vectors

Suppose I have a basis $v_1, ..., v_n$ of boolean vectors and a boolean vector $v$ that was constructed by iterated $v = v_i$ $OR$ $v_j$ statements. I want a way to figure our how many unique ...
5
votes
3answers
4k views

Simplify $A'B'C'D' + A'B'CD' + A'BCD' + ABCD' + AB'CD'$

How do you simply the following equation? $$X = A'B'C'D' + A'B'CD' + A'BCD' + ABCD' + AB'CD'$$ Here is what I did: $$\begin{eqnarray} X & = & A'B'C'D'+A'CD'(B'+B) + ACD'(B+B') \\ & ...
1
vote
1answer
111 views

Localizations of the Boolean Ring P(X)

Given a set $X$, we can construct the Boolean ring whose elements are the power set of $X$. The multiplication therein is intersection, and the addition is symmetric difference. I am interested in ...
0
votes
1answer
1k views

Boolean Algebra simplification - odd number terms

I'm new to boolean algebra and having problems simplifying expressions with odd number terms, Expressions such as: 1. A'B'C'D + A'B'CD + AB'C'D + AB'CD + ABC'D 2. A'BC + AB'C' + A'B'C' + ...
0
votes
1answer
136 views

A question about the regular languages being closed under Boolean operation (how to generalize)

I know that if $L_{1},L_{2}$ are regular languages then so is $L_{1}\cap L_{2},L_{1}\cup L_{2}$ are regular languages, I also know that $L$ is regular $\implies L^{c}$ is regular . It is easy to ...
0
votes
1answer
163 views

Converting a Proposition to DNF using proof systems

I have been attempting to convent a prop to DNF using a group of common rules, i have applied them all but i think i should be able to get it smaller, This is what I've got so far. Thanks! $$(p \wedge ...
5
votes
6answers
4k views

how to solve system of linear equations of XOR operation?

how can i solve this set of equations ? to get values of $x,y,z,w$ ? $$\begin{aligned} 1=x \oplus y \oplus z \end{aligned}$$ $$\begin{aligned}1=x \oplus y \oplus w \end{aligned}$$ $$\begin{aligned}0=x ...
2
votes
1answer
339 views

Lindenbaum Algebras

After reading this page, I still have some questions about Lindenbaum algebras. Assume that the scope is a propositional language with a denumerable set X of propositonal variables. In that case, ...
1
vote
2answers
279 views

boolean algebra simplification to remove extra term

how do i simplify this equation using boolean algebra: AB + ¬AC + BC to be equal to AB + ¬AC the BC is unneeded, but how do i remove that term using boolean algebra?