Задание 15

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

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

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

    Преобразование логических операций:
  • операцию импликация можно преобразовать в операции ИЛИ и НЕ:
    • A → B = ¬ A ∨ B
    или
    A → B = A + B
  • операцию эквивалентность можно преобразовать:
    • A ↔ B = A ⊕ B = A ∧ B ∨ A ∧ B
    или
    A ↔ B = A ⊕ B = A · B + A · B
  • операцию XOR (сложение по модулю 2) можно преобразовать так:
    • A ⊕ B = (¬A ∧ B) ∨ (A ∧ ¬B)
    или
    A ⊕ B = (A · B) + (A · B)
    Законы алгебры логики:
  • кроме того, могут пригодиться базовые аксиомы и формулы:
    • Закон двойного отрицания:
    ¬¬ A = A
    Закон исключения третьего:
    A ∧ ¬ A = 0 или A · A = 0
    A ∨ ¬ A = 1 или A + A = 1
    Закон повторения (идемпотентности):
    A ∧ A = A или A · A = A
    A ∨ A = A или A + A = A
    Законы исключения логических констант:
    A ∧ 0 = 0
    A ∧ 1 = A
    A ∨ 0 = A
    A ∨ 1 = 1
    Переместительный (коммутативный) закон:
    A ∧ B = B ∧ A
    A ∨ B = B ∨ A
    Сочетательный (ассоциативный) закон:
    (A ∧ B) ∧ C = A ∧ (B ∧ C)
    (A ∨ B) ∨ С = A ∨ (B ∨ С)
    Распределительный (дистрибутивный) закон:
    (A ∧ B) ∨ C = (A ∨ C) ∧ (B ∨ C)
    (A ∨ B) ∧ С = (A ∧ С) ∨ (B ∧ С)
    и наоборот:
    (A ∨ B) ∧ (A ∨ C) = A ∨ (B ∧ C)
    (A ∧ B) ∨ (A ∧ C) = A ∧ (B ∨ C)
    Закон общей инверсии (Законы де Моргана):
    ¬ (A ∧ B) = ¬ A ∨ ¬ B
    ¬ (A ∨ B) = ¬ A ∧ ¬ B
    Закон исключения (склеивания):
    (A ∧ B) ∨(¬A ∧ B) = B
    (A ∨ B) ∧(¬A ∨ B) = B
    Упрощать выражения можно с помощью формул:
    Закон поглощения:
    A ∨ A ∧ B = A
    A ∧ (A ∨ B) = A
    A ∨ ¬A ∧ B = A ∨ B
    ¬A ∨ A ∧ B = ¬A ∨ B
    A ∧ (¬A ∨ B) = A ∧ B
    ¬A ∧ (A ∨ B) = ¬A ∧ B
  • Порядок выполнения логических операций:
    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_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



Множества:

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

Комментарии

Отправить комментарий