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
480 views

What is the number of self dual boolean functions?

The dual of a Boolean function $F(x_1,x_2 \dots x_n,+,\bullet)$, written as $F^D$, is the same expression as that of $F$ with $+$ and $\bullet$ swapped. $F$ is said to be self-dual if $F=F^D$. What is ...
2
votes
2answers
1k views

Proving hypothetical sylloligism (p implies q, q implies r, therefore p implies r) with boolean algebra

I'm trying to prove the hypothetical sylloligism using boolean algebra. We already have a solution using propositional logic, which relies on proof by contradiction. $(p \implies q) \wedge (q ...
1
vote
1answer
48 views

AND using XOR and OR?

Is there a way to make an AND using only XOR and OR. I know that a XOR b = ab'+ba' but I have no idea how to proceed. Could it be impossible?
0
votes
2answers
189 views

How to simplify following boolean expression? A+A'BC+BC'?

please help I'm stuck. I'm trying to solve this. so far I have: a) a+b+c b) a+bc c) a+b d) a+b but for e) I can't progress further since I don't know how to deal with a'bc in this case. ...
-1
votes
1answer
43 views

Boolean Algebras

simplify: (1) $f= pq+r$ (2) $g=a+bc+a'bc'd$
0
votes
1answer
58 views

Finding conjunctive normal form of a Boolean polynomial

I have to find the conjunctive normal form of the following Boolean Polynomial : $(x_1+x_2+x_3)(x_1x_2+x_1'x_3)'$ I simplified this polynomial to get $x_1x_2'+x_1x_2x_3'$ for which i then formed the ...
1
vote
1answer
74 views

Simplification of a boolean polynomial

I have to simplify the following Boolean polynomial using $x\land y$ = $xy$ and $x\lor y$ = x+y : $xy'+x(yz)'+z$ =$xy'+x(y'+z')+z$ =$xy'+xy'+xz'+z$ =$xy'+xz'+z$ My book gives the following ...
0
votes
3answers
80 views

Terminology: algebras, sigma-algebras, complete algebras…

There are 2 things which create a lot of confusion in my mind. 1) I know that every sigma-algebra is an algebra. But not every algebra is a sigma-algebra. Put differently, it seems that ...
1
vote
1answer
77 views

Semantic consequence

I'm studying refutation trees in computer science II, but I have a big doubt: Let $\Gamma, \Psi \subseteq F_m$ Is the following hypothesis true? $\Gamma \vDash \Psi \iff \not\vDash\{\Gamma,\lnot ...
1
vote
2answers
138 views

Boolean Expression simplification help

Hi I am new to the board. Taking a computer architecture course and I am having trouble understanding further simplification on a question I got on a previous quiz. When I type in the expression ...
0
votes
1answer
42 views

Boolean Simplification for Kmap

Diclaimer: This is not a homework assignment, it's a practice sheet that already has answers provided and is not graded in any way, however the steps are not shown hence the question. I'm having ...
0
votes
1answer
43 views

Boolean algebra simplification.

I start with: $$\bar{A}\bar{B}\bar{C}+\bar{A}BC+A\bar{B}\bar{C}+A\bar{B}{C}=A\bar{B}+\bar{B}\bar{C}+\bar{A}BC$$ then I did: ...
5
votes
2answers
115 views

Boolean algebra question.

Is there a way to show that $$A\bar{B}C\bar{D}+D=A\bar{B}C+D$$ using the rules of boolean algebra? I tried several methods such as expanding D with $$D(D+\bar{D})$$ or adding $$D\bar{D}$$ to the ...
2
votes
1answer
72 views

How to solve this boolean algebra problem?

Given two expressions: $$A\bar{D}+A\bar{C}D +A\bar{B}C + ABCD = Y$$ and $$BD+A\bar{C}D=Z$$ is there a way to simplify this using the rules for Boolean Algebra? I tried different combinations, but if I ...
1
vote
1answer
33 views

Can covering be done on two elements?

The covering rule is: $$B \bullet (B+C) = B$$ and $$B+(B \bullet C)=B$$ So does it follow from this rule that: $$B \bullet A \bullet \bar{C} + B \bullet D \bullet\bar{F} = B \bullet ...
1
vote
1answer
43 views

Boolean Function with ^ and or

Please provide feedback on my answer to this question. Question: Prove that not every boolean function is equal to a boolean function constructed by only using ^ and or. Answer: True, Suppose that a ...
0
votes
3answers
60 views

finding a boolean function with specific property

The problem I am trying to solve is: Prove that not every boolean function is equal to a boolean function constructed by only using $\wedge$ and $\vee$. My solution is $$\left(p\wedge\thicksim ...
2
votes
1answer
74 views

Arrow's Impossibility Theorem Using Boolean Algebra

I am currently working on a research project which involves using Boolean matrices for the proof of Arrow's Impossibility Theorem and various other lemmas and results related to quasi ordered sets. In ...
3
votes
1answer
140 views

Boolean Least Squares semidefinite relaxation

So I'm working on the Boolean least squares problem that comes up a lot in circuit design. In its raw form, it looks like this, $$\phi = \min \operatorname{trace}(A^TAX) - 2b^TAx + b^Tb$$ s.t. $$X = ...
2
votes
0answers
120 views

Simplify Product of Sums

Similar question to: Boolean Algebra - Product of Sums I was given a truth table and asked to give the sums-of-products and the product-of-sums expressions. I reduced the sums-of-products ...
1
vote
1answer
46 views

Proving Boolean Functions

Please check my answer to this question and give me feedback . Question: Either exhibit 333 different boolean functions on the three variables p,q,r, or prove that there aren't 333 different such ...
0
votes
1answer
27 views

Boolean Functions with p,q,r

Please give me feedback for my answer to this question. Question: (1) Are the boolean functions $(p \land \neg q) \lor ( \neg r \land q)$ and $(p \lor \neg q) \land (r \lor \neg q)$ equal?. Explain ...
2
votes
3answers
207 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
36 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
2answers
50 views

showing Boolean algebra equality

I have this exercise in my worksheet : Show that x (z ⊕ y) = xz ⊕ xy I reached this in solving it , but didn't reach the final equation x(z'y + zy') xz'y + xzy' please can someone show how
1
vote
2answers
246 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 ...
0
votes
1answer
77 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 ...
0
votes
2answers
38 views

Boolean function construction [duplicate]

I need some proof on this statement that not every boolean function is equal to a function constructed by only using ∨ and ∧. I need a boolean function that does not constructed using ∧ and ∨ which I ...
3
votes
1answer
99 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
179 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
449 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
324 views

Boolean algebra - cube - minimal disjunctive normal form

I have a test coming up and I would like to know how to solve these kinds of problems. This is the description: ...
6
votes
3answers
230 views

Peculiar examples to the Stone Representation Theorem

The Stone Representation theorem states that every Boolean algebra is isomorphic to a field of sets. That is, a Boolean algebra whose elements are sets, and sums, products, negation are union, ...
2
votes
1answer
60 views

Is this a good enough proof?

Is this proof good enough? If not, any feedback would be appreciated. Thanks. Either exhibit $333 $ different boolean functions on the three variables $p; q; r,$ or prove that there aren’t $333$ ...
2
votes
1answer
115 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 ...
0
votes
1answer
57 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 ...
32
votes
0answers
1k 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
3answers
68 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.
0
votes
1answer
367 views

Boolean algebra simplification question

I'm trying to simplify the follow SOP expression: $\bar{A}$$\bar{B}$$\bar{C}$ + $\bar{A}$B$\bar{C}$ + $\bar{A}$BC + AB$\bar{C}$ Using a K-map (unless I've erred) it should simplify to: ...
1
vote
1answer
53 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?
2
votes
1answer
165 views

How do Boolean-valued functions work?

Consider this function: $$P: X\to \{true, false\}.$$ There's nothing in that expression that says when $X$ is true and when it is not true. How do these work?
1
vote
2answers
69 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
1answer
429 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
206 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
347 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
87 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". ...
0
votes
2answers
71 views

Boolean functions built from $\wedge$ and $\vee$ [duplicate]

Prove that not every Boolean function is equal to a Boolean function constructed by only $\wedge$ and $\vee$. Please can you help me giving some hint.
2
votes
0answers
31 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
1answer
106 views

Explain why the description defines a Boolean Algebra

This is the exercise: Let $A = \{a,b\}$ and list the four elements of the power set $\mathcal P(A)$. We consider the operations $+$ to be $\cup$, $\cdot$ to be $\cap$, and complement to be set ...