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.
1
vote
1answer
54 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
187 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
34 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
54 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
112 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
158 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}$ ...
0
votes
1answer
485 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
0answers
82 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
551 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
144 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
130 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
219 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
216 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
243 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
643 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 ...
2
votes
2answers
73 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
59 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
116 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) ...
1
vote
1answer
106 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
106 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
227 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
187 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
153 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
147 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
44 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 ...
1
vote
1answer
224 views
Expanding this boolean expression
Can this Boolean expression:
$$A*\overline{A*B}$$
be expanded to give:
$$A*\overline{A} * A*\overline{B}$$
Although that appears to reduce to zero?
I know $A(\overline{A+B})$ can be expanded to ...
0
votes
3answers
3k views
De Morgan's Theorems
Could someone give me an algebraical demonstration of the De Morgan's Theorems?
I already know the graphic demonstration with the truth table, but I need to understand the algebraical way.
EDIT
I ...
0
votes
1answer
297 views
Simplify boolean expression
$(xy’+z)’\cdot((xz)’+y')$
$$\begin{align*}
(xy’+z)’\cdot ((xz)’+y’) &=(x'+yz’)\cdot (x’+z’+y’)\\
&=x’x’ + x’z’ + x’y’ + yz’x’ + yz’z’ + yz’y’\\
&=x’ + x’z’ + x’y’ + yz’x’ + ...
0
votes
2answers
527 views
What do these terms mean: commutative, associative, distributive
I am reading a book, and I am trying to understand what the writer really mean by the following terms. I would like to understand what these words mean in relation to the examples.
In regular ...
3
votes
1answer
254 views
What are the algebras of the double powerset monad?
Let $\mathscr{P} : \textbf{Set} \to \textbf{Set}^\textrm{op}$ be the (contravariant) powerset functor, taking a set $X$ to its powerset $\mathscr{P}(X)$ and a map $f : X \to Y$ to the inverse image ...
0
votes
1answer
89 views
Boolean algebra-Modular lattice
Let $L=\{a,b,c,d,e,f\}$; $P(L)$ is the set of all partitions of $L$, and $\le$ is the order relation on $P(L)$ defined as:
if $r$ and $t$ are relations, then $r\le t$ iff every block in $r$ is a ...
2
votes
0answers
50 views
Name for this type of space over a boolean algebra?
The structure has two carrier sets $E$ and $A$, operators $({}^*, \wedge)$ over $E$, and a ternary "decision" operator $D:E \times A \times A \to A$, written infix $(p?a:b)$, whose intended meaning is ...
1
vote
1answer
138 views
Find an optimal 4-tuple which satisfies a boolean expression
(I have post a question with bounty for several days (Find a best 4-tuple which fulfils a variable boolean formula), but unfortunately got no answer yet. Here I simplify it to a smaller problem and ...
0
votes
1answer
51 views
Decompose boolean function of multiple variables into multiple functions of one variable
say I have a function $$f(x, y) : bool$$ of two variables x and y - whose type can be anything - returning either true or false.
I would like to create two functions of one variable each $g(x)$, ...
0
votes
1answer
68 views
BOOL algebra : simplifications
I have this expression :
(A && B) || (A && C) || (B && C)
I don't understand which steps I need to to to get this expression :
(A && B) || (C && (A XOR B))
0
votes
1answer
139 views
Find a best 4-tuple which fulfils a variable boolean formula
I am looking for an algorithm...
I have a kind of boolean formulae which contain $\wedge$, $\vee$, $+$ as arithmetic operator, relational operators ($<, >, \ldots)$, 4 integer constants $c_0, ...
0
votes
1answer
2k views
How to simplify in boolean algebra
I have some homework I can't seem to figure out. The assignment causing problems is devided into two parts; The first is to determine the inverse formula for a given formula (so the S = F'). The ...
1
vote
1answer
382 views
Parity Checking and truth tables
I have a question that I am very confused about.
Parity Checking.
Produce a truth table for a parity checking circuit that is based on $4$ input data bits, an input parity bit and a single ...
0
votes
2answers
118 views
Trouble with boolean algebra as used in logic
I'm having trouble knowing how to continue on with this problem, I don't know what to turn the equivalent sign into and I cant really continue with that side, can anyone help me out?
Do I just say ...
1
vote
1answer
303 views
Determining the result of Boolean shape operations on closed Bézier shapes
Given two closed shapes made up of Bézier curves (and/or straight lines), I'm looking for an efficient way of calculating the resulting shape of the following Boolean operations:
union
difference
...
1
vote
3answers
129 views
Boolean algebra probability not coming out right
Assuming A,B,C,D are mutually independent.
$P[(A\cup\overline{B}\cup C)\cap(A\cup C \cup \overline{D})]$
I get $(P(A) + 1 - P(B) + P(C))(P(A) + P(C) + 1 - P(D))$
But when I plug in the numbers, I ...
6
votes
1answer
222 views
Simple functions and axiom of choice
The question I have is more of a curiosity, and that is why I decided to post here instead of Mathoverflow.
Before posing the question, let me set up some background.
Background: Let $\Omega$ be a ...
1
vote
2answers
70 views
Low degree approximation of the polynomial extension of the logical-or function
Let $x\in\{0,1\}^n$ be a binary vector of dimension $n$, and let $OR(x)$ be the "logical or" function (i.e., returns $1$ if at least one of the coordinates is $1$ and otherwise returns $0$).
Consider ...
2
votes
1answer
76 views
Extending the logical-or function to a low degree polynomial over a finite field
Let $x\in\{0,1\}^n$ be a binary vector of dimension $n$, and let $OR(x)$ be the "logical or" function (i.e., returns $1$ if at least one of the coordinates is $1$ and otherwise returns $0$).
Is there ...
2
votes
2answers
667 views
All finite boolean algebras have an even number of elements?
This seems obvious but I wanted to check, since I don't see it mentioned anywhere.
If we define a boolean algebra as having at least two elements, then that algebra has a minimal element (0) and a ...
1
vote
1answer
4k views
Boolean algebra question: Converting between sum-of-products and product-of-sums
NOTE: $b'$ means $b$ not
I'm trying to convert $ab'd + ab'cf$ to product of sums form
My professor gave us the following hint:
"Invert the equation, reduce it to sum-of-products, ...
0
votes
2answers
56 views
Search the OR of negation between boolean algebra
I have this formula
$$(a\cdot b)+(\neg a\cdot \neg b)$$
At first I thought this kind of $a+\neg a = 1$ so the answer is 1, but then I realized $(\neg a\cdot \neg b) \neq \neg (a\cdot b)$.
I try to do ...
3
votes
1answer
199 views
What's a structure where $a-a = 1$ and $a\cdot a^{-1} = 0$?
I'm trying to specify a structure that has the basic features of a Boolean algebra but not necessarily restricted to binary sets. However, I observed that I almost have a field except that ...
3
votes
2answers
311 views
Sum of Products (Boolean Algebra)
I am having real trouble getting to the corrects answers when asked to simply Sum of products expressions.
For instance:
Determine whether the left and right hand sides represent the same ...
1
vote
2answers
264 views
Karnaugh Map for an expression with two terms
When I have an expression such as:
$f(x_1,x_2,x_3)= \sum m(1,4,7)+ D(2,5)$
What do I do with the part D(2,5)? Do I make a second k-map just for that term and OR(+) it to the expression or should I ...
