15. Алгебра логики – преобразование логических выражений —Каталог задач по ЕГЭ - Информатика БУ

Главная
Каталог задач
Каталог заданий по ЕГЭ - Информатика БУ
Алгебра логики – преобразование логических выражений

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

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

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

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

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

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

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

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

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

Задача 1#49372

На числовой прямой даны два отрезка: $P$ = [55;100], $Q$ = [66;129]. Укажите наименьшую возможную длину такого отрезка $A$ , что формула

(x ∈ P ) → (((x ∈ Q )∧¬ (x ∈ A)) → ¬(x ∈ P ))

истинна, т.е. принимает значение 1 при любом значении переменной $x$ .

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

В начале для удобства заменим некоторые выражения:

$x ∈ Q = Q$
$x ∈ P = P$
$x ∈ A = A$

Тогда выражение примет такой вид:

$P =⇒ ((Q ∧ ¬A ) =⇒ ¬P)$

Заменим импликацию на отрицание первого или второе. Выражение будет выглядеть следующим образом:

$¬P ∨ (¬(Q ∧¬A )∨ ¬P )$

Раскроем отрицание в скобке. Теперь выражение имеет такой вид:

$¬P ∨ (¬Q ∨ A ∨¬P )$

Избавимся от повторяющейся Р под отрицанием и получим окончательное упрощенное выражение:

$¬P ∨ ¬Q ∨ A$

Как можем заметить, нам нужно найти значения x когда выражение равно истине, при этом только А должна равняться единице, а все остальные – 0. Не P и Не Q будут равны 0, когда х будут находиться в пределах отрезков P и Q. Получается, нас интересует отрезок, который находится как в отрезке P,так и в отрезке Q. Это отрезок: $[66;100]$ . Ответ:34.

Ответ: 34

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

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

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

Задача 2#87947

Элементами множеств А, P и Q являются натуральные числа, причём P = {2, 5, 8, 10, 14, 15, 20, 25, 26, 30, 32} и Q = {5, 15, 25, 35, 40}. Известно, что выражение

¬(x ∈ A ) → ((x ∈ P ) → ¬(x ∈ Q ))

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

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

Раскроем скобки:

(x ∈ A) ∨(x ∕∈ P )∨ (x ∕∈ Q)

Отрицаем известную часть:

(x ∈ P )∧ (x ∈ Q)

Получаем, что множество A = {5, 15, 25}. Наибольшая возможная длина равна 3.

Ответ: 3

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

Задача 3#87946

Для какого наименьшего целого числа А выражение

(y+ 10⋅x < A) ∨(5⋅x + 2⋅y > 102)

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

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

Отрицаем известную часть: $5⋅x + y ≤ 101$ . Так как х и у – целые натуральные, то минимальное значение y равно 1. Тогда $5⋅x ≤ 100$ , то есть $xmax = 20$ .

Значит, $A > 1 + 10⋅20 → A > 201 → A = 202$ .

for a in range(-1000, 1000):
    c = 0 #флаг
    for x in range(1, 1000):
        for y in range(1, 1000):
            if ((y + 10*x < a) or (5*x + 2*y > 102)) == False:
                c = 1
                break #выход из цикла, если флаг изменился
        if c == 1:
            break
    if c == 0:
        print(a) #если флаг не изменился, выводим А
        break

Ответ: 202

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

Задача 4#87945

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

(Д ЕЛ(x,4) → ¬Д ЕЛ(x,6))∨ ДЕЛ (x,A )

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

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

Раскроем выражение:

¬Д ЕЛ (x,4)∨ ¬Д ЕЛ (x,6)∨ ДЕ Л(x,A)

Отрицаем известную часть:

ДЕ Л(x,4)∧ ДЕЛ (x,6)

Получаем, что число х должно делится и на 4, и на 6. Это числа 12, 24, 36, 48 и так далее.

Значит, минимальное значение $A = 12$ .

for a in range(1, 1000):
    c = 0 #флаг
    for x in range(1, 1000):
        #проверка условия
        if (((x % 4 == 0) <= (not(x % 6 == 0))) or (x % a == 0)) == False:
            c = 1
            break #выход из цикла, если флаг изменился
    if c == 0: print(a) #если флаг не изменился, выводим А

Ответ: 12

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

Задача 5#87944

На числовой прямой даны два отрезка: $P = [10,40]$ и $Q = [18,56]$ . Отрезок A таков, что формула

¬(¬((x ∕∈ A) → ((x ∈ P) → (x ∈ Q ))))

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

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

Раскроем скобки:

¬(¬((x ∈ A )∨ (x ∕∈ P)∨ (x ∈ Q )))

(x ∈ A) ∨(x ∕∈ P )∨ (x ∈ Q)

Отрицаем известную часть:

(x ∈ P )∧ (x ∕∈ Q)

Получаем, что нам подходит отрезок: [10; 17]. Его длина $17− 10 = 7$ .

Ответ: 7

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

Задача 6#87943

На числовой прямой даны два отрезка: $P = [15,44]$ и $Q = [20,46]$ . Отрезок A таков, что формула

(x ∈ P) −→ ((¬(x ∈ Q )∧ ¬(x ∈ A)) → ¬(x ∈ P ))

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

Руками:

Раскроем скобки:

¬ (x ∈ P)∨ (x ∈ Q )∨ (x ∈ A)∨ ¬(x ∈ P)

¬ (x ∈ P)∨ (x ∈ Q )∨ (x ∈ A)

Отрицаем известную часть:

(x ∈ P )∧ (x ∕∈ Q)

Получаем, что нам подходит отрезок: [15; 19]. Его длина $19− 15 = 4$ .

Прогой:

p = [i for i in range(15, 45)]
q = [i for i in range(20, 47)]
mn = 10**10
for a1 in range(1, 500):
    for a2 in range(a1+1, 501):
        c = 0
        a = [i for i in range(a1, a2)]
        for x in range(1, 500):
            if ((x in p) <= ((not(x in q) and not(x in a)) <= (not(x in p)))) == False:
                c = 1
                break
        if c == 0:
            mn = min(len(a)-1, mn)
print(mn)

Ответ: 4

Курсы

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

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

Задача 7#87942

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

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

(((x&10 = 0)∧ (x&5 ⁄= 0)) → (x&3 ⁄= 0))∨(x&A ⁄= 0)

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

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

for a in range(1, 1000):
    c = 0
    for x in range(1, 10000):
       if (((x & 10 == 0 and x & 5 != 0) <= (x & 3 != 0)) or (x & a != 0)) == False:
            c = 1
            break
    if c == 0:
        print(a)
        break

Ответ: 4

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

Задача 8#87941

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

(x&15 ⁄= 0) → ((x&34 = 0) → (x&A ⁄= 0))

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

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

for a in range(1, 1000):
    c = 0
    for x in range(1, 1000):
       if ((x & 15 != 0) <= ((x & 34 == 0) <= (x & a != 0))) == False:
            c = 1
            break
    if c == 0:
        print(a)
        break

Ответ: 13

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

Задача 9#87940

Элементами множеств А, P и Q являются натуральные числа, причём P = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24} и Q = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36}. Известно, что выражение

((x ∈ Q) → (x ∈ A))∧ (¬(x ∈ A ) → (x ⁄∈ P ))

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

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

Перепишем выражение в виде:

((x ⁄∈ Q )∨(x ∈ A))∧ ((x ∈ A)∨ (x ⁄∈ P))

(x ∈ A )∨ ((x ⁄∈ Q )∧ (x ⁄∈ P))

Отрицаем известную часть:

(x ∈ Q )∨ (x ∈ P)

Получаем, что $x = {2,3,4,6,8,9,10,12,14,15,16,18,20,21,22,24,27,30,33,36}$ могут принадлежать А. Значит, сумма элементов равна: $330$ .

Ответ: 330

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

Задача 10#87939

Для какого наименьшего целого числа А выражение

(x > 80) ∨(y > 70)∨(3⋅x − 5⋅y < A)

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

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

Отрицаем известную часть и получаем, что:

(x ≤ 80)∧ (y ≤ 70)

То есть $x ∈ [0;80],y ∈ [0,70]$ . Нам необходимо, чтобы $A > 3 ⋅x− 5⋅y$ .

Наименьшее значение А, при котором будет выполнено равенство, достигается в точке (80, 0). $A > 3 ⋅80 − 5⋅0 → A > 240 → A = 241$ .

Прогой:

for a in range(-1000, 1000):
    c = 0 #флаг
    for x in range(0, 1000):
        for y in range(0, 1000):
            if ((x > 80) or (y > 70) or (3*x - 5*y < a)) == False:
                c = 1
                break #выход из цикла, если флаг изменился
        if c == 1:
            break
    if c == 0:
        print(a) #если флаг не изменился, выводим А
        break

Ответ: 241

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

Задача 11#87938

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

(¬ ДЕЛ (x,3) → ¬Д ЕЛ (x,7))∨ (x+ A > 120)

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

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

Решение руками:

Раскроем выражение:

Д ЕЛ (x,3)∨ ¬Д ЕЛ (x,7)∨ (x+ A > 120)

Отрицаем известную часть и получаем, что

¬ ДЕЛ (x,3) ∧Д ЕЛ (x,7)

То есть x делится на 7 и не делится на 3. Это числа: 7, 14, 28, 35, 49...

Получаем, что наименьшее А, при котором выражение верно: $7 + A > 120$ , значит, $A > 113$ , то есть $A = 114$ .

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

for a in range(1, 1000):
    c = 0 #флаг
    for x in range(1, 1000):
        #проверка условия
        if (((x % 3 != 0) <= (x % 7 != 0)) or (x + a > 120)) == False:
            c = 1
            break #выход из цикла, если флаг изменился
    if c == 0:
        print(a) #если флаг не изменился, выводим А
        break

Ответ: 114

Интенсивы

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

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

Задача 12#80628

Элементами множеств А, P, R и Q являются натуральные числа, причём P = {1, 3, 7, 9, 11, 14, 18, 24, 26, 28, 30, 32, 36, 39, 40}, R = {1, 7, 8, 10, 11, 12, 13, 14, 16, 17, 18, 24, 32, 34, 38} и Q = {8, 11, 12, 13, 14, 16, 17, 25, 26, 29, 31, 33, 34, 35, 36}. Известно, что выражение

((x ∈ P ) → (x ∈ Q))∨ ((x ∈ R) → (x ∈ A))

истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное количество элементов множества A.

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

Упростим выражение:

(x ⁄∈ P)∨ (x ∈ Q )∨ (x ⁄∈ R)∨ (x ∈ A )

Чтобы выражение было истинно, необходимо, чтобы $(x ⁄∈ P)∨ (x ∈ Q )∨(x ⁄∈ R)$ было ложно. То есть

(x ∈ P )∧(x ⁄∈ Q)∧ (x ∈ R )

Это числа: 1, 7, 18, 24, 32. Они и будут являться элементами множества A. Их количество равно 5.

Ответ: 5

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

Задача 13#80627

Элементами множеств А, P и Q являются натуральные числа, причём P = {6, 7, 9, 13, 15, 18, 21, 24, 26, 27, 33, 34, 36, 37} и Q = {3, 4, 7, 13, 14, 20, 26, 27, 28, 29, 30, 32, 35, 37}. Известно, что выражение

((x ∈ P) → (x ∈ A))∨ (x ∈ Q )

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

Упростим выражение:

(x ⁄∈ P )∨(x ∈ A)∨ (x ∈ Q)

Чтобы выражение было истинно, необходимо, чтобы $(x ⁄∈ P )∨(x ∈ Q)$ было ложно. То есть $(x ∈ P)∧ (x ⁄∈ Q )$ Это числа: 6, 9, 15, 18, 21, 24, 33, 34, 36. Они и будут являться элементами множества A. Их количество равно 9.

Ответ: 9

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

Задача 14#80626

Элементами множеств А, P и Q являются натуральные числа, причём P = {5, 7, 15, 18, 19, 31, 36, 40} и Q = {1, 10, 15, 18, 23, 27, 31, 32}. Известно, что выражение

((x ∈ Q ) ≡ (x ∈ P )) → (x ∈ A )

истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное множество A. В ответе запишите количество чисел, которые включены во все три можетсва $A$ , $P$ и $Q$ .

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

Упростим выражение:

¬ ((x ∈ Q ) ≡ (x ∈ P ))∨(x ∈ A)

¬(((x ∈ Q ) ≡ (x ∈ P ))∧(x ⁄∈ A))

Чтобы выражение $¬(((x ∈ Q) ≡ (x ∈ P))∧ (x ⁄∈ A))$ было истинно, необходимо, чтобы $((x ∈ Q) ≡ (x ∈ P))∧ (x ⁄∈ A)$ было ложно. Найдём при каких $x$ истинно выражение

(x ∈ Q ) ≡ (x ∈ P)

Это числа: 15, 18 и 31, а также все числа которые не входят ни в множетсво $Q$ ни в множество $P$ одновременно. Они и будут являться элементами множества A.

Тогда получается, что во всех 3х множествах находятся числа 15, 18 и 31. Их количество равно 3.

Ответ: 3

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

Задача 15#80625

Элементами множеств А, P и Q являются натуральные числа, причём P = {1, 4, 8, 9, 10, 25, 35, 38} и Q = {2, 5, 6, 9, 10, 25, 37, 39}. Известно, что выражение

((x ∈ P ) → (x ∈ A ))∨(¬(x ∈ A) → (x ∈ Q))∨ ¬(¬(x ∈ P ) → ¬(x ∈ Q ))

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

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

Упростим выражение:

(x ⁄∈ P )∨ (x ∈ A)∨ (x ∈ A )∨ (x ∈ Q)∨ (x ⁄∈ P )∧ (x ∈ Q)

(x ⁄∈ P )∨(x ∈ A)∨ (x ∈ Q)

Найдём при каких $x$ ложно выражение

(x ⁄∈ P )∨ (x ∈ Q)

То есть

(x ∈ P )∧ (x ⁄∈ Q)

Это числа: 1, 4, 8, 35, 38. Они и будут являться элементами множества A. Их сумма равна 86.

Ответ: 86

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

Задача 16#80624

Элементами множеств А, P и Q являются натуральные числа, причём P = {6, 8, 20, 25, 27, 30} и Q = {2, 16, 19, 25, 30, 40}. Известно, что выражение

¬(¬(x ∈ A )∧ (x ∈ Q))∨ (¬(x ∈ P) → (x ∈ A ))

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

Упростим выражение:

(x ∈ A)∨ (x ⁄∈ Q )∨ (x ∈ P)∨ (x ∈ A )

(x ∈ A) ∨(x ⁄∈ Q )∨ (x ∈ P)

Найдём при каких $x$ ложно выражение

(x ∈ P )∨ (x ⁄∈ Q)

То есть

(x ⁄∈ P )∧ (x ∈ Q)

Это числа: 2, 16, 19, 40. Они и будут являться элементами множества A. Их сумма равна 77.

Ответ: 77

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

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

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

Задача 17#80623

Элементами множеств А, P и Q являются натуральные числа, причём P = {1, 3, 4, 5, 8, 10, 11, 12, 13, 14, 15, 18, 19, 20, 22, 23, 24, 25, 26, 28} и Q = {1, 3, 4, 7, 8, 9, 11, 13, 14, 15, 17, 19, 21, 22, 24, 25, 27, 28, 29, 30}. Известно, что выражение

(x ∈ P) → ((¬ (x ∈ Q) ∧(x ∈ P )) → (x ∈ A))

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

Упростим выражение:

(x ⁄∈ P )∨(¬(¬(x ∈ Q)∧ (x ∈ P ))∨ (x ∈ A ))

(x ⁄∈ P)∨ (x ∈ Q )∨ (x ⁄∈ P)∨ (x ∈ A )

(x ⁄∈ P )∨(x ∈ Q)∨ (x ∈ A)

Найдём при каких $x$ ложно выражение

(x ⁄∈ P )∨ (x ∈ Q)

То есть

(x ⁄∈ Q )∧ (x ∈ P)

Это числа: 5, 10, 12, 18, 20, 23, 26. Они и будут являться элементами множества A. Их сумма равна 114.

Ответ: 114

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

Задача 18#80622

Элементами множеств А, P и Q являются натуральные числа, причём P = {2, 4, 6, 7, 11, 13, 14, 15, 16, 19, 21, 24, 27, 28, 29} и Q = {2, 3, 6, 9, 12, 13, 16, 17, 19, 21, 22, 23, 24, 25, 29}. Известно, что выражение

((x ∈ Q) → ¬(x ∈ P)) → ¬ (x ∈ A)

истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наибольшее возможное количество элементов множества A.

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

Упростим выражение:

((x ⁄∈ Q)∨ (x ⁄∈ P )) → (x ⁄∈ A )

(x ∈ Q )∧(x ∈ P)∨ (x ⁄∈ A)

Найдём при каких $x$ ложно выражение

(x ∈ Q )∧ (x ∈ P)

То есть

(x ⁄∈ Q )∨ (x ⁄∈ P)

Это все числа, которые не входят ни в P ни в Q. Тогда, множество A будет состоять из чисел, которые есть в обоих множествах. Это числа: 2, 6, 13, 16, 19, 21, 24, 29. Значит, ответ – 8.

Ответ: 8

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

Задача 19#80621

Элементами множеств А, P и Q являются натуральные числа, причём P = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20} и Q = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30}. Известно, что выражение

¬ (¬ (x ∈ A)∧ (x ∈ Q )) ∨¬(x ∈ P)

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

Упростим выражение:

(x ∈ A) ∨(x ⁄∈ Q )∨ (x ⁄∈ P)

Найдём при каких $x$ ложно выражение

(x ⁄∈ Q )∨ (x ⁄∈ P)

То есть

(x ∈ Q )∧ (x ∈ P)

Это числа: 6, 12, 18. Они и будут являться элементами множества A. Значит, ответ – 3.

Ответ: 3

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

Задача 20#80620

Элементами множеств А, P и Q являются натуральные числа, причём P = {1, 3, 9, 13, 17, 29, 35, 51, 42} и Q = {2, 3, 13, 35, 36, 39, 42, 51, 67}. Известно, что выражение