Информатика ЕГЭ 18 задание разбор

18-е задание: «Элементы математической логики и теория множеств»
Уровень сложности — повышенный,
Максимальный балл — 1,
Примерное время выполнения — 3 минуты.

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

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

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

На числовой прямой даны два отрезка: P=[44,48] и Q=[23,35].

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

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

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

Ответ: 4

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

  • Упростим формулу, избавившись от «x ϵ«:
  • (P → Q) ∧ A
    
  • Теперь преобразуем импликацию в скобках:
  • правило импликации: a → b = ¬a ∨ b
    (¬P ∨ Q) ∧ A
    
  • Указанные в задании отрезки отобразим на числовой прямой. Разделим отрезки на части по точкам, соответствующим их границам.
  • решение 18 задания егэ по информатике

  • Вернемся к преобразованному выражению. В нем есть известная часть (выделим ее) и неизвестная. По условию выражение должно быть ложно:
  • (¬P ∨ Q) ∧ A = 0
  • Внешняя операция выражения — конъюнкция — ложна в трех случаях и только в одном — истинна:
  • (¬P ∨ Q) ∧ A
        0      0 = 0
        0      1 = 0
        1      0 = 0
        1      1 = 1
    
  • Теперь рассмотрим это выражение относительно наших отрезков на числовой прямой: если известная часть выражения (¬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

📹 Видео


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

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

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

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

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


Ответ: 10

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

  • Упростим выражение, введя обозначения:
  • 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.

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

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

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

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

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

Ответ: 8

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

  • Упростим выражение, введя обозначения:
  • 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.

📹 Видео


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

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

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

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

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


Ответ: 19

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

  • Упростим выражение, введя обозначения:
  • 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.

Задания с ДЕЛ

Задание с ДЕЛ:

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

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

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

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

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

Ответ: 3

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

  • Введем обозначения:
  • A = ДЕЛ(x,A); 
    D28 = ДЕЛ(x, 28); 
    D42 = ДЕЛ(x, 42)
    
  • Перепишем исходную формулу, согласно введенным обозначениям. Укажем, что формула должна быть тождественно истинна (по условию):
  • A → (¬D28 ∨ D42) = 1
    
  • Разделим данную формулу на две части: в одной из них — искомое A, а в другой — часть формулы с x, которую можно найти:
  • A → (¬D28 ∨ D42) = 1
     1        2
    
  • В части 2 полученной формулы находится операция дизъюнкция, которую проще найти, когда логическое выражение равно 0 (только один случай: 0 ∨ 0 = 0):
  • (¬D28 ∨ D42) = 0   один случай: когда ¬D28 = 0 и D42 = 0
  • Если вторая часть формулы равна 0, тогда необходимо, чтобы A = 0:
  • A → ¬D28 ∨ D42 = 1
    0       0     = 1
    1       0     = 0  - так нельзя! т.к. формула должна = 1
    
    ¬D28 ∨ D42 = 0 только при A = 0 
    
  • Т.е. имеем:
  • A = 0 
    при ¬D28 = 0 и D42 = 0
    
    или
    A = 1 
    при D28 = 0 и D42 = 1
    
  • Очевидно, что наименьшим x можем взять число 42: ДЕЛ(42, 42) и ¬(ДЕЛ(42, 28))
  • Поскольку мы ищем наименьшее A, такое что: ДЕЛ(x, A) и при этом ДЕЛ(x, 42) и ¬(ДЕЛ(x, 28)), то разложим 42 на сомножители, начиная с самого маленького числа — 2:
  • делитель 2 (A=2):
    42 = 2 * 21   тогда:   
    ДЕЛ(x, A): x может быть и 42 и 28, т.е.
    ДЕЛ(42, A=2) и ДЕЛ(28, A=2) - нам не подходит! (должно быть ¬(ДЕЛ(x, 28)))
    
    следующий делитель 3 (A=3):
    42 = 3 * 14   тогда:    
    ДЕЛ(x, A), x может быть только 42:
    ДЕЛ(42, A=3), т.к. 28 не делится целочисленно на 3
    (т.е. при A = 3 имеем ¬(ДЕЛ(x, 28)))
    
  • Т.е. наименьшим А является число 3.

Задание с ДЕЛ:

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

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

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

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

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

Ответ: 285

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

  • Введем обозначения:
  • A = ДЕЛ(x,A); 
    D19 = ДЕЛ(x, 19); 
    D15 = ДЕЛ(x, 15)
    
  • Перепишем исходную формулу, согласно введенным обозначениям. Укажем, что формула должна быть тождественно истинна (по условию):
  • (¬D19 ∨ ¬D15) → ¬A = 1
    
  • Избавимся от импликации:
  • D19 ∧ D15 ∨ ¬A = 1
    
  • Разделим данную формулу на две части: в одной из них — искомое A, а в другой — часть формулы с x, которую можно найти:
  • ¬A ∨ D19 ∧ D15 = 1
     1       2
    
  • Начнем с известной части — части 2 формулы. В ней находится операция конъюнкция, которую проще найти, когда все ее операнды равны 1 (единственный случай для конъюнкции: 1 ∧ 1 = 1).
  • Вторая часть общей формулы может равняться только 1, когда ¬A = 0 (если ¬A = 1, то вторая часть может равнять 0, а нам нужно 1) :
  • ¬A ∨ D19 ∧ D15 = 1
     0       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), то введем предположение:
  • предположим, A = 5 тогда: 
    ДЕЛ(x, A=5): x может быть любым числом кратным 5, 
    а нам необходимо, чтобы ДЕЛ(x, 19) и ДЕЛ(x, 15), т.е A = 5 - нам не подходит! 
    
  • Очевидно, что A должно быть таким числом, при котором x принимает единственно возможное (наименьшее) значение 285:
  • Таким наименьшим A является само число 285.

Задание с ДЕЛ:

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

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

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

  (ДЕЛ(x, 40) ∨ ДЕЛ(x, 64))  → ДЕЛ(x, A) 

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

Ответ: 8

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

  • Введем обозначения:
  • 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
          1         2
    
  • В полученной формуле необходимо, чтобы 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
    
  • В этом случае логическое сложение тоже дает истину в трех случаях (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:
  • 2

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

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

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

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

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

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

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

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

Ответ: 3

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

Стоит заметить, что для такого типа задач, нет универсального единственного решения. Поэтому на видео, расположенном ниже, представлено два варианта решения.

Рассмотрим один из вариантов решения:

  • Удалим из формулы X&, чтобы сократить ее запись:
  • (A = 0) ∧ ¬(35 ≠ 0 → 52 ≠ 0)
    
  • Обратим внимание, что внешней операцией является конъюнкция — логическое умножение:
  • (A = 0)  ¬(35 ≠ 0 → 52 ≠ 0)
    
  • Разделим общее выражение на две части относительно внешней операции. Первая часть — неизвестная, искомая, а вторая — известная, ее можно вычислить:
  • (A = 0) ∧ ¬(35 ≠ 0 → 52 ≠ 0)
       1               2
    
  • Выполним некоторые преобразования во второй части формулы:
  • Зная свойство импликации, преобразуем формулу (избавимся от импликации в скобках):
  • правило импликации: 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 ∧ 1 = 0
    1 ∧ 0 = 0
    1 ∧ 1 = 1
    
  • Вторая часть формулы — вычислима, поэтому начнем с нее. В ней находится операция конъюнкция, которая имеет один единственный вариант решения, когда ¬ A ∧ ¬ B = 1. То есть примем вторую часть за истину (=1). В таком случае, для того чтобы общее выражение стало ложным (так требуется по заданию), необходимо, чтобы утверждение, что A = 0 было ложным (т.к. в обратном случае получим: 1 ∧ 1 = 1):
  • (A = 0) ∧ 35 ≠ 0 ∧ 52 = 0
       0            1    = 0 
    
  • Вторая часть будет истинной только в том случае, если оба утверждения будут истинными:
  • 35 ≠ 0 ∧ 52 = истинно (=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. Для искомого X учтем уже полученные значения:
  • 35 1 0 0 0 1 1
    X 0
    (получено выше)
    0
    (получено выше)
    ? 0
    (получено выше)
    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
  • Переведем результат в десятичную систему счисления:
  • 0000112 = 310

📹 Видео


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

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

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

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

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

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

Ответ: 38

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

    ✎ Способ 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
  • Выполним поразрядную дизъюнкцию двоичных чисел 36 и 6:
  • 1001002 -> 36
    1102 -> 6
    
    100100
    +
       110
    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

📹 Видео 1

📹 Видео 2


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

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

Определите наименьшее натуральное число А из интервала [43, 55], такое, что выражение

((x & 17 ≠ 0) → ((x & A ≠ 0) → (x & 58 ≠ 0))) →
→ ((x & 8 = 0) ∧ (x & A ≠ 0) ∧ (x & 58 = 0))

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

Ответ: 48

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

    Кратко изложенное решение *:

  • Введем обозначения:
  • (¬Z17 → (¬A → ¬Z58)) → (z8 ∧ ¬A ∧ Z58) = 0
    
  • Для того, чтобы выражение было истинным, поставим его с отрицанием:
  • ¬(((¬Z17 → (¬A → ¬Z58)) → (z8 ∧ ¬A ∧ Z58)) = 1
     
  • Упростим выделенную часть выражения (свойство 1, теория):
  • Z8 ∧ Z58 = Z8 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


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

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

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

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

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

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


Ответ: 8

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

  • Для упрощения восприятия введем обозначения:
  • 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 (Zk + Zm = Zk and m):
  • 26 : 11010   единичные биты: 4, 3, 1
    13 :  1101   единичные биты: 3, 2, 0
    ∧ =------------------------
         01000 = 810
    
  • То есть получили z26 ∨ z13 = z8
  • По правилу импликации: все единичные биты двоичной записи результата (z78 ∨ A) должны входить во множество единичных битов двоичной записи z8.
  • Рассмотрим:
  • z8 → (z78 ∨ A)
    z78: не влияет на решение, так как операция дизъюнкция истинна тогда, 
    когда хотя бы один операнд истинен
    z8 → A     : ????
    
  • Для А единичными битами должны быть общие единичные биты для z8 (10002). Т.е. в нашим случае — это один бит — 3-й:
  • Наибольшее А = 1000 = 810
    

Результат: 8


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

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

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

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

Ответ: 99

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

  • Условно разделим исходное выражение на части:
  • решение 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=9, тогда A>=81

    Рассмотрим часть 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

📹 Видео


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

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

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

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

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

Похожие задания для тренировки: разбор досрочного егэ по информатике 2019

Ответ: 101

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

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

📹 Видео


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

Разбор 18 задания. Демоверсия егэ по информатике 2019:

Для какого наибольшего целого неотрицательного числа А выражение
  
(48 ≠ y + 2x) ∨ (A < x) ∨ (A < y)
 
тождественно истинно, т.е. принимает значение 1 при любых целых неотрицательных x и y?


Ответ: 15

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

  • Разделим общее выражение на две части. Выделим неизвестную часть красным:
  • (48 ≠ y + 2x) ∨ (A < x) ∨ (A < y)
    
  • Неизвестная часть должна быть истинной, она обязательно будет истинна, если известная часть — ложь:
  • (48 ≠ y + 2x) ∨ (A < x) ∨ (A < y) = 1
          0                  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
    

    решение 18 задания демоверсии егэ 2019

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

  • Далее решаем полученное линейное уравнение (для x = y):
  • x + 2x = 48 =>
    3x = 48
    x = 16
    
  • Так как значение A должно быть меньше x, то наибольшее А = 15.

📹 Видео


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

Разбор 18 задания ЕГЭ вариант № 3, 2019 Информатика и ИКТ Типовые экзаменационные варианты (10 вариантов), С.С. Крылов, Т.Е. Чуркина:

Для какого наименьшего целого числа А формула
  
(y + 5x <= 34) → ((y - x > 4) ∨ (y <= A))
 
тождественно истинна, т.е. принимает значение 1 при любых целых неотрицательных x и y?

Ответ: 9

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

  • Общая идея такова:
    необходимо упростить формулу так, чтобы последняя операция (внешняя) выполнялась со скобкой, в которой находится искомое 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
    
  • Отобразим получившиеся уравнения прямых на плоскости:
  • крылов вариант 3

  • Раз A >= y, значит, искомая область лежит выше обеих прямых. Наименьшее значение А будет достигнуто в указанной точке пересечения двух прямых.
  • В точке пересечения прямых уравнения равны, т.е. имеем:
  • 34 - 5x = 4 + x
    30 = 6x
    x = 5
    Найдем y: 
    y = 4 + 5 = 9
    
  • Поскольку имеем утверждение, что A >= y и в задании требуется найти наименьшее A, то получаем:
  • y = 9:
    A >= 9 => наименьшее A = 9
    


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

18_13. Разбор 18 задания ЕГЭ с сайта К. Полякова № 296:

Укажите наименьшее целое значение А при котором выражение
  
(2y + 5x < A) ∨ (2x + 4y > 100) ∨ (3x – 2y > 70)

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

Ответ: 171

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

📹 Видео


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

18_14. Разбор 18 задания ЕГЭ с сайта К. Полякова № 303:

Укажите наибольшее целое значение А при котором выражение
  
(3y – x > A) ∨ (2x + 3y < 30) ∨ (2y – x < –30)

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

Ответ: -30

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

📹 Видео

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

    Елена

    Здравствуйте! Понравилось Ваше объяснение задач. Всё очень просто и доступно. Вопрос по подобной задаче (у Вас 18_4) из решу егэ. Объяснение оттуда не очень меня удовлетворяет. Помогите, пожалуйста! Вот задача:

    На числовой прямой даны два отрезка: P = [8, 39] и Q = [23, 58].
    Выберите из предложенных отрезков такой отрезок A, что логическое выражение

    ((x ∈ P) ∨ (x ∈ А)) → ((x ∈ Q) ∨ (x ∈ А))

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

    1) [5, 30]

    2) [15, 40]

    3) [25, 50]

    4) [35, 60]
    В отличие от 19_4 вместо умножения стоит плюс

    Alex

    Решение к 18_8 как можно увидеть? У Вас только ответ

      admin

      скоро будет, спасибо

    Вилена Снегирева

    Здравствуйте, как можно решить задачу
    Определите наименьшее натуральное число A, при котором выражение
    ( x & 25 1) or ((x & 34 = 2) -> (x & A = 0))
    тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной x)?

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

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

*
*


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