логика и дискретная математика

Question

Может кто-нибудь, пожалуйста, объясните мне решение этого вопроса?

Вопрос: Сколько времени потребуется, чтобы выяснить, является ли формула с 90 различными атомными формулами тавтологией? Вы можете предположить, что для вычисления формулы требуется 1 нс для одного задания назначения .

Существует 2^90 ≈ 10^30 возможных назначений, поэтому требуется приблизительно 10^30 нс ≈ 10^16 дней≈10^12 лет.

Answer 1

Вопрос предполагает, что вы проверяете каждую возможную комбинацию из 90 переменных истины. Это означает, что у вас есть 90 переменных, каждый из которых либо true, либо false или другими словами 1 или 0. Представьте, что все 90 переменных записаны как нули и единицы в строке. Это соответствует 90-значному двоичному номеру. Попытка каждой комбинации значений истинности теперь состоит в том, чтобы опробовать каждые 90 цифр двоичного числа. Это то же самое, что и от 0 до 2^90 - 1, что дает вам 2^90 возможных комбинаций.

2^10 = 1024 есть примерно 1000 = 10^3, поэтому 2^90 ≈ 10^30.