# Tag Info

### Relationship between size of Boolean functions and DFAs

Complementing the other answers, here are a few research papers that explicitly study the size of (one-way) DFAs that represent Boolean functions in the way the OP describes. Maximum and average state ...
• 6,545

### Relationship between size of Boolean functions and DFAs

Regarding question 3: There are $S^{2S} \cdot 2^S$ different DFAs on $S$ states (fixing the initial state), and so most Boolean functions require $\Omega(2^n/n)$ states. This is the same calculation ...
• 14.5k

### Relationship between size of Boolean functions and DFAs

Here are are my attempts to answer. I'm not an expert on this subject. Please check all details for yourself. No. Consider $f$ defined by $f(x)=1$ iff $x_1 \ne x_{n/2+1}$ or $x_2 \ne x_{n/2+2}$ or ...
• 12.2k
Accepted

### Is there a generalized SAT problem for higher-order logics?

Yes, you may be interested in the paper "Higher-Order Quantified Boolean Satisfiability" by Chistikov, Haase, Hadizadeh, and Mansutti (https://doi.org/10.4230/LIPIcs.MFCS.2022.33)
• 1,337
Accepted

### Power of non-implicationally-complete Frege systems and Boolean equational calculus

$\let\eq\leftrightarrow\def\ru{\mathrel/}\let\ET\bigwedge$Frege systems are required to be implicationally complete to make all such systems p-equivalent, yielding a robust definition of the Frege ...
• 17.9k
1 vote
Accepted

### Solve 3CNF in Poly-Time with Satisfiability Oracle

hint: assign values to variables one at a time and call algorithm A on resulting formula. if the result of algorithm A is satisfiable or non-satisfiable what does that mean about last variable ...
• 26

Only top scored, non community-wiki answers of a minimum length are eligible