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

learn more… | top users | synonyms

1
vote
0answers
14 views

Tests for combinational logic - product of sums simplification

I am trying to understand how to simplify the Boolean cover function $(4+6)(12+14)(0+1+2+3)(11)(3)(9)(13)(10+14)(1+3+9)$ which is a stuck-at fault test cover function derived in this paper. I know ...
0
votes
1answer
33 views

Simplify a Boolean Algebra expression with don't cares

In my homework assignment, I'm asked to simplify an expression of Q'RS'T' + Q'R'S'T + RS'T with don't-cares of m3, m12, and m14. I know how I would achieve this result with a K-map, however the ...
2
votes
1answer
35 views

Solving $n$-binary-variable system of equations using only combinations of $n \over 2$ variables when $n \over 2$ is even

It seems that it's impossible to find the unique solution to an $n$-binary-variable system of XOR equations if you only use all $(n \text{ choose } {n \over 2})$ equations combining half the variables,...
0
votes
0answers
49 views

Boolean function analysis on random graphs?

Random graphs have some properties that are determined in some random way such as edge probabilities in the interval $[0,1]$. Ryan O'Donnell's book "Analysis of Boolean Functions" (2014) has analysis ...
1
vote
1answer
38 views

necessity of $f(0)=0$ and $f(1)=1$ in homomorphisms of boolean algebras

Let $A,B$ be boolean algebras and let $f \colon A \rightarrow B$. $f$ is a homomorphism of boolean algebras if $f$ is a homomorphism of the corresponding lattices and $f(0)=0$ and $f(1)=1$. Why is it ...
0
votes
0answers
12 views

Pseudo-Boolean functions restricted to integers

The Pseudo-Boolean functions are of the following form. $$ f : \mathbb{B}^n \to \mathbb{R} $$ I would like to know if there is a special sub-category of $$ f : \mathbb{B}^n \to \mathbb{Z} $$ with ...
1
vote
1answer
59 views

Are all algebras groups?

It seemed to me that boolean algebra is a group because it is closed (You can't use boolean algebra and get a result that is outside the group) under a logical primitive(?) and order of operands and ...
1
vote
1answer
35 views

Boolean Algebra laws of deduction question

I have a question in which I'm a little stuck at answering, could anyone help? ...
0
votes
1answer
28 views

Want to check if my Boolean Algebra simplification is correct

$(A+B)(B+\bar B)(\bar B+C)$ Distributive LAW $(AB+A \bar B+B B+B \bar B)(\bar B+C)$ Distributive LAW $(A B \bar B+A B C+A \bar B \bar B+A \bar B C+B B \bar B+B B C+B \bar B \bar B+B \bar B C)$ ...
0
votes
0answers
12 views

finding essential prime implicants on k-map

I was given the K-map ab\cd 00 01 11 10 00.......1...0...0...0 01........1...0...0...1 11........0...0...1...0 10.......1...1....1....1 my prime implicants are ab',a'bd',acd,a'c'd',b'c'd' ...
0
votes
0answers
21 views

Quadratization of $5 x_1 x_2 − 7 x_1 x_2 x_3 x_4 + 2 x_1 x_2 x_3 x_5$ using Rosenberg's algorithm

In section 4.4 of Pseudo-Boolean Optimization by Boros et al., the authors have reproduced Rosenberg's quadratization algorithm as follows. Then they have given an example of implementing the ...
0
votes
1answer
25 views

canonical expression in compact form??

Does canonical expression in compact form need to have all the variables in it? For example, if I have a,b,c, and d variables and the compact form comes out to be just c+d, is this possible? For ...
0
votes
1answer
14 views

quick question about writing consensus theorem

In order to prove $bc + abc + bcd + a'(d+c) = abc + a'c + a'd$ I got it down to $abc + a'c + a'd + bc + bcd$ (LHS), and from there I factor out $bc$ from $bc + bcd$, which is $bc(1+d)$, simplifies ...
0
votes
1answer
38 views

Dependence of the derivative of a pseudo-Boolean function on its variables

I am going through Pseudo-Boolean optimization by Boros et al. In the section 2, the paper introduces the idea of derivative and residual of a peudo-Boolean function. It is claimed that both $\...
0
votes
0answers
10 views

Deriving minimal SOP forms from Karnaugh maps

Given the following picture, I have derived that the list of all prime implicants are a’c’d’, a’bd’, acd, ab’ and all essential prime implicants are also a’c’d’, a’bd’, acd, ab’. But I am not sure how ...
-1
votes
2answers
40 views
2
votes
1answer
27 views

Consensus Theorem and Boolean algebra

I am trying to prove the following boolean equality. $$bc + abc + bcd + a’(d+c) = abc + a’c + a’d$$ I have simplified the left side to $bc + a'd + a'c$ by factoring out a $bc(1)$. However, ...
0
votes
0answers
21 views

number of permutation in a boolean expression containing only ANDs and ORs

I need to find the number of permutations of some expression which contains only conjunctions and disjunctions e.g.: $$ e = x_1x_2 \vee x_3x_4 $$ where $x_1x_2$ and $x_3x_4$ are boolean summands, ...
-1
votes
1answer
17 views

boolean algebra with finite elements

I need to define a boolean algebra with 8 elements. I know all the Axioms to define a binary boolean algebra but I don't know how to do that with 8 elements. Someone can guide me please? Thanks.
0
votes
1answer
17 views

Boolean algebra - Maxterms

I have a boolean expression and I need to get to its canonical forms (sum of minterms and product of maxterms). In order to get an expression for the first canonical form, I need to multiply every ...
0
votes
0answers
20 views

Is there a name for a semiring in which both operations distribute over each other?

For a semiring over a set $S$, with the operations $+$ and $*$, along with respective units $0$ and $1$, we have the law: $(a + b) * c = (a * c) + (b * c)$ But there are some semirings in which the ...
0
votes
2answers
20 views

Boolean Logic using proofs

ABC' + C = AB + C I understand this using venn diagrams and intuition. However, I am not able to derive the proof for getting from one side to the other. It's probably very simple step that I keep ...
0
votes
1answer
42 views

Demonstrate AB+C(A+B)=AB+C(A⊕B)

Please help me demonstrate that AB+C(A+B)=AB+C(A'B+AB'). I've tried a couple of times but i always reach AB=2AB .
0
votes
0answers
33 views

Ideal generated by a set of polynomials $X^{a/b}$ where each monomial having $a$ and not having $b$

Let $$\mathcal R=\mathbb Z_2[x_1,\dots,x_n]/\langle x_1^2-x_1,\dots,x_n^2-x_n\rangle.$$ I want to learn ideal arithmetics to deal with polynomials of the forms such as Consider a set of ...
0
votes
0answers
34 views

Quick question on Bitwise operations

I have some questions for homework to do with Bitwise operations, now it's a simple task but it doesn't actually explain how to handle the questions which is why I'm asking here before I begin ...
1
vote
2answers
24 views

Simplify $AC'+A'C+BCD'=AC'+A'C+ABD'$

How to prove that $$AC'+A'C+BCD'=AC'+A'C+ABD'$$ approch: a way to demonstrate is expressed in its canonical form. Any hint would be appreciated.
0
votes
0answers
25 views

How can I show a set B with 8 elements and two operations, such that the axioms of huntington for boolean algebra holds?

If It was about two members I would have choose B={0,1} with the operations: AND , OR And prove this. But how can I do this with 8 elements?
-3
votes
4answers
29 views

Boolean algebra; what does <-> mean?

Expression :$$(p\rightarrow q)\leftrightarrow(\neg q\rightarrow \neg p)$$ What does the symbol $\leftrightarrow$ mean ? Please explain by drawing the truth table for this expression and also with ...
2
votes
1answer
39 views

Boolean functions that are not too far from all linear functions.

Suppose I have a Boolean function $ f:\mathbb{F}_2^n\rightarrow \mathbb{F}_2 $ which satisfies the following property: $$d(f, \ell)\leq 2^{n-1}\quad\forall\; \text{linear functions}\; \ell .$$ where ...
0
votes
1answer
21 views

Boolean Simplification $ABC' + BC'D' + BC + C'D$

I'd like to simplify this equation: $ABC' + BC'D' + BC + C'D$ prove it to $B + C'D$ My attempt is : $$\begin{align} &= ABC' + BC'D'(A+A') + BC + C'D\\ &= ABC' + ABC'D' + A'BC'D' + BC + C'D\\ ...
0
votes
1answer
22 views

Boolean expression explanation

Could someone explain how to get the following Boolean expression in its simplest form, I am having difficulties working it out step by step $$A+B+A*B$$
1
vote
1answer
27 views

Boolean functions- depth of generated function and info

I'm looking for a general book/link to information about boolean function (Function from to {0,1}), we've introduced them in a logic course but it seems we won't focus on them.
1
vote
2answers
50 views

Boolean Algebra - Prove XYZ + XYZ' + XY'Z + X'YZ = XY + XZ + YZ

Trying to prove $((X\land Y\land Z)\lor (X\land Y\land \lnot Z)\lor (X\land \lnot Y\land Z ) \lor (\lnot X\land Y\land Z)) \equiv ((X\land Y)\lor (X\land Z)\lor (Y\land Z))$ and I am a bit stuck. I ...
1
vote
4answers
36 views

Boolean Algebra - Xor simplification

I have a boolean equation: $e(g \oplus (g + b))$ and it is simplified to $e(\lnot g)b$. I do not see how this simplification is done. What i did was the following: $e(g \oplus (g + b)) --> e(g(\...
0
votes
1answer
34 views

Do we complement Boolean variables in the Dual?

The Principle of Duality states that starting with a Boolean expression, another Boolean expression can be obtained by : 1. Changing OR to AND 2. Changing AND to OR 3. Changing 0 to 1 4. Changing 1 ...
1
vote
2answers
31 views

Simplifying a Boolean algebra equation

I have a boolean algebra equation that i'm not able to simplify fully. \begin{align} &(c+ab)(d+b(a+c))\\ &(c+ab)(d+ba+bc)\\ &cd+ abc + bc^2+abd+a^2 b^2 + ab^2 c\\ &\text{using boolean ...
0
votes
1answer
20 views

Delove the truth for the three function same table

Given Boolean functions: $F(x,y,z)=x'.(y'+z')(x+y'), G(x,y,z)=x'.(z+yz')(x\oplus zy')$ Develop the truth table for the three function in the same table
3
votes
2answers
62 views

Who is Petrick from Petrick's method?

I would like to ask your help. I think this is the best place for this. In my language -as well as English- I haven't found anything about Petrick yet. His method okay, but I would like to know about ...
-2
votes
1answer
30 views

Boolean Algebra Problem [closed]

$ab+(ac)'+ab'c(ab+c) = 1$? how ?
7
votes
1answer
115 views

Existence of surjective homomorphism between Boolean algebras $\Lambda\subset\mathscr P(\mathscr B)\to\mathscr B$ (in ZF)

I am trying to prove the following theorem, due to Tarski according to W. A. J. Luxemburg on Reduced powers of the real number system and equivalents of the Hahn-Banach extension theorem: Given a ...
0
votes
0answers
35 views

Does this always evaluate to true?

This expression: $1 \lor (0 \land 1 \land 1 \land 1 \land 1 \lor 0)$ Regardless of how order of operations inside the parentheses are taken, which are ambiguous, the fact that it is and Or operation ...
0
votes
0answers
11 views

Order of Galois connections between two boolean lattices

Is the poset of Galois connections between two boolean lattices itself a boolean lattice? If not, does it hold for: complete boolean lattices? atomic boolean lattices? atomistic boolean lattices?
0
votes
0answers
97 views

Galois connections between boolean lattices - an alternative representation

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 ...
1
vote
0answers
31 views

Two alleged counterexamples (about boolean algebras)

Trying to solve this question, I propose two possible counter-examples. Please help me to understand whether these cases are really counter-examples. Let $\mathfrak{A}$ and $\mathfrak{B}$ be (fixed) ...
0
votes
1answer
16 views

More on a construction on two boolean lattices

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 ...
1
vote
1answer
23 views

Boolean lattices vs boolean rings

Which kinds of theorems about boolean algebras are easier to prove with boolean rings (than with actual boolean lattices)? Give me at least one example, as an answer.
0
votes
0answers
16 views

Counting self dual functions

The dual of a function is defined as the same function with and/or operators exchanged .A function is self dual if dual of function and function itself are same.How many maximum self dual functions ...
0
votes
1answer
27 views

Simplifying a boolean expression without using sum-of-products

Yes this is for a school class, and no I'm not asking anyone to do my homework. This is from an example. I have a boolean algebra expression that I have to simplify. I also have the answer simplified ...
1
vote
1answer
33 views

Implement boolean function with OR-NAND and NOR-OR gates

This is the boolean function: F(A,B,C,D) = Σ (0,4,8,9,10,11,12,14) and so after using a K-map to minimize it, I came out with F(A,B,C,D) = C'D' + AB' + AD'. Now the other two parts of the problem were ...
0
votes
0answers
25 views

Boolean Algebra, simplify expression

I've been trying to simply this expression but all I have managed to do is get rid of a D'. I assume there must be more I can do but I can't find out what I'm supposed to do to it. If you can help me ...