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
1answer
17 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
0answers
13 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 $...
3
votes
4answers
133 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
14 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
32 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
38 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
65 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
546 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
33 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
39 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
87 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
236 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
31 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
44 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
38 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\...
3
votes
5answers
147 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
26 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
1answer
47 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 ...
4
votes
2answers
139 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
39 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
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 ---...
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
35 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,...
4
votes
4answers
151 views

Difficulty understanding why $ P \implies Q$ is equivalent to P only if Q.

I have difficulties understanding why $ P \implies Q$ is equivalent to P only if Q. I do understand that in the statement "P only if Q", it means if $ \lnot Q \implies \lnot P$". Regarding this ...
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) \...
-1
votes
1answer
41 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
27 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. ...
5
votes
2answers
654 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
1answer
838 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
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 ...
2
votes
2answers
34 views

Can$A \cap (B' \cap C')$ be $(A \cap B') \cap (A \cap C')$?

If I use the above statement, provided that it is right, in a question, would I have to prove it as well?
0
votes
1answer
44 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}$?
2
votes
1answer
48 views

Stuck at simplifying boolean expression

I'm getting stuck at the following boolean expression. $$z + (x'y) + (xy') + (xt') + (yt')$$ In my solutions it's simplified and the $(yt')$ term is gone. How do they simplify this? I really cant ...
0
votes
1answer
42 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
19 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 ...
0
votes
1answer
23 views

Is a boolean algebra closed under countable disjunction/conjunction?

I'm just curious if the properties in a sigma algebra is also satisfied in a boolean algebra. In a boolean algebra, the two operators are closed under finite operations, but can we say they are closed ...
1
vote
2answers
34 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 ...
0
votes
2answers
55 views

Boolean Logic - Why doesn't the Associativity Law work in this scenario?

By the associativity law, shouldn't the statement below be true? I understand that the truth tables are different but where exactly does the associativity law apply then if this is False? $(p \land q)...
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 ...