ЕГЭ информатика 15 задание разбор, теория, как решать.
Преобразование логических выражений, (П) — 1 балл
Теория и практика решения задания 15 ЕГЭ по информатике
Соционика – это информационная психология
Один из ее главных принципов – дополнение до целого ( дополнение противоположностью )
В алгебре логики есть формула дополнения до целого:
А ¬А = 1
В некоторых задачах мы будем использовать вместо этой формулы умножение противоположностей:
А ¬А = 0
Типы задания 15
Задания на отрезки
тождественно истинна, то есть принимает значение 1 при любом значении переменной х.
Источник — сайт Полякова К.Ю.
Для выбора решающей формулы важно внимательно прочитать требование задачи.
В нашей задаче в требовании сказано:
Выбор решающей формулы очевиден:
Решение задачи на отрезки
Разделим решение задачи на этапы:
Введем следующие обозначения:
P = x P
Q = x Q
A = x A
2) Формализация условия – перепишем формулу из условия задачи в соответствие с легендой.
3) Решение логического уравнения – вначале это, возможно, самый сложный этап в решении задачи. Но позже, при накоплении опыта, он уже не будет казаться таким уж сложным
Рассмотрим решение логического уравнения по шагам.
¬ (P ∧ Q) A = 1
3.2. Сведем получившееся выражение к решающей формуле: А ¬А = 1 (в алгебре логики справедлив закон коммутативности, т.е. А ¬А = ¬А А) :
¬(P ∧ Q) A = 1, отсюда
¬А = ¬(P ∧ Q)
Ответом в логическом уравнении будет:
А = P ∧ Q.
4) Интерпретация полученного результата .
Наш ответ: А = P ∧ Q .
В алгебре логики это выражение означает пересечение объемов двух логических объектов. По условию нашей задачи – это пересечение отрезков P и Q .
По условию нашей задачи, нам нужна минимальная длина отрезка А . Находим ее: 15 – 12 = 3 .
Ответ: 3 .
Ответ на сайте Полякова К.Ю.: 3
тождественно ложна, то есть принимает значение 0 при любом значении переменной х?
принимает значение 0 при любом значении переменной х.
R = x R
2) Формализация условия
A ∧ (¬ Q ¬R ) ∧ ¬ P = 0
A ∧ ( ¬ Q ¬R ) ∧ ¬ P = 0
3.2. Сведем получившееся выражение к решающей формуле: А ¬А = 0 и найдем, чему равно ¬А :
¬А = (¬ Q ¬R ) ∧ ¬ P
3.3. Упростим выражение для ¬А по закону де Моргана ¬А ¬В=¬(А В) :
¬А = ¬ (Q R ) ∧ ¬ P,
и по другому закону де Моргана ¬А ¬В =¬(А В ) :
¬А = ¬ (Q R P)
3.4. Очевидно, что
А = Q R P
Отрезок А – это пересечение отрезков Q и R и его объединение с отрезком Р .
По условию нашей задачи, нам нужна максимальная длина отрезка А . Находим ее: 30 – 10 = 20 .
Ответ: 20 .
Ответ на сайте Полякова К.Ю.: 20
2. Задания на множества
истинно (т.е. принимает значение 1 при любом значении переменной х. Определите наименьшее возможное количество элементов в множестве A.
Решение задачи на множества
A = x ∈ A
P = x ∈ P
Q = x ∈ Q
3.1. Представим логическое следование в базовых логических операциях и сгруппируем:
A ((¬P ∧ Q) ¬ Q) = 1
A (( ¬P ∧ Q) ¬Q) = 1
¬А = (¬P ∧ Q) ¬Q
3.3. Упростим выражение для ¬А, раскрыв скобки по закону дистрибутивности сложения:
¬А = ( ¬P ¬Q) (Q ¬Q)
Q ¬Q = 1
По закону де Моргана:
¬А = ¬(P Q)
А = P Q
Искомое множество А представляет собой пересечение множеств P и Q.
Искомое множество А есть пересечение множеств
и содержит только 2 элемента.
Ответ на сайте Полякова: 2
истинно (т. е. принимает значение 1 ) при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A.
3.1. Представим первое логическое следование (в скобках) в базовых логических операциях :
Представим второе логическое следование в базовых логических операциях, применим закон де Моргана и перегруппируем:
¬ P ( ¬ (Q ∧ ¬ A) ¬ P) = 1
¬ P ¬ Q A ¬ P = 1
A ( ¬ P ¬ Q ¬ P) = 1
и найдем, чему равно ¬А :
¬А = ( ¬ P ¬ Q ¬ P)
¬А = ¬ P ¬ Q ¬ P
3.3. Упростим выражение для ¬А по формуле А А = А :
Далее, по закону де Моргана получаем:
¬А = ¬( P Q)
P = 2, 4 , 6, 8 , 10, 12 и
и содержит только 3 элемента, сумма которых 4+8+12=24 .
Ответ на сайте Полякова: 24
3. Задания на поразрядную конъюнкцию
тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х)?
Решение задачи на поразрядную конъюнкцию
Легенда для задач на поразрядную конъюнкцию отличается от всех остальных случаев:
B = (x & 29 ≠ 0)
C = (x & 12 ≠ 0)
A = (x & А ≠ 0)
Мы принимаем за истинное высказывание поразрядную конъюнкцию, отличную от нуля, иначе поразрядная конъюнкция теряет свой логический смысл, т.к. всегда можно представить Х всеми нулями.
(¬В С) А = 1
¬А = ¬В С
¬А = ¬(В ¬ С)
А = В ¬ С
Искомое двоичное значение поразрядной конъюнкции А – это двоичное значение поразрядной конъюнкции значения В и инверсии двоичного значения С .
В или 29 = 11101 2
12 = 1100 2
¬С или инверсия 12 = 0011 2
х 11101 2
А = 1 0001 2 = 17
Ответ на сайте Полякова: 17
тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)?
B = (x & 49 ≠ 0)
C = (x & 33 ≠ 0)
(¬В С) А = 1
¬А = (¬В С)
А = В ¬С
В или 49 = 110001 2
C = (x & 33 ≠ 0)
33 = 100001 2
¬С или инверсия 33 = 011110 2
х 110001 2
А = 1 0000 2 = 16
Ответ на сайте Полякова: 16
4. Задания на условие делимости
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
Легенда простая: А = ДЕЛ(x,А)
21 = ДЕЛ(х,21)
35 = ДЕЛ(x,35)
тождественно истинна (то есть принимает значение 1)
А (¬21 ∧ ¬35) = 1
¬А = ¬21 ∧ ¬35
А = 21 35
Итак, наше число А таково, что Х делится на него без остатка, тогда и только тогда, когда Х делится без остатка на 21 или на 35. В этом случае ищем
А = НОД (21, 35) = 7
Ответ на сайте Полякова: 7
6 = ДЕЛ(x,6)
4 = ДЕЛ(x,4)
А (¬ 6 ¬4) = 1
¬А = ¬ 6 ¬4
А = 6 4
Итак, А таково, что Х делится на него без остатка тогда и только тогда, когда Х делится без остатка и на 6, и на 4. Т.е. А = НОК(6, 4) = 12
Ответ на сайте Полякова: 12
A ) ∨ ( x A ) истинно для любых целых положительных значений x и y . » width=»640″
5. Задания на функции
Укажите наибольшее целое значение А, при котором выражение
( y + 2 x 99) ∨ ( y A ) ∨ ( x A )
A ) or ( x A ) выполнялось при всех x и y , для которых ложно ( y + 2 x 99) , то есть истинно ( y + 2 x = 99) или y = –2 x + 99 » width=»640″
1) первое выражение не зависит от выбора A :
2) таким образом, нам нужно выбрать значение A так, чтобы условие ( y A ) or ( x A ) выполнялось при всех x и y , для которых ложно ( y + 2 x 99) , то есть истинно ( y + 2 x = 99) или y = –2 x + 99
A ) or ( x A ) для некоторого значения A , например, для A = 50 (конечно, нужно учесть, что x и y положительны и добавить ещё два ограничения: ( x 0) and ( y 0) ): » width=»640″
3) нарисуем линию y = –2 x + 99 , а также заштрихуем область ( y A ) or ( x A ) для некоторого значения A , например, для A = 50 (конечно, нужно учесть, что x и y положительны и добавить ещё два ограничения: ( x 0) and ( y 0) ):
4) по условию задачи нужно, чтобы все точки отрезка прямой y = –2 x + 99 в первой четверти плоскости оказались в заштрихованной зоне
5) поэтому все точки образовавшегося белого квадрата, в том числе и его вершина ( A, A ) , должны находиться строго под этим отрезком; такой квадрат, соответствующий максимальному значению A , выделен на рисунке зелёной штриховкой
6) находим координаты вершины зелёного квадрата: находим точку пересечения прямых y = –2 x + 99 и y = x ; эта задача сводится к линейному уравнению x = –2 x + 99 решение которого – x = 33
7) значение A должно быть меньше этого x , поэтому максимальное значение A = 32
50) ∨ (4 y – x истинно для любых целых положительных значений x и y . » width=»640″
Укажите наименьшее целое значение А, при котором выражение
( y + 3 x A ) ∨ (2 y +x 50) ∨ (4 y – x
50) or (4 y – x 2) таким образом, нам нужно выбрать значение A так, чтобы условие ( y + 3 x A ) выполнялось при всех x и y , для которых ложно (2 y +x 50) or (4 y – x y +x 50) and (4 y – x 40) 3) последние два условия можно переписать в виде ( y – x /2 + 25) and ( y x /4 + 10) » width=»640″
1) второе и третье выражения не зависят от выбора A : (2 y +x 50) or (4 y – x
0) and ( y 0) 5) изобразим схематично на плоскости x – y эту область (она заштрихована): » width=»640″
4) поскольку по условию x и y должны быть положительны, добавляем ещё два условия: ( y – x /2 + 25) and ( y x /4 + 10) and ( x 0) and ( y 0)
6) для всех точек этой области должно выполняться условие y + 3 x A , равносильное условию y x +A
7) это значит, что вся область должна лежать ниже линии y = – 3 x +A ; одна такая подходящая линия показана на рисунке сверху
75 откуда следует, что A min = 76. Ответ: 76 » width=»640″
8) из рисунка видно, что при параллельном переносе вниз, соответствующем изменению A , она коснётся заштрихованной области в правой вершине заштрихованного треугольника
9) найдём эту точку пересечения:
y = – x /2 + 25 = x /4 + 10 x = 20, y = 15
10) поэтому допустимые значение A определяются условием: 15 +A A 75 откуда следует, что A min = 76.
