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

How to deal with an 8 variable Karnaugh map

I'm reaching back into my high school days trying to remember one of the rules about Karnaugh Maps. I have an 8 variable input, and I remember that I should try and make the selections a big as ...
0
votes
1answer
41 views

Is there a blackboard bold letter for the set of Boolean numbers? [duplicate]

Is there a symbol (e.g. $\mathbb{B}$) for the special set of Boolean numbers or values; ${0,1}$ or ${True,False}$?
0
votes
1answer
36 views

Galois field of order 2 constituting a Boolean algebra

We know that the the set $\{0,1\}$ constitutes a Boolean Algebra over the usual $OR$ and $AND$ operations. However, because of the lack of an additive inverse for $1$ this does not produce a Galois ...
1
vote
1answer
34 views

A proof of maximality of an antichain in a complete Boolean algebra

Suppose $(\mathbf{B},\leqslant)$ is a complete Boolean algebra and let $|\mathbf{B}|=|\gamma|$. Let $C=\langle c_\alpha\mid \alpha<\gamma\rangle$ be a maximal descending chain without a lower ...
0
votes
1answer
17 views

Boolean Expression Simplifying explanation

Currently have worked xz' + x'y + (yz)' Down to z' + x'y + y' Is this its simplest form? METHOD: xz' + x'y + (yz)' -> De-Morgan on (yz)' xz' + x'y + y' + z' -> Commutative xz' + z' + x'y + y' -> ...
2
votes
0answers
16 views

Do DeMorgan's laws hold for pseudo-complement in Bi-Heyting Algebra?

A textbook says in Heyting Algebra, The pseudo-complement of an element $a$ is denoted as $a^{\ast}$. One of the DeMorgan's law $\left(\vee a_{i}\right)^{\ast}=\wedge a_{i}^{\ast}$ holds ...
1
vote
2answers
33 views

boolean algebra reduction question

hi im having a lot of trouble proving this boolean expression. Im getting many differing answers so I assume I must be going about it in the wrong way. To explain, I'm trying to negate the whole LHS ...
16
votes
2answers
2k views

Why are Boolean Algebras called “Algebras”?

Boolean algebras aren't algebras (to the best of my understanding). So why are they called algebras? Wouldn't it make more sense to call them a "Boolean system" or a "Boology" or something else like ...
1
vote
0answers
17 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: ...
-1
votes
1answer
30 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
8 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
22 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
30 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 ...
1
vote
1answer
37 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 ...
-1
votes
0answers
7 views

Simplify problem using duality or consensus theorem

I have a difficult with the problem, whenever I try to solve this problem $W'Y'+WYZ+XY'Z+W'X'+Y$ (three literal term) I confused with so I have to factor equation to simplify,and I quite confused ...
0
votes
1answer
24 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
26 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
132 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
17 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
140 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
33 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
17 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
49 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
30 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
33 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
37 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
11 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
34 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
19 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
24 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
35 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
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
19 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
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
19 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 ...