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
2answers
249 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$ ...
22
votes
2answers
1k views

Any two points in a Stone space can be disconnected by clopen sets

Let $B$ be a Stone space (compact, Hausdorff, and totally disconnected). Then I am basically certain (because of Stone's representation theorem) that if $a, b \in B$ are two distinct points in $B$, ...
1
vote
3answers
1k views

Show that $ \{\lnot,\leftrightarrow\} $ is not functional complete

I have to prove that this set of logical operators is not functional complete - $$ \{\lnot,\leftrightarrow\} $$ i've tried implement this set by $ \{\rightarrow,\lor\} $ which is not functional ...
2
votes
2answers
8k views

How to prove that a set of logical connectives is functionally complete(incomplete)?

How to prove that a set of logical connectives is functionally complete(incomplete)? For example, we are given this set: $ \left\{\begin{matrix} f = (01101001) \\ g = (1010) \\ h = (01110110) \\ ...
3
votes
0answers
198 views

A construction on boolean lattices is itself a boolean lattice?

Let $\mathfrak{A}$ and $\mathfrak{B}$ be (fixed) boolean lattices (with lattice operations denoted $\sqcup$ and $\sqcap$, bottom element $\bot$ and top element $\top$). I call a boolean funcoid a ...
2
votes
4answers
12k views

Prove XOR is commutative and associative?

Through the use of Boolean algebra, show that the XOR operator ⊕ is both commutative and associative. I know I can show using a truth table. But using boolean algeba? How do I show? I totally have ...
2
votes
1answer
918 views

Boolean Algebra, Simplification: Don't know the method used

Here's the Karnaugh map: The answer I should be getting from the Karnaugh should be: T = R ∙ (CGM)' I'm really not seeing how this was arrived at through any ...
1
vote
1answer
97 views

proof of functional completeness of logical operators

If I know that the set of operators {∨, & , ¬} is functionally complete, how do I go about proving/disproving the functional completeness of the following set of operators? a) $\{\vee,\neg\}$ b) ...
10
votes
2answers
420 views

A matrix w/integer eigenvalues and trigonometric identity

Any intuition and/or rigorous arguments on the proofs of the following statements would be appreciated: Let $n$ be a natural number. (a) Consider the following Toeplitz/circulant symmetric matrix: ...
6
votes
2answers
252 views

Boolean algebras without atoms

Why is the theory of Boolean algebras without atoms $\omega$-categoric?
0
votes
2answers
83 views

How to prove boolean ordering question

Let $\sqsubseteq$ be the boolean ordering of $X$, so for every $x$ and $y$ applies $x \sqsubseteq y$ if $x \sqcap y = x$. Let $v, w, a, b \in X$ with $v \sqsubseteq a$ and $w \sqsubseteq b$. Show that ...
5
votes
3answers
6k views

Simplify $A'B'C'D' + A'B'CD' + A'BCD' + ABCD' + AB'CD'$

How do you simply the following equation? $$X = A'B'C'D' + A'B'CD' + A'BCD' + ABCD' + AB'CD'$$ Here is what I did: $$\begin{eqnarray} X & = & A'B'C'D'+A'CD'(B'+B) + ACD'(B+B') \\ & ...
2
votes
1answer
81 views

Proving $(p\to q)\lor (r\to s) \vdash (p\to s)\lor(r\to q)$ using Fitch notation

I'm supposed to prove the validity of the following $(p\to q)\lor (r\to s) \vdash (p\to s)\lor(r\to q)$ I'm very new to natural deduction, so I still haven't got a "feel" about it. I can prove ...
2
votes
1answer
70 views

How to get from the statement $(AB'+C'A'+C'B')$ to equivalent statement $(AB'+C'A')$?

I've been working a Boolean algebra problem for probably 2 hours at this point, and while I arrive at a much simplified equivalent expression, there's a simpler one yet. Basically, I start out with a ...
2
votes
2answers
225 views

Parity function proofing for every n>=1 using only AND, OR, 0, and 1

Consider the parity function: $F_n$($x_1$, $...$ ,$x_n$) $=$ $\oplus_{i=1}^n$$x_i$ where each $x_i$ is boolean. Prove that, for every $n \ge 1$, there is no way to compute $F_n$ using only ...
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.
1
vote
3answers
70 views

Where did I go wrong with this Boolean simplification?

I am completely new to Boolean algebra, and I've tried to simplify this expression. All I did is tried to follow my lecturers methods, but I don't think it's right, and I have no idea how to do it. ...
1
vote
2answers
1k views

Trying to simplify $A'B'C'D + A'B'CD + A'BC'D + AB'CD + ABCD$

My solution so far: $A'(B'C'D + B'CD + BC'D) + A(B'CD + BCD)$ $= A'(C'D(B' + B) + B'CD) + A(CD(B'+B))$ $= A'(C'D(1) + B'CD) + A(CD(1))$ $= A'C'D + A'B'CD + ACD$ $= D(A'C' + AC) + A'B'CD$ $= ...
0
votes
1answer
57 views

simplify boolean expression: xy + xy'z + x'yz'

As stated in the title, I'm trying to simplify the following expression: $xy + xy'z + x'yz'$ I've only gotten as far as step 3: $xy + xy'z + x'yz'$ $=x(y+y’z) + x’(yz’)$ $=x(y+y’z)+x(y’+z)$ But I ...
0
votes
1answer
193 views

Simplify the expression below by using the Algebra laws:

Simplify the expression below by using the Algebra laws: $$ AB + \overline{(\bar AC + B)\cdot \overline{(\bar B \oplus C)}} $$
-1
votes
1answer
35 views

Applying De Morgans Laws to $a+bc+\overline{a}b\overline{c}d$ in terms of the NOR operator

I need to synthesize $f=a+bc+\overline{a}b\overline{c}d$ into the NOR form. Can I split this since I know that $a+bc=(a+b)(a+c)=\overline{\overline{a+b}+\overline{a+c}}$? I'm just not sure how to go ...
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 ...
15
votes
7answers
20k views

Is XOR a combination of AND and NOT operators?

I'm not sure whether this is the best place to ask this, but is the XOR binary operator a combination of AND+NOT operators?
6
votes
4answers
4k views

An “atom” in Boolean algebra

Could someone explain what an atom in Boolean algebra means? I am acquainted with ring theory and group theory but not Boolean algebra. As far as I can tell from browsing around, it is something like ...
5
votes
6answers
5k 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 ...
4
votes
1answer
300 views

Lindenbaum algebra is a free algebra

The following is a continuation of this question. I would like to prove that the Lindenbaum algebra is a free algebra. Hopefully I would like to hear hints on how to proceed in the 'right' ...
3
votes
2answers
3k views

All finite boolean algebras have an even number of elements?

This seems obvious but I wanted to check, since I don't see it mentioned anywhere. If we define a boolean algebra as having at least two elements, then that algebra has a minimal element (0) and a ...
2
votes
1answer
343 views

Free boolean algebra

Consider the following definition: Let $X$ be a set and $e : X \mapsto A$ a mapping to a boolean algebra $A.$ We say that $A$ is free over $X$ (with respect to $e$) if for every mapping $f:X ...
4
votes
2answers
97 views

Power set representation of a boolean ring/algebra

Let $R$ be a finite boolean ring. It's known that there's a boolean algebra/ring isomorphism $R\cong \mathcal P(\mathsf{Bool}(R,\mathbb Z_2))$. I'm trying to get a feel for this. The subsets of ...
4
votes
0answers
77 views

FOUR-algebra - boolean algebra?

Belnap’s logic contains the the truth values 'true' ($t$), 'false' ($f$), 'unknown' ($\bot$) and 'paradox' ($\top$). Each of these is represented by a pair of bits: \begin{align} t &\rightarrow ...
3
votes
1answer
118 views

Are there further transformation principles similar to the Inclusion-Exclusion Principle (IEP)?

This question is motivated by the elaboration of the question Combinatorial Proof of Inclusion-Exclusion Principle (IEP). Let's consider the following two aspects: 1.) IEP transforms at least ...
3
votes
2answers
7k views

self dual boolean function

How many self-dual Boolean functions of n variables are there?Please help me how to calculate such like problems. A Boolean function $f_1^D$ is said to be the dual of another Boolean function ...
3
votes
2answers
360 views

How to write boolean expressions as linear equations

I want to convert a set of boolean expressions to linear equations. In some cases, this is easy. For example, suppose $a, b, c$ $\in$ {0,1}. Then if the boolean expression is: $a$ $\ne$ b, I could use ...
3
votes
3answers
192 views

The sum of a polynomial over a boolean affine subcube

Let $P:\mathbb{Z}_2^n\to\mathbb{Z}_2$ be a polynomial of degree $k$ over the boolean cube. An affine subcube inside $\mathbb{Z}_2^n$ is defined by a basis of $k+1$ linearly independent vectors and an ...
3
votes
3answers
12k views

Can someone explain consensus theorem for boolean algebra

In boolean algebra, below is the consensus theorem $$X⋅Y + X'⋅Z + Y⋅Z = X⋅Y + X'⋅Z$$ $$(X+Y)⋅(X'+Z)⋅(Y+Z) = (X+Y)⋅(X'+Z)$$ I don't really understand it? Can I simplify it to ...
2
votes
1answer
229 views

Proving that a set with a ternary logical connective is functionally incomplete (i.e. inadequate)

I am stucked at trying to prove that the set $\{\lnot ,G\}$ of logical connectives is inadequate where $G$ is a ternary connective that gives $T$ (True) if most of its arguments are $T$. For example: ...
2
votes
1answer
146 views

Extending the logical-or function to a low degree polynomial over a finite field

Let $x\in\{0,1\}^n$ be a binary vector of dimension $n$, and let $OR(x)$ be the "logical or" function (i.e., returns $1$ if at least one of the coordinates is $1$ and otherwise returns $0$). Is there ...
1
vote
1answer
41 views

How to Solve this Boolean Equations?

I have a Boolean Equations, described as below, $$\neg \mathbf{x} = \mathbf{M}\cdot \neg(\mathbf{M} \cdot \mathbf{x})$$ in which $\mathbf{M}$ is an $n\times n$ Boolean matrix, and $\mathbf{x}$ is an ...
1
vote
1answer
146 views

Is Belnap's four valued-logic a boolean algebra?

Belnap's logic contains the the truth values 'true' (t), 'false' (f), 'unknown' ($\bot$) and 'paradox' (T). Each of these is represented by pair a of bits: t $\rightarrow$ (1,0) f $\rightarrow$ (0,1) ...
1
vote
1answer
48 views

The ability of a logical statement to represent a two-place truth function.

How can i determine which two-place truth functions can be represented using a logical statement built out of a subset of two logical connectors in $ \{\rightarrow, \wedge, \vee ,\equiv \}$ ? for ...
1
vote
1answer
223 views

Fiction variables?

In every Boolean function $f(x_1, x_2,\ldots, x_n)$, for every $i$ ($1\le i\le n$), $x_i$ is called fiction variable if and only if when for every Boolean assessment for the rest variables $x_1, ...
0
votes
0answers
67 views

How to Solve Boolean Matrix System?

I have a Boolean Matrix System (BMS) as described below $$Ax=c$$ where $A$ is a $n\times n$ Boolean matrix (i.e., all entries are either 0 or 1), $c$ and $x$ are two $n$-dimensional Boolean column ...
0
votes
1answer
70 views

Duality Principle in Boolean Algebra - Why do I alway get !F instead of F?

I have the function: F = !(a && d || b || c) Now i apply the duality principle and exchange all * with + ...
0
votes
1answer
78 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. ...
6
votes
1answer
385 views

Non-isomorphic countable Boolean algebras

I'm trying to solve the next exercise: Construct a sequence $\mathcal{B}_0,\mathcal{B}_1, \ldots$ of countable Boolean algebras such that for all $m \neq n$ then $\mathcal{B}_m \ncong \mathcal{B}_n$. ...
6
votes
3answers
1k views

How to prove a set of sentential connectives is incomplete?

On Page 52, A Mathematical Introduction to Logic, Herbert B. Enderton(2ed), Show that $\{\lnot, \# \}$ is not complete. A set of connective symbols is complete, if every function $G : \{F, T\}^n ...
4
votes
3answers
142 views

Difficulty understanding why $ P \implies Q$ is equivalent to P only if Q.

I have difficulties understanding why $ P \implies Q$ is equivalent to P only if Q. I do understand that in the statement "P only if Q", it means if $ \lnot Q \implies \lnot P$". Regarding this ...
3
votes
1answer
56 views

The set of all polynomial functions from $\mathbb{Z}^3 \rightarrow \mathbb{Z}/(2)$

Let $f:\mathbb{Z}^3 \rightarrow \mathbb{Z}_2$ be a polynomial function in $\mathbb{Z}[x_1, x_2, x_3]$. Then $f$ has the form $f(x_1, x_2, x_3) = c_1 x_1 + c_2 x_2 + c_3 x_3 + c_4 x_1 x_2 + c_5 x_1 ...
3
votes
1answer
250 views

Proof of $(P\Leftrightarrow Q)\Leftrightarrow((P\Rightarrow Q)\wedge (Q\Rightarrow P))$

Hi I've been working through Applied Mathematics for Database Professionals and I'm stuck trying to proof this equivalence: $$(P\Leftrightarrow Q)\Leftrightarrow((P\Rightarrow Q)\wedge ...
3
votes
2answers
424 views

Is it possible to derive all the other boolean functions by taking other primitives different of $NAND$?

I was reading the TECS book (The Elements of Computing Systems), in the book, we start to build the other logical gates with a single primitive logical gate, the $NAND$ gate. With it, we could easily ...