L'ajout d'un nouvel état mental est en fait la mise à jour du réseau existant en effectuant les propagations de probabilités nécessaires (éventuellement en instanciant de nouvelles règles d'inférence). Considérons d'abord la mise à jour sans propagation. Nous avons besoin de manipuler des termes avec leurs connecteurs logiques. La seule restriction est que les négations doivent apparaître devant des formules atomiques pour être traitées correctement. L'algorithme de mise à jour est récursif et dépend de chacun des constituants de la formule à traiter. Mettre à jour une formule avec une probabilité P signifie qu'après la mise à jour, elle sera vraie avec une probabilité au moins égale à P. Lorsqu'il y aura plusieurs mises à jour possibles, on ne réalisera que celles qui modifient le moins possible le réseau.