論理と離散数学

Question

誰かが私にこの質問の解答を説明してもらえますか？

質問： 90種類の異なる数式の式が同義語であるかどうかを調べるのにどれくらいの時間がかかりますか？単一の 真理割り当てで数式を評価するには1 nsかかると仮定することができます。

解決策： 2^90≈10^30の割り当てが可能であるため、約10^30 ns≈10^16日≒10^12年かかります。

Answer 1

質問には、90個の真理値変数のすべての可能な組み合わせをチェックしていることが前提です。これは、それぞれがtrueまたはfalseのいずれか、つまり1または0の90個の変数を持つことを意味します。 90個の変数すべてをゼロとして記述し、1つを連続して記述するとします。これは90桁の2進数に相当します。真理値のあらゆる組み合わせを試してみると、90桁の2進数ごとに試行することになります。これは0から2^90 - 1まで数えて、2^90の可能な組み合わせが得られるのと同じです。

2^10 = 1024は、約1000 = 10^3です。したがって、2^90 ≈ 10^30です。