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
votes
1answer
36 views

simplyfying boolean algebra

I need some help simplyfying a boolean algebra expression. (~abc*~d) + (a*~b*~c*~d) + (a*~bc~d) +(ab~cd) + (abc~d) I have managed to simplify to (~c*~D)(~a+~b)+(ab)(~c~d)+(a*~bc~d) but after this step ...
0
votes
0answers
15 views

Understanding the intuition behind Boolean Difference

Consider the boolean function below $F = a + b.c$ Evaluating function $F$ at $a = 0$ and $a = 1$ $F_{a=0} = b.c$ $F_{a=1} = 1$ $\frac{dF}{da} = F_{a=0} \oplus F_{a=1}$ = $\bar ...
1
vote
2answers
30 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'...
0
votes
0answers
17 views

group with infinity variables

Can a group contain infinity amount of same variables like $\{0,1,0,1,0,1,...\}$? I have been asked to prove or disprove that there is a group that contains infinity variables that follows the ...
0
votes
1answer
18 views

Simplify the boolean expression

Kindly help in Simplifying Y = BCD + BC'D. I have been trying to simplify the expression for sometime now, using the the 10 rules but cannot simplify fully.
1
vote
0answers
20 views

How to perform binary transformations?

One of the steps in Binary Index Tree algorithm is to find a node's parent which is done by un-setting the rightmost SET bit. For example: if a node has index 1010 than it's parent is 1000. To apply ...
0
votes
1answer
18 views

Simplify boolean algebra : (w'x+yz')((xz+w)(y+xz'))'

(w'x+yz')((xz+w)(y+xz'))' I gotten the answer w'xy'z+wyz' however the answer sheet was w'xz' +w'xy'z+w'yz' can anyone confirm?
1
vote
1answer
26 views

Proof writing involving Boolean algebra: AB' + AC + BC

How? AB' + AC + BC ≡ AB' + BC RS ≡ AB' + AC + BC ≡(AB' + A)(C + BC) ≡ AC Am I missing something? Thanks.
0
votes
1answer
32 views

Proof writing involving Boolean algebra: AB'+ AC + BC + D'C + DB'C'

Hello guys so I'm a bit skeptical about a problem: Given: AB'+ AC + BC + D'C + DB'C' how is the given equivalent to AB' + BC + D'C + DB'C'? If so what rule to simply from AB'+ AC + BC + D'C + DB'...
1
vote
4answers
53 views

Can't simplify this boolean expression

I'm trying to simplify this boolean expression: $$(AB)+(A'C)+(BC)$$ I'm told by every calculator online that this would be logically equivalent: $(AB)+(A'C)$ But so far, following the rules of ...
0
votes
1answer
26 views

Use Boolean algebra properties to prove the given equality.

Use Boolean algebra properties to prove the given equality.. How do I do this? $\bar{x}yz + \bar{y} + \bar{z} = \bar{x} + \bar{y} + \bar{z}$ I know $x + \bar{x}y = x + y$ I also know: $\bar{x}yz +...
2
votes
1answer
22 views

Equivalent definitions of Boolean Algebras

Assume that my definition of a Boolean algebras is the following one: I have a set $B$ with two binary operations $\vee$ and $\wedge$ which both satisfy the commutative, associative and distributive ...
1
vote
2answers
56 views

How to prove D70 = {1, 2, 5, 7, 10, 14, 35, 70} is a Boolean algebra

Prove that the set $D_{70}$ = {1, 2, 5, 7, 10, 14, 35, 70} of positive factors is a Boolean algebra under the operation (+), (.), (') defined by $$x + y = lcm(x, y)$$ $$x . y = gcd(x, y)$$ $$x' = \...
1
vote
2answers
36 views

Boolean SOP Expression Simplification: $F(a,b,c,d) = (a+d)(a'b+c'd)(ac+bd)'$

my answer that I have gotten is $b'c'd + a' b d'$ however, the answer given to me was b'c'd can someone tell me whether I am correct
1
vote
1answer
31 views

Simplify 4-term Boolean Algebra expression

How do I get from this: $F = AB' + AC' + AD + C'D'$ to this: $F = AB' + AD + C'D'$ Not sure how the $AC'$ disappeared.
0
votes
1answer
82 views

Simplify boolean expression $AB + A\bar B+ ABC $

Simplify $AB + A\bar B+ ABC $ I've been trying to simplify for a good while now. I'm using only the 10 rules but cannot find a way to simplify fully.
1
vote
1answer
41 views

How to Solve this Boolean Equations?

I have a Boolean Equations, described as below, $$\neg \mathbf{x} = \mathbf{M}\cdot \neg(\mathbf{M} \cdot \mathbf{x})$$ in which $\mathbf{M}$ is an $n\times n$ Boolean matrix, and $\mathbf{x}$ is an $...
1
vote
2answers
33 views

Tensor product of boolean rings

Is there an example of a Boolean ring $B$ such that the $B$-bimodule map $\mu:B\otimes_\mathbb{Z}B\rightarrow B,$ defined by $\mu(x\otimes y)=xy$, does not split? (To split means that there is a $B$-...
0
votes
1answer
38 views

Simplifying $ (A + B)' \cdot (C + D + F)' + (A + B)$

Firstly, please forgive me for my lack of experience in boolean algebra - I have not touched it in years. Also, as this is a coursework assignment I am only hoping for a little nudge in a right ...
1
vote
1answer
68 views

How to read Hasse diagrams and how they can describe a Boolean Algebra?

Consider a Hasse Diagram for a Boolean Algebra of Order 3 Just by using the diagram and defined Boolean Algebra System as : $\langle B, \vee ,\ \cdot \ , \bar{\ \ } \ ,0, 1 \rangle$ and for any 3 ...
4
votes
2answers
107 views

Power set representation of a boolean ring/algebra

Let $R$ be a finite boolean ring. It's known that there's a boolean algebra/ring isomorphism $R\cong \mathcal P(\mathsf{Bool}(R,\mathbb Z_2))$. I'm trying to get a feel for this. The subsets of $\...
0
votes
2answers
37 views

Simplifying boolean algebra expression that contains XOR

How can i simplify followed boolean algebra expression; Normally i express as simplify without XOR also this expresion contains both XOR and multiple variables. (((A + B)' * C') ⊕ ((A' + B') * C')' ) ...
1
vote
2answers
54 views

prove $(p → r) ∨ ( q → r)$ logically equivalent to the statement $(p∧q) → r$

I came across this problem, it asks to use logical equivalences (see image), show that $(p → r) ∨ (q → r)$ logically equivalent to the statement $(p ∧ q) → r$ (aka definition of biconditional) After ...
0
votes
0answers
20 views

Why aren't these two expressions equivalent by use of DeMorgan's Laws?

This has thoroughly confused me. According to DeMorgan, the following expressions are equivalent. $$ '(A*B) = 'A +'B $$ However, I have come across the following expression: $$ '('A+B*C) $$ By using ...
0
votes
0answers
70 views

How to Solve Boolean Matrix System?

I have a Boolean Matrix System (BMS) as described below $$Ax=c$$ where $A$ is a $n\times n$ Boolean matrix (i.e., all entries are either 0 or 1), $c$ and $x$ are two $n$-dimensional Boolean column ...
3
votes
2answers
38 views

Functional separation of regular open sets of a topological space

Let $\langle X,\mathscr{O}\rangle$ be a topological space. We say that disjoint $A,B\in 2^X$ are functionally separated iff there exists a continuous function $f\colon X\to [0,1]$ such that: if $x\...
1
vote
1answer
154 views

Proof that {xor,not} is not functionally complete

I am trying to figure out the formal proof that set of {xor, not} is not a functional complete system. Firstly I tried to build it by structural induction and show that any formula created by using ...
0
votes
1answer
138 views

How to create an AND , OR , XOR and NOT gates with a fredkin gate?

Ok so I am studying for an exam which is about logic gates and circuits , etc .The problem I have is with these two questions that are in the picture , it says build an AND , OR and NOT gate using ...
0
votes
2answers
51 views

How to test CNF for satisfiability?

If we have a conjunctive linked expression where only the following clauses are allowed: $A_i, \quad \neg A_i, \quad A_i \vee \neg A_j, \quad \neg A_i \vee A_j$ Example: $A_1 \wedge (A_2 \vee \neg ...
0
votes
0answers
21 views

Number of possible unate functions possible

An unate function f is one which is constant or can be represented by an SOP using either complemented or uncomplemented literals for each variable. My question is : How many such unate functions in ...
0
votes
2answers
59 views

lambda calculus, definition of true and false

Are the following lambda-calculus definitions axiomatic? true: $\lambda xy.x$ false: $\lambda xy.y$ Is the definition truly arbitrary? In my impression, it looks like we could just swap the ...
0
votes
1answer
40 views

Correspondence between ideals and congruences of Boolean algebras

I'm trying to prove that $con(B) \simeq I(B)$ where $B$ is a Boolean algebra and $con(B)$ is the lattice of congruences on $B$ and $I(B)$ is the lattice of ideals on $B$ I found a map s.t. for a ...
0
votes
1answer
27 views

Express logic and with +,-,*

How can a logic and be expressed using only the arithmetic operators $+,-,*$ on $\{0,1\}$, taking $1 = $ True? To be precise: What function that uses only $+,-,*$ is $1$ when both arguments are $1$ ...
0
votes
0answers
26 views

Boolean Algebra: Minterm/Maxterm with Constant?

I have a rather definition related question I guess. I have several Boolean Terms given (independent from each other, without a full function) and have to decide whether they can be seen as a Minterm, ...
0
votes
1answer
34 views

Obtaining one of DeMorgan's laws from the other

How can: $\lnot(x \lor y \lor z)=\lnot x \land \lnot y \land \lnot z$ be obtained from: $\lnot (x \land y \land z) = \lnot x \lor \lnot y \lor \lnot z$    such that $x, y, z $ are ...
0
votes
0answers
43 views

What is a complete set? Why its useful?

I am learning Discreet Mathematics and while learning Boolean algebra I came across the term Complete Set, the prof says that any formula that can be written with ...
1
vote
0answers
46 views

Sum of Products Expression using $K$-map

Determine the minimum SOP, sum of products expression using $K$-Map $F(A,B,C,D,E) = (A’ + B + C’ + D + E’)(A’ + C’ + D + E )(A’ + C’ + E )AC’$ My problem is, in my class room we have always done ...
0
votes
2answers
23 views

Problem simplifying equation using boolean algebra

I have this boolean equation: A'.B'.C'.D' + A'.B.C'.D' + B'.C'.D + B.C'.D Using a Karnaugh map I find I can simplify the above to: ...
0
votes
0answers
4 views

Regarding monomials of size k

I came across this example during my Math lecture: Consider a boolean space over 4 variables, $X = {x_1,x_2,x_3,x_4}$. Let I be the space of all monomials of size 3 over X. I understand that one ...
0
votes
0answers
35 views

Prime Implicants and Essential prime implicants to solve a K map

I was used to solve K maps directly by grouping 1 elements and then writing down the expression until I learnt the concept of Prime Implicants and Essential Prime Implicants. Is it necessary to use ...
6
votes
2answers
140 views

Can we describe multiplication on $\mathbb{F}_{2^n}$ as action on subsets of $n$-element set?

The symmetric difference between two set $A$ and $B$ denoted $A \triangle B$ is defined as the set $(A - B) \cup (B - A)$ or equivalently $(A \cup B) - (A \cap B)$. Some years ago I was quite excited ...
0
votes
1answer
30 views

How can I find POS from given SOP?

Here are the sets of POS C + B’D (AC) + (B’CD) + (AB’D) (BC) + (A’CD’) + (A’B’C’D) (BC) + (ACD’) (B’C) + (A’CD’) + (ACD) This (') stand for NOT. Please help!
0
votes
0answers
26 views

Finding Prime Implicants in a K-Map

I've been trying to solve this EE question about finding prime implicants from a K-map but there are just so many options, I really cannot be sure which ones I should pick. My K-map looks like this: ...
1
vote
2answers
44 views

Process of simplifying boolean expression

I have an expression: $$y = \overline{ab}c\overline{d} + \overline{ab}cd + \overline{a}b\overline{c}d + \overline{a}bcd + a\overline{b}cd + ab\overline{c}d$$ I've constructed the circuit for this ...
0
votes
1answer
75 views

Algebraic form from truth table with two outputs; simplifying boolean expression?

I have a truth table like below: x y z | a b ----------- 0 0 0 | 1 1 0 0 1 | 0 1 0 1 0 | 0 0 0 1 1 | 0 0 1 0 0 | 0 1 1 0 1 | 0 0 1 1 0 | 0 0 1 1 1 | 0 0 If the ...
0
votes
1answer
28 views

Why does the number of 1s in a prime implicant set in a Karnaugh Map need to be a power of 2?

Pretty much the title. We were learning about Karnaugh maps in class today and they didn't really mention why it has to be a power of 2. A quick google search basically confirmed that it needs to be a ...
-1
votes
1answer
47 views

simple logic to use only one operator to construct a function [closed]

So I was doing some of the problems on the book for discrete mathematics and I encountered this problem: We define a new operator ⊙ as follows: x ...y.... x⊙y F... F... T F... T... F T... F... F ...
2
votes
1answer
16 views

Looking for a particular algebraic mapping from one Boolean matrix to another

Consider the following Boolean matrix: \begin{align} X&=\begin{bmatrix} 1&1&1&1&1&1&1&1\\ 1&1&1&1&0&0&0&0\\ 0&0&0&0&1&1&...
0
votes
2answers
58 views

finding shortest equivalent expression

I am trying to find the shortest equivalent expression of the following: ((C → D) $\wedge$ (D → C)) $↔$ (C $\wedge$ D ∨ ¬C $\wedge$ ¬D) I have "simplified" the expression into the following: (($\...
1
vote
1answer
56 views

functional completeness of $\{\to\}$ [duplicate]

Given that the set {∨, $\wedge$ , ¬} is functionally complete, how would I prove whether the set $\{\to\}$ is functionally complete? expressing $→$ in terms of $∨$: $¬A∨B$ expressing $→$ in terms ...