Questions tagged [boolean-algebra]
The boolean-algebra tag has no summary.
291 questions
0
votes
0
answers
47
views
Can the constants of FNV1A be computed for a specific set of strings to make it a perfect hash function?
I am hashing a bunch of strings made up of a finite number of known keyword strings (n many keyword strings). Here I want to generate a perfect hash s.t. each ...
- 187
0
votes
1
answer
81
views
3-CNF to 2-CNF reduction
I want to start by saying that I've struggled to find any satisfying answer to this question of mine. I did read this question, but it's slightly different.
My idea is simply that every 3-cnf formula ...
- 101
1
vote
0
answers
59
views
Transforming a set of fundamental cycles of non-weighted undirected graph into simplest basic cycles using XOR
How to transform a set of fundamental cycles of non-weighted undirected graph into minimum basic cycles using XOR?
Definitions:
Fundamental cycle include in fundamental cycle basis, that can be formed ...
- 111
3
votes
0
answers
127
views
Trilinear sum of characters in $\mathbb{Z}_2^n$
This is my first time asking a question on this site, as I believe my question is probably related to computer science (and possibly to the analysis of Boolean functions), and someone here might be ...
- 131
0
votes
0
answers
61
views
Are the proposed truth tables for the rules correct?
I'm trying to propose truth tables for the following two rules which are originally defined on page 5 in this paper:
Title: An abstract framework for argumentation with structured arguments
Author: ...
- 101
2
votes
0
answers
103
views
A confusion about Karnaugh Map
Consider the following four variable Boolean function:
$$F(A,B,C,D)=\sum(0,2,3,5,7,8,9,10,11,13,15)$$
If I show you the map, then what I get is:
I have marked the Essential Prime Implicants with a ...
- 71
1
vote
0
answers
55
views
Pairwise (partial) equivalence of boolean functions [closed]
I have a bunch of boolean functions, say $b_1,b_2,\dots,b_k \colon \{0,1\}^m \to \{0,1\}^n$, all given in terms of circuits.
I want to determine for which inputs they pairwise agree, that is, I want ...
- 11
0
votes
0
answers
34
views
Boolean functions on the hypercube and sensitivity conjecture
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: \{...
- 123
1
vote
0
answers
86
views
Data structure for tracking boolean clauses size
Given an unordered sequence of n boolean conjonction clauses which may contain duplicates, I am looking for a data structure that would track the number of clauses grouped by the number of variables ...
- 11
2
votes
1
answer
72
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 ...
1
vote
2
answers
136
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 (...
- 165
-2
votes
2
answers
241
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)\ +\ ...
3
votes
1
answer
466
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
88
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 $\...
- 2,131
2
votes
0
answers
143
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:
...
- 233