I need an algorithm that finds the possible states of variables used in
"ifs"

for instance, I need to find out possible states:

if (a && b){

// 'a' is true
// 'b' is true

}
else
{ // 'a' maybe be true or false
// 'b' maybe be true or false
}

More complex:

if (a && b || c){
// 'a' maybe be true or false
// 'b' maybe be true or false
// 'c' maybe be true or false
} else
{ // 'a' maybe be true or false
// 'b' maybe be true or false
// 'c' maybe be true or false
}

I think this algorithm may already exists.. but not finding it.
Maybe something related with predicates.

Thiago Adams <thiago.adams@gmail.com> writes:
>I need an algorithm that finds the possible states of variables used in
>"ifs"
>
>for instance, I need to find out possible states:
>
>if (a && b){
>
> // 'a' is true
> // 'b' is true
>
>}
>else
>{
> // 'a' maybe be true or false
> // 'b' maybe be true or false
>}
>

Create truth tables. Optionally use deMorgans
laws to simplify.

https://en.wikipedia.org/wiki/Boolean_algebra
https://en.wikipedia.org/wiki/De_Morgan%27s_laws

Em 4/2/2024 6:23 PM, Scott Lurndal escreveu:
> Thiago Adams <thiago.adams@gmail.com> writes:
>> I need an algorithm that finds the possible states of variables used in
>> "ifs"
>>
>> for instance, I need to find out possible states:
>>
>> if (a && b){
>>
>> // 'a' is true
>> // 'b' is true
>>
>> }
>> else
>> {
>> // 'a' maybe be true or false
>> // 'b' maybe be true or false
>> }
>>
>
> Create truth tables. Optionally use deMorgans
> laws to simplify.
>
> https://en.wikipedia.org/wiki/Boolean_algebra
> https://en.wikipedia.org/wiki/De_Morgan%27s_laws
>

This truth table is kind of "brutal force" isn't it?
But this gave me an idea.

I can make a expression tree.

Visiting the tree I will find a variable that I don't know if it is true
or false.
Then I continue the evaluation considering this variable is true.
Then I continue the evaluation (from the point we did a branch)
considering it is false.
At the end of evaluation I have the final result of the expression true
and false I can merge all possible combinations for true and false.
I will try..

Thiago Adams ha scritto:
> Em 4/2/2024 6:23 PM, Scott Lurndal escreveu:
>> Thiago Adams <thiago.adams@gmail.com> writes:
>>> I need an algorithm that finds the possible states of variables used in
>>> "ifs"
>>>
>>> for instance, I need to find out possible states:
>>>
>>> if (a && b){
>>>
>>>    // 'a' is true
>>>    // 'b' is true
>>>
>>> }
>>> else
>>> {
>>>    // 'a' maybe be true or false
>>>    // 'b' maybe be true or false
>>> }
>>>
>>
>> Create truth tables. Optionally use deMorgans
>> laws to simplify.
>>
>> https://en.wikipedia.org/wiki/Boolean_algebra
>> https://en.wikipedia.org/wiki/De_Morgan%27s_laws
>>
>
>
> This truth table is kind of "brutal force" isn't it?
> But this gave me an idea.
>
> I can make a expression tree.
>
> Visiting the tree I will find a variable that I don't know if it is true
> or false.
> Then I continue the evaluation considering this variable is true.
> Then I continue the evaluation (from the point we did a branch)
> considering it is false.
> At the end of evaluation I have the final result of the expression true
> and false I can merge all possible combinations for true and false.
> I will try..
>

.... or you could create a two-dimensional lookup-table or an algorithm
that represents a Karnaugh map. You can find some "Karnaugh map solver"
on the web.

On 02.04.2024 22:53, Thiago Adams wrote:
> I need an algorithm that finds the possible states of variables used in
> "ifs"
>
> for instance, I need to find out possible states:
>
> [examples snipped]
>
> I think this algorithm may already exists.. but not finding it.
> Maybe something related with predicates.

Are you maybe looking for SAT solvers[*]?

There's also free software available, but I don't recall its name.

Janis

[*] https://logic4free.informatik.uni-kiel.de/llocs/SAT_solvers

Thiago Adams:

> I need an algorithm that finds the possible states of
> variables used in "ifs"

The industrial approach (e.g. from digital circuitry) is to
convert the expression into a minimal sum of truth
constituents. There are several algorithms to do so
efficiently, i.e. to find the minimal coverage of the truth
table by truth constituents. The only ones I know are by a
Russian author published in a Russian book by logic, so I
cannot provide a useful reference.

A family of appraches is based on the Karnaugh map:

https://en.wikipedia.org/wiki/Karnaugh_map

If you expressions are simple, however, a direct enumaration
of 2^n combinations could work.

--
() ascii ribbon campaign -- against html e-mail
/\ www.asciiribbon.org -- against proprietary attachments

Here is the algorithm I did. Kind of brute-force algorithm.

It requires two phases.

At phase 1 we collect the variables used by the expression.

This phase is not implemented here, but the result of this phase is
represented by.

struct var vars[] = { {"a"}, {"b"} , {"c"} };

The expression can be configured at

bool expression(struct var vars[], int l);

The expression used in this sample is

a && b || c

So what we have is

if (a && b || c)
{ //what are the possible values of a, b and c?
} else
{ //what are the possible values of a, b and c?
}

The phase two generates all possible combinations evaluating the expression.
if the result the expression is true, we store the possible states of
true_branch, otherwise se store the possible states of else branch.

---code --

#include <stdio.h>
#include <stdbool.h>

enum E
{ TRUE_FLAG = 1 << 0,
FALSE_FLAG = 1 << 1
};

struct var
{ const char * name; //name of the variable
bool value; //value

enum E true_branch; //possible values at true branch
enum E false_branch; //possible values at else branch
};

//List of variables used by expression
struct var vars[] = { {"a"}, {"b"} , {"c"} };

bool expression(struct var vars[], int l)
{ l;

//a && b
// return vars[0].value && vars[1].value;

//a && b || c
return vars[0].value && vars[1].value || vars[2].value;
}

void visit(int k, struct var vars[], int l)
{ if (k == l)
{
for (int i = 0; i < l; i++)
{
if (i > 0) printf(",");
printf("%s:%s", vars[i].name, (vars[i].value ? "T" : "F"));
}

bool r = expression(vars, l);
printf(" = %s\n", r ? "T" : "F");

for (int i = 0; i < l; i++)
{
if (r)
{
vars[i].true_branch |= (vars[i].value ? TRUE_FLAG :
FALSE_FLAG);
}
else
{
vars[i].false_branch |= (vars[i].value ? TRUE_FLAG :
FALSE_FLAG);
}
}

return;
}

vars[k].value = true;
visit(k + 1, vars, l);
vars[k].value = false;
visit(k + 1, vars, l);
}

int main()
{ int l = (sizeof(vars) / sizeof(vars[0]));
visit(0, vars, l);

printf("\nAt true branch..\n");
for (int i = 0; i < l; i++)
{
printf("%s can be : %s %s\n",
vars[i].name,
(vars[i].true_branch & TRUE_FLAG) ? " T" : "",
(vars[i].true_branch & FALSE_FLAG) ? " F" : "");
}

printf("\nAt else branch..\n");
for (int i = 0; i < l; i++)
{
printf("%s can be : %s %s\n",
vars[i].name,
(vars[i].false_branch & TRUE_FLAG) ? " T" : "",
(vars[i].false_branch & FALSE_FLAG) ? " F" : "");
}
}

https://godbolt.org/z/eEhY7rPsz

On 03/04/2024 08:33, Anton Shepelev wrote:
> Thiago Adams:
>
>> I need an algorithm that finds the possible states of
>> variables used in "ifs"
>
> The industrial approach (e.g. from digital circuitry) is to
> convert the expression into a minimal sum of truth
> constituents. There are several algorithms to do so
> efficiently, i.e. to find the minimal coverage of the truth
> table by truth constituents. The only ones I know are by a
> Russian author published in a Russian book by logic, so I
> cannot provide a useful reference.
>
> A family of appraches is based on the Karnaugh map:
>
> https://en.wikipedia.org/wiki/Karnaugh_map
>
> If you expressions are simple, however, a direct enumaration
> of 2^n combinations could work.
>

I think the number of variables will be small.

if (a) ...
if (a && b) ...
if (a || b) etc..

But even if I have let's say 10 variables, then 2^10 = 1024 still
something fast to do.

On 03/04/2024 08:33, Anton Shepelev wrote:
> Thiago Adams:
>
>> I need an algorithm that finds the possible states of
>> variables used in "ifs"
>
> The industrial approach (e.g. from digital circuitry) is to
> convert the expression into a minimal sum of truth
> constituents. There are several algorithms to do so
> efficiently, i.e. to find the minimal coverage of the truth
> table by truth constituents. The only ones I know are by a
> Russian author published in a Russian book by logic, so I
> cannot provide a useful reference.
>
> A family of appraches is based on the Karnaugh map:
>
> https://en.wikipedia.org/wiki/Karnaugh_map
>
> If you expressions are simple, however, a direct enumaration
> of 2^n combinations could work.
>

I think the number of variables will be small.

if (a) ...
if (a && b) ...
if (a || b) etc..

But even if I have let's say 10 variables, then 2^10 = 1024 still
something fast to do.

On 4/3/2024 8:33 AM, Thiago Adams wrote:
> On 03/04/2024 08:33, Anton Shepelev wrote:
>> Thiago Adams:
>>
>>> I need an algorithm that finds the possible states of
>>> variables used in "ifs"
>>
>> The industrial approach (e.g. from digital circuitry) is to
>> convert the expression into a minimal sum of truth
>> constituents.  There are several algorithms to do so
>> efficiently, i.e. to find the minimal coverage of the truth
>> table by truth constituents. The only ones I know are by a
>> Russian author published in a Russian book by logic, so I
>> cannot provide a useful reference.
>>
>> A family of appraches is based on the Karnaugh map:
>>
>>    https://en.wikipedia.org/wiki/Karnaugh_map
>>
>> If you expressions are simple, however, a direct enumaration
>> of 2^n combinations could work.
>>
>
> I think the number of variables will be small.
>
> if (a) ...
> if (a && b) ...
> if (a || b) etc..
>
> But even if I have let's say 10 variables, then 2^10 = 1024 still something fast to do.

I hope your problem is not as you describe it.

Performance will suck, when one of your customers (on purpose),
tests it with twenty variables, just so that individual can
file a bug report with your company :-) You know there are
people who do that sort of thing.

One of your posts suggested you were building a boolean expression
evaluator of some sort. For an unspecified purpose.

Logic manipulation is used for at least logic design,
and things like Quine McClusky helped minimize logic
gates in the jelly bean era. I was taught QM and Petrics
in uni, but no code was available to play with it, and
doing it by hand is, well, work.

One of the first things I did, when I got a job, is I got a
copy of QM from another engineer, and I ported it from C to Pascal
for the personal computer on my desk (which didn't have a C compiler).

https://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm

My preferred notation would be like this. ABC on the vertical,
DEF variables horizontal. DEF spanning 000,001, .. 111 . And
the vertical ABC values 000..111 being spelled out explicitly.
The purpose of using a notation like this, is fewer lines of input.
Any sort of rectangular array or square array, will do.
_
ABC|DEF A + ABCDEF ==> A + BCDEF
-----------------
000|0 0 0 0 0 0 0 0
001|0 0 0 0 0 0 0 0
010|0 0 0 0 0 0 0 0
011|0 0 0 0 0 0 0 1
100|1 1 1 1 1 1 1 1
101|1 1 1 1 1 1 1 1
110|1 1 1 1 1 1 1 1
111|1 1 1 1 1 1 1 1

Parity trees are not reducible, which is one of your test
cases when writing code. A parity tree has diagonals in it
as a pattern. Like a garden trellis made of wood.

*******

There is a sample QM here.

The way the program inputs data, determines how useful it is
for visualization. This program has an emphasis on symbolic
manipulation, but for I/O, you could not handle a very
big problem this way. For my table of a six variable function,
the data input is only eight lines or so. The EXE here would
be 64 inputs, and the counting sequence and position of MSB:LSB
when counting, is the reverse of what I would use. But it
doesn't really matter how you fill the table, before the code runs.
Naturally, the O() of the method sucks, and if you have an extreme
number of variables for this sort of thing, and your users expect
"real time" response, this will be too slow. For evaluating two
variables, the execution time is too small to measure. With maybe
a dozen variables, my poor desktop computer back then needed
fifteen minutes to do the job.

https://sourceforge.net/projects/mini-qmc/

https://sourceforge.net/projects/mini-qmc/files/

Name: quine_mc_cluskey_v0.2.zip
Size: 56368 bytes (55 KiB)
SHA256: 5A415B4012C53623A7351F7E1B55C3ED5D6EB72A35DF735D59886FAF6FDA13E7

*******
File: readme.txt

Sample
======

Here a simple sample for a NAND operator:

Enter number of variables: 2
Please enter desired results: ( 0 or 1)
_ _ __
yz = 0 yz| Input is: yz + yz + yz ----+
---- |
_ 11|0 |
yz = 1 01|1 |
10|1 +--- I added this section
_ 00|1 | for reference and
yz = 1 / \ | perspective
LSB MSB CountDown sequence |
__ (normally it would be MSB:LSB and count up) |
yz = 1 ----+

Result:

_ _
y + z

*******

What you're doing in your ELSE clause is: Input is: yz

yz = 1

_
yz = 0

_
yz = 0

__
yz = 0

And the output would be yz.

But at least you can see there might be a pattern there.

I tested the program with an XOR pattern for input, and
it does not print out a logic equation with an XOR as
a compact notation.

For a practical QM program then, the I/O, the material
for visualization, for seeing what was done, that is just
as important as the grinding process.

Notice in the Wikipedia article, one of the problems has
two output solutions. You pick the solution with a "shared term"
you just happens to be generated elsewhere in the circuit :-)
A circuit design can have many logic trees, and some of
the trees may intersect and be reduced by the sharing you
discover.

Of course humans don't do this any more. Logic is defined
in Verilog and VHDL files, CAD tools do the minimization,
find the shared term, floor plan, use simulated annealing
for the layout, pour logic gates into a rectangular space
using a serpentine shaped pattern. And it's all done
while you drink coffee and look out the window.

But the hard work, is algorithm definition, and the test benches
for boundary conditions are the "tax" you pay for being so clever.

Paul

Thiago Adams ha scritto:
> I need an algorithm that finds the possible states of variables used in
> "ifs"
>
> for instance, I need to find out possible states:
>
> if (a && b){
>
>   // 'a' is true
>   // 'b' is true
>
> }
> else
> {
>   // 'a' maybe be true or false
>   // 'b' maybe be true or false
> }
>
> More complex:
>
> if (a && b || c){
>   // 'a' maybe be true or false
>   // 'b' maybe be true or false
>   // 'c' maybe be true or false
> }
> else
> {
>   // 'a' maybe be true or false
>   // 'b' maybe be true or false
>   // 'c' maybe be true or false
> }
>
> I think this algorithm may already exists.. but not finding it.
> Maybe something related with predicates.
>
>

I'm not sure I understand exactly what you want to obtain,
but if I understand I can propose, to you, a simple idea:

#include <stdio.h>

int main()
{ #define SFMT "a:%-5.5s b: %-5.5s c: %-5.5s\n"
#define BIT(v, t) (v & t)
#define TST(v) ((v) ? "true" : "false")

unsigned char a = 1 << 0,
b = 1 << 1,
c = 1 << 2;

for(unsigned char i = 0; i <= 7; i++)
{
if(BIT(i, a) && BIT(i, b) || BIT(i, c))
{
printf("Then: " SFMT, TST(BIT(i, a)),
TST(BIT(i, b)),
TST(BIT(i, c)));
}
else
{
printf("Else: " SFMT, TST(BIT(i, a)),
TST(BIT(i, b)),
TST(BIT(i, c)));
}
}
return 0;
}

output:
Else: a:false b: false c: false
Else: a:true b: false c: false
Else: a:false b: true c: false
Then: a:true b: true c: false
Then: a:false b: false c: true
Then: a:true b: false c: true
Then: a:false b: true c: true
Then: a:true b: true c: true

On 04/04/2024 13:06, jak wrote:
> Thiago Adams ha scritto:
>> I need an algorithm that finds the possible states of variables used
>> in "ifs"
>>
>> for instance, I need to find out possible states:
>>
>> if (a && b){
>>
>>    // 'a' is true
>>    // 'b' is true
>>
>> }
>> else
>> {
>>    // 'a' maybe be true or false
>>    // 'b' maybe be true or false
>> }
>>
>> More complex:
>>
>> if (a && b || c){
>>    // 'a' maybe be true or false
>>    // 'b' maybe be true or false
>>    // 'c' maybe be true or false
>> }
>> else
>> {
>>    // 'a' maybe be true or false
>>    // 'b' maybe be true or false
>>    // 'c' maybe be true or false
>> }
>>
>> I think this algorithm may already exists.. but not finding it.
>> Maybe something related with predicates.
>>
>>
>
> I'm not sure I understand exactly what you want to obtain,
> but if I understand I can propose, to you, a simple idea:
>
> #include <stdio.h>
>
> int main()
> {
>     #define SFMT "a:%-5.5s b: %-5.5s c: %-5.5s\n"
>     #define BIT(v, t) (v & t)
>     #define TST(v) ((v) ? "true" : "false")
>
>     unsigned char a = 1 << 0,
>                   b = 1 << 1,
>                   c = 1 << 2;
>
>     for(unsigned char i = 0; i <= 7; i++)
>     {
>         if(BIT(i, a) && BIT(i, b) || BIT(i, c))
>         {
>             printf("Then: " SFMT, TST(BIT(i, a)),
>                                   TST(BIT(i, b)),
>                                   TST(BIT(i, c)));
>         }
>         else
>         {
>             printf("Else: " SFMT, TST(BIT(i, a)),
>                                   TST(BIT(i, b)),
>                                   TST(BIT(i, c)));
>         }
>     }
>     return 0;
> }
>
>
>
> output:
> Else: a:false b: false c: false
> Else: a:true  b: false c: false
> Else: a:false b: true  c: false
> Then: a:true  b: true  c: false
> Then: a:false b: false c: true
> Then: a:true  b: false c: true
> Then: a:false b: true  c: true
> Then: a:true  b: true  c: true
>
the algorithm is be used in flow analysis of C code.
I realized my previous approach will not work because I also need
intermediate result.

for instance

if (p && p->i) {}

I need to know p is not-null after && , I cannot wait until the end of
expression. The algorithm must propagate the results.
I am thinking on alternatives..

Paul:

> Logic manipulation is used for at least logic design, and
> things like Quine McClusky helped minimize logic gates in
> the jelly bean era. I was taught QM and Petrics in uni,
> but no code was available to play with it, and doing it by
> hand is, well, work.

Not where I work as a programmer. We use several large
commericial enterprise systems for business-process
organisation, and are implementors of yet another enterprise
system for ERP. I routinely meet with bugs and design flaws
in all those systems that interfere with my everyday work
and submit those bugs to the support of those products. Most
of the time they decide not to fix anything.

They have neither pride not other incentive to fix bugs
reported by a programmer from a client, because not fixing
it will have no negative consequences. SAP is one such
company. Announcing new features (however buggy) in a PR
pamphlet generates more revenue than having a reliable
product with a good API.

This seems the generally accepted approach by the developers
corporate commercial software, SAP being one of them.

--
() ascii ribbon campaign -- against html e-mail
/\ www.asciiribbon.org -- against proprietary attachments

Thiago Adams:

> the algorithm is be used in flow analysis of C code. I
> realized my previous approach will not work because I also
> need intermediate result.
>
> for instance
>
> if (p && p->i) {}
>
> I need to know p is not-null after && , I cannot wait
> until the end of expression. The algorithm must propagate
> the results. I am thinking on alternatives..

Then your original idea of analysing the expression tree is
good: the algorithm will be linear for conjunction and
negation, but will branch over disjunction. The short-
circuit evaluation may be accounted for by, eg., stroring
the known invariants with each node. For (a || b) you will
have:

OR
a
b [a is false]

yielding two branches: 1) a and 2) !a && b .

I do believe that waiting for the end of the expression
involves the chronology encoded in the expression tree.

--
() ascii ribbon campaign -- against html e-mail
/\ www.asciiribbon.org -- against proprietary attachments