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

13
votes
0answers
371 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 ...
3
votes
0answers
103 views

Weak Amalgamation Property for Boolean algebras

I'm trying to study universal algebra and lattice theory by myself. Just got stuck with an exercise from Gratzer's "General Lattice Theory" and it seems to me that I don't fully understand the notion ...
3
votes
0answers
30 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
53 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
93 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
63 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
73 views

Are there impossible boolean constructions?

I was reading about logic and I remember, for example: That with the binary $\mathtt{NAND}$ connector can be used to assemble all the other binary connectors - I already know that there are primitive ...
2
votes
0answers
75 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
43 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
38 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
118 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
51 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
218 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
20 views

Logical operations precedence and calculator program

I write the C library intended to be used in evaluating math expressions. It should support boolean algebra also. So at the moment I'm stuck with boolean precedence. I'm not a mathematician so that's ...
1
vote
0answers
14 views

Simplying Boolean-Logic Expression

Can you help me simplify this or is this the simplified form? A = (X + Y + Z) (X + ~Y + ~Z) (~X + Y + ~Z) (~X + ~Y + Z) Here's my attempt: ...
1
vote
0answers
19 views

Boolean Expression Simplification (De Morgan's)

I need to prove that: $$ !(!(X.W) + !(X.Z))) = X.W.Z $$ I have tried multiple approaches but cannot figure this out. Using DeMorgan's theorem, I break the negative sign binding $XW$, and $XZ$, and ...
1
vote
0answers
43 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= ...
1
vote
0answers
11 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
1
vote
0answers
58 views

Expression conversion using de Morgan's laws

I'm sorry strongly, because it's a very dummy question... I have an example in the algebra of logic. I need to convert an expression using the rules of de Morgan - replace by the conjunction of ...
1
vote
0answers
22 views

Can this be simplified any further? (Boolean algebra)

I've been working on this expression, but all my attempts have failed to simplify it further. $$A'.B' + A'.B.C' + A'.B.C + A.B'.C'$$ I have tried to pick out $A'$ based on the distribution law: ...
1
vote
0answers
48 views

Expansion of subsets of a hamming ball in hypercube

Consider a hypercube graph $G_n = (V,E)$ in n dimensions. Let $H_{1/2} \subset V$ be the set which represents the hamming ball of radius $n/2$. That is for every $v \in H_{1/2}$ the hamming weight of ...
1
vote
0answers
27 views

“Optimal Disjoint Decomposition” of a Boolean Lattice Subset?

I am looking for the name (and, possibly, an efficient solution) of the following problem: Given a Boolean lattice $(L, \sqcap, \sqcup)$ with least element $0$, and a finite subset $X \subseteq L$, ...
1
vote
0answers
42 views

Given a finite set of points construct a polynomial that meets the points.

Say I have a set of points in $\mathbb{Z}^3 \times \mathbb{Z}_2$ each of which represent part of a mapping $(z_1, z_2, z_3) \mapsto z_4 \in \mathbb{Z}_2$. How do I find the the simplest polynomial ...
1
vote
0answers
129 views

Sum-of-products to product-of sums conversion

I need to convert $A'B'C'$ from sum-of-products form to product-of-sums form. I used a K-map and I'm not sure if the answer is $C' + AB' + A'B' + A'B$ or just $AB' A'B' + A'B$. I think that by ...
1
vote
0answers
216 views

Understanding Sum of product and complete sum of product

I have a pair of problems, the first two of my homework, and I'm already unclear on how finding SOP and CSOP for them work. The first: E=xy(1+z)y' It seems like this just reduces to 0, since 1+z ...
1
vote
0answers
114 views

Showing that a Boolean algebra is a Boolean ring

I've proved that a Boolean ring is a Boolean algebra but I am having trouble with the converse. The operation for + is defined as the symmetric difference for elements $a$ and $b$ from the Boolean ...
1
vote
0answers
87 views

Question regarding implicant chart of Quine-McCluskey algorithm

In https://en.wikipedia.org/wiki/Quine-McCluskey#Example, at the end of Step 1, there is a table that shows the number of 1's, minterms, 0-cube and size-2 implicants and size-4 implicants. But I am ...
1
vote
0answers
159 views

When to Stop Simplifying a Well-Formed Formula?

I mean simplifying a wff(well-formed formula)in which, only $\lor$, $\land$, $()$and $\lnot$ are allowed, as minimizing the occurence of connective symbols( $\land$ and $\lor$). It's self-evident ...
1
vote
0answers
204 views

Inverse function in multi-valued logic through the Webb function

Let Webb function in multi-valued logic as $Webb(x, y) = W(x, y) = Inc(Max(x, y))$. There is a theorem about any function in any multi-valued logic can be represented through the Webb function. Then ...
1
vote
0answers
74 views

Generating Input Binary Combination Dynamically

this is probably right forum to post this question I am currently working on a application where there is a requirement to generate binary combination of input signals in a truth table. The signal ...
1
vote
0answers
341 views

Number of canonical expressions

There is a question: What is the number of canonical expressions that can be developed over a 3-valued boolean algebra? I was trying to solve this. Canonical expression is the combination of ...
1
vote
0answers
61 views

$\Delta_0$-formulas in the Boolean-valued model $V^B$

I want to show that $\Vert \check x = \check y \Vert = 1$ implies $x = y$, where $\check x$ is the canonical name for $x$ in $V^B$. I'd like try induction over the ranks of $\check x$ and $\check y$ ...
1
vote
0answers
119 views

boolean algebra how can i prove a theorem

In a set of lattice in boolean algebra how can i prove this: $$x \cdot (y+z) \ge (x\cdot y) +(x\cdot z)$$
1
vote
0answers
179 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 ...
0
votes
0answers
33 views

simple exercise in Cylindric algebra

I am trying to gain a better understanding of cylindric algebra, so I made up this example. Given a general rule that someone's father's father is his/her grandfather: $\forall_X ~ \forall_Y ~ ...
0
votes
0answers
11 views

Matrix representation of Boolean algebra?

Is there such a thing as matrix representations of Boolean algebra? Give a boolean algebra with finite elements {a,b,c...} and operations $\cap, \neg$, we can regard $\cap$ as matrix multiplication ...
0
votes
0answers
19 views

Sum of squares of series of boolean variables

I am going to simplify the following series: $$\sum^4_{v=1} \left(1 - \sum^4_{i=1} x_{v,i}\right)^2 + \sum^4_{i=1} \left(1 - \sum^4_{v=1} x_{v,i}\right)^2$$ Since $x_{i,j}$ is a boolean variable, ...
0
votes
0answers
23 views

XOR with multiply operation.

can I do that $((A*5) \oplus A)==A*(5\oplus1)?$ and that $(A \oplus B/2) == ((2*A) \oplus B)$? Thanks.
0
votes
0answers
15 views

Boolean operator precedence

I have a confusion with the following proposition $p\leftrightarrow q\leftrightarrow(p\land q)\lor(\lnot p\lor\lnot q)$ how does this work? can it be $p\leftrightarrow(q\leftrightarrow(p\land ...
0
votes
0answers
14 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}$$ ...
0
votes
0answers
16 views

The empirically-obvious statement about minimization of Boolean functions

The statement: $\forall f,g: \{0;1\}^n \to \{0;1\} \; (n > 0),$ if $$|f^{-1}(1)| > |g^{-1}(1)|$$ then $f$ has the (non-strictly-)simpler minimization than $g$. $\text{ }$ As mentioned, the ...
0
votes
0answers
25 views

Dont understand application of Demorgans Law when simplifying to Sum of Products Form - Boolean Algebra

I'm having trouble trying to understand how this can be simplified. I'm stuck at the first part... The expression is: where a AND b is ab or a*b, and ...
0
votes
0answers
19 views

Simplifying conjunctive normal form

I have to simplify the following conjunctive normal form of a polynomial : $(x_1'+x_2+x_3+x_4)(x_1'+x_2+x_3+x_4')(x_1'+x_2'+x_3+x_4')$ I started off by using the fact that$(\alpha + \beta)(\alpha + ...
0
votes
0answers
57 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: ...
0
votes
0answers
18 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 = ...
0
votes
0answers
21 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
10 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
0answers
47 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 ...
0
votes
0answers
32 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 ...