Tagged Questions

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

0
votes
1answer
69 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
319 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
98 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
89 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
175 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
175 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...
0
votes
0answers
141 views

Given a state transformation matrix and a state vector, how to find the total number of changes for each individual element.

I have a vector of binary variables, $s$ representing a state at some point in time, and a transformation matrix $T$. The initial state is $s_0$. $s_n = Ts_{n-1}$ Given a number of transformations, ...
1
vote
1answer
515 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
125 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
151 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
519 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
368 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
415 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
78 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
128 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
162 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 ...
0
votes
1answer
166 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
119 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
61 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
3k 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
102 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
965 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
124 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
132 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 ...
0
votes
0answers
134 views

Standard references for boolean algebra?

I'm wondering what books are considered standard references these days, for boolean algebra. I have: Givant & Halmos, Introduction to Boolean Algebras (2010); Sikorsi, Boolean Algebras (3rd ed., ...
4
votes
6answers
3k 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
294 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
251 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?
10
votes
1answer
143 views

Saturated Boolean algebras in terms of model theory and in terms of partitions

Let $\kappa$ be an infinite cardinal. A Boolean algebra $\mathbb{B}$ is said to be $\kappa$-saturated if there is no partition (i.e., collection of elements of $\mathbb{B}$ whose pairwise meet is $0$ ...
3
votes
1answer
152 views

Do filters on a Boolean algebra also make a Boolean algebra?

Let $\mathfrak{B}=(B,\bot,\top,\lnot,\wedge,\vee)$ be a boolean algebra. $B_F$ be the set of all filters on $\mathfrak B$. And for all filter $F$, $G$, $F \wedge_{B_F} G \colon= \mathbf C(F \cup G)$ ...
4
votes
1answer
214 views

Lindenbaum algebra is a free algebra

The following is a continuation of this question. I would like to prove that the Lindenbaum algebra is a free algebra. Hopefully I would like to hear hints on how to proceed in the 'right' ...
1
vote
1answer
84 views

What do you call 2 boolean functions which are equivalent if two arguments exchanged?

What do you call boolean functions which are identical accurate to argument order? EDIT1 I meant not symmetric function. I mean, for example, implication function with truth table 00=1 01=1 10=0 ...
2
votes
1answer
244 views

Free boolean algebra

Consider the following definition: Let $X$ be a set and $e : X \mapsto A$ a mapping to a boolean algebra $A.$ We say that $A$ is free over $X$ (with respect to $e$) if for every mapping $f:X ...
3
votes
1answer
320 views

Cardinality of the set of ultrafilters on an infinite Boolean algebra

Let $\mathfrak B$ be a Boolean algebra with an infinite power $\kappa$. My question is how many ultrafilters does it have? $\kappa$ or $2^\kappa$? Or even smaller?
3
votes
1answer
138 views

Inducing maps between Boolean completions of posets

Given a separative poset $P$, we can form it's Boolean completion $B(P)$. This is a Boolean algebra whose elements are regular cuts on $P$, as defined here. Also, $P$ embeds densely into $B(P)$ by ...
4
votes
2answers
166 views

Stone duality for ideals and filters (exercise)

In A Course in Universal Algebra (Burris, Sankapannavar), the exercise 4.4.7-8, p.158, says: Let $A$ be a Boolean algebra. Denote $A^\ast:=\{\text{ultrafilters of }A\}$, and give $A^\ast$ the ...
5
votes
1answer
207 views

A free boolean algebra

Consider the following definition: The boolean algebra $A$ is generated freely with the subset $G \subseteq A$ if for every boolean algebra $B$ and map $f:G \mapsto B$ there is precisely one ...
2
votes
2answers
94 views

Automorphisms of a boolean algebra

Let $A = P(\mathbb{N})$ be the powerset of the natural numbers. We can look at $A$ as the Boolean aglebra - having in mind the obvious operations on elements of $A$. What I am interested in knowing ...
0
votes
1answer
93 views

Extracting information from simultaneous boolean AND, XOR, and NOT

I'm looking to extract some information from a series of equations with AND, XOR and NOT. I've already covered all of the easy parts using various boolean identities, so I'm looking to now determine ...
3
votes
1answer
181 views

Non-Boolean group with every element of order two

Let $G$ be a group (not necessarily finite) such every element of $G$ has order 2. Every such group is abelian [1]. Clearly, every Boolean algebra $B$ is a group of this type, when equipped with the ...
5
votes
4answers
260 views

Non-isomorphic atomless Boolean algebras

All countable atomless algebras are isomorphic. Can one give an example of a pair of mutually non-isomorphic atomless Boolean algebras of cardinaliy continuum?
3
votes
1answer
75 views

Chains in the Lindenbaum algebra

What is the easiest example of an infinite chain in a Lindenbaum algebra for the propositional calculus? Does there exist an infinite antichain in a Lindenbaum algebra?
1
vote
1answer
41 views

Finding basis for $L\cap M$?

I've been tasked to find a basis for the following system of Boolean functions: $L\cap M$, where $L$ is a class of linear functions and $M$ is a class of monotone functions. Attempt at solution By ...
1
vote
2answers
4k views

simplifying using Boolean Algebra.

I was doing the following question. Using the following rules of boolean algebra: _ law 1: X+X=1 law 2: X.1=X law 3:X.Y+X.Z = X.(Y+Z) simplify: ...
1
vote
1answer
73 views

Maximal set of pairwise disjoint elements of a dense subset.

Let $B$ be a complete Boolean algebra, and suppose $D \subseteq B$ is a dense subset. How is it possible to construct a maximal set of pairwise disjoint elements of $D$? Is it true that $\sum S = \sum ...
2
votes
1answer
367 views

Translating FOL from English?

I have searched for answers/help, but I am not able to find specifics. I am on a "FOL for Dummies" level, I really have no clue what I'm doing. Edit: I understand most of the symbols (∀x, the ...
0
votes
1answer
42 views

Boolean Expression

If the syntax of a language is: $a ::= n | x | a_1 + a_2 | a_1 \star a_2 | a_1 - a_2 $ $b ::= true | false | a_1 = a_2 | a_1 \leq a_2 | ¬ b | b_1 \wedge b_2 $ As $x_1 > x_2 $ is not permitted in ...
1
vote
0answers
62 views

$\Delta_0$-formulas in the Boolean-valued model $V^B$

I want to show that $\Vert \check x = \check y \Vert = 1$ implies $x = y$, where $\check x$ is the canonical name for $x$ in $V^B$. I'd like try induction over the ranks of $\check x$ and $\check y$ ...