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

2
votes
1answer
66 views

Boolean model containing both confusion and junk

I'm doing a course in Equational Programming, and really new to these materials. So we got a specification for Booleans: ...
0
votes
1answer
14 views

K-Map multiple representations

I have a K-Map for a given function and need to figure out the minimal form. This map involves don't-cares. My question is: Do I need to use the don't-cares in my minimal form. I will show you why I ...
0
votes
1answer
37 views

Disjunction as sum operation in Boolean Ring

Boolean ring is defined with operations of ring multiplication corresponding to conjunction or meet ∧, and ring addition to exclusive disjunction or symmetric difference (not disjunction ∨). I ...
0
votes
1answer
29 views

Prove System is Boolean Algebra

There is a mathematical system with 2 operators # and & and 4 different inputs/variables. The 2 operators are defined in the picture. Chart I need to prove that the system is boolean algebra and ...
0
votes
1answer
19 views

Simplify Boolean Expression Given Truth Table

Truth Table I have the truth table above which gives the minterm expression $$F = (\neg a \land \neg b \land c) \lor (\neg a \land b \land \neg c) \lor (a \land \neg b \land \neg c) \lor (a \land b \...
0
votes
2answers
24 views

Help with Boolean Expression Simplification

I know that $$(\neg a \land \neg b \land \neg c) \lor (a \land \neg b \land c) \lor (\neg a \land b \land \neg c) \lor (a \land b \land c )$$ and $$(\neg a \land \neg b \land \neg c) \lor (a \land ...
1
vote
2answers
39 views

How to show that $f(w,x,y,z)=wx'y'+xz+w'x'y$ isn't universal?

First, I will note that I don't need a formal prove. short explanation is enough. The only way I know to show that an operator isn't universal, is by showing that you can't implement $NOT$ with it. ...
0
votes
0answers
16 views

Design a circuit for a function

I am so confused on this problem. We are given a function $f$ and told to design a circuit that has four inputs labeled $b_3,...,b_0$, and an output $f$, where $f = 1$ if the 4-bit input pattern is a ...
0
votes
1answer
42 views

Sum-of-products for a function

I am not quite sure if I am understanding this correctly or not. Here is the problem: "Find the simplest sum-of-products form for the function $f$ using the don't-care condition $d$, where $f = x_1(...
1
vote
0answers
33 views

What will be the answer to this K-Map?

I have a K-Map and I need to figure out which expression isn't equivalent to the provided K-Map. $$\begin{array}{r|cccc}_{xy}\backslash^{wz}&00&01&11&10\\\hline00&0&\times&...
2
votes
3answers
47 views

Solving a boolean expression

I am trying to solve the following Boolean expression: $$a + \neg{a} b + \neg{a} \neg b c + \neg a \neg b \neg c d + \dots$$ The question asked was to use Boolean algebra in order to solve the above ...
0
votes
0answers
61 views

Can anybody explain me how to solve logical equations with using matrices?

Task:I need to find N, with which number of solutions is 32. \begin{cases} (X_1 \land X_2) \oplus (X_1 \land X_3) \oplus (X_2 \land X_3) =X_1 \land (\lnot( X_2 \land X_3)) \\ (X_2 \land X_3) \oplus (...
0
votes
0answers
38 views

On a theorem concerning free Boolean algebras

In Sikorski's book "Boolean Algebras" (3rd edition), p. 42, one finds the following theorem: In order that $\mathfrak{A}$ be a free Boolean algebra with $n$ free generators, it is necessary and ...
0
votes
1answer
62 views

Is it possible to solve such system of Boolean equations?

During a discrete mathematics test I got this question. I did not see it in my course and I am baffled, because I don't even know from where to start. All I found on google for such subject were ...
0
votes
1answer
38 views

What is the value of 0 XNOR 1 XNOR 1? [closed]

We know that for 3 variables $(A=0,B=1,C=1)$, $f_1 = (A \mathop{\text{ XNOR }} B \mathop{\text{ XNOR }} C) = 1$, since the input has even number of $1$'s. But if we were to do this step by step, $f_2 ...
0
votes
2answers
95 views

Why is $a \implies b$ is true when $a$ is false [duplicate]

I understand that: $True \implies True$, is true. $True \implies False$, is False. But why is it that $False \implies True$, is True. and $False \implies False$, is True. If $a$ is false I don'...
3
votes
2answers
122 views

Intuition for orthogonality in $\{0, 1\}^n$

In the beginning of [Kanerva 1988] a boolean algebra over $$ \{0, 1\}^n $$ with bitwise OR and AND is introduced. Example for bitwise OR: $$101 + 001 = 101$$ Example for bitwise AND: $$101 * 001 = ...
0
votes
1answer
32 views

Adjust the result of a boolean expression

I need to solve this in boolean algebra: $$B(A+(B'+ A)')$$ Here is my attempt: $$B(A+(B'+ A)')=B(A+(BA'))=B((AA')+(AB))=B(0+AB)=B(AB),$$ and the result should be just $B$. Should I just decide ...
2
votes
0answers
21 views

Expressing associativity as a Boolean SAT problem

Suppose we have a binary operation $B: S \times S \to S$ on a finite set $S$. We can encode $B$ as an array of $|S|^3$ Boolean values by setting $$ B_{ijk} \equiv \text{True} \quad \text{ iff } \quad ...
0
votes
0answers
35 views

Separation in Boolean algebras

I am looking for a separation-like result for Boolean algebras which is intuitively clear to me. Suppose that $B$ is a Boolean algebra whose set of positive elements $B^+$ does not have countable ...
0
votes
1answer
37 views

Number of self dual functions and number of inputs for which self dual function is 1

I came across this slides which states following two theorems: Theorem There are $2^{2^{n-1}}$ different self-dual functions of $n$ variables. Theorem Let $f$ be a self-dual function of $n$ ...
0
votes
1answer
30 views

PIT implies: In a boolean lattice, every filter can be enlarged to a maximal one

I am working through this proof of Herrlich's Axiom of Choice: $(1)\Rightarrow(2)$: How do you define the quotient lattice $B$ modulo a Filter? And why is the preimage of the maximal filter $\...
0
votes
0answers
40 views

Finding the principal disjunctive normal form (PDNF) of a Boolean expression

Find the principal disjunctive normal form (PDNF) of a Boolean expression $$((p\wedge q) \rightarrow r)\vee((p\wedge q)\rightarrow \neg r).$$ I tried by expanding it but I am stuck with the ...
1
vote
1answer
37 views

Boolean Algebra Product of Sums

I have a question to solve the following expression and get it in terms of product of sums (AB' + A'B)C And I tried taking the compliment of this ...
0
votes
1answer
60 views

Design a circuit for a light fixture

Design a circuit for a light fixture controlled by four switches, where flipping one of the switches turns the light on when it is off and turns it off when it is on and please explain your answer
1
vote
2answers
41 views

Basic boolean prove

I need to prove that given $$ f_1 = c + a'd' + bd' \quad\text{and}\quad f_2 = a'b'd' + a'bd' + ab'c + abd' $$ that $f_1 = f_2$. How do I manipulate $f_2$ to be exactly like $f_1$? I have tried a lot ...
-2
votes
1answer
67 views

How can i simplyfy this boolean equation?

Please help me simplify this formula by using boolean algebra rules: $F= x_1'x_2'x_3'x_4'+x_1'x_2'x_3x_4+x_1'x_2x_3'x_4'+x_1'x_2x_3x_4'+x_1x_2'x_3x_4.$ I know that the answer should be: $(x_1'x_3'...
1
vote
1answer
59 views

Questions about Boolean logic

Is there a systematic way to show that a set of Boolean operators is complete? Or is it more of an art than a science? Similarly, is there a systematic way to convert any Boolean expression in terms ...
1
vote
1answer
85 views

How to solve for a variable in xor equation?

I am very new to algebra with bitwise operators. If i have 5x ^ 7x ^ 9x = 22 is it possible for me to solve for x (if so how is it done)? Do normal algebra techniques hold (factoring out x etc.?) I ...
4
votes
1answer
40 views

How do I derive logical statements simply?

For example if I want to show the equation for $x \rightarrow y$, using truth tables it is the same as: $$(\neg x \wedge \neg y) \lor (\neg x \wedge y) \lor (x \wedge y)$$ Is there a methodical way ...
0
votes
1answer
41 views

how to draw a truth table for following logical expression?

It's a question in my assignment, which I don't really understand it. However, there is an example here. e.g. A computer uses the following logical expression to control a finger print scanner. F(...
2
votes
1answer
60 views

A generalized Boolean algebra gives rise to an implication algebra

A generalized Boolean algebra $G$ is relatively complemented distributive lattice with largest element 1. That is, an element $a\in G$ has a complement in any interval $[x\,,\,1]$ that contains $a$. ...
0
votes
0answers
17 views

strict partial orders that guarantee monotonic orientation functions

Given a strict partial ordered set $>$ over a set $V$. Consider its directed acyclic graph $G=(V,E)$ where $(v,u)\in E$ if $u> v$ and there is no $w$ s.t. $u> w$ and $w>v$ Consider the ...
3
votes
1answer
33 views

Complete atomic boolean subalgebras of power set boolean algebra

Let $I$ be a set and $P(I)$ its power set. I want to prove: Set $E(I)$ of all equivalence relations on set $I$ and set $A(I)$ of all complete atomic subalgebras (i.e. subalgebras that are atomic and ...
1
vote
0answers
17 views

How many minimized forms can a boolean expression have with 4 variables?

I have this theoretical question I can't get my head around. Assuming I have a function (any function) with 4 variables, and I draw a Karnaugh Map in order to extract the most simplified expression ...
0
votes
0answers
27 views

How to prove that $f(w,x,y,z)=∑(4,5,13)$ isn't universal?

I know that: $f_{min}=w'xy'+xy'z$. In order to show that operator isn't universal, you can show that there is no way to get $NOT$ by the operator. However, in this question there are four ...
0
votes
3answers
51 views

Basic prove that boolean function is self-dual

I'm tring to prove this function: $$ f(x,y,z) = x'y'z'+x'yz+xyz'+xy'z $$ is self-dual, I've tried some basic manipulations like using double not on the function with de-morgan rules but got no ...
0
votes
1answer
39 views

Have I simplified this Min-term Correctly?

I have got two different solutions and I would like to know if they are correct, I would be very grateful if you could let me know if they are correct or what I can do to correct them. Solution 1 <...
0
votes
1answer
25 views

Boolean algebra how simplify products of sum Form

How Solve it to minimum number of literals i can't understand basic properties to simplify this expression $(A̅ +C)(A̅ +C̅ )(C+D)(B̅ +D)(A+B+C̅ D)(A+B̅ +C)$ explain me to understand concepts of ...
1
vote
2answers
34 views

How to convert $((x\land y)\lor(z\land u))\land((x\land\neg z)\lor (\neg y \lor u))\land((y\land z)\lor(x\land u))$ to the disjunctive normal form?

Is there a faster way than doing a gigantic truth table? I tried some transformation but didn't find a way to simplify the problem.
3
votes
0answers
52 views

What are universal abstract $\sigma$-algebras on $\sigma$-frames?

In this paper, the authors make the following definitions: An (abstract) $\sigma$-algebra is a boolean algebra with countable joins. A $\sigma$-frame is a bounded lattice with countable joins, where ...
1
vote
0answers
41 views

Finding solution to matrix equation over GF(2) with minimal true variables

I am looking for a general way to find a solution to a system of equations in GF(2) such that the solution has the least amount of true variables. After Gaussian elimination I get a matrix like such: ...
1
vote
1answer
31 views

Describe which partial orderings yield boolean algebras

I thougt about propositional logic and boolean algebras and how propositional logic is (at least from one point of view) not really about $\land,\lor,\neg,...$ but about boolean operators, i.e. n-ary ...
1
vote
1answer
35 views

Boolean Expression - ((a'.b)'+c')' + (a'+(b'.c)')'

I'm trying out one of the exercise, but not sure whether did I get the answer right, is the answer for the following output is 'C'? Kindly help to simplified it, as I'm not sure about it, still trying ...
0
votes
1answer
26 views

don't understand something in boolean algebra solution

I asked a question earlier and got the solution https://gyazo.com/372f0352b7d8aeb180586ac5218dd1bc I understand it all apart from this part AB(C⊕D)+D′(AB′+A′B) ...
0
votes
1answer
47 views

definition of projection operation for boolean functions

A boolean function $f$ over a set $A$ is a subset $X\subseteq A$ and $F$ is a set of boolean functions. I am trying to check whether $F$ is closed under projection. And I really do not know what ...
1
vote
0answers
31 views

Hochschild cohomology of a boolean ring

I can't find any papers studying the Hochschild cohomology ring $H^*(B,B)$, where $B$ is a boolean ring, so I was wondering if this is known.
0
votes
1answer
31 views

Which form of the function is simpler?

I'm simplifying function in Boolean algebra. Which form is simpler: $AB' + C'D + A'BC$ OR $DA' + C'D + AB'$ Second form has less letters but overlays itself at more spots. Which one is simpler?
0
votes
0answers
29 views

Finding the smallest decision tree of a Boolean function

From Computational Complexity: A Moden Approach, A decision tree is a model of computation used to study the number of bits of an input that need to be examined in order to compute some ...
-1
votes
1answer
35 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 ...