This question is inspired by something which came today in TestAs, a compulsory exam for Indian students who wish to study in Germany:
Modelled by propositions which can be true or false, there are $n$ possible symptoms which a patient can have $p_1,p_2,...p_n$. For each permutation of truth value of these propositions, one disease from $X_1,X_2,X_3....X_{2^n}$ can be associated. Describe an algorithm to generate a flowchart with each proposition appearing at most once. If this is not possible, find an algorithm to generate a flowchart where the sum of the number of times each proposition appears is least.
Elaboration
To understand what how I mean a flowchart, refer to this example from the TestAs site:
The rhombus boxes can be thought of as checks whether a certain proposition is true or not. The truth value determines how you proceed in the diagram.
One constraint I'd like to keep on the problem is that each propositioncan only be used once. So, the above graph is unsuitable, since condition $F_2$ is used twice. The latest comments seem to suggest that the problem may not be solvable under this constraint though.
We assign prime number values to all the $p_n$ propositions.
$p_1$ = 2 if true, 4 if false
$p_2$ = 3 if true, 9 if false
.
.
.
$p_n$ = $n^{th}$ prime if true, $(n^{th} prime)^{2}$ if false
So, all combinations of truth values produce unique natural numbers (due to The Fundamental Theorem of Arithmetic) of the form:
$p_1$$p_2$...$p_n$ = A
As each $p_n$ can be true or false, there are $2^n$ many unique A's
We can order them from least to greatest.
$A_1$ < $A_2$ ... < $A_{m}$
Let $f_1$ be the proposition
$p_1$$p_2$...$p_n$ = $A_1$
If $f_1$ is true proceed to $X_1$
END
If $f_1$ is false, proceed to $f_2$
etc...
where $f_i$ is the proposition:
$p_1$$p_2$...$p_n$ = $A_i$