Skip to main content

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.

Filter by
Sorted by
Tagged with
1 vote
1 answer
44 views

Does the variety of Boolean Algebras contain no proper nontrivial subvarieties/subquasivarieties?

Consider the variety, in the sense of universal algebra, of Boolean Algebras in the language $\{\cup,\cap,',0,1\}$, where $'$ represents complementation, and the other symbols are well known. I ...
user107952's user avatar
  • 21.5k
0 votes
0 answers
17 views

How to find the minimum sum of products expression from a two variable truth table with only one 0?

I am looking for a minimum sum of products expression from this truth table: A B f 0 0 1 1 0 0 1 1 1 0 1 1 From my understanding, I can create the minimum sum of products expression from the ...
Paul's user avatar
  • 1
0 votes
0 answers
22 views

I dont understand how to solve this Boolean Algebra question Help

Let S be a set and let F UN(S, {0, 1}) be the set of all functions with domain S and codomain {0, 1}. Define the Boolean operations on F UN(S, {0, 1}) as follows: Let F, G ∈ F UN(S, {0, 1}), then (a) ...
G21's user avatar
  • 1
-1 votes
0 answers
18 views

How Do I simplify This Boolean Expression? [duplicate]

Expression: $$XY' + Y'Z' + X'Z'.$$ I think it has something to do with the consensus formula, but I can't actually figure out how to approach this problem.
Mosaddeq Hussain's user avatar
0 votes
1 answer
24 views

Inverse of a boolean lower unitriangular matrix

Is the inverse of a boolean lower unitriangular matrix identical to the matrix itself? The matrix entries are considered to be in GF(2), i.e. bool.
Daniel S.'s user avatar
  • 532
0 votes
1 answer
70 views

Boolean NOT is missing: the count of items in set A but not in set B is the count of items in either set less the count of items in B, right?

A computer system I'm accessing has a weird query limitation: I can query using AND and OR Boolean operators, but NOT is restricted. However, there's a way around this limitation, isn't there? I've ...
Martin Burch's user avatar
1 vote
0 answers
13 views

Simplification of boolean expression algorithms allowing multiple input gates

I am looking to algorithmically generate simplified diagrams of boolean logic that exists in a DCS program. I have come across a number of online boolean expression simplification tools, that use De ...
bruceceng's user avatar
  • 141
3 votes
1 answer
91 views

Finite Commutative ring with 100 elements where $x^2=x$?

Does there exist a finite Commutative ring with 100 elements where $x^2=x$ for every $x\in R$? I know finite Boolean rings has the property this property but they have cardinality $2^n$, for some $n$. ...
Learner's user avatar
  • 369
0 votes
0 answers
25 views

Gray code permutation notation

I 'm trying to understand the notation of the Gray code permutation but since I only know 2-row matrix notation for permutations, I would like an explanation for the notations below . I understand the ...
user159729's user avatar
-5 votes
1 answer
102 views

A statement that seems to be neither true nor false [closed]

Let us consider a statement A that says "Statement A is false". Now is the statement A true or false? If it's false then statement that says "Statement A is false" is true ...
Filip Mazurek's user avatar
0 votes
0 answers
34 views

A generalized algorithm to convert a formula in algebraic normal form to an equivalent formula that minimizes the number of bitwise operations

In this question, “bitwise operation” means any operation from the set {XOR, AND, OR}. The NOT operation is not included because ...
lyrically wicked's user avatar
3 votes
1 answer
182 views

What statement is true for every $a$, $b$ and $c$?

I have this task in mathematical logic for which I don't really have a tool for solving. What statement is true for every a, b and c? $a \in b \wedge b \in c \rightarrow a \in c$ $a \in b \wedge b \...
Danilo Jonić's user avatar
0 votes
0 answers
33 views

A weaker version of the De Morgan algebras

A De Morgan algebra is a structure $\langle A, \lor, \land,0,1,\neg \rangle$ such that $\langle A, \lor, \land,0,1 \rangle$ is a bounded distributive lattice and $\neg$ is a involution that ...
MtSet's user avatar
  • 49
2 votes
1 answer
35 views

Generate as short as possible boolean formula from a given truth table

Given a truth table, maybe 3-vars, 5-vars or even 10-vars, i can write its formula in DNF or CNF, and simplify it using K-Map or Quine-McCluskey algorithm. But it is based on {NOT, AND, OR}. Now the ...
tangsongxiaoba's user avatar
0 votes
0 answers
125 views

Relationship between XOR operator with Summation

A functions $f : \{0,1\}^\ell\to \{0, 1\}$ such that for some $i \in [\ell]$ it holds that $f(x)=x_i.$ Also, $$f(x)=x_i,f(y)=y_i,f(x\land y)=x_i\land y_i\implies f(x)\land f(y)=f(x\land y).$$ If I ...
D. S.'s user avatar
  • 40
1 vote
1 answer
86 views

Time complexity of boolean function

We view Boolean functions $f : \{0,1\}^\ell\to \{0, 1\}$ as functions of $\ell$ Boolean variables; that is, we view the $\ell$-bit long argument to $f$ as an assignment of Boolean values to $\ell$ ...
D. S.'s user avatar
  • 40
3 votes
1 answer
51 views

Counting homomorphisms from non-free Boolean algebras to the free Boolean algebra on $n$ generators

I have been foraying a bit into belief revision theory and formal epistemology recently, and that has ended up at me having to explore some universal algebra and combinatorics. I'll cut straight to ...
safsom's user avatar
  • 497
1 vote
1 answer
49 views

Point-separating fields of clopen sets on compact spaces without Choice

In Matthew Dirk's Paper on Stone's representation theorem there is a proof of Lemma 3.8. If X is a Stone space and F is a separating field of clopen subsets of X, then F is the dual algebra of X; that ...
Daniel Weichhart's user avatar
1 vote
1 answer
60 views

Stone's Representation Theorem equivalences

I have seen statements such as "Stone's Representation Theorem is equivalent to Compactness, Tychonoff, Ultrafilter Lemma, Boolean Prime Ideal Theorem, Completeness Theorem.... over ZF" ...
Daniel Weichhart's user avatar
2 votes
0 answers
52 views

Clarification on the nature of the Cantor set in the algebra of Baire sets modulo meager sets

Let $X$ be the Stone space of a $\sigma$-complete Boolean algebra $A$. I know that $A$ is isomorphic to the algebra $Ba(X)/M$ of Baire subsets of $X$ modulo meager set and that the Cantor set is an ...
LJGC's user avatar
  • 151
-1 votes
1 answer
49 views

Application of the Duality Principle in Boolean Algebra [closed]

Can the Duality Principle in Boolean Algebra be applied to prove theorems in different branches of Mathematics? I ask because of the following: First, let multiplication signify conjunction, so that ...
Lorenzo Gil Badiola's user avatar
0 votes
0 answers
45 views

Can any finite set of binary sequences be expressed as CNF/DNF

I am new to logic and cannot figure out if there are instances when a given set of binary sequences of equal length is not possible to express as a conjunctive or disjunctive normal form. If such sets ...
MsTais's user avatar
  • 397
1 vote
0 answers
20 views

Generate, for a given number of variables, all expression post-absorption that use only conjunction and disjunction with no permutation

I learned the law of absorption in Boolean algebra and asked myself how to generate, for a given number of variables, all expression post-absorption that use only conjunction and disjunction with no ...
Emanresu's user avatar
0 votes
2 answers
107 views

Why is $[[x \in y]]$ not $y(x)$ in Boolean-valued models?

I'm reading about Boolean-valued models (in order to understand the first Cohen model), and it seems as though the truth value of the formula "$x \in y$", which is written $[[x \in y]]$, is ...
Cloudscape's user avatar
  • 5,146
0 votes
1 answer
70 views

What is the arity of a degenerate Boolean function? Or rather: Are there good names for the two possible answers?

For Boolean functions the term “arity” is somewhat ambiguous. I would say, that there are three different meanings, two of which are important. small: $A \land C$ has arity 2, because input $B$ is ...
Watchduck's user avatar
  • 117
1 vote
1 answer
72 views

Can we express binary functions in terms of differential equations with xor as differential operator?

Differential equations can be used to describe functions. Some famous ones include $$\frac{\partial f}{\partial x} - f(x) = 0$$ $$\frac{\partial^2 f}{\partial x^2} - f(x) = 0$$ The iterated running ...
mathreadler's user avatar
  • 26.1k
4 votes
1 answer
66 views

Complete Boolean Algebra and Distributivity [duplicate]

Thear are two facts about Boolean algebra: Every Boolean algebra is isomorphic to an algebra of sets. (Stone's Representation Thm) Every complete algebra of sets is completely distributive. (said in ...
BlowingWind's user avatar
0 votes
1 answer
40 views

Maximal number of independent vectors in a Boolean space

Consider the set of length $n$ Boolean vectors, with addition defined as component-wise OR, and multiplication by a boolean scalar value defined by component-wise AND with that scalar, as expected. ...
Michele's user avatar
  • 133
2 votes
1 answer
47 views

Saturation of infinite complete Boolean algebra is a regular cardinal

Similar question existed here. However there are still many gaps for stupid persons like me. A Boolean algebra $B$ is called $\kappa$-saturated if there is no antichain with supremum $1$ (also called ...
BlowingWind's user avatar
0 votes
1 answer
30 views

Is the dual of a principal filter to be a principal ideal?

A filter $F$ on $S$ is principal if $$ F=\{X\subseteq S\mid X\supseteq X_0\} $$ for some nonempty $X_0\subseteq S$. Consider $P(S)$ to be a Boolean ring $(P(S),\cup,\cap)$, then the $dual$ of a filter ...
BlowingWind's user avatar
3 votes
0 answers
85 views

computational complexity of stabilization problem in Boolean control network

Stabilization problem is a fundamental problem in control theory. There are many literature to achieve stabilization but fewer results are related in computational complexity. Consequently, we ...
MATH_LI's user avatar
  • 47
1 vote
0 answers
25 views

Boolean function with characters in the function value, not 0 and 1

I am currently studying the textbook Digital Design by Mano, and learned that the Boolean function can be expressed algebraically from a given truth table by forming a minterm for each combination of ...
user65452's user avatar
  • 391
0 votes
1 answer
60 views

Is the theory of Boolean algebras equal to the theory of Boole's algebra?

Let $BA$ be the set of axioms of Boolean algebras. Let $Th(BA)$ be the set of first-order sentences that are true when conjoined with the axioms in $BA$. I believe that $Th(BA) = Th(\langle \{0,1\}, \...
user1868607's user avatar
  • 5,965
3 votes
0 answers
61 views

Quantifier elimination for Boolean algebras

Is there a reference in English for the proof that Boolean algebras admit quantifier elimination? I'm interested in how quantifier elimination can be performed. However, the result of Tarski is not ...
user1868607's user avatar
  • 5,965
2 votes
1 answer
87 views

Why can a compound biconditional statement whose individual statements don't all have the same truth values be true?

Why can $P_1 ⇔ P_2 ⇔ P_3 ⇔ \ldots ⇔ P_n$ be true when not all the $P$’s have the same truth value? For example: If P1 = T P2 = T P3 = F P4 = F would this be true? T(P1) ⇔ T(P2) ⇔ F(P3) ⇔ F(P4) = ...
Swagmorticus Florian's user avatar
1 vote
2 answers
85 views

Simplifying the Boolean expression $x'y + x(x+y')$

Expression: $$x'y + x(x+y')$$ My attempt: $x'y + x(x+y')$ $x'y + xx + xy' \quad \textit{After applying second Distributive law.}$ $x'y + x + xy' \quad \textit{After applying second Idempotent law.}$ $...
Alix Blaine's user avatar
0 votes
1 answer
40 views

Trying to simplify the following boolean expression but suck and new to this

Expression: $[x + (yz)](x' + z)$ My attempt: $[x + (yz)](x' + z)$ $(x + y)(x + z)(x' + z) \quad \textit{Distributive law}$ The answer is supposed to be: $(x + y) \times z$ N.B. I am still new to ...
Alix Blaine's user avatar
1 vote
2 answers
180 views

How to simplify the boolean expression $(x\times y)'+(y\times z)$?

Expression: $$(x\times y)'+(y\times z)$$ My attempt: $(xy)' + (yz)$ $(x'+y') + (yz) \quad \textit{After applying de Morgan's Axiom}$ $x' + (y' + yz) \quad \textit{After applying 1st Distributive ...
Alix Blaine's user avatar
0 votes
1 answer
68 views

Where did I go wrong trying to simplify this down to $(x \times y)$ boolean expression?

Simplify: $[(x \times y') + x']' $ My attempt: $((x \times y') + x')' $ $(x \times y')' \times x''$ $(x'+ y'') \times x''$ $(x' + y'') \times x$ $(x' + y) \times x$ $(x'+ y)(x' + x)$ $x(x' + y) + x'(...
Alix Blaine's user avatar
1 vote
2 answers
86 views

Trying to simplify the following boolean expression [closed]

Simplify: $y \times [x + (x' \times y)]$ My attempt: $y \times [(x + x') \times (x + y)] \quad \textit{First Distributive Axiom} $ $y \times [1 \times (x + y)] \quad \textit{First Inverse Axiom} $ ...
Alix Blaine's user avatar
2 votes
0 answers
52 views

Find the minimum number of conjuncts in the DNF of function $g$

The Boolean function $g$ of the variables $x_1 , . . . , x_5 , y_1 , . . . , y_5$ , is given by the formula: $$ \bigwedge_{i=1}^{5} (x_i \ \vee \ y_i) $$ Mission: find the dnf($g$). (the minimum ...
Jacobs Monarch's user avatar
1 vote
0 answers
42 views

Finite distributive lattices and finite abelian monoids

A structure of semilattice over T is the same thing than a structure of finite abelian monoid such that $\forall t \in T$, $t² = t$. Given a semilattice T, we get an abelian monoid by defining $a.b$ =...
newuser's user avatar
  • 302
0 votes
2 answers
121 views

Why is the distributive law incorrect here?

I am trying to simplify: $(p \lor \neg q) \land (p \lor q) $ One thing, I identify from the table is this: $(p \lor q) \land (p \lor r) $ is second distributive law which becomes $p \lor (q \land r) $ ...
Alix Blaine's user avatar
5 votes
1 answer
160 views

Are Stonean spaces a reflective subcategory of topological spaces with continuous open maps?

I'm not talking about Stone spaces! A Stonean space is a compact Hausdorff extremally disconnected space i.e. a compact Hausdorff space such that for all open $U$, its closure $\overline{U}$ is also ...
Jakobian's user avatar
  • 10.5k
0 votes
0 answers
54 views

Example of a family of Boolean subalgebras such that their union is not a Boolean algebra

I read that given a family of Boolean subalgebras, their union is not in general a Boolean algebra except if the family is directed. What is an example of a family of Boolean subalgebras whose union ...
Link L's user avatar
  • 735
0 votes
1 answer
55 views

Boole Algebra, ab+bc+ca=(a+b)(b+c)(c+a), how to solve starting from left?

I was able to find a demonstration, starting from the right part, I wanted to start from the left part, in order to check if I understood well my knowdlege, Starting from left or right does make any ...
Delayer's user avatar
  • 197
0 votes
1 answer
69 views

I need help with this propositional logic problem

I study compound statements, and I encountered this problem in the book: The problem I tried a solution: Let p be proposition "The first door leads to freedom" and let q be proposition "...
Begginer2005's user avatar
0 votes
1 answer
27 views

Variable elimination by clause distribution in Conjunctive normal form (CNF)

I am refering to this document. The relevant part is: My question: I understand that (a or b) and (not(a) or c) implies b or c ...
mangolassi's user avatar
0 votes
1 answer
52 views

How to prove two tables are logically equivalent if they have different numbers of variables?

I used boolean algebra to simplify an expression with $3$ variables. After simplifying, it reduces to $2$ variables. The first truth table has $8$ rows and the second one has $4$. How to prove that ...
anothercodingnoob's user avatar
1 vote
1 answer
54 views

I've found the minimal AND-OR expression for a function, but I can't find the minimal OR-AND function

I am given a function $f(W,X,Y,Z)$ that only outputs $1$ if exactly three inputs are $1$. The AND-OR function is easy enough to find: $$ W'X\,YZ + WX'YZ + WX\,Y'Z + WX\,YZ' $$ I think that function is ...
Daniel's user avatar
  • 71

1
2 3 4 5
63