Компьютерный экзамен, задание 15, дискретные наборы и задание 15, компьютерный экзамен по кейсам python

Задание 15. Знание основных понятий и законов математической логики.

Логические функции. Законы алгебры
логики. Логические уравнения. Дизъюнктивная нормальная форма.

Решение задачи В15

(диагностическая работа №2)

Решение системы уравнений,

содержащих логические переменные

В15. Сколько различных решений имеет, представленная

ниже, система уравнений?

1. (Х1=Х2) (Х2=Х3) = 1

2. (Х2=Х3) (Х3=Х4) = 1

3. (Х3=Х4) (Х4=Х5) = 1

4. (Х4=Х5) (Х5=Х6) = 1

5. (Х5=Х6) (Х6=Х7) = 1

Таблицы истинности для эквивалентности и импликации

выглядят следующим образом

Результатом ЭКВИВАЛЕНТНОСТИ является новое логическое

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

исходных выражения одновременно истинны или ложны.

Результатом ИМПЛИКАЦИИ является ЛОЖЬ только тогда, когда условие А истинно, а следствие В ложно.

Определим сначала на скольких наборах значений переменных Х1, Х2 и Х3 будет истинно уравнение 1.

В таблице чёрным шрифтом представлены все возможные наборы значений трёх переменных.

Зелёным шрифтом в таблице

вписаны значения эквивалентности

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

Следовательно первое уравнение с тремя переменными будет истинно

только на 6 наборах.

Рассмотрим первое и второе уравнения вместе, приняв во внимание, что второе уравнение включает ещё одну переменную Х4.

В случае эквивалентности Х2 и Х3 (Х2=Х3=1) Х3 и Х4 обязательно

должны быть эквивалентны, то — есть должно быть Х3=Х4=1, в

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

второе уравнение не будет истинным.

Этому случаю соответствуют наборы , в которых эквивалентность

переменных выделена зелёным.

В тех же случаях, когда Х2=Х3=0

(красные цифры) Х3 и Х4 могут

быть как эквивалентны Х3=Х4=1

так и неэквивалентны Х3=Х4=0,

что порождает два

В результате два уравнения с четырьмя переменными будут истинны на восьми наборах.

Аналогично можно показать , что:

— 3 уравнения с 5-ю переменными будут истинны на 10-ти наборах;

— 4 уравнения с 6-ю переменными будут истинны на 12-ти наборах;

— 5 уравнений с 7-ю переменными будут истинны на 14-ти наборах.

Представленная в задаче система из 5-ти уравнений с 7-ю неизвестными

имеет 14 решений.

Как заходить в аудиторию на ЕГЭ

Как заходить в аудиторию на ЕГЭ

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

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

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

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

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

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

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

Получилось выражение (X ≥ 7) ∧ (X

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

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

Ответ: 5

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

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

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

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

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

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

 A (0, 300): k=0 x (1, 301): y (1, 301): (x >= A) (y >= A) (x * y if k==90000: (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

15 * 15 = 225
14 * 14 = 196

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

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

Ответ: 15

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

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

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

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

 (n, m): n%m==0: : A (1, 1000): k=0 x (1, 1001): D(x, A) ((D(x, 6)) (D(x, 9))): k=k+1 k==1000: (A)

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

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

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

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

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

Посмотрим, когда в правой части получается ноль. Функция ДЕЛ(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 = 1110₂ & 0101₂ = 4

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

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

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

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

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

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

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

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

51 = 110011₂
25 = 11001₂

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ: 14

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

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

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

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

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

Ответ: 3

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

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

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

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

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

 A (0, 300): k=0 x (1, 301): y (1, 301): ( (x and (y and (x * y > 603) ): k=k+1 k==90000: (A)

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

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

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

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

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

¬((x 603)) = ¬(x 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

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

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

 A (-300, 300): k=0 x (1, 301): y (1, 301): (3*x + y or (x or (16 if k==90000: (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

3 * 15 + 15
60

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

Ответ: 61

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

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

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

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

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

 A (0, 300): k=0 x (1, 301): y (1, 301): (x > A) (y > x) (2 * y + x if k==90000: (A)

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

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

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

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

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

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

2 * x_max + x_max

3 * x_max

36 * 3 = 108
37 * 3 = 111

x_max = y_max = 36

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

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

Ответ: 36

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

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

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

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

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

 (n, m): n%m==0: : A (1, 1000): k=0 x (1, 1001): D(120, A) and (not(D(x, 70) and D(x, 30)) or D(x, A)): k=k+1 k==1000: (A)

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

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

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

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

Т.е. 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

Рассмотрим значение 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, такое что выражение

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

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

 A (1, 1000): k=0 x (1, 1001): (x&49==0) ((x&33!=0) (x&A!=0)): k=k+1 k==1000: (A)

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

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

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

49₁₀ = 110001₂

33₁₀ = 100001₂

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

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

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

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

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

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

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

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

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

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

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

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

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

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

— 5 минут.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. выражения в скобках,
2. операции «НЕ»,
3. операции «И»,
4. операции «ИЛИ»,
5. операции «импликация»
6. операции «эквиваленция»

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

• пересечение множеств соответствует логическому умножению, а объединение – логическому сложению;
• пересечением двух множеств называется новое множество, состоящее из элементов, принадлежащих одновременно обеим множествам:
• объединением двух множеств называется новое множество, состоящее из элементов, принадлежащих отдельно каждому из множеств (без повторений);
• пустое множество ∅ – это множество, в котором не содержится ни одного элемента; пустому множеству в теории множеств соответствует 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 без отрицания
   то используется закон:

   A_min = ¬B

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

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

   A_max = B

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

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

   A_max = ¬B

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

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

   A_min = B

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

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

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

5 & 26

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

5 = 1012 26 = 1101020 = 000002

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

• Обозначим:

(x & K = 0) как Zk 

Z_k * Z_m = Z_{k or m}

(X & 5 = 0) ∧ (X & 26 = 0)

Z5 ∧ Z26

Z5 ∧ Z26 = Z26 or 5помним, что дизъюнкция - это операция логическое "ИЛИ" (сложение)
5 = 1012 26 = 11010231 = 111112

Z5 ∧ Z26 = Z31

Z_k + Z_m = Z_{k and m}

(X & 28 = 0) ∨ (X & 22 = 0)

Z28 ∨ Z22

Z28 ∨ Z22 = Z28 and 22помним, что конъюнкция - это операция логическое "И" (умножение)
28 = 111002 22 = 101102 101002 = 2010

Z28 ∨ Z22 = Z20

• На деле, это означает, что если имеем:

X & 29 = 0 → X & 5 = 0 Истинно или Ложно?

Z29 → Z5

Z29 → Z5 = 1 (истине), тогда, когда:
29 = 11025 = 02
единичные биты двоичного числа 5 входят в единичные биты двоичного числа 29
(совпадают с ними)

Z29 → Z5 = 1 (истинно)

(x & 125 = 5) то же самое, что и
Z₁₂₀ * ¬Z₄ * ¬Z₁ = 1 (истине)

• Так, например, если в задании имеем:

X & 130 = 3 

X & 130 = 3 то же самое, что и
Z127 * ¬Z2 * ¬Z1т.е. 3 = 2 + 1 :
2 = 101 = 013 = 11

Дискретные множества

Задачи с отрезками

Наименьшая возможная длина

Напишем программу для проверки:

Наибольшая возможная длина

Побитовая конъюнкция

Напишем программу для проверки:

Множества с ДЕЛ()

Координатная плоскость

Напишем программу для проверки:

Напишем программу для проверки:

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

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

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

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

15_16. Решение 15 задания (№ 95, К. Поляков):

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

((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 

¬P ∨ ¬Q = 0,
или
¬P = 0 отсюда P = 1
¬Q = 0 отсюда Q = 1

A = {3,9}

3 + 9 = 

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

15_17. Решение 15 задания:

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

(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 

¬P ∨ ¬Q = 0,
или
¬P = 0 отсюда P = 1
¬Q = 0 отсюда Q = 1

A = {6,12}

6 + 12 = 

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

( (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

 ∨ (P ∧ ¬Q) = 1 

P ∧ ¬Q = 1,
или
P = 1 и
¬Q = 1 отсюда Q = 0

A = {2, 4, 8, 10, 14, 16, 20}

15_20. Решение 15 задания (Вариант 100, К. Поляков): Закон поглощения

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

¬(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

 ∨ ¬P ∨ ¬Q = 1 

¬P ∨ ¬Q = 0,
или
P = 1 и Q = 1 

A = {1}

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

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

15_3: Задание 15 (18) ЕГЭ по информатике 2017 ФИПИ вариант 17 (Крылов С.С., Чуркина Т.Е.):

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

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

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

• Упростим формулу, избавившись от ‘x ϵ‘:

(P → Q) ∧ A

(¬P ∨ Q) ∧ A

(¬P ∨ Q) ∧ A = 0

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

1. (¬P ∨ Q) = 1 ∨ 0 = 1 - на данном отрезке А должно равняться 02. (¬P ∨ Q) = 1 ∨ 1 = 1 - на данном отрезке А должно равняться 03. (¬P ∨ Q) = 1 ∨ 0 = 1 - на данном отрезке А должно равняться 04. (¬P ∨ Q) = 0 ∨ 0 = - на данном отрезке А может! равняться 15. (¬P ∨ Q) = 1 ∨ 0 = 1 - на данном отрезке А должно равняться 0

48 - 44 = 

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

44 45 1
44 46 2
44 47 344 48 4

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

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

15_9: Разбор 15 (18) задания ЕГЭ по информатике, вариант 5 (ФИПИ, «ЕГЭ информатика и ИКТ, типовые экзаменационные варианты 2018», С.С. Крылов, Т.Е. Чуркина):

   Укажите наибольшую возможную длину отрезка 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

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

Результат: 10

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

15_10: Вариант 6: ФИПИ, «ЕГЭ информатика и ИКТ, типовые экзаменационные варианты 2018», С.С. Крылов, Т.Е. Чуркина:

   Укажите наибольшую возможную длину отрезка 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

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

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

¬(P ~ Q) ∨ ¬A = 1

Результат: 8

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

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

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

15_11: Вариант 7: ФИПИ, «ЕГЭ информатика и ИКТ, типовые экзаменационные варианты 2018», С.С. Крылов, Т.Е. Чуркина:

   Укажите наибольшую возможную длину отрезка 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

Результат: 19

Задания с ДЕЛ

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

15_7. Решение 15 задания (Вариант 133, К. Поляков) :

Обозначим через ДЕЛ(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

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

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

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

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

x/A : x/40 ∨ x/64

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

А = 1, 2, 4, 8

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

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

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

Результат: 8

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

1
2
4

1
2
4

Результат: 8

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

15_5. Разбор 15 задания (Вариант 138, К. Поляков) :

Обозначим через ДЕЛ(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 ∨ (¬D28 ∨ D42) = 1 1 

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

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

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

А = 1, 2, 

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

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

 A : OK x : OK * x % A x % x % OK: A 

 A ok x x A < x <> x ok ok printA 

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

a b F(a

Результат: 3

15_6. Разбор 15 задания (Вариант 136, К. Поляков) :

Обозначим через ДЕЛ(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 ∨ D19 ∧ D15 = 1 1 

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

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

A = 1
D19 = 1
D15 = 1

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 делится на 15)

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

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

 A : OK x : OK * x % x % x % A OK: A 

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

a b F(a

285

Результат: 285

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

15_1. Задание 15 (18) ЕГЭ по информатике 2017 ФИПИ вариант 9 (Крылов С.С., Чуркина Т.Е.):

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 12&6 = 1100₂&0110₂ = 0100₂ = 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) ∧ 1 

(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 = 0) ∧ 35 ≠ 0 ∧ 52 = 0 = 0 0 ∧  = 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)

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

0000112 = 

✎ Способ 2*:

Используем метод А.В. Здвижковой.
• Выполним последовательно следующие пункты:

1. Произвести замену (x & K = 0) на Zk
2. Выполнить преобразования по свойству импликации и закону Де Моргана.
3. Стремиться прийти к выражению с конъюнкциями без отрицаний типа: Zk * Zm.
4. Все выражения типа Zk * Zm преобразовать по свойству
   Zk * Zm = Z_{k or m}.
5. Путем преобразований прийти к импликации: .

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

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

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

¬A ∨ (Z35 ∨ ¬Z52) = 1

¬A ∨ ¬Z52 ∨ Z35 = 1

¬(A ∧ Z52) ∨ Z35 = 1

(A ∧ Z52) → Z35 = 1

ZA ∨ 52 → Z35 = 1

A = ??0?
52 = 110100
A or 52 = 110135 = 1000 

Аmin = 112 = 10

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

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

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

15_2: Задание 15 (18) ЕГЭ по информатике 2017 ФИПИ вариант 12 (Крылов С.С., Чуркина Т.Е.):

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 12&6 = 1100₂&0110₂ = 0100₂ = 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 → (z36 → ¬ z6) = A + ¬z36 + ¬z6 

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

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

z36 * z6 = z36 or 6

1001002 -> 36
1102 -> 6
100100 1101001102 -> 36 or 6 = 3810

z38 → A

A = 1001102 = 

  
✎ Способ 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) = 1;
или 1 ∨ (0) = 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)

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

100110 = 

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

  📹 Видеорешение на RuTube здесь
Способ 2:

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

15_8. Решение 15 задания (№ 209, С.С. Поляков, Саратов):

((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)) → ( ∧ ¬A ∧ )) = 1 

Z8 ∧ Z58 = Z8 or 58 :
8 = 1000 or58 = 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 = 10101 - не подходит!
58 = 111010
44 = 10100 - не подходит!
58 = 111010
45 = 1010 - не подходит!
58 = 111010
46 = 10110 - не подходит!
58 = 111010
47 = 1011 - не подходит!
58 = 111010 = 110000 - подходит!58 = 111010

Результат: 48

15_15. Решение 15 задания (№ 173, К. Поляков):

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

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

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

Типовые задания для тренировки: К. Поляков 174-177

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

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

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

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

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

Результат: 8

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

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

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

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

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

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

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

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

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



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