Задание 18 ЕГЭ по информатике 2018

Задание 18. Элементы математической логики и теория множеств: Разбор досрочного егэ по информатике 2018, демонстрационный вариант ЕГЭ по информатике 2018; государственный выпускной экзамен 2018; тренировочные варианты ЕГЭ по информатике, тематические тестовые задания и задачи из тренажера по информатике 2018

*** КАНАЛ ЮТЬЮБ ***
 
ЕГЭ по информатике -> ЕГЭ 2018 -> ЕГЭ 2018 — 18
 

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

Для какого наибольшего целого числа А формула
демоверсия егэ 2018 решение 18 задания
тождественно истинна, то есть принимает значение 1 при любых целых неотрицательных x и y?

📹 Видеоразбор

✍ Показать решение:

  • Условно разделим исходное выражение на части:
  • решение 18 задания демоверсии егэ информатика

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

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

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

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

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

  • таким образом, получаем:
  • x <= 9
    x2 <= A
    
    при любых x
    
  • так как нам необходимо найти наибольшее возможное А, то, значит, надо ограничить его значения сверху, а данная часть выражения ограничивает только снизу:
  • возьмем наименьшее натуральное: x=1, тогда A>=1

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

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

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

  • таким образом, получаем:
  • y > 9
    y2 > A
    
    при любых y
    
  • данная часть выражения ограничивает значения А сверху:
  • возьмем наименьшее возможное по условию натуральное: y = 10, тогда A < 100
  • Получаем, что наибольшее А меньшее 100: А = 99

Результат: 99

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

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

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

&A ≠ 0 → (x&10 = 0 → x&3 ≠ 0)

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

✍ Показать решение:

    ✎ Способ 1:

  • Произведем замену:
  • z10 = (x&10 = 0), z3 = (x&3 = 0), A = (x&A = 0)
    
  • Перепишем выражение:
  • ¬A → (z10 → ¬ z3)
    
  • Избавимся от импликации (A → B = ¬ A ∨ B):
  • Сначала по правилу преобразования импликации:
  • ¬A → (z10 → ¬ z3) = A + ¬z10 + ¬Z3 
    
  • По Закону де Моргана вынесем отрицание за скобки (¬ (A ∧ B) = ¬ A ∨ ¬ B):
  • A + ¬z10 + ¬z3 = A + ¬(z10 * z3)
    
  • Вернемся опять к импликации:
  • A + ¬(z10 * z3) = ¬(z10 * z3) + A = (z10 * z3) → A
    
  • Суть предыдущих действий в том, что нам необходимо прийти к импликации, но, избавившись от отрицания.
  • По следующему правилу ZK * ZM = ZK or M (К. Поляков) заменим конъюнкцию:
  • z10 * z3 = z10 or 3
  • Выполним поразрядную дизъюнкцию двоичных чисел 10 и 3:
  • 1010 -> 10
    0011 -> 3
    1011 -> 10 or 3 = 1110
    
  • Получаем:
  • z11 → A
    
  • Необходимо обеспечить истинность данного выражения при всех x. Это возможно, когда единичные биты A входят в единичные биты числа 11. То есть:
  • A = 10112 = 1110

    ✎ Способ 2:

  • Введем обозначения:
  • P = (x&10 = 0), Q = (x&3 = 0), A = (x&A = 0)
    
  • Перепишем выражение:
  • ¬A → (P → ¬Q) 
    
  • Избавимся от импликации:
  • A + ¬P + ¬Q
    
  • В выражении красным выделена известная часть (ее можно найти). Операция дизъюнкция (логическое сложение) проще находится, когда выражение ложно (=0). Так как результатом дизъюнкции ложь является только в одном случае: 0 + 0 = 0. Поэтому примем выделенную часть за 0.
  • Чтобы формула была истинна при любых x, нужно, чтобы ¬P + ¬Q = 0 и при этом A = 1.
  • По таблице истинности дизъюнкции имеем:
  • если ¬P + ¬Q = 0, то P = Q = 1
    
  • Таким образом, необходимо, чтобы P = Q = 1. Подставим в побитовую маску, с учетом введенных обозначений:
  • P = (x&10 = 0):
    3 2 1 0 - номер бита
    1 0 1 0 - 10
    0 * 0 * - x (маска)
    0 0 0 0 - x&10
    
    Q = (x&3 = 0):
    3 2 1 0 - номер бита
    0 0 1 1 - 3
    * * 0 0 - x (маска)
    0 0 0 0 - x&3
    
  • Пояснение: чтобы в результате поразрядной конъюнкции получить 0, в тех разрядах, в которых стоит единица, в маске x необходимо поставить 0.
  • общая маска х:
    0 * 0 0
  • Сопоставив обе маски, получаем, что в x биты 0, 1 и 3 - нулевые, значит, для x & A они должны быть единичные (так как по заданию требуется найти наибольшее А).
  • 0 * 0 0     общая маска х:
    1 0 1 1     x & A = 0
    
  • Переведем результат в десятичную систему:
  • 10112 = 1110

Результат: 11

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

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

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

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

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

📹 Видеоразбор

✍ Показать решение:

    ✎ Способ 1:

  • Произведем замену:
  • z36 = (x&36 = 0), z6 = (x&6 = 0), A = (x&A = 0)
    
  • Перепишем выражение:
  • ¬A → (z36 → ¬ z6)
    
  • Избавимся от импликации (A → B = ¬ A ∨ B):
  • Сначала по правилу преобразования импликации:
  • ¬A → (z36 → ¬ z6) = A + ¬z36 + ¬z6 
    
  • По Закону де Моргана вынесем отрицание за скобки (¬ (A ∧ B) = ¬ A ∨ ¬ B):
  • A + ¬z36 + ¬z6 = A + ¬(z36 * z6)
    
  • Вернемся опять к импликации:
  • A + ¬(z36 * z6) = ¬(z36 * z6) + A = (z36 * z6) → A
    
  • Суть предыдущих действий в том, что нам необходимо прийти к импликации, но, избавившись от отрицания.
  • По следующему правилу ZK * ZM = ZK or M (К. Поляков) заменим конъюнкцию:
  • z36 * z6 = z36 or 6
  • Выполним поразрядную дизъюнкцию двоичных чисел 10 и 3:
  • 1001002 -> 36
    1102 -> 6
    1001102 -> 36 or 6 = 3810
    
  • Получаем:
  • z38 → A
    
  • Необходимо обеспечить истинность данного выражения при всех x. Это возможно, когда единичные биты A входят в единичные биты числа 38. То есть:
  • A = 1001102 = 3810

     
    ✎ Способ 2:

  • Так как по заданию формула должна быть тождественно истинна, то перепишем ее так:
  • x&A ≠ 0 → (x&36 = 0 → x&6 ≠ 0) = 1
  • Введем обозначения:
  • A = (x&A = 0);
    P = (x&36 = 0);
    Q = (x&6 = 0);
    
  • Перепишем выражение согласно введенным обозначениям:
  • ¬A → (P → ¬Q) = 1
    
  • Избавимся от импликации:
  • A ∨ (¬P ∨ ¬Q) = 1
    
  • A - наше неизвестное; для части выражения ¬P ∨ ¬Q нам необходимо подобрать такой вариант (равный 0 или 1), при котором единственно возможным значением A была бы единица (1).
  • Возьмем (¬P ∨ ¬Q) = 0, тогда А должно быть только единицей (чтобы общее выражение было = 1):
  • A ∨ (¬P ∨ ¬Q) = 1; 
    или 
    1 ∨ (0) = 1
    
  • Иными словами, выражение истинно, если при ¬P ∨ ¬Q = 0, A равно единице (1).
  • Получаем:
  • ¬P ∨ ¬Q = 0
    Отсюда имеем: 
    ¬P = 0 и ¬Q = 0 
    
    (дизъюнкция равна 0 в единственном случае, когда все операнды равны 0)
    
  • Или запишем другим образом:
  • Q = 1 и P = 1
  • Построим побитовые маски:
  • 100100  : 36
    000110  : 6
    0**0**  : маска P (x&36 = 0)
    ***00*  : маска Q (x&6 = 0)
    
  • Сопоставим обе маски и маску x&A = 0:
  • 0**0**  : маска P (x&36 = 0)
    ***00*  : маска Q (x&6 = 0)
    0**00*  : общая маска x
    *00**0  : маска для A (x&A = 0)
    т.е. в тех битах А, где может получиться единица (звездочки в обеих масках),
    мы поставили нули.
  • Так как нам необходимо получить наибольшее A (по заданию), то вместо всех "звездочек" ставим единицы:
  • 100110 = 3810
    

Результат: 38

Разбор 18 задания ЕГЭ по информатике (контрольный вариант 2 экзаменационной работы 2018 года "Тренажер ЕГЭ информатика", С.С. Крылов, Д.М. Ушаков):

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

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

x&A ≠ 0 → (x&9 = 0 → x&3 ≠ 0)

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

✍ Показать решение:

  • Так как по заданию формула должна быть тождественно истинна, то перепишем ее так:
  • x&A ≠ 0 → (x&9 = 0 → x&3 ≠ 0) = 1
  • Введем обозначения:
  • A = (x&A = 0);
    P = (x&9 = 0);
    Q = (x&3 = 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
    
     
  • Построим побитовые маски:
  • 1001  : 9
    0011  : 3
    0**0  : маска P (x&9 = 0)
    **00  : маска Q (x&3 = 0)
    
  • Сопоставим обе маски и получим маску для x&A = 0:
  • 0**0  : маска P (x&9 = 0)
    **00  : маска Q (x&3 = 0)
    0*00  : общая маска х
    *0**  : маска для A (x&A = 0)
    т.е. в тех битах, где может получиться единица (звездочки в обеих масках P и Q),
    мы поставили нули.
  • Так как нам необходимо получить наибольшее A (по заданию), то вместо всех "звездочек" ставим единицы:
  • 1011 = 1110
    

Результат: 11

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

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

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

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

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

✍ Показать решение:

  • Так как по заданию формула должна быть тождественно ложна, то перепишем ее так:
  • x&A = 0 ∧ ¬(x&35 ≠ 0 → x&52 ≠ 0) = 0
  • Введем обозначения:
  • A = (x&A = 0);
    P = (x&35 = 0);
    Q = (x&52 = 0);
    
  • Перепишем выражение согласно введенным обозначениям:
  • A  ∧ ¬(¬P  → ¬Q) = 0
    
  • Избавимся от импликации:
  • A  ∧ ¬(P  ∨ ¬Q) = 0
    
  • Раскроем скобки, иcпользуя закон Де Моргана:
  • A  ∧ ¬P  ∧ Q = 0
    
  • A - наше неизвестное; для части выражения ¬P ∧ Q нам необходимо подобрать такой вариант (равный 0 или 1), при котором единственно возможным значением A был бы ноль (0).
  • Возьмем (¬P ∧ Q) = 1, тогда А должно быть только нулем (чтобы конъюнкция была = 0):
  • A ∧ ¬P  ∧ Q = 0
    или 
    0  ∧ 1 = 0
    
  • Иными словами, выражение ложно, если при ¬P ∧ Q = 1, A равно нулю (1).
  • Получаем:
  • ¬P  ∧ Q = 1
    Отсюда имеем ¬P = 1 и Q = 1 
    (конъюнкция равна 1 в единственном случае, когда все операнды равны 1)
    
  • Построим побитовые маски:
  • 100011  : 35
    110100  : 52
    1***11  : маска ¬P (x&35 ≠ 0)
    00*0**  : маска Q (x&52 = 0)
    
  • Вспомним, что А = 0, значит, x&А ≠ 0. Сопоставим обе маски с учетом, что нам необходимо получить
    x&A ≠ 0:
  • 1***11  : маска ¬P (x&35 ≠ 0)
    00*0**  : маска Q (x&52 = 0)
    00*011  : общая маска
    ****11  : маска A (x&A ≠ 0)
    т.е. в тех битах, где может получиться единица (например, 1-й бит справа может дать в результате 1 (1 и *)),
    мы поставили единицы.
  • Таким образом, получаем:
  • А = 000011 = 310
    

Результат: 3

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

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

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

x&56 ≠ 0 ∧ ¬(x&A ≠ 0 ∨   x&32 ≠ 0)

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

📹 Видеоразбор

✍ Показать решение:

  • Так как по заданию формула должна быть тождественно ложна, то перепишем ее:
  • x&56 ≠ 0 ∧ ¬(x&A ≠ 0 ∨ x&32 ≠ 0) = 0
  • Введем обозначения:
  • A = (x&A = 0);
    P = (x&56 = 0);
    Q = (x&32 = 0);
    
  • Перепишем выражение согласно введенным обозначениям:
  • ¬P ∧ ¬(¬A ∨ ¬Q) = 0
    
  • Раскроем скобки, используя закон Де Моргана:
  • ¬P ∧ A ∧ Q = 0
    или
    A ∧ ¬P ∧ Q = 0
    
  • A - наше неизвестное; для части выражения ¬P ∧ Q нам необходимо подобрать такой вариант (равный 0 или 1), при котором единственно возможным значением A был бы ноль (0).
  • Возьмем (¬P ∧ Q) = 1, тогда А должна быть только нулем (чтобы общая формула была = 0):
  • A ∧ ¬P ∧ Q = 0
    или 
    0 ∧ 1 = 0
    
    конъюнкция 0 * 1 = 0
    
  • Иными словами, выражение ложно, если при ¬P ∧ Q = 1, A должно быть равно нулю (1).
  • Получаем следующие утверждения:
  • ¬P ∧ Q = 1   Отсюда имеем: 
    ¬P = 1 и Q = 1 
    
    конъюнкция равна 1 в единственном случае, когда все операнды равны 1
    x&A = 0 - ложь т.е.
    x&A ≠ 0
    
  • Построим побитовые маски:
  • 111000  : 56
    100000  : 32
    111***  : маска ¬P (x&56 ≠ 0)
    0*****  : маска Q (x&32 = 0)
    
  • Сопоставим обе маски и получим x&A ≠ 0:
  • 111***  : маска ¬P (x&56 ≠ 0)
    0*****  : маска Q (x&32 = 0)
    011***  : общая маска х
    *11***  : маска A (x&A ≠ 0)
    т.е. в тех битах, где может получиться единица 
    (например, 4-й бит может дать в результате 1 (1 & *)), мы сохранили эти единицы и для A.
  • Так как нам необходимо получить наименьшее A (по заданию) при формуле тождественно ложной, то остальные разряды оставим равными 0:
  • 011000 = 2410
    

Результат: 24

 

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

На числовой прямой даны два отрезка: 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.
  • Отобразим отрезки на числовой прямой, чтобы найти искомое значение:
  • решение 18 задания ЕГЭ с числовой приямой

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

Результат: 10

 

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

На числовой прямой даны два отрезка: 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
    
  • Отобразим отрезки на числовой прямой, чтобы найти искомое значение:
  • 18 задание  ЕГЭ отрезки

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

 

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

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

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

Результат: 19

 

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

На числовой прямой даны два отрезка: P = [3, 23] и Q = [27, 38].
  
Укажите наибольшую возможную длину промежутка 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
    
  • А - наше неизвестное, необходимо, чтобы А = 1. А должно равняться только 1 в случае, если ¬P ∨ Q = 0 (если ¬P ∨ Q = 1, то А может равняться и 0 и 1, так как имеет место операция логического сложения - ∨)
  • Значит, имеем ¬P ∨ Q = 0:
  • А = 1
    ¬P ∨ Q = 0
    дизъюнкция ложна в единственном случае, когда оба операнда истинны:
    ¬P = 0  
    Q = 0
    или по-другому:
    P = 1 
    ¬Q = 1
    
  • То есть, А истинно (=1) в том случае, если P = 1 и ¬Q = 1
  • Отобразим отрезки на числовой прямой, чтобы найти искомое значение:
  • решение 18 задания егэ про числовую прямую

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

Результат: 20

 

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

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

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

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

📹 Видеоразбор

✍ Показать решение:

  • Упростим выражение, введя обозначения:
  • A: x ∈ A
    P: x ∈ P
    Q: x ∈ Q
    
  • Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно ложной (= 0):
  • (P → Q) ∧ A = 0
    
  • Избавимся от импликации:
  • ¬P ∨ Q ∧ A = 0
    
  • А - наше неизвестное. Необходимо найти такой отрезок, при котором ¬P ∨ Q = 0, тогда A на этом отрезке может быть равно 1 (так как имеет место операция конъюнкция: 0 ∧ 1 = 0).
  • Примем:
  • если
    ¬P ∨ Q = 0 
    то, возможно:
    А = 1
    
  • Отобразим отрезки на числовой прямой, чтобы найти искомое значение:
  • решение 18 задания егэ

  • Рассмотрим отдельно каждую часть числовой прямой:
  • 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, значит А - любое
    5) ¬P ∨ Q : 1 ∨ 0 = 1, значит А = 0
    
  • А - любое только в одном промежутке - [44, 48]. Найдем длину этого отрезка:
  • 48 - 44 = 4

Результат: 4

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

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

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

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

* В оригинальном тексте издания ответ дан с ошибкой

✍ Показать решение:

  • Упростим выражение, введя обозначения:
  • A: x ∈ A
    P: x ∈ P
    Q: x ∈ Q
    
  • Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно ложной (= 0):
  • (P → Q) ∧ A = 0
    
  • Избавимся от импликации:
  • ¬P ∨ Q ∧ A = 0
    
  • А - наше неизвестное. Необходимо найти такой отрезок, при котором ¬P ∨ Q = 0, тогда A на этом отрезке может быть равно 1 (так как имеет место операция конъюнкция: 0 ∧ 1 = 0).
  • Значит, примем следующее утверждение:
  • если
    ¬P ∨ Q = 0
    то, возможно:
    А = 1  
    
  • Отобразим отрезки на числовой прямой, чтобы найти искомое значение:
  • 1

  • Рассмотрим отдельно каждую часть числовой прямой:
  • 1), 3), 5) ¬P ∨ Q : 1 ∨ 0 = 1, значит А = 0
    2) ¬P ∨ Q : 0 ∨ 0 = 0, значит А - любое
    4) ¬P ∨ Q : 1 ∨ 1 = 1, значит А = 0
    
  • А - любое только в одном промежутке - [12, 22]. Найдем длину этого отрезка:
  • 22 - 12 = 10

Результат: 10

Досрочный егэ по информатике 2018, вариант 1:

Укажите наименьшее значение А, при котором выражение

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

истинно для любых целых положительных значений x и y.

📹 Видеоразбор

✍ Показать решение:

  • Определим основные части выражения, выделив отдельно неизвестную часть - с А, и, так сказать, известную часть, то есть остальную.
  •     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 -> ЕГЭ 2018 - 18
 

Поделитесь уроком с коллегами и друзьями:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*
*

Вставить формулу как
Блок
Строка
Дополнительные настройки
Цвет формулы
Цвет текста
#333333
Используйте LaTeX для набора формулы
Предпросмотр
\({}\)
Формула не набрана
Вставить