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

28
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 ...
4
votes
0answers
68 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 ...
4
votes
0answers
120 views

Axioms as recreational mathematics

Before modern group theory, mathematicians studied concrete permutation groups: algebraically closed subsets of the set of all bijections on a set $X$ in which all inverses was included. This was the ...
3
votes
0answers
47 views

What are universal abstract $\sigma$-algebras on $\sigma$-frames?

In this paper, the authors make the following definitions: An (abstract) $\sigma$-algebra is a boolean algebra with countable joins. A $\sigma$-frame is a bounded lattice with countable joins, where ...
3
votes
0answers
149 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 ...
3
votes
0answers
61 views

A discrepancy in the total number of conjunctive normal forms and the number of distinct boolean functions.

Consider a set of truth literals $C$. The set $\{\text T, \text F\}^{\mathcal{P}(C)}$ is the set of all boolean functions over all subsets of $C$. This comes from the notation ...
3
votes
0answers
72 views

Proving Boolean Logic using Axioms

I am trying to prove boolean logic formulas using axioms. I have a lot of trouble deciding what to do, which axiom to use, when to use it, etc. I've asked others on proving formulas but they have all ...
2
votes
0answers
21 views

Expressing associativity as a Boolean SAT problem

Suppose we have a binary operation $B: S \times S \to S$ on a finite set $S$. We can encode $B$ as an array of $|S|^3$ Boolean values by setting $$ B_{ijk} \equiv \text{True} \quad \text{ iff } \quad ...
2
votes
0answers
30 views

Mathematics of two's complement

I am trying to understand the underlying mathematics of two's complement. Googling the topic gives me a lot of articles on how to invert the digits and add one, and why computers use this system ...
2
votes
0answers
76 views

Countably closed Boolean algebra of subsets of the real plane,

The following problem was in The American Mathematical Monthly : A generalized rectangle is $E \times F$ for any subsets $E,F$ of $\Bbb R$ (the reals). If $\mathscr{B}$ is the smallest countably ...
2
votes
0answers
35 views

Solving equation set with boolean operators and very specific format

I have to write a program to solve a set of equations like the following (+ is XOR and * is ...
2
votes
0answers
135 views

Coproducts and pushouts of Boolean algebras and Heyting algebras

I am having trouble of find a reference explaining how to compute coproduts and pushouts in the category of Boolean algebras and in the category of Heyting algebras. To be precise I am looking for ...
2
votes
0answers
38 views

Does the class of all periodic subsets of $\mathbb{Z}$ of peroid greater than $k$ form a field of sets?

We say that a subset $X\subseteq \mathbb{Z}$ is a periodic subset of $\mathbb{Z}$ of period $k$ if the set obtained from $X$ by adding $k$ to each element of $X$ is $X$ itself. Does the class of all ...
2
votes
0answers
114 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 ...
2
votes
0answers
76 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". ...
2
votes
0answers
25 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
0answers
178 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 ...
2
votes
0answers
66 views

Fields of sets in which, if the l.u.b. of a subset exists at all, it is the union of the subset

I am learning about boolean algebras and how they can be represented as fields of sets. Stone's representation theorem tells us that every boolean algebra is isomorphic to a field of sets. Consider an ...
2
votes
0answers
108 views

Matrix of integers to boolean matrix

My Question is about converting a matrix of numbers, say each row is an item and each column is a feature of the item. The features are currently integers but I want to convert the feature ...
2
votes
0answers
51 views

Algebraization of attribute-value logic

Jürgen Wedekind ("Classical logics for attribute-value languages", can be googled up) has defined an attribute-value logic as a fragment of predicate logic. There are no predicates except for ...
2
votes
0answers
42 views

Inferring simplest method to convert bit array 1 to bit array 2.

Consider the set of all bit arrays of length $n$. Now consider the set of all 1-to-1 functions that map from this set to this set. Now select a single function out of the latter set. Is there any ...
2
votes
0answers
329 views

Basis of a Boolean Algebra

I have a construct that I proved forms a (finite) Boolean Algebra of sets over a given universe. My questions are as follows: Do I immediately know that there exists a unique basis for it? If yes, ...
2
votes
0answers
52 views

Name for this type of space over a boolean algebra?

The structure has two carrier sets $E$ and $A$, operators $({}^*, \wedge)$ over $E$, and a ternary "decision" operator $D:E \times A \times A \to A$, written infix $(p?a:b)$, whose intended meaning is ...
2
votes
0answers
226 views

bent and hyper-bent boolean functions

Is the AND logic function considered to be a bent function. If so, how would you make a hyper-bent function using logic gates? Thanks!
1
vote
0answers
29 views

Proof that an boolean algebra is free

I have a problem with proving that something is a free boolean algebra. I tried using the definition on the following problem: Prove that the boolean algebra of all the functions from a four element ...
1
vote
0answers
10 views

A polynomial majority function

Let us introduce a boolean function $F(x_1,x_2,x_3,...,x_n)$, where $F=1$ when most of the variables $x_1,x_2,...,x_n$ are equal to $1$ and $F=0$ otherwise. This is called a majority function. The ...
1
vote
0answers
15 views

How many minimized forms can a boolean expression have with 4 variables?

I have this theoretical question I can't get my head around. Assuming I have a function (any function) with 4 variables, and I draw a Karnaugh Map in order to extract the most simplified expression ...
1
vote
0answers
35 views

Finding solution to matrix equation over GF(2) with minimal true variables

I am looking for a general way to find a solution to a system of equations in GF(2) such that the solution has the least amount of true variables. After Gaussian elimination I get a matrix like such: ...
1
vote
0answers
31 views

Hochschild cohomology of a boolean ring

I can't find any papers studying the Hochschild cohomology ring $H^*(B,B)$, where $B$ is a boolean ring, so I was wondering if this is known.
1
vote
0answers
14 views

How to perform binary transformations?

One of the steps in Binary Index Tree algorithm is to find a node's parent which is done by un-setting the rightmost SET bit. For example: if a node has index 1010 than it's parent is 1000. To apply ...
1
vote
0answers
40 views

Sum of Products Expression using $K$-map

Determine the minimum SOP, sum of products expression using $K$-Map $F(A,B,C,D,E) = (A’ + B + C’ + D + E’)(A’ + C’ + D + E )(A’ + C’ + E )AC’$ My problem is, in my class room we have always done ...
1
vote
0answers
43 views

how to determine if formula satisfies without creating a truth table

$(p \wedge q \wedge r) \wedge (\neg p \vee r)$ So far, what I have got is that $(p \wedge q \wedge r)$ satisfies because if $p$, $q$ and $r = 1$ then $(p \wedge q \wedge r)$ also $= 1$. For $(\neg p ...
1
vote
0answers
45 views

Question on free Boolean algebras

Every Boolean algebra $A$ is isomorphic to a field of set. In particular, if $A$ is finite, then $A$ is isomorphic to the power set of its atoms. Now, suppose that $A$ is free Boolean algebra with 2 ...
1
vote
0answers
32 views

Simple Boolean Algebra Exercise but stuck

I have the following exercise that I can't really solve or I am not happy with the result: If Team A loses, Team B and C will lose too If the Teams A and B win, Team C will lose If Team B ...
1
vote
0answers
56 views

Generators of free Boolean algebras

Suppose $\mathfrak{A}$ is a free Boolean algebra and $G$ a countable set of free generators of $\mathfrak{A}$. What is the cardinality of $\mathfrak{A}$ if $G$ is countably infinite, but we only ...
1
vote
0answers
37 views

boolean algebra - belnap logic

How to find out wether an algebra is a correct boolean algebra? So if we have the following algebra (rejects to belnap-logic theorems): $ \langle \{ w,f, \top , \bot \} , \wedge \vee \neg \rangle$
1
vote
0answers
90 views

reducing Boolean expression to minimum literals

I'm finding it tough to simplify these types of expressions. Here's my problem: $(a+b+c')(a'b'+c)$ I have to reduce this to the minimum number of literals. So far I've only broken it down to: ...
1
vote
0answers
39 views

Monotonic operators in classical logic

Which means monotony for a logical operator, and affinity, in propositional calculus affinity..., here on wiki do not quite understand!!
1
vote
0answers
39 views

Coset state for non-abelian hidden subgroup problem

On page 14 of his classic paper, Quantum factoring, discrete logarithms and the hidden subgroup problem, Jozsa introduced a function $f$ for the non-abelian hidden subgroup representation of the graph ...
1
vote
0answers
36 views

Product of binary Boolean operators

I'm interested in the set $\mathcal{P}_N$ of boolean functions of boolean variables $p_1, p_2, \ldots, p_N$ that can be written as products of operators of 2 variables only: $$ \phi(p_1, \ldots, p_N) ...
1
vote
0answers
116 views

Dual formula in propositional logic

There's something I don't understand in my course on propositional logic. In the case of x being a variable, the definition of its dual is x* = x. Right. However, further in the course, there's a ...
1
vote
0answers
45 views

Distributivity of lattices and prime ideals.

I need help proving that, if $L$ is a lattice with the property that for every nonempty proper filter $F$ and every ideal $I$ such that $F \bigcap I = \emptyset$ then there is a prime filter $G$ such ...
1
vote
0answers
146 views

How to convert a mod 2 function to an expression in Boolean Algebra

I'm not sure if this is the right place to post it but I have a question I'm having a hard time understanding. The questions is: Convert the function $X^3Y + 2XZ + WX + W$ mod $2$ to an expression ...
1
vote
0answers
35 views

Boolean algebra-dual of an expression

Can anyone think of an expression that is equal to its dual ? I've been trying to solve this for the past 2 hours, but nothing comes to mind.
1
vote
0answers
89 views

question in math logic: find the d.n.f. and c.n.f.

The question is as follows: Find the disjunctive and conjunctive normal forms of the following: $$ (A \to (B \to C)) \to ((A \to \neg C) \to (A \to \neg B)) $$ My solution is as follows, but I ...
1
vote
0answers
121 views

How should I think when implementing Patrick's method?

I have implemented Quine-McCluskey method of boolean function simplification. I ended up with the table of prime implicants: As you can see my results are the same as these on wikipedia. However ...
1
vote
0answers
32 views

How do I know that min-term can't be combined any further?

I'm trying to learn (and implement) Quine-McCluskey algorithm for boolean function minimalisation. I'm learning the algorithm from wikipedia example. From that I understood the following: Take all ...
1
vote
0answers
322 views

Convert from sum of products to product of sums (Boolean algebra)

I had to simplify a boolean expression with a k-map then put it into a NOR-gate implementation circuit. I haven't made the circuit yet, but here is the work I've done: Original function: $$F(w, x, ...
1
vote
0answers
54 views

The number of Balanced Boolean functions

Suppose we have n-variable Boolean function (BF) and we know that the weight of a Balanced BF is $2^{n-1}$. The total number of BFs are $2^{2^n}$, Affine BFs are $2^{n+1}$ and Linear BFs are $2^n$. In ...
1
vote
0answers
22 views

What if I am not given the labels of a Karnaugh map?

Simplify this expression represented by the map $$\begin{matrix} 1 & 1 & 0 & 1\\ 0 & 0 & 0 & 0\\ 1 & 1 & 1 & 1\\ 1 & 1 & 0 & 1 \end{matrix}$$ ...