Questions tagged [boolean]
For questions related to Boolean function (whose arguments and result assume values from a two-element set).
89 questions
1
vote
0
answers
48
views
What is the maximum size of a basis for the class T₁ (1-preserving Boolean functions)?
I was able to figure out the maximum basis size for the classes L (Linear) and M (Monotonic), but I'm having trouble with the class T₁ (1-preserving).
The problem can't be solved using the five basic ...
- 511
9
votes
2
answers
352
views
Are all monotone Boolean functions weighted threshold functions?
$\DeclareMathOperator{\th}{th}$
A Boolean function $f:\{0,1\}^n \to \{0,1\}$ is monotone if for all $a_1,\dots,a_n,a'_1,\dots,a'_n$, if $a_i \leq a'_i$ for all $1 \leq i \leq n$ then $f(a_1,\dots,a_n) ...
- 5,547
2
votes
0
answers
94
views
Is there a Turing complete cellular automaton buidable from XOR and 1?
I recently learned in my last question that rule 110, while being Turing-complete, can be built from a set of falsity-preserving functions (such as $\{\lor, \oplus\}$) which isn't functionally ...
1
vote
1
answer
81
views
Simulating rule 110 with OR and XOR gates.
I will start with a few definitions:
Let $X$ be a set, and let $i, n \in \mathbb{N}^*$ such that $i \leq n$. The $i$-th $n$-ary projection is defined as:
$$\pi_i^n : X^n \rightarrow X$$
$$x_1, \dots, ...
-3
votes
1
answer
115
views
Number of subsets with even-sized intersections equals the number of subsets with odd-sized intersections [duplicate]
This seems like a simple question , but I cant seem to figure it out. Let $I\subseteq [n]$ be a fixed subset. As we run through subsets $A\subseteq [n] $, exactly half of $A\cap I$ will be even sized.
...
- 807
1
vote
1
answer
97
views
Prove that formulas in $\{\land,\lor,0,1\}$ represents exactly the monotonic boolean functions
The Problem from Rautenberg's A Concise Introduction to Mathematical
Logic:
Show that the formulas in $\land,\lor,0,1$ represents exactly the
monotonic Boolean functions. These are the constants from ...
- 695
0
votes
1
answer
85
views
Prove that each formula $\alpha$ in signature $\{\neg, +\}$ represents a linear Boolean function
$f\in\boldsymbol{B}_n$ is called linear if
$f(x_1,\ldots,x_n)=a_0+a_1x_1+\cdots+a_nx_n$ for suitable coefficients
$a_0, \ldots , a_n\in \{ 0, 1\}.$ Here + denotes exclusive disjunction
(addition ...
- 695
1
vote
1
answer
102
views
Does Gauss-Jordan elimination have any application in boolean logic?
I'm in the very early stages of learning Linear Algebra. Having studied boolean algebra in the past, I couldn't help but notice a striking similarity between the two. Boolean sum of products appear to ...
- 149
2
votes
0
answers
52
views
construct the circuit which checks whether the $j$-th bit of the sum of given binary numbers $k$ and $m$ is 1
A boolean circuit C has n inputs and m outputs, and is constructed with AND, OR, and NOT gates. Each gate has fan-in 2 except the NOT gate which has fan-in 1. The out-degree can be any number. A ...
- 131
0
votes
1
answer
87
views
Small detail in Thomas Jech proof of Lemma 7.12
Competition of Boolean algebra is unique up to isomorphism.
Proof: Let $C, D$ be two completions of Boolean algebra $B$. Then, we want to show that $C \cong D$. There's this reference which I find ...
- 664
1
vote
0
answers
44
views
An example of 6-function basis in 3-value logic?
In 1973 L. Krnic proved that there is at-most-6-element basis in 3-value logic {0, 1, 2}, following Jablonskii's proof that there are 18 pre-complete classes in this logic with 27 different types of ...
- 11
0
votes
1
answer
150
views
How do you make a K-Map when you're missing a few variables?
I've got the following problem -
That's got the following solution:
And I don't understand how this K-Map was made. Every exercise I've encountered thus far always has equations that have 3 elements(...
- 125
0
votes
1
answer
77
views
Why does the mechanical work of getting the conjunctive normal form and disjunctive normal form work?
I'm having a hard time understanding why/how does these processes really work.
All I know is how to get the original expression from the truth table, using the step-by-step work I've been taught, but ...
1
vote
1
answer
120
views
Boolean functions on the hypercube
I'm reading this paper which relates the sensitivity conjecture to a graph-theoretic question on the hypercube and I'm struggling to understand some things. A Boolean function here is defined as $f: \{...
- 885
1
vote
1
answer
89
views
Is there a finite upper bound for the minimal number of generators of a Boolean clone?
A Boolean clone is a clone (in the sense of universal algebra) on the set $\{0,1\}$. Post proved that every Boolean clone is finitely generated. I want to know if a stronger version of Post's theorem ...
- 24.8k