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

0
votes
0answers
13 views

Axioms for a Heyting Algebra as a Set System (Partial Order Lattice Under Inclusion)

According to the corresponding section in Wikipedia: An element $x$ of a Heyting algebra $H$ is called regular iff $x = \neg y$ for some $y \in H$. Elements $x$ and $y$ of a Heyting algebra ...
3
votes
0answers
30 views

Is the tensor product of BAOs a kind of extended BAO?

I've been reading "Boolean algebras with operators. Part I." (Jonsson, Tarski) where, given a subalgebra of a Boolean Algebra, they define its perfect extension. As far as I understand it can be ...
0
votes
1answer
12 views

Why choosing 1 or 0 for the dont care values give different function in a Karnaugh Map?

If I have a Karnaugh Map with dont care values . I can give any dont care the value 1 or 0 depend on my needs. But why if I will choose 1 for the dont care values, it will give me a function $f$ And ...
0
votes
1answer
16 views

Karnaugh map grouping of element

In Karnaugh map ($4\times 4$) can we group an element that is shared two three different groups. I think answer should be no but I do not know why it is?Can anybody provide a reason in support of this ...
1
vote
0answers
17 views

Interior algebra vs. Regular open algebra

I know that an interior algebra is a Boolean algebra on which is defined an operation satisfying Kuratowski's axioms for the interior of a set. I recently heard about the regular open algebra, which ...
1
vote
1answer
50 views

How to rewrite all the boolean operations using if-then-else operator?

Cited by Conditional Term Rewriting Systems: 1st International Workshop Orsay, France, July 8-10, 1987, p. 105 Additional Boolean operations are not needed, because all the usual Boolean ...
0
votes
0answers
6 views

Boolean expression to check whether a path is a dipath?

Suppose you have an alternating sequence of vertices and egdes $v_0,e_1,v_1,\ldots,e_n,v_n$ for a digraph $G.$ You know that this sequence is at least a path between $s$ vertex and vertex $t$. Does ...
0
votes
1answer
32 views

Proof Sequences using inference

$(p \land (p \implies q) \land (q \implies r)) \implies r$ It is written slightly different in the text book, but this should be the equivalent form. The book is a bit unclear but I think the author ...
-1
votes
0answers
3 views

Boolean equivalence

Given a boolean formula $\phi$ and an interpretation $x$ that satisfies it, is it possible to come up with a permutation $P$ such that $x$ satisfies $P(\phi)$ but it is computationally hard to ...
-1
votes
1answer
49 views

Is there a book about discrete algebraic structures? [closed]

In German it is called "Diskrete algebraische Strukturen".The literal translation would be discrete algebraic structures, does something like this exist? The course contains the following topics ...
2
votes
1answer
38 views

How to convert numbers with related bases quickly?

Let: $a = (1011011)_2 = (1123)_4$ There two ways to solve it: Convert the number in base 2 to base 10 then to base $4$. Consider $4 = 2^2$ and group each of two numbers in base $2$ to one in base ...
0
votes
1answer
11 views

Sum of products expansion of basic Boolean function: $ F(x,y) = \bar{y} $

So I have a question about this very basic-looking sum of products expansion. My professor has this particular example in his lecture slides but I can't quite wrap my head around this. I don't ...
2
votes
1answer
44 views

From an axiom system of propositional logic to an axiom system for a Boolean algebra

A well-known set of axioms for the classical propositional logic is Lukasiewicz's 3rd set: $A\rightarrow(B\rightarrow A)$ $(A\rightarrow (B\rightarrow C)\rightarrow ((A\rightarrow B)\rightarrow (A\...
0
votes
1answer
29 views

Boolean Algebra simplifcation

I have an expression I need to simplify for a class assignment, yet I simply can not figure out how to apply the rules in this case. Can someone put me on the right direction? w’x’y’z + w’xy’z + wxy’...
0
votes
0answers
21 views

Fourier Analysis for Derandomization of Functions

I was wondering if there was an extension to Fourier Analysis on Boolean Functions. Specifically, it's well known that for any boolean function $$f: \{-1,1\}^{n} \rightarrow [-1,1] $$ we can decompose ...
1
vote
1answer
34 views

Help with Boolean algebra

Consider a system with $n$ units where each unit is either working or failing. $x_j=1$ represents the condition that $j$-th unit is working. Suppose each unit is working with independent probability $...
0
votes
0answers
15 views

Clarity on Boolean Algebra and Rings

I'm trying to wrap my head around Abstract Algebra, Boolean rings, and it's a little difficult. So I understand the ring (I believe it's a ring) <ℤ ,x, +, -, 0, 1 > is normal integer arithmetic ...
1
vote
1answer
40 views

Prove universal gate math

I tried to deal with this question: $$F(a,b,c,d) = (a'+b'+c')\oplus bcd$$ While I asked to prove that F with the constant '$0$' is universal gate. I know that to prove that some function is ...
1
vote
1answer
26 views

How can I find a DNF and Minimal Form for this boolean expression?

$Q(x,y,z)=(y′\vee z′ \vee 0\vee x′)\wedge1\wedge(z\vee x′\vee 0\vee y\vee z)′\wedge(z′\vee x\vee y\vee z′)$ I'm not supposed to use tables but only proprieties like De Morgan ecc. EDIT: So I ...
1
vote
3answers
68 views

How to simplify using algebra laws

Simplify the following by using algebra laws. (i) X’.Y’ + X.Y.Z. + X’.Y + X.Y My attempt: X’.Y’ + Y(X.Y.Z + X'Y + X.Y) X’.Y’ + (X.Z + X' + X) X’(X’.Y’ + X') + X.Z + X Y’ + X' + X.Z + X Y’ + X' +...
0
votes
1answer
13 views

How can I show a set B with 8 elements and two operations (huntington axioms)

How can I show a set B with 8 elements and two operations, such that the axioms of huntington for boolean algebra holds? I found it with set of 2 elemtnts. but can't understand how to start with 8 ...
-2
votes
1answer
37 views

De Morgan's Law Operation order

I have the following boolean logic: $$ \overline {\overline {\overline {B+C+D} + \overline {DA}} + \overline {\overline {\overline {A+E} + \overline { B}} + \overline {E}}} $$ I am trying to simplify ...
-1
votes
1answer
33 views

XOR equation with multiplication arrangment

How can I move all the X to one side so the equation will become x=y XOR <somthing>... $$\begin{align} &2x \oplus y = x \end{align}$$ ...
2
votes
1answer
40 views

Simplify semi-boolean expression

I'm trying to simplify the following expression: (A == B) OR ( (A > B) AND (A < C) ) Given that B <= C, this is my ...
0
votes
1answer
39 views

Naive question about 3 sets intersection point

I have three intersecting in at least one point sets $A$, $B$, $C$ with arbitary finite countable cardinality. The known facts are: $$ |A|, |B|, |C| $$ $$ |A \cap B| $$ $$ |B \cap C| $$ $$ |C \cap A|...
1
vote
1answer
48 views

On boolean algebras as rings, modules and/or R-algebras

After trying to make sense of first order logic from an algebraic point of view I started to read about boolean algebras (similar to the explanations given here: wikipedia on boolean algebras. I also ...
0
votes
0answers
28 views

Partition of complete boolean algebra induces partition on elements

Given a complete boolean algebra B, and two partitions W and T of B, why is it true that W induces a partition on every element of T? (And is this true more generally - does W induce a partition on ...
2
votes
5answers
153 views

$f(x) = 0$ when $x$ is $0$, and $1$ otherwise

I've been trying to create a function that will return $0$ when $x$ is $0$, and for any other $x$ value it should return $1$. I've searched for a pre-existing function online too and wasn't able to ...
2
votes
1answer
49 views

Is there a way to reduce a set of linear inequalities representing a set of vectors in $\{0,1\}^n$?

Given a fixed number $r$, such that a vector $v_i \in \{1,0\}^n$ has exactly $r$ ones and $n-r$ zeroes, and a number of inequalities, (say $I$ is this set of inequalities) representing a set $J$ of ...
0
votes
1answer
40 views

Why is Boolean a lattice?

I've had minimal exposure to lattice theory but I must answer this question due to a project I'm working in. If anyone could answer this question in the simplest explanation possible with examples ...
0
votes
0answers
27 views

Complexity of some contact circuit

How to prove that for every boolean function $f$ of $n$ variables there exists a (1, 2)-contact circuit $\Sigma_f$ (i.e. with one input and two outputs), implementing boolean function system $(f, \...
1
vote
1answer
16 views

Stuck on boolean algebra problem

Could someone please explain me why $x.y+x.z+y'.z$ Is equal to $x.y+y'.z$? I just can't simplificate it..
1
vote
1answer
35 views

Prove that $\lambda(f) = o(2^n)$ for almost all boolean functions

How to prove that $\lambda(f) = o(2^n)$ for almost all boolean functions $f$ of $n$ variables? Here $\lambda(f)$ denotes minimal length (i.e. count of terms) of all possible disjunctive normal forms (...
1
vote
0answers
24 views

Lower bound of DNF terms count for some symmetric boolean function

Consider boolean function $s_n^{[r,\,n - r]}\colon \{0,1\}^n\rightarrow\{0,1\}$ defined as follows: $$ s_n^{[r,\,n - r]}(x_1, ..., x_n) = 1 \iff |\{x_i: x_i = 1\}| \in [r,\,n - r] $$ (in other words,...
0
votes
1answer
17 views

Monomorphism between finite Boolean algebras

Let $A$ be a finite Boolean algebra. If I define a monomorphism (i.e. an injective homomorphism) from $A$ to another finite Boolean algebra $B$ of the same similarity type. Is this monomorphism an ...
1
vote
0answers
24 views

Isolate $A$ from $A\oplus(129^3A)$

I've been working through the following problem and I'm really stuck Starting with the following three equations: $$ a= (129A \oplus C)\mod 256 \\ b= (129B \oplus A) \mod 256\\ c= (129C \oplus B) \...
0
votes
2answers
32 views

Stuck in Boolean Algebra equation

I have this equation in Boolean Algebra: $x*y*z+x'*y*z+x*y'*z+x*y*z' = y*z+x*z+x*y$ I got this: $= yz(x+x')+xy'z+xyz'$ $= yz+xy'z+xyz'$ And from here I tried multiple things but it goes wrong ...
1
vote
2answers
37 views

Having trouble with simplifying in Boolean algebra

I want to solve this problem: $$(x . y . z + x . y + x)$$ Which turns into this when you group $x$ $$x . ( yz + y + 1 ) $$ What I don't understand is why is there a "1" at the end? ...
-1
votes
1answer
44 views

Using the laws of logic (algebraic version) to show the following equivalences [closed]

I have some questions about algebra and discrete, with using law of logic. I am not sure how to prove the equivalences. Can someone please show me how this works and show the equivalence using the ...
2
votes
1answer
52 views

How can I prove that $(a + b )\oplus(a + c)$ is not possible to simplify. Or is it?

I was trying to simplify the following expression $(a + b )\oplus(a + c)$, where $+$ is just a simple addition of two numbers and $\oplus$ is a binary xor operation. By simplifying I mean exanding or ...
2
votes
2answers
29 views

Logic Puzzle (Valid and Invalid Arguments)

I have been given a logic puzzle and I am having a tough time figuring out how to set it up and solve. Here is the puzzle: a) The Statement "If Dr. Jones did not commit the murder then neither Ms. ...
2
votes
3answers
72 views

Logical limitations of Proofs by Contradiction

In general proofs by contradiction go as follows: Given an arbitrary hypothesis, $\ p \implies q$, we assume $\left(p\implies q\right) = T$, and then we show that by assuming the hypothesis to be ...
4
votes
2answers
146 views

How to deal with an 8 variable Karnaugh map

I'm reaching back into my high school days trying to remember one of the rules about Karnaugh Maps. I have an 8 variable input, and I remember that I should try and make the selections a big as ...
0
votes
1answer
46 views

Is there a blackboard bold letter for the set of Boolean numbers? [duplicate]

Is there a symbol (e.g. $\mathbb{B}$) for the special set of Boolean numbers or values; ${0,1}$ or ${True,False}$?
0
votes
1answer
43 views

Galois field of order 2 constituting a Boolean algebra

We know that the the set $\{0,1\}$ constitutes a Boolean Algebra over the usual $OR$ and $AND$ operations. However, because of the lack of an additive inverse for $1$ this does not produce a Galois ...
1
vote
1answer
35 views

A proof of maximality of an antichain in a complete Boolean algebra

Suppose $(\mathbf{B},\leqslant)$ is a complete Boolean algebra and let $|\mathbf{B}|=|\gamma|$. Let $C=\langle c_\alpha\mid \alpha<\gamma\rangle$ be a maximal descending chain without a lower bound:...
0
votes
1answer
20 views

Boolean Expression Simplifying explanation

Currently have worked xz' + x'y + (yz)' Down to z' + x'y + y' Is this its simplest form? METHOD: xz' + x'y + (yz)' -> De-Morgan on (yz)' xz' + x'y + y' + z' -> Commutative xz' + z' + x'y + y' -> ...
3
votes
0answers
27 views

Do DeMorgan's laws hold for pseudo-complement in Bi-Heyting Algebra?

A textbook says in Heyting Algebra, The pseudo-complement of an element $a$ is denoted as $a^{\ast}$. One of the DeMorgan's law $\left(\vee a_{i}\right)^{\ast}=\wedge a_{i}^{\ast}$ holds ...
1
vote
2answers
36 views

boolean algebra reduction question

hi im having a lot of trouble proving this boolean expression. Im getting many differing answers so I assume I must be going about it in the wrong way. To explain, I'm trying to negate the whole LHS ...
17
votes
2answers
2k views

Why are Boolean Algebras called “Algebras”?

Boolean algebras aren't algebras (to the best of my understanding). So why are they called algebras? Wouldn't it make more sense to call them a "Boolean system" or a "Boology" or something else like ...