Questions tagged [boolean-algebra]

Boolean algebras are structures which behave similar to a power set with complement, intersection and union. Use this tag for questions about Boolean algebras as structures, or about functions defined from/to Boolean algebras. For Boolean logic use the tag propositional-calculus.

0
votes
1answer
42 views

Get the non-overlapping area of two overlapping squares represented as two squares.

We have two rectangles. These are represented by coordinate pairs at the bottom-left (L) and top-right coordinates (R). In the following diagram, the second rect is translated x+ and y+, but the shape ...
0
votes
0answers
64 views

1+AB=1 using boolean algebra ? Am I right or not?

As 1+AB Now if I put A=0 & B=1 then the above expression gives the answer 1 Conversely if I put A=1 & B=0 then again the answer of above expression is 1 I've seen manly rules or laws to ...
0
votes
0answers
18 views

Exact requirements for the redundancy theorem

I've encounter a few formats which the redundancy theorem could be applied to. Such as, $B$$C$$A$$+$$\overline{A}$$+$$\overline{C}$$+$$\overline{B}$ $C$$B$$+$$B$$A$$C$$+$$\overline{A}$ $B$$C$$+$$\...
0
votes
1answer
28 views

Is there a term for a boolean expression that only consists of atoms, negations of atoms, and a single unique logical operator?

For example: $a \vee b \vee c \vee \neg d$ $a \land \neg b \land \neg c \land d$ these could be described using the term I'm looking for. The following, however, could not be: $(a \vee b) \land (c ...
0
votes
1answer
38 views

Prove this A∆B=C <=> B∆C=A [duplicate]

$A∆B=C <=> B∆A=C$ I don't idea. Is this correct task? Maybe the <=> means something else i don't know?
-1
votes
1answer
52 views

Complicated index models and Boolean algebras/ Shelah/ Unclear step in the proof

Here on the page $10$ in the $5$th line (the proof of lemma $1.10$), Shelah defines $n_*$ as $\omega$: $$n_*=\omega,$$ and then he continues: be such that $n_*\geq\text{max}\{n(0),...,n(m-1)\}<\...
0
votes
1answer
42 views

$\omega$ , modulo operation, Boolean algebras

In this paper of Shelah on the page 6 in the -3rd line, what it means $$\bigwedge_{i<\kappa}h(i)=i \text{ mod } \omega$$? I just do not understand the notation.
1
vote
2answers
27 views

Let $A$ be a Boolean algebra and $F\subseteq A$ be a filter on $A$. Why are the following properties equivalent?

Let $\mathcal{A}$ be a Boolean algebra and $F\subseteq \mathcal{A}$ be a filter on $\mathcal{A}$. Why are the following properties equivalent? $$(1)\,\,\,A\land B\in F\Rightarrow A,B\in F$$ $$(2)\,\,\...
2
votes
1answer
29 views

Countably closed ultrafilters on incomplete Boolean algebras

Suppose that $B$ is a Boolean algebra. Say that an ultrafilter, $U$, on $B$ is countably closed iff whenever $X\subseteq U$ is countable and the meet $\bigwedge X$ exists, $\bigwedge X\in U$. I ...
1
vote
1answer
46 views

Characterization of zero-dimensional frames via lattices of ideals

My question concerns the left-to-right implication of the following: Theorem A frame $L$ is compact and zero-dimensional iff it is isomorphic to the lattice of ideals $\mathcal{I}(B)$ of some Boolean ...
0
votes
4answers
25 views

Using the replacement laws to prove that ($a \to $b) $\vee$ ($a \to $c) = $a \to ($b $\vee$ c)

I have been asked to prove that ($a \to $b) $\vee$ ($a \to $c) = $a \to ($b $\vee$ c). I believe it is just the simple case of using the distributive law: $a \wedge ($b $\vee$ c)= (a $\wedge c) \...
1
vote
1answer
80 views

Category theoretic proof of Stone's representation theorem

Can Stone's representation theorem about Boolean algebras that every Boolean algebra $B$ is isomorphic to the algebra of clopen subsets of its Stone space $S(B)$, be proven categorically using Yoneda ...
0
votes
1answer
31 views

Intersection and conditioned set

I don't understand why if it's true that $P(A\cap B|C)=P(A|C)\cdot P(B|C)$ (formula, moreover, used in a number of exercises), in this case he writes:
0
votes
0answers
14 views

Minimal boolean representation of an AND via two-input NOR

Let $x_1,x_2,x_3,x_4$ be boolean variables (i.e $x_i \in \{0,1\}$) Consider $f(x_1,x_2,x_3,x_4) = x_1 \wedge x_2 \wedge x_3 \wedge x_4 $ I want to write $f$ in terms of two-input NOR gates. I.e, $\...
0
votes
1answer
40 views

how do I simplify this particular boolean expression?

so I have spent nearly 5 hours trying to simplify this particular expression but I keep going round and round in circles. I have my hard copy notes to show you where I scribbled for hours and hours to ...
0
votes
1answer
179 views

Representation of 3-queens problem as boolean expression for SAT solver

The nxn queens problem is if the is a solution where n queens can exists on a nxn board with the rules of chess, 1 per row,col,diagonal. I am trying to represent the nxn queens problem where n=3 in ...
0
votes
1answer
33 views
2
votes
1answer
127 views

What is the “official” name for these boolean algebra rules?

In boolean algebra, we have the following simplification rules: $$P + (\ldots P \ldots) = P + (\ldots 0 \ldots)$$ and $$P \cdot (\ldots P \ldots) = P \cdot (\ldots 1 \ldots)$$ (Here $\;\ldots P \...
2
votes
4answers
69 views

Where does this rule for Boolean simplification come from?

In the simplification: $$\begin{align}A'BC + AB'C + ABC \\ BC(A' + A) + AB'C \\ BC + AB'C \\ \color{red}{C(B + AB')} \\ \color{blue}{C(B + A)} \\ AC + BC\end{align}$$ What is the rule that permits ...
4
votes
1answer
69 views

Stone representation of the free $\sigma$-algebra on $\omega_1$ free generators

Let $A$ be the free Boolean algebra on $\omega$ free generators. Then $A$ is isomorphic to the field of clopen subsets of the Cantor space $2^\omega$, which is the Stone space of $A$. Let $B$ be the ...
-2
votes
4answers
62 views

boolean algebra simple question

Simplfy : $$ (x+y)\cdot(x+yz) $$ I have tried to solve the question through by evaluating the expressions $x(x+y)$ and $yz(x+y)$ but I didn't get the right answer which is: $$ (x+y)\cdot(x+yz)=x + ...
0
votes
1answer
69 views

Shall we call this relation an “isomorphism”?

This is a short question: Assume the values: $\mathbf{True}$, $\mathbf{False}$ and the logic symbols: $\land,\lor$ Is $\mathbf{True}$, $\mathbf{False}$ under $\land,\lor \,$ isomorphic to $\...
0
votes
1answer
48 views

Boolean algebra - prove $x_1 = x_2$

I'm trying to prove that two boolean algebra expressions are equivalent: $x_1 = a'b'c + bc' + ac + ab'c$ $x_2 = b'c + bc’ + ab$ I got up to here: LHS $a'b'c + bc' + ac + ab'c$ RHS $= (a + a')c +...
0
votes
0answers
28 views

Proving boolean equivalence formula

$$ x\oplus18 = ((x \lor \neg44) \land (x \oplus 62)) + (x \land 44) $$ whereas $(\land, \lor, \oplus)$ correspond to bitwise operations over Boolean algebra ($B^n, \land , \lor, \neg)$ and arithmetic ...
-2
votes
2answers
38 views

logic - how to convert this formula

I have this formula: $$(X \wedge (Y \rightarrow Z)) \vee \neg(\neg X \rightarrow (Y \rightarrow Z))$$ Is it possible to convert it to this: $$X ↔ (Y → Z)$$ the truth table show that they are ...
-1
votes
1answer
31 views

Formula to get result as $0$ for a variable assigned as $1$.

I actually want to perform bitwise not operating in normal calculation mode in my Casio fx-991 ex. I want a formula which consists of one variable, which can be assigned with either $0$ or $1$. The ...
1
vote
0answers
29 views

Boolean algebra homomorphisms with adjoints

I'm interested in a particular class of maps between boolean algebras: the homomorphisms $f:A\to B$ such that there exist functions (not necessarily homomorphisms) $u,d:B\to A$ such that $$f(a)\leq b\...
0
votes
3answers
38 views

Why is $ (a \lor b \lor c) \oplus ( a \lor b)$ equivalent to $\lnot a \land \lnot b \land c$?

I'm having a hard time understanding why $(a \lor b \lor c) \oplus (a \lor b)$ (where $\oplus$ stands for XOR) is equivalent to $\lnot a \land \lnot b \land c$ in propositional logic. Any help would ...
0
votes
2answers
45 views

Boolean Identity: (x + yx) = (x + y)(x + z) what is z

In the boolean Identity: (x + yx) = (x + y)(x + z) Where does z come from and what does it mean?
-1
votes
1answer
26 views

How do i prove this equality using boolean algebra?

$x'yx' + (x' + y')' = y''y$ I don't know how to prove this to be true? Any help would be truly appreciated!
0
votes
1answer
44 views

Disprove universal gate of the following function: $F(x,y)=(x+y')'$

Prove that the following function: $F(x,y)=(x+y')'$ can not be a universal gate. I believe that 'Not' can not be represented using this function (by trying many combinations). How ...
1
vote
1answer
60 views

Is the equational theory of generalized boolean algebras decidable?

One can easily check by using truth tables whether a propositional formula is a logical identity. Thus, the theory of Boolean algebras is decidable. But a generalized Boolean algebra (GBA), i.e. a ...
0
votes
1answer
121 views

Prove that set $\{\wedge, \vee \}$ is not functionally complete

How to prove that set $\{\wedge, \vee \}$ is not functional complete? I tried to do it like this, I tried to show that $\neg x$ couldnt be received by $\wedge$ and $\vee$. I take function $\neg x = \...
0
votes
0answers
21 views

Boolean (partial) eigenvectors

First of all, I hope this isn't a stupid question but I wasn't sure how to even Google what I wanted to ask. I am asking this in the context of boolean vectors and operators of the form $A:\{0,1\}^N ...
0
votes
1answer
193 views

Simple proof XOR with 0,1 is not universal

$XOR(x,y)=x'y+xy'$ and so $XOR(x,1)=x'=NOT(x)$. Howver $XOR$ cannot create $AND(x,y)$. Is there simple proof of this? We are allowed $XOR$ gate and $0,1$ constants.
0
votes
1answer
44 views

(Blackburn's book) Question regarding a lemma about ultrafilter extension

I am reading the proof of: Let $\tau$ be a modal similarity type, and M a $\tau$-model. Then, for any formula $\phi$ and any ultrafilter $u$ over $W$, $V (\phi)\in u$ iff $ue(M),u\Vdash \phi$. $ue(M)$...
1
vote
1answer
18 views

Existence of a finite almost-non-contradicting triple

Define an n-variable propositional formula as a function $f: \lbrace{0,1 \rbrace}^n \rightarrow \lbrace 0,1 \rbrace$. A function $f$ is a contradiction if it maps all it's inputs to false ($0$ in this ...
0
votes
2answers
167 views

Proof that $a + 1 = 1$ (Boolean algebra)

The proof works like this: $$a + 1 = (a + 1) * 1 = (a + 1) * (a + \lnot a) = a + (1 * \lnot a) = a + \lnot a = 1$$ It only uses the axioms of Boolean algebra. I understand every step besides the ...
1
vote
1answer
30 views

Ultrafilters preserving infinite joins

A filter $U$ over a boolean algebra $A$ (isomorphic to a powerset algebra) "preserves" a join $a = \bigcup_{i\in I}a_i$, if $a\in U$ implies $a_i\in U$ for some $i\in I$. A join $a$ is infinite if $I$ ...
6
votes
2answers
112 views

Are there products in the category of $\sigma$-algebras and (reversed) $\sigma$-homomorphisms?

Let $\mathcal{A}$ be a $\sigma$-algebra on a set $X$, and $\mathcal{B}$ be a $\sigma$-algebra on a set $Y$. A map $h\colon\mathcal{B}\to\mathcal{A}$ is called a $\sigma$-homomorphism if $h(\emptyset)=\...
1
vote
1answer
769 views

Simplify ABC+AB'C+A'BC+A'B'C+A'B'C'

ABC+AB'C+A'BC+A'B'C+A'B'C', AC + A'BC + A'B'C + A'B'C', C(A+A'B+A'B') + A'B'C', C(A + A'(B+B') + A'B'C', C ( A + A') + A'B'C', C + A'B'C', but true answer is C+A'B. Help me, what I missed?
0
votes
5answers
131 views

Starting with a false statement, how can one prove anything is true? [duplicate]

So I've been learning a bit of logic for class and heard that if you begin with a false statement, you can then prove anything to be true, however I don't entirely understand what this means or how to ...
2
votes
1answer
49 views

Is there a $\sigma$-complete homomorphism of $\sigma$-algebras that is not generated by a function on underlying sets?

Let $\mathcal{A},\mathcal{B}\,$ be $\sigma$-algebras on sets $X,Y$, respectively. A mapping $h\colon\mathcal{A}\to\mathcal{B}\,$ is called a $\sigma$-complete homomorphism if $h(\emptyset)=\emptyset$, ...
1
vote
2answers
61 views

It it possible to express an always-true function using product of sums in boolean algebra?

Consider such boolean function: $$f(x,y,z) = 1$$ It is easy, but a trifle tedious, to express this function using the sum of products. However, let's say that we are asked to express it using the ...
1
vote
2answers
63 views

Translating Predicate Logic to English

$E(x,y)$: $x$ can eat $y$ $L(x,y)$: $x$ loves eating $y$ $D$ is the domain of all dogs $S$ is the domain of all snakes Predicate Logic to English:             &...
0
votes
2answers
179 views

Boolean Algebra simplify problem

I am reading a section on Boolean algebra in a text book and trying to understand a solution to simplifying problem they have presented.the expression $$(¬p ∧ ¬q ∨ p)$$ is simplified to $$(¬q ∧ p).$...
3
votes
0answers
41 views

I dont see how its possible to explain why these logical connectives is adequate

"Explain why {$\wedge$, $\perp$} is adequate". I translate this to: Show how to construct {$\vee$, $\implies$, $\neg$} using only {$\wedge$, $\perp$}. I know that I can show this by comparing truth ...
0
votes
1answer
54 views

Representation of free sigma-algebras

In his Lectures on Boolean Algebras, Halmos states the following theorem (p. 102): Theorem 14 For every set $I$, there exists a free $\sigma$-algebra generated by $I$, and, in fact, that algebra is ...
3
votes
2answers
53 views

The lattice of annihilator ideals of a ring

The question is about an exercise from the book "Lattice-ordered rings and modules" from Stuart A. Steingberg. This is the exercise 7 from chapter 1, section 2. Let $R$ a ring with no nonzero ...
0
votes
0answers
21 views

How should I consider signals with thresholds when reducing Boolean expressions?

Let's say I have a simple logic circuit comprised of three signals (A, B, and C) that go through two AND gates and one OR gate as follows: $$Q = (AC)+(BC)$$ But C will have different thresholds ...