Решение задания 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

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

Источник

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

Версия для печати и копирования в 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 заданию из ЕГЭ по информатике 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)

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

Источник

ЕГЭ информатика 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

Источник

За это задание ты можешь получить 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

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