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
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 ...
0
votes
1answer
397 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? ...
-2
votes
1answer
46 views

Simplifying a 4-term equation using boolean algebra

1432928 So, I have a logical expression: $(\lnot A\land B\land C\land \lnot D)\lor (\lnot A\land B\land C\land D)\lor (A\land \lnot B\land \lnot C\land D)\lor (A\land \lnot B\land C\land D)\lor (A\...
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
2answers
2k views

problem simplifying boolean algebra expression using consensus theorem

Please simplify this logic expression for me with helping boolean algebra : A'C'D + A'BD + BCD + ABC + ACD' I know that must use consensus theorem . my solve : STEP 1 : Terms 1 & 3 ---...
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
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 ...
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 ...
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\...
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 ...
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 $...
5
votes
2answers
660 views

calculating number of boolean functions

I would just like to clarify if I am on the right track or not; I have these questions: Consider the Boolean functions $f(x,y,z)$ in three variables such that the table of values of $f$ contains ...
0
votes
3answers
60 views

How to simplify this Boolean algebra expression?

I have this question that I need some help with, I just can't get to grips with simplifying. I'm looking at the rules and such but I just can't see where to apply them. Can someone show me the ...
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
1answer
840 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 $...
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
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 ...
3
votes
4answers
136 views

Why can't AND and NOT be represented with only IMPLICATION?

Can someone please explain why I can't use only IMPLICATION to represent AND and NOT with proof as well? I know that I can represent OR simply by using IMPLICATION. Was thinking if I could find ...
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
2answers
34 views

Minimizing basic boolean function

$==============================$ Given the function $f(x,y,z) = y'z'+x'y+x'yz+xyz'$ (where ' means the NOT operator), I need to transfer this function to its basics. The possible answers are: $x'y+y'...
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
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
548 views

Minimize SOP and POS algebraically?

Is it possible to simplify an SOP (sum of products) or POS (product of sums) expression algebraically? I can only do it through k-maps. Example: $a'b'c'd' + a'b'c'd + a'b'cd' + a'b'cd + ab'c'd + abc'...
-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 ...
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
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 ...
0
votes
1answer
88 views

Trying to prove Equivalency using Boolean Algebra

The question presented was to use boolean algebra to show that XY’Z + X’Y’Z’ + XY’Z’ + X’YZ’ ≡ XYZ’ + XY’Z + XY’Z’ + XYZ’ I've tried using various laws of Boolean algebra, but the answer that I ...
1
vote
1answer
238 views

Expression conversion using de Morgan's laws

I'm sorry strongly, because it's a very dummy question... I have an example in the algebra of logic. I need to convert an expression using the rules of de Morgan - replace by the conjunction of ...
3
votes
2answers
8k 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 $f_1$...
-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}$$ ...
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
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|...
0
votes
0answers
30 views

An intuition connected with Heyting implication

Suppose $L$ is a bounded lattice and let $\Rightarrow$ be its Heyting implication, i.e. the operation defined in the standard way: $x\Rightarrow y$ is the largest object of the set $\{u\in L\mid u\...
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 ...
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 ...
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
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
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? ...
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,...