Clever Geek Handbook

Deduction Algorithm

Here's the problem.

If we have two statements p=>q

and q=>r

, this also means that p=>r

.

Given a set of statements, I need to find whether a given statement true

or false

or can not be concluded from these statements.

Example:
Formulated Statementsp=>q, p=>r, q=>s

  • if input p=>s

    i should get outputtrue

  • if input p=>t

    i should get outputCannot be concluded

  • if input p=> ~p

    i should get outputfalse

Here my question is the best data structure to implement it and the algorithm to use it.

Thank.

+3


source to share


3 answers


So, I still don't fully understand what you are trying to do. At the risk of being the voter, I'm going to kick it out there and see what people think.

I could start by plotting. Each object (p, q, etc.) has its own node. Implies means that you draw a line between two nodes. So any data input is just a question if a way can be found to intersect the graph - so in your example a => b, b => c, the graph has three nodes connected to b, b connected to c. The fact that a path exists between a and c means that a implies c.



I haven't tested this idea yet, but it seems like an interesting perspective. Particularly because graph theory is cool and many people are interested in it (i.e. Facebook Artists). And Python has good modules for analyzing graphs. (I believe the same is true for C ++. And you can always specify it manually using Gephi: https://gephi.org/ )

+1


source


Many people have studied this problem for many years. You need a SAT Solver . Search for Chaff or zChaff or whatever is used by SAT Solver. You want to take your suggestions as (p-> q && q-> r) → (p → r) and reverse them and determine if this is doable. If negation is not feasible, then you have a theorem, something that is always true. If the original clauses are doable and the denial of sentences is doable, you should return "cannot be concluded". And if the original suggestions are not doable, then you have something false.



This is a really well studied problem. There are good algorithms, but there are tight limits on the number of propositional variables you can handle. The SAT is at the center of NP issues. A class of problems for which efficient algorithms are not known.

+1


source


I think that given the simplicity of your problem, you can get rid of the simple map

. The main advantage over vector

is much faster searching.

// For "p":  { name: "p", positive: "true" }
// For "~q": { name: "q", positive: "false" }
struct Predicate {
    std::string _name;
    bool _positive;
};

using PredicateSetType = std::unordered_set<Predicate>;
using PredicateMapType = std::unordered_map<Predicate, PredicateSetType>;

You use a map in the following way: when given, p => q

you insert { "q", true }

into a set of predicates associated with { "p", true }

.

Note that this actually encodes a directed graph, so typical graph exploration techniques apply when it comes to validating a statement.

+1


source






More articles:


All Articles