Решение 15 задания егэ информатика 2022 на питоне

Сегодняшний урок посвящён 15 заданию из ЕГЭ по информатике 2022.

Темой этого урока связана с преобразованием логических выражений.

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

Перейдём к практике решения задач 15 задания из ЕГЭ по информатике 2022.

Задача (Неравенство, одна переменная)

Какое количество натуральных чисел удовлетворяет логическому условию:

¬(X2 ≥ 9) ∨ ¬((X < 7) ∨ (X ≥ 10)) ?

Решение:

Первый способ (с помощью питона).

k=0
for x in range(1, 1000):
    if not(x**2 >= 9) or not((x < 7) or (x>=10)):
        k = k + 1
        
print(k)

Здесь перебираем с помощью цикла for натуральные числа от 1 до 1000.

Если логическое выражение выдаёт истину, то мы подсчитываем такой вариант.

Программа напечатает число 5.

Второй способ (с помощью рассуждений).

Натуральные числа — это целые, положительные числа. Например: 1, 2, 3, 4, и т. д.

Преобразуем первое выражение ¬(X2 ≥ 9) = (X2 < 9). Отрицание внесли в скобки. В этом случае знак, который находится в скобках, нужно поменять на противоположный.

Важно: Если было строгое неравенство, то оно станет нестрогим, и наоборот, если было неравенство нестрогим, то оно станет строгим.

Получается, что выражение (X2 < 9) будет истинно только при двух значениях: X = 1, X = 2.

Во втором выражении ¬((X < 7) ∨ (X ≥ 10)) удобно применить формулу Де Моргана.

Формула де Моргана:

¬(A ∨ B) = ¬A ∧ ¬B

¬(A ∧ B) = ¬A ∨ ¬B

Преобразуем выражение по формуле де Моргана и внесём отрицание в скобки:

¬((X < 7) ∨ (X ≥ 10)) = ¬(X < 7) ∧ ¬(X ≥ 10) = (X ≥ 7) ∧ (X < 10)

Получилось выражение (X ≥ 7) ∧ (X < 10). Между двумя выражениями стоит логическое умножение. Значит, одновременно должны выполняться и первое неравенство, и второе. Таким образом, получается, что подходят три значение для выражения (X ≥ 7) ∧ (X < 10). Это X = 7, X = 8, X = 9.

Обратимся к самому начальному логическому условию. Там два выражения соединятся логическим сложением. Значит, мы должны объединить те случаи, когда у нас первое выражение становится истинным (X=1, X=2), и те случаи, когда второе выражение становится истинным (X = 7, X = 8, X = 9).

Получается всего 5 натуральных чисел удовлетворяют изначальному логическому условию.

Ответ: 5

Разберём ещё одну разминочную задачу для подготовки к ЕГЭ по информатике 2022.

Задача (Неравенство, две переменные)

Для какого наибольшего целого неотрицательного числа A выражение

(x ≥ A) ∨ (y ≥ A) ∨ (x * y ≤ 205)

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

Решение:

Первый способ (с помощью питона).

for A in range(0, 300):
    k=0
    for x in range(1, 301):
        for y in range(1, 301):
            if (x >= A) or (y >= A) or (x * y <= 205):
                k=k+1
    if k==90000:
        print(A)

В первом цикле перебираем значения для A. Здесь мы пытаемся подобрать ответ в диапазоне от 0 до 300. Этот диапазон меньше, чем в прошлой задаче. Потому что здесь три вложенных цикла, и если перебирать числа от 0 до 1000, то программа может работать очень долго. При необходимости можно указать другой диапазон.

Для каждого A устанавливаем счётчик k в ноль.

Затем перебираем все числа в диапазоне от 1 до 300 (включительно) для переменных x и y, тем самым имитируем фразу «для любых x и y».

Если логическое выражение сработает при каждом значении x и y, то считается, что значение A нам подходит, и в счётчике по окончанию вложенных циклов будет значение 90000 (300 * 300 = 90000).

Наибольшее число, которое напечатает программа равно 15.

Второй способ (с помощью рассуждений).

Здесь есть три выражения в скобках, которые соединены логическим сложением. При логическом сложении достаточно хотя бы одного выражения, где будет истина, чтобы всё общее выражение было истинно.

Если мы сделаем A слишком большим, к примеру A = 250, то найдутся такие x = 16, y = 16, при которых все три условия в скобках не будут выполняться, и, значит, всё общее выражение будет ложным.

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

Сделаем так: пока x и y меньше A, должно «работать» третье выражение в скобках. Как только x или y сравняются с A — начинают «работать» первое или второе выражение.

До какого же максимального значения могут дойти x и y, чтобы перемножение этих двух чисел было меньше или равно 205 (x * y <= 205) ?

15 * 15 = 225
14 * 14 = 196

Получается, пока числа x и y меньше 15, «выручает» третье выражение (x * y ≤ 205), как только станут x ≥ 15 и y ≥ 15, будут «работать» первое и второе выражение.

Отсюда получаем, что максимальное число A = 15

Ответ: 15

Задача (Функция ДЕЛ)

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

¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 9))

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

Решение:

Первый способ (с помощью питона).

def D(n, m):
    if n%m==0:
        return True
    else:
        return False

for A in range(1, 1000):
    k=0
    for x in range(1, 1001):
        if D(x, A) or (not(D(x, 6)) or not(D(x, 9))):
            k=k+1
    if k==1000:
        print(A)

Здесь мы формируем функцию ДЕЛ (функцию D). Если n делится на m, то функция возвращает Истину, в противном случае функция возвращает Ложь.

Далее решаем примерно так же, как и в прошлых задачах: для каждого числа A перебираем все значения x. Следование расписываем по формуле A ⟶ B = ¬A ∨ B.

Наибольшее число здесь получается равно 18.

Второй способ (с помощью рассуждений).

Рассмотрим случай, когда в левой части логического выражения будет 1, а в правой 0. В остальных случаях беспокоится не за что, потому что вся формула будет выдавать истину.

ЕГЭ по информатике 2022 - задание 15 (Функция ДЕЛ)

Посмотрим, когда в правой части получается ноль. Функция ДЕЛ(x, 6) должна выдавать истину. Т.е. x должен делится на 6. А функция ¬ДЕЛ(x, 9) должна выдавать ноль. Т.е. без отрицания ДЕЛ(x, 9) должна выдавать истину. Значит, x так же делится на 9.

x делится на 6 => x = 2*3*n, n ∈ N
x делится на 9 => x = 3*3*n, n ∈ N

Чтобы выполнялся случай, когда в правой части получается ноль, икс должен быть равен x = 3*3*2*n (n ∈ N). Т.е. получается, что икс должен быть кратен 18.

Т.е. получается, что когда x делится на 18, в правой части логического выражения будет получатся ноль. Чтобы спасти ситуацию, мы должны в левой части логического выражения не получать 1. Следовательно, ¬ДЕЛ(x, А) должно выдавать ноль. Значит, ДЕЛ(x, А) должно выдавать 1. Таким образом, приходим к выводу, что A должно равняться 18.

Если получится опасная ситуация, когда x кратен 18, то она будет нейтрализована, ведь в левой части будет получатся ноль.

Ответ: 18

Ещё один важный тип задач 15 задания ЕГЭ по информатике 2022

Задача (Поразрядная конъюнкция)

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14&5 = 11102 & 01012 = 4

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

x&51 ≠ 0 → (x&A = 0 → x&25 ≠ 0)

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

Решение:

Первый способ (с помощью питона).

for A in range(0, 1000):
    k=0
    for x in range(0, 1000):
        if x&51==0 or (x&A!=0 or x&25!=0):
            k=k+1

    if k==1000:
        print(A)

Здесь следование преобразовываем по формуле: A ⟶ B = ¬A ∨ B. Так же и A, и x неотрицательные числа. Поэтому мы перебираем их диапазон, начиная с нуля. Из-за этого в цикле, который перебирает переменную x, мы устанавливаем верхнюю границы равной 1000, а не 1001. Тогда тоже будет 1000 повторений в этом цикле.

Наименьшее число равно 34.

Второй способ (с помощью рассуждений).

Переведём числа 51 и 25 в двоичную систему.

51 = 1100112
25 = 110012

Формула будет тождественно ложна, когда

ЕГЭ по информатике 2021 - задание 15 (Поразрядная конъюнкция)

Этого допустить нельзя!

При каком x получается в левой выражении формулы истина ? Если у икса в двоичном представлении в тех разрядах, где у числа 51 стоят 1, будет хотя бы в одном месте 1.

Рассмотрим правое выражение формулы. Ноль получается в единственном случае:

ЕГЭ по информатике 2021 - задание 15 (Поразрядная конъюнкция)

Рассмотрим выражение x&25 ≠ 0. Чтобы в этом логическом выражении получился ноль, нужно x&25 = 0. Посмотрим на двоичное представление числа 25. В тех разрядах, где стоят единицы, у икс должны быть нули (для x&25 = 0).

Сформулируем окончательное условие для x, при котором возникает опасность превращение общей формулы в ложь.

ЕГЭ по информатике 2021 - задание 15 (Поразрядная конъюнкция, схема решения)

Нам нужно «поломать эту песенку» с помощью x&A = 0. Т.е. нельзя допускать, чтобы это выражение было истинно.

Получается, что A = 1000102. Это наименьшее из возможных число, при котором мы точно себя обезопасим от того, что вся формула будет ложна.

A = 1000102 в десятичной системе будет 34.

Ответ: 34

Ещё один тип задач 15 задания ЕГЭ по информатике

Задача (числовая прямая)

На числовой прямой даны отрезки P=[5, 13] и Q=[8, 19]. Укажите наименьшую возможную длину такого отрезка A, что формула (¬(x ∈ P) → (x ∈ Q)) → (x ∈ A ) верна при любых значениях x.

Решение:

Первый способ (с помощью питона).

def F(a, b, x):
    if a <= x <= b:
        return True
    else:
        return False

mn=10**9

for a in  range(0, 200):
    for b in  range(a, 200):
        k=0
        for i in  range(-200, 200):
            x = i / 2
            if not((F(5, 13, x) or F(8, 19, x))) or F(a, b, x):
                k=k+1

        if k==400:
            mn= min(mn, b-a)

 print(mn)

Получается ответ 14. Более подробно, как решать задачи на ОТРЕЗКИ из 15 задания ЕГЭ по информатике на Python, можете посмотреть в этой статье.

Второй способ (с помощью рассуждений).

Если будут такие варианты:

ЕГЭ по информатике 2021 - задание 15 (Задача числовая прямая)

То нам беспокоится не о чём. Потому что формула всегда будет истинна! (см. таблицу истинности для следования →)

Нас же будет интересовать этот случай.

ЕГЭ по информатике 2021 - задание 15 (Задача числовая прямая, решение)

При таком раскладе вся формула будет ложна! Нам нужно этого не допустить при любом значении x!

Единица получается в первом подвыражении в трёх случаях:

1) Случай

ЕГЭ по информатике 2021 - задание 15 (Задача числовая прямая, решение, первый случай)

Выражение ¬(x ∈ P) получается ложно, когда (x ∈ P) будет истинно! Получается при x ∈ [5, 13] выражение ¬(x ∈ P) — ложно!

Выражение (x ∈ Q) ложно, когда x ∉ [8, 19]

Какой же минимальной длины должен быть отрезок A, чтобы этот случай не проходил при любом x ? При этом случае отрезок A должен быть равен [5, 8). Тогда левое выражение пусть и может стать единицей при x ∈ [5, 8), но выражение (x ∈ A) будет также равно 1 при x ∈ [5, 8)! И схема 1 → 0 не пройдёт. Будет 1 → 1.

Для 1 случая A=[5, 8) .

2) Случай

ЕГЭ по информатике 2021 - задание 15 (Задача числовая прямая, решение, второй случай)

При каких x выражение ¬(x ∈ P) обращается в ноль, мы уже рассматривали: x ∈ [5, 13].

Второе выражение «выдаёт» 1 при x ∈ [8, 19].

Получается, что при при x ∈ [8; 13] первое выражение в скобках в главной формуле будет тождественно истинно!

С помощью отрезка A нужно это нейтрализовать путём превращения второго выражения в скобках в главной формуле в 1, пока x ∈ [8; 13]. Значит, для этого случая A = [8; 13]

3) Случай

ЕГЭ по информатике 2021 - задание 15 (Задача числовая прямая, решение, третий случай)

В выражении ¬(x ∈ P) единица получается, когда в выражении (x ∈ P) получается ноль. Тогда x ∉ [5, 13]!

Чтобы во втором выражении (x ∈ Q) была единица, нужно, чтобы x ∈ [8, 19].

Получается, что 3 случай выполняется, если x ∈ (13, 19].

С помощью отрезка A нужно этому противодействовать! Нужно чтобы выражение (x ∈ A) было всегда 1 при x ∈ (13, 19]. Тогда A должно быть (13, 19].

Следовательно, для третьего случая A=(13, 19].

Нам нельзя допустить ни одного случая! Поэтому, объединив все случаи, получаем, что A=[5, 19].

Длина отрезка равна 14.

Ответ: 14

Ещё одна задача про числовую прямую из банка тренировочных заданий ЕГЭ по информатике 2021.

Задача (Числовая прямая, закрепление)

На числовой прямой даны отрезки P=[5, 13] и Q=[8, 19]. Укажите наименьшую возможную длину такого отрезка A, что формула ((x ∈ P) ∧ ¬(x ∈ A)) → ((x ∈ Q) ∧ ¬(x ∈ A)) верна при любых значениях x.

Решение:

Первый способ (с помощью питона).

def F(a, b, x):
    if a <= x <= b:
        return True
    else:
        return False

mn=10**9

for a in range(0, 200):
    for b in range(a, 200):
        k=0
        for i in range(-200, 200):
            x = i / 2
            if not((F(5, 13, x) and not(F(a, b, x)))) or (F(8, 19, x) and not(F(a, b, x))):
                k=k+1

        if k==400:
            mn=min(mn, b-a)

print(mn)

Второй способ (с помощью рассуждений).

Формула может быть ложна, когда

ЕГЭ по информатике 2022 - задание 15 (Отрезки 2)

Во всех остальных случаях, формула всегда верна.

Чтобы выражение ((x ∈ P) ∧ ¬(x ∈ A)) было тождественно 1, выражение (x ∈ P) обязательно должно быть тождественно 1. А, значит, x ∈ [5, 13] — это опасная зона, при которой появляется возможность обратить всю формулу в ноль!

Мы можем сразу пресечь эту опасность с помощью отрезка A. Выбрать такой отрезок, чтобы он всегда «выдавал» ложь при x ∈ [5, 13]. Для этого достаточно выбрать A=[5, 13]! Но вдруг его можно сделать ещё более маленьким за счёт правой части формулы ?

Предположим, что отрезок A сделали ещё меньшим. Тогда при каком-то x (x ∈ [5, 13]) выражение ¬(x ∈ A) будет «выдавать» 1! Причём такое же выражение стоит и в правой части формулы! Там тоже будет 1 для выражения ¬(x ∈ A).

Нас же в этом случае должно выручить выражение (x ∈ Q). Если оно «выдаст» 1 в этот «сложный» момент, то мы спасены! Ведь тогда получается, что правая часть всей формулы будет «выдавать» не 0, а 1. Посмотрим при каких x из отрезка [5, 13] приходит это спасение.

Видим, что в интервале x ∈ [8, 13] нас спасает выражение (x ∈ Q).

Значит, отрезок A можно сократить до A=[5, 8).

Длина отрезка будет равна 3!

Ответ: 3

Задачи для закрепления

Задача (Неравенство, две переменные, закрепление)

Для какого наибольшего целого неотрицательного числа A выражение

(x < A) ∧ (y < A) ∧ (x * y > 603)

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

Решение:

Первый способ (с помощью питона).

for A in range(0, 300):
    k=0
    for x in range(1, 301):
        for y in range(1, 301):
            if not( (x < A) and (y < A) and (x * y > 603) ):
                k=k+1
    if k==90000:
        print(A)

Т.к. выражение должно быть ЛОЖНО, то обернём логическое выражение в функцию not(). Видим, что программа не сильно отличается от прошлой задачи. Данный шаблон подходит для большинства задач подобного типа.

Наибольшее число получается равно 25.

Второй способ (с помощью рассуждений).

В этой задаче нужно, чтобы общее выражение было ложно!

Если мы поставим отрицание над всем выражением, то можно искать такое максимальное A, при котором всё выражение тождественно истинно, а не ложно!

¬((x < A) ∧ (y < A) ∧ (x * y > 603)) = ¬(x < A) ∨ ¬(y < A) ∨ ¬(x * y > 603)

Здесь применили формулу де Моргана! Т.е. каждое подвыражение получило отрицание + соединительная логическая операция (логическое умножение) сменилась на противоположную операцию (логическое сложение).

Внесём отрицание в скобки. Получается:

(x ≥ A) ∨ (y ≥ A) ∨ (x * y ≤ 603)

Получили ситуацию, как в прошлой задаче! Напомню, что теперь нужно, чтобы общее выражение было истинно.

Найдём максимальное число, до которого могут «подняться» x и y, чтобы ещё работало третье выражение!

Обратите внимание, что x и y — симметричны. Значит, что верхняя планка для x и y будет одно и тоже число.

Поэтому вспоминаем таблицу квадратов.

25 * 25 = 625
24 * 24 = 576

Получается, что максимальное число до которого могут «дойти» x и y, чтобы «работало» третье выражение, равно 24.

Тогда, начиная с 25 для x и y, должны работать первое и второе выражение.

Получается, что максимальное число для A равно 25.

Ответ: 25

Ещё одна задачка подобного типа из тренировочных упражнений 15 задания ЕГЭ по информатике.

Задача (Неравенство, две переменные, закрепление)

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

(3 * x + y < A) ∨ (x < y) ∨ (16 ≤ x)

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

Решение:

Первый способ (с помощью питона).

for A in range(-300, 300):
    k=0
    for x in range(1, 301):
        for y in range(1, 301):
            if (3*x + y < A) or (x < y) or (16 <= x):
                k=k+1
    if k==90000:
        print(A)

Наименьшее число равно 61. Здесь не сказали, что A принимает неотрицательные значения, поэтому мы включили в диапазон для A числа, которые меньше нуля. Из-за этого увеличилось время выполнения программы, но ответ получим за приемлемое время.

Второй способ (с помощью рассуждений).

Чтобы вся формула была тождественно истинна, нужно, чтобы хотя бы одно выражение «выдавало» истину, т.к. выражения в формуле соединяются с помощью логического сложения!

Взглянем на третье выражение. Пока x ≥ 16, всё идёт как надо. Третье выражение будет истинно, и, значит, вся формула будет истинна.

Но если x ≤ 15, то нужно, чтобы нас «спасало» первое или второе выражение.

Рассмотрим второе выражение. Пока y > x (x ≤ 15) => y > 15, у нас всё нормально, второе выражение будет истинно, и вся формула будет истинна.

Теперь обратим внимание на первое выражение. Оно должно нас «спасать», когда третье и второе выражение «не спасло»! Это возможно, если x ≤ 15 (иначе «спасло» бы третье выражение), а так же y ≤ 15 (иначе «спасало» бы второе выражение).

Но, чтобы первое выражение было всегда истинно при x ≤ 15 и y ≤ 15, мы должны подобрать число A при максимальных x и y (x=15, y=15)! Ведь для более маленьких значений выражение (3 * x + y < A) точно будет истинно.

Получается:

3 * 15 + 15 < A
60 < A

Нужно найти наименьшее число для A, при котором A > 60. Тогда там, где не «спасли» третье и второе выражение, точно «спасёт» первое выражение. Получается A = 61.

Ответ: 61

Задача (ЕГЭ по информатике, Москва, 2020)

Для какого наибольшего целого неотрицательного числа A выражение

(x > A) ∨ (y > x) ∨ (2 * y + x < 110)

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

Решение:

Первый способ (с помощью питона).

for A in range(0, 300):
    k=0
    for x in range(1, 301):
        for y in range(1, 301):
            if (x > A) or (y > x) or (2 * y + x < 110):
                k=k+1
    if k==90000:
        print(A)

Максимальное число получается равно 36.

Второй способ (с помощью рассуждений).

Пока y > x, второе подвыражение всегда истинно, значит, и всё выражение истинно.

Теперь будем рассматривать случай y ≤ x.

Рассмотрим третье подвыражение. Найдём максимальные значения для x и для y, которые они одновременно могут принимать, и при которых ещё выполняется третье условие.

Т.к. мы рассматриваем случай y ≤ x, то максимальное число для y будет xmax т.е. ymax = xmax.

Тогда

2 * xmax + xmax < 110

3 * xmax < 110

36 * 3 = 108
37 * 3 = 111

xmax = ymax = 36

Если x «перевалит» за 36, и при этом y ≤ x (иначе «спасает» второе подвыражение), то должно «спасать» первое выражение.

Получается, что наибольшее значение A будет равно 36.

Ответ: 36

Следующий тип задач часто можно встретить в тренировочных вариантах ЕГЭ по информатике 2022.

Задача (С функцией ДЕЛ, закрепление)

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

ДЕЛ(120, A) ∧ ((ДЕЛ(x, 70) ∧ ДЕЛ(x, 30)) → ДЕЛ(x, A))

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

Решение:

Первый способ (с помощью питона).

def D(n, m):
    if n%m==0:
        return True
    else:
        return False

for A in range(1, 1000):
    k=0
    for x in range(1, 1001):
        if D(120, A) and (not(D(x, 70) and D(x, 30)) or D(x, A)):
            k=k+1
    if k==1000:
        print(A)

Наибольшее число получается равно 30.

Второй способ (с помощью рассуждений).

Рассмотрим левую часть логического выражения. Мы видим, что число 120 должно делится на A. Значит, для A уже есть некоторое ограничение (A <= 120).

Рассмотрим правую часть выражения. Изучим, когда она превращается в ноль. Тогда


ЕГЭ по информатике 2022 - задание 15 (Функция ДЕЛ) 2

Т.е. x должен делится на 70 и одновременно x должен делится на 30.

x = 70*n = 2*5*7*n (n ∈ N)

x = 30*n = 2*5*3*n (n ∈ N)

Чтобы одновременно выполнялись два условия, икс должен быть равен x = 2*5*7*3*n (n ∈ N).

Для того, чтобы правое выражение не превращалось в ноль, x как раз должен делится на число 2*5*7*3. Тогда будет 1->1. Т.е. число A должно равняться 2*5*7*3. Но мы сказали, что A <= 120, плюс, должно являться делителем числа 120. Значит, должны снизить значение для A.

Рассмотрим значение 2*5*7 для числа A (Предыдущее число, но без тройки). Для правой части оно подходит, т.к. «при малейшей» возможности превращения правого выражения в ноль (т.е. ДЕЛ(x, 70) = True), у нас будет спасаться ситуация, т.к. ДЕЛ(x, A) так же
будет равно 1. И снова получаем 1->1. Но это значение не подходит для левой части, ведь тогда A не является делителем числа 120.

Приходится брать число 2*5*3 (без семёрки). Здесь ситуация аналогично предыдущему случаю, только теперь это число является делителем числа 120.

В ответе напишем 30.

Ответ: 30

Задача (Поразрядная конъюнкция, закрепление)

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

(X & 49 ≠ 0) → ((X & 33 = 0) → (X & A ≠ 0))

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

Решение:

Первый способ (с помощью питона).

for A in range(1, 1000):
    k=0
    for x in range(1, 1001):
        if (x&49==0) or ((x&33!=0) or (x&A!=0)):
            k=k+1

    if k==1000:
        print(A)

Наименьшее число равно 16.

Второй способ (с помощью рассуждений).

Переведём числа 49 и 33 в двоичную систему.

4910 = 1100012

3310 = 1000012

Рассмотрим случай, когда функция стремится превратится в ноль.

ЕГЭ по информатике 2022 - задание 15 (Поразрядная конъюнкция, схема решения)

Чтобы левое выражение выдавало истину, икс должен иметь 1 (единицу) в первом разряде или во второй разряде, или в последнем разряде (в 6-ти битном числе).

Рассмотрим правое выражение. Посмотрим, когда выражение (X & 33 = 0) выдаёт истину. Первый бит и последний бит должен быть равен нулю. Т.е получается, что в 6-ти битном числе нас интересует второй бит. Если он будет равен 1 и при этом первый бит и последний будут равны 0, то возникает опасная ситуация, которую нужно спасть.

При выше описанных условиях выражение (X & A ≠ 0) должно выдавать истину. Тогда наименьшее A равно 100002 = 162.

Ответ: 16

Задача (числовая прямая, закрепление 2)

На числовой прямой даны два отрезка: P = [20, 30] и Q = [35, 60]. Найдите наименьшую возможную длину отрезка A, при котором формула

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

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

Решение:

Первый способ (с помощью питона).

def F(a, b, x):
    if a <= x <= b:
        return True
    else:
        return False

mn=10**9

for a in range(0, 200):
    for b in range(a, 200):
        k=0
        for i in range(-200, 200):
            x = i / 2
            if not(not(F(a, b, x)) and (F(20, 30, x) or F(35, 60, x))):
                k=k+1

        if k==400:
            mn=min(mn, b-a)

print(mn)

Ответ будет 40.

Второй способ (с помощью рассуждений).

Рассмотрим наоборот, когда логическое выражение выдаёт истину.

ЕГЭ по информатике 2022 - задание 15 (Отрезки 3)

В правой части получается 1, когда x ∈ P или x ∈ Q. Именно в эти моменты выражение ¬(x ∈ A) должно спасать ситуацию и выдавать 0. Тогда без отрицания (x ∈ A) должно выдавать 1. Чтобы покрыть два отрезка, берём A=[20; 60].

Минимальная длина получается 60-20=40.

Ответ: 40

На этом всё! Увидимся в новых уроках по подготовке к ЕГЭ по информатике!

Добрый день! А как в 5 задаче (про числовую прямую) получился ответ 14?
В конце же получается, что A принадлежит [5, 19], то есть длина отрезка 15.

5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 — 15 штук
Или я что-то неправильно понял?

Считается количество единиц, а не сколько целых чисел в этом отрезке.

И в самой последней задаче на закрепление, у вас, видимо, та же ошибка. Не 40, а 41 должно быть?

Как решать 15 задание с «~» тильдой на питоне?
Как например это задание:
На числовой прямой даны два отрезка: P = [7, 14] и Q = [9, 11]. Укажите наибольшую возможную длину промежутка A, для которого формула
((x ∈ P) ~ (x ∈ Q)) → ¬(x ∈ A)

Грамотное объяснение. Безумно здорово, что есть объяснения как на питон (перебором) так и чисто в математической форме, потому что в информатике оба подхода, мне кажется, равносильны. Спасибо

Источник

СДЕЛАЙТЕ СВОИ УРОКИ ЕЩЁ ЭФФЕКТИВНЕЕ, А ЖИЗНЬ СВОБОДНЕЕ

Благодаря готовым учебным материалам для работы в классе и дистанционно

Скидки до 50 % на комплекты
только до

Готовые ключевые этапы урока всегда будут у вас под рукой

Была в сети 24.11.2022 11:28



Подлесных Елена Викторовна

учитель информатики и физики

37 лет

рейтинг1 449
место27 918

30.03.2022 20:49

Нажмите, чтобы узнать подробности

Решение задач с отрезками с помощью программирования на языке Python

Просмотр содержимого документа

«Решение задач c отрезками на Python»

Решение задач ЕГЭ №15 (отрезки) способом программирования на Python (Для составления решений использовались задачи с сайта К.Полякова https://kpolyakov.spb.ru/school/ege.htm)

№4876

№4972

№4973

№4974

№4962

№4545

№4874

№4563

Рекомендуем курсы ПК и ППК для учителей

Похожие файлы

Источник

На уроке рассматривается разбор 15 задания ЕГЭ по информатике, дается подробное объяснение того, как решать подобные задачи

Содержание:

  • Объяснение задания 15 ЕГЭ по информатике
    • Элементы математической логики
    • Математическая логика и теория множеств
    • Задания с отрезками и ДЕЛ
    • Задания с поразрядной конъюнкцией
  • Решение заданий 15 ЕГЭ по информатике
    • Задания с множествами
    • Задания с отрезками на числовой прямой
    • Задания с ДЕЛ
    • Задания с поразрядной конъюнкцией
    • Задания на поиск наибольшего или наименьшего числа А

15-е задание: «Основные законы алгебры логики»

Уровень сложности

— повышенный,

Требуется использование специализированного программного обеспечения

— нет,

Максимальный балл

— 1,

Примерное время выполнения

— 5 минут.

  
Проверяемые элементы содержания: Знание основных понятий и законов математической логики

До ЕГЭ 2021 года — это было задание № 18 ЕГЭ

Типичные ошибки и рекомендации по их предотвращению:

«Важно понимать, что выражение должно быть тождественно истинно, т.е. истинно при любых допустимых значениях переменных x и у, а не только при некоторых наборах значений»

ФГБНУ «Федеральный институт педагогических измерений»

Элементы математической логики

    Для решения 15 задания, потребуется знание таблиц истинности.

    Для выполнения задания рекомендуется повторить следующие темы:

    Преобразование логических операций:

  • операцию импликация можно преобразовать в операции ИЛИ и НЕ:

    • A → B = ¬ A ∨ B
    или
    A → B = A + B

  • операцию эквивалентность можно преобразовать:

    • A ↔ B = A ⊕ B = A ∧ B ∨ A ∧ B
    или
    A ↔ B = A ⊕ B = A · B + A · B

  • операцию XOR (сложение по модулю 2) можно преобразовать так:

    • A ⊕ B = (¬A ∧ B) ∨ (A ∧ ¬B)
    или
    A ⊕ B = (A · B) + (A · B)

    Законы алгебры логики:

  • кроме того, могут пригодиться базовые аксиомы и формулы:
    • Закон двойного отрицания:

    ¬¬ A = A

    Закон исключения третьего:

    A ∧ ¬ A = 0 или A · A = 0
    A ∨ ¬ A = 1 или A + A = 1

    Закон повторения (идемпотентности):

    A ∧ A = A или A · A = A
    A ∨ A = A или A + A = A

    Законы исключения логических констант:

    A ∧ 0 = 0
    A ∧ 1 = A
    A ∨ 0 = A
    A ∨ 1 = 1

    Переместительный (коммутативный) закон:

    A ∧ B = B ∧ A
    A ∨ B = B ∨ A

    Сочетательный (ассоциативный) закон:

    (A ∧ B) ∧ C = A ∧ (B ∧ C)
    (A ∨ B) ∨ С = A ∨ (B ∨ С)

    Распределительный (дистрибутивный) закон:

    (A ∧ B) ∨ C = (A ∨ C) ∧ (B ∨ C)
    (A ∨ B) ∧ С = (A ∧ С) ∨ (B ∧ С)
    и наоборот:
    (A ∨ B) ∧ (A ∨ C) = A ∨ (B ∧ C)
    (A ∧ B) ∨ (A ∧ C) = A ∧ (B ∨ C)

    Закон общей инверсии (Законы де Моргана):

    ¬ (A ∧ B) = ¬ A ∨ ¬ B
    ¬ (A ∨ B) = ¬ A ∧ ¬ B

    Закон исключения (склеивания):

    (A ∧ B) ∨(¬A ∧ B) = B
    (A ∨ B) ∧(¬A ∨ B) = B

    Упрощать выражения можно с помощью формул:
    Закон поглощения:

    A ∨ A ∧ B = A
    A ∧ (A ∨ B) = A
    A ∨ ¬A ∧ B = A ∨ B
    ¬A ∨ A ∧ B = ¬A ∨ B
    A ∧ (¬A ∨ B) = A ∧ B
    ¬A ∧ (A ∨ B) = ¬A ∧ B

  • Порядок выполнения логических операций:
    1. выражения в скобках,
    2. операции «НЕ»,
    3. операции «И»,
    4. операции «ИЛИ»,
    5. операции «импликация»
    6. операции «эквиваленция»
  • последовательность из операций импликации выполняется слева направо (при этом соблюдается принцип «операции с одинаковым приоритетом выполняются слева направо»):

    • A → B → C → D = ((A → B) → C) → D

Математическая логика и теория множеств

  • пересечение множеств соответствует логическому умножению, а объединение – логическому сложению;
  • пересечением двух множеств называется новое множество, состоящее из элементов, принадлежащих одновременно обеим множествам:

    • пересечение множеств
    Пример:
    пример пересечения множеств

  • объединением двух множеств называется новое множество, состоящее из элементов, принадлежащих отдельно каждому из множеств (без повторений);

    • Пример:
    пример объединения множеств

  • пустое множество ∅ – это множество, в котором не содержится ни одного элемента; пустому множеству в теории множеств соответствует 0;
  • универсальное множество U (на кругах Эйлера обозначается в виде прямоугольника) – это множество, содержащее все возможные элементы определенного типа (например, все вещественные числа):

    • универсальное множество

  • универсальное множество соответствует логической единице: для любого множества целых чисел X справедливы равенства:

    • X ∨ U = U и X ∧ U = X

  • разностью двух множеств A и B называется новое множество, элементы которого принадлежат A, но не принадлежат B:

    • разность двух множеств
    Пример разности множеств:
    пример разности множеств

  • дополнение множества X – это разность между универсальным множеством U и множеством X (например, для целых чисел ¬ X – все целые числа, не входящие в X)

    • дополнение множества

  • пусть требуется выбрать множество A так, чтобы выполнялось равенство A ∨ X = I; в этом случае множество A должно включать дополнение ¬ X, то есть A ≥¬ X (или A ⊇¬ X), то есть Amin = ¬ X
  • пусть требуется выбрать множество A так, чтобы выполнялось равенство ¬ A ∨ X = I, в этом случае множество ¬ A должно включать дополнение ¬ X, то есть ¬ A ⊇ ¬ X; отсюда A ⊆ X, то есть Amax = X

Для большей определенности стоит рассмотреть тему круги Эйлера

Задания с отрезками и ДЕЛ

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

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

  1. 1. Если в задании формула тождественно истинна (равна 1), и
    2. после упрощения A без отрицания
    то используется закон:

    Amin = ¬B

    где B — известная часть выражения.

    1. Если в задании формула тождественно истинна (равна 1), и
    2. после упрощения A с отрицанием
    то используется закон:

    Amax = B

    где B — известная часть выражения.

  2. 1. Если в задании формула тождественно ложна (равна 0), и
    2. после упрощения A без отрицания
    то используется закон:

    Amax = ¬B

    где B — известная часть выражения.

    1. Если в задании формула тождественно ложна (равна 0), и
    2. после упрощения A с отрицанием
    то используется закон:

    Amin = B

    где B — известная часть выражения.

Задания с поразрядной конъюнкцией

В задании 15 ЕГЭ встречаются задачи, связанные с поразрядной конъюнкцией.
Например: 

5 & 26

означает поразрядную конъюнкцию (логическое «И») между двоичными значениями двух чисел — 5 и 26. Выполняется так:

5  =   1012 
26 = 110102
0  = 000002

Задания, связанные с поразрядной конъюнкцией, решаются несколькими способами. Рассмотрим один из них.

  • Обозначим:
    • (x & K = 0) как Zk
  • Для решения методом, предложенным А.В. Здвижковой, пригодится использование следующих свойств:

    • Zk * Zm = Zk or m

  • Так, например, если в задании имеем:
    • (X & 5 = 0) ∧ (X & 26 = 0)
  • то сначала введем замену:
    • Z5 ∧ Z26
  • а затем, используя свойство 1, вычислим поразрядную дизъюнкцию двоичного значения чисел 26 и 5:
    • Z5 ∧ Z26 = Z26 or 5
помним, что дизъюнкция - это операция логическое "ИЛИ" (сложение)
5  =   1012 
26 = 110102
31 = 111112
  • таким образом, получили:
    • Z5 ∧ Z26 = Z31

    Zk + Zm = Zk and m

  • Так, например, если в задании имеем:
    • (X & 28 = 0) ∨ (X & 22 = 0)
  • то сначала введем замену:
    • Z28 ∨ Z22
  • а затем, используя свойство 2, вычислим поразрядную конъюнкцию двоичного значения чисел 28 и 22:
    • Z28 ∨ Z22 = Z28 and 22
помним, что конъюнкция - это операция логическое "И" (умножение)
28 = 111002 
22 = 101102
     101002 = 2010
  • таким образом, получили:
    • Z28 ∨ Z22 = Z20

Условие Zk → Zm истинно для любых натуральных значений x тогда и только тогда, когда все единичные биты двоичной записи числа M входят во множество единичных битов двоичной записи числа K.

  • На деле, это означает, что если имеем:
    • X & 29 = 0 → X & 5 = 0  Истинно или Ложно?
  • то сначала введем замену:
    • Z29 → Z5
  • а затем, используя свойство 3, определим истинность высказывания Z29 → Z5:
    • Z29 → Z5 = 1 (истине), тогда, когда:
29 = 111012
5  =   1012  
единичные биты двоичного числа 5 входят в единичные биты двоичного числа 29 
(совпадают с ними)
  • таким образом, получили:
    • Z29 → Z5 = 1 (истинно)

(x & 125 = 5) то же самое, что и
Z120 * ¬Z4 * ¬Z1 = 1 (истине)

  • Так, например, если в задании имеем:
    • X & 130 = 3
  • то сначала введем замену и, используя свойство 4, получим:
    • X & 130 = 3 то же самое, что и
Z127 * ¬Z2 * ¬Z1

т.е. 3 = 2 + 1 :	

2 = 10
1 = 01
3 = 11

Решение заданий 15 ЕГЭ по информатике

Плейлист видеоразборов задания на YouTube:

Задание демонстрационного варианта 2022 года ФИПИ

Задания с множествами

Множества:
 

15_16:

Элементами множества А являются натуральные числа. Известно, что выражение

((x ∈ {1, 3, 5, 7, 9, 11}) → ¬(x ∈ {3, 6, 9, 12})) ∨ (x ∈ A)

истинно (т. е. принимает значение 1) при любом значении переменной х.

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

✍ Решение:

  • Введем обозначения:
    • P ≡ (x ∈ {1, 3, 5, 7, 9, 11}) ; 
Q ≡ (x ∈ {3, 6, 9, 12}) ; 
A ≡ (x ∈ A).
  • Выполним преобразования:
    • (P → ¬Q) ∨ A = 1
Избавимся от импликации:
¬P ∨ ¬Q ∨ A = 1
  • Разделим выражение на две части — известную часть и неизвестную. Чтобы неизвестная часть (А) была непременно истинной, необходимо, чтобы известная часть была ложна:
    • ¬P ∨ ¬Q ∨ А = 1
    0      1
  • То есть получаем:
    • ¬P ∨ ¬Q = 0,
или 
¬P = 0  отсюда P = 1
¬Q = 0 отсюда Q = 1
  • Таким образом имеем пересечение (умножение) двух множеств Q и P. То есть необходимо выбрать элементы, которые встречаются в обоих множествах одновременно:
    • A = {3,9}
  • Сумма элементов:
    • 3 + 9 = 12

Ответ: 12

Аналитическое решение:
📹 YouTube здесь

📹 Видеорешение на RuTube здесь

Множества:

15_17:

Элементами множества А являются натуральные числа. Известно, что выражение

(x ∈ {2, 4, 6, 8, 10, 12}) → (((x ∈ {3, 6, 9, 12, 15}) ∧ ¬(x ∈ A)) → 
→ ¬(x ∈ {2, 4, 6, 8, 10, 12}))

истинно (т. е. принимает значение 1) при любом значении переменной х.

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

Типовые задания для тренировки

✍ Решение:

  • Введем обозначения:
    • P≡(x ∈ {2, 4, 6, 8, 10, 12}) ; 
Q ≡ (x ∈ {3, 6, 9, 12, 15}) ; 
A ≡ (x ∈ A).
  • Выполним преобразования:
    • P → ((Q ∧ ¬A) → ¬P) = 
P → (¬(Q ∧ ¬А) ∨ ¬P) = 
¬P ∨ (¬(Q ∧ ¬А) ∨ ¬P) = 
¬P ∨ ¬Q ∨ А.
  • Разделим выражение на две части — известную часть и неизвестную. Чтобы неизвестная часть (А) была непременно истинной, необходимо, чтобы известная часть была ложна:
    • ¬P ∨ ¬Q ∨ А = 1
    0      1
  • То есть получаем:
    • ¬P ∨ ¬Q = 0,
или 
¬P = 0  отсюда P = 1
¬Q = 0 отсюда Q = 1
  • Таким образом имеем пересечение (умножение) двух множеств Q и P. То есть необходимо выбрать элементы, которые встречаются в обоих множествах одновременно:
    • A = {6,12}
  • Сумма элементов:
    • 6 + 12 = 18

Ответ: 18

Множества:

15_18: Закон распределения

Элементами множеств А, 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 ∈ P) ) ∧ ( (x ∈ Q) → ¬(x ∈ A) )

истинно (т. е. принимает значение 1) при любом значении переменной х.

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

Типовые задания для тренировки

✍ Решение:

  • Введем обозначения:
    • P ≡ (x ∈ P); 
Q ≡ (x ∈ Q); 
A ≡ (x ∈ A).
  • Выполним преобразования:
    • Избавимся от импликации:
(¬A ∨ P) ∧ (¬Q ∨ ¬A) = 1
Применим распределительный закон (но можно вывести самостоятельно):
¬A ∨ (P ∧ ¬Q) = 1
  • Разделим выражение на две части — известную часть и неизвестную. Чтобы неизвестная часть (А) была непременно истинной, необходимо, чтобы известная часть была ложна:
    • ¬A ∨ (P ∧ ¬Q) = 1
 0      1
  • То есть получаем:
    • P ∧ ¬Q = 1,
или 
P = 1  и
¬Q = 1 отсюда Q = 0
  • Таким образом имеем разность двух множеств Q и P. То есть это новое множество, элементы которого принадлежат P, но не принадлежат Q:
    • A = {2, 4, 8, 10, 14, 16, 20}
  • Количество элементов = 7

Ответ: 7

Множества:

15_20:

Элементами множества А являются натуральные числа. Известно, что выражение

¬(x ∈ A) →¬(x ∈ {1, 3, 7}) ∨ (¬(x  ∈ {1, 2, 4, 5, 6}) ∧ (x ∈ {1, 3, 7}))

истинно (т. е. принимает значение 1) при любом значении переменной х.

Определите наименьшее возможное количество элементов множества A.

✍ Решение:

  • Введем обозначения:
    • P ≡ (x ∈ {1, 3, 7}); 
Q ≡ (x  ∈ {1, 2, 4, 5, 6}); 
A ≡ (x ∈ A).
  • Выполним преобразования:
    • Избавимся от импликации:
A ∨ ¬P ∨ (¬Q ∧ P) = 1
Применим закон поглощения (но можно вывести самостоятельно):
A ∨ ¬P ∨ ¬Q = 1
  • Разделим выражение на две части — известную часть и неизвестную. Чтобы неизвестная часть (А) была непременно истинной, необходимо, чтобы известная часть была ложна:
    • A ∨ ¬P ∨ ¬Q = 1
 1      0
  • То есть получаем:
    • ¬P ∨ ¬Q = 0,
или 
P = 1 и Q = 1
  • Таким образом имеем пересечение двух множеств Q и P:
    • A = {1}
  • Количество элементов = 1

Ответ: 1

Задания с отрезками на числовой прямой

Отрезки на числовой прямой:
  

15_3:

На числовой прямой даны два отрезка: P=[44,48] и Q=[23,35].

Укажите наибольшую возможную длину отрезка А, для которого формула

((x ϵ P) → (x ϵ Q)) ∧ (x ϵ A)

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

✍ Решение:

  • Упростим формулу, избавившись от ‘x ϵ‘:
    • (P → Q) ∧ A
  • Теперь преобразуем импликацию в скобках:

    • правило импликации: a → b = ¬a ∨ b

    (¬P ∨ Q) ∧ A
  • Указанные в задании отрезки отобразим на числовой прямой. Разделим отрезки на части по точкам, соответствующим их границам.

    • решение 15 задания егэ по информатике

  • Вернемся к преобразованному выражению. В нем есть известная часть (выделим ее) и неизвестная. По условию выражение должно быть ложно:
    • (¬P ∨ Q) ∧ A = 0
  • Внешняя операция выражения — конъюнкция — ложна в трех случаях и только в одном — истинна:
    • (¬P ∨ Q) ∧ A
    0     ∧ 0 = 0
    0     ∧ 1 = 0
    1     ∧ 0 = 0
    1     ∧ 1 = 1
  • Теперь рассмотрим это выражение относительно наших отрезков на числовой прямой: если известная часть выражения (¬P ∨ Q) на каком-либо отрезке прямой дает истину, то неизвестная часть (A) должна возвращать ложь (по условию формула должна быть тождественно ложна).
  • Рассмотрим все отрезки числовой прямой для известной части выражения:
    • 1. (¬P ∨ Q) = 1 ∨ 0 = 1  - на данном отрезке А должно равняться 0
2. (¬P ∨ Q) = 1 ∨ 1 = 1  - на данном отрезке А должно равняться 0
3. (¬P ∨ Q) = 1 ∨ 0 = 1  - на данном отрезке А должно равняться 0
4. (¬P ∨ Q) = 0 ∨ 0 = 0  - на данном отрезке А может! равняться 1
5. (¬P ∨ Q) = 1 ∨ 0 = 1  - на данном отрезке А должно равняться 0
  • Получаем, что на всех отрезках кроме 4-го выражение ¬P ∨ Q истинно, т.е. на отрезках 1, 2, 3 и 5 неизвестная часть A должна быть ложной (чтобы формула вернула ложь). Отсюда следует, что А может быть истинно только на отрезке 4.
  • Длина отрезка 4 составляет: 
    • 48 - 44 = 4

Результат: 4
✎ Решение 2 (программирование):
Внимание! этот способ подходит НЕ для всех заданий с отрезками!
Python:

1
2
3
4
5
6
7
8
9

def f(a1,a2,x):
    return((44<=x<=48)<=(23<=x<=35))and(a1<=x<=a2)
maxim = 0
for a1 in range (1,200):
    for a2 in range (a1+1,200):
        if all(f(a1,a2,x)==0 for x in range (1,200)):# если все ложны
            if a2-a1>maxim:
                maxim=a2-a1
                print(a1,a2, a2-a1) # сами точки отрезка и длина

Вывод:

44 45 1
44 46 2
44 47 3
44 48 4

PascalABC.net:

Вывод:





С подробным аналитическим решением задания 15 ЕГЭ по информатике можно ознакомиться по видео:


📹 YouTube здесь

📹 Видеорешение на RuTube здесь


Отрезки на числовой прямой:

  




15_9: 



На числовой прямой даны два отрезка: P = [10,20] и Q = [30,40].



  

Укажите наибольшую возможную длину отрезка A, для которого формула 


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


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


Типовые задания для тренировки





✍ Решение:




    

  • Упростим выражение, введя обозначения:
    • 

    A: x ∈ A
P: x ∈ P
Q: x ∈ Q

    

  • Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно истинной:
    • 

    (P → Q) → ¬A = 1

    

  • Избавимся от импликации:
    • 

    (P → Q) → ¬A = 1        =>
¬(P → Q) ∨ ¬A = 1       =>
¬(¬P ∨ Q) ∨ ¬A = 1   

    

  • Используем закон Де Моргана для последующего преобразования:
    • 

    ¬(¬P ∨ Q) ∨ ¬A = 1    =>
P ∧ ¬Q ∨ ¬A = 1

    

  • А — наше неизвестное, а выделенную часть формулы можно найти. Необходимо, чтобы А = 1. Значит, предположим, что ¬А = 0, тогда P ∧ ¬Q = 1 (если P ∧ ¬Q = 0, то ¬А может равняться и 0 и 1, так как имеет место операция логического сложения ∨)
    • 

  • Значит, имеем P ∧ ¬Q = 1. Кроме того, в данном случае имеет место операция конъюнкция, которую проще вычислить, если выражение равно 1 (так как для конъюнкции существует один единственный случай истинности: 1 & 1 = 1). Таким образом имеем утверждения:
    • 

    А = 1
P = 1
¬Q = 1 или Q = 0

    

  • Т.е. A истинно (=1) на промежутке пересечения отрезков P и ¬Q.
    • 

  • Отобразим отрезки на числовой прямой, чтобы найти искомое значение:
    • 

    решение 15 задания ЕГЭ с числовой приямой
    

  • Очевидно, что А будет истинно, только в части 2 (на рис. желтым цветом), то есть соответствовать отрезку [10,20], имеющему длину 10.
    • 



Результат:  10






Отрезки на числовой прямой:




15_10: 



На числовой прямой даны два отрезка: P = [3, 20] и Q = [6, 12].



  

Укажите наибольшую возможную длину отрезка A, для которого формула


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


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





✍ Решение:




    

  • Упростим выражение, введя обозначения:
    • 

    A: x ∈ A
P: x ∈ P
Q: x ∈ Q

    

  • Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно истинной:
    • 

    (P ~ Q) → ¬A = 1

    

  • Избавимся от импликации:
    • 

    (P ~ Q) → ¬A = 1      =>
¬(P ~ Q) ∨ ¬A = 1

    

    

    Далее возможно 2 способа решения.
    

    ✎ 1 способ:
    

  • Избавимся от эквивалентности по правилу преобразования эквивалентности:
    • 

    (a ~ b) = a * b + ¬a * ¬b
    

    ¬(P ~ Q) = ¬((P ∧ Q) ∨ (¬P ∧ ¬Q)) =
= ¬(P ∧ Q) ∧ ¬(¬P ∧ ¬Q) 

    

  • Преобразуем часть данного выражения по закону Де Моргана:
    • 

    ¬(P ∧ Q) ∧ ¬(¬P ∧ ¬Q) =
= ¬(P ∧ Q) ∧ (P ∨ Q) 

    

  • В итоге получим:
    • 

    ¬(P ∧ Q) ∧ (P ∨ Q) ∨ ¬A = 1
    

  • А — наше неизвестное, а выделенную часть выражения можно найти. Необходимо, чтобы А = 1. Значит, предположим, что ¬А = 0, тогда, чтобы общее выражение было истинным (по условию), нужно чтобы ¬(P ∧ Q) ∧ (P ∨ Q) = 1.
    • 

  • Имеем:
    • 

    ¬(P ∧ Q) ∧ (P ∨ Q) = 1
А = 1

    

  • Отобразим отрезки на числовой прямой, чтобы найти искомое значение:
    • 

    15 задание  ЕГЭ отрезки
    

  • Очевидно, что А будет истинно в двух отмеченных на рисунке частях: 2 и 4 (на рис. желтым цветом). Но по условию нам необходимо найти А наибольшей длины,  соответственно, выбираем отрезок [12,20], имеющий длину 8.
    • 

    ✎ 2 способ:
    
После того, как мы избавились от импликации, имеем:
    

    ¬(P ~ Q) ∨ ¬A = 1

    

  • А — наше неизвестное, а выделенную часть выражения можно найти. Необходимо, чтобы А = 1. Значит, предположим, что ¬А = 0, тогда ¬(P ~ Q) = 1 (чтобы общее выражение было истинным, как указанно в условии).
    • 

  • Иными словами ¬(P ~ Q) истинно для всех значений x, при которых P не равно Q (т.е. либо P = 1 и Q = 0, либо P = 0 и Q = 1).
    • 

  • Это соответствует двум отрезкам (см. рисунок выше, желтым цветом): [3,6] и [12,20]. Но по условию нам необходимо найти А наибольшей длины,  соответственно выбираем отрезок [12,20], имеющий длину 8.
    • 



Результат:  8





С решением задания 15 вы также можете ознакомиться, посмотрев видео (аналитическое решение):


📹 YouTube здесь

📹 Видеорешение на RuTube здесь


Отрезки на числовой прямой:




15_11: 



На числовой прямой даны два отрезка: P = [11, 21] и Q = [15, 40].



  

Укажите наибольшую возможную длину отрезка A, для которого формула 


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


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


Типовые задания для тренировки





✍ Решение:




    

  • Упростим выражение, введя обозначения:
    • 

    A: x ∈ A
P: x ∈ P
Q: x ∈ Q

    

  • Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно истинной:
    • 

    A → ¬(P ~ Q) = 1

    

  • Избавимся от импликации:
    • 

    A → ¬(P ~ Q) = 1    =>
¬A ∨ ¬(P ~ Q) = 1

    

  • А — наше неизвестное, тогда как выделенную часть формулы можно найти. Введем предположение, что А = 1. Значит, ¬А = 0 (т.е. А = 1), тогда ¬(P ~ Q) = 1 (так как общая формула должна быть истинной по условию).
    • 

  • Иными словами ¬(P ~ Q) истинно для всех значений x, при которых P не равно Q (т.е. либо P = 1 и Q = 0, либо P = 0 и Q = 1).
    • 

  • Отобразим отрезки на числовой прямой, чтобы найти искомое значение:
    • 

    15 задание отрезки на числовой прямой
    

  • Получаем, что А соответствует двум отрезкам (см. рисунок, желтым цветом): [11,15] и [21,40]. Но по условию нам необходимо найти А наибольшей длины,  соответственно выбираем отрезок [21,40], имеющий длину 19.
    • 



Результат:  19





Задания с ДЕЛ


Поиск наибольшего А, известная часть Дел ∨ Дел = 1




15_7:


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


  

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


  (ДЕЛ(x, 40) ∨ ДЕЛ(x, 64))  → ДЕЛ(x, A) 


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


Типовые задания для тренировки





✍ Решение:



✎ Решение 1 (теоретическое):


    

  • Введем обозначения:
    • 

    A = ДЕЛ(x,A); 
D40 = ДЕЛ(x, 40); 
D64 = ДЕЛ(x, 64)

    

  • Перепишем исходную формулу, согласно введенным обозначениям. Укажем, что формула должна быть тождественно истинна (по условию):
    • 

    (D40 ∨ D64)  → A = 1

    

  • Избавимся от импликации:
    • 

    ¬(D40 ∨ D64) ∨ A = 1
или
(¬D40 ∧ ¬D64) ∨ A = 1

    

  • Разделим данную формулу на две части: в одной из них — искомое A, а в другой — часть формулы с x, которую можно найти:
    • 

    (¬D40 ∧ ¬D64) ∨ A = 1
      1          2

    

  • В полученной формуле необходимо, чтобы искомая часть с A в конечном счете было истинно.

    Т.е. (¬D40 ∧ ¬D64) должно быть = 0. Это нам ничего не дает, т.к. конъюнкция ложна в трех случаях (1*0, 0*1 и 0*0), т.е. D40 и D64 могут быть равны как 0, так и 1 (исключение составляет лишь вариант, когда оба D истинны, тогда логическое умножение 1 * 1 ≠ 0).
    

    • 

  • Преобразуем выражение первой части формулы по закону Де Моргана (чтобы оно равнялось 1):
    • 

    ¬D40 ∧ ¬D64 = 0
или
¬(¬D40 ∧ ¬D64) = 1

Преобразуем по закону Де Моргана и получим:
D40 ∨ D64 = 1

    

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

    Решение с помощью логических рассуждений:
    

  • Найдем все такие x, которые делятся на А и при этом делятся на 40 ИЛИ делятся на 64:
    • 

    x/A : x/40 ∨ x/64
    

    x = 40, 64, 80, 120, 128, 160, 192, 200, ...
    

  • Теперь найдем такие A, начиная с самого наименьшего (единицы), на которые делятся все x без исключения:
    • 

    А = 1, 2, 4, 8
    

  • Наибольшее А равно 8.
    • 

  • Или то же самое можно найти поиском наибольшего общего делителя чисел 40 и 64 (используем формулу Евклида):
    • 

    НОД (40,64) = 8 
40,64  (64 - 40 = 24)
40,24  (40 - 24 = 16)
24,16  (24 - 16 = 8)
16,8   (16 - 8 = 8)
8,8

    

    Решение с помощью кругов Эйлера:
    

  • В этом случае логическое сложение тоже дает истину в трех случаях (1+1, 1+0, 0+1). Т.е. мы не сможем найти А с помощью функции ДЕЛ. Необходимо прибегнуть к решению с помощью кругов Эйлера.
    • 

  • В множество A должны входить все числа, которые попадают в объединение D40 + D64. Таким образом, нужно найти множество, в которое входят оба этих множества.
    • 

  • Найдем наибольший общий делитель чисел 40 и 64; это число 8:
    • 

    64 / 40 = 1 (24 остаток)
40 / 24 = 1 (16 остаток)
24 / 16 = 1 (8 остаток)
16 / 8 = 2 (0 остаток) - НОД = 8
+++
40 / 8 = 5
64 / 8 = 8

    

  • Т.е. можно сказать, что A = D40 + D64 = D8*D5 + D8*D8 = D8*(D5 + D8). D8 входит в каждое из множеств D40 и D64. Объединение D40 + D64 тоже входит в D8:
    • 

    2
    

  • 8 — наибольший общий делитель числе 40 и 64, значит, оно соответствует максимальному значению A.
    • 



Результат:  8


✎ Решение 2 (программирование):

Python:










1
2
3
4
5
6





for A in range(1,500):
    OK = 1
    for x in range(1,1000):
        OK *= ((x % 40 == 0) or (x % 64 == 0))<=(x % A== 0)
    if OK:
        print( A )










Вывод:


1
2
4
8



PascalABC.net:










1
2
3
4
5
6
7
8
9
10
11
12
13
14
15





begin
  for var A := 1 to 500 do
  begin
    var ok := 1;
    for var x := 1 to 1000 do
    begin
      if (((x mod 40 = 0) or (x mod 64 = 0)) <= (x mod A = 0)) = false then
      begin
        ok := 0; 
        break;
      end;
    end;
    if (ok = 1) then print(A)
  end;
end.










Вывод:


1
2
4
8



Результат:  8





Поиск наименьшего А, известная часть Дел ∧ ¬Дел = 1




15_5:


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


  

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


ДЕЛ(x, A) → (¬ДЕЛ(x, 28) ∨ ДЕЛ(x, 42))


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


Типовые задания для тренировки





✍ Решение:



✎ Решение 1 (теоретическое):


    

    Имеем:
    

    ДЕЛ(x, A) → (¬ДЕЛ(x, 28) ∨ ДЕЛ(x, 42)) = 1 
    

  • Введем обозначения:
    • 

    A = ДЕЛ(x,A); 
D28 = ДЕЛ(x, 28); 
D42 = ДЕЛ(x, 42)

    

  • Перепишем исходную формулу, согласно введенным обозначениям. Укажем, что формула должна быть тождественно истинна (по условию):
    • 

    A → (¬D28 ∨ D42) = 1

    

    Избавимся от импликации:
    

    ¬A ∨ (¬D28 ∨ D42) = 1

    

  • Разделим данную формулу на две части: в одной из них — искомое A, а в другой — часть формулы с x, которую можно найти:
    • 

    ¬A ∨ (¬D28 ∨ D42) = 1
 1        2

    

  • В части 2 полученной формулы находится операция дизъюнкция, которую проще найти, когда логическое выражение равно 0 (только один случай: 0 ∨ 0 = 0):
    • 

    (¬D28 ∨ D42) = 0   один случай: когда ¬D28 = 0 и D42 = 0
    

  • Т.е. имеем: 
    • 

    x/¬A : x/28 ∧ x/¬42
    

  • Иными словами найдем все такие x, которые НЕ делятся на А и при этом делятся на 28 И НЕ делятся на 42:
    • 

    x = 28, 56, 84, 112, 140, 168, 196, 224, ...
    

  • Теперь найдем такие A, начиная с самого наименьшего (единицы), на которые НЕ делятся все x без исключения:
    • 

    А = 1, 2, 3
    

  • Наименьшее А равно 3.
    • 



✎ Решение 2 (программирование). Язык Python, Pascal:


    
Из общего выражения:
    

    ДЕЛ(x, A) → (¬ДЕЛ(x, 28) ∨ ДЕЛ(x, 42)) = 1 
    

  • Можно сделать вывод, что для некоторого диапазона натуральных значений А, необходимо рассмотреть диапазон натуральных значений x. Если выражение будет истинным для диапазона всех рассматриваемых х, то такое А необходимо вывести на экран.
    • 

  • То есть следует рассмотреть вложенный цикл: для внешнего цикла, перебирающего значения А (ограничим их числом 50, т.к. необходимо найти наименьшее А), будем запускать внутренний цикл, перебирающий значения х (х ограничим числом 1000, будем рассматривать данный диапазон, как «любое натуральное значение переменной х»).
    • 

  • Во внутреннем цикле расположим формулу:
    • 

    Python:
    

    

    for A in range(1,50):
    OK = 1
    for x in range(1,1000):
        OK *= (x % A == 0) <= ((x % 28 != 0) or (x % 42== 0))
    if OK:
        print( A )
        break
    

    

    PascalABC.net:
    

    

    begin
  for var A := 1 to 50 do
  begin
    var ok := 1;
    for var x := 1 to 1000 do
    begin
      if (x mod A = 0) <= ((x mod 28 <> 0)or (x mod 42 = 0)) = false then
      begin
        ok := 0; 
        break;
      end;
    end;
    if (ok = 1) then begin
      print(A);
      break;
      end
  end;
end.
    

    

    

    OK — переменная-индикатор: если находится такое А при котором, диапазон всех значений x, подставленных в выражение, возвращает истинное значение выражения, то ОК остается равным 1, т.к. используется операция умножения (до цикла ОК необходимо присвоить единице).
    
Следует иметь в виду, что в программировании вместо операции импликация (->) можно использовать нестрогое неравенство: <=. Т.к. таблица истинности для операции импликация соответствует операции <=:
    

    a b   F(a<=b)
0 0      1
0 1      1
1 0      0
1 1      1  

    

    

  • После запуска программы выдается наименьшее значение А, т.к. используется оператор break для выхода из цикла после первого найденного значения:
    • 

    3

    



Результат:  3







15_6:


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


  

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


 (¬ДЕЛ(x, 19) ∨ ¬ДЕЛ(x, 15)) → ¬ДЕЛ(x, A) 


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





✍ Решение:



✎ Решение 1 (Путём рассуждений):


    

  • Введем обозначения:
    • 

    A = ДЕЛ(x,A); 
D19 = ДЕЛ(x, 19); 
D15 = ДЕЛ(x, 15)

    

  • Перепишем исходную формулу, согласно введенным обозначениям. Укажем, что формула должна быть тождественно истинна (по условию):
    • 

    (¬D19 ∨ ¬D15) → ¬A = 1

    

  • Избавимся от импликации:
    • 

    D19 ∧ D15 ∨ ¬A = 1

    

  • Разделим данную формулу на две части: в одной из них — искомое A, а в другой — часть формулы с x, которую можно найти:
    • 

    ¬A ∨ D19 ∧ D15 = 1
 1       2

    

  • Начнем с известной части — части 2 формулы. В ней находится операция конъюнкция, которую проще найти, когда все ее операнды равны 1 (единственный случай для конъюнкции: 1 ∧ 1 = 1).
    • 

  • Вторая часть общей формулы может равняться только 1, когда ¬A = 0 (если ¬A = 1, то вторая часть может равнять 0, а нам нужно 1) :
    • 

    ¬A ∨ D19 ∧ D15 = 1
 0  ∨     1      = 1

    

  • Т.е. получаем:
    • 

    ¬A = 0 при D19 ∧ D15 = 1
или
A = 1 при D19 = 1 и D15 = 1

    

  • Таким образом, имеем:
    • 

    A = 1
D19 = 1
D15 = 1

    

  • Очевидно, что наименьшим x можем взять число 285 (15 * 19 = 285): ДЕЛ(285, 19) и ДЕЛ(285, 15)
    • 

  • Поскольку мы ищем наименьшее A, такое что: ДЕЛ(x, A) и при этом ДЕЛ(x, 19) и ДЕЛ(x, 15), то нам необходимо найти наименьшее делимое чисел 19 и 15:
    • 

    19 * 2 = 38 (38 не делится на 15)
19 * 3 = 57 (57 не делится на 15)
19 * 4 = 76 (76 не делится на 15)
19 * 5 = 95 (95 не делится на 15)
...
19 * 10 = 190 (190 не делится на 15)
19 * 15 = 285 (285 делится на 15)

    

  • A должно быть таким числом, при котором x принимает единственно возможное (наименьшее) значение 285.
    • 

  • Таким наименьшим A является само число 285.
    • 



✎ Решение 2 (программирование). Язык Python:


    
Из общего выражения:
    

     (¬ДЕЛ(x, 19) ∨ ¬ДЕЛ(x, 15)) → ¬ДЕЛ(x, A)  = 1
    

  • Можно сделать вывод, что для некоторого диапазона натуральных значений А, необходимо рассмотреть диапазон натуральных значений x. Если выражение будет истинным для диапазона всех рассматриваемых х, то такое А необходимо вывести на экран.
    • 

  • То есть следует рассмотреть вложенный цикл: для внешнего цикла, перебирающего значения А (ограничим их числом 500, т.к. необходимо найти наименьшее А), будем запускать внутренний цикл, перебирающий значения х (х ограничим числом 1000, будем рассматривать данный диапазон, как «любое натуральное значение переменной х»).
    • 

  • Во внутреннем цикле расположим формулу:
    • 

    

    for A in range(1,500):
    OK = 1
    for x in range(1,1000):
        OK *= ((x % 19 != 0) or (x % 15 != 0))<= (x % A!= 0)
    if OK:
            print( A )
    

    

    

    OK — переменная-индикатор: если находится такое А при котором, диапазон всех значений x, подставленных в выражение, возвращает истинное значение выражения, то ОК остается равным 1, т.к. используется операция умножения (до цикла ОК необходимо присвоить единице).
    
Следует иметь в виду, что в программировании вместо операции импликация (->) можно использовать нестрогое неравенство: <=. Т.к. таблица истинности для операции импликация соответствует операции <=:
    

    a b   F(a<=b)
0 0      1
0 1      1
1 0      0
1 1      1  

    

    

  • После запуска программы выдается одно значение А:
    • 

    285

    



Результат:  285





Задания с поразрядной конъюнкцией



Поразрядная конъюнкция:

 




15_1:


Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 12&6 = 11002&01102 = 01002 = 4


  

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


(X & A = 0) ∧ ¬(X & 35 ≠ 0 → X & 52 ≠ 0)


тождественно ложна (то есть принимает значение 0 при любом неотрицательном значении переменной X)?




✍ Решение:





Стоит заметить, что для такого типа задач, нет универсального единственного решения. Поэтому на видео, расположенном ниже, представлено два варианта решения.

 ✎ Способ 1:


Рассмотрим один из вариантов решения:


    

  • Удалим из формулы X&, чтобы сократить ее запись:
    • 

    (A = 0) ∧ ¬(35 ≠ 0 → 52 ≠ 0)

    

  • Обратим внимание, что внешней операцией является конъюнкция — логическое умножение:
    • 

    (A = 0) ∧ ¬(35 ≠ 0 → 52 ≠ 0)

    

  • Разделим общее выражение на две части относительно внешней операции. Первая часть — неизвестная, искомая, а вторая — известная, ее можно вычислить:
    • 

    (A = 0) ∧ ¬(35 ≠ 0 → 52 ≠ 0)
   1               2

    

  • Выполним некоторые преобразования во второй части формулы:
    • 

  • Зная свойство импликации, преобразуем формулу (избавимся от импликации в скобках):
    • 

    

    правило импликации: a → b = ¬a ∨ b
    

    

    (A = 0) ∧ ¬(35 = 0 ∨ 52 ≠ 0)
т.к. в результате получается отрицание того, что 35 ≠ 0, 
то убираем знак "не равно": было 35 ≠ 0, стало 35 = 0

    

  • Избавимся от отрицания перед скобками по закону Де Моргана:
    • 

    

    закон де Моргана: ¬ (A ∨ B) = ¬ A ∧ ¬ B
    

    

    A = 0 ∧ 35 ≠ 0 ∧ 52 = 0 = 0
    

  • По условию формула должна быть ложной. Вспомним таблицу истинности для конъюнкции (внешняя операция в нашей общей формуле):
    • 

    0 ∧ 0 = 0
0 ∧ 1 = 0
1 ∧ 0 = 0
1 ∧ 1 = 1

    

  • Вторая часть формулы — вычислима, поэтому начнем с нее. В ней находится операция конъюнкция, которая имеет один единственный вариант решения, когда ¬ A ∧ ¬ B = 1. То есть примем вторую часть за истину (=1). В таком случае, для того чтобы общее выражение стало ложным (так требуется по заданию), необходимо, чтобы утверждение, что A = 0 было ложным (т.к. в обратном случае получим: 1 ∧ 1 = 1):
    • 

    (A = 0) ∧ 35 ≠ 0 ∧ 52 = 0 = 0
   0    ∧        1    = 0 

    

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

    35 ≠ 0 ∧ 52 = 0 = истинно (=1)  если:
35 ≠ 0 = истинно (=1)
и
52 = 0 = истинно (=1)

так как стоит логическое умножение ∧ - 
смотрим выше таблицу истинности для конъюнкции

    

  • Из двух последних пунктов получаем три утверждения:
    • 

    35 ≠ 0  = 1  (истина)
и
52 = 0  = 1  (истина)
и
A = 0   = 0  (ложь)

    

  • Переведем числа в двоичную систему счисления:
    • 

    35: 100011  (≠ 0)
52: 110100 (= 0)

    

  • Найдем такой X, который при поразрядной конъюнкции даст истинное значение для обеих частей. 
    • 

  • Для начала рассмотрим ситуацию с числом 52 — это проще, т.к. для получения в результате нуля (52 = 0 => истина), достаточно во всех разрядах «перекрыть» единицы нулями:
    • 

    


    
52
1
1
0
1
0
0

    

    
X
0
0
?
0
?
?

    
    

    

  • Мы «перекрыли» все единицы нулями, чтобы в результате получить 0.
    • 

  • Теперь рассмотрим 35 ≠ 0  = истина (1):
    • 

    


    
35
1
0
0
0
1
1

    

    
X
1
?
?
?
1
1

    
    

    

  • Объединим обе маски в одну: 
    • 

    0 0 ? 0 ? ?  &
1 ? ? ? 1 1
0 0 ? 0 1 1

    

  • Так как выражение X & A = 0 должно быть ложным, то найдем такое наименьшее А, при котором X & A ≠ 0. Для этого в тех разрядах Х, в которых находится единица, необходимо сохранить эту единицу и в соответствующих разрядах А:
    • 

    


    
X
0
0
?
0
1
1

    

    
A
0
0
0
0
1
1

    
    

    

  • Переведем результат в десятичную систему счисления:
    • 

    0000112 = 310
    



Ответ: 3 


✎ Способ 2*:


    
Используем метод А.В. Здвижковой.
    

  • Выполним последовательно следующие пункты:
    • 

      

    1. Произвести замену (x & K = 0) на Zk
      2. 

    2. Выполнить преобразования по свойству импликации и закону Де Моргана.
      3. 

    3. Стремиться прийти к выражению с конъюнкциями без отрицаний типа: Zk * Zm. 
      4. 

    4. Все выражения типа Zk * Zm  преобразовать по свойству 
      Zk * Zm = Zk or m.
      5. 

    5. Путем преобразований прийти к импликации: Zk → Zm.
      6. 

    

  • Согласно первому пункту производим замену:
    • 

    A ∧ ¬(¬Z35 → ¬Z52) = 0

    

  • Введем отрицание в выражение, чтобы оно было истинным:
    • 

    ¬(A ∧ ¬(¬Z35 → ¬Z52)) = 1

    

  • По закону де Моргана:
    • 

    ¬A ∨ (¬Z35 → ¬Z52) = 1

    

  • По свойству импликации:
    • 

    ¬A ∨ (Z35 ∨ ¬Z52) = 1

    

  • Объединим слагаемые с отрицанием:
    • 

    ¬A ∨ ¬Z52 ∨ Z35 = 1

    

  • Чтобы прийти к конъюнкции (пункт 3), используем закон де Моргана:
    • 

    ¬(A ∧ Z52) ∨ Z35 = 1

    

  • Чтобы прийти к импликации (пункт 5), используем свойство импликации:
    • 

    (A ∧ Z52) → Z35 = 1

    

  • Получаем:
    • 

    ZA ∨ 52 → Z35 = 1

    

  • Вспомним свойство: 
    • 

    Условие Zk → Zm истинно для любых натуральных значений x тогда и только тогда, когда все единичные биты двоичной записи числа M входят во множество единичных битов двоичной записи числа K.
    

  • В нашем случае это говорит о том, что все единичные биты двоичной записи числа 35 должны входить в результат ZA or 52.
    • 

  • Рассмотрим подробно:
    • 

    A       = ??0?11
52      = 110100
A or 52 = 110111
35      = 100011
 
    

  • поскольку мы ищем наименьшее А, то:
    • 

    Аmin = 112 = 310
    



Результат: 3





Детальный разбор данного задания 15 ЕГЭ по информатике предлагаем посмотреть на видео:


Вариант решения №1 (универсальный, теоретический):

📹 YouTube здесь

📹 Видеорешение на RuTube здесь


Вариант решения №2 (не универсальный, но простой):

📹 YouTube здесь



Поразрядная конъюнкция:

  




15_2: 


Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 12&6 = 11002&01102 = 01002 = 4 


  

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


X & A ≠ 0 → (X & 36 = 0 → X & 6 ≠ 0)


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





✍ Решение:




    
✎ Способ 1:
    

  • Произведем замену:
    • 

    z36 = (x&36 = 0), z6 = (x&6 = 0), A = (x&A = 0)

    

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

    ¬A → (z36 → ¬ z6)

    

  • Избавимся от импликации (A → B = ¬ A ∨ B):
    • 

  • Сначала по правилу преобразования импликации:
    • 

    ¬A → (z36 → ¬ z6) = A + ¬z36 + ¬z6 

    

  • По Закону де Моргана вынесем отрицание за скобки (¬ (A ∧ B) = ¬ A ∨ ¬ B):
    • 

    A + ¬z36 + ¬z6 = A + ¬(z36 * z6)

    

  • Вернемся опять к импликации:
    • 

    A + ¬(z36 * z6) = ¬(z36 * z6) + A = (z36 * z6) → A

    

  • Суть предыдущих действий в том, что нам необходимо прийти к импликации, но, избавившись от отрицания.
    • 

  • По следующему правилу ZK * ZM = ZK or M (К. Поляков) заменим конъюнкцию:
    • 

    z36 * z6 = z36 or 6
    

  • Выполним поразрядную дизъюнкцию двоичных чисел 36 и 6:
    • 

    1001002 -> 36
1102 -> 6

100100
   110
1001102 -> 36 or 6 = 3810

    

  • Получаем:
    • 

    z38 → A

    

  • Необходимо обеспечить истинность данного выражения при всех x. Это возможно, когда единичные биты A входят в единичные биты числа 38. То есть:
    • 

    A = 1001102 = 3810
    

      
    
✎ Способ 2:
    

  • Так как по заданию формула должна быть тождественно истинна, то перепишем ее так:
    • 

    x&A ≠ 0 → (x&36 = 0 → x&6 ≠ 0) = 1
    

  • Введем обозначения:
    • 

    A = (x&A = 0);
P = (x&36 = 0);
Q = (x&6 = 0);

    

  • Перепишем выражение согласно введенным обозначениям:
    • 

    ¬A → (P → ¬Q) = 1

    

  • Избавимся от импликации:
    • 

    A ∨ (¬P ∨ ¬Q) = 1

    

  • A — наше неизвестное; для части выражения ¬P ∨ ¬Q нам необходимо подобрать такой вариант (равный 0 или 1), при котором единственно возможным значением A была бы единица (1). 
    • 

  • Возьмем (¬P ∨ ¬Q) = 0, тогда А должно быть только единицей (чтобы общее выражение было = 1):
    • 

    A ∨ (¬P ∨ ¬Q) = 1; 
или 
1 ∨ (0) = 1

    

  • Иными словами, выражение истинно, если при ¬P ∨ ¬Q = 0, A равно единице (1).
    • 

  • Получаем:
    • 

    ¬P ∨ ¬Q = 0
Отсюда имеем: 
¬P = 0 и ¬Q = 0 

(дизъюнкция равна 0 в единственном случае, когда все операнды равны 0)

    

  • Или запишем другим образом:
    • 

    Q = 1 и P = 1
    

  • Построим побитовые маски:
    • 

    100100  : 36
000110  : 6
0**0**  : маска P (x&36 = 0)
***00*  : маска Q (x&6 = 0)

    

  • Сопоставим обе маски и маску x&A = 0:
    • 

    0**0**  : маска P (x&36 = 0)
***00*  : маска Q (x&6 = 0)
0**00*  : общая маска x
*00**0  : маска для A (x&A = 0)
т.е. в тех битах А, где может получиться единица (звездочки в обеих масках),
     мы поставили нули.

    

  • Так как нам необходимо получить наибольшее A (по заданию), то вместо всех «звездочек» ставим единицы:
    • 

    100110 = 3810

    



Результат: 38





Подробное решение данного задания 15 ЕГЭ по информатике предлагаем посмотреть в видео уроке:

Способ 1:

📹 YouTube здесь

  📹 Видеорешение на RuTube здесь

Способ 2:

📹 YouTube здесь

📹 Видеорешение на RuTube здесь


Поразрядная конъюнкция:

  




15_8:


Определите наименьшее натуральное число А из интервала [43, 55], такое, что выражение 


((x & 17 ≠ 0) → ((x & A ≠ 0) → (x & 58 ≠ 0))) →
→ ((x & 8 = 0) ∧ (x & A ≠ 0) ∧ (x & 58 = 0))


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


Типовые задания для тренировки





✍ Решение:




    
Кратко изложенное решение *:
    

  • Введем обозначения:
    • 

    (¬Z17 → (¬A → ¬Z58)) → (z8 ∧ ¬A ∧ Z58) = 0

    

  • Для того, чтобы выражение было истинным, поставим его с отрицанием:
    • 

    ¬(((¬Z17 → (¬A → ¬Z58)) → (z8 ∧ ¬A ∧ Z58)) = 1
 
    

  • Упростим выделенную часть выражения (свойство 1, теория):
    • 

    Z8 ∧ Z58 = Z8 or 58  :

8  =   1000  or
58 = 111010
     111010 = 58

    

  • Получили:
    • 

    Z8 ∧ Z58 = Z58
 
    

  • Перепишем все выражение снова, избавившись от импликации:
    • 

    ¬(¬(Z17 ∨ A ∨ ¬Z58) ∨ (¬A ∧ Z58)) = 1
 
    

  • По закону Де Моргана получим:
    • 

    (Z17 ∨ A ∨ ¬Z58) ∧ ¬(¬A ∧ Z58)) = 1
 
    

  • Еще раз применим закон теперь ко второй скобке:
    • 

    (Z17 ∨ A ∨ ¬Z58) ∧  (A ∨ ¬Z58) = 1

    

  • Используем закон поглощения:
    • 

    A ∨ ¬Z58 = 1

    

  • Приведем к импликации, чтобы избавиться от отрицания:
    • 

    ¬Z58 ∨ A => 
 Z58 → A = 1

    

  • Поскольку по заданию нас интересует диапазон [43;55], то проверять будет с числа 43.
    • 

  • По свойству 3 (теория), необходимо, чтобы единичные биты А входили в единичные биты двоичного представления числа 58:
    • 

    43 = 101011 - не подходит!
58 = 111010

44 = 101100 - не подходит!
58 = 111010

45 = 101101 - не подходит!
58 = 111010

46 = 101110 - не подходит!
58 = 111010

47 = 101111 - не подходит!
58 = 111010

48 = 110000 - подходит!
58 = 111010

    



Результат:  48






Поразрядная конъюнкция:

  




15_15:


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


((x & 26 = 0) ∨  (x & 13 = 0)) → ((x & 78 ≠ 0) → (x & A = 0))


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


Типовые задания для тренировки:





✍ Решение:




    

  • Для упрощения восприятия введем обозначения:
    • 

    z26 = (x & 26 = 0)
z13 = (x & 13 = 0)
z78 = (x & 78 = 0)
A = (x & A = 0)

    

  • Таким образом, получим следующее выражение:
    • 

    (z26 ∨ z13) → (¬z78 → A) = 1

    

  • Упростим выражение по свойству импликации для второй скобки:
    • 

    (z26 ∨ z13) → (z78 ∨ A) = 1

    

  • Упростим левую часть, используя свойство 2 (Zk + Zm = Zk and m):
    • 

    26 : 11010   единичные биты: 4, 3, 1
13 :  1101   единичные биты: 3, 2, 0
∧ =------------------------
     01000 = 810

    

  • То есть получили z26 ∨ z13 = z8
    • 

  • По правилу импликации: все единичные биты двоичной записи результата (z78 ∨ A) должны входить во множество единичных битов двоичной записи z8.
    • 

  • Рассмотрим:
    • 

    z8 → (z78 ∨ A)
z78: не влияет на решение, так как операция дизъюнкция истинна тогда, 
когда хотя бы один операнд истинен
z8 → A     : ????

    

  • Для А единичными битами должны быть общие единичные биты для z8 (10002). Т.е. в нашим случае — это один бит — 3-й:
    • 

    Наибольшее А = 1000 = 810

    



Результат:  8





Задания на поиск наибольшего или наименьшего числа А



Поиск наибольшего или наименьшего числа А:

  




15_4: 15 задание. Демоверсия ЕГЭ 2018 информатика:


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

демоверсия егэ 2018 решение 15 (18) задания

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





✍ Решение:





✎ Способ 1 (программный):


Важно: Поскольку используется метод полного перебора, то возможна ситуация, когда транслятор будет работать слишком медленно. Но работоспособность представленного алгоритма проверена на онлайн компиляторах.


Pascalabc.net:










1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18





begin
  for var A := 200 downto -100 do
  begin
    var OK := 1;
    for var x := 0 to 100 do
      for var y := 0 to 100 do
        if ((x <= 9) <= (x * x <= A)) and ((y * y <= A) <= (y <= 9)) = false then 
        begin
          OK := 0;
          break;
        end;
    if OK = 1 then 
    begin
      print(A);
      break
    end;
  end;
end.

















Бейсик:



Python:




for A in range(200,-100,-1):
    OK = 1
    for x in range(0,100):
        for y in range(0,100):
            OK *= ((x<=9) <= (x*x<=A)) and((y*y<=A) <= (y<=9)) 
    if OK:
        print(A)
        break









С++:










✎ Способ 2 (теоретическое решение):


    

  • Условно разделим исходное выражение на части:
    • 

    решение 15 (18) задания демоверсии егэ информатика
    

  • Главное действие (внешняя операция) в исходном выражении — это конъюнкция. Конъюнкция истинна, когда все операнды истинны. Т.е. в задаче обе части 1 и 2 должны быть истинными (т.к. по условию общая формула должна быть истинной).
    • 



    
Рассмотрим часть 1:
    

  • если в 1.1 имеем x > 9, то часть 1 будет истинна независимо от А. Значит, значение числа А влияет на решение только при выполнении условия:
    • 

    x<=9
    

    (импликация 0 → 0 = 1, 0 → 1 = 1)
    

  • теперь, для того чтобы в части 1, выражение было истинным, надо чтобы часть 1.2 была истинной:
    • 

    x*x <= A 
    

    (импликация 1 → 1 = 1)
    

  • таким образом, получаем:
    • 

    x <= 9
x2 <= A

при любых x

    

  • так как нам необходимо найти наибольшее возможное А, то, значит, надо ограничить его значения сверху, а данная часть выражения ограничивает только снизу:
    • 

    возьмем максимальное натуральное: x=9, тогда A>=81
    

    Рассмотрим часть 2:
    

  • если 2.2 истинно (т.е. y <= 9), то часть 2 будет истинна независимо от А. Значит, значение числа А влияет на решение только при выполнении условия:
    • 

    y > 9
    

  • теперь, для того чтобы в части 2 выражение было истинным, надо чтобы часть 2.1 была ложной:
    • 

    y * y > A 
    

    (импликация 0 → 0 = 1)
    

  • таким образом, получаем:
    • 

    y > 9
y2 > A

при любых y

    

  • данная часть выражения ограничивает значения А сверху:
    • 

    возьмем наименьшее возможное по условию натуральное: y = 10, тогда A < 100
    

  • Получаем, что наибольшее А меньшее 100: А = 99
    • 


    



Результат:  99





Подробное решение 15 задания демоверсии ЕГЭ 2018 года смотрите на видео (аналитическое решение):


📹 YouTube здесь

 📹 Видеорешение на RuTube здесь


Поиск наибольшего или наименьшего числа А:

  


✍ Решение:





✎ Способ 1 (программный):


Важно: Поскольку используется метод полного перебора, то возможна ситуация, когда транслятор будет работать слишком медленно. Но работоспособность представленного алгоритма проверена на онлайн компиляторах.


Pascalabc.net:










1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18





begin
  for var A := -100 to 200 do
  begin
    var OK := 1;
    for var x := 1 to 100 do
      for var y := 1 to 100 do
        if ((y+3*x<A) or (x >20)or(y>40)) = false then 
        begin
          OK := 0;
          break;
        end;
    if OK = 1 then 
    begin
      print(A);
      break
    end;
  end;
end.

















Бейсик:



Python:




for A in range(-100,200):
    OK = 1
    for x in range(1,100):
        for y in range(1,100):
            OK *= (y+3*x<A) or (x > 20) or (y > 40) 
    if OK:
        print(A)
        break









С++:










✎ Способ 2 (теоретическое решение):


    

  • Определим основные части выражения, выделив отдельно неизвестную часть — с А, и, так сказать, известную часть, то есть остальную.
    • 

        1                 2
(y+3x < A) ∨ (x > 20) ∨ (y > 40)

    

  • Поскольку основными операциями являются операции дизъюнкции (логического сложения) и порядок их выполнения не важен, то последней, внешней, операцией будем выполнять дизъюнкцию слева, т.к. она объединяет неизвестную и известную часть.
    • 

  • Сначала важно рассмотреть вторую часть выражения, известную, так как от нее будет зависеть значение A. Если вторая часть истинна, то А может быть как = 1, так и = 0. Такой вариант нам не подходит:
    • 

    (y+3x < A) ∨ (x > 20) ∨ (y > 40)
  1 или 0?                   1               = 1
Не подходит!

    

  • Соответственно, рассмотрим вариант, когда вторая часть ложна, тогда часть выражения с неизвестным А будет обязательно истинной, т.е.:
    • 

    1. (y+3x < A) = 1
2. (x > 20) ∨ (y > 40) = 0

    

  • Дизъюнкция ложна, когда оба операнда ложны, т.е. из второго пункта имеем:
    • 

    x <= 20
y <= 40

    

  • Для того, чтобы перекрыть все x и все y, возьмем наибольшие из возможных значений: x = 20, y = 40.
    • 

  • Выразим А:
    • 

    А > 3x + y
A > 3*20 + 40
A > 100 

    

  • Поскольку требуется найти наименьшее значение А, то имеем А = 101.
    • 



Результат:  101





Подробное решение досрочного ЕГЭ 2018 года смотрите на видео (аналитическое решение):


📹 YouTube здесь

📹 Видеорешение на RuTube здесь


Поиск наибольшего или наименьшего числа А:

  




15_0:Разбор 15 задания. Демоверсия егэ по информатике 2019:




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



  

(48 ≠ y + 2x) ∨ (A < x) ∨ (A < y)



  

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








✍ Решение:

✎ Решение 1 (теоретическое):


    

  • Разделим общее выражение на две части. Выделим неизвестную часть красным:
    • 

    (48 ≠ y + 2x) ∨ (A < x) ∨ (A < y)

    

  • Неизвестная часть должна быть истинной, она обязательно будет истинна, если известная часть — ложь:
    • 

    (48 ≠ y + 2x) ∨ (A < x) ∨ (A < y) = 1
      0                  1

    

  • Т.е. 48 ≠ y + 2x = 0 или y + 2x = 48. На графике это уравнение представляет линию. Из условия имеем два ограничения:(x > 0) and (y > 0). Отобразим линию для 1-й четверти, соответствующей положительным x и y:
    • 

    y + 2x = 48  :
при x = 0, y = 48
при y = 0, 2x = 48 => x = 24

    

    решение 15 (18) задания демоверсии егэ 2019
    

  • Возьмем некоторое значение A, например, A = 25, отметим его на графике белой областью так, чтобы выполнялось (A < x) ∨ (A < y). По условию имеем, что все точки данной части отрезка прямой y + 2x = 48 должны принадлежать отмеченной белой области. Заштрихуем область для всех точек прямой (голубым цветом):
    • 

    

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

  • Наибольшее значение голубая область приобретает в точке пересечения прямой y + 2x = 48 с прямой y = x:
    • 

    линия на графике для решения 15 задания егэ
    

  • Далее решаем полученное линейное уравнение (для x = y):
    • 

    x + 2x = 48 =>
3x = 48
x = 16

    

  • Так как значение A должно быть меньше x, то наибольшее А = 15. 
    • 



✎ Решение 2 (программное):

Python:










1
2
3
4
5
6
7
8





for A in range(200,0,-1):
    OK = 1
    for x in range(0,100):
        for y in range(0,100):
            OK *= (48!=y+2*x) or(A<x)or (A<y) 
    if OK:
        print(A)
        break










Результат:  15





Видео решения 15 задания демоверсии ЕГЭ 2019 (аналитическое решение):

📹 YouTube здесь

📹 Видеорешение на RuTube здесь


Поиск наибольшего или наименьшего числа А:

  




15_19:


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



  

(y + 5x <= 34) → ((y — x > 4) ∨ (y <= A))



  

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






✍ Решение:


    

  • Общая идея такова:
    
 необходимо упростить формулу так, чтобы последняя операция (внешняя) выполнялась со скобкой, в которой находится искомое A. После чего разделить формулу на две части, в одной из которых находится искомое.
    • 

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

    ¬(y + 5x <= 34) ∨ (y - x > 4) ∨ (y <= A)

    

  • Разделим формулу на две части таким образом, чтобы внешняя операции отделяла часть, в которой находится искомое A:
    • 

    ¬(y + 5x <= 34) ∨ (y - x > 4) ∨ (y <= A) = 1
        1 часть                  2 часть

    

  • Формула по условию должна быть истинной (=1). Внешняя операция — дизъюнкция — истинна аж в трех случаях: a=1 b=0, a=0 b=1, a=1 b=1. 
    • 

  • Если мы допустим, что первая часть истинна, то вторая, искомая часть, может быть как истинной, так и ложной. Поэтому такой вариант не подходит.
    • 

  • Допустим, что первая часть ложна, тогда вторая, искомая часть, должна быть только истинной:
    • 

    ¬(y + 5x <= 34) ∨ (y - x > 4) ∨ (y <= A) = 1
        1 часть = 0               2 часть = 1

    

  • С учетом, что в первой части формулу находится операция дизъюнкция, которая ложна только в одном случае (a=0 b=0), то выпишем утверждения, получившиеся из первой части:
    • 

    y + 5x > 34 = 0, значит:
1. y + 5x <= 34
y - x > 4 = 0, значит:
2. y - x <= 4

    

  • Кроме того, имеем еще одно утверждение второй части:
    • 

    y <= A
или
A >= y

    

  • Отобразим получившиеся уравнения прямых на плоскости:
    • 

    решение
    

  • Раз A >= y, значит, искомая область лежит выше обеих прямых. Наименьшее значение А будет достигнуто в указанной точке пересечения двух прямых.
    • 

  • В точке пересечения прямых уравнения равны, т.е. имеем:
    • 

    34 - 5x = 4 + x
30 = 6x
x = 5
Найдем y: 
y = 4 + 5 = 9

    

  • Поскольку имеем утверждение, что A >= y и в задании требуется найти наименьшее A, то получаем:
    • 

    y = 9:
A >= 9 => наименьшее A = 9

    



✎ Решение 2 (программное):

Python:










1
2
3
4
5
6
7
8





for A in range(-100,100):
    OK = 1
    for x in range(0,100):
        for y in range(0,100):
            OK *= (y+5*x<=34)<=((y-x >4)or(y<=A)) 
    if OK:
        print( A )
        break










PascalABC.NET:










1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21





 
begin
  for var A := -100 to 100 do
  begin
    var OK := true;
    for var x := 0 to 100 do
    begin
      for var y := 0 to 100 do
      begin
        OK := (y + 5 * x <= 34) <= ((y - x > 4) or (y <= A));
        if OK = false then break;
      end;
      if OK = false then break;
    end;
    if OK then 
    begin
      print(A);
      break;
    end;
  end;
end.










Результат:  9






Поиск наибольшего или наименьшего числа А:

  




15_13:


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



  

(2y + 5x < A) ∨ (2x + 4y > 100) ∨ (3x – 2y > 70)


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


Типовые задания для тренировки







✍ Решение:


    
✎ Решение (программное):
    
Python:
    

    

    


    


    1
2
3
4
5
6
7
8

    
    		


    for A in range(-200,200):
    OK = 1
    for x in range(1,100):
        for y in range(1,100):
            OK *= (2*y + 5*x < A) or (2*x + 4*y > 100) or (3*x - 2*y > 70) 
    if OK:
        print( A )
        break
    
    		

    
    

    

    

    PascalABC.NET:
    

    

    


    


    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

    
    		


    begin
  for var A := -200 to 200 do
  begin
    var OK := true;
    for var x := 1 to 100 do
    begin
      for var y := 1 to 100 do
      begin
        OK := (2*y + 5*x < A) or (2*x + 4*y > 100) or (3*x - 2*y > 70);
        if OK = false then break;
      end;
      if OK = false then break;
    end;
    if OK then 
    begin
      print(A);
      break;
    end;
  end;
end.
    
    		

    
    

    

    



Результат:  171





Видео разбора задания смотрите на видео (аналитическое решение):


📹 YouTube здесь

 📹 Видеорешение на RuTube здесь


Поиск наибольшего или наименьшего числа А:

  




15_14:


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



  

(3y – x > A) ∨ (2x + 3y < 30) ∨ (2y – x < –31)


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


Типовые задания для тренировки







✍ Решение:


    
✎ Решение 1 (теоретическое):
    

  • Разделим выражение на две части: часть с неизвестным = 1, часть известная = 0:
    • 

    (3y – x > A) ∨ (2x + 3y < 30) ∨ (2y – x < –31) = 1
    

  • Выпишем отдельно обе скобки известной части:
    • 

    (1) 
(2x + 3y) >= 30,
y >= (30 - 2x) / 3
x = (30 - 3y) /2
    

    (2) 
(2y – x >=–31)
y >= (x - 31) / 2
x = 2y + 31

    

  • Подберем значения координат для x и y обеих частей, и отобразим линии на графике функций:
    • 

    (1)
x | y
0 | 10
15| 0
    

    (2)
x | y
0 | -15 ( целые)
30|0
    

  • Для первого уравнения:
    • 

    

  • Для второго уравнения:
    • 

    

  • Сопоставим обе области:
    • 

    

  • Добавим на график прямую A<3y-x:
    • 

    

  • Раз  A < 3y – x, то будем перемещать А снизу вверх. Наибольшее значение А будет достигнуто в указанной точке пересечения с прямой (2).
    • 

  • Т.е. для уравнения (2) имеем:
    • 

    если y = 1, то x = 2*1 + 31 = 33
    

  • Подставим в выражение для поиска А:
    • 

    А < 3y - x
A < 3-33, A < -30, A=-31
    

    ✎ Решение (программное):
    
Python:
    

    

    


    


    1
2
3
4
5
6
7
8

    
    		


    for A in range(200,-200,-1):
    OK = 1
    for x in range(1,100):
        for y in range(1,100):
            OK *= (3*y-x>A) or (2*x+3*y<30) or (2*y-x<-31) 
    if OK:
        print(A)
        break
    
    		

    
    

    

    



Результат:  -31





* В некоторых задачах использован метод, предложенный А.В. Здвижковой








Источник
















Solntselikaya






1 / 1 / 0


Регистрация: 03.04.2021


Сообщений: 2












	1








03.04.2021, 10:24. Показов 20901. Ответов 3




Метки нет  (Все метки)












			Прошу, помогите пожалуйста с кодом!


Текст задачи: «Укажите наименьшее целое значение А, при котором выражение (2y + 3x < A) ∨ (x + y > 40) истинно для любых целых неотрицательных значений x и y.»

Пишу такой код:








Python
















1
2
3
4
5
6
7
8
9





for a in range(1, 400):
    check = True
    for x in range(1, 1000):
        for y in range(1, 1000):
            if not((2*y + 3*x < a) or (x+y > 40)):
                check = False
                break
    if check == True:
        print(a)


















Наименьшее значение, которое выдаёт — 120. А в ответе к задаче — 121 

В питоне недавно, поэтому прошу подсказать, что не так 


Заранее большое спасибо!





		__________________

		Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
	




    

        


            1


        

    


	


















Programming


Эксперт


94731 / 64177 / 26122


Регистрация: 12.04.2006


Сообщений: 116,782





			03.04.2021, 10:24
		    






3
			



















Gdez






6989 / 3910 / 1745


Регистрация: 27.03.2020


Сообщений: 6,722










				03.04.2021, 11:09




	2










Solntselikaya, вообще то при х = 0   у = 41 -> А >= 83


Добавлено через 13 минут

Solntselikaya, 








Python
















1
2
3
4
5





a = 205
for x in range(42):
    y = 41 - x
    a = min(a, 2*y+3*x+1)
print(a)




















    

        


            1


        

    


	


















3730 / 2306 / 498


Регистрация: 07.11.2019


Сообщений: 3,914










				03.04.2021, 14:21




	3








Лучший ответ Сообщение было отмечено Solntselikaya как решение
			


Решение






Цитата

					Сообщение от Solntselikaya

					Посмотреть сообщение


целых неотрицательных значений x и y




Поэтому в 3 и 4 строке замените range(1, 1000) на range(0, 1000) и все получится.

Хотя код и не оптимален..






    

        


            1


        

    


	


















1 / 1 / 0


Регистрация: 03.04.2021


Сообщений: 2










				05.04.2021, 13:13


				 [ТС]




	4












Цитата

					Сообщение от u235

					Посмотреть сообщение


в 3 и 4 строке замените range(1, 1000) на range(0, 1000)




Огромное спасибо! Все и правда получилось как в ответе 

По поводу оптимальности.. Как уже упоминала, в Питоне совсем недавно и изучаю я его самостоятельно  поэтому была бы невероятно признательна, если бы Вы мне еще и в этом вопросе что-то подсказали!!!






    

        


            0


        

    


	












Источник

















    

  • 

    • 

  • 

  • 
                                    Информатика — уроки для подготовки к экзаменам ЕГЭ ОГЭ
                            
    • 

  • 

  • 
                                    ГИА по информатике
                            
    • 

  • 

  • 
                                    ЕГЭ по информатике. Все типы задания 15 на Python
                            
    • 









ЕГЭ по информатике. Все типы задания 15 на Python






Смотреть видео: 




#информатика #егэинформатика #икт #экзамены #егэ_2020 #мгту #школьникам #помощь_студентам #подготовкакэкзаменам







Свежая информация для ЕГЭ и ОГЭ по Информатике (листай): 






С этим видео ученики смотрят следующие ролики: 






Облегчи жизнь другим ученикам — поделись! (плюс тебе в карму):








    

  • Комментарии
    • 






            Нет комментариев. Ваш будет первым!        












Источник







Пройти тестирование по этим заданиям
Вернуться к каталогу заданий


Версия для печати и копирования в MS Word






1




Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. 


Так, например, 14 & 5 = 11102 & 01012 = 01002 = 4. Для какого наименьшего неотрицательного целого числа А формула 


x & 29 ≠ 0 → (x & 17 = 0 → x & А ≠ 0)


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










2




Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14&5 = 11102&01012 = 01002 = 4.


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


x&25 ≠ 0 → (x&17 = 0 → x&А ≠ 0)


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










3




Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14 & 5 = 11102 & 01012 = 01002 = 4. Для какого наименьшего неотрицательного целого числа А формула 


x & 29 ≠ 0 → (x & 12 = 0 → x & А ≠ 0)


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










4




Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. 


Так, например, 14&5  =  11102&01012 = 01002 = 4. 


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


 левая круглая скобка левая круглая скобка x28 не равно 0 правая круглая скобка vee левая круглая скобка x45 не равно 0 правая круглая скобка правая круглая скобка arrow левая круглая скобка левая круглая скобка x17=0 правая круглая скобка arrow левая круглая скобка xA не равно 0 правая круглая скобка правая круглая скобка 


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










5




Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. 


Например, 14&5 = 11102&01012 = 01002 = 4.  


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


x&25 ≠ 0 → (x&9 = 0 → x&А ≠ 0) 


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








Пройти тестирование по этим заданиям








Источник






Доброго времени суток каждому жителю Хабрвилля! Давненько я не писал статей! Пора это исправить!


В сегодняшней статье поговорим о насущной для многих выпускников школ теме — ЕГЭ. Да-да-да! Я знаю, что Хабр — это сообщество разработчиков, а не начинающих айтишников, но сейчас ребятам как никогда нужна поддержка именно сообщества. Ребят опять посадили на дистант. Пока не ясно на какой период, но уже сейчас можно сказать, что ЕГЭ по информатике будет на компьютерах и его можно зарешать при помощи языка Python.


Вот я и подумал, чтобы не получилось как в песне, стоит этим заняться. Я расскажу про все задачи первой части и их решения на примере демо варианта ЕГЭ за октябрь.


Всех желающих — приглашаю ниже!


Быстрый перевод из системы в систему


В Python есть интересные функции bin(), oct() и hex(). Работают данные функции очень просто:


bin(156) #Выводит '0b10011100'
oct(156) #Выводит '0o234'
hex(156) #Выводит '0x9c'


Вывод в интерпретационном режиме
Вывод в интерпретационном режиме
Как вы видите, выводится строка, где 0b — означает, что число далее в двоичной системе счисления, 0o — в восьмеричной, а 0x — в шестнадцатеричной. Но это стандартные системы, а есть и необычные…


Давайте посмотрим и на них:


n = int(input()) #Вводим целое число
 
b = '' #Формируем пустую строку
 
while n > 0: #Пока число не ноль
    b = str(n % 2) + b #Остатот от деления нужной системы (в нашем сл записываем слева
    n = n // 2 #Целочисленное деление
 
print(b) #Вывод


Данная программа будет работать при переводе из десятичной системы счисления в любую до 9, так как у нас нет букв. Давайте добавим буквы:


n = int(input()) #Вводим целое число

b = '' #Формируем пустую строку

while n > 0: #Пока число не ноль
	if (n % 21) > 9: #Если остаток от деления больше 9...
		if n % 21 == 10: #... и равен 10...
			b = 'A' + b #... запишем слева A
		elif n % 21 == 11:#... и равен 11...
			b = 'B' + b#... запишем слева B

'''

И так далее, пока не дойдём до системы счисления -1 (я переводил в 21-ную систему и шёл до 20)

'''

		elif n % 21 == 11:
			b = 'B' + b
		elif n % 21 == 12:
			b = 'C' + b
		elif n % 21 == 13:
			b = 'D' + b
		elif n % 21 == 14:
			b = 'E' + b
		elif n % 21 == 15:
			b = 'F' + b
		elif n % 21 == 16:
			b = 'G' + b
		elif n % 21 == 17:
			b = 'H' + b
		elif n % 21 == 18:
			b = 'I' + b
		elif n % 21 == 19:
			b = 'J' + b
		elif n % 21 == 20:
			b = 'K' + b
	else: #Иначе (остаток меньше 10)
		b = str(n % 21) + b #Остатот от деления записываем слева
	n = n // 21 #Целочисленное деление

print(b) #Вывод


Способ объёмен, но понятен. Теперь давайте используем тот же функцию перевода из любой системы счисления в любую:


def convert_base(num, to_base=10, from_base=10):
    # Перевод в десятичную систему
    if isinstance(num, str): # Если число - строка, то ...
        n = int(num, from_base) # ... переводим его в нужную систему счисления
    else: # Если же ввели число, то ...
        n = int(num) # ... просто воспринять его как число
    # Перевод десятичной в 'to_base' систему
    alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" # Берём алфавит
    if n < to_base: # Если число меньше системы счисления в которую переводить...
        return alphabet[n] # ... вернуть значения номера в алфавите (остаток от деления)
    else: # Иначе...
        return convert_base(n // to_base, to_base) + alphabet[n % to_base] # ... рекурсивно обратиться к функии нахождения остатка


Вызвав функцию вывода print(convert_base(156, 16, 10)) мы переведём 156 из 10 в 16 систему счисления, а введя print(convert_base('23', 21, 4)) переведёт 23 из 4-ичной в 21-ичную систему (ответ: B). 


Задача 2


Все задания беру из первого октябрьского варианта (он же вариант № 9325894) с сайта Решу.ЕГЭ.


Решение данной задачи совсем простое: банальный перебор.


print('y', 'x', 'z', 'F') #Напечатаем заголовки таблицы
for y in range(2): #Берём все переменные и меняем их в циклах '0' и '1'
	for x in range(2):
		for z in range(2):
			for w in range(2):
				F = ((not x or y) == (not z or w)) or (x and w) #Записываем функцию
				print(x, y, z, F) #Выводим результат


Результат:


Нам вывелась вся таблица истинности (1 = True, 0 = False). Но это не очень удобно. Обратите внимание, что в задании, функция равно 0, так и давайте подправим код:


print('y', 'x', 'z', 'F') #Напечатаем заголовки таблицы
for y in range(2): #Берём все переменные и меняем их в циклах '0' и '1'
	for x in range(2):
		for z in range(2):
			for w in range(2):
				F = ((not x or y) == (not z or w)) or (x and w) #Записываем функцию
				if not F:
					print(x, y, z, F) #Выводим результат


Результат:


Далее —  простой анализ.


Задача 5


Данная задача легко решается простой последовательностью действий в интерпретационном режиме:


Задача 6


Перепечатали и получили ответ:


s = 0
k = 1
while s < 66:
    k += 3
    s += k
print(k)


Задача 12


В очередной раз, просто заменим слова на код:


a = '9' * 1000

while '999' in a or '888' in a:
	if '888' in a:
		a = a.replace('888', '9', 1)
	else:
		a = a.replace('999', '8', 1)
print(a)


Задача 14


Компьютер железный, он всё посчитает:


a = 4 ** 2020 + 2 ** 2017 - 15
k = 0

while a > 0:
    if a % 2 == 1:
    	k += 1
    a = a // 2

print(k)


Задача 16


Опять же, просто дублируем программу в python:


def F(n):
    if n > 0:
        F(n // 4)
        print(n)
        F (n - 1)
print(F(5))


Результат:


Задача 17


Задача с файлом. Самое сложное — достать данные из файла. Но где наша не пропадала?!


with open("17.txt", "r") as f: #Открыли файл 17.txt для чтения
    text = f.read() #В переменную text запихнули строку целиком
a = text.split("n") #Разбили строку энтерами (n - знак перехода на новую строку)

k = 0 #Стандартно обнуляем количество
m = -20001 #Так как у нас сумма 2-ух чисел и минимальное равно -10000, то минимум по условию равен -20000, поэтому...

for i in range(len(a)): #Обходим все элементы массива
	if (int(a[i - 1]) % 3 == 0) or (int(a[i]) % 3 == 0): #Условное условие
		k += 1 #Счётчик
		if int(a[i - 1]) + int(a[i]) > m: #Нахождение минимума
			m = int(a[i - 1]) + int(a[i])

print(k, m) #Вывод


Немного пояснений. Функция with() открывает файл считывает данные при помощи функции read() и закрывает файл. В остальном — задача стандартна.


Задача 19, 20 и 21


Все три задачи — задачи на рекурсию. Задачи идентичны, а вопросы разные. Итак, первая задача:


Пишем рекурсивную функцию и цикл перебора S:


def f(x, y, p): #Рекурсивная функция
	if x + y >= 69 or p > 3: #Условия завершения игры
		return p == 3
	return f(x + 1, y, p + 1) or f(x, y + 1, p + 1) or
		   f(x * 2, y, p + 1) or f(x, y * 3, p + 1) #Варианты действий

for s in range (1, 58 + 1): #Перебор S
	if f(10, s, 1): #Начали с 10 камней
		print(s)
		break


Немного пояснений. В рекурсивной функции существует 3 переменные x — число камней в первой куче, y — число камней во второй куче, p — позиция. Позиция рассчитывается по таблице:











Игра




Петя




Ваня




Петя




Ваня




Петя








p




1




2




3




4




5




6










Далее — всё по условию задачи.


Вторая задача на теорию игр:


Все отличия в рамке. Ну и код, соответственно, не сильно отличается:


def f(x, y, p): #Рекурсивная функция
	if x + y >= 69 or p > 4: #Условия завершения игры
		return p == 4
	if p % 2 != 0:
		return f(x + 1, y, p + 1) or f(x, y + 1, p + 1) or
			   f(x * 2, y, p + 1) or f(x, y * 3, p + 1) #Варианты действий
	else:
		return f(x + 1, y, p + 1) and f(x, y + 1, p + 1) and
			   f(x * 2, y, p + 1) and f(x, y * 3, p + 1) #Варианты действий


for s in range (1, 58 + 1): #Перебор S
	if f(10, s, 1): #Начали с 10 камней
		print(s)


Отличия:


    

  1. 

    Выиграл Петя, соответственно, позиция 4
    

    2. 

  2. 

    Так как Петя не может выиграть за один ход — он выигрывает за 2 хода (and, а не or на нечётных позициях (играх Пети))
    

    3. 

  3. 

    Убрали break, так как нам нужны все S, а не единственный
    

    4. 



Последняя вариация задачи:


Сразу код:


def f(x, y, p): #Рекурсивная функция
	if x + y >= 69 or p > 5: #Условия завершения игры
		return p == 3 or p == 5
	if p % 2 == 0:
		return f(x + 1, y, p + 1) or f(x, y + 1, p + 1) or
			   f(x * 2, y, p + 1) or f(x, y * 3, p + 1) #Варианты действий
	else:
		return f(x + 1, y, p + 1) and f(x, y + 1, p + 1) and
			   f(x * 2, y, p + 1) and f(x, y * 3, p + 1) #Варианты действий


for s in range (1, 58 + 1): #Перебор S
	if f(10, s, 1): #Начали с 10 камней
		print(s)


Ну и всего лишь 2 отличия:


    

  1. 

    Позиции 3 или 5, а не 4, так как выиграл Ваня
    

    2. 

  2. 

    На второй ход выигрывает Ваня и нам нужно or и and поменять. Я заменил только кратность 2.
    

    3. 



Задача 22


Ctrl+C, Ctrl+V — наше всё!  :) 


for i in range(1, 100000):
	x = i
	L = 0
	M = 0
	while x > 0 :
		L = L+1
		if (x % 2) != 0:
			M = M + x % 8
		x = x // 8
	if L == 3 and M == 6:
		print(i)


Задача 23


Итак, код:


def f(x, y):
	if x > y: #Перегнали цель
		return 0
	if x == y:  #Догнали цель
		return 1
	if x < y: #Догоняем цель тремя методами
		return f(x + 1, y) + f(x + 2, y) + f(x * 2, y)

print(f(3, 10) * f(10, 12)) #Прошло через 10, значит догнали 10 и от де догоняем 12


Так как в условии задачи мы увеличиваем число, но будем числа «догонять». Три метода описаны, ну а пройти через 10 — значит дойти до него и идти от него.


Собственно, это и есть вся первая часть ЕГЭ по информатике решённая на Python.


Ссылка на репозиторий со всеми программами:


Надеюсь, что смог помочь в своей статье выпускникам и готовящимся  ;) 


Остался один вопрос — нужен ли разбор второй части ЕГЭ по информатике на Python? Оставлю этот вопрос на ваше голосование.


Всем удачи!








Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.




Делаю разбор второй части?



       Проголосовали 106 пользователей. 


       Воздержались 15 пользователей.
    






Источник







  



                       
  






	









    
    
    
    



    

                
Понравилась статья? Поделить с друзьями:

        
        

























    








			

  • Решение 12 задания егэ по математике профиль тригонометрические
    • 

  • Решение 12 задания егэ по математике профиль онлайн
    • 

  • Решение 12 задания егэ по математике профиль 2023 ященко 36 вариантов
    • 

  • Решение 12 задания егэ по математике профиль 2022 ященко 36 вариантов
    • 

  • Решение 12 задания егэ по информатике на паскале

    •