Решение 15 задания ЕГЭ по информатике про основные законы Алгебры Логики

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

Объяснение задания 15 ЕГЭ по информатике

15-е задание: «Основные законы алгебры логики»
Уровень сложности — повышенный,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 5 минут.
  
Проверяемые элементы содержания: Знание основных понятий и законов математической логики
До ЕГЭ 2021 года — это было задание № 18 ЕГЭ
Типичные ошибки и рекомендации по их предотвращению:

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

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

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

    Для решения 15 задания, потребуется знание таблиц истинности.

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

    Преобразование логических операций:
  • операцию импликация можно преобразовать в операции ИЛИ и НЕ:
  • A → B = ¬ A ∨ B
    или
    A → B = A + B
  • операцию эквивалентность можно преобразовать:
  • A ↔ B = A ⊕ B = A ∧ B ∨ AB
    или
    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
  • Порядок выполнения логических операций:
    1. выражения в скобках,
    2. операции «НЕ»,
    3. операции «И»,
    4. операции «ИЛИ»,
    5. операции «импликация»
    6. операции «эквиваленция»
  • последовательность из операций импликации выполняется слева направо (при этом соблюдается принцип «операции с одинаковым приоритетом выполняются слева направо»):
  • 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), то есть Amin = ¬ X
  • пусть требуется выбрать множество A так, чтобы выполнялось равенство ¬ A ∨ X = I, в этом случае множество ¬ A должно включать дополнение ¬ X, то есть ¬ A ⊇ ¬ X; отсюда A ⊆ X, то есть Amax = X

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

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

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

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

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

    Amin = ¬B

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

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

    Amax = B

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

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

    Amax = ¬B

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

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

    Amin = B

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

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

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

5 & 26

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

5  =   1012 
26 = 110102
0  = 000002

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

  • Обозначим:
  • (x & K = 0) как Zk  
    
  • Для решения методом, предложенным А.В. Здвижковой, пригодится использование следующих свойств:
  • свойство 1:
    Zk * Zm = Zk or m
  • Так, например, если в задании имеем:
  • (X & 5 = 0)  (X & 26 = 0)
    
  • то сначала введем замену:
  • Z5 ∧ Z26
    
  • а затем, используя свойство 1, вычислим поразрядную дизъюнкцию двоичного значения чисел 26 и 5:
  • Z5 ∧ Z26 = Z26 or 5
    помним, что дизъюнкция - это операция логическое "ИЛИ" (сложение)
    5  =   1012 
    26 = 110102
    31 = 111112
    
  • таким образом, получили:
  • Z5 ∧ Z26 = Z31
    
    свойство 2:
    Zk + Zm = Zk and m
  • Так, например, если в задании имеем:
  • (X & 28 = 0)  (X & 22 = 0)
    
  • то сначала введем замену:
  • Z28 ∨ Z22
    
  • а затем, используя свойство 2, вычислим поразрядную конъюнкцию двоичного значения чисел 28 и 22:
  • Z28 ∨ Z22 = Z28 and 22
    помним, что конъюнкция - это операция логическое "И" (умножение)
    28 = 111002 
    22 = 101102
         101002 = 2010
    
  • таким образом, получили:
  • Z28 ∨ Z22 = Z20
    
свойство 3:
Условие Zk → Zm истинно для любых натуральных значений x тогда и только тогда, когда все единичные биты двоичной записи числа M входят во множество единичных битов двоичной записи числа K.
  • На деле, это означает, что если имеем:
  • X & 29 = 0  X & 5 = 0  Истинно или Ложно?
    
  • то сначала введем замену:
  • Z29 → Z5
    
  • а затем, используя свойство 3, определим истинность высказывания Z29 → Z5:
  • Z29 → Z5 = 1 (истине), тогда, когда:
    29 = 111012
    5  =   1012  
    единичные биты двоичного числа 5 входят в единичные биты двоичного числа 29 
    (совпадают с ними)
    
  • таким образом, получили:
  • Z29 → Z5 = 1 (истинно)
    
свойство 4:
(x & 125 = 5) то же самое, что и
Z120 * ¬Z4 * ¬Z1 = 1 (истине)
  • Так, например, если в задании имеем:
  • X & 130 = 3 
    
  • то сначала введем замену и, используя свойство 4, получим:
  • X & 130 = 3 то же самое, что и
    Z127 * ¬Z2 * ¬Z1
    
    т.е. 3 = 2 + 1 :	
    
    2 = 10
    1 = 01
    3 = 11
    

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

Плейлист видеоразборов задания на YouTube:

Задание демонстрационного варианта 2022 года ФИПИ


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


Множества:
 

15_16:

№ 95
Элементами множества А являются натуральные числа. Известно, что выражение

((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
          0      1
      
    • То есть получаем:
    • ¬P ∨ ¬Q = 0,
      или 
      ¬P = 0  отсюда P = 1
      ¬Q = 0 отсюда Q = 1
    • Таким образом имеем пересечение (умножение) двух множеств Q и P. То есть необходимо выбрать элементы, которые встречаются в обоих множествах одновременно:
    • A = {3,9}
      
    • Сумма элементов:
    • 3 + 9 = 12

    ✎ Решение программированием:
    PascalAbc.net:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    
    begin
      var s1 := hset(1, 3, 5, 7, 9, 11);
      var s2 := hset(3, 6, 9, 12);
      var a:=new List<integer>;
      for var x := 1 to 100 do
      begin
        if (x in s1 <= not (x in s2)) = false then // если ложь, то x∈A - истина
          a.Add(x)
      end;
      a.Sum.Print;
    end.

    Ответ: 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
        0      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
     0      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: Закон поглощения

№ 100
Элементами множества А являются натуральные числа. Известно, что выражение

¬(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
     1      0
    
  • То есть получаем:
  • ¬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
    
  • Указанные в задании отрезки отобразим на числовой прямой. Разделим отрезки на части по точкам, соответствующим их границам.
  • решение 15 задания егэ по информатике

  • Вернемся к преобразованному выражению. В нем есть известная часть (выделим ее) и неизвестная. По условию выражение должно быть ложно:
  • (¬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

Результат: 4
✎ Решение программированием

Важно: Этот способ подходит НЕ для всех заданий с отрезками!

Python:

1
2
3
4
5
6
7
8
9
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) # сами точки отрезка и длина

Вывод:

44 45 1
44 46 2
44 47 3
44 48 4

PascalABC.net (классическое решение):

1
2
3
4
5
6
7
8
9
10
11
12
13
begin
var s1:=44..48;
var s2:=23..35;
var a:=new List<integer>;
for var x:=1 to 1000 do
begin
  var p:=x in s1;
  var q:=x in s2; 
  if not (p<=q) = true then
    a.Add(x);
end;
a.count.print
end.

Вывод:

5

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

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

Результат: 10

✎ Решение программированием

Важно: Этот способ подходит НЕ для всех заданий с отрезками!

Python:

1
 

Вывод:


PascalABC.net (классическое решение):

1
2
3
4
5
6
7
8
9
10
11
12
13
##
var s1:=10..20;
var s2:=30..40;
var a:=new List<integer>;
for var x:=1 to 1000 do
begin
  var p:=x in s1;
  var q:=x in s2; 
  if not(p<=q) = true then 
    a.Add(x);
end;
a.Println;
print(a.Count-1) // так как требуется длина отрезка

Вывод:

10 11 12 13 14 15 16 17 18 19 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
    
  • Отобразим отрезки на числовой прямой, чтобы найти искомое значение:
  • 15 задание  ЕГЭ отрезки

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

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

Результат: 19

Задания с ДЕЛ

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

15_7:

№ 133

Обозначим через ДЕЛ(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
          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
    

      
    Далее можно решать задание либо с помощью кругов Эйлера, либо с помощью логических рассуждений.

    Способ 2:

  • Найдем все такие 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:
  • 2

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

Результат: 8

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

1
2
3
4
5
6
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 )

Вывод:

1
2
4
8

PascalABC.net (LINQ):

##
function f(a,x:integer):= (x.Divs(40) or (x.Divs(64)) <= x.Divs(a))?true:false;
(1..500).Where(a->(1..1000).All(x->f(a,x))).print;

Вывод:

1 2 4 8

PascalABC.net (классическое решение):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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.

Вывод:

1
2
4
8

Результат: 8

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

15_5:

№ 138

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

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

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

тождественно истинна (то есть принимает значение 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
     1        2
    
  • В части 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.

✎ Решение программированием. Язык 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 (LINQ):

    ##
    function f(a,x:integer):= x.Divs(a) <= ((not x.Divs(28)) or (x.Divs(42)))?true:false;
    (1..500).Where(a->(1..1000).All(x->f(a,x))).take(1).print;

    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
    

Результат: 3

15_6:

№ 136

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

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

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

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

✍ Решение:

✎ Теоретическое решение (логическое):

  • Введем обозначения:
  • 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), то нам необходимо найти наименьшее делимое чисел 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.

✎ Решение программированием:

    Из общего выражения:

     (¬ДЕЛ(x, 19) ∨ ¬ДЕЛ(x, 15)) → ¬ДЕЛ(x, A)  = 1
  • Можно сделать вывод, что для некоторого диапазона натуральных значений А, необходимо рассмотреть диапазон натуральных значений x. Если выражение будет истинным для диапазона всех рассматриваемых х, то такое А необходимо вывести на экран.
  • То есть следует рассмотреть вложенный цикл: для внешнего цикла, перебирающего значения А (ограничим их числом 500, т.к. необходимо найти наименьшее А), будем запускать внутренний цикл, перебирающий значения х (х ограничим числом 1000, будем рассматривать данный диапазон, как "любое натуральное значение переменной х").
  • Python:

  • Во внутреннем цикле расположим формулу:
  • 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 )
    OK - переменная-индикатор: если находится такое А при котором, диапазон всех значений x, подставленных в выражение, возвращает истинное значение выражения, то ОК остается равным 1, т.к. используется операция умножения (до цикла ОК необходимо присвоить единице).
    Следует иметь в виду, что в программировании вместо операции импликация (->) можно использовать нестрогое неравенство: <=. Т.к. таблица истинности для операции импликация соответствует операции <=:

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

    PascalABC.net (LINQ):

    ##
    function f(a,x:integer):= x.Divs(a) <= ((not x.Divs(19)) or (not x.Divs(15))) <= not x.Divs(a)?true:false;
    (1..500).Where(a->(1..1000).All(x->f(a,x))).take(1).print;
  • После запуска программы выдается одно значение А:
  • 285
    

Результат: 285

  

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


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

15_1:

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 12&6 = 11002&01102 = 01002 = 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)
       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
    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            1    = 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
  • Переведем результат в десятичную систему счисления:
  • 0000112 = 310

Ответ: 3

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

    Используем метод А.В. Здвижковой.

  • Выполним последовательно следующие пункты:
    1. Произвести замену (x & K = 0) на Zk
    2. Выполнить преобразования по свойству импликации и закону Де Моргана.
    3. Стремиться прийти к выражению с конъюнкциями без отрицаний типа: Zk * Zm.
    4. Все выражения типа Zk * Zm преобразовать по свойству
      Zk * Zm = Zk or m.
    5. Путем преобразований прийти к импликации: 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
    
  • Получаем:
  • ZA ∨ 52 → Z35 = 1
    
  • Вспомним свойство:
  • Условие Zk → Zm истинно для любых натуральных значений x тогда и только тогда, когда все единичные биты двоичной записи числа M входят во множество единичных битов двоичной записи числа K.

  • В нашем случае это говорит о том, что все единичные биты двоичной записи числа 35 должны входить в результат ZA or 52.
  • Рассмотрим подробно:
  • A       = ??0?11
    52      = 110100
    A or 52 = 110111
    35      = 100011
     
  • поскольку мы ищем наименьшее А, то:
  • Аmin = 112 = 310

✎ Решение программированием
PascalAbc.net (LINQ):

##
function f(a,x:integer):= ((x and A)=0) and 
    not(not(x and 35=0) <= not(x and 52=0))?true:false;
(1..2000).Where(a->(1..2000).All(x->f(a,x)=false)).print;

PascalAbc.net (классическое решение):

begin
  for var a:=1 to 1000 do
  begin
    var ok:=1;
    for var x:=1 to 1000 do
    begin
      var f1:=(x and a)=0;
      var f2:=(x and 35)=0;
      var f3:=(x and 52)=0;
      if f1 and not (not f2<= not f3) = true then begin
        ok:=0;break;
      end;
    end;
    if ok = 1 then
      print(a)
  end;
end.

Результат: 3

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

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

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


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

15_2:

Обозначим через 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
  • Выполним поразрядную дизъюнкцию двоичных чисел 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
    

✎ Решение программированием
PascalAbc.net (LINQ):

##
function f(a,x:integer):= not(x and A=0) <=((x and 36=0) <= not(x and 6=0))?true:false;
(1..2000).Where(a->(1..2000).All(x->f(a,x))).print;

PascalAbc.net (классическое решение):

begin
  for var a:=1 to 1000 do
  begin
    var ok:=1;
    for var x:=1 to 1000 do
    begin
      var f1:=(x and a)<>0;
      var f2:=(x and 36)=0;
      var f3:=(x and 6)<>0;
      if f1 <= (f2 <= f3) = false then begin
        ok:=0;break;
      end;
    end;
    if ok = 1 then
      print(a)
  end;
end.

Результат: 38

Подробное решение данного задания 15 ЕГЭ по информатике предлагаем посмотреть в видео уроке:
Способ 1:
📹 YouTube здесь
  📹 Видеорешение на RuTube здесь
Способ 2:
📹 YouTube здесь
📹 Видеорешение на RuTube здесь

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

15_8:

№ 209
Определите наименьшее натуральное число А из интервала [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 = 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
✎ Решение программированием:
PascalAbc.net (LINQ):

##
function f(a,x:integer):= (not(x and 17=0) <=(not(x and a=0) <= not(x and 58=0)))
<= ((x and 8 = 0) and (not(x and a = 0)) and (x and 58=0))?true:false;
(43..55).Where(a->(1..2000).All(x->f(a,x)=false)).print;

PascalAbc.net (классическое решение):

begin
  for var a:=43 to 55 do
  begin
    var ok:=1;
    for var x:=1 to 1000 do
    begin
      var f1:=x and 17<>0;
      var f2:=x and a<>0;
      var f3:=x and 58<>0;
      var f4:=x and 8 = 0;
      var f5:=x and a<>0;
      var f6:=x and 58=0;
      if f1 <= (f2 <= f3)<=(f4 and f5 and f6) = true then begin
        ok:=0;break;
      end;
    end;
    if ok = 1 then
      print(a)
  end;
end.

Результат: 48


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

15_15:

№ 173
Определите набольшее натуральное число 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 (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
✎ Решение программированием:
PascalAbc.net (LINQ):

##
function f(a,x:integer):= ((x and 26=0) or (x and 13=0)) <= (not(x and 78=0)
<= (x and a=0))?true:false;
(1..2000).Where(a->(1..2000).All(x->f(a,x))).print;

PascalAbc.net (классическое решение):

begin
  for var a:=1 to 1000 do
  begin
    var ok:=1;
    for var x:=1 to 1000 do
    begin
      var f1:=x and 26=0;
      var f2:=x and 13=0;
      var f3:=x and 78<>0;
      var f4:=x and a=0;
      if (f1 or f2) <= (f3 <= f4) = false then begin
        ok:=0;break;
      end;
    end;
    if ok = 1 then
      print(a)
  end;
end.

Результат: 8

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


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

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

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

✍ Решение:

✎ Способ 1 (программный):
Pascalabc.net (LINQ - решение запросом):

##
function f(a,x,y:integer):= ((x<=9)<=(x*x<=a)) and ((y*y<=a) <= (y <=9))?true:false;
(-1000..1000).Where(a->(0..1000).All(x->(0..1000).All(y->f(a,x,y)))).print;

Pascalabc.net (классическое решение методом перебора):

Важно: Поскольку используется метод полного перебора, то возможна ситуация, когда транслятор будет работать слишком медленно. Но работоспособность представленного алгоритма проверена на онлайн компиляторах.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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) <= (x*x<=A)) and((y*y<=A) <= (y<=9)) 
    if OK:
        print(A)
        break
С++:

 

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

  • Условно разделим исходное выражение на части:
  • решение 15 (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

Результат: 99

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

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

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

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

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

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

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

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

✍ Решение:

✎ Способ 1 (программный):
Pascalabc.net (LINQ - решение запросом):

##
function f(a,x,y:integer):= (y+3*x<a) or (x>20) or (y >40)?true:false;
(-1000..1000).Where(a->(1..1000).All(x->(1..1000).All(y->f(a,x,y)))).Take(1).print;

Pascalabc.net (классическое решение методом перебора):

Важно: Поскольку используется метод полного перебора, то возможна ситуация, когда транслятор будет работать слишком медленно. Но работоспособность представленного алгоритма проверена на онлайн компиляторах.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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+3*x<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.

✎ Данное задание также можно решить графическим способом
Выбрав произвольное значение A и представив А > 3x + y как прямую на плоскости.
Результат: 101

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

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

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

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

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

✍ Решение:
✎ Решение 1 (программный способ):
Pascalabc.net (LINQ - решение запросом):

##
function f(a,x,y:integer):= (48 <> y+2*x) or (a<x) or (a<y)?true:false;
(0..1000).Where(a->(0..1000).All(x->(0..1000).All(y->f(a,x,y)))).print;

Python (классическое решение методом перебора):

1
2
3
4
5
6
7
8
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

✎ Решение 2 (графический способ):

  • Разделим общее выражение на две части. Выделим неизвестную часть красным:
  • (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
    

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

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

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

Результат: 15

Видео решения 15 задания демоверсии ЕГЭ 2019 (аналитическое решение):
📹 YouTube здесь
📹 Видеорешение на RuTube здесь

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

15_19:

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    
    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 (LINQ - решение запросом):

    ##
    function f(a,x,y:integer):= (y+5*x<=34) <=((y-x>4) or (y<=a))?true:false;
    (0..1000).Where(a->(0..1000).All(x->(0..1000).All(y->f(a,x,y)))).take(1).print;

    Pascalabc.net (классическое решение методом перебора):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    
    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

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

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

Результат: 9


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

15_13:

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

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

Типовые задания для тренировки

✍ Решение:

    ✎ Способ 1 (программный):
    Python (классическое решение методом перебора):

    1
    2
    3
    4
    5
    6
    7
    8
    
    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 (LINQ - решение запросом):

    ##
    function f(a,x,y:integer):= (2*y+5*x<a) or (2*x+4*y>100) or (3*x-2*y>70)?true:false;
    (-1000..1000).Where(a->(1..1000).All(x->(1..1000).All(y->f(a,x,y)))).take(1).print;

    PascalABC.NET (классическое решение методом перебора):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    
    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.

✎ Способ 2 (графический): представлен в видеоразборе ниже.
Результат: 171

Видео разбора задания смотрите на видео (аналитическое решение):

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

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

15_14:

№ 303
Укажите наибольшее целое значение А при котором выражение
  
(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

    ✎ Способ 2 (программный):
    Pascalabc.net (LINQ - решение запросом):

    ##
    function f(a,x,y:integer):= (3*y-x>a) or (2*x+3*y<30) or (2*y-x<-31)?true:false;
    (-100..1000).Where(a->(1..1000).All(x->(1..1000).All(y->f(a,x,y)))).print;

    Python (классическое решение методом перебора):

    1
    2
    3
    4
    5
    6
    7
    8
    
    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

Смотрите решение подобного задания:
  
📹 YouTube здесь
📹 Видеорешение на RuTube здесь

15_21:

№ 277

Известно, что для некоторого отрезка А формула

((x ∈ A) → (x2 <= 100)) ∧ ((x2 <= 16) → (x ∈ A)) 

тождественно истинна (то есть принимает значение 1 при всех вещественных значениях переменной x).
Какую наибольшую длину может иметь отрезок A?

✍ Решение:

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

  • Разделим выражение на две части. Основная (внешняя) операция - конъюнкция.
  • ((x ∈ A) → (x2 <= 100)) ((x2 <= 16) → (x ∈ A)) = 1
    
  • Так как выражение должно быть истинным, то обе части выражения должны быть истинными (таблица истинности для конъюнкции):
  • 1) ((x ∈ A) → (x2 <= 100)) = 1
    2) ((x2 <= 16) → (x ∈ A)) = 1
  • Преобразуем выражения, избавившись от импликации:
  • 1) ((x ∉ A) ∨ (x2 <= 100)) = 1
    2) ((x2 > 16) ∨ (x ∈ A)) = 1
  • Рассмотрим (1). Разделим выражение на две части. Первая часть должна быть истинной, когда вторая часть ложна:
  • 1) ((x ∉ A)(x2 <= 100)) = 1
          true        false
    
  • Найдем диапазон для x для (1) части:
  • 1) x ∉ A, для x2 > 100 => x > 10, x < -10  => x ∈ [-∞ ; -10), (10; ∞]
    То есть найден диапазон, в котором нет A.
    
  • Рассмотрим (2). Разделим выражение на две части. Вторая часть должна быть истинной, когда первая часть ложна:
  • 2) ((x2 > 16)(x ∈ A)) = 1
        false         true
    
  • Найдем диапазон для x для (2) части:
  • (x ∈ A), для x2 <= 16 => x <= 4, x >= -4 => x ∈ [-4;4]
  • Для отрезка А имеем два диапазона x: [-4;4] и [-10;10]. Поскольку требуется найти наибольший отрезок А, то имеем x ∈[-10;10]. Длина:
  • 10+10 = 20

Ответ: 20

Смешанные выражения

15_22:

№ 502

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

(ДЕЛ(x, 250) → ¬ ДЕЛ(x, 10)) ∨ (3x + 2A ≥ 1000)

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

✍ Решение:

    ✎ Способ 1 (программный):
    Pascalabc.net (LINQ - решение запросом):

    ##
    function f(a,x:integer):= (x.divs(250) <= not(x.Divs(10))) or (3*x+2*a>=1000)?true:false;
    (-1000..1000).Where(a->(1..1000).All(x->f(a,x))).Take(1).print;

Ответ: 125

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

    Наталья

    Спасибо!!!! Все понятно!

    Светлана

    спасибо

    Noname

    Почему в первой задаче длина отрезка 4,если в отрезок входят: 44,45,46,47,48. Т.е. пять цифр.

      Игорь

      я думал, что я один такой умный. Замечание правильное. Ответ = 5 !!!
      Потому что в задании сказано промежуток, а не отрезок. Крылов с Чуркиной тоже ошиблись 😉
      Промежуток (математика)
      Промежуток, или более точно, промежуток числовой прямой — множество вещественных чисел, обладающее тем свойством, что вместе с любыми двумя числами содержит любое, лежащее между ними.
      В задаче имеется в виду конечно же промежуток не вещественных, а целых чисел.

        admin

        Спасибо) значит, исправим само задание: вместо «промежуток» укажем «отрезок»

    Аноним

    18_10 видео не соответствует задаче.

      Аноним

      Отмена

    Галина

    26 в 10-ой =11010 в 2-ой
    А в целом большое спасибо!

      admin

      Спасибо:) исправлено

    Аноним

    Последняя задача (18_14.) не соответствует задаче в прикреплённом видеоролике, но ответ указан от задания в видео. Можно узнать правильный ответ?

      admin

      Там написано, что в видео объясняется подобное задание

    Алекс

    Простите, я не понимаю…
    В примере 130&x=3.
    130=10000010.
    Побитовая конъюнкция с каким числом даст 3???
    10000010 & xxxxxxxx =00000011
    Поразрядная конъюнкция с последним 0 всегда даст 0, то есть такого числа не существует.
    Или я чего-то не понимаю?..

      admin

      каждый бит одного числа умножить на соответствующий ему бит другого числа — это поразрядная конъюнкция

    Полина

    Добрый день!
    Разбираю теорию, исследую первое свойство поразрядной конъюкции. В нем Z(k) * Z(n) = Z(k or n), и здесь необходимо применять поразрядую дизъюнкцию. Обнаружила ошибку: 26 и 5 дадут 31, но в разобранном примере ответ равен 29. А все дело в том, что неверно представлено число 26 в 2 СС. Оно равно не 11000, а 11010.
    Прошу исправить ошибку, иначе школьники совсем запутаются!
    Спасибо)

      admin

      Спасибо большое! исправлено)

    Виталий

    Здравствуйте,

    В связи со свойством 4 у вас пара ошибок:
    1) У вас написано, что свойство верно для выражения x & 125 = 5, а применяете вы его к выражению X & 130 = 3, для которого неизвестно ещё ничего о его верности.
    2) В первом же шаге, у вас «замена» X & 130 = 3 на Z_130 = 3, но проведя обратную замену по определению над свойством 1, получим 3 = Z_130 = ( x & 130 = 1) — тождественно ложное утверждение в множестве натуральных чисел, т.к. 1 не равно 3 в множестве целых.

    И вообще, всем было бы проще и понятнее, если бы вы по-разному обозначали операции в булевой алгебре множеств (\cap, \cup), в кольце целых чисел (+, \times) и логические операции (логическое «или», логическое «и»). Вообще круто было бы ещё и нейтральные элементы обозначать по-разному, хотя бы для булевой алгебры множеств и всего остального.

      admin

      Спасибо большое! постараемся всё учесть)

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

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

*
*

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