Как устно решить элементарную задачу с логическим выражением на делимость чисел

225

24 апреля 2018, 03:08

Добрый день. Есть функция D(n, m), проверяющая, кратно ли натуральное число n натуральному числу m (пишу на C++ 11):

bool D(int n, int m) {
    return n % m == 0;
}

Так же есть функция F(A), которая сообщает о том, истинно ли некоторое выражение F при заданном натуральном значении A при натуральном 0 < x < 10000:

bool F(int A) {
    for (int x = 1; x < 10000; x++) {
        bool F = !D(x, A) || D(x, 21) || D(x, 35); // некоторое выражение
        if (!F) {
            return false;
        }
    }
    return true;
}

В задаче дано выражение F и требуется найти либо минимальное, либо максимальное натуральное значение числа A, при котором данное выражение будет истинно при любом натуральном значении переменной x. Задачу программным способом я решил. Как решать такую задачу при помощи ручки и листка бумаги? Очень прошу помощи, нужно научиться решать такую задачу устно. Потратил 2 месяца впустую.

Вот пример некоторых задач:

№1. bool F = !(D(x, 6) && !D(x, 4)) || (!D(x, 4) && D(x, A)); Найти наименьшее натуральное число A. Ответ: 1.

№2. bool F = D(x, A) || (!D(x, 21) && !D(x, 35)) Найти наибольшее натуральное число A. Ответ: 7.

№3. bool F = !D(x, 18) || D(x, A) || !D(x, 12) Найти наибольшее натуральное число A. Ответ: 36.

№4. bool F = !D(x, A) || !D(x, 21) || D(x, 35) Найти наименьшее натуральное число A. Ответ: 5.

№5. bool F = !(D(x, 456) && !D(x, 123)) || (!D(x, 123) && !D(x, A)) Найти наименьшее натуральное число A. Это шок, решать такую задачу на бумажке..

Answer 1

Вам нужно преобразовывать логическое выражение используя законы де Моргана и прочие свойства, а так же руководствуясь понятиями Наибольшего Общего Делителя и Наименьшего Общего Кратного. Законы де Моргана:

не (a и b) = (не a) или (не b)  
не (a или b) = (не a) и (не b)

В ваших примерах устно задачи решались бы так (цифра будет означать делимость на эту цифру, а цифра с воскл. знаком перед ней неделимость на неё):
№1

!(6 && !4) || (!4 && A) -> !6 || 4 || (!4 && A)

Здесь стоит обратить на то что у нас есть 4 || !4. Если бы у нас не было домножения на A, мы бы всегда имели истину. Однако мы можем избавиться от него, если выражение будет истинным всегда, т.е. когда x всегда кратен А, т.е. когда А=1. Кроме того, такой ход выбирает минимальное натуральное А.

№2

А || !21 && !35 -> A || !(21 || 35)

Второе слагаемое будет равно единице когда x не делится на 21 или 35, т.е. когда не делится на 7 (их НОД). Чтобы выражение всегда было равно единице, нам нужно обеспечить, чтобы все оставшиеся x были кратны 7 -> A=7.

№3

!18 || A || !12 -> !(18 && 12) && A

Это противоположный вариант, так что теперь нам нужно не НОД, а НОК, т.е. 36.

№4

!A || !21 || 35

Здесь НОД=7, т.е. все числа, которые не кратны 3*7 или кратны 5*7 дадут нам истину, взяв А=5 истину нам дадут все числа, которые не кратны 35 или кратны 35, т.е. R. Если бы было не !А, а А, то наименьшим А было бы 3, поскольку мы бы взяли все числа, которые кратны 21 или не кратны 21.

№5

!(456 && !123) || (!123 && !A) -> !456 || 123 || (!123 && !A)

Как и в первой задаче есть 123 || !123, нам нужно чтобы всегда выполнялось !A когда число кратно 456 и не кратно 123. НОК 456 и 123 равен трем, поэтому если число кратно 456 и не кратно 123, значит оно не кратно 123/3=41 (за исключением чисел 456*41*n), но эти числа за исходным диапазоном. Таким образом, А=41.