Simplifier l'algorithme d'expression booléenne

Quelqu'un sait d'un algorithme afin de simplifier des expressions booléennes?

Je me souviens de l'algèbre booléenne et Karnaught cartes, mais c'est prévu pour le matériel numérique où EVERITHING est un booléen. Je voudrais quelque chose qui prend en compte le fait que certains sous-expressions ne sont pas de type boolean.

Par exemple:

a == 1 && a == 3

cela pourrait être traduite en une pure expression booléenne:

a1 && a3

mais c'est l'expression est irréductible, alors qu'avec un peu de connaissance de l'arithmétique everibody peut déterminer que l'expression est juste:

false

Certains corps connaît quelques liens?

source d'informationauteur Olmo

  1. 8

    Vous pourriez être intéressé par K-cartes et la Quine–McCluskey algorithme.

    Je pense que SymPy est capable de résoudre et de simplifier des expressions booléennes, à la recherche à la source pourrait être utile.

  2. 4

    Votre exemple pourrait être résolu par une Solveur SMT. (Il faudrait déterminer qu'aucune définition des variables pourraient faire l'expression du vrai; par conséquent, il est toujours faux. Plus général de la simplification est hors de portée pour de tels problèmes.) Montrer qu'une expression est équivalente à true ou false est bien sûr un problème NP-difficile, même sans apport de l'arithmétique dans l'affaire, donc c'est plutôt cool qu'il y a des logiciels pratiques, même pour autant. Selon la quantité de l'arithmétique de la connaissance est dans la portée, le problème peut être indécidable.

  3. 4

    Il y a deux parties à ce problème, la logique de la simplification et de la représentation de la simplification.

    Pour la logique de la simplification, de Quine-McCluskey. Pour la simplification de la représentation, de manière récursive extraire des termes à l'aide de la distribution de l'identité (0&1/0&2) == 0&(1/2).

    J'ai détaillé le processus ici. Qui donne l'explication en utilisant seulement & et |, mais il peut être modifié pour inclure tous les opérateurs booléens.

  4. 2

    Premier coup à l'aide de Google a trouvé ce document:

    http://hopper.unco.edu/KARNAUGH/Algorithm.html

    Bien sûr, qui ne traite pas avec les non-booléenne sous-expressions. Mais cette dernière partie dans sa forme générale est vraiment dur, car il n'y a certainement pas d'algorithme pour vérifier si un arbitraire expression arithmétique est vrai, faux ou quoi que ce soit. Ce que vous demandez va profondément dans le domaine de la optimisation du compilateur.

  5. 2

    Est le nombre de valeurs distinctes fini et connu? Si donc, vous pouvez convertir chaque expression une expression booléenne. Par exemple, si une a 3 valeurs distinctes, alors vous pourriez avoir des variables a1a2et a3 où a1 être vrai signifie que a == 1etc. Une fois que vous avez fait cela, vous pouvez compter sur le Quine-McCluskey algorithme (qui est probablement mieux pour les plus grands exemples de Karnaugh cartes). Voici quelques Le code Java pour Quine-McCluskey.

    Je ne peux pas parler pour savoir si cette conception de simplifier les choses ou de les rendre plus compliqué, mais vous pourriez vouloir considérer à moins.

  6. 0

    C'est dur de l'homme. L'algorithme de la façon la plus simple que j'ai trouvé était correspondre à chaque sortie en combinaison avec chaque entrée de chaque combinaison. Mais c'est l'algorithme de base, ne résout pas toutes les expressions.

    Si toutes les données de sortie (q1,q2,q3,q4) même avec de je.e entrée Une combinaison alors le résultat de la simplification sera A.

    Si non, vous allez essayer un autre variabel d'entrée /de dépendance.