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

2
votes
0answers
21 views

Is every quotient algebra of a Boolean algebra isomorphic to a subalgebra?

Is every (non-trivial) quotient of a Boolean algebra isomorphic to a subalgebra of that Boolean algebra? And conversely is every subalgebra isomorphic to a quotient algebra?
0
votes
1answer
28 views

What is this product called?

Let $X$ be a finite set and let $2^X$ be its power set. Let $Z$ be some ring (e.g. the complex numbers; it doesn't matter). Suppose $f:2^X\to Z$ and $g:2^X\to Z$ are two functions from $2^X$ to $Z$. ...
0
votes
1answer
106 views

Can $P(\omega)$ be superatomic?

A Boolean algebra is superatomic if its every subalgebra has an atom. I'm trying to determine whether $P(\omega)$, i.e. the power set algebra of the set of all natural numbers (finite ordinals) ...
0
votes
1answer
15 views

Confirmation of an answer of a question on Boolean Algebra

Here are the solution I have worked out. Is it correct? Given $C + BC'$: $C + B' + C'$ $C + (B'+C')'$ $C + B + C$ $C (C + B + C)$. Is the answer (2)?
0
votes
0answers
18 views

How to find standard product of sums?

I have came across an exercise in book to find the standard product of sums with the following function: F(A,B,C,D,E,F) = (A + BC'+ CD) (B' + EF) Here's my approach to solve it: Step 1: [ (A + B) ...
0
votes
3answers
34 views

Boolean Algebra Simplication $(A+B)(A+C)$ [on hold]

Answer is $AA + AC + AB + BC$ Is the answer wrong? It should be $AA + AB + BA + BC$ right?
4
votes
1answer
134 views

$\vDash \varphi$ iff $\| \varphi \|_A =1$ for every boolean valued structure $A$

In the book Axiomatic Set Theory (Takeuti, G; Zaring, W.M. - 1973) the theorem 6.4 states that if $\varphi$ is a closed formula of a given language then it is satisfied in every boolean valued ...
0
votes
1answer
13 views

Reducing a Boolean function

I have the following boolean function: f(x,y,z) = xyz + xyz' + xy'z + x'yz + xy'z' I could reduce it to the following: f(x,y,z) = xy + xy'z + x'yz + xy'z Im not sure what to do next, i know it can ...
0
votes
2answers
26 views

help on simplifying boolean algebra

I need t show the the terms on the left simplify to the ones on the right $$(X+Y).(X'+Z)= X.Z+X'.Y$$ My attempt: I went with $$XX'+XZ+YX'+YZ= 0 +XZ+YX'+YZ$$ But I'm stumped beyond ...
2
votes
2answers
30 views

Can$A \cap (B' \cap C')$ be $(A \cap B') \cap (A \cap C')$?

If I use the above statement, provided that it is right, in a question, would I have to prove it as well?
0
votes
1answer
15 views

Is this the correct way of drawing a combinatorial circuit based on the disjunctive normal form and logic table?

The logic table: $$\begin{array}{|c3:c|}\hline x & y & z & f(x,y,z) \\\hline 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & ...
0
votes
1answer
44 views

Algorithms - Finding Clique of size n in a Graph

I have the following statements (NOTE: $\bar x$ means the complement of $x$): $(x_1 V \bar x_2 V x_3) ∧ ( \bar x_1 V x_2 V x_3) ∧ (x_1 V \bar x_3) ∧ (x_2 V \bar x_3 V x_4)$ I need to do the ...
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
29 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
28 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 ...
0
votes
0answers
46 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
36 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
10 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
55 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
31 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
18 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
19 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
13 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
31 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 ...
-1
votes
2answers
38 views
2
votes
1answer
25 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
16 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
16 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
16 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
18 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
41 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
21 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
25 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
38 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
20 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
21 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
22 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
42 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
votes
0answers
21 views

A logic circuit simplification and boolean algebra question

Here is my logic circuit Hey guys, I have a question that I'm working on for 2 days but I couldnt find a way out. The question is : Determine a boolean function F(x,y,z) and reduce F using boolean ...
1
vote
4answers
34 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)) --> ...
0
votes
1answer
29 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
29 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