Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
2answers
52 views

How Does $AB{\sim} C + {\sim}ABC + {\sim} A {\sim}B{\sim} C$ Turn into $(A+C+{\sim}B)(B+{\sim}A)(B+{\sim} C)({\sim} A+{\sim} C)$?

I'm trying to figure out this Boolean algebra question and I cannot for the life of me figure it out. I know that the answer is $(A+C+{\sim} B)(B+{\sim}A)(B+{\sim} C)({\sim} A+ {\sim} C)$ but I can't ...
0
votes
3answers
56 views

Showing that (A⊕B)⊕B is equal to A

I found this solution somewhat incomplete in a video I was watching. Here's the image and video (solution starts at ~2:11). Here's what he wrote: (A⊕B)⊕B=A ⇒ x∈(A⊕B)⊕B = x∈(A⊕B) xor x∈B = (x∈A ...
-3
votes
0answers
20 views

Boolean expression need help 1 [on hold]

a'bc+ab'c'+a'b'c'+ab'c+abc need help please
-2
votes
1answer
21 views

Boolean expression need help [on hold]

(ab+ac)'+a'b'c' How to solve this.. I am stuck
-2
votes
1answer
29 views

if $a'b+cd'=0$, then prove that $ab+c'(a'+d')=ab+bd+b'd'+a'c'd$

Let $a'b+cd'=0$, then prove that $$ab+c'(a'+d')=ab+bd+b'd'+a'c'd$$ I would like to know how to solve this expression, not able to make any headway. I have tried canonical form expansion and reduction ...
0
votes
1answer
30 views

If $t \leq s$ and $t \neq s$, why $t' \land s \neq 0$

In boolean algebra, why if $t \leq s$ and $t \neq s$, why $t' \land s \neq 0$, where ' is the complement. I see it if I use that all boolean algebras are $\{0,1\}^n$ but I want to have a proof using ...
1
vote
2answers
21 views

Finding the simplest circuit formula for this boolean logic statement

I have a boolean logic statement: boolean logic statement I get the truth table to derive the statement: truth table derived statement: (-A^-B^C) V (-A^B^-C) V (-A^B^C) V (A^-B^C) V (A^B^C) But ...
0
votes
0answers
13 views

Specify a unitary matrix for a function

I have a negation function (for bits) that maps a 0 to a 1 and a 1 to a 0. If you translate this into a matrix, it's like this: \begin{pmatrix}0&1\\1&0\end{pmatrix} Now this function is ...
0
votes
1answer
14 views

Can there be prime implicants or essential prime implicants of SOP form?

I had got a following question let $f(A,B,C,D)=Π(2,3,5,9,11,12,13)$. The total number of prime implicants and essential prime implicants are denoted by P and Q respectively. What is the value Q%P ...
0
votes
2answers
32 views

What determines an identity in Boolean algebra?

I'm a newbie to probability theory and am currently working through Chapter 1 of Jaynes' "Probability Theory, The Logic of Science". In it, he introduces the Boolean algebra and a number of identities ...
0
votes
1answer
32 views

Interpolating/estimating f on subset of integers

Here is the question I have been struggling to solve lately. Imagine we have two integers $x, y \in \mathbb Z, x \le y$ and $Y = \{ a | a \in \mathbb Z\ and\ x \le a \le y \}$; $X\subset Y$. In the ...
-1
votes
1answer
44 views

“nothing” in boolean algebra

Is there formal notation for saying "there is no x for which P(x)" or is it simply something like $( \neg \exists x) P(x)$?
-1
votes
0answers
40 views

How does a'bc+ab'c'+ab'c+abc' become (a xor bc)

I'm trying to simplify (a'bc + ab'c' + ab'c + abc') this expression which should be (a xor bc) but I don't understand how to go beyond (a'bc + ab' + ac')
0
votes
1answer
18 views

Determining elements of a Boolean algebra by a set of ultrafilters

Let $A$ be a Boolean algebra and let $Ult(A)$ be its Stone space. Let us say that a set $U\subseteq Ult(A)$ determines an element $a\in A$ if there exists $V\subseteq U$ such that $$\big\{b\in A\!: (\...
1
vote
1answer
54 views

Proof: $U$ is an ultrafilter of a Boolean algebra $B$ if and only if for all $x$ in $U$ exactly one of $x$,$x^*$ belongs to $U$.

I have been stuck with this problem for a while now. I have a proof that letting $U$ be an ultrafilter, exactly one of $x,x^*$ belongs to $U$ for all $x$ in $B$, I did this by showing that both belong ...
-1
votes
0answers
28 views

Principal Disjunctive form of the following

I have to calculate the PDNF and PCNF of the following expression $$(P \longleftrightarrow Q) \longleftrightarrow (P \longleftrightarrow Q)$$ As it is a tautology so it will only have PDNF. I'm ...
0
votes
1answer
44 views

Is there always true predicate? [closed]

Is there such predicate $P(x)$ where the statement is always true, for whatever the $x$ is?
2
votes
0answers
28 views

Given a Boolean function, decide if it can be implemented only with the $\mathrm{AND}$, $\mathrm{OR}$, and $\mathrm{NOT}$ gates

True or false? Prove or justify, respectively. "Given $$f(x,y,z)=x\cdot z+\overline y\cdot\overline{z+\overline x}$$ can be implemented in a circuit formed only by an $\mathrm{AND}$ gate, an $\mathrm{...
0
votes
0answers
56 views

Boolean algebras/Unknown notation

Does someone know what is meant (in the context of trees and Boolean algebras by Shelah) here on the page 8 right above Remark 1.5: $$\{\langle\rangle\}\cup\{\langle\xi\rangle\otimes_{\zeta(*)}d\eta:\...
1
vote
1answer
30 views

Equivalent properties of a proper ideal of a generalized boolean algebra

I do not understand the item c) of the following question, the exercise 9 from section 1.2 from the book "Lattice-ordered Rings and Modules" from Stuart A. Steinberg: A generalized boolean algebra is ...
1
vote
0answers
26 views

Boolean algebra and closure axiom

A Boolean algebra is an algebraic system (B,$∨$,$∧$,$¬$), where $∨$ and $∧$ are binary, and $¬$ is a unary operation. One of the Boolean algebra axiom is: If $a$ and $b$ are elements of $B$, then $(a ...
2
votes
2answers
88 views

Reason why addition and multiplication are both required - unlike boolean algebra where NOR is enough?

Apologies for the simplicity of this question. In Boolean Algebra the introduction of the function {NOR} is sufficient to create, with suitable finite combinations of this function, all possible sets ...
0
votes
1answer
27 views

Solving this equation to be 3 literals

I am trying to solve this to be 3 literals, but I keep getting errors: Question:$(x'y' + z)' + z + xy + wz$ My answer: $(x+y)z' + xy + z(1+w)\implies xz' + yz' + xy + z\implies zx + zz' + yz' + xy$ ...
0
votes
0answers
39 views

Is this a Boolean algebra? (proof)

Let $B=\{0,1\}$ and the binary operations $\oplus,\cdot$ We define a bijection $\varphi$ s.t.: $$ \varphi:B \longrightarrow L=\{\mathbf{False},\mathbf{True}\}, $$ $$ \varphi(x):= \begin{cases} \...
0
votes
1answer
60 views

How to solve a system of equations written using XOR? [closed]

How to solve a bunch of linear equations written like:- AXORBXORC=a BXORC...
1
vote
0answers
40 views

Why there are rarely any further discussion on Boolean lattice in topology and algebra?

Here is the definition for Boolean lattice, or Boolean algebra. I've seen several results about how one can represent a Boolean lattice from a certain structure, or to verify a Boolean lattice can be ...
1
vote
0answers
44 views

Relative consistency of ZF with respect to IZF

Is there a forcing argument of this fact? Can anybody point me to the place? The reason I'm asking is because I was reading Heyting-Valued Models for Intuitionistic Set Theory by R.J. Grayson, yet ...
1
vote
0answers
26 views

How to prove de Vries algebras morphisms are dense and full if their duals are into ?

Well, this is a quite short question but I think it will require some explainations. Let's say that a de Vries (or compingent) algebra is a Boolean algebra $B=(B,0,1, \wedge, \vee, \neg) $ with a ...
0
votes
2answers
59 views

Show $p \lor (p \land q ) \equiv p $ using equivalences

I am trying to show $p \lor (p \land q ) \equiv p $ using equivalences. I have tried many replacements (e.g. distributivity and de Morgans) but cannot see a way to simplify the left hand side that ...
2
votes
1answer
22 views

Help with boolean algebra simplification and equivalent

I have the following boolean expression: See number 5 and 7 What I have trouble with are the actual steps of simplification using the boolean algebra laws for number 5 and 7 . I'm probably missing ...
1
vote
0answers
32 views

Representation of chained XOR operation as a set of linear inequalities

I'm trying to solve an integer linear program (ILP) in which a constraint of the following kind must be met: $x_1 \oplus x_2 \oplus \cdots \oplus x_n = 1$ where $\oplus$ is the binary xor operator. ...
0
votes
0answers
19 views

boolean logic minimization

Two level boolean logic minimization(AND, OR, NOT) for big number of variables,(say n) is time-consuming. I want to minimize an n variable sum of Product form boolean expression efficiently where n ...
2
votes
1answer
45 views

Proving associativity of a certain binary aperation in any complemented distributive lattice

If, in a Boolean lattice $(X,\vee,\wedge,0,1,')$ (i.e. a complemented distributive lattice), we define $x+y=(x'\wedge y)\vee(x\wedge y')$, is there an elegant way to prove that $(x+y)+z=x+(y+z)$ ...
0
votes
0answers
30 views

About isomorphic of a boolean algebra to bolean algebra

Let $\mathcal A$ be a boolean algebra. It`s non-empty subset $\mathcal F$ is called a filter if $∅ \notin \mathcal F$, for all $A ∈ \mathcal A$, $B ∈ \mathcal F$ from $B ⊂ A$ follows $A ∈ \mathcal F$, ...
1
vote
1answer
31 views

Help with boolean algebra simplification.

I had the following boolean expression: $$(C\lor D)\land({\sim} B\lor D)\land({\sim} A\lor {\sim} C\lor {\sim} D)$$ I know this can be simplified to: $$(C\land{\sim}B\land{\sim} D)\lor(D\land{\sim} A)...
1
vote
1answer
22 views

how to use Shannon-expansion to rewrite Logic to Normal if-then-else Form (INF)

I'm taking a (online) course in logic, one goal of the course is to rewrite logic expressions to if-then-else form, using shannon-expansion, the following is a text-book example: we got: ...
0
votes
1answer
30 views

I need help in simplifying a Boolean expression.

My starting point was (A+D)*(A+B+C)*(~A+C+~D) And I should end at ~A*B*D +A*~D +C*D (according to online solvers.) But when I ...
2
votes
1answer
20 views

Prove that either $a\leq x$ or $a\leq -x$ if and only if $a$ is an atom.

Let $(\mathbb{B},\wedge,\vee,-,0,1,\leq)$ be a Boolean algebra. I wish to prove the following: Claim: $a$ is an atom if and only if for each $x\in\mathbb{B}$ either $a\leq -x$, or $a\leq x$ (...
0
votes
2answers
30 views

Showing $a \setminus (a \setminus b) = a \cap b$ using only set notation.

I need to prove that $a \setminus (a \setminus b) = a \cap b$ only through set notations. I have reached the fact that $a \setminus (a \setminus b)$ = {x | x $\in$ A $\land$ x $\notin$ (A $\setminus$...
0
votes
1answer
20 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
39 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
15 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
27 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
33 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
21 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
22 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 ...
0
votes
1answer
23 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
24 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) \...