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

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 ...
4
votes
0answers
78 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
126 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
22 views

Do DeMorgan's laws hold for pseudo-complement in Bi-Heyting Algebra?

A textbook says in Heyting Algebra, The pseudo-complement of an element $a$ is denoted as $a^{\ast}$. One of the DeMorgan's law $\left(\vee a_{i}\right)^{\ast}=\wedge a_{i}^{\ast}$ holds ...
3
votes
0answers
50 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
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 ...
3
votes
0answers
62 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
84 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
37 views
+50

How to deal with an 8 variable Karnaugh map

I'm reaching back into my high school days trying to remember one of the rules about Karnaugh Maps. I have an 8 variable input, and I remember that I should try and make the selections a big as ...
2
votes
0answers
26 views

Is every quotient algebra of a Boolean algebra isomorphic to a subalgebra?

Is every (non-trivial) quotient of a Boolean algebra isomorphic to a subalgebra of that Boolean algebra? And conversely is every subalgebra isomorphic to a quotient algebra?
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
33 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
79 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
38 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
169 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
40 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
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 ...
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". ...
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
0answers
196 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
109 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
54 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
375 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
53 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

Can the reduced product construction generate boolean-valued models?

In model theory, the reduced product construction contains a collection of structures or models, a set I that indexes the collection, and a filter U on I. Ultraproducts are a special case of reduced ...
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
17 views

General rules for transforming boolean equations?

Are there general or restricted rules for transforming between equivalent boolean equations? A concrete problem that I have is given the following equation: ...
1
vote
0answers
14 views

Tests for combinational logic - product of sums simplification

I am trying to understand how to simplify the Boolean cover function $(4+6)(12+14)(0+1+2+3)(11)(3)(9)(13)(10+14)(1+3+9)$ which is a stuck-at fault test cover function derived in this paper. I know ...
1
vote
0answers
31 views

Two alleged counterexamples (about boolean algebras)

Trying to solve this question, I propose two possible counter-examples. Please help me to understand whether these cases are really counter-examples. Let $\mathfrak{A}$ and $\mathfrak{B}$ be (fixed) ...
1
vote
0answers
48 views

Simplifying bitwise expressions

Using various methods it is possible to simply boolean expressions consisting of boolean operators and binary variables. In programming languages another closely related set of operators exists: ...
1
vote
0answers
13 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
33 views

What will be the answer to this K-Map?

I have a K-Map and I need to figure out which expression isn't equivalent to the provided K-Map. ...
1
vote
0answers
17 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
39 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
15 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
44 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
46 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
46 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
33 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
59 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
40 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
100 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
40 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
40 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
37 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
130 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
46 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 ...