7
$\begingroup$

I'm trying to find a way to compute the set of inputs that lead to a specific output given an expression.

For example, if you take the expression :

!A && B && C == 1

and you want this expression to be true, then some possible inputs are :

A = false, B = "foo", C = 1

A = 0, B = true, C = 1

...

What is the name of the general theory around this if any?

Improve this question
New contributor
Exifers is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
3
  • 1
    $\begingroup$ Are you looking for boolean expression specifically, or arbitrary programs in general? $\endgroup$
    – Bergi
    Commented yesterday
  • $\begingroup$ Dijkstra's weakest precondition. $\endgroup$
    – philipxy
    Commented yesterday
  • $\begingroup$ Not just booleans, general expressions that could involve lists, sets, dictionaries, etc.. $\endgroup$
    – Exifers
    Commented yesterday

2 Answers 2

Reset to default
18
$\begingroup$

Finding all (or any) inputs that make a logical expression true is exactly the realm of satisfiability problems:

Boolean SAT – variables are just 0/1.

SMT (Satisfiability Modulo Theories) – variables can be integers, bit-vectors, strings, arrays, etc.

CSP (Constraint Satisfaction Problem) – the most general umbrella, popular in AI/OR.

As a sidenote it is not the same as reversible computing

Improve this answer
$\endgroup$
3
0
$\begingroup$

Since it got a mention in comments: there is also a notion of Weakest Preconditions which determine what must be true about a program before a single step (pre-condition) to satisfy a predicate after the step (post-condition). They are especially useful in certain kinds of proofs and often feel like backwards reasoning.

See the Logical Foundations texts (Vols. 1 & 2 if memory serves) for a mechanized introduction in Coq.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.