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

5
votes
3answers
2k 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
92 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
842 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
116 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
114 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
94 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
2k 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
257 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
231 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
130 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
136 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
194 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
73 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
216 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
274 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
132 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
148 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
180 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
81 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
90 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
152 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
233 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
72 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
38 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 ...
0
votes
3answers
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
72 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
311 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
39 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
60 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$ ...
2
votes
1answer
123 views

Question about Cuts in Boolean Algebras

Let $A$ be a Boolean algebra, and let $A^+$ denote the set of non-zero elements of $A$. A cut $U \subseteq A^+$ is a set such that if $q\in U$, then $p\le q \implies p \in U$, for all $p \in A^+$. A ...
5
votes
1answer
186 views

Boolean algebras of projections

Suppose $X$ is a Banach space with an unconditional basis $(e_n)$. Then, one may easily define a Boolean algebra of projections in $\mathcal{L}(E)$ which is isomorphic to the power-set of $\mathbb{N}$ ...
1
vote
1answer
2k views

Boolean algebra operation precedence?

In my discrete mathematics class we wrote down the truth table for some Boolean functions and in that table they go in the following order: ¬, ∧, ∨, →, ~, ⊕, |, ↓ So, I assumed that this is the ...
0
votes
1answer
180 views

Single Complement Variable + 1

Is a complement + 1 = 1? For example A' + 1 = 0; I was thinking it was (I'm new to boolean algebra) since A' = 0, and 0 + 1 in boolean algebra is just 1. Of course, A can be anything, but assuming ...
0
votes
2answers
683 views

Simplify expression using boolean algebra laws

I can work out what the expression simplifies to and can show the equivalence with a truth table, but I don't know the law (or sequence of laws) that need to be applied to show this formally. This is ...
1
vote
2answers
178 views

simplify the boolean expression $abc|ab\sim c|a\sim bc|\sim abc$

I worked this through to a&c but this has to be wrong. I'm clearly going wrong somewhere. Could someone point out the wrong step in my method? $$(a\land b\land c)\lor (a\land b\land \lnot c)\lor ...
2
votes
1answer
158 views

What does Tarski mean by a “tautological operation” on a Boolean algebra?

I am reading Part II of Chin and Tarski's "Distributive and Modular Laws in the Arithmetic of Relation Algebras". In the beginning of section 4, the authors say "In general, if $\odot$ is a binary ...
1
vote
2answers
479 views

Stuck on rewriting logical implication

I've started to work through Applied Mathematics for Database Professionals and have been stuck on one of the exercises for two days. I've been able to prove the expression: $$\left( P\Rightarrow Q ...
1
vote
2answers
316 views

Boolean simplification with some known term combinations

I am doing boolean simplification using Quine-McCluskey which works well. However, I now need to perform the simplification with some known term combinations. For example, I want to simplify: ...
6
votes
2answers
304 views

Is there an $O(n^2)$ test to determine if an $n \times n$ Boolean matrix $B$ has an inverse?

D.E. Rutherford shows that if a Boolean matrix $B$ has an inverse, then $B^{-1}= B^T$, or $BB^T=B^TB=I$. I have two related questions: The only invertible Boolean matrices I can find are ...
3
votes
4answers
1k views

An “atom” in Boolean algebra

Could someone explain what an atom in Boolean algebra means? I am acquainted with ring theory and group theory but not Boolean algebra. As far as I can tell from browsing around, it is something like ...
3
votes
2answers
92 views

Countable saturation impossible in a complete Boolean algebra?

Let $B$ be an infinite, complete Boolean algebra, and let $\kappa = \operatorname{sat}(B)$. I would like to show that $\kappa$ is uncountable. If we suppose $\kappa$ is countable, that is to say ...
2
votes
2answers
67 views

Is it true that a dense subset of a complete Boolean algebra has supremum 1?

Let $S\subseteq B$ be a dense subset of a complete Boolean algebra $B$. Is is true that $\sum S = 1$? Jech seems to use this fact several times in his book (e.g. the proof of 7.15) but I have been ...
0
votes
1answer
134 views

A Distributivity Law in Complete Boolean Algebras

Let $B$ be a complete Boolean algebra. Define 3 subsets of B as follows: $B_I:= \{ u_{0,i} \mid i \in I \}$ $B_J := \{ u_{1,j} \mid j \in J \}$ $B_{I \times J} := \{ u_{0,i} \cdot u_{1,j} | (i,j) ...
2
votes
1answer
127 views

If $B$ is an infinite complete Boolean algebra, then its saturation is a regular uncountable cardinal

I am trying to understand the proof of the statement (Jech 7.15) If $B$ is an infinite complete Boolean algebra, then $\operatorname{sat}(B)$ is a regular uncountable cardinal. I understand the ...
1
vote
1answer
127 views

A complete Boolean algebra $B$ satisfies the $\kappa$-chain condition if and only if $B$ is $\kappa$-saturated

Let $B$ be a Boolean algebra. Then we say $B$ is $\kappa$-saturated if there is no partition $W$ of $B$ such that $|W| = \kappa$. We say that $B$ satisfies the $\kappa$-chain condition if there is no ...
3
votes
3answers
268 views

The completion of a Boolean algebra is unique up to isomorphism

Jech defines a completion of a Boolean algebra $B$ to be a complete Boolean algebra $C$ such that $B$ is a dense subalgebra of $C$. I am trying to prove that given two completions $C$ and $D$ of $B$, ...
1
vote
1answer
254 views

Simplifying a boolean expression

Can someone help me simplify this boolean expression? $$(a+b+c+d)(a'+b'+c'+d')$$ so if I use the distributive property, I'll get: ...
4
votes
1answer
184 views

Question about Boolean algebra and ultrafilters

In the following $B$ denotes a Boolean algebra and $\bar{x}$ is the complement of $x$. In my notes there is the following theorem: If $U \subset B$ is an ultrafilter on $B$ then for every $x \in B$ ...
0
votes
2answers
186 views

Can Boolean function's value be computed by using a rewrite system?

Suppose there is a function in e.g. CNF form. For example: $$ (A \vee B) \wedge (\neg B \vee C \vee \neg D) \wedge (D \vee \neg E) $$ For given A,B,C,D,E values it is possible to compute the value ...
1
vote
2answers
46 views

In a Boolean algebra B and $Y\subseteq B$, $p$ is an upper bound for $Y$ but not the supremum. Is $q<p$ for some other upper bound $q$?

I don't think that this is the case. I am reading over one of my professor's proof, and he seems to use this fact. Here is the proof: Let $B$ be a Boolean algebra, and suppose that $X$ is a dense ...