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
26 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
72 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 ...
4
votes
0answers
97 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
80 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
44 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
67 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
85 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
88 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
35 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
18 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
77 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
77 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
41 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
32 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
47 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
56 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
395 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?
2
votes
1answer
109 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
40 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
46 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
47 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
56 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
78 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
42 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
55 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
48 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
41 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
26 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
47 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
43 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
28 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 ...
0
votes
1answer
37 views

Simplifying Boolean Function with Karnaugh Map

How to write Product-of-sum(POS) and Sum-of-product(SOP) Above K-Map? I already write POS please check my answer.
0
votes
1answer
40 views

Proof for $∃xA⇔¬∀x¬A$

I want to prove, that $∃xA⇔¬∀x¬A$, using classic axioms. I think, I have to start with the following step: $∃xA⇔∃x¬¬A$ But I do not know, how to make this step, using axioms: $∃x¬¬A⇔¬∀x¬A$
2
votes
3answers
44 views

How to show that if $\neg b = a \land d$ then $a \land \neg b = \neg b$ and $b \land \neg a = \neg a$

I'm new to boolean algebra and am having trouble proving the following simple theorem. Many thanks for any help. If $\neg b = a \land d$ then $a \land \neg b = \neg b$ and $b \land \neg a = \neg a$. ...
0
votes
1answer
18 views

Simplifying a Boolean Expression 2

The boolean expression is as follows: (¬A^¬B^¬C)∨(A^¬B^C)∨(A^B^¬C)∨(A^B^C) I have found that A⊕(¬B^¬C) is equal to the above but I have absolutely no idea on how to get this result, I have spent ...
1
vote
2answers
33 views

Inequality with respect to transitivity

Given a relation R, R is said to be transitive if aRb ∧ bRc, then aRc. The unequal relation (≠) is not transitive, for instance a≠b ∧ b≠c, then a≠c is an invalid consequent of the antecedent (a≠b ∧ ...
0
votes
2answers
27 views

Joins in lattices and sublattices

Let $A$ be a lattice, and $B$ be a sublattice of $A$. Why is the join of $A$ included in the join of $B$? That is, why is $\bigcup_{t\in T}^{A} a_t\leq\bigcup_{t\in T}^{B} a_t$? (I am tempted to ...
0
votes
1answer
22 views

Product of maxterms

Please help me break the ice in understanding how we derive a product of maxterms, say, for: $xy+x'z $ I could be missing some concept here in this but be patient with me. I have also done SOP and ...
1
vote
1answer
22 views

Is there any way to simplify the following boolean expression?

I was trying to manipulate with litarals and minterms of this booleans expression but it really did not lead to anything that could simplify the expression further.. Not sure if I am doing it wrong or ...
1
vote
2answers
19 views

Proving relation in boolean algebra, need help

Here is the logic equation and I am trying to prove the relation ($'$ stands for complement): $$𝑥_1𝑥_3' + 𝑥_2'𝑥_3' +𝑥_1𝑥_3 +𝑥_2'𝑥_3 = 𝑥_1'𝑥_2' + 𝑥_1𝑥_2 + 𝑥_1𝑥_2'$$ What I am doing: ...
0
votes
1answer
46 views

Least and greatest element of the $(\mathbb{N}, |)$

Consider the relation | on $\mathbb{N}$, where $\mathbb{N} = \{0,1,2,... \}$ and $n|m$ means $n$ divides $m$. I know that the pair $(\mathbb{N}, |)$ is a partial order, : (1) Find the least and ...
0
votes
1answer
58 views

Duality Principle in Boolean Algebra - Why do I alway get !F instead of F?

I have the function: F = !(a && d || b || c) Now i apply the duality principle and exchange all * with + ...
1
vote
1answer
24 views

How can I prove that (x and ¬y) or (¬x and y) = ¬((x and y) or (¬x and ¬y))?

I'm stuck at this problem: (x and ¬y) or (¬x and y) = ¬((x and y) or (¬x and ¬y)) Basically what I have to do is to convert the right side of the equation to the left side using boolean algebra. I ...