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

0
votes
0answers
13 views

Problem in the correspondence between boolean rings and boolean algebra through characteristic functions

I was working on the relation between boolean algebras and boolean ring and that they are in fact, the same object. But I find something which seems to be incorrect, It's quite long and I try to give ...
0
votes
1answer
71 views

Discrete Math Predicate Logic

Consider truth assignments involving only the propositional variables $x_0, x_1, x_2, x_3$ and $y_0, y_1, y_2, y_3$. Every such truth assignment gives a value of $1$ (representing true) or ...
1
vote
1answer
18 views

Set of Numbers when added in any combination always produce unique result

What I'm looking for is a set of numbers that when added in any combination they always have a unique sum? Is this called something? I have searched on google for hours and I'm having a hard time ...
0
votes
1answer
26 views

A question about truth tables

Hello guys i have a question, I am trying to make a truth table which consists out of 4 variables F(A,B,C,D) = B'D + A'D + BD Is it true on the truth table when for example in B'D we have 0001 or ...
0
votes
1answer
55 views

Boolean algebra Simplification of “xy + x'z + yz” [closed]

I'd like to simplify the following expression "xy + x'z + yz": ...
0
votes
0answers
13 views

Homomorphism from a four-element Boolean algebra

I have a set like: $$ S = \{0, a, b, 1\} $$ I need to show all homomorphisms from a four-element Boolean algebra to another four-element Boolean algebra. How to find and write them?
0
votes
1answer
26 views

All subalgebras of eight-element Boolean algebra

Let's assume that we have a set: $$ X = \{a, b, c\} $$ Is it true, that a Boolean algebra of this set is like below? $$ P(X) = \{\emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, ...
1
vote
1answer
25 views

Number of subalgebras of the power set algebra

Let $X=\{a,b,c\}$ and $\mathcal{P}X=\{\emptyset,X,\{a\},\{b\},\{c\},\{a,b\}.\{a,c\},\{b,c\}\}$. I can only see 4 subalgebras of $\mathcal{P}X$, namely: $\mathcal{F}_0=\{\emptyset,X\}$ ...
0
votes
1answer
58 views

Stone space of finite Boolean algebras

Is the Stone space of every finite Boolean algebra a finite discrete space (for every finite Boolean algebra is complete, atomic, and isomorphic to the power set of its atoms; and finite discrete ...
0
votes
0answers
46 views

Trying to prove Equivalency using Boolean Algebra

The question presented was to use boolean algebra to show that XY’Z + X’Y’Z’ + XY’Z’ + X’YZ’ ≡ XYZ’ + XY’Z + XY’Z’ + XYZ’ I've tried using various laws of Boolean algebra, but the answer that I ...
0
votes
0answers
22 views

Automorphism groups of Boolean algebras and atomicity

Let $A$ be a complete Boolean algebra, $B$ a complete Boolean subalgebra of $A$, $G$ a group of automorphisms of $A$. Finally let $Fix_G(A)$ be the subalgebra of $A$ that is fixed by every ...
0
votes
0answers
20 views

Connection between Directed Acyclic Graphs and Boolean Functions

I am given a set of $n$ vertices and testing some properties over the set of all directed graphs over them (i.e. acyclicity and bipolarity). I already done this by generating every undirected graph ...
1
vote
2answers
69 views

Why cant AND and NOT represented only with IMPLICATION?

Can someone please explain why can't I use only implication to represent AND and NOT with proof as well? I know that I can represent OR simply by using implication. Was thinking if I could find ...
3
votes
0answers
85 views

Axioms as recreational mathematics

Before modern group theory, mathematicians studied concrete permutation groups: algebraically closed subsets of the set of all bijections on a set $X$ in which all inverses was included. This was the ...
0
votes
1answer
35 views

$f(x) = x$ or a , if $f(x)$ and $a$ is known find $x$ boolean algebra

I am new to boolean algebra. I am facing difficulty solving this problem: Given $f(x) = x \lor a$, for some $f(x)$ and $a$, deduce the value of $x$. Can someone provide me the solution with ...
1
vote
3answers
63 views

Designing a circuit to verify operation of an OR gate.

Consider the following image: I need to design a circuit that verifies the logical operation of the OR gate. In the above image, the LED will be on (f = 1) if the or gate is working properly. I can ...
0
votes
1answer
47 views

Are Boo and BooRng really isomorphic?

In ACC on the top of page 34, I read: The construct Boo of boolean algebras is isomorphic to the construct BooRng of boolean rings and ring homomorphisms. This contradicts my intuition since ...
0
votes
1answer
41 views

AND, OR, NOT, and creating turing complete programming languages

Suppose I have an arbitrary computing language, and the following holds: Let all constants be finite, and assume we are computing in binary. An arbitrary number of inputs, A, and outputs, B, can be ...
0
votes
1answer
50 views

Boolean algebra proof and cancellation law

I have a Boolean algebra with some elements $a,b,c$. I have to show this: $(a ∧ b) ∨ (a′ ∧ c) ∨ (b ∧ c) = (a ∧ b) ∨ (a′ ∧ c)$. Now I have done other such proofs before but this one I got lost in. I ...
2
votes
2answers
73 views

DNF Form of XOR Operator with N Arguments

I’m working on this problem: Explain how to express $p$ using the boolean connectives AND, OR, and NOT so that the resulting expression has length polynomial in $n$. $$p(x_1\cdots x_n) = x_1 \oplus ...
6
votes
1answer
86 views

Boolean algebra gives rise to a ring

There is a well-known result that every boolean algebra $(R,0,1,\land,\lor,\neg)$ can be made a boolean ring by defining $$x\cdot y=x\land y\qquad\text{and}\qquad x+y=(x\land\neg y)\lor(y\land\neg ...
0
votes
0answers
34 views

consider a base 16 adder how to modify the adder so that it can perform a base 8 addition

Consider a base $16$ adder. How can I modify the adder so that it can perform a base $8$ addition? I expect this question will appear in my exam tomorrow; if anyone can give me a hint or a solution, ...
0
votes
0answers
17 views

unique children of a point in a boolean lattice

I am working with two-element boolean algebra, e.g. points composed of strings of $0$s and $1$s and bit-wise $AND$ and $OR$ to find maxima and minima. In the domain I'm working in, I need to assign ...
2
votes
1answer
76 views

Convergence of monotone boolean network in the worst case

I'm looking for (upper bound) convergence of increasing monotone boolean network (network composed only with OR, AND, identity ($f_i(x)=x_j$) functions) in asynchronous updating mode. It means that if ...
0
votes
0answers
65 views

Converting boolean expression - POS to SOP

Convert the following to sum of products form: (a' + c)(a' + b + c')(a + b') I did the following: multiply out the first two expressions: = (a'a' + a'b + a'c' + ca' + cb + cc')(a + b') ...
0
votes
1answer
25 views

Number of bit operations in nxn zero-one matrix boolean product

I was reading transitivity closure from the book Discrete Mathematics and Its Application by Kenneth Rosen It says that in the boolean product of nxn zero-one matrix, there are $n^2(2n-1)$ bit ...
0
votes
1answer
23 views

What is meant by $AB$ in boolean algebra?

I am endeavoring to teach myself Boolean Algebra. Oh what fun! From the questions I've read on this site, one of the most common notations I've seen is $AB$ (examples: here, here, and here). Problem ...
0
votes
1answer
31 views

consider a base-16 adder. explain how to modify the adder so that it can perform a base-10 addition

consider a base-16 adder. explain how to modify the adder so that it can perform a base-10 addition I found this when I searched in Google but not understand please guide me to understand this ...
1
vote
1answer
42 views

How to simplify Boolean expression: $(C'B')+(CB)$

I'm very weak in math and logic, and currently tried doing K-map, and got this as result: $$(C'B')+(CB)$$ My question is, can this be further simplified? I tried it myself, but I got $0$ (False). ...
3
votes
1answer
55 views

Boolean algebra with measures

Let $A,B$ be two Boolean algebra with measures $m,p$ thereon, respectively such that the measure algebra $(A,m)$ is isomorphic to the measure algebra $(B,p)$. Suppose that we have two isomorphic ...
1
vote
4answers
288 views

Simplifying P AND (P OR NOT Q)

How can I simplify this? I've tried invoking Demorgan's Law and I get P AND (NOT (NOT P AND Q)) but I can't seem to simplify this further. The answer is P, but how can I prove this?
0
votes
0answers
46 views

Boolean algebra and boolean subalgebra

I have to prove that set of all dividers of number 210 with appropriate operations forms a Boolean algebra. And describe these operations and create a Hasse diagram. In the secondd part I have to ...
2
votes
1answer
97 views

Stone Representation Theorem

Given two Boolean algebras $A$ and $B$ such that $A$ is a subalgebra of $B$. What is the relation between the Stone space of $A$ and the Stone space of $B$. The question maybe silly but I am getting ...
0
votes
1answer
38 views

Getting sum of products from products of sum

I need to write the following Boolean expression in the form of sum of products $F(A,B,C,D)= (A+B+C+D)(A'+B'+C+D')(A'+C)(A+D)(B+C+D)$ I just want to know how to deal with the missing letters. Is $ ...
0
votes
1answer
33 views

How many satisfying assignments are there in a set of 3-CNF clauses where no clause share the same variable?

Say I have a set of 3-CNF clauses $$\mathcal{S} = \{ x_1 \vee x_2 \vee \bar{x_3}, ~~x_4 \vee x_5 \vee x_6\}$$ where $\bar{x}$ is the negation of $x$. Each variable range over $\mathbb{Z}^2$. How ...
1
vote
1answer
45 views

Logic expression simplification

I want to simplify this logic expression: Y = (A ∧ B ∧ ¬C ∧ D ) ∨ (C ∧ ¬D) ∨ (A ∧ B ∧ C) ∨ (¬A ∧ C) I know it must become Y = (A ∧ B ∧ D) ∨ (C ∧ ¬D) ∨ (¬A ∧ C) and I found it with Karnaugh, but I ...
0
votes
1answer
39 views

DeMorgan's Law with Boolean Algebra

So I'm studying for an Assembly Language final tomorrow and I'm trying to simplify the following expression using Boolean Algebra. Here are the steps I've written so far, am I safe in assuming that ...
0
votes
1answer
15 views

Simplification of expressions?

The expression below fd < S && ld > e || fs > s && ld > e || fd > s && ld < e || fd < s && ld < e Is the ...
0
votes
1answer
50 views

Jayne's Equation 1.13 Derivation

Dear Stack Exchange Members, I'm reading 'Probability Theory - The Logic of of Science" by ET Jaynes, and I'm on pg. 11. Jayne's says: *"...For example, we shall presently have use for a rather ...
0
votes
0answers
49 views

Converting a boolean expression into CNF and DNF

Is there any systematic way to convert the following boolean expression (QUBO) into CNF or DNF? Here, $x_1, \ldots, x_n \in \{0, 1\}$, $a_1, \ldots, a_n \in \mathbb{Z}$ and $b_{1,1}, \ldots, b_{n,n} ...
0
votes
2answers
40 views

Boolean Algebra: Simplifying product of sums

I'm trying to simplify (A+B+C)(A+notB+C)(notA+B+notC) The K-map gives me (A+C)(notA+B+notC) but when I use boolean ...
2
votes
2answers
46 views

How to efficiently determine if any two propositional formulas are equivalent

Given any two arbitrary propositional formulas (but only using $\land, \lor, \lnot$), like $\lnot(A \land (B \lor \lnot B) \land C)$ and $\lnot C \lor \lnot A$, how can I (or a computer) efficiently ...
2
votes
1answer
45 views

An example of an ultrafilter

This is Theorem 3.5 (pp. 150) of the book "A course in universal algebra." http://www.math.uwaterloo.ca/~snburris/htdocs/UALG/univ-algebra.pdf Theorem 3.15. Let $\bf B$ be a Boolean algebra. (a) ...
0
votes
1answer
33 views

Complete subalgebra of regular open Boolean algebra generated from open intervals

Let $X$ be a totally ordered set, considered as a topological space with the order topology. The regular open subsets of $X$ (i.e., the sets $U = \operatorname{int} \operatorname{cl} U$) form a ...
1
vote
2answers
19 views

What is $A^c \cap B^c \cap C^c$

I am working with boolean algebra for my Navy coursework and I was wondering if anyone knew what the formula for $A^c \cap B^c \cap C^c$ is? Also does $A^c \cap B^c \cap C^c = (A \cap B \cap C)^c$? ...
0
votes
1answer
24 views

Trying to simplify boolean algebra a+ac+ab

I am trying to simplify A+AC+AB. I think I have solved it, but I want to double check its right, can it be simplified to A+A(C+b) and then again to A(C+B) as A+A = A?
1
vote
1answer
45 views

How many n-ary Boolean functions essentially dependent on each of their arguments?

How many n-ary Boolean functions essentially dependent on each of their arguments? essentially dependent means that $$f(b_1,…,b_{i−1},0,b_{i+1},…,b_n) \neq f(b_1,…,b_{i−1},1,b_{i+1},…,b_n)$$
1
vote
0answers
39 views

How to convert a mod 2 function to an expression in Boolean Algebra

I'm not sure if this is the right place to post it but I have a question I'm having a hard time understanding. The questions is: Convert the function $X^3Y + 2XZ + WX + W$ mod $2$ to an expression ...
0
votes
0answers
19 views

Are epimorphisms (defined via an obvious action) of free Boolean algebras whose set of generators is a group automorphisms?

Let $G$ be a group. Consider $B$, the free Boolean algebra with generating set (I'll call them "variables") $G$. Let $F$ be some formula (that is, some fixed element of $B$). Define an endomorphism ...
0
votes
0answers
25 views

Number of elements in a Boolean algebra

Consider a set $X$ consisting of $n$ elements Does the Boolean algebra of all subsets of $X$ (i.e. the power set of $X$) have $2^n$ or $2^{2^n}$ elements? I came across both answers, which confuses ...