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

15
votes
0answers
535 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
29 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 ...
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". ...
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 ...
2
votes
0answers
113 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
65 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
96 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
44 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
39 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
176 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
221 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
31 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
19 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
39 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
15 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
28 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
60 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
36 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
84 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
35 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
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= ...
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
1
vote
0answers
100 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
26 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
62 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
29 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
78 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 ...
1
vote
0answers
55 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
167 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
289 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
125 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
98 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
175 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
248 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
83 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
396 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
63 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
192 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

Boolean algebra and boolean subalgebra

I have to prove that set of all dividers of number 210 with appropriate operations forms a Boolean algebra. And describe these operations and create a Hasse diagram. In the secondd part I have to ...
0
votes
0answers
7 views

Converting a boolean expression into CNF and DNF

Is there any systematic way to convert the following boolean expression (QUBO) into CNF or DNF? Here, $x_1, \ldots, x_n \in \{0, 1\}$, $a_1, \ldots, a_n \in \mathbb{Z}$ and $b_{1,1}, \ldots, b_{n,n} ...
0
votes
0answers
19 views

What is the following boolean equation: ΣM(1,2,4,7)?

I am supposed to find the minimum-cost SoP form of that equation Σm(1, 2, 4, 7) for a homework question. However, this is extremely unclear to me. As I understand it this is the summation of the ...
0
votes
0answers
15 views

Are epimorphisms (defined via an obvious action) of free Boolean algebras whose set of generators is a group automorphisms?

Let $G$ be a group. Consider $B$, the free Boolean algebra with generating set (I'll call them "variables") $G$. Let $F$ be some formula (that is, some fixed element of $B$). Define an endomorphism ...
0
votes
0answers
13 views

Number of elements in a Boolean algebra

Consider a set $X$ consisting of $n$ elements Does the Boolean algebra of all subsets of $X$ (i.e. the power set of $X$) have $2^n$ or $2^{2^n}$ elements? I came across both answers, which confuses ...
0
votes
0answers
21 views

How to prove that $abd = abcd + abc'd$ for all general occassions

It is true for example that $abd = abcd + abc'd$. Each of the terms on the right part of the equation contains all the used letters. Is there anyway to prove that any term is equal to the sum of the ...
0
votes
0answers
14 views

Simplify the Boolean functions using K-Map

I was able to derive these boolean expressions correctly from a circuit diagram. (Professor put answers up to compare) She now wants us to use a K-Map to simplify these functions. This where I am ...
0
votes
0answers
22 views

Defining an example of a Boolean algebra (Discrete Math)

This question is listed in my textbook: Give an example of a Boolean algebra B and elements $x$, $y$, $z$ in $B$ such that $x + z = y + z$, but $x \neq y$. Now, I believe this means I have to ...
0
votes
0answers
12 views

Help with boolean algebra simplification

How can I simplify this using Boolean algebra: wx'z+xy'z I was thinking of distributing the z so it would be z(wx'+xy') but what should I do next? Help will be greatly appreciated.
0
votes
0answers
11 views

Boolean Algebra simplification

How can I simplify this expression? given: wx'z+y'z'+xz'+xy'z my work: z(wx'+xy')+y'z'+xz'is this step correct? How can I simplify further, maybe to three terms?
0
votes
0answers
23 views

How do you simplify this boolean expression?

Original expression : $$J = ((A′ + B)′ + C′)′ + DC′ + AB′ $$ Here is what I did but the correct answer is $AB' + C + D$. $$J = ((AB') + C')' + DC' + AB'\\ J = ((AB')'C) + DC' + AB' \\ J = ((A' + ...