import numpy as np

def c_star(d, o):
    return (-(o+1-d) + np.sqrt((o+1-d)**2 + 4*d*o)) / (2*d)

def homeo_prune(beliefs, d=0.96):
    return {k: v for k, v in beliefs.items() if v[0] >= c_star(d, v[0])}

def backward_chain(goal, beliefs, rules, d=0.96, max_depth=5, depth=0):
    if depth > max_depth:
        return None
    pruned = homeo_prune(beliefs, d)
    if goal in pruned:
        return [('FOUND', goal, pruned[goal])]
    for (conclusion, premise, rule_conf) in rules:
        if conclusion == goal:
            sub = backward_chain(premise, pruned, rules, d, max_depth, depth+1)
            if sub:
                return sub + [('DEDUCED', goal, rule_conf)]
    return None

beliefs = {'cat_is_animal': (0.9, 0.9), 'animal_is_living': (0.85, 0.8), 'living_is_entity': (0.7, 0.7), 'weak_claim': (0.2, 0.3), 'stale_rumor': (0.15, 0.2)}
rules = [('cat_is_living', 'cat_is_animal', 0.9), ('cat_is_entity', 'cat_is_living', 0.85), ('cat_is_living', 'animal_is_living', 0.8)]
d = 0.96
print('c* threshold:', round(c_star(d, 0.5), 4))
print('Before pruning:', list(beliefs.keys()))
print('After pruning:', list(homeo_prune(beliefs, d).keys()))
print('Chain cat_is_entity:', backward_chain('cat_is_entity', beliefs, rules, d))
print('Chain with dead belief:', backward_chain('stale_rumor', beliefs, rules, d))