Задание 15

В этих задачах необходимо просто перебрать числа, подставить в логическое выражение и вывести ответ.

Пример 1

Задача

Обозначим через ДЕЛ(n,m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа А формула

$$\lnot ДЕЛ(x,А)\Rightarrow (ДЕЛ(x,6)\Rightarrow \lnot ДЕЛ(x,9))$$

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

Т.к. нам нужно наибольшее значение, то будем перебирать с большого числа до 1. Большое число я задал как 1000, если программа не выдаст верный ответ, увеличьте диапазон.

Переменную x будем тоже перебирать от 0 до 1000.

Скорее всего, такого размера хватит, но если хотите перестраховаться, возьмите в качестве большого числа $1000000$

Java

public class Example1 {
    // операция импликации(следования)
    static boolean impl(boolean a, boolean b) {
        return !a || b;
    }

    public static void main(String[] args) {
        // перебираем значения A
        for (int A = 1000; A > 0; A--) {
            // переменная, отвечающая на вопрос, истинно ли выражение
            // для любых при при заданном A
            boolean f = true;
            // перебираем значения x
            for (int x = 1; x < 1000; x++) {
                // если выражение ложно
                if (!(impl(x % A != 0, impl(x % 6 == 0, x % 9 != 0)))) {
                    // помещаем в переменную ответ, что выражение
                    // истинно не для всех x
                    f = false;
                    // заканчиваем перебор x
                    break;
                }
            }
            // если выражение оказалось истинным для всех x
            if (f) {
                // выводим A
                System.out.println(A);
                // заканчиваем перебор
                break;
            }
        }
    }
}

C++

#include <iostream>

// операция импликации(следования)
bool impl(int a, int b) {
    return !a || b;
}

// главный метод программы
int main() {
    // перебираем значения A
    for (int A = 1000; A > 0; A--) {
        // переменная, отвечающая на вопрос, истинно ли выражение
        // для любых при при заданном A
        bool f = true;
        // перебираем значения x
        for (int x = 1; x < 1000; x++) {
            // если выражение ложно
            if (!(impl(x % A != 0, impl(x % 6 == 0, x % 9 != 0)))) {
                // помещаем в переменную ответ, что выражение
                // истинно не для всех x
                f = false;
                // заканчиваем перебор x
                break;
            }
        }
        // если выражение оказалось истинным для всех x
        if (f) {
            // выводим A
            std::cout << A << std::endl;
            // заканчиваем перебор
            break;
        }
    }
    return 0;
}

Python

# операция импликации(следования)
def impl(a, b):
    return not a or b


# перебираем значения A
for A in range(1000, 1, -1):
    # переменная, отвечающая на вопрос, истинно ли выражение
    # для любых при при заданном A
    f = True
    # перебираем значения x
    for x in range(1, 1000):
        # если выражение ложно
        if not (impl(x % A != 0, impl(x % 6 == 0, x % 9 != 0))):
            # помещаем в переменную ответ, что выражение
            # истинно не для всех x
            f = False
            # заканчиваем перебор x
            break

    # если выражение оказалось истинным для всех x
    if f:
        # выводим A
        print(A)
        # заканчиваем перебор
        break
        

На выходе получим

18

Ответ: 18.

Пример 2

Задача

Укажите наименьшее целое значение А, при котором выражение

$(5k + 6n \gt 57) \lor ((k \leq A) \land (n \lt A))$

истинно для любых целых положительных значений k и n.

Здесь выполняется похожий перебор, только в этот раз перебирать следует от меньшего значения A к большем. А внутри перебора A перебираются две переменные.

Java

public class Example2 {
    public static void main(String[] args) {
        // перебираем значения A
        for (int A = 1; A < 1000; A++) {
            // переменная, отвечающая на вопрос, истинно ли выражение
            // для любых при при заданном A
            boolean f = true;
            // перебираем значения k
            for (int k = 1; k < 1000; k++) {
                if (!f)
                    break;
                for (int n = 1; n < 1000; n++) {
                    // если выражение ложно
                    if (!((5 * k + 6 * n > 57) || ((k <= A) && (n < A)))) {
                        // помещаем в переменную ответ, что выражение
                        // истинно не для всех x
                        f = false;
                        break;
                    }
                }
            }
            // если выражение оказалось истинным для всех x
            if (f) {
                // выводим A
                System.out.println(A);
                // заканчиваем перебор
                break;
            }
        }
    }
}

C++

#include <iostream>

// операция импликации(следования)
bool impl(int a, int b) {
    return !a || b;
}

// главный метод программы
int main() {
    // перебираем значения A
    for (int A = 1; A < 1000; A++) {
        // переменная, отвечающая на вопрос, истинно ли выражение
        // для любых при при заданном A
        bool f = true;
        // перебираем значения k
        for (int k = 1; k < 1000; k++) {
            if (!f)
                break;
            for (int n = 1; n < 1000; n++) {
                // если выражение ложно
                if (!((5 * k + 6 * n > 57) || ((k <= A) && (n < A)))) {
                    // помещаем в переменную ответ, что выражение
                    // истинно не для всех x
                    f = false;
                    break;
                }
            }
        }
        // если выражение оказалось истинным для всех x
        if (f) {
            // выводим A
            std::cout << A << std::endl;
            // заканчиваем перебор
            break;
        }
    }
    return 0;
}

Python

# операция импликации(следования)
def impl(a, b):
    return not a or b


# перебираем значения A
for A in range(1, 1000):
    #  переменная, отвечающая на вопрос, истинно ли выражение
    #  для любых при при заданном A
    f = True
    # перебираем значения k
    for k in range(1, 1000):
        if not f:
            break
        for n in range(1, 1000):
            # print(k , " " , n)
            # если выражение ложно
            if not ((5 * k + 6 * n > 57) or ((k <= A) and (n < A))):
                # помещаем в переменную ответ, что выражение
                # истинно не для всех x
                f = False
                # заканчиваем перебор x
                break

    # если выражение оказалось истинным для всех x
    if f:
        # выводим A
        print(A)
        # заканчиваем перебор
        break

На выходе получим

10  

Ответ: 10.

Пример 3

Задача

На числовой прямой даны отрезки $A = [70; 90]$, $B = [40; 60]$ и $C =[0; N]$ и функция

$$F(x) = (\lnot (x \in A) \Rightarrow (x \in B) ) \land (\lnot (x \in C) \Rightarrow (x \in A) )$$

При каком наименьшем числе N функция F(x) истинна более чем для 30 целых чисел x?

Java

public class Example3 {
    // операция импликации(следования)
    static boolean impl(boolean a, boolean b) {
        return !a || b;
    }

    public static void main(String[] args) {
        // перебираем значения A
        for (int N = 1; N < 1000; N++) {
            // кол-во целочисленных переменных x, которые при заданном N
            // дают истинное значение для функции f(x)
            int cnt = 0;
            // перебираем значения x
            for (int x = 1; x < 1000; x++) {
                // если выражение истинно
                if (impl(!(x >= 70 && x <= 90), x >= 40 && x <= 60) && impl(!(x >= 0 && x <= N), x >= 70 && x <= 90)) {
                    // увеличиваем кол-во на 1
                    cnt++;
                }
            }
            // если при заданном N функция f(x) истинна для более чем 30 целых значений x
            if (cnt > 30) {
                // выводим N
                System.out.println(N);
                // заканчиваем перебор
                break;
            }
        }
    }
}

C++

#include <iostream>

// операция импликации(следования)
bool impl(int a, int b) {
    return !a || b;
}

// главный метод программы
int main() {
    // перебираем значения A
    for (int N = 1; N < 1000; N++) {
        // кол-во целочисленных переменных x, которые при заданном N
        // дают истинное значение для функции f(x)
        int cnt = 0;
        // перебираем значения x
        for (int x = 1; x < 1000; x++) {
            // если выражение истинно
            if (impl(!(x >= 70 && x <= 90), x >= 40 && x <= 60) && impl(!(x >= 0 && x <= N), x >= 70 && x <= 90)) {
                // увеличиваем кол-во на 1
                cnt++;
            }
        }
        // если при заданном N функция f(x) истинна для более чем 30 целых значений x
        if (cnt > 30) {
            // выводим N
            std::cout << N << std::endl;
            // заканчиваем перебор
            break;
        }
    }
    return 0;
}

Python

# операция импликации(следования)
def impl(a, b):
    return not a or b


# перебираем значения A
for N in range(1, 1000):
    #  кол-во целочисленных переменных x, которые при заданном N
    #  дают истинное значение для функции f(x)
    cnt = 0
    # перебираем значения x
    for x in range(1, 1000):
        # если выражение истинно
        if impl(not (x >= 70 and x <= 90), x >= 40 and x <= 60) and impl(not (x >= 0 and x <= N), x >= 70 and x <= 90):
            # увеличиваем кол-во на 1
            cnt = cnt + 1
    # если при заданном N функция f(x) истинна для более чем 30 целых значений x
    if cnt > 30:
        # выводим N
        print(N)
        # заканчиваем перебор
        break

На выходе получим

49

Ответ: 49.

Пример 4

Задача

Известно, что для некоторого отрезка А формула

$$((x\in A)\Rightarrow(x^2\leq64))\land((x^2\leq 25)\Rightarrow(x\in A))$$

тождественно истинна (то есть принимает значение 1 при всех вещественных значениях переменной x). Какую наименьшую длину может иметь отрезок A?

В этой задаче мы будем перебирать начало и конец диапазона от -1000 до 1000, а внутри перебирать целые значения x от -1000 до 1000.

Внутри цикла мы будем считать проверять, что текущий интервал обращает функцию $f(x)$ в истину при всех x из заданного интервала.

Для каджого подходящего интервала будем сравнивать его длину с минимальной найденной длиной, если его длина меньше, будем записывать его длину в переменную минимума.

Java

public class Example4 {
    // операция импликации(следования)
    static boolean impl(boolean a, boolean b) {
        return !a || b;
    }

    public static void main(String[] args) {
        // минимальная длина интервала
        int minRange = 2000;
        // перебираем начало интервала
        for (int A0 = -1000; A0 < 1000; A0++) {
            // перебираем конец интервала
            for (int A1 = A0 + 1; A1 < 1000; A1++) {
                // переменная, отвечающая на вопрос, истинно ли выражение
                // для любых при при заданном A
                boolean f = true;
                // перебираем значения x
                for (int x = -1000; x < 1000; x++) {
                    // если выражение ложно
                    if (!(
                            impl(x >= A0 && x <= A1, x * x <= 64) &&
                                    impl(x * x <= 25, x >= A0 && x <= A1)
                    )) {
                        // помещаем в переменную ответ, что выражение
                        // истинно не для всех x
                        f = false;
                        // заканчиваем перебор x
                        break;
                    }
                }
                // если выражение оказалось истинным для всех x
                if (f) {
                    // если минимальная длина диапазона меньше
                    // длины текущего
                    if (minRange > A1 - A0)
                        // сохраняем новую длину
                        minRange = A1 - A0;
                }
            }
        }
        // выводим минимальную длину диапазона
        System.out.println(minRange);
    }
}

C++

#include <iostream>

// операция импликации(следования)
bool impl(int a, int b) {
    return !a || b;
}

// главный метод программы
int main() {
    // перебираем значения A
    for (int A = 1; A < 1000; A++) {
        // переменная, отвечающая на вопрос, истинно ли выражение
        // для любых при при заданном A
        bool f = true;
        // перебираем значения k
        for (int k = 1; k < 1000; k++) {
            if (!f)
                break;
            for (int n = 1; n < 1000; n++) {
                // если выражение ложно
                if (!((5 * k + 6 * n > 57) || ((k <= A) && (n < A)))) {
                    // помещаем в переменную ответ, что выражение
                    // истинно не для всех x
                    f = false;
                    break;
                }
            }
        }
        // если выражение оказалось истинным для всех x
        if (f) {
            // выводим A
            std::cout << A << std::endl;
            // заканчиваем перебор
            break;
        }
    }
    return 0;
}

Python

# операция импликации(следования)
def impl(a, b):
    return not a or b


# минимальная длина интервала
minRange = 200

# перебираем начало интервала
for A0 in range(-1000, 100):
    # перебираем конец интервала
    for A1 in range(A0 + 1, 100):
        # переменная, отвечающая на вопрос, истинно ли выражение
        # для любых при при заданном A
        f = True
        # перебираем значения x
        for x in range(-100, 100):
            # если выражение ложно
            if not (impl(x >= A0 and x <= A1, x * x <= 64) and
                    impl(x * x <= 25, x >= A0 and x <= A1)):
                # помещаем в переменную ответ, что выражение
                # истинно не для всех x
                f = False
                # заканчиваем перебор x
                break

        # если выражение оказалось истинным для всех x
        if f:
            # если минимальная длина диапазона меньше
            # длины текущего
            if minRange > A1 - A0:
                # сохраняем новую длину
                minRange = A1 - A0

print(minRange)

На выходе получим

10

В программе python я уменьшил большие по модулю числа, чтобы программа быстрее выполнилась, если у вас есть время ждать выполнения программы, увеличьте их.

Пример 5

Задача

Введём выражение $M \& K$, обозначающее поразрядную конъюнкцию $M$ и $K$ (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число a, такое что выражение

$$( x \& 125 \ne 1) \lor ((x \& 34 = 2) \rightarrow (x \& a = 0))$$

тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной x)?

Java

public class Example5 {
    // операция импликации(следования)
    static boolean impl(boolean a, boolean b) {
        return !a || b;
    }

    public static void main(String[] args) {
        // перебираем значения A
        for (int a = 1; a < 1000; a++) {
            // переменная, отвечающая на вопрос, истинно ли выражение
            // для любых при при заданном a
            boolean f = true;
            // перебираем значения x
            for (int x = 1; x < 1000; x++) {
                // если выражение ложно
                if (!(((x & 125) != 1) || impl((x & 34) == 2, (x & a) == 0))) {
                    // помещаем в переменную ответ, что выражение
                    // истинно не для всех x
                    f = false;
                    // заканчиваем перебор x
                    break;
                }
            }
            // если выражение оказалось истинным для всех x
            if (f) {
                // выводим a
                System.out.println(a);
                // заканчиваем перебор
                break;
            }
        }
    }
}

C++

#include <iostream>

// операция импликации(следования)
bool impl(int a, int b) {
    return !a || b;
}

// главный метод программы
int main() {
    // перебираем значения A
    for (int a = 1; a < 1000; a++) {
        // переменная, отвечающая на вопрос, истинно ли выражение
        // для любых при при заданном a
        bool f = true;
        // перебираем значения x
        for (int x = 1; x < 1000; x++) {
            // если выражение ложно
            if (!(((x & 125) != 1) || impl((x & 34) == 2, (x & a) == 0))) {
                // помещаем в переменную ответ, что выражение
                // истинно не для всех x
                f = false;
                // заканчиваем перебор x
                break;
            }
        }
        // если выражение оказалось истинным для всех x
        if (f) {
            // выводим a
            std::cout << a << std::endl;
            // заканчиваем перебор
            break;
        }
    }
    return 0;
}

Python

# операция импликации(следования)
def impl(a, b):
    return not a or b


# перебираем значения A
for a in range(1, 1000):
    # переменная, отвечающая на вопрос, истинно ли выражение
    # для любых при при заданном a
    f = True
    # перебираем значения x
    for x in range(1, 1000):
        # если выражение ложно
        if not (((x & 125) != 1) or impl((x & 34) == 2, (x & a) == 0)):
            # помещаем в переменную ответ, что выражение
            # истинно не для всех x
            f = False
            # заканчиваем перебор x
            break

    # если выражение оказалось истинным для всех x
    if f:
        # выводим a
        print(a)
        # заканчиваем перебор
        break
        

На выходе получим

4

Ответ: 4.

Задания для самостоятельного выполнения