1
$\begingroup$

Suppose I have a statement made of many propositions.

$\left(a \rightarrow b\right) \wedge \left(c \oplus d\right) \vee \left(e\wedge f\right) \dots$

composed of the standard 16 binary operators. Is there a way to know how many truths there will be in the truth table? That doesn't involve putting all combinations of 1 and 0 in to evaluate them?

Thanks in advance for any help.

$\endgroup$
2
$\begingroup$

This problem is intractable and #P-complete.

$\endgroup$
  • $\begingroup$ What do you mean by intractable? I have created a method that solves this problem. I'm not sure if it has been done before though? $\endgroup$ – Ben Crossley Jun 28 at 22:00
  • 1
    $\begingroup$ @BenCrossley "Intractable" means that any algorithm that attempts to solve the problem will take "more than polynomially longer as a function of problem size" in finding the solution. Generally, exponentially longer. Here, the problem size is given by the number of variables. Your method may work for 20 variables, but once it's 200 variables, you will wait forevermore for the algorithm to finish. More specifically, going through 2^20 possibilites vs going through 2^200 possibilities. This is somewhat weakly related to "P=NP" (of course NP will never be P, that would be sheer magic) $\endgroup$ – David Tonhofer Jun 29 at 7:39
  • 1
    $\begingroup$ @BenCrossley Well, yes. There is no better way (in general) to find "the number of times a given proposition resolves to true" than to use the brute-force method of going through all possible inputs and evaluating. So, for an expression in x,y,z you have to check 000,001,010,011,100,101,110,111 ... 2^3 evaluations. For an expression with hundreds (or millions, not unheard of) variables you have 2^100 tests to make, you will not be able to count the number of solutions. The universe won't last long enough to go through the table. $\endgroup$ – David Tonhofer Jun 29 at 10:46
  • 1
    $\begingroup$ @BenCrossley On the other hand, for some specific formulas, you may be able to throw away large areas of the table to search immediately by a little forethought, for example if your formula is "x & some-expression-in-x,y,z", you immediately know that x must be 1. $\endgroup$ – David Tonhofer Jun 29 at 10:47
  • 1
    $\begingroup$ @BenCrossley Uh-hu. Don't get your hopes up on having cracked a known hard problem though. They are known hard for a good reason. Check out SAT solving for related fun. $\endgroup$ – David Tonhofer Jun 29 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.