Егэ информатика задание 15 графики - Помощь в подготовке к экзаменам и поступлению

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

Содержание:

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

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

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

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

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

— нет,

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

— 1,

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

— 5 минут.

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

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

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

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

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

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

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

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

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

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

Порядок выполнения логических операций:

выражения в скобках,
операции «НЕ»,
операции «И»,
операции «ИЛИ»,
операции «импликация»
операции «эквиваленция»

последовательность из операций импликации выполняется слева направо (при этом соблюдается принцип «операции с одинаковым приоритетом выполняются слева направо»):

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), то есть A_min = ¬ X
пусть требуется выбрать множество A так, чтобы выполнялось равенство ¬ A ∨ X = I, в этом случае множество ¬ A должно включать дополнение ¬ X, то есть ¬ A ⊇ ¬ X; отсюда A ⊆ X, то есть A_max = X

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

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

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

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

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

A_min = ¬B

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

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

A_max = B

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

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

A_max = ¬B

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

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

A_min = B

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

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

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

5 & 26

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

5  =   101₂ 
26 = 11010₂
0  = 00000₂

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

Обозначим:

(x & K = 0) как Z_k

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

Z_k * Z_m = Z_{k or m}

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

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

то сначала введем замену:

Z₅ ∧ Z₂₆

а затем, используя свойство 1, вычислим поразрядную дизъюнкцию двоичного значения чисел 26 и 5:

Z₅ ∧ Z₂₆ = Z_{26 or 5}
помним, что дизъюнкция - это операция логическое "ИЛИ" (сложение)
5  =   101₂ 
26 = 11010₂
31 = 11111₂

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

Z₅ ∧ Z₂₆ = Z₃₁

Z_k + Z_m = Z_{k and m}

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

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

то сначала введем замену:

Z₂₈ ∨ Z₂₂

а затем, используя свойство 2, вычислим поразрядную конъюнкцию двоичного значения чисел 28 и 22:

Z₂₈ ∨ Z₂₂ = Z_{28 and 22}
помним, что конъюнкция - это операция логическое "И" (умножение)
28 = 11100₂ 
22 = 10110₂
     10100₂ = 20₁₀

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

Z₂₈ ∨ Z₂₂ = Z₂₀

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

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

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

то сначала введем замену:

Z₂₉ → Z₅

а затем, используя свойство 3, определим истинность высказывания Z₂₉ → Z₅:

Z₂₉ → Z₅ = 1 (истине), тогда, когда:
29 = 11101₂
5  =   101₂  
единичные биты двоичного числа 5 входят в единичные биты двоичного числа 29 
(совпадают с ними)

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

Z₂₉ → Z₅ = 1 (истинно)

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

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

X & 130 = 3

то сначала введем замену и, используя свойство 4, получим:

X & 130 = 3 то же самое, что и
Z₁₂₇ * ¬Z₂ * ¬Z₁

т.е. 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
    ⁰      ¹

То есть получаем:

¬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
    ⁰      ¹

То есть получаем:

¬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
 ⁰      ¹

То есть получаем:

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
 ¹      ⁰

То есть получаем:

¬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

Указанные в задании отрезки отобразим на числовой прямой. Разделим отрезки на части по точкам, соответствующим их границам.

Вернемся к преобразованному выражению. В нем есть известная часть (выделим ее) и неизвестная. По условию выражение должно быть ложно:

(¬P ∨ Q) ∧ A = 0

Внешняя операция выражения — конъюнкция — ложна в трех случаях и только в одном — истинна:

(¬P ∨ Q) ∧ A
    ⁰     ^∧ ⁰ ⁼ ⁰
    ⁰     ^∧ ¹ ⁼ ⁰
    ¹     ^∧ ⁰ ⁼ ⁰
    ¹     ^∧ ¹ ⁼ ¹

Теперь рассмотрим это выражение относительно наших отрезков на числовой прямой: если известная часть выражения (¬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:

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) # сами точки отрезка и длина

Вывод:

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.
Отобразим отрезки на числовой прямой, чтобы найти искомое значение:

Очевидно, что А будет истинно, только в части 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

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

Очевидно, что А будет истинно в двух отмеченных на рисунке частях: 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).
Отобразим отрезки на числовой прямой, чтобы найти искомое значение:

Получаем, что А соответствует двум отрезкам (см. рисунок, желтым цветом): [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
      ¹          ²

В полученной формуле необходимо, чтобы искомая часть с 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:

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

Результат: 8

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

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 )

Вывод:

PascalABC.net:

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.

Вывод:

Результат: 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
 ¹        ²

В части 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

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
 ¹       ²

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

¬A ∨ D19 ∧ D15 = 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 )

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

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

Результат: 285

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

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

15_1:

Обозначим через 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) ∧ ¬(35 ≠ 0 → 52 ≠ 0)
   ¹               ²

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

правило импликации: 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}

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

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

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

000011₂ = 3₁₀

Ответ: 3

✎ Способ 2*:

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

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

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

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

Получаем:

Z_{A ∨ 52} → Z35 = 1

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

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

В нашем случае это говорит о том, что все единичные биты двоичной записи числа 35 должны входить в результат Z_{A or 52}.
Рассмотрим подробно:

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

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

Аmin = 11₂ = 3₁₀

Результат: 3

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

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

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

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

15_2:

Обозначим через 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 → 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

Суть предыдущих действий в том, что нам необходимо прийти к импликации, но, избавившись от отрицания.
По следующему правилу Z_K * Z_M = Z_{K or M} (К. Поляков) заменим конъюнкцию:

z36 * z6 = z_{36 or 6}

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

100100₂ -> 36
110₂ -> 6

100100
   110
100110₂ -> 36 or 6 = 38₁₀

Получаем:

z38 → A

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

A = 100110₂ = 38₁₀

✎ Способ 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 = 38₁₀

Результат: 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 = Z_{8 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 (Z_k + Z_m = Z_{k and m}):

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

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

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

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

Наибольшее А = 1000 = 8₁₀

Результат: 8

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

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

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

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

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

✍ Решение:

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

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

Pascalabc.net:

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) <= (xx<=A)) and((y*y<=A) <= (y<=9)) if OK: print(A) break
С++:

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

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

Главное действие (внешняя операция) в исходном выражении — это конъюнкция. Конъюнкция истинна, когда все операнды истинны. Т.е. в задаче обе части 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
x² <= 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
y² > A

при любых y

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

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

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

Результат: 99

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

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

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

✍ Решение:

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

Pascalabc.net:

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+3x<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
      ⁰                  ¹

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

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

То есть все точки голубого квадрата должны находиться под отрезком линии (включая вершину (A, A)), и данный квадрат, соответствует максимальному значению A.
Наибольшее значение голубая область приобретает в точке пересечения прямой y + 2x = 48 с прямой y = x:

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

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

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

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

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:

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:

 
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:

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:

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:

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

* В некоторых задачах использован метод, предложенный А.В. Здвижковой

Источник

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

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

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

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

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

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

¬(X² ≥ 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, и т. д.

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

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

Получается, что выражение (X² < 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. В остальных случаях беспокоится не за что, потому что вся формула будет выдавать истину.

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

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 = 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.

Ответ: 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, можете посмотреть в этой статье.

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

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

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

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

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

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

1) Случай

Выражение ¬(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, .

2) Случай

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

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

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

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

3) Случай

В выражении ¬(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)

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

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

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

Чтобы выражение ((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 будет x_max т.е. y_max = x_max.

Тогда

2 * x_max + x_max < 110

3 * x_max < 110

36 * 3 = 108
37 * 3 = 111

x_max = y_max = 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).

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

Т.е. 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 в двоичную систему.

49₁₀ = 110001₂

33₁₀ = 100001₂

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

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

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

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

Ответ: 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.

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

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

В правой части получается 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)

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

Источник

Пройти тестирование по этим заданиям
Вернуться к каталогу заданий

Версия для печати и копирования в MS Word

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

((x ≤ 9) →(x ⋅ x ≤ A)) ⋀ ((y ⋅ y ≤ A) → (y ≤ 9))

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

Источник: Демонстрационная версия ЕГЭ—2018 по информатике.

Сколько существует целых значений числа A, при которых формула

((x < 6) → (x² < A)) ∧ ((y² ≤ A) → (y ≤ 6))

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

Источник: СтатГрад: Тренировочная работа 28.11.2017 ИН10203

Сколько существует целых значений числа A, при которых формула

((x < 5) → (x² < A)) ∧ ((y² ≤ A) → (y ≤ 5))

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

Сколько существует целых значений числа A, при которых формула

((x < A) → (x² < 100)) ∧ ((y² ≤ 64) → (y ≤ A))

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

Сколько существует целых значений числа A, при которых формула

((x < A) → (x² < 81)) ∧ ((y² ≤ 36) → (y ≤ A))

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

Пройти тестирование по этим заданиям

Источник

ЕГЭ информатика 15 задание разбор, теория, как решать.

Преобразование логических выражений, (П) — 1 балл

Е15.42 Для какого наименьшего натурального числа А формула (ДЕЛ(x, 2) → ¬ДЕЛ(x, 3)) / (x + A ≥ 100)

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа А формула (ДЕЛ(x, 2) → ¬ДЕЛ(x, 3)) / (x + A ≥ 100) тождественно истинна (т.е. принимает значение 1) при любом натуральном значении переменной х? Ответ: Демонстрационный вариант ЕГЭ 2023 г. – задание №15

Е15.41 для которого формула ((x ∈ Q) ≡ (x ∈ P)) ∨ (¬(x ∈ A) → ((x ∈ P) ∧ ¬(x ∈ Q))) тождественно истинна

На числовой прямой даны два отрезка: P = [ 6; 4 5] и Q = [18; 52]. Укажите наименьшую возможную длину такого отрезка A, для которого формула ((x ∈ Q) ≡ (x ∈ P)) ∨ (¬(x ∈ A) → ((x ∈ P) ∧ ¬(x ∈ Q))) тождественно истинна (т. е. принимает значение 1 при любом …

Е15.40 выражение (2у + 3х ≠ 135) ∨ (у > А) ∨ (x > A) истинно

Определите наибольшее целое значение A, при котором выражение (2у + 3х ≠ 135) ∨ (у > А) ∨ (x > A) истинно для любых целых положительных значений х и у. Ответ: Апробация ЕГЭ по информатике 19 февраля 2022 – задание №15 Тренировочный экзамен по информатике и ИКТ (КЕГЭ) в компьютерной форме

Е15.39 формула (x ∈ Q) → (((x ∈ P) ≡ (x ∈ Q)) ∨ (¬(x ∈ P) → (x ∈ A))) тождественно истинна

На числовой прямой даны два отрезка: P = [69; 91] и Q = [77; 114]. Укажите наименьшую возможную длину такого отрезка A, для которого формула (x ∈ Q) → (((x ∈ P) ≡ (x ∈ Q)) ∨ (¬(x ∈ P) → (x ∈ A))) тождественно истинна (т. е. принимает значение 1 при любом значении переменной …

Е15.38 выражение ((x & 26 ≠ 0) ∨ (x & 13 ≠ 0)) → ((x & 29 = 0) → (x & A ≠ 0)) тождественно истинно

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14&5 = 11102&01012 = 01002 = 4 . Определите наименьшее натуральное число A, такое что выражение ( (x & 26 ≠ 0) ∨ (x & 13 ≠ 0)) → ((x & 29 = 0) → (x & A ≠ 0)) тождественно истинно …

Е15.37 формула (x ∈ Q) → (¬(x ∈ P) → ¬((x ∈ Q) ∧ ¬(x ∈ A))) тождественно истинна

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

Е15.36 формула ( (x ∈ А) → (x ∈ P) ) / (x ∈ Q) тождественно истинна

На числовой прямой даны два отрезка: P = [5, 17] и Q = [13, 23]. Найдите наибольшую возможную длину отрезка A, при котором формула ( (x ∈ А) → (x ∈ P) ) / (x ∈ Q) тождественно истинна, то есть принимает значение 1 при любом значении переменной х. Ответ: источник: informatikaexpert.ru

Е15.35 ДЕЛ(A, 40) / (ДЕЛ(780, x) → (¬ДЕЛ(A, x) → ¬ДЕЛ(180, x)))

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа A формула ДЕЛ(A, 40) / (ДЕЛ(780, x) → (¬ДЕЛ(A, x) → ¬ДЕЛ(180, x))) тождественно истинна, то есть принимает значение 1 при любом натуральном x? Ответ: СтатГрад Вариант ИН2010401 17.03.2021– задание №15

Е15.34 формула x & 85 = 0 → (x & 54 ≠ 0 → x & А ≠ 0) тождественно истинна

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Например, 14 & 5 = 11102 & 01012 = 01002 = 4. Для какого наименьшего неотрицательного целого числа А формула x & 85 = 0 → (x & 54 ≠ 0 → x & А ≠ 0) тождественно истинна (т. е. принимает …

Е15.33 формула ((x ∈ P) ∧ ¬(x ∈ A)) → ¬(x ∈ Q) тождественно истинна

На числовой прямой даны два отрезка: P = [10, 32] и Q = [18, 45]. Найдите наименьшую возможную длину отрезка A, при котором формула ((x ∈ P) ∧ ¬(x ∈ A)) → ¬(x ∈ Q) тождественно истинна, то есть принимает значение 1 при любом значении переменной х. Источник: informatikaexpert.ru

Источник

В решение заданий демо-версии используется язык программирования Python.

Задание 1. Анализ информационных моделей

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта D в пункт В и из пункта F в пункт A. В ответе запишите целое число.

На графе расставим веса вершин.
Мы видим, что вершина В уникальна, имеет вес 2 и связана с двумя «тройками по весу».
Из таблицы видим, В это 4, далее видим, что «тройки по весу» это вершины 2 и 7.
7 вершина связана кроме В, еще с двумя «тройками по весу», значит D это 7, а F это 2.

Далее 2 и 7 вершины ведут нас к 5, значит А это 5, оставшаяся «тройка» это вершина Е под номером 6.
Рассуждая дальше видим, что С это 1, G это 2.

Сумма дорог BD + AF = 53 + 5 = 58

Ответ: 58

Задание 2. Построение таблиц истинности логических выражений

Миша заполнял таблицу истинности логической функции F

F= ¬(y → x) v (z→ w) v ¬z , но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z. В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример. Функция задана выражением ¬x v y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид. В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать yx.

¬(y → x) v (z→ w) v ¬z=0. Следовательно y → x =1, z→ w=0, z=1. Значит третий столбец z. z→ w=0, значит w=0, и это может быть только 4 столбец. y → x =1, следовательно из второй строки мы видим, что первый столбец может быть только у, а второй х.

y	x	z	w
0	0	1	0
0	1	1	0
1	1	1	0

Решение на Python

Ответ: YXZW

Задание выполняется с использованием прилагаемых файлов

Задание 3. Базы данных. Файловая система

В прикрепленном файле приведён фрагмент базы данных «Продукты» о поставках товаров в магазины районов города. База данных состоит из трёх таблиц. Таблица «Движение товаров» содержит записи о поставках товаров в
магазины в течение первой декады июня 2021 г., а также информацию о проданных товарах. Поле Тип операции содержит значение Поступление или Продажа, а в соответствующее поле Количество упаковок, шт. занесена информация о том, сколько упаковок товара поступило в магазин или было продано в течение дня.

На рисунке приведена схема указанной базы данных.

Используя информацию из приведённой базы данных, определите общий вес
(в кг) крахмала картофельного, поступившего в магазины Заречного района
за период с 1 по 8 июня включительно. В ответе запишите только число.

На третьем листе книги применим фильтр по району и получим ID четырех магазинов.

На втором листе применим фильтр по товару и получим ID товара.

На первом листе применим фильтры по ID товара и ID магазинов и типу операции. Все даты попадают в интервал от 1 до 8 июня. Получим:

Поступило в продажу 710 упаковок. В упаковке 0,5 кг. Получим 355 кг.

Ответ: 355

Задание 4. Кодирование и декодирование информации

По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Ч. Для передачи используется двоичный код,удовлетворяющий прямому условию Фано, согласно которому никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений.

Кодовые слова для некоторых букв известны: Н – 1111, З – 110. Для трёх оставшихся букв А, К и Ч кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЗАЧКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

Ответ: 14

Задание 5. Анализ и построение алгоритмов для исполнителей

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему
новое число R следующим образом.

1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 0, а затем два левых разряда заменяются на 10;
б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 1, а затем два левых разряда заменяются на 11.

Полученная таким образом запись является двоичной записью искомого числа R.Например, для исходного числа 610 = 1102 результатом является число
10002 = 810, а для исходного числа 410 = 1002 результатом является число 11012 = 1310.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, большее 40. В ответе запишите это число в десятичной системе счисления.

Минимальное R, большее 40, это 41.
В результате выполнения алгоритма число R должно либо начинаться на 10 и оканчиваться 0, либо начинаться на 11 и оканчиваться 1.
Из чисел, больших 41, это 42, 44, 46, 49, и т.д.
Мы должны найти минимальное N, из которого данное число получено.
Поскольку первые цифры заменялись, то мы видим, что данные числа могли быть получены из чисел 29, 30, 23, 16.
Из которых 16 минимальное, и меньше уже быть не может.

ИЛИ программное решение

Ответ: 16

Задание 6. Определение результатов работы простейших алгоритмов

Исполнитель Черепаха действует на плоскости с декартовой системой координат.
В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует две команды:
Вперёд n (где n–целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова, и Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке.
Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что последовательность из S команд повторится k раз.

Черепахе был дан для исполнения следующий алгоритм:
Повтори 7 [Вперёд 10 Направо 120].
Определите, сколько точек с целочисленными координатами будут находиться внутри области, ограниченной линией, заданной данным алгоритмом. Точки на линии учитывать не следует.

ИЛИ

Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует 5 команд: Поднять хвост, означающая переход к перемещению без рисования; Опустить хвост, означающая переход в режим рисования; Вперёд n (где n– целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Назад n (где n– целое число), вызывающая передвижение в противоположном голове направлении; Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке, Налево m (где m– целое число), вызывающая изменение направления движения на m градусов против часовой стрелки.

Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что последовательность из S команд повторится k раз.

Черепахе был дан для исполнения следующий алгоритм:
Повтори 2 [Вперёд 10 Направо 90 Вперёд 20 Направо 90]
Поднять хвост
Вперёд 3 Направо 90 Вперёд 5 Налево 90
Опустить хвост
Повтори 2 [Вперёд 70 Направо 90 Вперёд 80 Направо 90]

Определите, сколько точек с целочисленными координатами будут находиться внутри пересечения фигур, ограниченных заданными алгоритмом линиями, включая точки на границах этого пересечения.

Сначала нужно построить фигуру.
Это можно сделать к примеру, на тетрадном листе, при помощи библиотеки Turtle или в Excel.

Далее мы находим уравнения прямых, которыми ограничена фигура и решаем
систему уравнений программно.

ИЛИ
Фигуру можно построить программно или к примеру, в Excel.
Далее анализируем и считаем точки.

Ответ: 1 задание — 38, 2 задание — 128

Задание 7. Кодирование и декодирование информации. Передача информации

Музыкальный фрагмент был записан в формате моно, оцифрован и сохранён в виде файла без использования сжатия данных. Размер полученного файла – 28 Мбайт. Затем тот же музыкальный фрагмент был записан повторно в формате стерео (двухканальная запись) и оцифрован с разрешением в 3,5 раза выше и частотой дискретизации в 2 раза меньше, чем в первый раз. Сжатие данных не производилось. Укажите размер полученного при повторной записи файла в Мбайт. В ответе запишите только целое число, единицу измерения писать не нужно.

I = ν ⋅ i ⋅ t ⋅ k, где ν — частота дискретизации (Гц),

i — разрешение (бит), t — время (с), k — количество дорожек (1 -моно, 2- стерео, 4 — квадро)

I₁ = ν ⋅ i ⋅ t
I₂ = ν/2 ⋅ 3,5 ⋅ i ⋅ t ⋅ 2 = 3,5 ⋅ I₁

I₂ = 3,5 · 28 = 98

Ответ: 98

Задание 8. Перебор слов и системы счисления

Определите количество пятизначных чисел, записанных в восьмеричной системе счисления, в записи которых только одна цифра 6, при этом никакая нечётная цифра не стоит рядом с цифрой 6.

* * * * * — пятизначное число.
В восьмеричной системе счисления в алфавите 8 цифр: 0..7.
Первая цифра 0 быть не может.
Цифра 6 — одна, при этом стоит рядом только с четными цифрами — 0, 2 или 4.
Получим:

6 * * * * — вариантов 3 ⋅ 7 ⋅ 7 ⋅ 7 = 1029
* 6 * * * — вариантов 2 ⋅ 3 ⋅ 7 ⋅ 7 = 294
* * 6 * * — вариантов 6 ⋅ 3 ⋅ 3 ⋅ 7 = 378
* * * 6 * — вариантов 6 ⋅ 7 ⋅ 3 ⋅ 3 = 378
* * * * 6 — вариантов 6 ⋅ 7 ⋅ 7 ⋅ 3 = 882

Ответ: 2961

Задание выполняется с использованием прилагаемых файлов

Задание 9. Работа с таблицами

Файл с данными

Откройте файл электронной таблицы, содержащей в каждой строке шесть натуральных чисел. Определите количество строк таблицы, содержащих числа, для которых выполнены оба условия:
– в строке только одно число повторяется дважды;
– среднее арифметическое неповторяющихся чисел строки не больше суммы повторяющихся чисел.
В ответе запишите только число.

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

Затем сумму каждой строки диапазона H:M. Если повторений нет, то эта сумма равна 6.

Далее мы найдем среднее арифметическое неповторяющихся значений.

Затем найдем сумму повторяющихся значений.

Затем проверим соблюдение двух условий. И подсчитаем количество строк, в которых соблюдаются оба условия.

Ответ: 2241

Задание выполняется с использованием прилагаемых файлов

Задание 10. Поиск символов в текстовом редакторе

Файл с данными

Текст произведения Льва Николаевича Толстого «Севастопольские рассказы» представлен в виде файлов различных форматов. Откройте один из файлов и определите, сколько раз встречается в тексте отдельное слово «теперь» со строчной буквы. Другие формы этого слова учитывать не следует.
В ответе запишите только число.

В текстовом редакторе используем инструмент найти (по умолчанию он не учитывает регистр, в расширенном поиске есть кнопка больше, где можно проверить настройки). Ищем слово целиком. Ставим галочку учитывать регистр. Слово теперь со строчной буквы встречается 45 раз.

Ответ: 45

Задание 11. Вычисление количества информации

При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 250 символов и содержащий только десятичные цифры и символы из 1650-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит. Определите объём памяти (в Кбайт), необходимый для хранения 65 536 идентификаторов. В ответе запишите только целое число – количество Кбайт.

I = K · i, N = 2 ⁱ

ID : ****….**** – всего 250 различных символов в наборе

N = 10 + 1650 = 1660, 1024<1660<2048, 2048 = 2¹¹, значит для кодирования одного символа нужно 11 бит.

I_ID = 250 · 11 = 2750 бит = 343,75 байт ≈ 344 байт – отводится на идентификатор целое число байт

I₆₅₅₃₆ = 65536 ⋅ 344 = 22544384 байта = 22016 Кбайт– всего

Ответ: 22016

Задание 12. Выполнение алгоритмов для исполнителей

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

А) заменить (v, w). Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w.
Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.

Б) нашлось (v). Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Цикл
    ПОКА условие
        последовательность команд
    КОНЕЦ ПОКА

выполняется, пока условие истинно.

В конструкции

    ЕСЛИ условие
        ТО команда 1
    КОНЕЦ ЕСЛИ

выполняется команда 1 (если условие истинно).

В конструкции

    ЕСЛИ условие
        ТО команда 1
        ИНАЧЕ команда 2
    КОНЕЦ ЕСЛИ

выполняется команда 1 (если условие истинно) или команда 2 (если условие ложно).

Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (>1) ИЛИ нашлось (>2) ИЛИ нашлось (>0)
ЕСЛИ нашлось (>1)
ТО заменить (>1, 22>)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (>2)
ТО заменить (>2, 2>)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (>0)
ТО заменить (>0, 1>)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
На вход приведённой выше программе поступает строка, начинающаяся с символа «>», а затем содержащая 39 цифр «0», n цифр «1» и 39 цифр «2», расположенных в произвольном порядке. Определите наименьшее значение n, при котором сумма числовых значений цифр строки, получившейся в результате выполнения программы, является простым числом.

def pr(n): #функция определяет простое ли число
for i in range(2,int(n**0.5)+1):
if (n%i) == 0:
return False
return True

for n in range(100): #перебираем n
s=’>’ + 39*’0′ + n*’1′ + 39*’2′
while ‘>1’ in s or ‘>2’ in s or ‘>0’ in s:
if ‘>1’ in s:
s=s.replace(‘>1′,’22>’,1)

if ‘>2’ in s:
s=s.replace(‘>2′,’2>’,1)

if ‘>0’ in s:
s=s.replace(‘>0′,’1>’,1)

sum_s = 0
for i in s[:-1]: #считаем сумму цифр в строке
sum_s += int(i)
if pr(sum_s): #проверяем на простоту
print(n)
break

Ответ: 5

Задание 13. Поиск путей в графе

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе Е, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза.

Начнем подсчет из вершины Е налево через В и возвращаемся в Е через Л.

Ответ: 21

Задание 14. Кодирование чисел. Системы счисления

Операнды арифметического выражения записаны в системе счисления с основанием 15.
123x515 + 1x23315
В записи чисел переменной x обозначена неизвестная цифра из алфавита 15-ричной системы счисления. Определите наименьшее значение x, при котором значение данного арифметического выражения кратно 14. Для найденного значения x вычислите частное от деления значения арифметического выражения на 14 и укажите его в ответе в десятичной системе счисления. Основание системы счисления в ответе указывать не нужно.

for x in range(15):
s1=’123’+ str(x) +’5′
s2=’1’+ str(x) +’233′
n= int(s1,15)+ int(s2,15)

if n%14 == 0:
print(n//14)
break

Ответ: 8767

Задание 15. Преобразование логических выражений

На числовой прямой даны два отрезка: D = [17; 58] и C = [29; 80]. Укажите наименьшую возможную длину такого отрезка A, для которого логическое выражение
(x ∈ D) → ((¬(x ∈ C) & ¬(x ∈ A)) → ¬(x ∈ D)) истинно (т.е. принимает значение 1) при любом значении переменной х.

def deli(n,m):
if n%m == 0:
return True

for A in range(1,1000):
Ok = True
for x in range(1,10000):
Ok*=( (not(deli(x,2)) or (not(deli(x,3)))) or ((x+A)>=100) )

if Ok:
print(A)
break

Ответ: 94

Задание 16. Рекурсивные алгоритмы

Алгоритм вычисления значения функции F(n), где n – натуральное число,
задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n × F(n — 1), если n > 1.
Чему равно значение выражения F(2023) / F(2020)?

F(2023) = 2023! = 2023 ⋅ 2022!

F(2023)/F(2020) = (2023 ⋅ 2022 ⋅ 2021 ⋅ 2020!)/2020! = 2023 ⋅ 2022 ⋅ 2021 =

= 8266912626

Ответ: 8266912626

Задание выполняется с использованием прилагаемых файлов

Задание 17. Проверка на делимость

Файл с данными

В файле содержится последовательность целых чисел. Элементы последовательности могут принимать целые значения от –10 000 до 10 000 включительно. Определите количество пар последовательности, в которых
только одно число оканчивается на 3, а сумма квадратов элементов пары не меньше квадрата максимального элемента последовательности, оканчивающегося на 3. В ответе запишите два числа: сначала количество найденных пар, затем максимальную из сумм квадратов элементов таких пар. В данной задаче под парой подразумевается два идущих подряд элемента последовательности.

f= open(’17.txt’)
p=[int(i) for i in f]
f.close()

k = 0
PP = 0
M3 = 0

for i in p:
if (abs(i))%10 == 3:
M3 = max(i, M3)

for i in range(1,len(p)): #Осторожно, скобки!
if ( ((abs(p[i-1])%10 == 3) + ((abs(p[i])% 10 == 3)) ==1 ) and ((p[i-1]**2 + p[i]**2) >= M3**2) ):
k+=1
PP = max(PP, p[i-1]**2 + p[i]**2)

print(k,PP)

Ответ: 180 190360573

Задание выполняется с использованием прилагаемых файлов

Задание 18. Робот-сборщик монет

Файл с данными

Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.

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

Исходные данные представляют собой электронную таблицу размером N×N, каждая ячейка которой соответствует клетке квадрата.Пример входных данных:

1	8	8	4
10	1	1	3
1	3	12	2
2	3	5	6

Для указанных входных данных ответом должна быть пара чисел 41 и 22.

Сначала скопируем таблицу рядом, начиная со столбца АА, можно уменьшить ширину столбца до 4-5. Ячейка АА1=А1. Ячейка АВ1 = АА1+В1, протягиваем ее до АТ1. Ячейка АА2 = АА1 + А2, протягиваем ее до АА20. Далее ячейка АВ2 = В2+МАКС(АА2;АВ1), протягиваем ее на весь оставшийся диапазон, копируем только значения, не трогая стен.

Справа от стен формулы повторяют крайний левый рял, столбец АА, снизу от стен формулы копируют верхнюю строку 1.

Далее делаем замену всех формул МАКС на МИН.

Ответ: 1099 1026

Задание 19. Выигрышная стратегия. Задание 1

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

Игра завершается в тот момент, когда количество камней в куче становится не менее 129. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу из 129 или больше камней.

В начальный момент в куче было S камней, 1 ≤ S ≤ 128. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

При значениях S < 64 у Пети есть возможность сделать такой ход, что Ваня не сможет выиграть своим первым ходом. При значении S = 64 Петя своим первым ходом может получить 65 или 128 камней в куче. Во всех случаях Ваня увеличивает количество камней в куче в два раза и выигрывает своим первым ходом.

Ответ: 64

Задание 20. Выигрышная стратегия. Задание 2

Для игры, описанной в задании 19, найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причем одновременно выполняются два условия:

Петя не может выиграть за один ход;
Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в порядке возрастания.

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

Ответ: 32 63

Задание 21. Выигрышная стратегия. Задание 3

Для игры, описанной в задании 19, найдите значение S, при котором одновременно выполняются два условия:

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

Если найдено несколько значений S, в ответе запишите минимальное из них.

Ответ: 62

Задание 22. Многопроцессорные системы

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор процесса (ID), во второй строке таблицы – время его выполнения в миллисекундах, в третьей строке перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.
Типовой пример организации данных в файле:

Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В независимых процессах время считается от 0,
в зависимых прибавляется к времени процесса, от которого зависит.

Ответ: 17

Задание 23. Анализ программы с циклами и условными операторами

Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 2
Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 35, при этом траектория вычислений содержит число 10 и не содержит 17?
Траектория вычислений программы – это последовательность результатов
выполнения всех команд программы. Например, для программы ABA при
исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

def f(x, y):
if x == y:
return 1
if x > y or x == 17:
return 0
else:
return f(x + 1, y) + f (2 * x, y)

print (f(1,10) * f(10, 35))

Ответ: 98

Задание выполняется с использованием прилагаемых файлов

Задание 24. Анализ программы с циклами и условными операторами

Файл с данными

Текстовый файл состоит из символов A, C, D, F и O. Определите максимальное количество идущих подряд пар символов вида согласная + гласная
в прилагаемом файле. Для выполнения этого задания следует написать программу.

f=open(’24.txt’)
p= f.readline()
f.close()

PP = [‘CA’, ‘CO’, ‘DA’, ‘DO’, ‘FA’, ‘FO’]
M=k=0

for i in range(1, len(p), 2):
x = p[i-1] + p[i]
if x in PP:
k += 1
else:
k = 0
M=max(M,k)
print(M)

Ответ: 95

Задание 25. Анализ программы с циклами и условными операторами

Назовём маской числа последовательность цифр, в которой также могут
встречаться следующие символы:
– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины;
в том числе «*» может задавать и пустую последовательность.

Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 1?2139*4, делящиеся на 2023 без остатка.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 2023. Количество строк в таблице для ответа избыточно.

Самый простой способ использовать библиотеку fnmatch.
Функция fnmatch() проверяет, соответствует ли строка шаблонной строке, возвращая True или False

или так полным перебором:

y = {»,’0′,’00’,’000′}
for x in y:
for j in range(10):
s = ‘1’ + str(j) + ‘2139’ + x + ‘4’
if int(s) % 2023 == 0:
print (s, int(s)//2023)

for x in range (1000):
for j in range(10):
s = ‘1’ + str(j) + ‘2139’ + str(x) + ‘4’
if int(s) % 2023 == 0:
print (s, int(s)//2023

Ответ: 162139404 80148
1321399324 653188
1421396214 702618
1521393104 752048

Задание выполняется с использованием прилагаемых файлов

Задание 26. Анализ программы с циклами и условными операторами

В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д.
Одну коробку можно поместить в другую, если длина её стороны хотя бы на 3 единицы меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.
Входные данные
В первой строке входного файла находится число N – количество коробок в магазине (натуральное число, не превышающее 10 000). В следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000), каждое – в отдельной строке.
Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.
Типовой пример организации данных во входном файле
5
43
40
32
40
30
Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет 3 единицы. При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 32.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

Задание выполняется с использованием прилагаемых файлов

Задание 27. Анализ программы с циклами и условными операторами

У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах вместимостью не более 36 штук. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории.
Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна.
Определите минимальную общую стоимость доставки биоматериалов из всех пунктов приёма в лабораторию.
Входные данные

Файл А
Файл В

Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число N (1 ≤ N ≤ 10 000 000) – количество пунктов приёма биоматериалов. В каждой из следующих N строк находится два числа: номер пункта и количество пробирок в этом пункте (все числа натуральные, количество пробирок в каждом пункте не превышает 1000). Пункты перечислены в порядке их расположения вдоль дороги, начиная от нулевой отметки.
В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.
Типовой пример организации данных во входном файле
6
1 100
2 200
5 4
7 3
8 2
10 190
При таких исходных данных и вместимости транспортировочного контейнера, составляющей 96 пробирок, компании выгодно открыть лабораторию в пункте 2. В этом случае сумма транспортных затрат составит: 1 ∙ 2 + 3 ∙ 1 + 5 ∙ 1 + 6 ∙ 1 + 8 ∙ 2.

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

Ответ: 51063 5634689219329

Источник

Автор — Лада Борисовна Есакова.

Подсчет путей в ориентированном графе. ЗАДАЧА № 15.

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

Рассмотрим простой и эффективный способ решения.

В этой задаче мы имеем дело с ориентированным графом (графом, у которого ребра имеют направление). Т.е. ребра имеют вид стрелок. Две вершины, соединенные напрямую стрелкой, называются смежными. Вершина, из которой выходит стрелка, называется предком, а вершина, в которую входит стрелка – потомком.

Несложно понять, что количество путей, которыми можно попасть в некоторую вершину, равно сумме количеств путей предков этой вершины.

Пример:

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

Решение:

Каждой вершине, начиная с начальной (A), поставим в соответствие индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины A (начало пути) индекс всегда равен 1 (в начало пути можно попасть единственным образом – никуда не двигаясь). Теперь сформулируем правило: индекс вершины равен сумме индексов его предков. Исходя из этого индекс Б равен 1 (предок у Б один – вершина A).

У вершины Д предками являются А и Б, значит индекс вершины Д равен 1+1=2.

Очевидно, что мы можем посчитать индекс только тех вершин, индексы предков которых уже посчитаны. Например, мы не можем посчитать индекс Г, пока не посчитан индекс В. Двигаясь последовательно, мы рассчитаем индексы всех вершин.

Индекс вершины Ж и будет ответом задачи.

Ответ: 11

Благодарим за то, что пользуйтесь нашими статьями.
Информация на странице «Задача №15. Графы. Поиск количества путей.» подготовлена нашими авторами специально, чтобы помочь вам в освоении предмета и подготовке к экзаменам.
Чтобы успешно сдать необходимые и поступить в ВУЗ или колледж нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий.
Также вы можете воспользоваться другими статьями из разделов нашего сайта.

Публикация обновлена:
08.03.2023

Источник

За это задание ты можешь получить 1 балл. На решение дается около 3 минут. Уровень сложности: повышенный.
Средний процент выполнения: 68.7%
Ответом к заданию 15 по информатике может быть цифра (число) или слово.

Разбор сложных заданий в тг-канале

Задачи для практики

Задача 1

На числовой прямой даны два отрезка: P = [18, 63] и Q = [2, 29]. Укажите наименьшую возможную длину такого отрезка A, что логическое выражение

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

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

Решение

1) преобразуем выражение, заменив (x∈A) на А, (x∈P) на P,(x∈Q) на Q

(¬A / P*A) / ¬Q / P

первую скобку преобразуем по формуле поглощения

A / ¬Q / P

2) Строим числовую прямую и отмечаем на ней значения известной части (¬Q / P)

3) Чтобы выражение было истинным на всей числовой оси, необходимо и достаточно, чтобы A ∈ [2, 18], поскольку на этом отрезке известная часть ложна. Длина отрезка = 16

Ответ: 16

Задача 2

Даны множества P = {5, 8, 19, 24, 42, 124}, Q = {3, 8, 12, 24, 64, 127, 211} и A. Элементами множества являются натуральные числа. Известно, что выражение

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

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

Решение

Обозначим $P↖{∼}$: (x ∈ P); $Q↖{∼}$: (x ∈ Q); $A↖{∼}$: (x ∈ A).

Перепишем исходное выражение: ($A↖{∼}$ → ¬($P↖{∼}$ ∨ $A↖{∼}$)) ∨ ¬($Q↖{∼}$ → ¬ $P↖{∼}$).

На основании законов алгебры логики преобразуем это выражение.

($A↖{∼}$ → ¬($P↖{∼}$ ∨ $A↖{∼}$)) ∨ ¬($Q↖{∼}$ → ¬ $P↖{∼}$) ≡

≡ (¬ $A↖{∼}$ ∨ ¬($P↖{∼}$ ∨ $A↖{∼}$)) ∨ ¬(¬$Q↖{∼}$ ∨ ¬ $P↖{∼}$) ≡

≡ ¬ $A↖{∼}$ ∨ (¬ $P↖{∼}$ ∧ ¬ $A↖{∼}$) ∨ ($Q↖{∼}$ ∧ $P↖{∼}$) ≡

≡ ¬ $A↖{∼}$ ∨ ($Q↖{∼}$ ∧ $P↖{∼}$)

Возвращаясь к исходным выражениям, получим: ((x ∉ A) ∨ ((x ∈ Q)) ∧ (x ∈ P)).

Логическое выражение (x ∈ Q)) ∧ (x ∈ P) истинно на промежутке на множестве Q ∩ P = {8, 24}. Согласно условию, нужно выбрать такое множество A, что для любого целого x будет истинным выражение (x ∉ A) ∨ x ∈ {8, 24}. При этом множество A должно содержать наибольшее число элементов.

Таким множеством A является {8, 24}.Сумма элементов этого множества равна 32.

Ответ: 32

Задача 3

На числовой прямой даны два отрезка: P = [1, 70] и Q = [25, 96]. Укажите наибольшую возможную длину такого отрезка A, что логическое выражение

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

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

Решение

Преобразуем выражение:
((x ∈ P) → ((x ∈ Q) ∧ (x ∈ P))) → ¬(x ∈ A) преобразуем импликацию
(¬(x ∈ P) / ((x ∈ Q) ∧ (x ∈ P))) → ¬(x ∈ A) применяем формулу поглощения
(¬(x ∈ P) / (x ∈ Q)) → ¬(x ∈ A) преобразуем импликацию
(x ∈ P) / ¬(x ∈ Q) / ¬(x ∈ A)

Известная часть: (x ∈ P) / ¬(x ∈ Q) истинна на отрезке от 1 до 25.

Чтобы выражение было истинно на всей числовой прямой, необходимо чтобы ¬(x ∈ A) было истинно, поэтому отрезок не должен лежать вне границ отрезка [1, 25], то есть А ∈ [1, 25] и его длина 25 — 1 = 24

Ответ: 24

Задача 4

На числовой прямой даны два отрезка: P = [2, 35] и Q = [12, 54]. Укажите наибольшую возможную длину такого отрезка A, что логическое выражение

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

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

Задача 5

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

$((x^4 < A) → (x ≤ 2)) ∧ ((y < 7) → (y^2 < A))$

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

Задача 6

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

$((x ≤ 6) → (x^2 ≤ A)) ∧ ((y^3 ≤ A) → (y ≤ 3))$

Задача 7

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

$((x · x < A) ∨ (x ≥ 8)) ∧ ((y · y < A) → (y < 8))$

Задача 8

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

$(4 · x + 8 · y ≠ 124) ∨ (x > 3 · A − 1) ∨ (2 · y > A)$

Задача 9

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

(5 · x + 2 · y ≠ 32) ∨ (x > A − ∨ (y > A + 1)

Задача 10

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

$(x + 2 · y ≤ A) ∨ (x > 25) ∨ (y > 12)$

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

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

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

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

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

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

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

Задания с ДЕЛ

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

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

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

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

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

Е15.42 Для какого наименьшего натурального числа А формула (ДЕЛ(x, 2) → ¬ДЕЛ(x, 3)) / (x + A ≥ 100)

Е15.41 для которого формула ((x ∈ Q) ≡ (x ∈ P)) ∨ (¬(x ∈ A) → ((x ∈ P) ∧ ¬(x ∈ Q))) тождественно истинна

Е15.40 выражение (2у + 3х ≠ 135) ∨ (у > А) ∨ (x > A) истинно

Е15.39 формула (x ∈ Q) → (((x ∈ P) ≡ (x ∈ Q)) ∨ (¬(x ∈ P) → (x ∈ A))) тождественно истинна

Е15.38 выражение ((x & 26 ≠ 0) ∨ (x & 13 ≠ 0)) → ((x & 29 = 0) → (x & A ≠ 0)) тождественно истинно

Е15.37 формула (x ∈ Q) → (¬(x ∈ P) → ¬((x ∈ Q) ∧ ¬(x ∈ A))) тождественно истинна

Е15.36 формула ( (x ∈ А) → (x ∈ P) ) / (x ∈ Q) тождественно истинна

Е15.35 ДЕЛ(A, 40) / (ДЕЛ(780, x) → (¬ДЕЛ(A, x) → ¬ДЕЛ(180, x)))

Е15.34 формула x & 85 = 0 → (x & 54 ≠ 0 → x & А ≠ 0) тождественно истинна

Е15.33 формула ((x ∈ P) ∧ ¬(x ∈ A)) → ¬(x ∈ Q) тождественно истинна

Задачи для практики

Задача 1

Решение

Задача 2

Решение

Задача 3

Решение

Задача 4

Задача 5

Задача 6

Задача 7

Задача 8

Задача 9

Задача 10

Рекомендуемые курсы подготовки