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

10
votes
0answers
265 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
25 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
43 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
41 views

Is this a good enough proof?

Is this proof good enough? If not, any feedback would be appreciated. Thanks. Either exhibit $333 $ different boolean functions on the three variables $p; q; r,$ or prove that there aren’t $333$ ...
2
votes
0answers
85 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
72 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
54 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
98 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
215 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
34 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
10 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
35 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
21 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
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
39 views

Free Product VS Direct Product of Boolean algebras

Could someone give me the definitions of Free Product and Direct Product of Boolean algebra (possibly Boolean algebras that carries measures) I have seen some definition of free product which ...
1
vote
0answers
39 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
120 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
191 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
109 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
77 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
154 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
183 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
71 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
317 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
60 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
118 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
172 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
14 views

Boolean Algebras and Spaces

Show that a countably infinite free Boolean algebra $B$ has a Boolean space homeomorphic to $2^\omega$; where $2$ is the discrete space $\{0,1\}$; hence B is isomorphic to the Boolean algebra of ...
0
votes
0answers
27 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
16 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
14 views

Boolean Algebra Simplification help

Can anybody help me solve this Boolean algebra, Im a bit stuck on it and any assiastance would be great. Thanks A'B'C'D' + A'B'CD + A'BCD' + A B'C'D'
0
votes
0answers
10 views

How do Boolean-valued functions work?

Consider this function: P: X→ {true, false} There's nothing in that expression that says when X is true and when it is not true. How do these work?
0
votes
0answers
16 views

Proof by Induction… For any Boolean function F we can define its dual fd by?…

For any Boolean function $f$ we can define its dual $f^d$ by: $ f^d = ( x_{1}, x_{2},...,x_{n}) = \overline f(\bar x_{1}, \bar x_{2},...,\bar x_{n}) $ How do I prove this by induction?
0
votes
0answers
19 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
9 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
26 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
20 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 ...
0
votes
0answers
29 views

What am I doing wrong simplifying here?

Our professor asks us to simplify this question in our notes: = ABC+AB'[A'C']' This is what I did: ...
0
votes
0answers
8 views

Cardinality of a subalgebra of a boolean algebra

Let $X$ be a subset of a Boolean algebra $B$, and let ,$A$ be the subalgebra generated by $X$. Show that, if $X$ is finite, then $|A|$ $\leq$ $2^{2^{|X|}}$ , and that, if X is infinite, then |A| = ...
0
votes
0answers
15 views

A filterbase generating filter F

Show that a non empty subset $X$ of a filter $F$ in $B$ is a base for $F$ iff $X$ generates $F$ and for all $x,y$ $\in$ $X$ $\exists$ $z $ $\in$ $X$ such that $z$ $\leqq$ x $\wedge$ y.
0
votes
0answers
33 views

How to show that two (Boolean) algebras are NOT isomorphic?

Suppose that we have two algebras $A$ and $B$. To show such algebras are isomorphic, all we have to do is constructing a bijective homomorphism between them. Not for negative case, we should check all ...
0
votes
0answers
26 views

A set with a property in a Boolean lattice.

Are there a Boolean lattice $(X,\le)$, $A\subseteq X$ and $b\in X$, such that $\sup A$ exists but $\sup\{a\wedge b|a\in A\}$ does not exist.
0
votes
0answers
40 views

Zhegalkin polynomial Boolean algebra

I have to find the Zhegalkin polynomial of $ (x\rightarrow y)\rightarrow z $. Please tell me if this is right: my polynomial is of this kind $ a_{0} + a_{1}x + a_{2}y + a_{3}z + a_{4}xy + a_{5}yz + ...
0
votes
0answers
20 views

Dual functions in boolean algebra

Are all the properties satisfied by a Boolean function satisfied by its dual also(for example if a+b=c+d,then is ab=cd,this is just a simple demonstration, but it does it hold for even some complex ...
0
votes
0answers
41 views

Proving functional completeness

Assume given a Boolean Function $f(a,b,c)$ and you're asked if it's functional complete, this, as far as I know, means that by applying $\left \{ x,y,1,0\right \}$ to the function you can get $\left ...