Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
1answer
32 views

Boolean Algebra (Matrix?)

I am new to Boolean Algebra and I'd just like to know: Is it possible to encode boolean logic into a matrix such that successive powers of that matrix perform logical computations? For example, given ...
0
votes
2answers
29 views

Absorption laws in Boolean algebra

Does anyone know how to prove the absorption laws in Boolean algebra? i.e. $$x + (x * y) = x$$ $$x * (x + y) = x$$ Thankyou so much
0
votes
5answers
42 views

Simplify (p v (r v q)) ∧ ~(~q ∧ ~r)

I understand that ~(~q ∧ ~r) simplifies down to (q v r), but I don't understand how the answer to this question is ...
0
votes
0answers
30 views

Boolean function: prime implicants - disjunctive minimal form

I applied the Quine-McCluskey method to determine the respective prime implicants for a boolean functions and find a disjunctive minimal form. We have the function \begin{equation*}f(x_1, x_2, x_3, ...
0
votes
0answers
21 views

Do Boolean Algebra,propositional logic,and set theory share laws of operation?

There's a lot of laws that have same ideas in Logic operations and operations of set. (Examples : I.$((P∧Q)∨R) = ((P∨R)∧(Q∨R))$ and $((A∩B)∪C) = (A\cup C)\cap(B\cup C)$,II.De Morgan's Laws.etc) ...
0
votes
0answers
35 views

Solving a system of linear equations of boolean values with magma [on hold]

Hello I´m new to magma and this site. My question is the following: I have a system of boolean variable in the following form which I get from a text file: $x_4+x_2+x_0$ $x_3+x_2+x_0+1$ $x_2+x_0+1$ $...
-1
votes
0answers
14 views

Need help with boolean expression simplification [closed]

The expression is ABCD + A'D' + AB'C'D + A'B'C' I know the answer is ABCD + A'D' + B'C'D But I have no idea how to solve it, Please help
1
vote
1answer
15 views

Relationship between algebras of sets

Let $\mathcal{N}$ and $\mathcal{M}$ be algebras of sets on $S$ and $T$ respectively. Let $\mathcal{N}\times\mathcal{M}$ the algebra generated by the rectangles in $S\times T$ (i,e the sets with the ...
0
votes
2answers
31 views

Subset proof, show A⊆B

So I was reviewing this question and Im lost on how to do this question, and Ive seen to of misplaced the notes. The question is as follows: if (A ∩ C) ⊆ (B ∩ C) and (A ∩ C̅) ⊆ (B ∩ C̅) then A ⊆ B ...
0
votes
0answers
15 views

Extension of a homomorphism on a boolean algebra into a complete boolean algebra

I'm trying to prove the following: Let $A$ be a subalgebra of a Boolean algebra $B$, let $u\in B$ and let $A(u)$ be the algebra generated by $A\cup\{u\}$. If $h$ is a homomorphism from $A$ into ...
0
votes
2answers
16 views

Antonym of the word nullity in the context of Boolean algebra

Depending on what axioms one uses to define a Boolean algebra, one result one can often show for a Boolean algebra $(S,+,*)$ is that for all $x \in S$, $x + 1 = 1$ and $x * 0 = 0$. I have seen some ...
1
vote
0answers
30 views

How to calculate the number $A_k(n)$ denoting the number of k-element anti chains in the boolean algebra $B_n$?

I.e., the number of subsets S of $2^{[n]}$ such that no element of S is a subset of another? How to prove: $$A_1(n)=2^n$$ $$A_2(n)=\frac 12(4^n-2\cdot 3^n)+2^n$$ $$A_3(n)=\frac 16 (8^n-6\cdot 6^n +6\...
0
votes
0answers
20 views

Is NOR a threshold function?

I'm studying threshold functions and am a bit stuck with x↓y. As I understand it, threshold functions return 1 when the sum of the weigths is greater than or equal to the threshold F and 0 when it's ...
0
votes
1answer
23 views

Transform the circuit of combinational logic into a boolean expression

We have the following: I want to transform this circuit of combinational logic into a boolean expression. The circles mean the negation and the symbol that is used is the symbol for AND, or not? ...
2
votes
1answer
64 views

Boolean algebra: Why does the equation hold?

I want to show that $$\bar y\land (x\lor z)\land (\bar x \lor \bar y) = \bar y\land (x\lor z)$$ I have done the following: \begin{align*}\bar y\land (x\lor z)\land (\bar x \lor \bar y) &=\bar ...
1
vote
0answers
25 views

sum of xor of all subarrays

I am adding a small program of two loops where i am getting problem ,I know this is not legal here but this was necessary to introduce my problem .Although i have linked the detailed explanation of my ...
0
votes
1answer
44 views

There are exactly $3^n$ possible monomials of $n$ Boolean variables?

In §2.2.1 of Introduction To Machine Learning: An Early Draft Of A Proposed Textbook, author Nilsson says about conjunctions of Boolean literals: It is easy to show that there are exactly $3^n$ ...
0
votes
0answers
56 views

“Either of which” - meaning

Stuck with a task in a LOGIC TESTS book. What "either of which" should mean? task about doors If meaning of "either of which" is exclusive OR then solution is straightforward: B bears a true sign ...
7
votes
0answers
87 views

Stone Duality: What are $\sigma$-Algebras Dual To?

Stone duality, one of many dualities between certain lattices and certain topological spaces, asserts that there is a contravariant categorical equivalence between the category $\text{Bool}$ of ...
0
votes
1answer
21 views

I'm confused about a boolean algebra simplification that somewhat resembles common identities

I am trying to simplify this equation: ( ' = NOT) 'AD+ACD+A'BC+ABCD The result I get is when using demorgan's and other rules is: ...
0
votes
1answer
24 views

Karnaugh MAP VS Boolean Algebra as Boolean Simplification Methods. Same Answer after simplification??

I've been having problems simplifying Boolean expressions with Boolean algebra and Karnaugh maps, I tried to simplify the same Boolean Expression using both ways but the two answers I got were ...
0
votes
1answer
53 views

Simplify statement using the laws and axioms of logic.

I am trying to do logic expression simplification using boolean algebra laws and axioms of logic, but I don't understand it at all. I attempt the question and this is what i have come up with. the ...
2
votes
0answers
30 views

Cycle length of K-ary Boolean function

Boolean networks have been extensively studied, however I didn't find a reference to the following problem. May be you can provide one, or give hints to a possible solution. Define K Boolean ...
0
votes
0answers
6 views

Prove that $\hat{\alpha}$ is a base of $2^\mathbb{P}$

Let it be $\mathbb{P}$ a set of propositional letters and $\phi$ a set of formulas generated by $\mathbb{P}$. Consider the space $2^{\mathbb{P}}$ with the product topology, and define for every ...
0
votes
1answer
37 views

How could I proceed in proving that a Lindenbaum algebra is atomless?

Given a $P$ infinite set of propositional variables we consider the Lindenbaum algebra generated by $P$. Then is this algebra atomless?
2
votes
1answer
55 views

If every truth assignment satisfies some wff, some finite disjunction is a tautology

Let $X_1,X_2,X_3,...$ be well formed formulas. If for every truth assignment $v$ there exists $n$ with $X_n$ satisfied by $v$, show there exists $n$ with $X_1\lor...\lor X_n$ a tautology. We can ...
0
votes
0answers
12 views

How to finding minterm from 5 var Boolean Expression that having 4 terms

I have this question for my assignment and I am not getting that how can we find the minterms of this expression. It has 4 terms, it is 5 variable expression and it contains NAND. i need the minterms ...
0
votes
0answers
30 views

How can this boolean expression be simplified?

I would like to have a step-by-step simplification of this boolean expression $\bar{x}\bar{y}\bar{z}\bar{w}+\bar{x}\bar{y}z\bar{w}+\bar{x}yz\bar{w}+\bar{x}yzw+x\bar{y}\bar{z}\bar{w}+x\bar{y}z\bar{w}+x\...
3
votes
2answers
81 views

Singletons in the $\sigma$-algebra generated by clopen sets of a Stone space

Let $A$ be a Boolean algebra and let $Ult(A)$ be its Stone space, that is, the set of all ultrafilters on $A$. It is well known that $C=\{\{u\in Ult(A)\!:a\in u\}\!:a\in A\}$ is an algebra of sets ...
0
votes
2answers
38 views

How to prove “ If (A is included in B) then (A Intersection Complement of B is equal to the null set) ” using only set algebra laws?

This statement is quite easy to prove using logic ( and the constant F = " Falsum" = the proposition equivalent to any logical falsehood). But I cannot manage to prove it simply with the laws of the ...
0
votes
1answer
21 views

Converting Four Variable OR to NOR (using only NOR GATE)

I want to convert a four variable OR (i.e. OR(A,B,C,D)) to NOR. I did this using 6 two variable NOR like the picture below. but I think it can be done easier. Can anyone suggest any way to do this and ...
0
votes
1answer
14 views

$\bar{A}\bar{B}+A\bar{B}\bar{C} \equiv \bar{A}\bar{B}+\bar{B}\bar{C}$

When simplifying an expression I managed to get as far as the left hand side of the below. $$\bar{A}\bar{B}+A\bar{B}\bar{C} \equiv \bar{A}\bar{B}+\bar{B}\bar{C}$$ The answer was the right hand side. ...
0
votes
0answers
12 views

Is $F\mapsto \overline{\pi_X(intF)}$ boolean mononorphism?

Let $X$ be a Hausdorff compact and let $(EX,\pi_X)$ be it's projective cover, i.e. $EX$ is the Stone space of the boolean algebra of the Regular Closed subsets of $X$ and $\pi_X$ maps each ultrafilter ...
-1
votes
1answer
41 views

Simplification of logic circuit using algebra

The following is the logic circuit: I have to simplify the following: (((AB)')'+(B+C)+(AB)'(B+C)')C =(AB+B+C+(A'+B')(B'C'))C =(B+C+A'B'C'+B'C')C =BC+C+A'B'C+B'C =C+A'BC'+B'C
0
votes
0answers
43 views

Is there some way to transform statements in predicate logic/ first order logic to an expression in the integers mod2 and evaluate?

As the title says, I want to turn a statement such as (P AND(P->Q)) - >Q into a multivariable polynomial in the field Z/2Z and evaluate using the rules of modular arithmetic to get (hopefully) 1, ...
1
vote
0answers
20 views

Size of a boolean vectorial subspace

We know that a boolean vectorial space of dimension n is defined by all posible n-tuples formed by 0 or 1 in each position (note this set is finite), and adding to this set the operations of: ...
-1
votes
1answer
18 views

Boolean algebra Simplification of “xy'+xz+x'y+yz+z" [closed]

F = x'y'z' + xyz' F' = (x+y+z)(x'y'z) F = x'y + xy' + z How can this display?
0
votes
1answer
11 views

Finding SOP form of function f

An exercise says : Use algebraic manipulation to find the mimimum SOP expression for the function $$f = x_1x_3 + x_1x_2' + x_1'x_2x_3 + x_1'x_2'x_3'$$ The given solution says: $f = x_1x_3 + x_1x_2' +...
2
votes
2answers
57 views

Simplification of the boolean expression

Simplify the following expressions to the simplest expression using De Morgan's theorem and Boolean algebra. AB+(C+B')(AB+C') =AB+ABC+CC'+ABB'+B'C' =AB+CC'+A+B'C' =A+CC'+B'C' =A+B'C'
1
vote
1answer
32 views

Example of Stone space such that …

Suppose $X$ is a totally disconnected compact Hausdorff space and $F_1,F_2,F_3$ three finite subsets of $X$. I would like to know if $F_1 \cap F_2 \cap F_3 = \emptyset$ implies that there exists ...
1
vote
0answers
21 views

Truth table for digital circuit using multiplexers

I need to draw a truth table but I don't understand what logic functions I should use in order to complete the truth table. Can someone give me a hint or push me in the right direction?
0
votes
0answers
24 views

How to interpret the $\oplus$ operator over a range of boolean variables

Suppose that I have a set of boolean variables $x_1,x_2,...x_n$. How do I interpret the following function: $$ f(x_1,x_2,...x_n) = \oplus_{i=1}^nx_i $$ i.e. $f(x_1,x_2,...x_n) = x_1\oplus x_2\oplus ...
1
vote
1answer
33 views

Sum of products expression using Karnaugh maps

Use a Karnaugh Map to simplify the following Sum of Products expression, where A is the most significant bit of each component and C the least significant: Y = ∑(0,2,3,6,7). The answer is suppose to ...
1
vote
1answer
45 views

Simplification of the expression using De-Morgan's rule

Simplify the following expressions to the simplest expression using De Morgan’s theorem and Boolean algebra. ¬(A(¬(B+¬C))D)=¬(AD(¬(B+¬C)) ...
0
votes
2answers
40 views

Simplification of the boolean expression with XOR

I need to simplify the following boolean expression ¬A¬B¬C + (B ⊕ C) + A¬B I know B⊕C = ¬BC + B¬C Then the expression will become ¬A¬B¬C +(¬BC + B¬C) +A¬B However, I'm stuck on it and I don't ...
0
votes
0answers
10 views

Implement 4-variable boolean functions using a 2x4 decoder and a 2-bit magnitude comparator

As mentioned, I am given a 2x4 decoder and a 2-bit magnitude comparator. I am to implement the following 4-variable Boolean functions using either or both. The use of any other logic gates is ...
0
votes
0answers
63 views

Proof of the duality principle in Boolean Algebra

I have looked at some proofs of the duality principle online, and those use a lot of algebra which I do not understand. Is there a simple proof of the duality principle? I know the basic laws, ...
1
vote
1answer
29 views

Prove tautology using propositional equivalence and the laws of logic determine

q ∧ ( p → ¬q) → ¬p q ∧ ( ¬p ∨ ¬q) → ¬p (q ∧ ¬p)∨ (q ∧ ¬q) → ¬p (q ∧ ¬p)∨ F → ¬p i dont know how to solve this further. Kind of leaves me confused what would be ...
1
vote
1answer
23 views

OR equality constraint for binary integer program

I am trying to find a way to implement an OR equality constraint in a Binary Integer Program. For example, say I want to add the following logical condition to the program: $$x_1+x_2+x_3+x_4+x_5 = 1\...
0
votes
1answer
36 views

Problem finding SOP form of f + g

I have a project and I am asked to find the sop form of f+g and find its cost and then compare it to the cost if I implement f and g separately. I am trying to find SOP form of f+g and I am stack ...