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.
1
vote
2answers
53 views
Partially Ordered Sets question
For $m\in\mathbb{N}$, which integers are covered by $m$? I've been playing with the prime factors of $m$ and I can't seem to see any pattern. Can anyone help?
1
vote
1answer
78 views
Reduce following expression to one literal, boolean algebra
$$W'X(Z'+Y'Z)+X(W+W'YZ)$$
The goal is to reduce the following to one literal
So after I expanded it out, i got the following:
$$W'XZ'+W'XY'Z+WX+W'XYZ$$
Now from here, I got stuck and didn't know ...
2
votes
3answers
48 views
How can I prove this logical expression?
I've already confirmed that the following expression is true with a truth table, but I need to prove this with other Boolean expressions for my assignment. The $\oplus$ symbol is exclusive or in this ...
3
votes
1answer
166 views
Designing a circuit: Hamming Code
How would I design and build a circuit that would generate check bits for 4-bit word?
In this instance, the same circuit should also be used to generate check bits for when you read data back in case ...
-1
votes
1answer
62 views
Desiging a circuit that implements Hamming Code
How would I design and build a circuit that would generate check bits for 4-bit word?
In this instance, the same circuit should also be used to generate check bits for when you read data back in ...
2
votes
5answers
93 views
Value of $(a=1) \wedge (b=1) \wedge (c=2)$ given $a=1$, $b=2$ and $c=2$
How would I solve the following question.
Assume $a=1$, $b=2$ and $c=2$ what is the value of the following Boolean expression
$(a=1)$ AND $(b=1)$ AND $(c=2)$
I am kind of confused because I know ...
0
votes
3answers
143 views
Simplifying Boolean Algebra
I am trying to prove that BC + !A!B + !A!C = ABC +!A
I have attempted using De Morgan laws, and substituting X for !A!B and ...
0
votes
0answers
19 views
Binary Subtraction for two unsigned integers [duplicate]
For unsigned integers X = 00110101 and Y = 10110101 determine the value for:
X-Y = ?
I know that this would come out to -10000000...but since X and Y are unsigned integers then it cannot be a ...
-2
votes
1answer
150 views
Boolean Algrebra: Karnaugh Map
Using the Karnaugh map, express the following function:
F(0, 1, 4, 5, 8, 10, 11, 12, 13, 15)
0
votes
1answer
58 views
Boolean Algebra proving algebraically simple
$$(X'+Y
)(X+Y')=XY+X'Y'$$
I am just wondering how these are equal, and what laws are used to get there
-4
votes
1answer
177 views
Boolean Algebra (Help Needed)
How would I draw the gate-level logic circuit of the following Boolean expression?
$$
(((A \land B \lor C) \lor D \land E \land F) \lor G \land (H \lor I \land J)).
$$
Then how would I implement this ...
-4
votes
4answers
115 views
How to show Boolean identity : $(ab + c + d)(c' + d)(c' + d + e) = abc' + d$
How to show Boolean identity : $(ab + c + d)(c' + d)(c' + d + e) = abc' + d$
0
votes
2answers
44 views
Conjunctive normal form of logical expression
I tried to convert this to a CNF-expression but failed.
What did I do wrong? Or are there simply missing steps?
$$ F' = (( A \lor \lnot B) \land C) \to ( \lnot A \land C) $$
Removed Implication
$$ ...
1
vote
1answer
68 views
Prove the identity in this boolean equation
$$AD'+A'B+C'D+B'C=(A'+B'+C'+D')(A+B+C+D)$$
Don't know where to begin with this.
2
votes
2answers
39 views
How do we know what $A$ or $B$ or $C$ is after simplifying?
I understand the basics of boolean algebra and how to simplify them. What I am confused about is how do we know what to call a value after simplifying? Imagine we create a boolean algebra expression ...
1
vote
1answer
435 views
Boolean Algebra, 4-variable Expression Simplification
I have the following Boolean expression:
$$w'x'y'z + wx'y'z + xz + xyz'\tag{1}$$
Upon doing my own work, I can only get as far as:
$$zx + xy + zy'\tag{2}$$
Now, when I put the original equation ...
0
votes
1answer
148 views
Simplify the following expression using Boolean Algebra into sum-of-products (SOP) expressions
Simplify the following expression using Boolean Algebra into sum-of-products (SOP) expressions
$Q.S.U + (Q' + S').(R + V) + U.(R + V) + Q' + S.T.U$
$.$ = AND
$+$ = OR
This is what I have so far
...
2
votes
1answer
42 views
Incompleteness of Connectives
I’m currently trying to learn more about Mathematical Logic and have reached a sticking point. I also have the solutions to the problems I’m working through and I usually don’t need to ask for help to ...
2
votes
1answer
325 views
Boolean Algebra - Product of Sums
I converted from a truth table to sum of products and simplified that easily. What I am having problems with is simplifying the product of sums for that same truth table. I have:
NOTE: $A' = ...
2
votes
2answers
104 views
Logic gates analyses
How to write the output of the gates not, and, or, xor, nand and nor in terms
of their inputs, expressed as zeros and ones, using base 10 addition and
multiplication.
Thanks much in advance!!!
0
votes
1answer
72 views
1
vote
1answer
32 views
How can I express xNORy solely with NAND operations?
I've tried every which way I can think of to manipulate the algebra using the various laws I was given, but I cannot figure out a way to get $\overline{x+y}$ to convert to only NAND operations using ...
1
vote
1answer
51 views
Atomic Boolean lattice is weakly atomic
The book "Introduction to Lattices and Order" says at Exercise 10.12 that an atomic Boolean lattice is weakly atomic.
Could you tell me why it holds?
1
vote
2answers
56 views
Construct countable Boolean algebra
How can I construct a countably infinite Boolean algebra with $n$ atoms, for $n \in \mathbb{N}$?
1
vote
3answers
330 views
Prove XOR is commutative and associative?
Through the use of Boolean algebra, show that the XOR operator ⊕ is both commutative
and associative.
I know I can show using a truth table.
But using boolean algeba?
How do I show? I totally have ...
2
votes
2answers
396 views
Simplifying the following expression using Boolean Algebra
Simplify the following expression using Boolean Algebra into sum-of-products (SOP) expressions
. refers to AND
+ refers to OR
a'.b'.c' + a.b'.c' + a.b.c'
This is what I have so far.
a'.b'.c' + ...
0
votes
1answer
579 views
How to convert between Sum Of Products and Product of sums?
I have a Boolean expression. we'll call it F.
for instance, F = ab' + ad + c'd + d'.
Assuming I did all the necessary steps ...
0
votes
2answers
65 views
Simplifying the expression using Boolean Algebra Part 2
Simplifying the expression using Boolean Algebra into sum-of-products (SOP) expressions . refers to AND + refers to OR
Updated with new question
( (a + b) ∙ (a' + c') )' + (b + c')' + a∙b'∙c
= ( (a ...
1
vote
1answer
92 views
Simplifying the expression using Boolean Algebra
Simplifying the expression using Boolean Algebra into sum-of-products (SOP) expressions
. refers to AND
+ refers to OR
(y' + x) ∙ (z + z') ∙ (y' + x') + (z + x'∙z) ∙ (x + y)
This is what I have so ...
0
votes
0answers
34 views
Booleans: Solve Algebraically
Prove using Prove algebraically :
1) x'′⊕ y = x⊕y' = (x⊕y)'
2) x⊕1 = x'
3) x⊕x' = 1
4) (A+B)(A'C'+C)(B'+AC') = A'B
$(A+B)(A'.C'+C)(B'+AC)' = A'B$
I know x⊕y = xy'+x'y But how do i deal with X'⊕Y? ...
0
votes
0answers
60 views
Representation of Boolean algebras
Stone's representation theorem states that every Boolean algebra is isomorphic to an algebra of point sets.
Loomis-Sikorski theorem states that ''every $\sigma$-complete Boolean algebra is ...
5
votes
0answers
76 views
Non-isomorphic countable Boolean algebras
I'm trying to solve the next exercise:
Construct a sequence $\mathcal{B}_0,\mathcal{B}_1, \ldots$ of countable Boolean algebras such that for all $m \neq n$ then $\mathcal{B}_0 \ncong \mathcal{B}_1$.
...
0
votes
0answers
56 views
Truth table for X = A.(B+C)'?
I have been beating my head on this for hours. I'm pretty certain that I've done it correctly, but my Quartus II simulation seems to disagree.
My Boolean expression: X = A.(B+C)'
My truth table ...
0
votes
2answers
27 views
Boolean Simplification: Identifying a rule
I'm in the process of minimizing a boolean equation, and I've gotten it into the following form:
$$\lnot B \lor (B \land \lnot C) \lor C$$
Just by looking at it, I can tell that this is always ...
0
votes
2answers
226 views
Product of Sums to Sum of Products
I apologize if this is a dumb question, but I'm having some trouble seeing how we can go from the Boolean equation
...
0
votes
1answer
39 views
Represent the three element chain as a subdirect product of subdirectly irreducible lattices.
Represent the three element chain as a subdirect product of subdirectly irreducible lattices.
I know the two element chain as either a Boolean algebra or a semilattice,is subdirectly irreducible.In ...
0
votes
1answer
63 views
Help with simplifying boolean functions algebraically
I have 2 boolean functions that I am having some difficulty solving algebraically.
NOTE: ~ means NOT, & means AND, + means OR
1) $(\sim b~\&~\sim d)+(b~\&~\sim ...
0
votes
1answer
114 views
The input represent a 4-bit unsigned binary number, the output W, is 1 if the number is multiple of 2 or 3 but not both.
I completely understand how to make a truth table and the entire concept of boolean algebra. However, I am confused how to make the truth table for the above information. Because the input is a 4-bit ...
0
votes
2answers
154 views
Boolean Algebra equivalency
Which Boolean algebra laws are required to show that
$$(\lnot y \land \lnot z) \lor (x \land ((\lnot y \land z) \lor (y \land \lnot z))) = (\lnot y \land \lnot z) \lor (x\land (\lnot (y \land ...
5
votes
1answer
113 views
Example of Boolean Algebra that satisfies distributive law but violates complete distributive law
More precisely, I'm interested to know the example of Boolean Algebra $B$, such that for any $a, b, c \in B$, $a \cap (b \cup c) = (a \cap b) \cup (a \cap c)$, but there exists $\{ P_{ij}:i\in I, j ...
2
votes
1answer
72 views
Number of non degenerate boolean functions
I got in my lecture the formula that describe the number of nondegenerate Boolean functions of $n$ variables (or how many boolean functions have no fictitious variables), but we don't have proof for ...
1
vote
1answer
150 views
Fiction variables?
In every Boolean function $f(x_1, x_2,\ldots, x_n)$, for every $i$ ($1\le i\le n$), $x_i$ is called fiction variable if and only if when for every Boolean assessment for the rest variables $x_1, ...
1
vote
1answer
100 views
Composition of boolean function
In this problem we describe the boolean functions of $n$ variables like a vectors with lenght $2^n$ with standard assumption that $k$-th component of the vector $0\leq k \leq 2^n -1$ is thе value of ...
4
votes
2answers
177 views
Hypercube problem
$B$ is an n-dimensional hypercube, considered as undirected graph. Let $A$ be a subset of the vertices of $B$ such that $|A| \gt 2^{n-1}$.
Let $H$ is a subgraph of $B$ induced by $A$. Prove that $H$ ...
5
votes
3answers
172 views
Counting Rows of a Truth Table that Satisfy a Condition
How can I mathematically count the number of rows in a truth table of n-inputs that will satisfy a certain boolean condition?
For example, say I have a 4-input truth table that will in turn have 16 ...
0
votes
1answer
124 views
An exercise of Boolean algebras
On page 87, Introduction to Boolean Algebras,Steven Givant,Paul Halmos(2000)
Give an example of a subalgebra $B$ of a Boolean algebra $A$
and of a subset $E$ of $B$ such that $E$ has a supremum ...
1
vote
2answers
250 views
How to prove that a set of logical connectives is functionally complete(incomplete)?
How to prove that a set of logical connectives is functionally complete(incomplete)?
For example, we are given this set:
$
\left\{\begin{matrix}
f = (01101001) \\
g = (1010) \\
h = (01110110) \\
...
0
votes
0answers
43 views
Question regarding implicant chart of Quine-McCluskey algorithm
In https://en.wikipedia.org/wiki/Quine-McCluskey#Example, at the end of Step 1, there is a table that shows the number of 1's, minterms, 0-cube and size-2 implicants and size-4 implicants. But I am ...
2
votes
1answer
112 views
Infitive distributive law in boolean valued models
I'm posting the problem 2.14 and 2.15 of the book "Set theory" of J.L. Bell. These problem are proposed after the forcing relation chapter and I'm new in this kind of stuff, so I have some little ...
3
votes
2answers
80 views
Prove $(x+yz)(y'+x)(y'+z')=x(y'+z')$ in Boolean algebra
How can we prove $(x+yz)(y'+x)(y'+z')=x(y'+z')$ in a Boolean algebra $B$?
