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
19 views

General rules for transforming boolean equations?

Are there general or restricted rules for transforming between equivalent boolean equations? A concrete problem that I have is given the following equation: ...
0
votes
1answer
33 views

Help with Simplifying boolean algebra, not sure if i have done it correctly.

I have no idea how to do boolean algebra, First question is x'y + x(x + y') I need to first draw a circuit diagram(logic gate) and then simplify it and draw a simplified logic gate. As of now I ...
0
votes
0answers
9 views

Correct definition of the co-occurrence graph of a pseudo-Boolean function

In section 4.6 of Pseudo-Boolean Optimization, Boros and Hammer have defined the co-occurrence graph of a pseudo-Boolean function as follows. If a pseudo-Boolean function $f : \mathbb{B}^n \mapsto ...
0
votes
1answer
25 views

Is a boolean algebra closed under countable disjunction/conjunction?

I'm just curious if the properties in a sigma algebra is also satisfied in a boolean algebra. In a boolean algebra, the two operators are closed under finite operations, but can we say they are closed ...
0
votes
1answer
32 views

Comparing entropies $H((f(X,Y), g(X,Y)))$ and $H ((f(X,Y),g(X,Z)))$

Let X,Y,Z be three independent uniform distributions on $\{0,1\}^n$; $f, g:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}$ be two boolean functions. Is it true that $$H((f(X,Y), g(X,Y)))\leq H ((f(X,Y),...
1
vote
1answer
42 views

how to construct a boolean algebra out of a set of well formed formulas?

Given a set of well formed formulas of a first order language (with equality, constants, variables, non-logical symbols, etc), is it possible to use it as some kind of base to construct a (possible ...
1
vote
1answer
45 views

What is the name of a “basis” in Boolean algebras

So, a basis in linear algebra is the smallest set which generates a particular vector space. (More formally, a subset of the vector space which is linearly independent and spans the vector space) Is ...
0
votes
1answer
29 views

What is wrong with my Boolean expression?

I've got the following expression: A*!B*(!B*C+!C*A*(D+B*!A+D*A*B+C*!D)) After translating it to Wolfram's understandable language I got this: ...
2
votes
0answers
29 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
30 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$. ...
1
vote
1answer
134 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
18 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
21 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) (...
4
votes
1answer
141 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
15 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
29 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
35 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
18 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
53 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
37 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
51 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
39 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
36 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
13 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
23 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
28 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
42 views
2
votes
1answer
29 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
24 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
18 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
21 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
35 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
26 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
30 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
41 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$$