logique et mathématiques discrètes

Question

Quelqu'un pourrait-il m'expliquer la solution de cette question? La question: Combien de temps faut-il approximativement pour savoir si une formule contenant 90 formules atomiques différentes est une tautologie? Vous pouvez supposer qu'il faut 1 ns pour évaluer la formule sur une seule affectation de vérité .

Solution: Il ya 2^90 ≈ 10^30 affectations possibles, il faut donc environ 10^30 ns ≈ 10^16 jours≈10^12 ans.

Answer 1

La question suppose que vous vérifiez toutes les combinaisons possibles des 90 variables de vérité. Cela signifie que vous avez 90 variables, chacune d'elles true ou false ou en d'autres termes 1 ou 0. Imaginez les 90 variables écrites en tant que zéros et en une rangée. Cela correspond à un nombre binaire de 90 chiffres. Essayer chaque combinaison de valeurs de vérité revient maintenant à essayer chaque nombre binaire de 90 chiffres. C'est la même chose que de compter 0 à 2^90 - 1 qui vous donne 2^90 combinaisons possibles.

Maintenant 2^10 = 1024 est approximativement 1000 = 10^3, donc 2^90 ≈ 10^30.