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
3answers
110 views

Construct XNOR with only OR gates

Is it possible to construct the XNOR gate which is given as, a XNOR b = (a AND b) OR (~a AND ~b), by using only OR gates. So from the definition, the question boils down to: can you construct the AND ...
1
vote
1answer
31 views

Boolean-like algebra

Suppose one had an algebra that that follows most of the laws of Boolean algebra (associative, commutative, distributive, identity, annihilator, idempotent, double negation, De Morgan) but does not ...
0
votes
1answer
58 views

A well-defined operation on measure algebra

Let $(X,\cal{M},\mu)$ be a measure space, and for $E,F\in \cal{M}$ write $E \sim F$ iff $\mu(E \Delta F)=0$. Let $\widetilde{\cal{M}}$ be the set of equivalence classes in $\cal{M}$ for $\sim$; for ...
1
vote
2answers
108 views

How to prove the divisors of 15 form a Boolean algebra

This from Exercise 3.1 in "A Beginner's Guide to Discrete Mathematics" Let B be the set of all positive integer divisors of 15, that is B = {1, 3, 5, 15}. Prove that B forms a Boolean algebra with ...
3
votes
1answer
92 views

Prove if Tautology, Contradicton, or Neither. Is my proof ok?

Determine whether $((p \Rightarrow q) \Rightarrow r) \Leftrightarrow (p \Rightarrow (q \Rightarrow r))$ is a tautology, a contradiction, or neither. If $p,q,r = (0,0,0)$ then $((p \Rightarrow ...
1
vote
1answer
87 views

Alternative to xor(A,B,C)

How can we make a comprehensive statement, which will correspond to the truth table of xor (A, B, C) by combining logical operators AND (&), OR (|), XOR (xor) and NOT (!)?
2
votes
1answer
182 views

Convert a boolean function into K-map

I would like to know how can I convert the following boolean function into a truth table and accordingly construct the k-map $$F = A'B'C'+B'CD'+A'BCD'+AB'C'$$ thanks in advance :)
0
votes
1answer
42 views

Number of non-increasing boolean functions of $n$ booleans, up to permutations.

How many non-increasing boolean functions of $n$ boolean variables are there? I don't want to count functions that ignore some of their inputs. If two or more functions differ only by permuting their ...
17
votes
0answers
761 views

Is this $really$ a categorical approach to $integration$?

Here's an article by Reinhard Börger I found recently whose title and content, prima facie, seem quite exciting to me, given my misadventures lately (like this and this); it's called, "A Categorical ...
2
votes
1answer
90 views

How to prove that linear functions cannot represent binary functions

Yesterday, I thought about representing boolean algebra as linear functions: For some vector space $V$ and for some $A, B \subset V$ such that $A \ne \emptyset \,\wedge\, B \ne \emptyset ...
1
vote
5answers
74 views

If one of the hypotheses holds, then one of the conclusions holds. (looking for a proof)

Using a huge truth table, I proved the theorem below. I cannot find a more elegant proof. I tried to rewrite expressions; e.g. using the distributive laws and the laws of absorption - to no avail. Is ...
2
votes
3answers
65 views

Proving $\neg A\vee(A\wedge \neg B)= \neg A \vee \neg B$.

How do I prove using boolean algebra that $\neg A\vee(A\wedge \neg B)= \neg A \vee \neg B$? I can see it in the logic table and it is logical, but I can't prove it mathematically.
1
vote
1answer
42 views

Number of Positive Definite Binary Matrices

How may positive definite matrices (over finite field- $F_p$) are possible? What is the criterion in getting those?
5
votes
6answers
4k views

how to solve system of linear equations of XOR operation?

how can i solve this set of equations ? to get values of $x,y,z,w$ ? $$\begin{aligned} 1=x \oplus y \oplus z \end{aligned}$$ $$\begin{aligned}1=x \oplus y \oplus w \end{aligned}$$ $$\begin{aligned}0=x ...
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
150 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
116 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
141 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
60 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
153 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
204 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
75 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
71 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
136 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
286 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
55 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
317 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
107 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
40 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
123 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
524 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
160 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
148 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 ...
2
votes
2answers
59 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
134 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 ...