Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [boolean-algebra]

Boolean algebras are structures which behave similar to a power set with complement, intersection and union. Use this tag for questions about Boolean algebras as structures, or about functions defined from/to Boolean algebras. For Boolean logic use the tag propositional-calculus.

Boolean algebras are structures which behave similar to a power set with complement, intersection and union. Use this tag for questions about Boolean algebras as structures, or about functions defined from/to Boolean algebras.

A Boolean algebra uses Boolean variables, typically denoted by capital letters, e.g. $A,B$, which can only take the values $0$ or $1$. Operators are $\land$ (conjunction), $\lor$ (disjunction) and $\lnot$ (negation).

For Boolean logic use the tag .

3083 questions
2
votes
2 answers

Simplifying 4-term Boolean Expression

I am given a pretty lengthy Boolean expression: $$(¬A ∧ ¬B ∧ ¬C ∧ ¬D) ∨ (¬A ∧ B ∧ ¬C ∧ D) ∨ (A ∧ ¬B ∧ C ∧ ¬D) ∨ (A ∧ B ∧ C ∧ D)$$ which I am asked to simplify. The solution should be: $$((¬D ∨ B) ∧ (D ∨ ¬B)) ∧ ((¬A ∨ C) ∧ (A ∨ ¬C))$$ But I'm not…
James Taylor
  • 588
2
votes
1 answer

How to prove that any Boolean function can be simulated only using AND gate and NOT gate?

I want to see how to prove the functional completeness of NAND gate, but all the materials in the web I have reached just relies on the fact that the set $\{AND,NOT\}$ is complete and shows how to simulate those gates only using NAND gate. I want to…
Guldam
  • 934
2
votes
1 answer

Boolean algebra: How does the imply operator work?

I am conflicted because our professor said that "(not) A implies B only and only if A and B = 0" which doesn't match with what I found on Wikipedia or other books on Boolean algebra: "A implies B = (not) A or B". Are the two equivalent, or one of…
Andrew
  • 137
2
votes
2 answers

Understanding how $\mathcal{P}(A)$ is a Boolean algebra

I'm currently doing work on discrete mathematics in my free time and am having some difficulties with understanding Boolean algebra. To be specific, I'm stuck on the following practice question: Let $A = \{a, b\}$ and list the four elements of the…
Johnathan Scott
  • 333
2
votes
2 answers

Why does (A'+ AC) = (A'+C)?

Why does (A'+ AC) = (A'+C)? I can understand this via a truth table, but I cannot see why this works in boolean algebra. Conceptually I understand that A doesn't matter, but I can not seem to prove this. Can someone lend some advice?
Adam
  • 103
2
votes
1 answer

Boolean functions

Boolean function f(x1,x2,x3): If f(x1,x2,x3)= TRUE then f(TRUE,x2,x3)= TRUE f(x1,TRUE,x3)= TRUE f(TRUE,TRUE,x3)= TRUE f(x1,x2,TRUE)= TRUE f(TRUE,x2,TRUE)= TRUE f(x1,TRUE,TRUE)= TRUE f(TRUE,TRUE,TRUE)= TRUE For 2 arguments there is 6 such functions.…
Anlhord Smithson
  • 29
  • 2
2
votes
1 answer

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 see it.... Many thanks!
Stekke
  • 23
2
votes
1 answer

karnaugh map simplification

I really wonder why my method is wrong. Could you explain step-by-step and why my methods wrong. Drawings includes just one time isn't it enough for simplification ? First boolen expression: $$ F = A'B'C'D' + A'B'C'D + A'B'CD + A'B'CD' + A'BC'D +…
NewCoder
  • 65
2
votes
2 answers

Simplifying $(\neg x\land \neg y \land \neg z) \lor (\neg x\land \neg y \land z) \lor (x\land \neg y \land z) \lor ( x\land y \land z)$

I'm looking at this logical formula: $(\neg x\land \neg y \land \neg z) \lor (\neg x\land \neg y \land z) \lor (x\land \neg y \land z) \lor ( x\land y \land z)$ Asked to simplify it as much as possible, and I did something like this: $((\neg x…
εν οίδα ότι ουδέν οίδα
  • 1,138
2
votes
2 answers

Show that every boolean function with 3 variables can be represented with maximum number of 10 gates

I need to show that every Boolean function with 3 variables can be represented with maximum number of 10 gates, limited to the following: AND(2 ins), OR(2 ins), NOT(1 in). I tried to find Boolean function with 3 variables, of a higher complexity,…
Korunoski
  • 21
2
votes
1 answer

Equivalent form of biconditional

I'm reading How to Prove It: A Structured Approach (Velleman) Second Ed. Doing all the end of chapter exercises for chapter 1 and having trouble on problem 5a which reads Show that $P \leftrightarrow Q$ is equivalent to $(P \wedge Q) \vee (\neg P…
Obrazi
  • 23
2
votes
0 answers

Product of binary Boolean operators

I'm interested in the set $\mathcal{P}_N$ of boolean functions of boolean variables $p_1, p_2, \ldots, p_N$ that can be written as products of operators of 2 variables only: $$ \phi(p_1, \ldots, p_N) = \bigwedge\limits_{i
Maxim
  • 380
2
votes
1 answer

How to get from the statement $(AB'+C'A'+C'B')$ to equivalent statement $(AB'+C'A')$?

I've been working a Boolean algebra problem for probably 2 hours at this point, and while I arrive at a much simplified equivalent expression, there's a simpler one yet. Basically, I start out with a truth table and am asked to get it to a…
orn
  • 23
2
votes
1 answer

Boolean algebra Simplification of "xy + x'z + yz"

I'd like to simplify the following expression "xy + x'z + yz": xy + x'z + yz = xy + z(x' +y) = (xy + z)(xy + x' + y) = (xy + z)(y(x + 1) + x') = (xy + z) ( y + x') What…
Pantelis10
  • 35
2
votes
1 answer

Number of subalgebras of the power set algebra

Let $X=\{a,b,c\}$ and $\mathcal{P}X=\{\emptyset,X,\{a\},\{b\},\{c\},\{a,b\}.\{a,c\},\{b,c\}\}$. I can only see 4 subalgebras of $\mathcal{P}X$,…
user60264
1 2 3
…
64 65