Егэ информатика битовые операции

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

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

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

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

x&25 ≠ 0 → (x&17 = 0 → x&А ≠ 0)

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

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

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14 & 5 = 1110₂ & 0101₂ = 0100₂ = 4. Для какого наименьшего неотрицательного целого числа А формула

x & 29 ≠ 0 → (x & 12 = 0 → x & А ≠ 0)

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

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Так, например, 14&5  =  1110₂&0101₂ = 0100₂ = 4.

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

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

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Например, 14&5 = 1110₂&0101₂ = 0100₂ = 4.

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

x&25 ≠ 0 → (x&9 = 0 → x&А ≠ 0)

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

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 29 ноября 2016 года Вариант ИН10203

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Например, 14&5 = 1110₂&0101₂ = 0100₂ = 4.

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

x&25 ≠ 0 → (x&19 = 0 → x&А ≠ 0)

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

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 29 ноября 2016 года Вариант ИН10204

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

Источник

Скачать материал

Сейчас обучается 31 человек из 21 региона

Курс добавлен 16.12.2022
Сейчас обучается 20 человек из 14 регионов

Описание презентации по отдельным слайдам:

1 слайд

Множества и логика Решение задач ЕГЭ (А18, побитовые операции).
2 слайд

Базовые понятия. Задача1 Каким должно быть множество A, чтобы
3 слайд

Базовые понятия. Задача 2 Каким должно быть множество A, чтобы A B
4 слайд

Задача 1 Определите наименьшее натуральное число A такое, что выражение (x & 53 ≠ 0) → ((x & 41 = 0) → (x & A ≠ 0)) тождественно истинно. Решение: Обозначим через DN множество натуральных чисел, для которых побитовая конъюнкция с числом N дает ненулевое значение. DN={x: x & N ≠ 0 }
5 слайд

Преобразуем исходное выражение: Используя правило Моргана получаем:
6 слайд

Таким образом, мы пришли к базовой задаче.
7 слайд

Переведем числа 53 и 41 в двоичную систему счисления. 53=110101 41=101001
8 слайд

Номер бита 5 4 3 2 1 0 53 = 1 1 0 1 0 1 x = a b c d e f x&53 = a b 0 d 0 f Если x & 53 ≠ 0, значит среди битов (5,4,2,0) есть ненулевые
9 слайд

Номер бита 5 4 3 2 1 0 41 = 1 0 1 0 0 1 x = a b c d e f x&41 = a 0 c 0 0 f Если x & 41 = 0, значит биты (5,3,0) числа x нулевые.
10 слайд

Среди битов (4,2) числа x есть ненулевые. Для всех таких чисел x & A ≠ 0, где A может быть любым числом, у которого биты 4 и 2 равны 1. Минимальное из таких чисел 24 + 22 = 20
11 слайд

Задача 2 Определите наибольшее натуральное число A такое, что выражение (x & A ≠ 0) → ((x & 20 = 0) → (x & 5 ≠ 0)) тождественно истинно. Решение: Обозначим через DN множество натуральных чисел, для которых побитовая конъюнкция с числом N дает ненулевое значение. DN={x: x & N ≠ 0 }
13 слайд

Переведем числа 53 и 41 в двоичную систему счисления. 20 = 10100 5 = 101
14 слайд

Номер бита 4 3 2 1 0 20 = 1 0 1 0 0 x = b c d e f x&20 = b 0 d 0 0 Если x & 20 ≠ 0, значит биты (4,2) числа x ненулевые.
15 слайд

Номер бита 2 1 0 5 = 1 0 1 x = a b c x& 5 = a 0 c Если x & 5 ≠ 0, значит биты (2,0) числа x ненулевые.
16 слайд

Объединение этих множеств – это множество чисел, в двоичной записи которых среди битов {4,2,0} есть ненулевые. Это (максимальное) множество определяется условием x & A ≠ 0. Биты (0, 2, 4) числа А могут быть 0 и 1. Чтобы А было максимальным они должны быть равны 1. А= 20+22+24=1+4+16=21
17 слайд

Задачи для самостоятельного решения 1. Для какого наименьшего неотрицательного целого числа А формула (x & 25 ≠ 0) ((x & 17 = 0)  (x & A ≠ 0 )) тождественна истинна, то есть принимает значение 1 при любом неотрицательном целом значении переменной x. Ответ: А = 8
18 слайд

Задачи для самостоятельного решения 2. Определите наименьшее натуральное число А, такое что выражение (x & 15 ≠ 0) ((x & 35 ≠ 0 )  (x & A ≠ 0 )) тождественно истинно. Ответ А=3
19 слайд

Задачи для самостоятельного решения 3. Определите наименьшее натуральное число А, такое что выражение (x & 50 = 0) ((x & 35 ≠ 0 )  (x & A ≠ 0 )) тождественно истинно. Ответ А=16
20 слайд

Задачи для самостоятельного решения 4. Определите наибольшее натуральное число А, такое что выражение (((x & A ≠ 0 )  (x &12 = 0))  ((x & A = 0) (x & 21 ≠ 0) )) v ((x & 21 = 0)  (x & 12 = 0)) тождественно истинно. Ответ А=12
21 слайд

Используемые источники Поляков К.Ю. Подготовка к ЕГЭ по информатике. [Электронный ресурс] / URL: http//www.kpolyakov.spb.ru/school/ege.htm Поляков К.Ю. Множества и логика в задачах ЕГЭ. // Информатика №10, 2015, с. 38-43.

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

6 153 681 материал в базе

Выберите категорию:
Выберите учебник и тему

Выберите класс:
Тип материала:
- Все материалы
- Статьи
- Научные работы
- Видеоуроки
- Презентации
- Конспекты
- Тесты
- Рабочие программы
- Другие методич. материалы

Найти материалы

Другие материалы

21.03.2016
465
0

Рейтинг:
5 из 5

21.03.2016
12512
201

21.03.2016
3859
0

21.03.2016
2067
12

21.03.2016
938
10

21.03.2016
1160
5

21.03.2016
2897
16

Вам будут интересны эти курсы:

Курс повышения квалификации «Информационные технологии в деятельности учителя физики»
Курс повышения квалификации «Сетевые и дистанционные (электронные) формы обучения в условиях реализации ФГОС по ТОП-50»
Курс повышения квалификации «Развитие информационно-коммуникационных компетенций учителя в процессе внедрения ФГОС: работа в Московской электронной школе»
Курс повышения квалификации «Использование компьютерных технологий в процессе обучения в условиях реализации ФГОС»
Курс повышения квалификации «Специфика преподавания информатики в начальных классах с учетом ФГОС НОО»
Курс повышения квалификации «Применение MS Word, Excel в финансовых расчетах»
Курс повышения квалификации «Введение в программирование на языке С (СИ)»
Курс повышения квалификации «Современные тенденции цифровизации образования»
Курс повышения квалификации «Специфика преподавания дисциплины «Информационные технологии» в условиях реализации ФГОС СПО по ТОП-50»

Источник

Подборка по базе: КЛАСТЕРНЫЙ АНАЛИЗ В ЗАДАЧАХ СОЦИАЛЬНО-ЭКОНОМИЧЕСКОГО ПРОГНОЗИРОВ, КР, Решение задач кластеризации в задачах технического зрения , , Справка по операции.pdf, Готовое решение Какими проводками отражаются операции по ка.doc, Карты эскизов к операции 20.doc, Карты эскизов к операции 15.doc, Карта эскизов к операции 25.doc, Карта эскизов к операции 10.doc, Справка по операции.pdf, мат операции матрицы.rtf

19.02.2017
Битовые операции в задачах КИМ ЕГЭ по информатике.
Часть II
К.Ю. Поляков, д.т.н., учитель информатики ГБОУ СОШ № 163, г. Санкт-Петербург
В данной статье рассматриваются задачи следующего типа (впервые эти задачи поя- вились в КИМ на ЕГЭ 2015 года):
Введёмвыражение M & K, обозначающее поразрядную конъюнкцию M и K (логиче- ское «И» между соответствующими битами двоичной записи).
1. Определите наименьшее натуральное число a, такое что выражение
(x &
α
= 0 ) → ((x & 29 = 0) → (x &43≠ 0))
тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной x)?
2. Определите наибольшее натуральное число a, такое что выражение
(x &
α
≠ 0 ) → ((x & 29 = 0) → (x &43≠ 0))
тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной x)?
Предлагается и обосновывается новый подход к решению таких задач, основанный на идее А.В. Здвижковой (г. Армавир).
Обозначения
Через
K
Z
обозначим множество чисел, которые в результате поразрядной конъюнк- ции с числом K дают 0:
}
0
&
:
{
=
=
K
x
x
K
Z
Соответственно, числа, которые в результате поразрядной конъюнкции с числом K дают ненулевое значение, составляют множество
K
Z :
}
0
&
:
{
≠
=
K
x
x
K
Z
Введём утверждения
)
(
)
(
K
K
x
x
Z
Z
∈
=
,
)
(
)
(
K
K
x
x
Z
Z
∈
=
Для сокращения записи будем вместо
)
(x
Z
K
и
)
(x
Z
K
писать соответственно
K
Z
и
K
Z .
Нашей целью будет поиск чисел a, при которых некоторое логическое выражение, зависящее от a, истинно для любых натуральных значений x. Будет обозначать через A выражение
)
(x
Z
a
Два свойства импликации
Сначала докажем два свойства импликации, которые будут нам нужны далее
1
Свойство 1. Следующее равенство тождественно истинно:
)
(
)
(
)
(
C
A
B
A
C
B
A
→
+
→
=
+
→
1
Автору не удалось обнаружить их в известной литературе, хотя они легко доказываются.

К.Ю. Поляков, 2016
2
Доказательство. Представим левую и правую часть равенства через операции ИЛИ и НЕ:
C
B
A
C
B
A
+
+
=
+
→
)
(
C
B
A
C
A
B
A
C
A
B
A
+
+
=
+
+
+
=
→
+
→
)
(
)
(
В обоих случаях получили одинаковые выражения, что и требовалось доказать.
Свойство 2.
Следующее равенство тождественно истинно:
)
(
)
(
)
(
C
A
B
A
C
B
A
→
⋅
→
=
⋅
→
Доказательство. Представим левую и правую часть равенства через операции ИЛИ и НЕ:
C
B
A
C
B
A
⋅
+
=
⋅
→
)
(
C
B
A
C
A
B
A
C
A
B
A
⋅
+
=
+
⋅
+
=
→
⋅
→
)
(
)
(
)
(
)
(
При упрощении второго выражения использован распределительный закон. В результате в обоих случаях получили одинаковые выражения, что и требовалось доказать.
Математическое обоснование метода
В этом разделе мы докажем несколько утверждений, на которых основан предлагаемый метод решения.
Утверждение 1.
Пусть логическое выражение
K
Z
истинно для некоторого нату- рального числа x. Тогда все биты двоичной записи числа x, соответствующие еди- ничным битам двоичной записи числа K, нулевые.
Доказательство. Пусть k
i
– i-ый бит числа K (находящийся в i-м разряде его двоич- ной записи) – равен 1. По условию для числа x истинно логическое выражение
)
0
&
(
)
(
=
=
K
x
x
Z
K
Тогда в результате конъюнкции с соответствующим i-м битом двоичной записи числа x, который обозначим как x
i
, получаем
0
&
=
i
i
k
x
. Поскольку по условию k
i
= 1, это возмож- но только при
0
=
i
x
, что и требовалось доказать.
Утверждение 2.
Логическоевыражение
M
K
Z
Z
→
истинно для всех x тогда и только тогда, когда множество единичных битов двоичной записи числа M входит во мно- жество единичных битов двоичной записи числа K.
Доказательство. Пусть множество единичных битов числа M:
}
,…,
,
{
2 1
q
M
m
m
m
B
=
входит во множество единичных битов числа K:
}
,…,
,
{
2 1
p
K
k
k
k
B
=
и пусть для некоторого x выполняется условие
K
Z
. Это значит, что все биты числа x с но- мерами
p
k
k
k
,…,
,
2 1
равны 0. Поскольку любой единичный бит числа M входит в это мно- жество, истинно также и условие
M
Z
Предположим обратное: условие
M
K
Z
Z
→
истинно для всех x. Пусть при этом один из единичных битов числа M, скажем, бит с номером m
1
, не входит во множество
K
B
. Это

К.Ю. Поляков, 2016
3 значит, что для любого числа x, в котором все биты из множества
K
B
равны 0, а бит m
1
равен 1, высказывание
K
Z
будет истинно, а
M
Z
– ложно, так что высказывание
M
K
Z
Z
→
истинно не для всех x. Получили противоречие, что и доказывает вторую часть утвержде- ния.
Утверждение 3.
Для любого натурального x справедливо равенство:
M
K
M
K
Z
Z
Z
or
)
(
=
⋅
, где or обозначает поразрядную дизъюнкцию между двоичной записью чисел K и M.
Доказательство. Обозначим множества единичных битов чисел K и M через
}
,…,
,
{
2 1
p
K
k
k
k
B
=
, }
,…,
,
{
2 1
q
M
m
m
m
B
=
Пусть одновременно истинны логические выражения
K
Z
и
M
Z
. Тогда логическое выра- жение
N
Z истинно для всех N, у которых множество единичных битов
}
,…,
,
{
2 1
w
N
n
n
n
B
=
таково, что каждый из них входит во множество
K
B
или во множество
M
B
. В частности, одно из таких чисел – это
M
K
N
or
=
Напротив, пусть
M
K
N
or
=
. При этом все единичные биты двоичной записи чисел
K и M входят во множество
N
B . Из утверждения 2 следует, что одновременно истинны выражения
K
Z
и
M
Z
, то есть истинно
M
K
Z
Z
⋅
. Утверждение доказано.
Утверждение 4.
При любых натуральных числах K и M существуют значения x, при которых логическоевыражение
M
K
Z
Z
→
ложно.
Доказательство. Рассмотрим отдельно два случая.
1) Множество единичных битов числа M, }
,…,
,
{
2 1
q
M
m
m
m
B
=
, входит во множество единичных битов числа K,
}
,…,
,
{
2 1
p
K
k
k
k
B
=
. Если при этом истинно
K
Z
, то все биты чис- ла x из множества
K
B
равны нулю. Среди этих битов не может быть ненулевых. Поэтому высказывание
M
K
Z
Z
→
ложно для всех x, для которых истинно
K
Z
2) Множество
M
B
содержит биты, не входящие во множество
K
B
. При этом выска- зывание
M
K
Z
Z
→
ложно для всех x, для которых истинно
K
Z
и, кроме того, все биты, входящие во множество
M
B
, равны нулю.
Утверждение 5.
При любых натуральных числах K и M существуют значения x, при которых логическоевыражение
N
M
K
Z
Z
Z
⋅
→
ложно.
Доказательство. Применим доказанное выше свойство 2 импликации:
)
(
)
(
N
K
M
K
N
M
K
Z
Z
Z
Z
Z
Z
Z
→
⋅
→
=
⋅
→
В силу утверждения 4 второй сомножитель,
N
K
Z
Z
→
, равен нулю хотя бы для некоторых
x, что доказывает утверждение.
Утверждение 6.
Пусть выражение
N
K
Z
Z
→
истинно при любом натуральном x. То- гда выражение
)
(
N
K
Z
A
Z
+
→
истинно для всех x при любом выборе a.

К.Ю. Поляков, 2016
4
Доказательство. Применим доказанное выше свойство 1 импликации:
)
(
)
(
)
(
N
K
K
N
K
Z
Z
A
Z
Z
A
Z
→
+
→
=
+
→
Так как второе слагаемое истинно при любых x, результат не зависит от первого слагаемо- го, то есть от выбора a.
Утверждение 7.
Пусть выражение
N
K
Z
Z
→
ложно при некотором натуральном x.
Тогда выражение
)
(
N
K
Z
A
Z
+
→
истинно для всех x при условии, что
1
=
→ A
Z
K
Доказательство. Применим доказанное выше свойство 1 импликации:
)
(
)
(
)
(
N
K
K
N
K
Z
Z
A
Z
Z
A
Z
→
+
→
=
+
→
Если первое слагаемое истинно при любых x, то и левая часть равенства тоже истинна.
Что и требовалось доказать.
Утверждение 8.
Пусть выражение
M
K
Z
Z
+
истинно при некотором натуральном x.
Тогда истинно выражение
M
K
Z
&
Доказательство. Обозначим множества единичных битов чисел K и M через
}
,…,
,
{
2 1
p
K
k
k
k
B
=
, }
,…,
,
{
2 1
q
M
m
m
m
B
=
Пусть для некоторого x истинно одно из логических выражений,
K
Z
или
M
Z
. Истинность
K
Z
означает, что в числе x биты с номерами
p
k
k
k
,…,
,
2 1
– нулевые, истинность
M
Z
озна- чает, что в числе x биты с номерами
q
m
m
m
,…,
,
2 1
– нулевые. В любом случае биты числа x, номера которых входят в оба множества, и в
}
,…,
,
{
2 1
p
K
k
k
k
B
=
, и в
}
,…,
,
{
2 1
q
M
m
m
m
B
=
, – нулевые. Соответствующее число можно получить как результат поразрядной операции
«И» между числами K и M. Утверждение доказано.
Необходимо отметить, что обратное высказывание неверно: если
M
K
Z
&
истинно, то это совершенно не означает, что истинно
M
K
Z
Z
+
. Контрпример: пусть при K = 3 и M = 5 истинно выражение
1 5
&
3
&
Z
Z
Z
M
K
=
=
, то есть бит 0 числа x равен нулю. Этому условию соответствует любое чётное число, например, x = 6, в котором биты 1 и 2 равны 1, то есть
0
)
6
(
)
6
(
3
=
= Z
Z
K
и
0
)
6
(
)
6
(
5
=
= Z
Z
M
Утверждение 9.
Минимальное натуральное число a, при котором истинновыраже- ние
)
(
M
K
Z
Z
A
+
→
, равно
)
,
min(
M
K
Доказательство. Согласно Свойству 1, представим выражение в виде
)
(
)
(
)
(
M
K
M
K
Z
A
Z
A
Z
Z
A
→
+
→
=
+
→
Как следует из Утверждения 2, при A = K или A = M это выражение равно 1 при всех x, так как, по крайней мере, одно из слагаемых равно 1. Таким образом, при
)
,
min(
M
K
a
=
ут- верждение верно.
Докажем, что нет меньшего подходящего a, используя метод «от противного»: пусть существует такое a, меньшее, чем
)
,
min(
M
K
, при котором
1
)
(
=
+
→
M
K
Z
Z
A
для всех натуральных x.
Поскольку a < K, двоичная запись числа K содержит единичные биты, которых нет в двоичной записи числа a (обозначим это множество битов через
0
K
B ). Поэтому для всех

К.Ю. Поляков, 2016
5 чисел x, у которых все единичные биты числа a также равны 1, но ещё есть единичные би- ты из множества
0
K
B , получаем
0 0
1
=
→
=
→
K
Z
A
Аналогично двоичная запись числа M содержит единичные биты, которых нет в двоичной записи числа a (обозначим это множество через
0
M
B ). Поэтому для всех чисел x, у которых все единичные биты числа a также равны 1, но ещё есть единичные биты из множества
0
M
B , получаем
0 0
1
=
→
=
→
M
Z
A
. Таким образом, для всех чисел, в двоичной записи которых все единичные биты числа a равны 0, но есть ещё единичные биты, вхо- дящие во множества
0
K
B и
0
M
B , оба слагаемых равны 0, так что все выражение ложно. Что и требовалось доказать.
Утверждение 10.
Пусть
0
=
→
M
K
Z
Z
. Тогда
1
)
(
=
+
→
M
K
Z
A
Z
тогда и только то- гда, когда
1
=
→ A
Z
K
Доказательство. Согласно Свойству 1, представим выражение в виде
)
(
)
(
)
(
M
K
K
M
K
Z
Z
A
Z
Z
A
Z
→
+
→
=
+
→
Во-первых, если
1
=
→ A
Z
K
, то сразу
1
)
(
=
+
→
M
K
Z
A
Z
Чтобы доказать обратное, рассмотрим слагаемое
M
K
Z
Z
→
. Обозначим через
K
B множество единичных битов двоичной записи числа K,а через
0
M
B – множество единич- ных битов в двоичной записи числа M, которые равны 0 в двоичной записи числа K.
Выражение
M
K
Z
Z
→
ложно для всех x, в двоичной записи которых все биты из множества
K
B равны 0, а среди битов из множества
0
M
B есть единичные. Если для этих значения x истинно выражение
)
(
M
K
Z
A
Z
+
→
, то это значит, что для них
1
=
→ A
Z
K
Поскольку в двоичной записи всех таких x все биты из множества
K
B равны нулю, то
1
=
→ A
Z
K
для всех натуральных x, что и требовалось доказать.
Утверждение 11.
1
)
(
=
+
→
M
K
Z
A
Z
тогда и только тогда, когда
1
=
→ A
Z
M
K or
Доказательство. Согласно Свойству 1, представим выражение в виде
)
(
)
(
)
(
M
K
K
M
K
Z
Z
A
Z
Z
A
Z
→
+
→
=
+
→
Рассмотрим слагаемое
M
K
Z
Z
→
. Обозначим через
K
B множество единичных битов двоичной записи числа K,а через
M
B – множество единичных битов в двоичной записи числа M. Как следует из доказательства Утверждения 4, выражение
M
K
Z
Z
→
ложно для всех x, в двоичной записи которых все биты из множеств
K
B и
M
B равны 0. Таким обра- зом, выражение
M
K
Z
Z
→
ложно тогда, когда истинно
M
K
Z
or
, и истинно тогда, когда ис- тинно
M
K
Z
or
. Поэтому можно выполнить замену
M
K
Z
Z
→
на
M
K
Z
or
:
A
Z
A
Z
Z
A
Z
Z
Z
A
Z
Z
A
Z
M
K
M
K
K
M
K
K
M
K
K
M
K
→
=
→
⋅
=
+
+
=
+
→
=
+
→
or
or
or
or
)
(
)
(
)
(
Поскольку в силу Утверждения 3 имеем
M
K
M
K
K
Z
Z
Z
or
or
=
⋅
, получаем
A
Z
Z
A
Z
M
K
M
K
→
=
+
→
or
)
(

К.Ю. Поляков, 2016
6
Утверждение 12.
Пусть
0
=
→
L
K
Z
Z
. Тогда
1
)
(
=
⋅
+
→
M
L
K
Z
Z
A
Z
тогда и только тогда, когда
1
=
→ A
Z
K
Доказательство. Представим выражение в виде
)
(
)
(
)
(
M
L
K
K
M
L
K
Z
Z
Z
A
Z
Z
Z
A
Z
⋅
→
+
→
=
⋅
+
→
Во-первых, если
1
=
→ A
Z
K
, то сразу
1
)
(
=
⋅
+
→
M
L
K
Z
Z
A
Z
Чтобы доказать обратное, рассмотрим второе слагаемое, преобразуя его согласно
Свойству 2:
)
(
)
(
)
(
M
K
L
K
M
L
K
Z
Z
Z
Z
Z
Z
Z
→
⋅
→
=
⋅
→
Предположим, что для некоторого a выражение
A
Z
K
→
ложно при некоторых x, но
1
)
(
=
⋅
+
→
M
L
K
Z
Z
A
Z
для всех x. Поскольку
A
Z
K
→
ложно при некоторых x, двоичная запись числа a содержит единичные биты, которые равны 0 в двоичной записи числа K.
Так как по условию двоичная запись числа L содержит единичные биты, которые равны 0 в двоичной записи числа K, то для значений x, в двоичной записи которых эти «лишние» биты равны 1, имеем
0
=
→
L
K
Z
Z
, так что всё выражение равно 0. Получили противоре- чие. Следовательно,
1
=
→ A
Z
K
Утверждение 13.
Пусть
1
=
→
L
K
Z
Z
. Тогда
1
)
(
=
⋅
+
→
M
L
K
Z
Z
A
Z
тогда и только тогда, когда
1
=
→ A
Z
M
K or
Доказательство. Используя доказанные выше утверждения, преобразуем выраже- ние:
M
K
L
K
K
M
K
L
K
K
M
L
K
K
M
L
K
Z
Z
Z
A
Z
Z
Z
Z
Z
A
Z
Z
Z
Z
A
Z
Z
Z
A
Z
or
⋅
→
+
→
=
→
⋅
→
+
→
=
=
⋅
→
+
→
=
⋅
+
→
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
Поскольку по условию множество единичных битов двоичной записи числа L явля- ется подмножеством множества единичных битов числа K, то
1
=
→
L
K
Z
Z
для всех x. По- этому выражение далее преобразуется так же, как и при доказательстве Утверждения 11:
1 1
1 1
)
(
=
→
=
+
⋅
=
+
+
=
+
→
A
Z
A
Z
Z
Z
A
Z
Z
A
Z
M
K
M
K
K
M
K
K
M
K
K
or
or
or
or
что и требовалось доказать.
Общий метод решения
Идея метода решения, предложенная А.В. Здвижковой, состоит в следующем:
1) упростить логическое выражение так, чтобы свести его к импликации и избавиться от всех инверсий;
2) применить утверждения 3-7 с целью свести задачу к форме, в которой можно исполь- зовать утверждение 2.
Упрощение может привести к нескольким разным формам выражения, например,

К.Ю. Поляков, 2016
7 1)
N
K
Z
A
Z
→
⋅ )
(
2)
A
Z
K
→
3)
)
(
N
K
Z
A
Z
+
→
4)
)
(
N
K
Z
A
Z
⋅
→
В первом случае
a
K
K
Z
A
Z
or
=
⋅
, так что с помощью числа a можно добавить в левую часть единичные биты числа N, которых нет во множестве единичных битов числа K.
Во втором случае согласно утверждению 2 число a должно быть выбрано так, чтобы все его единичные биты входили во множество единичных битов числа K.
В третьем случае с помощью утверждений 6 и 7 можно либо свести задачу ко второ- му случаю, либо придти к выводу от том, что число a можно выбрать произвольно.
В четвёртом случае решение не всегда существует: с помощью числа a можно доба- вить в правую часть единичные биты, но нельзя их убрать. Поэтому если множество еди- ничных битов числа N не является подмножеством единичных битов числа K, задача не имеет решения (при любом выборе a выражение будет ложно при некоторых значениях x).
Примеры
Пример 1
. Определите наименьшее натуральное число a, такое что выражение
(x & 53
≠ 0) → ((x & 41 = 0) → (x & a ≠ 0)) тождественно истинно.
Решение. Используя обозначения, приведенные в начале статьи, запишем выражение в виде
)
(
41 53
A
Z
Z
→
→
. Упрощаем выражение, раскрывая импликации по формуле
B
A
B
A
+
=
→
:
A
Z
Z
A
Z
Z
A
Z
Z
+
+
=
→
+
=
→
→
41 53 41 53 41 53
)
(
)
(
Теперь избавляемся от инверсий, применяя закон де Моргана и переходя к импликации:
53 41 53 41 41 53
)
(
)
(
Z
A
Z
Z
A
Z
A
Z
Z
→
⋅
=
+
⋅
=
+
+
Применяем утверждение 3:
53
or
41 53 41
)
(
Z
Z
Z
A
Z
a
→
=
→
⋅
Таким образом, с помощью числа a мы должны добавить в левую часть недостающие би- ты – те, которые есть в двоичной записи числа 53, но отсутствуют в двоичной записи чис- ла 41: разряды
5 4 3 2 1 0 41 = 101001 53 = 110101
Биты, которые обязательно должны быть в числе a – это биты в разрядах 4 и 2 (выделены фоном), поэтому минимальное значение числа a
min
= 2 4
+ 2 2
= 20. Можно выбрать и любое другое значение a, в двоичной записи которого эти биты равны 1.
Пример 2
. Определите наибольшее натуральное число a, такое что выражение
(x & a
≠ 0) → ((x & 20 = 0) → (x &5≠ 0))

К.Ю. Поляков, 2016
8 тождественно истинно.
Решение. Используя обозначения, приведенные в начале статьи, запишем выражение в виде
)
(
5 20
Z
Z
A
→
→
. Упрощаем выражение, раскрывая импликации по формуле
B
A
B
A
+
=
→
:
5 20 5
20 5
20
)
(
)
(
Z
Z
A
Z
Z
A
Z
Z
A
+
+
=
→
+
=
→
→
Теперь избавляемся от инверсий, применяя закон де Моргана и переходя к импликации:
A
Z
Z
A
Z
Z
Z
Z
A
→
⋅
=
+
⋅
=
+
+
)
(
)
(
5 20 5
20 5
20
Согласно утверждению 3,
5
or
20 5
20
Z
Z
Z
=
⋅
. Вычисляем разряды
4 3 2 1 0 20 = 10100 5 = 00101 20 or 5 = 10101 = 21
Таким образом, получили
1 21
=
→ A
Z
. Согласно утверждению 2, все единичные биты числа а должны присутствовать в числе 21. Поэтому максимальное значение a
max
= 21.
Кроме того, можно взять и другие значения a, которые не содержат в двоичной записи других единичных битов, кроме 4-го, 2-го и 0-го (это 1, 4, 5, 16, 17 и 20).
Пример 3
. Определите наибольшее натуральное число a, такое что выражение
(x & a
≠ 0) → ((x & 12 = 0) → (x &21= 0)) тождественно истинно.
Решение. Используя обозначения, приведенные в начале статьи, запишем выражение в виде
)
(
21 12
Z
Z
A
→
→
. Упрощаем выражение, раскрывая импликации по формуле
B
A
B
A
+
=
→
:
21 12 21 12 21 12
)
(
)
(
Z
Z
A
Z
Z
A
Z
Z
A
+
+
=
→
+
=
→
→
Теперь избавляемся от инверсий, переходя к импликации:
)
(
21 12 21 12
Z
A
Z
Z
Z
A
+
→
=
+
+
Согласно свойству 1 импликации,
)
(
)
(
)
(
21 12 12 21 12
Z
Z
A
Z
Z
A
Z
→
+
→
=
+
→
. Двоичная за- пись числа 21 = 10101 2
содержит единичные биты, которые не входят во множество еди- ничных битов числа 12 = 1100 2
. Поэтому по утверждению 7 задача сводится к обеспече- нию условия
1 12
=
→ A
Z
Согласно утверждению 2, все единичные биты числа a должны присутствовать в числе 12. Поэтому максимальное значение a
max
= 12. Кроме того, можно взять и другие значения a, которые не содержат в двоичной записи других единичных битов, кроме 3-го и 2-го (это 4, 8 и 12).
Пример 4
. Определите наименьшее натуральное число a, такое что выражение
( (x &28
≠ 0) ∨ (x & 45 ≠ 0)) → ((x & 48 = 0) → (x & a ≠ 0)) тождественно истинно.
Решение. Используя обозначения, приведенные в начале статьи, запишем выражение в виде
)
(
)
(
48 45 28
A
Z
Z
Z
→
→
+
. Упрощаем выражение, раскрывая импликации:

К.Ю. Поляков, 2016
9
A
Z
Z
Z
A
Z
Z
Z
A
Z
Z
Z
+
+
⋅
=
→
+
+
=
→
→
+
48 45 28 48 45 28 48 45 28
)
(
)
(
)
(
Теперь избавляемся от инверсий, используя закон де Моргана и переходя к импликации:
)
(
)
(
45 28 48 45 28 48 48 45 28
Z
Z
A
Z
Z
Z
A
Z
A
Z
Z
Z
⋅
→
⋅
=
⋅
+
⋅
=
+
+
⋅
Упрощаем выражение в правой части, используя утверждение 3:
45
or
28 45 28
Z
Z
Z
=
⋅
. Вычис- ляем: разряды
5 4 3 2 1 0 28 = 011100 45 = 101101 28 or 45 = 111101 = 61
Нам нужно обеспечить истинность выражения
61 48
)
(
Z
A
Z
→
⋅
при всех x. Согласно утвер- ждению 2 для этого необходимо, чтобы множество битов числа 61 входило во множество битов числа 48 or a, то есть с помощью a мы можем добавить недостающие биты: разряды
5 4 3 2 1 0 48 = 110000 61 = 111101
Биты, которые обязательно должны быть в числе a – это биты в разрядах 3, 2 и 0 (выделе- ны фоном), поэтому минимальное значение числа a
min
= 2 3
+ 2 2
+ 2 0
= 13. Можно выбрать и любое другое значение a, в двоичной записи которого эти биты равны 1.
Пример 5
. (А.Г. Гильдин). Определите наибольшее натуральное число a, такое что выражение
(x &19= 0)
∧ (x & 38 ≠ 0) ∨ ((x & 43 = 0) → ((x & a = 0) ∧ (x & 43 = 0))) тождественно истинно.
Решение. Используя обозначения, приведенные в начале статьи, запишем выражение в виде
))
(
(
43 43 38 19
Z
A
Z
Z
Z
⋅
→
+
⋅
. Упрощаем выражение, приводя его к импликации:
))
(
)
((
38 19 43 43
Z
Z
Z
A
Z
⋅
+
⋅
→
Согласно свойству 1 импликации,
)
(
)
(
))
(
)
((
38 19 43 43 43 38 19 43 43
Z
Z
Z
Z
A
Z
Z
Z
Z
A
Z
⋅
→
+
⋅
→
=
⋅
+
⋅
→
По утверждению 12, второе слагаемое в правой части можно отбросить, поэтому остается обеспечить истинность выражения
43 43
Z
A
Z
⋅
→
В силу утверждений 3 и 2, множество единичных битов числа a or 43 должно вхо- дить во множество единичных битов числа 43. Поэтому число a может содержать единич- ные биты только в тех разрядах, где они есть в двоичной записи числа 43. Таким образом,
a
max
= 43. Кроме этого, можно использовать и другие значения a, все единичные биты ко- торых входят во множество единичных битов числа 43: это 1, 2, 3, 8, 9, 10, 11, 32, 33, 34,
35, 40, 41, 42 и 43.
Пример 6
. (М.В. Кузнецова). Определите наибольшее натуральное число a, такое что выражение
(( (x &13
≠ 0) ∨ (x & a ≠ 0)) → (x & 13 ≠ 0) ∨ ((x & a ≠ 0) ∧ (x & 39 = 0))

К.Ю. Поляков, 2016
10 тождественно истинно.
Решение. Используя обозначения, приведенные в начале статьи, запишем выражение в виде
39 13 13
)
)
((
Z
A
Z
A
Z
⋅
+
→
+
. Упрощаем выражение, раскрывая импликацию:
39 13 13 39 13 13 39 13 13
)
)
((
Z
A
Z
A
Z
Z
A
Z
A
Z
Z
A
Z
A
Z
⋅
+
+
⋅
=
⋅
+
+
+
=
⋅
+
→
+
Применяем распределительный закон
13 13 13 13 13 13
)
(
)
(
Z
A
Z
A
Z
Z
Z
A
Z
+
=
+
⋅
+
=
+
⋅
Получаем
39 13 39 13 13
Z
A
Z
A
Z
A
Z
A
Z
⋅
+
+
=
⋅
+
+
⋅
Используем распределительный закон ещё раз
39 39 39
)
(
)
(
Z
A
Z
A
A
A
Z
A
A
+
=
+
⋅
+
=
⋅
+
так что выражение сводится к
39 13
Z
Z
A
+
+
. Теперь избавляемся от инверсий, переходя к импликации:
)
(
39 13 39 13
Z
A
Z
Z
Z
A
+
→
=
+
+
По свойству 1 импликации имеем
)
(
)
(
)
(
39 13 13 39 13
Z
Z
A
Z
Z
A
Z
→
+
→
=
+
→
Поскольку число 39 = 100111 2
содержит единичные биты, которых нет в числе 13 = 1101 2
, второе слагаемое,
39 13
Z
Z
→
, равно 0 (ложно для каких-то x), поэтому остается обеспечить только равенство
1 13
=
→ A
Z
. В силу утверждения 2, для этого требуется, чтобы двоичная запись числа a имела единичные биты только там, где есть единичные биты в числе 13.
Поэтому a
max
= 13.
Кроме того, условие выполнено при выборе a = 1, 4, 5, 8, 9, 12 и 13. Количество этих решений несложно подсчитать. Число 13 содержит m = 3 ненулевых бита, в числе a каж- дый из них может быть равен 0 или 1. Поэтому общее количество возможных комбинаций равно 2
m
. Учитывая, что нас интересуют только натуральные числа, нельзя выбрать все эти биты нулевыми, поэтому один вариант исключается. Итог: количество решений на множестве натуральных чисел равно 2
m
–1.
Отметим, что если в этой задаче вместо чисел 13 и 39 взять, например, числа 53 и 21, то выражение истинно при любом выборе a (см. утверждение 6). Это связано с тем, что все единичные биты числа 21 = 10101 2
входят во множество единичных битов числа
53 = 110101 2
Пример 7
. Определите наибольшее натуральное число a, такое что выражение
((x &46= 0)
∨ (x & 18 = 0)) → ((x & 115 ≠ 0) → (x & a = 0))) тождественно истинно.
Решение. Используя обозначения, приведенные в начале статьи, запишем выражение в виде
)
(
)
(
115 18 46
A
Z
Z
Z
→
→
+
. Упрощаем выражение, раскрыв вторую импликацию и из- бавившись от инверсий:
)
(
)
(
115 18 46
A
Z
Z
Z
+
→
+
Преобразуем левую часть согласно Утверждению 8:

К.Ю. Поляков, 2016
11 2
18
&
46 18 46
Z
Z
Z
Z
=
⇒
+
и получаем таким образом (с помощью свойства 1 импликации)
)
(
)
(
)
(
2 115 2
115 2
A
Z
Z
Z
A
Z
Z
→
+
→
=
+
→
Первая импликация в сумме равна 0, так как двоичная запись числа 115 содержит единич- ные биты, которых нет в двоичной записи числа 2. Поэтому требуется обеспечить истин- ность второй импликации,
A
Z
→
2
. Для этого множество единичных битов числа a долж- но входить во множество единичных битов числа 2 (а это единственный бит в 1-м разря- де). Поэтому единственное натуральное число a, удовлетворяющее условию – это 2.
Пример 8
. Определите наименьшее натуральное число a, такое что выражение
((x &23
≠ 0) ∧ (x & 45 ≠ 0)) → ((x & a ≠ 0) ∧ (x & 23 ≠ 0)) тождественно истинно.
Решение. Используя обозначения, приведенные в начале статьи, запишем выражение в виде
)
(
)
(
23 45 23
Z
A
Z
Z
⋅
→
⋅
. Упрощаем выражение, раскрывая импликацию и избавляясь от инверсий:
=
+
+
⋅
+
=
⋅
+
+
=
⋅
+
⋅
45 23 23 23 23 45 23 23 45 23
)
(
)
(
Z
Z
Z
A
Z
Z
A
Z
Z
Z
A
Z
Z
)
(
45 23 45 23
Z
Z
A
Z
A
Z
+
→
=
+
+
=
Преобразуем левую часть согласно Свойству 1 импликации:
)
(
)
(
)
(
45 23 45 23
Z
A
Z
A
Z
Z
A
→
+
→
=
+
→
Таким образом, нужно обеспечить выполнение для всех x одного из условий:
1 23
=
→ Z
A
или
1 45
=
→ Z
A
Первое из них верно при минимальном значении 23, второе – при минимальном значении
45. Поэтому в качестве ответа выбираем наименьшее из двух – 23.
У этой задачи возможно интересное продолжение – давайте найдем все решения,
меньшие 100
. Сначала найдём все решения уравнения
1 23
=
→ Z
A
. Учитывая, что разряды
6 5 4 3 2 1 0 23 = 0010111 биты 0, 1, 2 и 4 нужно обязательно сохранить. К ним можно добавить бит 3 (получается
23+8=31), бит 5 (23+32=55), биты 4 и 5 (23+32+8=63), бит 6 (23+64=87), биты 6 и 3
(23+64+8=95), остальные подходящие значения больше 100.
Теперь найдём все решения уравнения
1 45
=
→ Z
A
. Запишем 45 в двоичной системе счисления: разряды
6 5 4 3 2 1 0 45 = 0101101
Рассуждая аналогично, добавляем биты 1 (45+2=47), 4 (45+16=61), 4 и 1 (45+16+2=63), остальные значения получаются больше 100.
В итоге получается такой список всех возможных значений a, меньших 100:
23, 31, 45, 47, 55, 61, 63, 87, 95.

К.Ю. Поляков, 2016
12
Литература
1. К.Ю. Поляков, Множества и логика в задачах ЕГЭ // Информатика, № 10, 2015, с.
38-42.
2. К.Ю. Поляков, Битовые операции в задачах КИМ ЕГЭ по информатике. Электрон- ный ресурс [URL: http://kpolyakov.spb.ru/download/bitwise.pdf
] Дата обращения:
06.11.2016.

Источник

На уроке рассматривается разбор 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

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

Источник

Что это такое?

Здесь представлены материалы для подготовки к ЕГЭ по информатике.
В отличие от известной литературы, для большинства задач из демо-вариантов ЕГЭ
сравниваются несколько способов решения,
анализируются их достоинства и недостатки, возможные проблемы и
«ловушки». Приведены рекомендации, позволяющие выбрать
эффективные методы решения каждой конкретной задачи.

Автор признателен
О.А. Тузовой (г. Санкт-Петербург) за обсуждение
этих материалов и конструктивную критику. Спасибо всем, кто присылал и
присылает мне замечания, предложения, сообщения об опечатках и неточностях.

Особая благодарность Н.Н. Паньгиной (г. Сосновый Бор) за
взаимовыгодное сотрудничество и разностороннюю поддержку проекта.

Автор будет благодарен за новые отзывы по поводу представленных
здесь материалов для подготовки к ЕГЭ по информатике.
Если вы заметили ошибку или у вас просто есть что
сказать по существу вопроса, пишите.

Тренажёр компьютерного ЕГЭ

ЕГЭ по информатике в 2023 году будет проводиться в компьютерной форме.
На этом сайте вы можете попробовать, как это будет выглядеть в
тренажёре. Он является копией официального тренажёра,
но позволяет загружать любой вариант из генератора. Кроме того, после завершения
пробного экзамена вы узнаете, сколько баллов вы набрали бы на ЕГЭ, если бы
отправили такие ответы. Попробуйте:

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

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

Робот-Blockly

Робот-Blockly — это версия исполнителей Робот и Водолей,
программы для которых составляются из готовых блоков, как в Scratch. Это избавляет учеников от
синтаксических ошибок, которые неминуемо возникают при ручном наборе текстовой программы.
Программа подходит для вводного курса алгоритмизации в 5-6 (и даже более старших) классах.
У программы есть оффлайн-версия, которую можно использовать
без доступа к Интернету. Вы можете создавать свои наборы задач, а
не только использовать готовые.

Коллеги тащат то, что не приколочено…

Мартынов Антон Иванович, председатель предметной комиссии по информатике Ульяновской области,
опубликовал представленные здесь рекомендации по решению задач части C под своим именем в
официальном аналитическом отчете (Ульяновск, 2009).

Актуальные публикации

В.С. Попов.

Новая задача ЕГЭ по информатике № 22: решение с помощью графа
// Потенциал: Математика, Физика, Информатика, № 8, 2022.
К.Ю. Поляков.

Особенности решения задач 25 и 26 в компьютерном
ЕГЭ по информатике. Материалы вебинара для учителей г. Сочи, 24.03.2021.
К.Ю. Поляков.

Динамическое программирование в задачах обработки последовательностей ЕГЭ по информатике.
К.Ю. Поляков.

Задачи на анализ логических выражений в ЕГЭ по информатике. //
Информатика в школе, № 9, 2019, с. 29–35.
А.Н. Сидоров

Задача 18 ЕГЭ по информатике: логическое выражение с делимостью.
Н.Л. Конина

Задачи 18 с делимостью.
Н.И. Герасименко

Задачи 18 с делителями в КИМ ЕГЭ по информатике.
К.Ю. Поляков

Линейное (и нелинейное) программирование в задаче 18 ЕГЭ по информатике (презентация).
К.Ю. Поляков,

Битовые операции в задаче 18 КИМ ЕГЭ по информатике. Часть 2.
К.Ю. Поляков,

Множества и логика в задачах ЕГЭ //
Информатика, № 10, 2015, с. 38-42.
Е.А. Мирончик.

Алгебра предикатов и построение геометрических моделей на ЕГЭ по информатике //
Информатика, № 3, 2019, с. 40-47.

См. также полный список статей.

Что еще посмотреть?

Тренажёр для подготовки к компьютерному ЕГЭ
Тесты для подготовки к ЕГЭ (для системы NetTest)
Онлайн-тесты для подготовки к ЕГЭ
Генератор тренировочных вариантов ЕГЭ
Программное обеспечение
Статьи, презентации
Видеоматериалы
Дополнительные материалы
Материалы прошлых лет (демо-варианты, анализ, разбор задач)
Вопросы и ответы
Отзывы

Новости теперь и в
Telegram-канале

9 марта 2023 г.
Исправлено условие задаче 8.330.
Исправлен ответ к задаче 14.403.

5 марта 2023 г.
Новые задачи для тренировки 8, 9.

4 марта 2023 г.
    Новые задачи для тренировки 14.
    Новые задачи для тренировки 1-3, 7-9, 12-16, 19-25, 27 (А. Богданов).
    Новая задача для тренировки 8 (А. Малышев).
    Новая задача для тренировки 17 (Д. Статный).

3 марта 2023 г.
Новые задачи для тренировки 26.
Новые задачи для тренировки 23 (Д. Муфаззалов).

2 марта 2023 г.
Новые задачи для тренировки 27.

28 февраля 2023 г.
Новая задача для тренировки 27 (А. Бойко).

25 февраля 2023 г.
    Новые задачи для тренировки 17 (И. Митин).
    Новые задачи для тренировки 23, 24, 25.
    Новые задачи для тренировки 23 (М. Шагитов).
    Новая задача для тренировки 27 (А. Рогов).

24 февраля 2023 г.
Новые задачи для тренировки 25, 26 (А. Рогов).

23 февраля 2023 г.
Изменено условие и ответ к задаче 26.94.

Приложение для ОС Android

Багрепорты, замечания, предложения можно присылать на
форум.

Официальные материалы

Тренажёры для подготовки к компьютерному ЕГЭ (КЕГЭ)

Лицензионное соглашение

Все опубликованные ниже материалы для
подготовки к ЕГЭ по информатике могут быть свободно использованы
в некоммерческих целях при условии сохранения авторства.

Без письменного согласия автора ЗАПРЕЩАЕТСЯ:

1) публикация материалов в любой форме, в том числе размещение материалов на других Web-сайтах;
2) распространение неполных или измененных материалов;
3) включение материалов в сборники на любых носителях информации;
4) получение коммерческой выгоды от продажи или другого использования материалов.

Использование и скачивание материалов означает, что вы приняли условия этого лицензионного соглашения.

Описание презентации по отдельным слайдам:

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

Другие материалы

Вам будут интересны эти курсы:

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

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

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

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

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

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

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

Задания с ДЕЛ

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

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

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

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

Что это такое?

Тренажёр компьютерного ЕГЭ

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

Робот-Blockly

Коллеги тащат то, что не приколочено…

Актуальные публикации

Что еще посмотреть?

Новости теперь и в
Telegram-канале

Приложение для ОС Android

Официальные материалы

Тренажёры для подготовки к компьютерному ЕГЭ (КЕГЭ)

Лицензионное соглашение

Скачать все сразу

Информация

Системы счисления

Логика

Пользовательский курс

Алгоритмизация и основы программирования

Ответы и решения