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
19 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
12 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
13 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: ...
4
votes
2answers
39 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
0answers
47 views

Boole's functions' domain is D = {1, 2, 3, 4}. Find ∃xF(x, 2), when F(x, y) = 1100 1111 0011 0101. [closed]

The problem is, I actually do not understand this problem very well. When the logical function is given, making truth table is not a problem for me at all. I wonder, if this exercise requires to make ...
2
votes
1answer
41 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
28 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
18 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
2answers
40 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 ...
1
vote
1answer
25 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 ...
2
votes
1answer
29 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
43 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
19 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
19 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
51 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 ...
0
votes
0answers
14 views

Boolean Algebras and Spaces

Show that a countably infinite free Boolean algebra $B$ has a Boolean space homeomorphic to $2^\omega$; where $2$ is the discrete space $\{0,1\}$; hence B is isomorphic to the Boolean algebra of ...
1
vote
1answer
25 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
21 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
35 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
40 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 ...
3
votes
1answer
68 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
37 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 (!)?
1
vote
1answer
30 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
0answers
20 views

Homework Question [duplicate]

How to prove that not every boolean function is equal to a boolean function constructed by only using ∧ and ∨. Should I choose a specific function or just compare any two Boolean functions constructed ...
0
votes
0answers
28 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: ...
4
votes
2answers
55 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, ...
0
votes
0answers
17 views

algèbre de boole

hello By a communicating channel 0 and 1. As a result of a spurious noise (lightning, an electric switch manipulation, ...) transmitting a 0 is sometimes received as a 1 and vice versa. Let E = ...
2
votes
0answers
41 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
54 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
64 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
0answers
16 views

Boolean Algebra Simplification help

Can anybody help me solve this Boolean algebra, Im a bit stuck on it and any assiastance would be great. Thanks A'B'C'D' + A'B'CD + A'BCD' + A B'C'D'
0
votes
1answer
18 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 ...
10
votes
0answers
265 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
54 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
17 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
26 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?
0
votes
0answers
10 views

How do Boolean-valued functions work?

Consider this function: P: X→ {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
50 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
37 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
40 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
34 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= ...
3
votes
0answers
25 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
0answers
16 views

Proof by Induction… For any Boolean function F we can define its dual fd by?…

For any Boolean function $f$ we can define its dual $f^d$ by: $ f^d = ( x_{1}, x_{2},...,x_{n}) = \overline f(\bar x_{1}, \bar x_{2},...,\bar x_{n}) $ How do I prove this by induction?
1
vote
0answers
10 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
0
votes
0answers
19 views

Simple explanation of a Boolean function?

I took on the challenge to self study discrete math and I've come to Boolean functions. Please note, that I'm new to set notation (just learned it) and the form of the Boolean function confuses me ...
0
votes
0answers
9 views

Boolean prime covering

Let $\mathbb B^n$ be an n-dimentional boolean cube. The set ${E}$ of edges is called its 1-cover if any vertex of $\mathbb B^n$ belongs to exactly one edge from ${E}$. The 1-cover is prime if no ...
0
votes
3answers
69 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
49 views

Checking Boolean Algebra work - Simplification

I am currently working on an assignment for a CE class I am taking, and I wanted to know if I have been simplifying these equations correctly. I'm supposed to reduce them to a sum of products. 1) ...
-1
votes
0answers
22 views

Simplify $(y + z')' (x' + y)'$ to Sum of Products

This is my working $r: (y + z')' (x' + y)' = (y)' (z')' (x')' (y)'=xy'y'z=xyz$ The answer sheet says $= xy'z$ Please explain where I've gone wrong and show working
1
vote
1answer
27 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 ...