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
1answer
32 views
completeness and saturation
Let $B$ a complete Boolean algebra. Suppose, for $\kappa$ cardinal, that $B$ is not $\kappa$-saturated. Then there exists a partition $W$ of $B$. Because of completeness, we have $B=\sum W\in B$. So ...
4
votes
2answers
74 views
Which law of logical equivalence says $P\Leftrightarrow Q ≡ (P\lor Q) \Rightarrow(P\land Q)$
I'm going through the exercises in the book Discrete Mathematics with Applications. I'm asked to show that two circuits are equivalent by converting them to boolean expressions and using the laws in ...
1
vote
1answer
51 views
Isomorphism Subalgebra
Given, the unit interval $I$ endowed with the Lebesgue measure $\mu$, and let $A$ be the (Boolean) algebra of Jordan measurable subsets of $X$ with respect to $\mu$, (i.e. those sets that satisfying ...
4
votes
3answers
132 views
Rationale behind truth values
I originaly asked a question on Programmers.SE to know why $0$ was consider $\text{false}$ and all the other [integral] values were considered $\text{true}$. That was a huge debate and many said it ...
0
votes
2answers
27 views
Generalization of Boolean OR?
I have been looking at the Boolean OR function and Im trying to find its integral analogue.
What I mean is:
Boolean AND (x, y) where x and y are Boolean Values with 0 = False, 1 = True is equivalent ...
3
votes
2answers
42 views
Reducing Boolean expressions
Just learning mathematical proof writing and came upon this interesting question Writing an expression using logic.
$$(P \land Q \land \lnot R) \lor (P \land \lnot Q \land \lnot R) \lor (\lnot P ...
10
votes
2answers
257 views
A matrix w/integer eigenvalues and trigonometric identity
Any intuition and/or rigorous arguments on the proofs of the following statements would be appreciated:
Let $n$ be a natural number.
(a) Consider the following Toeplitz/circulant symmetric matrix:
...
2
votes
0answers
27 views
Inferring simplest method to convert bit array 1 to bit array 2.
Consider the set of all bit arrays of length $n$. Now consider the set of all 1-to-1 functions that map from this set to this set.
Now select a single function out of the latter set. Is there any ...
0
votes
0answers
21 views
A problem on duality of boolean algebra
A Boolean function $f_1^{D}$
is said to be the dual of another Boolean
function $f_1$ if $f^{D}_1$ is obtained from $f_1$ by interchanging the operations
$+$ and $.$, and the constants $0$ and $1$.
A ...
3
votes
1answer
34 views
Boolean Algebra Transform
I am revisiting Boolean algebra after a long while.
Can somebody help show me how to simplify the LHS to get the RHS?
$$abc * a'bc + (abc)' * (a'bc)'\quad = \quad \;b'+c'$$
2
votes
1answer
28 views
Filters of Boolean algebras which are Boolean algebras
Looking at some filters generated by elements of a finite Boolean algebra I have the impression that many/most/all of them are by themselves Boolean algebras (at least I didn't stumble upon a ...
1
vote
1answer
52 views
0
votes
1answer
24 views
How do we go about factorizing boolean expressions?
How do we know how to go about factorizing a boolean expression when there are so many ways?
For example, the factorized form of $ABC + A'B'C'$ is $(A + C')(B' + C)(A' + B)$, but how do we know how ...
1
vote
1answer
25 views
Boolean Equation Transformation
Can someone show me the steps in getting from $f = (ab + c')(d' + e + f')$ to $f = abe +ab(df)' + c'e + c'(df)'$? I am trying to relearn Boolean algebra after a long hiatus.
1
vote
2answers
59 views
Prove that $(S \cap T = \varnothing) \land (S \cup T = T) \rightarrow S = \varnothing$.
Logically, the following proposition makes sense:
$(S \cap T = \varnothing) \land (S \cup T = T) \rightarrow S = \varnothing$
Or, in english, if sets $S$ and $T$ share no elements, and the union of ...
0
votes
0answers
31 views
Karnaugh map question $\displaystyle \sum_{} (2,3,6,7) $
I can't write here the map of Karnaugh of this function so I just ask whether this reduction goes after Y?
$F(w,x,y) =\displaystyle \sum_{} (2,3,6,7) $
In addition if there are two functions like: ...
2
votes
1answer
59 views
Measure on Boolean algebra
my question is:
Suppose that $\mathfrak{B}$ is a measurable Boolean algebra, does this mean that "Every measure on $\mathfrak{B}$ should be strictly positive ? or this will be the case after ...
1
vote
1answer
29 views
Simplify Expression Question
Anyone can tell me if I can simplify this expression more?
I Simplified this function => $minterm(1,3,4,6,7,9,10,11,12,15)$ to this expression:
$W'X'Z+W'Z'X+WYZ+W'XYZ+WX'Y'Z+WX'YZ'+WXY'Z'$
Thanks!
0
votes
0answers
17 views
Write the following functions in algebraic sum of multiples or multiplying Amounts. If possible,simplify the expression
Write the following functions in algebraic sum of multiples or multiplying Amounts. If possible,simplify the expression
The Question is:
$F(A,B,C): Maxterms(4,5,6,7)$ :
$M4 = 100 => A'+B+C $
...
0
votes
1answer
19 views
Single variable true or false statements
If I have a true or false statement S, depending on a varible x, is there some standard function or opperation in formal logic, that takes the statement S and the variable x, and outputs $1$ if ...
0
votes
0answers
14 views
What is the order of steps when simplifying functions with NOT
What is the order of steps when simplifying functions with NOT
I need advice on simplifying the following function, I have a function with several stages of NOT, Do I followed the steps?
Thanks!
0
votes
1answer
18 views
Expressions Simplifications Boolean Algebra
Expressions Simplifications Boolean Algebra
I started simplifying function and got to the detailed picture and wanted to know if I can reduce the above expressions, for example :
Y'.X'.Y = 0 ?
...
0
votes
2answers
35 views
Boolean Algebra Simplification Question - Proof of equation
Boolean Algebra Simplification Question - Proof of equation
I`m trying to proof this equation:
X'.Y' + Y'.Z + X.Z + X.Y + Y.Z' = X'.Y'+X.Z+Y.Z'
What your are suggesting? to add some
...
2
votes
0answers
35 views
Basis of a Boolean Algebra
I have a construct that I proved forms a (finite) Boolean Algebra of sets over a given universe.
My questions are as follows:
Do I immediately know that there exists a unique basis for it?
If yes, ...
0
votes
2answers
35 views
Simplifying boolean expression: $!(x!z+y!z+xy+z)$
This is the expression:
', ! not+ or
$((x'y'+z)'+z+xy+wz)'$
After some steps I can get
$!(x!z+y!z+xy+z)$
How can I continue from here?
8
votes
1answer
138 views
Stone's Representation Theorem and The Compactness Theorem
If you're working on $ZF$ and you assume the compactness theorem for propositional logic, then you have the prime ideal theorem, and thus you can show that the dual of the category of Boolean algebras ...
1
vote
1answer
54 views
Free algebra (Boolean algebra)
Could someone give me a simple explanation of Free Algebra on $\kappa$. How to construct free($\omega$).
here is it says
http://en.wikipedia.org/wiki/Free_Boolean_algebra
free($\omega$) is equal to ...
2
votes
2answers
75 views
How to prove that $(A \lor B) \land (\lnot A \lor B) = B$
I know this is fairly basic, and I understand that it becomes
$$
\begin{align}
(A \land \lnot A) \lor B \\
F \lor B \\
B
\end{align}
$$
However, I can't work out how to prove that it becomes that ...
2
votes
1answer
60 views
Can boolean homomorphisms of boolean algebras correspond to ultrafilters?
I am trying to solve 5th problem in Exercises 2.9 in Awodey's book on page 55:
Show that for any boolean algebra $B$, boolean homomorphisms $h :
B \to 2$ correspond exactly to ultrafilters in $B$.
I ...
3
votes
1answer
41 views
How do I find the size of this set?
For homework, I need to show that the size of a certain set is $\le 2^{(3n)^k}$ but I'm not getting this (I think I may just misunderstand how the set is defined).
So the set is defined as follows:
...
2
votes
1answer
40 views
Boolean Algebra Question
my problem is ,Please give the algorithm: how can rewrite an arbitrary propositional formula alfa(α) into a proposional formula beta(β) so that beta does not contain disjunction(∧) and alfa ...
0
votes
0answers
46 views
Is the choose function polynomial?
I have this problem which is described as follows:
Input:
You are given a multi-set M (a set that can contain duplicates), and two numbers P and T.
$ M = {(x_1,y_1), (x_2,y_2), ..., ...
1
vote
1answer
43 views
Is it true “Every Boolean algebra is an algebra of sets, for any given set X”
I have confused between these two notions, please help
Every Boolean algebra is an algebra of sets, for any given set $X$, and the converse is false.
0
votes
1answer
63 views
How can you design a 3 bit adder using a 4 bit adder?
How can you design a 3 bit adder using a 4 bit adder?
The description and/or the circuit's scheme would be great.
1
vote
1answer
134 views
Proof of Associativity in Boolean Algebra
I must prove the most basic associativity in boolean algebra and there is two equation to be proved:
(1) a+(b+c) = (a+b)+c (where + indicates OR).
(2) a.(b.c) = (a.b).c (where . indicates AND).
I ...
1
vote
1answer
42 views
Trouble understanding boolean logic proof.
*Find the complement of $F=x+yz$; then show that $FF’ = 0$ and $F + F’ = 1$
$F(x,y) = x+yz$
$F’(x,y) = (x+yz)’ = x’(yz)’ = x’(y’+z’)$
$FF’ = (x+yz)x’(y’+z’) = (xx’+x’yz)(y’+z’) = x’yz(y’+z’) = ...
2
votes
2answers
26 views
Get A⊕(B+1) from A⊕B
I have numbers A,B,C.D.
(⊕ is XOR)
C = A⊕B
D = A⊕(B+1)
Is there any way to get D from C, when I do not know A and B? How?
Thanks for help!
1
vote
1answer
86 views
Implement using only XOR gates F=A'B'C'D+A'B'CD'+A'BC'D'+A'BCD+AB'CD
How can we implement the function:
F=A'B'C'D+A'B'CD'+A'BC'D'+A'BCD+AB'CD
without simplifying it and using ONLY XOR gates (not using AND/OR gates) ? NOT gates are usable too, since they can be ...
0
votes
1answer
54 views
Software to Find Kernels/Co-Kernels of Boolean Expressions
Is there any (free) software available that calculates all the possible kernel/co-kernel pairs of a boolean expression?
0
votes
1answer
41 views
Memory and bits. Need some help
Could someone check over my answers to verify I am correct.
Say we have a memory consisting of 2048 locations, and each location contains 16 bits.
◦ A) How many bits are required for the address? ...
0
votes
1answer
37 views
LC-3 instruction set. Help needed
Using only one LC-3 instruction, how would I move the value in Register 2 into Register 3
How to perform R1 = R2 - R3 using only 3 LC-3 instructions?
Hope you can help. Thanks
0
votes
1answer
46 views
Memory and bits
If a memory's addressability is 64 bits. What does that tell you about the size of the memory address register (MAR) and memory data register (MDR)?
2
votes
2answers
41 views
finding signs of 3 numbers
This is slightly more of a coding problem than a math problem but I think it is still relevant.
So let's say I have 3 numbers A,B,C and I can only call a given function if two are negative and one ...
2
votes
2answers
61 views
Proving if Boolean Equations are valid
I need to prove algebraically that:
$$ab + abc'd + abde' + abc'e + a'b = b$$
$$(wxyz)(wxyz' + wx'yz + w'xyz + wxy'z) = 0$$
1
vote
0answers
54 views
Showing that a Boolean algebra is a Boolean ring
I've proved that a Boolean ring is a Boolean algebra but I am having trouble with the converse. The operation for + is defined as the symmetric difference for elements $a$ and $b$ from the Boolean ...
1
vote
1answer
61 views
Simplify $F=MNO+Q'P'N'+PRM+Q'OMP'+MR$
How can we simplify $$F=MNO+Q'P'N'+PRM+Q'OMP'+MR$$ using the theorems of boolean algebra, not Karnaugh or anything else?
Well, I can obviously simplify $MR(P+1)=MR$, so the expression becomes ...
0
votes
1answer
32 views
Is there a unique minimal expression for every boolean function?
Is there a unique minimal expression for every boolean function?
I've heard that there are some boolean expressions for which the minimal form is not unique. What are the characteristics of this kind ...
3
votes
3answers
472 views
De-Morgan's theorem for 3 variables?
The most relative that I found on Google for de morgan's 3 variable was: (ABC)' = A' + B' + C'.
I didn't find the answer for my question, therefore I'll ask here:
...
0
votes
2answers
81 views
Binary Operations on Subsets--Two Questions
I have two questions about the properties of binary set operations that I am having difficulty arriving at answers that I completely trust (though I am sure they are not difficult questions). Here ...
0
votes
0answers
59 views
M-generic, transitive model and Boolean-valued model
$M$ is defined as a model of ZFC set theory. This
is Boolean-valued model question: how does one
prove that ultrafilter $U$ being M-generic leads to
the fact that $M^{\mathbb{B}}/U$ has isomorphic ...
