Questions tagged [boolean-algebra]
The boolean-algebra tag has no usage guidance.
282
questions
4
votes
1
answer
261
views
Simple example of exponential gap between monotone and non-monotone circuits
Is there a simple example of a monotone Boolean function $f:\{0,1\}^m \to \{0,1\}$ that we know can be computed by a polynomial-size circuit, but cannot be computed by any polynomial-size monotone ...
- 231
2
votes
1
answer
138
views
Is such variant of SAT always satisfiable?
Let we have a SAT instance where every clause has length $\ge3$ (when length $2$ is allowed, it can be unsatisfiable) and each pair of literals appear only once.
Non-example: $(x\lor y\lor z)\land(x\...
CommunityBot
- 1
2
votes
1
answer
29
views
Are all solutions to a HORN-SAT problem required to contain the minimal model as a subset?
I'm studying HORN-SAT problems and I have a specific question about the minimal model.
Given a HORN-SAT problem with multiple solutions, I understand that the minimal model is the one with the ...
D.W.♦
- 164k
9
votes
1
answer
214
views
Boolean formula that agrees with most truth assignments
Let $X_1,\dots,X_n$ be $n$ boolean variables. I have an unknown predicate $P(X_1,\dots,X_n)$ on these boolean variables. Of course, I can view the predicate as a function $f_P : \{0,1\}^n \to \{0,1\}...
- 278k
0
votes
1
answer
94
views
Prove that it is impossible to construct the toffoli gate using only CNOT gates
Show that it is not possible to construct the toffoli gate using only CNOT gates, given we are allowed to choose any number of ancilla bits.
My Attempt
The action of a toffoli gate can be defined as,
...
CommunityBot
- 1
3
votes
1
answer
99
views
Number of n-variable symmetric boolean functions that are linear
How many symmetric boolean functions exist that are linear?
Let $f$ be a $n$-variable boolean function. $f$ is said to be symmetric if it is unchanged by any permutation of its variables, i.e. for 2-...
D.W.♦
- 164k
1
vote
1
answer
154
views
Boolean Integer Linear Optimization/Programming
Trying to solve an ILP optimization problem with a number of potential boolean variables and then express constraints on these variables based on those boolean results.
Let's say I am doing 5 coin ...
CommunityBot
- 1
1
vote
2
answers
56
views
Is there a linear programming method that is polynomial in the number of variables, constraints and bitlength of numbers?
AFAIK, Interior Point method for solving a system of linear inequations is polynomial in the number of variables and constraints. Probably there are others. I don't need to optimize any function (...
- 1,661
-2
votes
2
answers
92
views
Building a XOR gate out of NOR gates
Can someone explain for me how to build a XOR gate using 5 NOR gates? The thing I'm looking for is a proof similar to this:
$A^B\ =\ (!A)B\ +\ A(!B)$
$=\ !!((!A)B)\ +\ !!(A(!B))$
$=\ !(!!A\ +\ !B)\ +\ ...
- 31.5k
3
votes
1
answer
411
views
What is special about a canonical representation of Boolean functions?
My textbook (Saurabh's Introduction to VLSI Design Flow) mentions while discussing formal verification that a representation of a Boolean function is said to be canonical if the following holds:
If a ...
- 133
3
votes
1
answer
38
views
Is boolean formula equivalence problem for 2-CNFs $\mathsf{coNP}$-hard?
The problem:
Given two boolean formulas in 2-CNF, decide if they are equivalent.
I know that the problem is $\mathsf{coNP}$-hard when at least one formula is in 3-CNF. However, the same proof of $\...
D.W.♦
- 164k
4
votes
2
answers
2k
views
Do Karnaugh maps yield the simplest solution possible?
I'm learning to use a Karnaugh map, but I'm not sure if I obtained the simplest expression possible. Have a look at this example:
Truth table (inputs are A B C; output is F):
...
- 203
5
votes
0
answers
166
views
Can minimal CNF contain clause longer than initial CNF?
Let $\Phi$ be a k-CNF and $\Phi_{min}$ be a minimal CNF (one that contains smallest amount of literal occurences) that is equal to $\Phi$.
Can $\Phi_{min}$ contain a clause of size $m > k$?
What I ...
- 1,966
2
votes
0
answers
75
views
Prove or disprove that the Quine-McCluskey method generates the circuit with the minimum inputs and minimum gates?
Recently, when I self-learnt Discrete Mathematics and Its Applications 8th by Kenneth Rosen, it says in 12.4 Minimization of Circuits which uses the Karnaugh Map or the Quine-McCluskey method:
...
- 203
0
votes
3
answers
64
views
Is there an algorithm to implement N-input-gates using smaller gates?
To borrow part of a description from a similar but distinct question: there exist 2^(2^N) different functions which accept N binary inputs and return a 1 bit output. For the purposes of my question I ...
0
votes
1
answer
63
views
what is the smallest 3-CNF possible that enforces the boolean expression: a = b + c?
What is the smallest 3-CNF system of equations possible that enforces the boolean expression: a = b + c for boolean variables a, b, c?
'Smallest' can be defined as: (1) Number of 3 CNF clauses. (2) ...
- 4,735
1
vote
0
answers
24
views
CNF Horn-renamability to 3-CNF Horn-renamability reduction?
A CNF formula is Horn-renamable if you can invert variables in such a way that each clause has at most one positive literal. There is an algorithm based on a reduction to 2-SAT given in Renaming a Set ...
- 1,966
0
votes
0
answers
39
views
Expressing Boolean Functions In Terms of Another Function
Given two boolean functions f1 and f2, are there any tools available that could be used to automate the process to represent f1 in terms of f2? I understand the process of this doing this by hand ...
6
votes
1
answer
714
views
Representing binary functions with a finite gate set without exponential blow-up?
It is pretty well taught that any binary function can be represented using CNF. But conversion to CNF can take an exponential number of gates. The truth table is exponentially sized relative to the ...
D.W.♦
- 164k
0
votes
2
answers
110
views
Polynomial representations of Boolean functions
The AND boolean function $AND(x)$ can be represented using the polynomial $P(x) = x_1x_2\cdots x_n$. I have a few questions:
Is there a similar polynomial for the PARITY boolean function?
Is there a ...
CommunityBot
- 1
7
votes
1
answer
880
views
Why do Karnaugh maps work?
The question is quite straightforward: Why do Karnaugh maps work? What was the reasoning that led Maurice Karnaugh to come up with these maps? At first glance, it doesn't seem a natural approach, ...
- 103
2
votes
0
answers
26
views
Equivalent-symmetric (E-symmetric) variables check for Boolean functions
In [1], it states that checking $f(..., x_i, ..., \bar{x}_j, ...) = f(..., \bar{x}_j, ..., x_i, ...)$ (variables $x_i$ and $x_j$ are E-symmetric) is equivalent to checking $f_{x_ix_j} = f_{\bar{x}_i\...
- 21
1
vote
1
answer
294
views
Why is conjunctive normal form (CNF) "better" for SAT than disjunctive normal form (DNF)?
When hand-manipulating algebra DNF (sum of products) is easier than
CNF (product of sums). Possibly because factoring is more difficult
than expanding. So why is it the opposite for computational ...
CommunityBot
- 1
0
votes
0
answers
17
views
Complexity Class of the Problem: Existence of Unsatisfying Interpretations in Boolean Formulas
What is the complexity class of the problem if there exist two different interpretations that do not satisfy a given Boolean formula? I believe the problem of existence of an interpretation that does ...
- 1
1
vote
1
answer
45
views
Why do simple Logical Gates have an Irrational amount of Bits?
Suppose $2$ bits are used to encode a message, A and B.
If you know $A$ is $1$, you have one bit of information.
If you know $A\land B$ is $1$, you have two bits of information.
If you know $A\land B$...
CommunityBot
- 1
-3
votes
2
answers
64
views
!(ab)*(!a+b)(!b+b)=!a Boolean Algebra
How can I prove that !(ab)(!a+b)(!b+b)=!a* in boolean algebra? This is an exercise from a past paper of my teacher but I can't really find the way to the answer. I would appreciate some help.
0
votes
1
answer
108
views
How to solve boolean SAT with equality constraints
Say I have boolean formula in form of a CNF(x1,x2,...) with $x_i$ being boolean variables.
Testing the satisfiability of the CNF is the SAT problem, i.e. determine ...
- 161
5
votes
5
answers
1k
views
Prove HAKMEM Item 23: connection between arithmetic operations and bitwise operations on integers
Prove that for $A, B \in \mathbb{Z}$, $A + B = (A \operatorname{\&} B) + (A \mid B) = (A \oplus B) + 2(A \operatorname{\&} B)$ where $\&$ is bitwise AND, $|$ is bitwise OR and $\oplus$ is ...
CommunityBot
- 1
0
votes
0
answers
104
views
Is this a valid method to merge clauses in CNF formulas?
Assume $$C_1 = (x_1 \lor x_2 \lor \lnot x_3)\hspace{0.2cm} C_2 = (x_4 \lor x_5 \lor x_3) \hspace{0.2cm} C_3 = (x_3 \lor x_5 \lor x_6)$$ Let
$$ \phi_1 = C_1 \land C_2 \land C_3$$ and
$$ \phi_2 = (x_1 \...
- 185
20
votes
3
answers
6k
views
Is it possible to write an AND gate using XOR gates?
How could I express an AND gate using only XOR gates ?
0
votes
0
answers
28
views
Is this language PSPACE complete
Prove $PSPACE$-completeness of the language $READALLEXACT$ = $\{$$(M, x, 1^ s , t)$ | $A$ deterministic Turing machine $M$ on input $x$ reads all bits of the input in exactly $t$ steps and using no ...
- 3
0
votes
1
answer
22
views
influence of neighourhood points
Im trying to understand the following question. Suppose $h,f:\{-1,1\}^n\rightarrow \{-1,1\}$ satisfy $\sum_x h(x)f(x)\leq 0.5$, then one can rewrite this as $\textsf{Pr}_x [h(x)=f(x)]\leq 3/4$. Can we ...
CommunityBot
- 1
0
votes
2
answers
95
views
is duality principle in boolean algebra is true for every expression
Let say A = 1 and B = 1
and then A+B = 1
now by using duality(replacing or gate by and gate and 1 by 0) we can say that, A.B = 0
but this is not 0, because 1.1 = 1, so please anyone clear my ...
CommunityBot
- 1
0
votes
1
answer
55
views
7 segment decoder Combinational Logic Circuits using Logic Gates
How can a 7 segment decoder operation be implemented using boolean NOR gate ONLY?
Question:
Here's my truth table and k-map:
Normal circuit diagram:
CommunityBot
- 1
0
votes
2
answers
202
views
Two's complement using logic gates
How can a 4-bit two's complement operation be implemented using boolean NOR gate?
I search lots of 4-bit two's complement videos and articals, but most of them are using XOR gate.
CommunityBot
- 1
1
vote
2
answers
260
views
For a logic gate to be universal, must it necessarily be able to perform duplication?
It is said that a gate that can simulate AND and NOT is universal and able to recreate any classical circuit. I was looking at some of the circuits simulated by NAND, and for some of them, we need to ...
- 101
1
vote
0
answers
123
views
Method for simplifying complex logic tables
Not sure if this is the right StackExchange site, but back in college (20 years ago) I took a Digital Systems Design class where we learned how to reverse engineer a boolean function to meet the ...
- 111
0
votes
2
answers
149
views
Boolean Logic when one component switches from 0 to 1
I recently was constructing boolean logic for all sorts of examples from Morris Mano's "Digital Logic and Circuit Design".
I noticed that it is possible to construct a boolean logic wrt the ...
- 23.1k
0
votes
1
answer
123
views
Is there a notation for boolean algebra complexity?
To represent complexity of an algorithm, Computer Scientist is used to using big-O notation.
How about complexity of boolean algebra?
Boolean algebra is commonly used in digital circuit design with ...
2
votes
1
answer
1k
views
Why can't 3-SAT be solved efficiently if you convert all clauses (x ∨ y ∨ z) into (u ∨ z) by introducing a variable?
Let $a_i$, $b_i$, etc., be a literal, i.e., a variable or the negation of a variable.
3-SAT concerns formulas in CNF form: $(a_1 \vee a_2 \vee a_3) \wedge \dots \wedge (b_1 \vee b_2 \vee b_3)$ (3-CNF)....
- 39.1k
1
vote
1
answer
182
views
Sorting by boolean algebra (hardware) instead of algorithm (software)
Consider there's an 5 elements list that foreach element are 2-bits. Forexample [01,00,10,00,11], if the list is sorted, we hope the output like this [00,00,01,10,11]
Maybe that case seems complicated,...
CommunityBot
- 1
1
vote
2
answers
356
views
Combinational logic check if bits is prime
I wonder if there's Digital Logic Circuit (using combinatorial logic gates) that check if number is prime or not.
For example given input fixed 8-bit that will produce 1-bit output.
00000101 will ...
- 31.5k
0
votes
0
answers
120
views
Time complexity of negating a CNF formula
Suppose i have a CNF formula. If i negate the CNF formula, then i obtain DNF formula. However, i can't find anywhere on internet that mention the time complexity. What is the time complexity of ...
- 113
1
vote
1
answer
88
views
How many different boolean functions exist up to permutation of its $n$ variables
i am relatively new here, so if this was asked before, feel free to redirect me. I am searching for an answer in form of a (iterative or recursive) Formula or even better, an algorithm to list them ...
- 278k
1
vote
1
answer
65
views
Why do we use {+1, -1} in place of {0, 1} for the Fourier analysis of boolean functions?
I want to know what will change if we keep on using {0,1} for our Fourier analysis of boolean functions? What are the things, which can not be performed with {0,1} and can be done with {+1, -1}?
- 278k
1
vote
0
answers
38
views
Fourier Dimension of Boolean functions
I was recently reading about Fourier dimension of Boolean functions. What I understand is that if we take the Fourier expansion of $f: \{\pm1\}^n \to \{\pm1\}$ and consider the monomials with non zero ...
- 123
1
vote
2
answers
265
views
Clarification regarding linear boolean functions!
I am a little confused when it comes to linear boolean functions.
According to this post:
What is a simple way of explaining what a linear boolean function means in boolean algebra and relating it to ...
CommunityBot
- 1
1
vote
1
answer
74
views
Influence of a variable in composition of Boolean functions
Suppose $f$ and $g$ are Boolean functions without a constant term, and where every variable has the same influence. How to show every variable will have the same influence in $f \circ g$?
To me it ...
- 278k
1
vote
1
answer
24
views
How to come up with combination a short-circuit evaluation table?
(a || b) || (c && d))
Given the above, how do I derive the table below:
a
b
c
d
output
T
-
-
-
TRUE
F
T
-
-
TRUE
F
F
T
T
TRUE
F
F
T
F
FALSE
F
F
F
-
FALSE
I'm told that this is short ...
- 892
1
vote
2
answers
7k
views
How do i simplify this SOP expression?
Hi i have derived the following SoP (Sum of Products) expression , by analyzing the truth table of a 3 bit , binary to gray code converter. I ask for verification, because i feel as though this answer ...
- 1