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
0answers
26 views

LL(1) grammar for boolean language

Is there a LL(1) grammar for this language? Here are some words of this language. It is a boolean logic, which uses negation, binary operators and braces (redundant braces are allowed too): A ...
0
votes
0answers
20 views

What can we say about the space just by looking at its Borel sets?

What can we say about a compact space $X$ just by looking at the Borel sets of $X$? In general, it seems that not much but maybe it is still not a bad question. For instance, let $X$ be a compact ...
0
votes
2answers
177 views

Every boolean function is constructed from $\wedge$'s and $\vee$'s

Prove that not every boolean function is equal to a boolean function constructed by only using $\wedge$ and $\vee$. Here is my solution, can I ask for a feed back on my solution please? $p∧q$ ...
1
vote
2answers
32 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
62 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
29 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: ...
1
vote
1answer
22 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, ...
0
votes
0answers
8 views

Cardinality of a subalgebra of a boolean algebra

Let $X$ be a subset of a Boolean algebra $B$, and let ,$A$ be the subalgebra generated by $X$. Show that, if $X$ is finite, then $|A|$ $\leq$ $2^{2^{|X|}}$ , and that, if X is infinite, then |A| = ...
0
votes
1answer
21 views

A boolean algebra is complete iff its Stone Space is extremally disconnected

I have the following proof, but I don't understand one of the steps: Theorem 4.4. A Boolean algebra is complete iff its Stone space is exlremally disconnected. Proof. Identify the given ...
0
votes
0answers
15 views

A filterbase generating filter F

Show that a non empty subset $X$ of a filter $F$ in $B$ is a base for $F$ iff $X$ generates $F$ and for all $x,y$ $\in$ $X$ $\exists$ $z $ $\in$ $X$ such that $z$ $\leqq$ x $\wedge$ y.
2
votes
1answer
60 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
47 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, ...
0
votes
1answer
30 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
1answer
53 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
41 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
21 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
34 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 ...
0
votes
1answer
51 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
25 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
21 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
17 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
27 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
82 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 ...
1
vote
2answers
47 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
2answers
128 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.
1
vote
1answer
10 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 ...
2
votes
0answers
84 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
45 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
43 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
28 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
43 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 ...
1
vote
1answer
128 views

Examples of boolean functions in conjunctive normal form

Give an $n$-variable Boolean function $f(x_1; x_2; \cdots ; x_n)$ in conjunctive normal form so that $f$ is $1$, respectively, (a) If at least one of the $n$ variables is $1$; (b) If at most one of ...
2
votes
1answer
17 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 ...
0
votes
0answers
33 views

How to show that two (Boolean) algebras are NOT isomorphic?

Suppose that we have two algebras $A$ and $B$. To show such algebras are isomorphic, all we have to do is constructing a bijective homomorphism between them. Not for negative case, we should check all ...
1
vote
1answer
106 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 ...
0
votes
2answers
46 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
vote
2answers
114 views

Boolean Simplification (ABCD)' + ((CD)'(B+D)'

I have to simplify (ABCD)' + ((CD)'(B+D)' function using boolean algebra. I simplified it using a truth table and got ...
0
votes
3answers
130 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 ...
1
vote
1answer
44 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 ...
0
votes
1answer
26 views

need help simplifying boolean algebra exrpressions

Can someone walk me through simplifying the following expression? $$a\lnot b\lnot s + ab \lnot s + \lnot abs + abs$$ help and advice is appreciated!
0
votes
1answer
22 views

Homomorphism theorem for boolean algebras

This theorem states that every boolean ideal $I$ of a boolean algebra $A$ is the kernel of a boolean isomorphism. I'm reading a paper where the author presents a short proof of this theorem, saying ...
0
votes
3answers
43 views

Simplify this Logic Function?

Have a Hardware Lab to do, and I need to reduce the following function before I actually hook it up to the Logic Trainer. (not ac) + (abc) + (a not c) Or: $\lnot (a \land c) \lor (a \land b ...
1
vote
1answer
57 views

Simplification of a Boolean Expression

I want to simplify this expression: ACD' + E(A+C)(A'+D') + A'C . The result must be a product of sums, where every sum should be consisted of just two variables. For example (A+B)(C+A)(Z+Y) ... ...
0
votes
2answers
42 views

simplify the boolean expression

I'm fairly new too boolean algebra. I've tried simplifying this equation but I'm not quite sure if I've done it correctly. Simplify to 1 literal, (X + Y + Y'Z)(Y + X)(Y + X') My attempt: ...
1
vote
2answers
91 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 ...
0
votes
4answers
205 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
2answers
47 views

Exercise regarding boolean algebra?

We need to simplify $AC+A'B'C$ $Y=A'B' +A'B C'+(A+C')'$ For (1) I wrote $C(A+A'B')$ but the result must be $AC+ B'C$. How do I get that to happen? I tried to simplify (2) using deMorgan but no ...
2
votes
1answer
54 views

On proving that $\mathcal{P}(\omega)/Finite$ is atomless

As I mentioned elsewhere, I'm working on Schimmerling's A Course on Set Theory. One of the nice features of the book (for me, anyway) is the addition of some interesting exercises on Boolean algebras. ...
0
votes
1answer
37 views

boolean algebra question here very short?

We have the Boolean expression Y=A'BC' + ABC'+A'BC Simplify it. Now, this is what I did Y=BC'(A'+A) +A'BC. Now using idempotence ...
1
vote
1answer
46 views

non-atomic complete Boolean lattice

Is there a Boolean complete lattice that is not atomic?