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

1k views

Any two points in a Stone space can be disconnected by clopen sets

Let $B$ be a Stone space (compact, Hausdorff, and totally disconnected). Then I am basically certain (because of Stone's representation theorem) that if $a, b \in B$ are two distinct points in $B$, ...
250 views

Not every boolean function is constructed from $\wedge$ (and) and $\vee$ (or)

Prove that not every boolean function is equal to a boolean function constructed by only using $\wedge$ and $\vee$. Here is my solution, can I ask for a feed back on my solution please? $p∧q$ ...
9k views

255 views

Boolean algebras without atoms

Why is the theory of Boolean algebras without atoms $\omega$-categoric?
83 views

How to prove boolean ordering question

Let $\sqsubseteq$ be the boolean ordering of $X$, so for every $x$ and $y$ applies $x \sqsubseteq y$ if $x \sqcap y = x$. Let $v, w, a, b \in X$ with $v \sqsubseteq a$ and $w \sqsubseteq b$. Show that ...
203 views

A construction on boolean lattices is itself a boolean lattice?

Let $\mathfrak{A}$ and $\mathfrak{B}$ be (fixed) boolean lattices (with lattice operations denoted $\sqcup$ and $\sqcap$, bottom element $\bot$ and top element $\top$). I call a boolean funcoid a ...
1k views

Show that $\{\lnot,\leftrightarrow\}$ is not functional complete

I have to prove that this set of logical operators is not functional complete - $$\{\lnot,\leftrightarrow\}$$ i've tried implement this set by $\{\rightarrow,\lor\}$ which is not functional ...
60 views

simplify boolean expression: xy + xy'z + x'yz'

As stated in the title, I'm trying to simplify the following expression: $xy + xy'z + x'yz'$ I've only gotten as far as step 3: $xy + xy'z + x'yz'$ $=x(y+y’z) + x’(yz’)$ $=x(y+y’z)+x(y’+z)$ But I ...
44 views

What is the symbol you'd use for Boolean results?

What I mean is that $\mathbb{CRZ}$ etc. are used for different classes of numbers, allowing me to do stuff like this: $$f:\mathbb{R}\to\mathbb{R}$$ $$f:x\mapsto 3x$$ But say I have an expression ...
1k views

Is this *really* a categorical approach to *integration*?

Here's an article by Reinhard Börger I found recently whose title and content, prima facie, seem quite exciting to me, given my misadventures lately (like this and this); it's called, "A Categorical ...
21k views

Is XOR a combination of AND and NOT operators?

I'm not sure whether this is the best place to ask this, but is the XOR binary operator a combination of AND+NOT operators?
4k 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 ...
5k views

122 views

Are there further transformation principles similar to the Inclusion-Exclusion Principle (IEP)?

This question is motivated by the elaboration of the question Combinatorial Proof of Inclusion-Exclusion Principle (IEP). Let's consider the following two aspects: 1.) IEP transforms at least ...
192 views

The sum of a polynomial over a boolean affine subcube

Let $P:\mathbb{Z}_2^n\to\mathbb{Z}_2$ be a polynomial of degree $k$ over the boolean cube. An affine subcube inside $\mathbb{Z}_2^n$ is defined by a basis of $k+1$ linearly independent vectors and an ...
385 views

How to write boolean expressions as linear equations

I want to convert a set of boolean expressions to linear equations. In some cases, this is easy. For example, suppose $a, b, c$ $\in$ {0,1}. Then if the boolean expression is: $a$ $\ne$ b, I could use ...
8k views

self dual boolean function

How many self-dual Boolean functions of n variables are there?Please help me how to calculate such like problems. A Boolean function $f_1^D$ is said to be the dual of another Boolean function $f_1$...
148 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 ...
250 views

Proving that a set with a ternary logical connective is functionally incomplete (i.e. inadequate)

I am stucked at trying to prove that the set $\{\lnot ,G\}$ of logical connectives is inadequate where $G$ is a ternary connective that gives $T$ (True) if most of its arguments are $T$. For example: ...
167 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 ...
171 views

Is Belnap's four valued-logic a boolean algebra?

Belnap's logic contains the the truth values 'true' (t), 'false' (f), 'unknown' ($\bot$) and 'paradox' (T). Each of these is represented by pair a of bits: t $\rightarrow$ (1,0) f $\rightarrow$ (0,1) ...
42 views

70 views

How to Solve Boolean Matrix System?

I have a Boolean Matrix System (BMS) as described below $$Ax=c$$ where $A$ is a $n\times n$ Boolean matrix (i.e., all entries are either 0 or 1), $c$ and $x$ are two $n$-dimensional Boolean column ...
1k views

258 views

Hi I've been working through Applied Mathematics for Database Professionals and I'm stuck trying to proof this equivalence: $$(P\Leftrightarrow Q)\Leftrightarrow((P\Rightarrow Q)\wedge (Q\... 3answers 24k views Boolean Simplification of A'B'C'+AB'C'+ABC' My question is how do I reduce \bar A\bar B\bar C+A\bar B\bar C+AB\bar C To get (A+\bar B)\bar C. I'm so lost just been trying to get it for awhile only using the 10 boolean simplification rules. 1answer 129 views A boolean algebra is complete if its stone space is extremally disconnected I have the following proof, but I don't understand one of the steps: Theorem 4.4. A Boolean algebra is complete iff its Stone space is exlremally disconnected. Proof. Identify the given ... 0answers 186 views Coproducts and pushouts of Boolean algebras and Heyting algebras I am having trouble of find a reference explaining how to compute coproduts and pushouts in the category of Boolean algebras and in the category of Heyting algebras. To be precise I am looking for ... 2answers 259 views How to prove that (A \lor B) \land (\lnot A \lor B) = B I know this is fairly basic, and I understand that it becomes$$ \begin{align} (A \land \lnot A) \lor B \\ F \lor B \\ B \end{align}  However, I can't work out how to prove that it becomes that ...
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) \...