Stack Exchange Network

Stack Exchange network consists of 175 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.

0
votes
0answers
10 views

When can the order of boolean operations be exchanged? Is there an easier way?

Suppose that we have two binary boolean operators $\circ$ and $\star$ (not necessarily different). Now in general $(A\circ B) \star C = A \circ (B\star C)$ doesn't hold, but certainly sometimes it ...
0
votes
0answers
16 views

SOP simplification using mathematical method [on hold]

F = X1X2'X3' + X1X2X4 + X1X2'X3X4' How can i solve this using mathematical method?
1
vote
1answer
17 views

How can I simplify my boolean expression further

I have the following boolean expression that I want to simplify $$B\cdot D+ \overline{A\cdot B\cdot D} + \overline{B}\cdot C\cdot \overline{D}$$ Here is what I have been able to due so far $$B\...
0
votes
0answers
21 views

Finite covers of Boolean algebras

It is a student exercise that no group can be represented as a set-theoretic union of its two proper subgroups. The same also can be shown for Boolean algebras. On the other hand, it's not hard to ...
0
votes
0answers
17 views

How is it possible for a set of (algebraic normal form) monomials to have disjoint support?

We call $supp(F) = \{v \in V : F(v) = 1\}$ the support of F. Neumann, 2006, page 5. (http://www.mathematik.uni-kl.de/~dempw/Thesis/neumann.pdf) This is the standard definition of "support of a ...
0
votes
2answers
28 views

Boolean expression simplification - is my solution correct?

I have this boolean expression: (x′ ∧ y ∧ z′) ∨ (x′ ∧ z) ∨ (x ∧ y) and I simplified it using K-maps to this: (y ∧ z′) ∨ x Is my solution correct? Thanks!
0
votes
1answer
34 views

The indicator of a Boolean function

In the paper "Componentwise APNness, Walsh uniformity of APN functions and cyclic difference sets" by Claude Carlet, it is written that: Let F be any power function on $F_{2^n}$ and $\Delta _{F}=\{F(x)...
1
vote
2answers
26 views

Understanding the simplification of a boolean expression

$ABC+AB'C+A'BC+A'BC'= AB'C+A'BC+A'BC$ I was reading a book about digital systems and it said that i could supress $ABC$ because it belongs to $BC$ but i can't just look to the expression and have a ...
0
votes
1answer
25 views

Simpler sum of products from boolean algebra than from karnaugh map

I was given a question, simplify the expression represented by the sum of minterms 0,1,3 and 7 for the 3 parameter function f. Writing this out I got $f = A'B'C' + A'B'C + A'BC + ABC = A'B' + BC$. ...
0
votes
1answer
29 views

Simplify using boolean algebra laws/formulas

I am trying to learn logic expression simplification using boolean algebra laws/formulas, but I don't understand it at all. We have this expression: $ (x'\wedge y \wedge z' ) \vee (x' \wedge z) \vee (...
2
votes
0answers
62 views

Semi-rigid boolean algebras

A forcing construction I'm trying to do seems to require a complete atomless boolean algebra (used as a forcing poset) that is "semi-rigid" in the sense defined below. I'm wondering if anyone has ...
0
votes
1answer
41 views

How can I prove $p \oplus (\lnot p \land q ) \equiv p \lor q$

Having a lot of trouble with the $q$ in $p \oplus q$ being replaced with $(\lnot p \land q)$. This is for my first unit of Discrete Mathematics, but it's a bit of a curve ball. I've been picking at ...
0
votes
0answers
11 views

Fourier spectrum of a particular boolean function

I'm trying to compute the Fourier spectrum of the following boolean function, $f_q :\{0, 1\}^n \to \{\pm 1\}$, where $f_q(x) = (-1)^{q(x)}$. Above, I pick $q(x) = x_1x_2 + x_2 x_3 + \cdots + x_{n-1} ...
2
votes
1answer
21 views

Representation of sigma complete Boolean algebras

In Terrence Tao's article 245B notes 4: The Stone and Loomis-Sikorski representation theorems he gives a proof that not each sigma-complete Boolean algebra can be realized as a $\sigma$-complete ...
1
vote
1answer
32 views

Correctness of DNF representation of XOR

I'm trying to show that XOR can be written as a DNF with $2^{n-1}$ terms. Note that $\mathrm{XOR}_n(x_1, \dots, x_n) := \oplus_{k=1}^n x_k$, where $\oplus$ is addition in $\mathbf{F}_2$, and $\...
0
votes
1answer
23 views

How is boolean expression A*B + C*(A⊕B) equal to A*B + C*B + A*C

I'm having trouble trying to simplify one boolean equation into another (and visa versa). Why are these Boolean expressions, A.B + C.(A⊕B) = A.B + C.B + A.C equal? They have the same truth ...
0
votes
1answer
18 views

Using Boolean algebra, how do I convert the SOP expression listed below into A ⊕ B ⊕ C ⊕ D?

SOP expression: A'B'C'D + A'B'CD' + A'BC'D' + A'BCD + AB'C'D' + AB'CD + ABC'D + ABCD' Desired expression: A ⊕ B ⊕ C ⊕ D
0
votes
1answer
33 views

logical propositions $\left ( \left ( p\Rightarrow q \right )\Leftrightarrow p \right )\iff p \wedge q$

I have been trying to do this exercise but I can t come to the solution so I need a hint pls, i think that there is a step that i don t see (i can't use truth tables to demonstrate this). $$\left ( \...
0
votes
0answers
11 views

2-divisibility of exponential sums of boolean functions

Let $F(x_1,\ldots,x_m)$ be an A.N.F. Boolean function. Define $ S(F) = \sum_{X\in (F_2)^m}(-1)^{F(X)} $. If $C$ is a minimal set of monomials s.t. every variable appears in one of the ...
1
vote
1answer
32 views

Minimize term without Karnaugh map

I have the following term, that should get minimized with Boolean algebra (no Karnaugh map!): (a ∧ ¬b ∧ c) ∨ (a ∧ c ∧ d) ∨ (b ∧ d) I already figured out, that the minimzed term is as follows (...
0
votes
1answer
41 views

Convert Boolean function to NAND-only using De Morgan's law

I have a function that I must convert to NAND-only. I've been trying to use the De Morgan's law but, I'm getting wrong results. Here is my function: $$z = \overline{d} \overline{f}(\overline{a}ce + ...
0
votes
0answers
28 views

meaning of $←$ in propositional logic

what is the meaning of the symbol ($←$) in regards to boolean logic? Here is an example of the notation I have come across while reading about qualitative choice logic theory $$T = \{w\land s > \...
0
votes
0answers
25 views

Simplify a POS Expression

I have a boolean function, and my duty is to simplify it as much as possible. Also simplified expression must be in POS form. The expression is this : $b = (r+c+g+p)(r+c+g+p’)(r+c+g’+p)(r+c+g’+p’)(r+...
0
votes
1answer
46 views

Boolean Expression Simplification Problem

I started with a big problem and through various simplifications I've arrived at a point where I don't quite know what else to do. I've tried to further simplify but I keep running into issues. ...
0
votes
0answers
26 views

Show that the Lindenbaum-Tarski algebra is free over the set of propositional variables

Show that the Lindenbaum-Tarski algebra is free over the set of propositional variables. I was given that statement to prove. My lecturer said we need to show that any map from said set to a given ...
0
votes
2answers
38 views

Simplify boolean expression, so close but yet so far

$$F(w,x,y,z) = w'y' + w'z + x' + yz + y'z'$$ The simplest form is apparently $w'y' + x' + yz + y'z'$, but for the life of me, I cannot figure out how, no matter what trick I use.
2
votes
1answer
62 views

Tseytin transformation example

I am trying to understand Tseytin transformation and I can't really find any reliable info on the internet. I pretty much understand the steps until I get to the point I have to convert all ...
1
vote
0answers
39 views

why does a closed circuit represent a false proposition? (Claude Shannon thesis)

In reading through Claude Shannon's paper: A Symbolic Analysis of Relay and Switching Circuits. As a software engineer, I got confused by Shannon's choice to have 0 as representing a closed circuit, ...
2
votes
0answers
95 views

How many distinct subsets of binary boolean operators are closed under composition?

Question: There are $2^4=16$ distinct binary boolean operators. Two operators are regarded the same if one can be obtained from the other by exchanging the operands (input). It is easy to see only $...
0
votes
1answer
30 views

How to choose a set of boolean functions with a specified probability of getting a 1

So let's say I have a boolean function $f(x)$ that takes in a size k binary vector and outputs a binary scalar. Each function is defined as a $2^k$ vector. For example $f((0,0)) = 0, f((0,1)) = 1, f((...
6
votes
2answers
68 views

Is $P(tautology) = 1$? What are the connections between logic and probability?

It's well-known that sets are "isomorphic" to logic: if we treat $\varphi(A_1, A_2)$ as a shorthand for $\forall x: \varphi(x \in A_1, x \in A_2)$ then $A \land B \equiv A \cap B$ and $A \rightarrow B ...
-1
votes
1answer
25 views

Ordered Sets and Lattices

Recall the topic “Ordered sets and Lattices” that the set $D_m$ of divisors of $m$ is a bounded, distributive lattice with $$a+b = a\lor b =\operatorname{lcm}(a, b)$$ $$ab = a\land b =\gcd(a, b)$$ (...
0
votes
0answers
13 views

Can all the boolean expression be simplified without Karnaugh Map?

I know when Boolean expressions get too complex it is comfortable to use Karnaugh Map. But is it possible to simplify very complex Boolean expressions without this map, using just the laws?
0
votes
1answer
28 views

Is there a way to simplify of the next boolean expression?

Im trying to simplify the next expression $$A\bar{B}E+\bar{A}B\bar{E}$$ so the approach is to factor $E$ and ·$\bar{E}$ to get something like $$A\bar{B}+\bar{A}B (E+\bar{E})$$ (this step before is ...
3
votes
1answer
39 views

Opposite category of SET is Boolean Algebra

I'm reading introductory notes on category theory. While discussing the notion of opposite category, the author makes a remark that if we take opposite category of SET, that is $SET^{op}$ category, we ...
1
vote
1answer
32 views

Is it true that for a Boolean Algebra, $a'b+(abc)'+c(b'+a)=b'+c'$?

Analyze if the following statement is true or false: Suppose $(D,+,\cdot,',0,1)$ is a Boolean Algebra. Then $a'b+(abc)'+c(b'+a)=b'+c'$. My guess is that the statement is false. Let $D=D_{15}$ be the ...
0
votes
2answers
40 views

Proving uniqueness of solution in Boolean algebra

System: $a+x=1 \land a\cdot x=0$ has unique solution for x, for all values of $a \in B$. It is obvious that $x=a'$ is one solution , but how to prove the it is only one? I have tried assuming that ...
1
vote
1answer
27 views

Boolean Expression Simplification - Issue

I don't understand where to even begin with this problem. Any helpful tips would be nice. $(A \lor \lnot B \lor \lnot D) \land (\lnot B \lor C \lor D) \land (B \lor \lnot C \lor \lnot D)$
0
votes
0answers
35 views

Determine whether an integer can be constructed from other integers by applying bitwise AND and OR operations

Given binary numbers $b_1, b_2, ... , b_m < 2^n$ as well as their complements $b'_1, b'_2, ..., b'_m$ (with leading $1$'s if necessary, such that $b_i + b'_i = 2^n - 1$), is it possible to quickly ...
1
vote
2answers
35 views

Complementing a Boolean Function from Shannon's Expansion

Given a Boolean function $f: B^n \longrightarrow B$, using Shannon's expansion across variable $x$, I can write it as $f = xf_x + x^{'}f_{x^{'}}$. I want to complement $f$. Using Shannon's expansion ...
0
votes
1answer
27 views

Canonical Form Question

I have a quick question about some Boolean algebra. The problem is: F (A, B, C) = A + B And I want to expand it into canonical-sum form. The problem is there is no 'C' so I am unclear on how to ...
2
votes
1answer
25 views

Boolean expression simplification using 3 variables

(!A B !C) + (B !C !D) + (!ACD) + (!BCD) + (!ABD) = (!A B !C) + (B !C !D) + (!ACD) + (!BCD) + (!ABD)(1) = (!A B !C) + (B !C !D) + (!ACD) + (!BCD) + (!ABD)(C + !C) = (!A B !C) + (B !C !D) + (!ACD) + (...
1
vote
2answers
29 views

Boolean expression simplification - Short problem

I don't know exactly how to simply this problem. I can clearly see that (A + B) is in all of them but I don't know what to do next. (A + B + C)(A + B + !C + D)(A + B + !C + !D) -- Edit 1 -- I am ...
0
votes
2answers
25 views

Can any boolean expression with OR operators be converted to only AND operators?

I'm fairly new to Boolean algebra and I was wondering, using Boolean theorems,can any Boolean expression with an OR operators in it be converted to an equivalent expression using only AND operators? ...
2
votes
1answer
28 views

Find a homomorphism that maps a point in a Boolean algebra into the image of a proper filter

Let $\mathbb B$ be a Boolean algebra. Let $F$ be a proper filter in $\mathbb B$ (i.e. $0 \notin F$), and let $I$ be its dual ideal. Suppose there exists $a \in \mathbb B$ such that $a \notin F \cup I$....
4
votes
1answer
38 views

$\kappa$-distributivity and Stone's Representation Theorem

On page 85 of Jech's Set Theory (3rd Edition), a complete Boolean algebra $B$ is defined to be $\kappa$-distributive if \begin{equation}\label{a}\tag{1} \prod_{\alpha < \kappa}\, \sum_{i \in I_\...
2
votes
2answers
183 views

Simplify [p∧ (¬(¬p v q)) ] v (p ∧ q) so that it become p, q, ¬p, or ¬q

Had a question on a test that asked for us to simplify (using rules of inference) the following proposition: [p∧ (¬(¬p v q)) ] v (p ∧ q) to p, q, or their negation (¬p, ¬q). Here is what I did: 1) [p∧...
1
vote
2answers
41 views

How to automatically create proofs in Boolean Algebra

Given a complete set of axioms (for example, associativity, communtative, distributivity, identity, annihilator, idepotence, and the "complementation" laws) for boolean algebra, I know any other true ...
0
votes
0answers
18 views

How do I derive the NOR expression of x'yz' + xy' + z using K-Maps?

How would I derive NOR boolean expression of this using K-maps? I know you can do it algebraically but I want to know how to do it using K-maps.
1
vote
1answer
23 views

Divisibility represented by Boolean logic

Some context: I was thinking about the feasibility of using SAT solvers to prove primality, especially of Mersenne primes, by showing that there exists no Boolean sequence $d_1,d_2, ..., d_{b'}$ that ...