Тема 15. Алгебра логики – преобразование логических выражений

15.07 Прочие прототипы

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела алгебра логики – преобразование логических выражений

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#47183

Элементами множества $A$ являются натуральные числа, причем

$A ⊂ {1,2,3,4,5,6,7,8,9}$

Известно, что выражение

$(x%2 == 0)∨(x ∈ A)∨ ($ существует $y ∈ A$ такой, что $(x ⋅y)%15 == 0)$

истинно (т.е. принимает значение $1$ ) для всех $x ∈ {1,2,3,4,5,6,7,8,9}$

Определите минимальную сумму элементов множества $A$ .

Показать ответ и решение

Максимальный размер множества $A$ : $A = {1,2,3,4,5,6,7,8,9}$ . Будем выкидывать из него элементы, чтобы найти минимальную сумму.

Очевидно, что при любом чётном $x$ первая скобка всегда будет истинной, и неважно, входит $x$ в множество $A$ или нет. Значит, из множества $A$ можно убрать все чётные элементы, то есть $A = {1,3,5,7,9}$

При $x = 3$ или $x = 9$ в качестве $y$ можно взять число $5$ , тогда будет верна третья скобка, и неважно, входит $x$ в множество $A$ или нет. Значит, из множества $A$ можно убрать элементы $3$ и $9$ , то есть $A = {1,5,7}$

Тогда минимальная сумма элементов $A$ равна: $1 +5 + 7 = 13$ .

Неверное решение программой:

a = []
for x in range(1, 10):
    if ((x % 2 == 0) or (x in a) or (any(y*x % 15 == 0 for y in a))) == 0:
        a.append(x)
print(a)

В данной задаче стандартное решение программой ошибочно, поскольку оно не учитывает, что, если в множестве $A$ будет элемент $5$ , то элементы $3$ и $9$ можно не добавлять в множество, поскольку они оба в произведении с $5$ кратны $15$ . Тогда итоговая сумма будет меньше той, что получила программа.

Ответ: 13

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#56448

Пусть через ДЕЛ(m, n) обозначается утверждение «натуральное число m делится без остатка на натуральное число m»; через СУММБОЛ(k, p) –утверждение «сумма целых чисел k и p больше 0».

Для какого наименьшего натурального числа А формула

(ДЕЛ(x, 13) $→$ $¬$ СУММБОЛ(x, 25)) $∨$ (x + A $≥$ 245)

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

Показать ответ и решение

Программное решение:

for a in range(1, 240):
f = True
for x in range(1, 240):
        if not (((x % 13 == 0) <= (not x + 25 > 0)) or x + a >= 245 ):
             f = False
             break
    if f:
        print(a)
        break

Ответ: 232

Ошибка.
Попробуйте повторить позже

Задача 3#60315

Обозначим через УГОЛ(a, b, c) утверждение «значения чисел a, b, c являются углами невырожденного треугольника».Для какого наименьшего натурального числа А формула:

УГ ОЛ (A, 15,x + 25) ≡ УГ ОЛ (x,A, 60) ∧¬ (A + 10 < 100)

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

Показать ответ и решение

def angle(a,b,c):#Функция, которая проверяет может ли существовать с такими углами треугольник
    return (a+b+c) == 180
for a in range(1,1000):
    # Переменная-флаг, которой присваивается единица при ложном значении выражения
    # Если ложных значений не было, то текущее значение A нам подходит
    f = 0
    for x in range(1,10000):
        if (angle(a,15,x+25) == angle(x,a,60) and (a + 10 >= 100)) == False:
            # При ложности выражения пропускаем текущее значение A
            f = 1
            break
    # Если значение подходит по флагу — выводим
    if f == 0:
        print(a)
        break

Ответ: 140

Ошибка.
Попробуйте повторить позже

Задача 4#63122

Введём два утверждения. ОСТРОУГ(a, b, c) – «существует остроугольный треугольник со сторонами a, b и c». ТУПОУГ(a, b, c) – «существует тупоугольный треугольник со сторонами a, b и c». Аргументы a, b и c в каждой из функций подаются в неё по возрастанию, иначе функция возвращает ложное значение.

Для какой минимальной длины отрезка $A$ формула

------------------ ----------------- (ОС ТРО УГ(39,80,x)∧ ТУП ОУ Г(65,72,x)) → (((x > 80)∧(x < 119)) → (x ∈ A ))

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

Показать ответ и решение

Раскрываем импликацию и упрощаем выражение, получаем:

О СТР ОУ Г(39,80,x)∨ ТУ ПО УГ(65,72,x)∨ (x ≤ 80)∨ (x ≥ 119)∨ (x ∈ A)

«Враги» хотят, чтобы выражение было ложно:

( ||О СТ РОУ Г(39,80,x) = 0 |||| |||{Т УП ОУ Г(65,72,x) = 0 |||x > 80 ||||x < 119 ||( x ∕∈ A

Разберёмся, когда первый треугольник не будет остроугольным и когда второй треугольник не будет тупоугольным. При $x ≤ 41$ или $x ≥ 119$ треугольник (39, 80, x) не существует. При $x ≤ 7$ или $x ≥ 137$ треугольник (65, 72, x) не существует. По условию в функции ОСТРОУГ(a, b, c) и ТУПОУГ(a, b, c) подаются аргументы по возрастанию, поэтому x будет являться наибольшей стороной.

Треугольник является остроугольным, когда $a2 + b2 < c2$ и является тупоугольным при $a2 + b2 > c2$ . Таким образом, получаем, что для $(39,80,x)$ остроугольный треугольник не существует при $√ --2----2 x ≥ 39 + 80$ , то есть при $x ≥ 89$ . Аналогично для $(65,72,x )$ , тупоугольный треугольник не существует при $√-------- x ≤ 652 +722$ , то есть при $x ≤ 97$ .

Преобразуем систему в соответствии с нашими высказываниями.

( || x ≥ 89 |||| |||{ x ≤ 97 ({ ⇒ x ∈ [89;97] ||| x > 80 ( x ∕∈ A |||| x < 119 ||( x∈∕A

«Друзья» хотят победить врагов, поэтому им нужно, чтобы следующая система была истинной при всех $x$ и $A$ .

⌊ x ∕∈ [89;97] ⌈ x ∈ A

Это обеспечивается тогда, когда $[89,97] ⊂ A$ . Следовательно, минимальная длина $A$ обеспечивается, когда $A = [89,97]$ . Таким образом, длина $A$ равна $8$ .

Ответ: 8

Ошибка.
Попробуйте повторить позже

Задача 5#63124

Обозначим через ТРЕУГ( $n,m, k$ ) утверждение «существует невырожденный треугольник с длинами сторон $n,m$ и $k$ ».

Для какого наибольшего натурального числа $A$ формула

¬((Т РЕ У Г(x, 11, 18) ≡ (¬(М А КС (x, 5 ) > 15)))∧ Т РЕ УГ (x, A, 5))

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

Примечание. $М АК С(a,b) = a$ , если $a > b$ и $МА КС (a,b) = b$ , если $a ≤ b$ .

Показать ответ и решение

def triangle(a, b, c):
    a, b, c = sorted([a, b, c])
    return a + b > c

for A in range(1, 100):
    flag = True
    for x in range(1, 100):
        if not((triangle(x, 11, 18) == (not(max(x, 5) > 15))) and triangle(x, A, 5)) == False:
            flag = False
    if flag:
        print(A)

Ответ: 24

Ошибка.
Попробуйте повторить позже

Задача 6#63126

Обозначим через ТРЕУГ( $n,m, k$ ) утверждение «существует невырожденный треугольник с длинами сторон $n,m$ и $k$ ».

Для какого наибольшего натурального числа $A$ формула

¬((Т РЕ У Г(x, 12, 20) ≡ (¬(М А КС (x, 5 ) > 28)))∧ Т РЕ УГ (x, A, 3))

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

Примечание. $М АК С(a,b) = a$ , если $a > b$ и $МА КС (a,b) = b$ , если $a ≤ b$ .

Показать ответ и решение

def triangle(a, b, c):
    a, b, c = sorted([a, b, c])
    return a + b > c

for A in range(1, 100):
    flag = True
    for x in range(1, 100):
        if not((triangle(x, 12, 20) == (not(max(x, 5) > 28))) and triangle(x, A, 3)) == False:
            flag = False
    if flag:
        print(A)

Ответ: 6

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#63665

Обозначим через ТРЕУГ( $n,m, k$ ) утверждение «существует невырожденный треугольник с длинами сторон $n,m$ и $k$ ».

Для скольких натуральных чисел $A$ формула

ТР ЕУ Г(x, 25, 36)∨ Т РЕ УГ (x, 28, 55 )∨ ТР ЕУ Г(М А КС (x, 20), 40, A )∨ (x > 80)

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

Примечание. $М АК С(a,b) = a$ , если $a > b$ и $МА КС (a,b) = b$ , если $a ≤ b$ .

Показать ответ и решение

def triangle(a, b, c):
    a, b, c = sorted([a, b, c])
    return a + b > c

counter = 0
for A in range(1, 100):
    flag = True
    for x in range(1, 100):
        if (triangle(x, 25, 36) or triangle(x, 28, 55) or triangle(max(x, 20), 40, A) or (x > 80)) == False:
            flag = False
    if flag:
        counter += 1
print(counter)

Ответ: 39

Ошибка.
Попробуйте повторить позже

Задача 8#63666

Обозначим через ТРЕУГ( $n,m, k$ ) утверждение «существует невырожденный треугольник с длинами сторон $n,m$ и $k$ ».

Для скольких натуральных чисел $A$ формула

ТР ЕУ Г(x, 10, 28)∨ Т РЕ УГ (x, 14, 56 )∨ ТР ЕУ Г(М А КС (x, 20), 25, A )∨ (x > 60)

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

Примечание. $М АК С(a,b) = a$ , если $a > b$ и $МА КС (a,b) = b$ , если $a ≤ b$ .

Показать ответ и решение

def triangle(a, b, c):
    a, b, c = sorted([a, b, c])
    return a + b > c

counter = 0
for A in range(1, 100):
    flag = True
    for x in range(1, 100):
        if (triangle(x, 10, 28) or triangle(x, 14, 56) or triangle(max(x, 20), 25, A) or (x > 60)) == False:
            flag = False
    if flag:
        counter += 1
print(counter)

Ответ: 27

Ошибка.
Попробуйте повторить позже

Задача 9#63667

Обозначим через ТРЕУГ( $n,m, k$ ) утверждение «существует невырожденный треугольник с длинами сторон $n,m$ и $k$ ».

Найдите сумму всех натуральных чисел $A$ , для которых формула

¬(¬Т РЕ УГ (x, 546, A) ∧¬ ТР ЕУ Г(777, x, A ))∨(x > 1000)

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

Показать ответ и решение

def triangle(a, b, c):
    a, b, c = sorted([a, b, c])
    return a + b > c

summa = 0
for A in range(1, 1000):
    flag = True
    for x in range(1, 1000):
        if (not(not triangle(x, 546, A) and not triangle(777, x, A)) or x > 1000) == False:
            flag = False
    if flag:
        summa += A
print(summa)

Ответ: 1323

Ошибка.
Попробуйте повторить позже

Задача 10#63668

Обозначим через ТРЕУГ( $n,m, k$ ) утверждение «существует невырожденный треугольник с длинами сторон $n,m$ и $k$ ».

Найдите сумму всех натуральных чисел $A$ , для которых формула

¬(¬ТР ЕУ Г(x, 333, A )∧ ¬Т РЕ УГ (879, x, A ))∨ (x > 600)

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

Показать ответ и решение

def triangle(a, b, c):
    a, b, c = sorted([a, b, c])
    return a + b > c

summa = 0
for A in range(1, 1000):
    flag = True
    for x in range(1, 1000):
        if (not(not triangle(x, 333, A) and not triangle(879, x, A)) or (x > 600)) == False:
            flag = False
    if flag:
        summa += A
print(summa)

Ответ: 1212

Ошибка.
Попробуйте повторить позже

Задача 11#63669

Обозначим через ТРЕУГ( $n,m, k$ ) утверждение «существует невырожденный треугольник с длинами сторон $n,m$ и $k$ ».

Для скольких натуральных чисел $A$ формула

ТР ЕУ Г(x, 20, 45)∨ Т РЕ УГ (x, 15, 50 )∨ ТР ЕУ Г(М А КС (x, 16), 36, A )∨ (x > 75)

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

Примечание. $М АК С(a,b) = a$ , если $a > b$ и $МА КС (a,b) = b$ , если $a ≤ b$ .

Показать ответ и решение

def triangle(a, b, c):
    a, b, c = sorted([a, b, c])
    return a + b > c

counter = 0
for A in range(1, 100):
    flag = True
    for x in range(1, 100):
        if (triangle(x, 20, 45) or triangle(x, 15, 50) or triangle(max(x, 16), 36, A) or (x > 75)) == False:
            flag = False
    if flag:
        counter += 1
print(counter)

Ответ: 12

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#63670

Обозначим через ТРЕУГ( $n,m, k$ ) утверждение «существует невырожденный треугольник с длинами сторон $n,m$ и $k$ ».

Найдите сумму всех натуральных чисел $A$ , для которых формула

¬(¬ТР ЕУ Г(x, 111, A )∧ ¬Т РЕ УГ (101, x, A ))∨ (x > 200)

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

Показать ответ и решение

def triangle(a, b, c):
    a, b, c = sorted([a, b, c])
    return a + b > c

summa = 0
for A in range(1, 1000):
    flag = True
    for x in range(1, 1000):
        if (not(not triangle(x, 111, A) and not triangle(101, x, A)) or x > 200) == False:
            flag = False
    if flag:
        summa += A
print(summa)

Ответ: 212

Ошибка.
Попробуйте повторить позже

Задача 13#63672

Обозначим через ТРЕУГ( $n,m, k$ ) утверждение «существует невырожденный треугольник с длинами сторон $n,m$ и $k$ ».

Для какого наибольшего натурального числа $A$ формула

¬ ((Т РЕУ Г(x, 6, 10) ≡ (¬(М АК С (x, 7) > 35)))∧ ТР ЕУ Г(x, A, 5))

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

Примечание. $М АК С(a,b) = a$ , если $a > b$ и $МА КС (a,b) = b$ , если $a ≤ b$ .

Показать ответ и решение

def triangle(a, b, c):
    a, b, c = sorted([a, b, c])
    return a + b > c

for A in range(1, 100):
    flag = True
    for x in range(1, 100):
        if not((triangle(x, 6, 10) == (not(max(x, 7) > 35))) and triangle(x, A, 5)) == False:
            flag = False
    if flag:
        print(A)

Ответ: 31

Ошибка.
Попробуйте повторить позже

Задача 14#63682

Обозначим через $Q%m == n$ утверждение «Натуральное число $Q$ при делении на натуральное число $m$ даёт остаток $n$ ».

Для какого наименьшего целого числа $A$ формула

$(x < A )∨ (y < A) ∨((x∗ y)%3 == 0)∨ (4x+ 2y ⁄= 150)$

тождественно истинна (т. е. принимает значение $1$ при любых целых неотрицательных значениях переменных $x$ , $y$ )?

Показать ответ и решение

for A in range(1000):
    flag = True
    for x in range(1000):
        for y in range(1000):
            if not((x<A) or (y<A) or ((x*y)%3==0) or (4*x+2*y!=150)):
                flag = False
                break
        if not(flag):
            break
    if flag:
        print(A)
        break

Ответ: 26

Ошибка.
Попробуйте повторить позже

Задача 15#63692

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Обозначим через $m&n$ поразрядную конъюнкцию неотрицательных целых чисел $m$ и $n$ .

На числовой прямой даны отрезки $Q = [16;64]$ и $P = [48,96]$ .

Определите наименьшее натуральное число $A$ , такое что выражение

ДЕ Л(x,10)∨ (x ∕∈ Q)∨ (x&A = 0) ∨((x ∈ P ) → (|x− 30| ≥ 20))

тождественно истинно, то есть принимает значение 1 при любом целом значении переменной х.

Показать ответ и решение

def f(x, A):
    Q = [16, 64]
    P = [48, 96]
    return ((x%10 == 0) or (not inn(x, Q)) or (x & A == 0) or ((inn(x, P)) <= (abs(x - 30) >= 20)))

def inn(x, P):
    return P[0] <= x <= P[1]

for A in range(1, 1000):
    flag = True
    for x in range(-1000, 1000):
        if not f(x, A):
            flag = False
            break
    if flag:
        print(A)

Ответ: 2

Ошибка.
Попробуйте повторить позже

Задача 16#63693

Так, например, $14&5 = 1110 &0101 = 0100 = 4 2 2 2$ .

На числовой прямой дан отрезок $Q = [8;48]$ и множество $S = {43,23,76}$ .

Определите наименьшее натуральное число $A$ , такое что выражение

(¬ДЕ Л(x,5)∧ (x ∕∈ S)) → (((|x − 40| ≤ 11) → (x ∈ Q))∨ (x&A = 0))

тождественно истинно, то есть принимает значение 1 при любом целом значении переменной х.

Показать ответ и решение

def inn(x, A):
    return A[0] <= x <= A[1]

def f(x, A):
    S = {43, 23, 76}
    Q = [8, 48]
    return (((x % 5 != 0) and (not (x in S))) <=
    (((abs(x - 40) <= 11) <= (inn(x, Q))) or (x & A == 0)))

for A in range(1, 1000):
    flag = True
    for x in range(-100, 1000):
        if not f(x, A):
            flag = False
            break
    if flag:
        print(A)
        break

Ответ: 4

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 17#63717

Обозначим через ДЕЛ( $n$ , $m$ ) утверждение «число $n$ делится без остатка на число $m$ ». Для дробных чисел это означает, что результатом деления $n$ на $m$ является целое число.

На числовой прямой даны отрезки $P = [13,25]$ , $Q = [18,35]$ . Найдите максимальную длину промежутка $A$ , такого что выражение

------- ------- ------- (¬ (Д ЕЛ (x,5.5)) ∧¬ (Д ЕЛ (x,4))∨ (x ∈ Q) ∨(x ∈ A ))∧((x ∈ P )∨ (x ∈ A))

тождественно истинно, то есть принимает значение $1$ при любом натуральном числе $x$ .

Показать ответ и решение

def inn(x, A):
    return A[0] <= x <= A[1]
def f(x, A):
    P = [13, 25]
    Q = [18, 35]
    return (((x % 5.5 != 0) and (x % 4 != 0) or (not inn(x, Q)) \
         or (not inn(x, A))) and (inn(x, P) or (not inn(x, A))))
ans, n = 0, 15
borders = [0 ,0]
for a in range(1 * n, 70 * n):
    for b in range(a, 70 * n):
        A = [a / n, b / n]
        flag = True
        for x in range(1, 70 * n):  # только натуральные
            if not f(x, A):
                flag = False
                break
        if flag:
            if A[1] - A[0] > ans:
                ans = A[1] - A[0]
                borders[0] = A[0]
                borders[1] = A[1]
print(borders)
print(ans)

Видим, что программа вывела промежуток $[12.067,19.934]$ и его длину $≈ 7.867$ .

Значит, ответом является промежуток с дробными границами, левая граница которого стремится к $12$ , а правая к $20$ , тогда длина стремится к $8$ .

Ответ: 8

Ошибка.
Попробуйте повторить позже

Задача 18#63718

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

На числовой прямой дан промежуток $A$ и множество $S = {25,28,45,48,57,67}$ .

Определите максимальную длину промежутка $A$ , такого что его правая граница не больше $50$ и выражение

------- ((¬Д ЕЛ(x,5)∧ (y ∕∈ S)) → ((x > 5) → (y > 13)))∨ (x⋅y ≤ 67)∨(x ∕∈ A)∨ (y ∈ A)

тождественно истинно, то есть принимает значение $1$ при любых натуральных значениях переменных $x$ , $y$ .

Показать ответ и решение

def inn(x, A):
    return A[0] <= x <= A[1]

def f(x, y, A):
    S = {25, 28, 45, 48, 57, 67}
    return (((x % 5 != 0) and (not y in S)) <= ((x > 5) <= (y > 13))) \
        or (x * y <= 67) or (not inn(x, A)) or (not inn(y, A))

n = 5
ans = 0
for a in range(1 * n, 50 * n):
    for b in range(a, 50 * n + 1):  # + 1 чтобы проверить саму точку b
        A = [a / n, b / n]
        flag = True
        for x in range(1, 100):
            for y in range(1, 15):
                if not f(x, y, A):
                    flag = False
                    break
            if not flag:
                break
        if flag:
            ans = max(ans, A[1] - A[0])
print(ans)

Видим, что программа выдаёт результат 36.8 – это значит, что ответ стремится к 37.

Ответ: 37

Предыдущий раздел

Следующий раздел