Формула по дискретной математике
Добрый день. Год назад, на экзамене по дискретной математике, мне задали вопрос про количество/число чего-то связанного с днф / кнф / скнф, ответом на этот вопрос было то ли «два в степени два в степени два в степени эн минус один», то ли то же самое но на одну «в степени два» меньше. Всю голову сломала, все учебники пересмотрела, никак не могу найти что это за формула. Подскажите пожалуйста
Из вашего описания получается, что вам была задана формула для вычисления количества всех возможных формул в дизъюнктивной нормальной форме (ДНФ), конъюнктивной нормальной форме (КНФ) или сокращенной конъюнктивной нормальной форме (СКНФ) с использованием n логических переменных.
Точная формула зависит от того, какая именно степень двойки присутствует. Возможные формулы для различных форм нормализации выглядят следующим образом:
Для ДНФ:
- "два в степени два в степени два в степени n минус один" или 2^(2^(2^n-1))
Для КНФ:
- "два в степени два в степени два в степени n" или 2^(2^(2^n))
Для СКНФ:
- "два в степени два в степени два в степени n минус один за вычетом n" или 2^(2^(2^n-1)) - n
Обратите внимание, что n - количество логических переменных в формуле. Если n у вас отличается от задания, вам нужно заменить его на нужное значение.
Однако, уточню, что данный ответ предполагает, что вам вопрос был задан с точностью до верхней или нижней границы количества формул, так как точные формулы могут варьироваться в зависимости от контекста задания.
