Questions tagged [boolean-algebra]
Boolean algebras are structures which behave similar to a power set with complement, intersection and union. Use this tag for questions about Boolean algebras as structures, or about functions defined from/to Boolean algebras. For Boolean logic use the tag propositional-calculus.
3,033
questions
0
votes
1
answer
28
views
Transform to CNF (conjunctive normal form)
I am trying to convert the following expression to CNF (conjunctive normal form):
$\left(A\Rightarrow B\right)\Rightarrow\left(A\Rightarrow C\right)$
As my first steps I am removing the implications ...
0
votes
0
answers
67
views
How to prove below two logic formulas?
Below 2 formulas are used for SM3 algorithm, first one is FF2 & second one is GG2.
FF2(X,Y,Z) = $(X \land Y) \lor (X \land Z) \lor (Y \land Z)$
GG2(X,Y,Z) = $(X \land Y) \lor (\lnot X \land Z)$
...
- 101
0
votes
0
answers
16
views
Encoding lexicographic order into CNF
Suppose we have two Boolean vectors, $x$ and $y$, of length $n$. How can I encode $x<_{\text{lex}}y$ into a CNF?
The only Boolean formula I can think of is
$$(\neg x_0\land y_0)\lor\bigvee_{i=1}^{n-...
- 423
-2
votes
0
answers
28
views
Boolean Algebra: Simplifying $(x +y + z'wu')' + y'zw'$ [closed]
$$(x +y+z'*w*u') + y'*z*w'$$
$$\left((x'*y')*z''+w'+u''\right) + y'*z*w'$$
$$(x´*y'.z+w´+u)y'*z*w'$$
1
vote
1
answer
72
views
Construct truth table based on circuit given.
I need help with this circuit Boolean algebra question. The question and the image for figure 1 is below.
Write the input/output truth table for the circuit in figure 1. $A$ and $B$ are inputs and $X$...
-1
votes
0
answers
7
views
How to express the Boolean cardinality constraint to CNF formulas? [closed]
A Boolean cardinality constraint
$$\sum_{j=0}^{n-1}x_j=k,$$
where $x_j$’s are Boolean
variables, and $k$ is a non-negative integer.
How to express the Boolean cardinality constraint to CNF formulas?
0
votes
0
answers
10
views
What does it mean for a Boolean function to have a single minimal expression as SOP or POS.
My lecturer sometimes asks questions about functions that have a single minimal expression, I have trouble understanding what I can conclude from the fact that the expression is single.
I know that a ...
- 1
-1
votes
0
answers
16
views
Set Theory: Prove by Boolean algebra using absorption and/or CDNF/CCNF conversion. [closed]
i am having a hard time how to approach this problem, i keep getting stuck after applying the set difference/relative complement.
(A\B)'(B\A)' = B\A
- 1
0
votes
0
answers
39
views
Homogeneity of Lévy Collapse
I'm reading the section from Jech's Set Theory regarding the Lévy Collapse $Coll(\aleph_0,<\lambda)$. The following is a lemma towards proving the homogeneity of the Lévy Collapse:
Here Jech is ...
- 415
0
votes
1
answer
35
views
Complete Subalgebras and Dense Subalgebras of Complete Boolean Algebras are Regular Subalgebras
In Thomas Jech's Set Theory book, he states that
If $A$ is a complete subalgebra of a complete Boolean algebra $B$ then $A$ is a regular subalgebra of $B$.
Also, if $A$ is a dense subalgebra of $B$ ...
- 435
1
vote
2
answers
76
views
Equational axiomatization and first-order axiomatization of the class of fields united with the class of Boolean algebras
This is really two questions in one, one about universal algebra and one about model theory. Let our signature be $\{+,*,-,0,1\}$. I have recently realized that both fields and Boolean algebras share ...
- 18.5k
1
vote
1
answer
28
views
Define Boolean operations in terms of inclusive denial
Define the binary operation of inclusive denial, denoted by $|$ on a Boolean algebra making $x|y = x' \vee y'$.
Show that the binary operations of disjunction $\vee$, conjunction $\wedge$, the unary ...
- 183
0
votes
0
answers
14
views
minimise logic function using K-map
I was asked to minimise the following logic function using K-map:
𝐹(𝑥,𝑦,𝑧) = 𝑥'𝑦'𝑧' + 𝑥'𝑦 + 𝑥𝑦𝑧' + 𝑥𝑧
Then, I tried to construct the following k-map (not sure if this is correct), and ...
- 1
1
vote
0
answers
19
views
Is there a way to generalize the product $\sigma$-algebra for any Boolean algebras
For two measurable space $(X,\mathcal X)$ and $(Y,\mathcal Y)$, their product $\sigma$-algebra is $(X\times Y,\mathcal X\otimes \mathcal Y)$. It is the smallest sub $\sigma$-algebra of $\mathcal P(X\...
- 5,395
-1
votes
1
answer
47
views
Boolean Simplification - Confused
I am doing some mathematics, and I am currently stuck on something. I do not understand this part at all, how can one approach this?
No variable is used here.
Problem:
Simplify the following Boolean ...
- 199
3
votes
0
answers
33
views
Convert list of Boolean functions into logic circuit
Assume that I have a list of variables $x_1,...,x_n$ and a list of Boolean functions $f_1(x_1,...,x_n),...,f_m(x_1,...,x_n)$
What I would like to do is create a circuit gate graph $G=(V,E)$ which ...
- 309
0
votes
1
answer
46
views
what is the maximal and minimum number of linear equations can be satisfied
Given $\alpha>0$, consider the following system of linear equations of variable $x=(x_1,\cdots,x_n)$ where $x\in\mathbb{R}^n\backslash x_0$. The $x_0$ denotes vectors that all elements are equal. ...
- 139
0
votes
0
answers
65
views
Prove $\vdash(A\supset B)\supset C\equiv C\overline{\vee }[A\wedge \neg(B\vee C)]$ using your favorite method
I've been playing with Boolean logic vs ordinary laws of logic like DeMorgan's etc., and I've come up with the following theorem in about 4 lines: $$[(A\supset B)\supset C]\equiv \left\{C\overline{\...
- 1,495
0
votes
1
answer
56
views
What is Mathematical equation for (x * a) XOR (x * b) XOR (x * c)?
The question is; how to calculate (x * a) XOR (x *b) XOR (x *c)?
Definitions are; x, a, b, c are all large hexadecimal numbers known by default.
Solutions are; to ...
- 101
1
vote
4
answers
90
views
Understanding absorption law
I can't understand how absorption law is obtained. I get following steps.
$$a∨(a∧𝑏) = (a∧⊤)∨(a∧𝑏)$$
$$=(a∨a)∧(a∨b)∧(⊤∨a)∧(⊤∨b)$$
then,
I come up with $$=a∧(a∨b)∧⊤∧⊤$$ $$=a∧(a∨b)$$
But, I cannot get $...
0
votes
1
answer
40
views
A sort of generalization of De Morgan's law for Boolean algebras
I've proved the De Morgan's law $\neg (x \vee y) = \neg x \wedge \neg y$.
How can I prove that in every complete Boolean algebra $\neg \bigvee_{i \in I} x_i = \bigwedge_{i \in I} \neg x_i$?
- 445
0
votes
0
answers
25
views
Generated boolean sub-algebras
So in class we came across the next definition:
Let B be a boolean algebra and E a subset of B, let A be a boolean sub-algebra of B that contains E, we will say that A is generated by E if for every D,...
- 51
0
votes
0
answers
12
views
Zeroes of a $n$-variable boolean function of degree $d$.
Let $f$ be a non-constant boolean function of degree $d$ in variables $x_1,x_2,\dots,x_n$ where $d < n$. How do we prove that there exists a non-zero vector with at most $d+1$ many $1$ such that $f(...
1
vote
1
answer
98
views
Sublattices of rank n of the Boolean algebra and partial orders
Let $f(n)$ be the number of sub lattices of rank n the Boolean algebra $B_n$.
I want to show that $f(n)$ is also the number of partial orders of $P$ on $[𝑛]$.
I have read this question from Counting ...
0
votes
1
answer
39
views
Countable generation of the Borel measure algebra
Consider the Borel sigma-algebra on $\mathbb{R}$ quotiented by the ideal of measure-zero sets (see definitions below). This forms a measure algebra. My question is whether this measure algebra is ...
- 107
-2
votes
2
answers
55
views
How to form a CNF of following formula [closed]
We got an exercise to make a CNF out of the following formula: $$G = ((A \vee \neg B \vee C) \wedge (C \vee D)) \vee ((A \vee \neg C) \wedge (B \wedge D))$$ I've tried to make an equivalent equation ...
0
votes
1
answer
50
views
Is there a proof of Pratt's lemma on Chu spaces?
This isn't the typical Pratt's lemma. In his notes$^\color{magenta}{\star}$, Pratt claimed the following without proof:
A simple case of interference is given by a Chu space having a constant row. If ...
- 320
-1
votes
1
answer
77
views
Can we further simplify this expression$?$
Simplify
$$ab+\bar ac+bc$$ where $a,b,c$ are Boolean numbers, that is, $0$ or $1$
$$ab+\bar ac+bc$$
$$=ab+\bar ac+bc\cdot1$$
$$=ab+\bar ac+bc(a+\bar a)$$
$$=ab+bca+\bar ac+bc\bar a$$
$$=ab(1+c)+\bar ...
1
vote
1
answer
73
views
Can any logical operator be rewritten in mathematical logic using only logical conjunction, disjunction, and negation operators? [duplicate]
Assume that we define the operator $\leadsto$ between two propositions $p$ and $q$ as follows:
$$\begin{array}{|c|c|}
\hline
p & q & p \leadsto q \\\hline
\text{T} & \text{T} & \text{...
- 37
1
vote
0
answers
47
views
Generalized boolean algebra structure on connected subset of euclidean space
This is a curiosity question that I've been grappling with as I've been reading more about lattice theory:
Is it possible to endow some connected subset of $\mathbb{R}^n$ with a generalized boolean ...
- 107
0
votes
0
answers
28
views
Boolean algebra derivative - expression independent of the value of certain variable
I'm given the following expression:
$I=((xw \implies (y \bar z)) \Leftrightarrow x \bar w) \overline{(xy \bar z w)}$
This expression simplifies to $x \bar w \lor x \bar y \lor xz$.
Now, I know that ...
- 613
0
votes
0
answers
29
views
Logic function for $c=a-b$ where $a,b \in [0,31]$.
I need to create a switching function that performs the subtraction $c=a-b$ where $a,b \in [0,31]$.
Now, my workbook has realized $c=a+b, a,b \in [0,15]$ using two functions (each with three arguments)...
- 893
0
votes
0
answers
21
views
Does always exist a homomorphism from a power set Boolean algebra to the 2-element Boolean algebra $\mathbf2$?
Wikipedia states:
"there may exist many homomorphisms from a Boolean algebra B to 2".
I would be very grateful for any references to the literature that there always exists a homomorphism ...
- 307
3
votes
3
answers
2k
views
What am I doing wrong to get A = ~A
(Sorry if this is a bad question, I am new to boolean algebra)
If there is a simple expression:
~A
Couldn't I convert it to:
...
- 197
0
votes
0
answers
17
views
Regular Open closure Commutes with Intersection
I have looked in Halmos and Engelking, which would be the natural places to look, and could not find anything related to this. I am trying to understand how the complete Boolean algebra of regular ...
0
votes
0
answers
30
views
Expression for transitive matrices
I am trying to find a mathematical expression for the number of all possible transitive boolean matrices of order nxn.
For example,
$$T_1^n = n(n - 1)^3 + \frac{1}{6}n(n - 1)^4(n - 2) + \frac{1}{6}n(n ...
- 21
1
vote
1
answer
30
views
Converting from binary to RC(Radix Complement - Two's complement) and back from RC to binary
Assume we have a negative number X.
To convert X from binary to Radix Complement we perform two's complement (Complement on the digits) + 1.
Now to convert X from Radix Complement we can perform two'...
- 186
1
vote
1
answer
145
views
Prove that if x and y are real numbers, then max(x,y) + min(x,y) = x+y. [duplicate]
Prove that if x and y are real numbers, then max(x,y) + min(x,y) = x+y. [Hint: Use a proof by cases, with the two cases corresponding to x≥y and x<y, respectively.]
Using hint, I supposed two cases ...
- 97
2
votes
1
answer
105
views
Satisfiability in an Heyting algebra implies satisfiability in a Boolean algebra for propositional logic?
Let $\mathcal{L}$ be a propositional language and let $\text{Prop}(\mathcal{L})$ be the set of all the propositions of the language $\mathcal{L}$.
Let $(H,\wedge,\vee,\rightarrow,1,0)$ be an Heyting ...
- 445
0
votes
1
answer
43
views
Boolean XOR conversion- rewriting to XOR in simplifed form
I have a Boolean Expression simplified to:
BC + AC + A'B'C'
and get to this be rewriting:
C(B + A) + A'B'C'
I need to rewrite to
(A + B) XOR C'
I can check with a Truth Table and can show they are ...
- 11
0
votes
1
answer
38
views
Every boolean algebra is a product of the binary boolean algebra.
I am reading 'From Peirce to Skolem: A neglected chapter in the history of logic'. There the author mentions that the Stone representation theorem 'says that every Boolean algebra is a subalgebra of a ...
- 639
1
vote
1
answer
50
views
Complete Boolean algebras and second-countability
In Wikipedia's article "Complete Boolean algebra, the following example is given:
The Boolean algebra of all Baire sets modulo meager sets in a topological space with a countable base is ...
- 111
1
vote
0
answers
45
views
Applications of Boolean Differential Calculus
I've recently read about a subject field called "Boolean differential calculus", which discusses changes of Boolean variables and functions. This subject defines the derivative of a Boolean ...
- 227
0
votes
0
answers
27
views
Name of the notion dual to disjoint union? ("Exhaustive intersection"?)
Question: Given a set $X$ and subsets $S_1, S_2 \subseteq X$, what is $S_1 \cap S_2$ called when $S_1 \cup S_2 = X$?
More generally, given a set $X$ and subsets $\{S_{i}\}_{i \in \mathcal{I}}$, with $...
- 1,280
2
votes
0
answers
38
views
Maximum fixed points over boolean functions
Given a function $F:\mathbb{Z}_{2}^{n} \to \mathbb{Z}_{2}^{n}$ (We can asume that is in algebraic normal form)
I need to find the max value of $C(A)$ over all $A$ invertible matrices with binary ...
- 152
1
vote
1
answer
101
views
How to prove this theorem $(v\lor s)\land(v\rightarrow p)\land(s\rightarrow a)\land\lnot a\vdash p$
I'm noob to Discrete Math, but I need to prove this $(v\lor s)\land(v\rightarrow p)\land(s\rightarrow a)\land\lnot a\vdash p$
If you can explain what shall I do to prove it.
I can create truth table ...
- 31
0
votes
0
answers
34
views
The Stone mapping and the spremum that is preserved by the mapping
I have some trouble with proving the following proposition in Handbook of Boolean Algebra by Koppelberg.
Let $A$ be a Boolean algebra and $\mathrm{Ult}A$ the set of ultrafilters in $A.$ The Stone ...
- 119
0
votes
0
answers
24
views
Converting ITE to ROBDD form
I need to convert expression $(A \vee C) \wedge (B \vee D) \wedge (A \vee B)$ from ITE tree form to ROBDD form.
ITE FORM
To convert to ROBDD I used the following steps:
joining end nodes
joining ...
- 135
2
votes
2
answers
52
views
Simplify Boolean Expression A'B'C + A'BC + AB'C
The K-map method of simplifying the Boolean Expression A'B'C + A'BC + AB'C gives the answer to be A'C+B'C. But I am not able to solve this algebraically. Please help me out.
What I have tried is
...
- 23
0
votes
0
answers
51
views
Can we improve redundancy theorem of Boolean Algebra?
By redundancy theorem of Boolean Algebra, we have
$xy+\bar{x}z+yz=xy+\bar{x}z$.
My problem is, can we further simply the term in the right side of the above expression? That is, $xy+\bar{x}z=y+z$? Is ...
- 1,322