Tagged Questions

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. For Boolean logic use the tag propositional logic

learn more… | top users | synonyms

1
vote
3answers
464 views

Is “(p AND q) OR r” logically equivalent to “p AND (q OR r)” ??

In the context of discreet math / boolean algebra / logic, is "(p AND q) OR r" logically equivalent to "p AND (q OR r)"? I believe so, but my professor said: ...
1
vote
2answers
281 views

Proving boolean algebra property

Let $S$ a boolean algebra; $a,b,c \in S$ prove that $(a'+b)'+(a'+b')'=a$ Then: $(a'+b)'+(a'+b')'= (a')'+b'+(a')'+(b')'=a+b'+a+b = (a+a)+(b+b')=a+1=1$ Maybe i'm wrong but I think that the problem is ...
-1
votes
1answer
101 views

Simplification of boolean expressions

Question 1 $$\begin{align*}A'BC + AB'C + ABC + A'B'C' &=A'B C + B' C (A +A') + ABC\\ &=A'B + C + B'C + ABC \end{align*}$$ Question 2 $$\begin{align*}A'B + B'C + CB &=A'B + C(B +B')\\ ...
1
vote
1answer
3k views

Boolean-expression simplification $F = AB'C + (A'B' + ABC'D)'$

Here are my solutions. Hence: I am stuck on where or what path I am going to take Problem: F = AB'C + (A'B' + ABC'D)' Solution 1 --------------- F = AB'C + (A'B' + ABC'D)' = AB'C + (A'B')' (ABC'D)' ...
1
vote
0answers
24 views

Proving a boolean algebra question [duplicate]

Let $\sqsubseteq$ be a boolean ordering of the boolean algebra $X$, which means that for each $x$ and $y$ the following applies: $x \sqsubseteq y$ if $x \sqcap y = x$. Let $v, w, a, b \in X$ with $v ...
2
votes
0answers
94 views

Matrix of integers to boolean matrix

My Question is about converting a matrix of numbers, say each row is an item and each column is a feature of the item. The features are currently integers but I want to convert the feature ...
1
vote
1answer
239 views

Check if tautology (w/o truth table)

$(A+B)(A+C)(B+C) = AB + AC + BC$ is a tautology (checked with Wolfram Alpha) and not hard to see if you apply duality principle $(invert + * 0 1)$ But how to prove with simplyfication It'S not much ...
2
votes
2answers
64 views

Ist it a tautology w/o truth table

AB + CD = (A+C)(A+D)(B+C)(B+D) is a tautology (checked with wolfram alpha) I have to prove this whith boolean algebra but I don't get it right. That'S what I have: AB + CD = A(C+D)B(C+D) AB + CD = ...
0
votes
1answer
25 views

Create a simple expression that is larger than zero if and only if a-b > 0 and c-d < 0

Ok, this is simple but I cant figure out a solution to it. I have four signals, a, b, c, d. I want to generate a signal when a-b > 0 and c-d < 0. This signal should be in the form of an algebraic ...
0
votes
1answer
146 views

Using induction to prove universality of gate

Can we use induction to prove gate(like NAND) is universal. If so how?
1
vote
1answer
44 views

Are ordinal spaces extremally disconnected?

The wikipedia article on ordinal spaces claims that they are not extremally disconnected: However, they are not extremally disconnected in general (there is an open set, namely $\omega$, whose ...
3
votes
1answer
43 views

Looking for an algebraic structure

I'm looking for the name of algebraic structures (in which the elements are partially ordered) with the following properties: Top element defined, bottom optional; Join defined for all elements, ...
1
vote
3answers
3k views

Boolean Algebra: Simplifying multiple XOR and XNOR

Is there any way to simplify a combination of XOR and XNOR gates in the following expression? I have tried multiple boolean theorems and I have not been able to simplify this any further: The ...
-1
votes
1answer
69 views

Product of Sums Minimzation. Please help! [closed]

Minimize the product of sums expression. (x + y + z!)(x + y! + z)(x + y! + z!) Please help! I am not sure whether to factor out by grouping or to factor out a x etc.
0
votes
2answers
112 views

Rewrite equivalent boolean function for p ⇔ q

Using only the operators ⇒ (conditional) and ∼ (negation) Rewrite p ⇔ q How should I go about this? Thanks
1
vote
1answer
188 views

Converting into CNF Form

If you have disjunctive clause comprising of n literals for example $(X_1\cup X_2\cup X_3\cup\cdots \cup X_n)$. where $n\geq 4$. How you can convert it into CNF (Conjunctive Normal Form) of $n-2$ ...
1
vote
2answers
41 views

Question about poset and boolean ordering, inf and sup

We have a poset $(X, \sqsubseteq)$, and we define operations $+$ and $\cdot$ by $x+y=inf(x, y)$ and $x\cdot y=sup(x, y)$ ($+$ can be seen as union in sets and $\cdot$ as intersection in sets). The ...
0
votes
3answers
524 views

Boolean-expression simplification F = [ AB ( C + (BC)' ) + AB' ] CD'

Basing on that problem. All I have in my solution is this: mystep1:[AB(C +(B' + C')) + AB']CD' mystep2:[AB(CB'+ CC') + AB']CD' mystep3: [AB(CB') + AB']CD' mystep4:[B(A+C+B') + ...
2
votes
1answer
208 views

Solving Boolean Expressions with Theorems

I'm having the hardest time wrapping my head around this stuff. This is a homework problem, one of many. I just need some help on what to do. ...
1
vote
0answers
160 views

Sum-of-products to product-of sums conversion

I need to convert $A'B'C'$ from sum-of-products form to product-of-sums form. I used a K-map and I'm not sure if the answer is $C' + AB' + A'B' + A'B$ or just $AB' A'B' + A'B$. I think that by ...
1
vote
2answers
46 views

Boolean simplification of $AB'(B' + C)$

Simplifying $AB'(B'+ C)$, then using the distributive property I know I would get $AB'B' + AB'C$ I am just confused as to how to simplify $B'B'$
0
votes
1answer
76 views

Correctness of answers and question about sup en inf

In $A=\{2, 3, 6, 12, 36, 72, 108\}$ we define the relation $R$ by $aRb$ if $b=a$, or $b=2a$ or $b=3a$. Q1: Draw the graph of $R$ and list which properties $R$ has. A1: The properties are: ...
0
votes
1answer
82 views

Condition for the boolean algebra of clopen sets to be extremely disconnected.

Let $X$ be a topological space and let $\Gamma \mathcal O(X)$ be it's boolean algebra of clopen subsets. For compact totally disconnected space, show that $\Gamma \mathcal O(X)$ is complete (as a ...
2
votes
1answer
68 views

Can a minimal representation of a Boolean Function be 1 or 0

After using the Karnaugh map to find the minimal representation of a Boolean function, my answer is 1. Is 1 a valid answer for minimal representation? If yes, what is the implication of a Boolean ...
2
votes
2answers
99 views

Order of operations for logic operations?

I have some code, that does a comparison to find how many of set of values fall within a range defined by a mean±sd, like this: ...
0
votes
2answers
71 views

How to prove boolean ordering question

Let $\sqsubseteq$ be the boolean ordering of $X$, so for every $x$ and $y$ applies $x \sqsubseteq y$ if $x \sqcap y = x$. Let $v, w, a, b \in X$ with $v \sqsubseteq a$ and $w \sqsubseteq b$. Show that ...
0
votes
1answer
48 views

How do I solve this Boolean Algebra Problem?

Let A be an arbitrary but fixed Boolean algebra with operator $@$ and $*$ and $'$ and the zero and unit element be denoted by $0$ and $1$ respectively. let $x,y,z \in A$ if $a,y \in A$ such that ...
1
vote
1answer
53 views

Boolean Algebra: Explain why (M AND (NOT N)) OR (X AND M AND N) = (M AND NOT N) OR (X AND M)?

I have no idea how this is true, by what theorem, and I literally have been thinking about this for 3 hours now. I know it's really simple, but I just must not be in the right mindset to discover ...
2
votes
1answer
40 views

Need help for right direction simplifying boolean algebra formula

I have the following boolean algebra, where union is $+$ and intersection is $\cdot$ : $(x\cdot y)+((z+y)\cdot \bar{z})+y=y$ Is there a systematic way of doing this, or do you need to puzzle? My ...
-2
votes
1answer
46 views

boolean algebra simplification for x(1 +bc') + x'(b' + bc)

in this equation using boonlean algebra: X(1 +BC') + X'(B' + BC). can i simplify (1 +BC') = 1 and (B' + BC) = B' +C? i used truth table and they have the same result, but i do not know how to solve ...
0
votes
1answer
56 views

Boolean Algebra Syntax

Six alphabets, A,B,C,D,E, and F have to be arranged in six numbered positions(1-6). How many ways can you arrange them so that A is not in position numbered 1 , B a is not in position numbered 2 and C ...
2
votes
1answer
91 views

How to find the minimum expression(s) of a set of fixed-width bit fields?

If we define $x_1 x_2 \cdots x_n$ as a bit field of width $n$, and each element $x_i$ may be $0$, $1$, or wildcard $*$. A set of 4-width bit fields $\{0000, 0001, 0100, 0101\}$ can be aggregated ...
0
votes
1answer
46 views

Help with getting the right direction on a boolean algebra question

Need some help getting in the right direction for answering the following question: Prove the following property and interpret this in $\mathcal P \left ({V} \right)$: if $x+ \bar y=$ 1, then ...
5
votes
1answer
108 views

Independent families versus generators in boolean algebras

Let $\kappa$ be an infinite cardinal. A family $\mathcal{A} \subseteq \mathcal{P}(\kappa)$ is independent if, for all $A_1,\ldots,A_n\in\mathcal{A}$ and $i_1,\ldots,i_n\in\{0,1\}$, we have $$ ...
3
votes
1answer
67 views

Do all equational theorems of Boolean algebra not involving complementation also hold for all bounded distributive lattices?

Or we might ask the question in the negative: Do there exist equational theorems of Boolean algebra involving only the operations $\wedge,\vee$ and the constants $\top$ and $\bot$ that fail to be ...
1
vote
1answer
58 views

Where can I learn more about these two functions obtained from IFF and XOR?

Given a set $X$, write $\mathrm{heaps}(X)$ for the set of all finite heaps (or 'multisets', if you prefer) on $X$. Under this definition, it is well-known that if a binary operation $*$ on a set $X$ ...
4
votes
1answer
90 views

Can we convert this statement about sets into a statement of propositional logic?

A question was just asked here about proving $$A⊆(B∪C)⟺A\setminus C⊆B.$$ We can prove this statement directly, using the concepts of first-order logic. "Suppose $x \in A \setminus C$ and that ...
2
votes
3answers
99 views

Given $x \wedge y=\mathbf{F}$, how to simplify $x \wedge \lnot y$?

Given that the boolean expression $x \wedge y=\mathbf{F}$, how to simplify $x \wedge \lnot y$? Is the above question equivalent to the following question? Find z so that $\lnot(x \wedge ...
2
votes
0answers
44 views

Algebraization of attribute-value logic

Jürgen Wedekind ("Classical logics for attribute-value languages", can be googled up) has defined an attribute-value logic as a fragment of predicate logic. There are no predicates except for ...
0
votes
2answers
269 views

Can these nested if-then-else be turned into a boolean formula?

I have this logic statement: (A and x) or (B and y) or (not (A and B) and z) The problem is that accessing A and B are rather expensive. Therefore I'd like ...
2
votes
2answers
94 views

Boolean Algebra-Simplification Assistance Needed

I have to show that (!(P.Q) + R)(!Q + P.!R) => !Q by simplifying it using De Morgan's Laws. Here is what I did but I'm not sure it's right. (!(P.Q) + R)(!Q + P.!R) => !Q (!P + !Q + R)(!Q + P.!R) ...
3
votes
3answers
168 views

Existence of maximal boolean-algebra sublattice (preserving top and bottom) of finite distributive lattice

If I regard a modal logic as some sort of many-valued logic, a "modal operator" projecting into a classical propositional logic context could sometimes be useful. Such an operator would provide a ...
0
votes
2answers
195 views

The Rotate and Shift operations in a Finite Field

Do the Rotate and Shift operations in $GF_2$ have simple expressions in a finite field? The Rotate operation $ROT[x,n]$ left rotates by n-bits. So $ROT[(0,1,1,1),2]=(1,1,0,1)$. The Shift operation ...
0
votes
2answers
24 views

Boolean bit OR operation on a Finite Field

How can I express $x \vee y$ in $GF_2$? I know that XOR is $GF_2[x]+GF_2[y]$ and AND is $GF_2[x]*GF_2[y]$ for instance. But I cannot figure out bitwise disjunction. This may be because OR does not ...
1
vote
2answers
353 views

Boolean Algebra simplification: $X=((AB)'C(A'+(B+C)'))'$

I've had two statements I need to simplify, and I'm not sure about my work: $X=((AB)'C(A'+(B+C)'))'.\quad $ With this one, do you apply DeMorgan's theorem to the interiors of the brackets and ...
1
vote
1answer
135 views

Is an algebraic formula to test real numbers equality?

Is there a formula to test numbers equality ? Let $x$ and $y$ real numbers. If $x=y$ the formula will results $1$. Else the formula will results $0$. I'm not searching for an algorithmic solution ...
1
vote
1answer
665 views

Boolean Algebra Simplification - In sum of products form

How would you simplify this expression? I've been struggling with it for a while, but seem not to be getting anywhere near the right answer. Y = (A' + BD + C'D)' (B'CD')
3
votes
2answers
115 views

Monomorphisms and epimorphisms in the category of Boolean algebras

A Boolean algebra is a ring with unity all of whose elements are idempotent. We regard a zero ring $0$ as a Boolean algebra. Let $\mathcal{B}$ be the category of Boolean algebras. A morphism in ...
1
vote
2answers
3k views

self dual boolean function

How many self-dual Boolean functions of n variables are there?Please help me how to calculate such like problems. A Boolean function $f_1^D$ is said to be the dual of another Boolean function ...
0
votes
1answer
99 views

How are boolean expressions converted to NOR expressions?

What kind of rules help to convert an expression into a 3 input NOR expression? Do all variables have to be of the form (a+b+c)' + (d+e+f)'? What happens if there is an expression that is just (a')' ...