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
vote
2answers
66 views

Assignment for discrete mathematics

How can I prove that not every boolean function is equal to a boolean function constructed by only using ∧ and ∨?.Need help in proving it.
0
votes
3answers
94 views

Discrete Mathematics (boolean)

Either exhibit 333 different boolean functions on the three variables p; q; r, or prove that there aren’t 333 different such functions $p$ $q$ $r$ $0 0 0$ $001$ $010$ ...
0
votes
1answer
142 views

prove that there does not exists a boolean algebra containing only three element

please prove that there does not exists a Boolean algebra containing only three elements .prove it with example so that i can understand easily.i cant understand the question and i could not tried to ...
0
votes
1answer
108 views

How can I simplify this boolean equation for the multiplexer a little further?

I've obtained a formula through cannonical representation, which is: $$A\cdot \overline{B\cdot S}+A\cdot B\cdot \overline{S}+\overline{A}\cdot B\cdot S+A\cdot B \cdot S$$ And I'm trying to simplify ...
1
vote
0answers
136 views

What are three possible ways to express the following Boolean function with eight or fewer literals?

F= A'BC'D + AB'CD + A'B'C' + ACD' I assumed that the question was asking for me to simplify. I placed the terms into a kmap and have gotten SOP F= A'B'C' + A'C'D + AB'C + ACD' or POS F= ...
2
votes
0answers
59 views

Finding the atoms of a Boolean Algebra

I have a homework question that asks me to find the atoms of the Boolean Algebra that contains 256 Boolean functions "such as F1(x,y,z) = x + y +z, F2(x,y,z) = x + xz, F3(x,y,z) = xyz+ xyz and so on". ...
1
vote
0answers
18 views

Logic subject-reductio ad absurdum

Can you solve this using method reductio ad absurdum? 1)A ↔ (¬ B v C) ¬ A ¬ B 2)¬(R∧ (S v T)) 3)R∧¬ T S ¬R∧ S
2
votes
5answers
152 views

Value of $(a=1) \wedge (b=1) \wedge (c=2)$ given $a=1$, $b=2$ and $c=2$

How would I solve the following question. Assume $a=1$, $b=2$ and $c=2$ what is the value of the following Boolean expression $(a=1)$ AND $(b=1)$ AND $(c=2)$ I am kind of confused because I know ...
1
vote
1answer
194 views

Conjunctive Normal Form vs Product of Sums

I am confused as to what the difference between Conjunctive Normal Form and Product of Sums is. Can someone explain what is different about them? It seems like they both only use groups of OR ...
1
vote
1answer
74 views

Whats wrong with this reasoning…

Suppose I have two non-distinguishable balls (for example two white ones) and I color them with red and green, then a combinatorial reasoning could go like this. Suppose I enumerate the balls, ball ...
1
vote
1answer
69 views

Sigma Algebra: Etymology

Why do we talk of sigma algebras in measure theory. As far as I know sigma is related to the countability. But what does it stand for?
1
vote
2answers
56 views

Boolean algebra simplification hw

I'm given the equation $F=(a+b+c)(a'+b')(a+b'+c)$ and it's supposed to simplify into a sum of two product terms, each with two literals. I know the answer is $ab'+a'c$, but I'm unsure how to get ...
0
votes
2answers
129 views

How to construct the truth table for a combinational circuit

I am trying to construct the truth table for a combinational circuit with the following conditions : A) Room with 4 doors , 1 light, a switch near each door that controls the light (4 in total) B) ...
0
votes
0answers
33 views

What am I doing wrong simplifying here?

Our professor asks us to simplify this question in our notes: = ABC+AB'[A'C']' This is what I did: ...
2
votes
2answers
272 views

Is my answer for this truth table & boolean expression correct?

I was given the following boolean diagram: I had to come out with the truth table and the simplified expression. I need help to check if my answers are correct below.
0
votes
1answer
54 views

Simplifying Boolean Algebra Expression with 3 variables

Can someone help me simplify this in Boolean algebra? It should be one step at a time so I can understand it. The expression is: $(x+y+z)(x+z)(x'+y+z)$ I tried doing this: (it's probably wrong, ...
2
votes
1answer
81 views

What does quotienting by a congruence mean?

I have come across quotient algebras in my different mathematics courses. I know of quotienting with normal groups, quotienting with ideals etc. While studying Boolean Algebra I encounter quotienting ...
0
votes
1answer
57 views

Discrete Mathmematics

Are the boolean functions $(p\wedge \neg q)\vee (\neg r\wedge q)$ and $(p\vee \neg q)\wedge (r \vee \neg q)$ equal? Explain your answer. Here my solution, Please give me a feed back on this solution, ...
1
vote
1answer
313 views

Simplifying the expression using Boolean Algebra

Simplifying the expression using Boolean Algebra into sum-of-products (SOP) expressions . refers to AND + refers to OR (y' + x) ∙ (z + z') ∙ (y' + x') + (z + x'∙z) ∙ (x + y) This is what I have so ...
0
votes
1answer
42 views

Homomorphism between a ring which is a boolean algebra and one which is not.

I remember reading in a textbook that there can exist a homomorphism between a ring which is a boolean algebra and one which is not. Can anyone give me some example of this.
1
vote
2answers
101 views

Boolean Algebra, removal of redundant term

How do I simplify this boolean expression A¬B + A¬C + BC¬D + A¬D to A¬B + A¬C + BC¬D with boolean algebra? The A¬D is redundant, I can see why it is when I examine the truth table for this ...
0
votes
1answer
37 views

Boolean Functions-Algebraic rules for Boolean functions-Associative Rule

Is the function $(p \wedge q) \vee r$ equal to the function $p \wedge (q \vee r)$? Let $a(p,q,r)=(p \wedge q) \vee r$ $b(p,q,r)= p \wedge (q \vee r)$ By associate law $a=b$, but using $a(0,0,1)=1$ and ...
1
vote
0answers
117 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 ...
1
vote
1answer
37 views

Boolean Equation Transformation

Can someone show me the steps in getting from $f = (ab + c')(d' + e + f')$ to $f = abe +ab(df)' + c'e + c'(df)'$? I am trying to relearn Boolean algebra after a long hiatus.
1
vote
1answer
515 views

Boolean Algebra Distributive Laws

Given that $x\cdot(y+z)=(x\cdot y)+(x\cdot z)$ and $x+(y\cdot z)=(x+y)\cdot (x+z)$, what is the name for the opposite of those rules? Say I'm trying to prove the opposite, and I need to simplify from ...
0
votes
1answer
144 views

Logic boolean algebra problem

so I have to prove that these equations : are equivalent?
0
votes
1answer
66 views

Boolean Queries in First Order Logic

I understand first order logic and how its constructed but I have some trouble understanding how the following statement and its FO query are formed. This is from a book. ...
1
vote
1answer
28 views

Proving the Boolean expressions

Are these two Boolean expressions the same? *$co$ is the carry out while $ci$ is the carry in.
1
vote
0answers
28 views

Can this be simplified any further? (Boolean algebra)

I've been working on this expression, but all my attempts have failed to simplify it further. $$A'.B' + A'.B.C' + A'.B.C + A.B'.C'$$ I have tried to pick out $A'$ based on the distribution law: ...
-1
votes
2answers
22 views

boolean expressions simplification Help needed.

I am stuck simplifying. Can anyone help? It states that $$ (XY’+YZ)’ = X’Y’ + X’Z’+YZ’ $$ I tried all axioms yet I can't figure it out.
2
votes
2answers
29 views

Prove $ab + ab\overline{c} + bcd = b(a+c)(a+d)$

Do I need to use absorbtion law to prove them? $ab + ab\overline{c} + bcd = b(a+c)(a+d)$ $ab + cd = (a+c)(a+d)(b+c)(b+d)$. For 1), I simplified $ab+ ab\overline{c} + bcd$ into $b(a\overline{c} + ...
2
votes
1answer
93 views

the quotient boolean algebra of $P(\kappa)$ over the nonstationary ideal

Let $\kappa$ be a regular cardinal. Then the quotient boolean algebra over the nonstationary ideal, $P(\kappa)/I_{NS}$ is $\kappa^+$-complete. Specifically, any $S \subseteq P(\kappa)/I_{NS}$ of ...
0
votes
1answer
144 views

Two question on ternary Cantor set & Jordan content

Is it true that all subsets of the Cantor set have Jordan content zero? What is the definition of countably generated Boolean algebra? Does the Boolean algebra of subsets $[0,1]$ which ...
1
vote
2answers
58 views

Boolean simplification expression

In words my problem is NOT(p AND q) AND (NOT p OR q) AND (p OR p). I have rewritten it in symbols ¬(p ∧ q) ∧ (¬p ∨ q) ∧ (p ∨ p) I got this far: (¬p ∨ ¬q) ∧(¬p ∨ q) ∧ p Any help please?
2
votes
0answers
130 views

Back-and-Forth Argument vs. “One-Way” Argument

The wikipedia article on the Back and Forth Argument claims at the end: If we iterated only step $(1)$, rather than going back and forth, then in some cases the resulting function from A to B ...
1
vote
1answer
11 views

Converting to complements

Let's say I wanted to convert the ands and positive variables to their complements and ors. Would this be correct? $$DE=$$ $$(DE)''=$$ $$(D'+E')'$$ Or another example: $$D'E=$$ $$(D'E)''$$ Can ...
1
vote
1answer
57 views

boolean algebra simplyfing

I need to solve these expressions with boolean algebra: $$Z = a'bc+ab'c+abc'+abc\mbox{ AND }Z = a'(b+db'c')+a'b'(d'c'+c)$$ Every advice is more then welcome. Thanks
0
votes
1answer
44 views

Can I factor out or statements on the other side of an equation in boolean?

I have this boolean equation: X'Y'+XY+X'Y=X'+Y I want to prove it. Now I was wondering if I can rearrange this equation, if I could, so I can factor out the ...
0
votes
1answer
38 views

Simplify a Boolean Expression

I have to simplify this w′x′y′z + wx'yz' + w'xyz' I keep getting different answers depending on whether I start on the left or the right of the expression Any advice or help would be appreciated. ...
1
vote
1answer
45 views

A problem with a boolean function.

This is one of my assignment problem and I almost finished others. This question confused me for quite a long time and now I get nothing about that. I did understand what is an increasing function ...
2
votes
1answer
24 views

Boolean matrices and Algebra

Let us consider, a set of binary rectangular matrices of finite dimensions, call the set as $T$. The cardinality of the set $T$ is $2^{mn}$ where each matrix are of order m cross n. Suppose $S$ is a ...
1
vote
1answer
341 views

convert circuit to nor only gates

for an assignment I need to convert a circuit to NOR gates only circuit. (A+B)C + D I know that morgan's theorem states: (a) (A+B)'=A'B' (b) (AB)'=A'+B' I've seen online how to convert some ...
1
vote
2answers
163 views

Prove $(A \backslash B)'\backslash (B \backslash A) = B \backslash A$

Let $A$ and $B$ be subsets of some universal set. Prove that $(A \backslash B)'\backslash (B \backslash A) = B \backslash A$ Given: Definition 3.3.1 states that $A$ and $B$ are sets. The complement ...
1
vote
1answer
3k views

Boolean-expression simplification $F = AB'C + (A'B' + ABC'D)'$

Here are my solutions. Hence: I am stuck on where or what path I am going to take Problem: F = AB'C + (A'B' + ABC'D)' Solution 1 --------------- F = AB'C + (A'B' + ABC'D)' = AB'C + (A'B')' (ABC'D)' ...
1
vote
2answers
72 views

A detail in the proof of Stone representation Theorem

Let $(\mathcal{B},\sqcap,\sqcup,\leq)$ be a Boolean algebra. Let $x,y\in\mathcal{B}$. I want to prove the following implication: $$x\sqcap y'\leq 0\Rightarrow x\leq y$$ where $y'$ is the complement ...
0
votes
3answers
250 views

Using rules of inference (Leibniz) to prove theorems.

Leibniz: If $A \equiv B$ is a theorem, then so is $C[p:= A] \equiv C[p:= B]$. Note: p is "fresh" means p doesn't occur in $A, B, C$. I am trying to understand how to use Leibniz rule of inference for ...
0
votes
2answers
48 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? ...
-1
votes
4answers
408 views

Prove $A \subseteq B \cap C$ if and only if $A \subseteq B$ and $A \subseteq C$

Prove the following for any sets $A,B$ and $C$. This is actually two sets that I'm trying the prove. The title character restriction wouldn't allow me to post both at the same time. a. $A \subseteq ...
1
vote
3answers
67 views

Where did I go wrong with this Boolean simplification?

I am completely new to Boolean algebra, and I've tried to simplify this expression. All I did is tried to follow my lecturers methods, but I don't think it's right, and I have no idea how to do it. ...
1
vote
1answer
48 views

Boolean equation simplification

This is the problem: XY’ + XYZ + XY'Z= X + Y'Z And so far I have this, XY’ + XYZ + XY'Z= X + Y'Z X(Y’ + YZ + Y’Z) Factor out X X(Y’ + Z + Y’Z) De Morgan Any tips on how to proceed? I know ...