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
0answers
75 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
27 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
26 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
87 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
29 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
38 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
71 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
56 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
28 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
87 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
69 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
109 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
107 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
3answers
154 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
21 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
1answer
55 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
85 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
70 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
33 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 ...
15
votes
0answers
538 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
60 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
260 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
37 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?
1
vote
1answer
35 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
63 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
99 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
73 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
127 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
48 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
61 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.
1
vote
0answers
12 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
23 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
13 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
87 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
73 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
vote
1answer
142 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 ...
0
votes
0answers
49 views

Whats wrong with this reasoning… A Textbook Example?

This question is directly related to another one, as I see it the faulty reasoning is applied in the proof I will giving next: Lemma: Suppose we have $b$ boolean functions with two arguments (like ...
1
vote
1answer
70 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 ...
0
votes
0answers
34 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
21 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
217 views

Not every boolean function is constructed from $\wedge$ (and) and $\vee$ (or)

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
52 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
105 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
30 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
43 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
68 views

A boolean algebra is complete if 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
20 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
77 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
55 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
40 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.