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..
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.
I need an algorithm that finds the possible states of
variables used in "ifs"
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.
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.
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 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 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
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.
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..
Sysop: | Tetrazocine |
---|---|
Location: | Melbourne, VIC, Australia |
Users: | 7 |
Nodes: | 8 (0 / 8) |
Uptime: | 120:59:48 |
Calls: | 46 |
Files: | 21,492 |
Messages: | 64,790 |