Разбор 18 задания ЕГЭ 2017 по информатике из демоверсии

Разбор 18 задания ЕГЭ 2017 года по информатике из проекта демоверсии. Это задание повышенного уровня сложности. Примерное время выполнения задания 3 минуты.

Проверяемые элементы содержания:
— знание основных понятий и законов математической логики.

Элементы содержания, проверяемые на ЕГЭ:
— высказывания, логические операции, кванторы, истинность высказывания.

Задание 18

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

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

x&51 = 0 ∨ (x&41 = 0 → x&А ≠ 0)

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

Ответ: ________

Разбор 18 задания ЕГЭ 2017

1) Для начала упростим нашу формулу x&51 = 0 ∨ (x&41 = 0 → x&А ≠ 0)

, заменив импликацию простыми логическими операциями используя формулу: A→B = ¬A + B

x&51 = 0 ∨ x&41 ≠ 0 ∨ x&А ≠ 0

2) Рассмотрим первое выражение (x&51 = 0) и узнаем для каких чисел X это выражение будет истинно:
Переведём число 51 в двоичную систему счисления

5110 = 1100112

3) Определяем те значения X, при которых истинно выражение x&51 = 0:
5110 110011
  Х    111111
=0    110011

Если в числе Х на месте 1-го, 2-го, 5-го и 6-го разряда окажутся единицы, то после поразрядной конъюнкции на этих местах также будут стоять единицы, т.е. мы не получим «0» и выражение

(x&51 = 0) будет ЛОЖНО.
Все остальные цифры в числе X могут быть любыми, так как после поразрядной конъюнкции на этих местах все равно будет «0».
Значит первое слагаемое учитывает все числа х, в которых нет на 1-м, 2-м, 5-м и 6-м местах единиц.

4) Рассмотрим второе выражение (x&41 ≠ 0): только для тех чисел Х, у которых на 1-м, 2-м, 5-м и 6-м местах стоят единицы.
Переведём число 41 в двоичную систему счисления

4110 = 1010012

5) Определяем те значения X, при которых истинно выражение x&41 ≠ 0:
4110 101001
  Х    11    11
≠0    10    01

Если в числе Х на месте 2-го и 5-го разряда стоят единицы, то после поразрядной конъюнкции на этих местах будут стоять нули, т.е. мы не получим «1» и выражение (x&41 ≠ 0) будет ложно.
Единицы на 1-м и 6-м месте в числе Х после поразрядной конъюнкции дадут «1» и выражение (x&41 ≠ 0) будет истинно.
Значит второе слагаемое учитывает числа Х, в которых на 1-м и 6-м местах стоят «1» и не учитывает числа

Х, в которых на 2-м и 5-м местах стоят «1».

6) Рассмотрим третье выражение (x&A≠0):
У нас остались неучтенными лишь те числа Х, у которых на 5-м и 2-м месте стоят «1», следовательно, их нужно учесть в числе А.
Минимально возможное такое число это 100102 = 1810

Ответ: 18

infedu.ru

ЕГЭ по информатике задание 18 — Информатика в школе

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

Тема: «Логические выражения и множества».

Элементами множеств A, P, Q являются натуральные числа, причём P = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20}, Q = { 3, 6, 9, 12, 15, 18, 21, 24, 27, 30}. Известно, что выражение

 

истинно (т.е. принимает значение 1) при любом значении переменной x. Определите наименьшее возможное значение суммы элементов множества A.

Данный пример взят из учебно-методического издания «Информатика и ИКТ. Подготовка к ЕГЭ 2018 году. Диагностические работы. — М: МЦНМО, 2018.»

Данную книгу вы можете купить здесь

РЕШЕНИЕ

Еще один вид задания  ЕГЭ по информатике задание 18. Отрезки

Задание №18 ЕГЭ по информатике проверяет знания по темам:

 

amlesson.ru

Решение задания 18 егэ по информатике с помощью таблиц истинности

Л. И. Мазничевская

средняя общеобразовательная школа № 763, Москва

Решение задания 18 ЕГЭ ПО ИНФОРМАТИКЕ С ПОМОЩЬЮ ТАБЛИЦ ИСТИННОСТИ

Аннотация

В статье представлены материалы, предназначенные для использования учителями информатики при подготовке учащихся к ЕГЭ по информатике.

К сожалению, правильно решают задание 18 ЕГЭ по информатике малая часть учащихся. Это связано с тем, что предлагаются различные способы решения этого задания, но эти способы применимы только на некотором сегменте заданий.

В представленных вашему вниманию материалах четыре различных типа задач решаются с помощью составления таблиц истинности. Все задачи выбраны из заданий для тренировки с известного сайта К. Ю. Полякова[1].

Ключевые слова: информатика, таблица истинности, алгоритм, законы алгебры логики, импликация.

Контактная информация

Мазничевская Лариса Ивановна, учитель информатики высшей категории, государственное бюджетное общеобразовательное учреждение города Москвы “Школа № 763”, адрес: 129346, г. Москва, ул. Стартовая, д. 27, к. 3; телефон: (495) 474-90-60; e-mail: mli97@inbox.ru

При решении любого задания 18 ЕГЭ по информатике необходимо знать основные понятия и законы математической логики, а также выполнить следующие шаги алгоритма:

  • определение элементарных высказываний

  • замена переменных (при необходимости)

  • раскрытие импликации или эквивалентности

  • преобразование с использованием законов алгебры логики

  • построение таблиц истинности

  • запись ответа.

Задача 1(105 Поляков)

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

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

Решение:

Введем обозначения и упростим выражение:

=P Q

Вся числовая ось распадается на интервалы, построим таблицу истинности для одного из значений заданного интервала для полученной формулы

Интервал

Значение Х

P

Q



А

Итог

(-;28]

20

0

0

1

0

1

[28;44]

30

0

1

любое

любое

1

[44;49]

48

1

1

любое

любое

1

[49;53]

50

0

1

любое

любое

1

[53;+]

54

0

0

1

0

1

Так как нам нужна наибольшая возможная длина такого отрезка A, чтобы формула

была тождественно истинна, то есть принимала значение 1 при любом значении переменной х, то А принимает значение истинно на [28;53], длина этого отрезка равна 53-28=25

Ответ: 25

Задача 2(135 Поляков)

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

ДЕЛ(x, A)  (ДЕЛ(x, 14)  ДЕЛ(x, 21))

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

Решение:

Упростим выражение:

ДЕЛ(x, A)  (ДЕЛ(x, 14)  ДЕЛ(x, 21))=  ДЕЛ(

x, A) ДЕЛ(x, 14)  ДЕЛ(x, 21)

Определим числа, входящие во множество ДЕЛ(x, 14) и ДЕЛ(x, 21): 14, 21, 28, 42, 56,63…

Построим таблицу истинности для формулы  ДЕЛ(x, A) ДЕЛ(x, 14)  ДЕЛ(x, 21)

Число Х

ДЕЛ(x, 14)

ДЕЛ(x,21)

ДЕЛ(x, 14)  ДЕЛ(x, 21)

Х не кратно А

А

Итог

14

1

0

0

1

0

1

21

0

1

0

1

0

1

28

1

0

0

1

0

1

42

1

1

1

любое

любое

1

56

1

0

0

1

0

1

Необходимо выбрать первое значение А, при котором высказывание «Х не кратно А»может принимать любое значение Х=42, оно является наименьшим.

Ответ: 42

Задача 3(150 Поляков)

Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число A, такое что выражение

(X & 56  0)  ((X & 48 = 0)  (X & A  0))

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

Решение:

Для удобства введем обозначения и упростим выражение

56= X & 56  0

48=X & 48  0

A= X & A  0

(X & 56  0)  ((X & 48 = 0)  (X & A  0))=56  ( 48  A ) = А

Переведем в двоичную систему счисления числа 18, 54

5610=1110002

4810=1100002

Искомое число х – разрядное слагаемое двоичной системы счисления из множества {1, 2, 4,8,16,32}. Построим таблицу истинности

Число Х, его двоичный код

X & 56 = 0

1110002

X & 48  0

1100002

А

X & A  0

Итог

1, 000001

1

0

Любое(0 или1)

1

2, 000010

1

0

Любое(0 или1)

1

4, 000100

1

0

Любое(0 или1)

1

8, 001000

0

0

1

1

16, 010000

0

1

Любое(0 или1)

1

32, 100000

0

1

Любое(0 или1)

1

Из таблицы х=8, оно является наименьшим

Ответ: 8

Задача 4(88 Поляков)

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

(x {2, 4, 6, 8, 10, 12}) → (((x {3, 6, 9, 12, 15})  ¬(x A)) → ¬(x {2, 4, 6, 8, 10, 12}))

истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A.

Решение:

Для удобства введем обозначения и упростим выражение

В=x {2, 4, 6, 8, 10, 12}

С= x {3, 6, 9, 12, 15}

А= x A

(x {2, 4, 6, 8, 10, 12}) → (((x {3, 6, 9, 12, 15})  ¬(x A)) → ¬(x {2, 4, 6, 8, 10, 12}))=B→((C ¬A) → ¬B) = ¬B((C ¬A) → ¬B)= ¬B¬C ¬A) ¬B= ¬B¬C

Построим таблицу истинности

Число Х

¬B

¬C

A

Итог

2

0

1

любое(0 или1)

1

3

1

0

любое(0 или1)

1

4

0

1

любое(0 или1)

1

6

0

0

1

1

8

0

1

любое(0 или1)

1

9

1

0

любое(0 или1)

1

10

0

1

любое(0 или1)

1

12

0

0

1

1

15

1

0

любое(0 или1)

1

6+12=18

Ответ: 8

Литература

  1. http://kpolyakov.spb.ru/school/probook.htm

videouroki.net

КАК НАУЧИТЬ РЕШАТЬ ЗАДАНИЕ 18 ЕГЭ ПО ИНФОРМАТИКЕ

как научить решать задание 18 егэ по информатике

Перед тем как приступать к решению заданий 18 «Проверка истинности логического выражения» экзаменационной работы по информатике, нужно объяснить (или вспомнить) учащимся, что такое понятие «объединение» и «пересечение» нескольких множеств. И так как задание 18 связано с определением отрезков, то и лучше всего эти понятия объяснять на отрезках. Но связать необходимо эти понятия с понятиями алгебры логики – «конъюнкция» и «дизъюнкция», ну и, конечно же, «инверсия». Приведу это все на примере. Для начала рассмотрим инверсию отрезка, или, проще говоря, отрицание отрезка.

Дан отрезок P=[6,15]. Найти отрезки, которые будут инверсией отрезка P=[6,15]. Рассмотрим координатную прямую (рис. 1):

§

рис. 1

На прямой отмечаем отрезок P (синяя область), тогда понятно, что промежутки не P будут промежутки и (зеленая область) – рис. 1. Обращая внимание, что точки 6 и 15 в инверсию отрезка входить не будут.

Рассмотрим еще пример: даны два отрезка P=[6,15] и Q=[8,25]{приведены те же обозначения, что и в задании ЕГЭ, чтобы учащиеся сразу привыкали к обозначениям}. Найти отрезок, который будет обозначать конъюнкцию (объединение) и дизъюнкцию (пересечение) этих отрезков

Рисуем отрезки на координатной прямой (рис. 2):

15

8

25

рис. 2

Сначала отмечаем области на координатной прямой, которые обозначают отрезки P (синий цвет) и Q (желтый цвет). Затем определяем, какая часть координатной прямой будет служить конъюнкцией этих двух отрезков. Здесь вспоминаем, что конъюнкция – это логическая операция, которая объединяем два простых высказывания в сложное с помощью логической связки «и», и сложное высказывание будет приобретать значение «истина» тогда и только тогда, когда истины оба исходных простых высказывания. Таким образом, получаем, что нужно найти области, где и отрезок P и отрезок Q имеют место, а такая область только одна – отрезок [8,15] (красный цвет). Более подробно исследуем все отрезки прямой, чтобы учащимся было нагляднее и понятнее воспринимать материал, итак:

  1. — на этом промежутке отрезки имеют следующие значения («равно 1» – ставим, если любая точка, взятая в этом промежутке будет принадлежат рассматриваемому отрезку, и «равно 0» – если точка не принадлежит отрезку) P=0, Q=0, следовательно, и конъюнкция этих отрезков будет также равна 0.

  2. — P=1, Q=0, конъюнкция отрезков будет равна 0

  3. — P=1, Q=1, конъюнкция отрезков будет равна 1 – это искомый нами отрезок (красный цвет) – рис. 2

  4. — P=0, Q=1, конъюнкция отрезков будет равна 0

  5. — P=0, Q=0, конъюнкция отрезков будет равна 0

Теперь аналогичным образом разберемся с дизъюнкцией этих отрезков. Опять же обратимся к определению этой логической операции – «дизъюнкцией называется логическая операция, которая в соответствии двум и более логическим высказываниям ставит новое, которое истинно тогда и только тогда, когда истинно хотя бы одно из входящих исходных высказываний». То есть другими словами, нам надо найти на координатной прямой такие промежутки, где есть хотя бы один из исходных наших отрезков, этот искомый промежуток будет [6,25] – зеленый цвет (рис. 2). Также разберем каждый из промежутков и покажем, что это действительно так:

  1. — на этом промежутке отрезки имеют следующие P=0, Q=0, следовательно, и дизъюнкция этих отрезков будет также равна 0.

  2. — P=1, Q=0, дизъюнкция отрезков будет равна 1 – искомый промежуток

  3. — P=1, Q=1, дизъюнкция отрезков будет равна 1 – искомый промежуток

  4. — P=0, Q=1, дизъюнкция отрезков будет равна 1 – искомый промежуток

  5. — P=0, Q=0, дизъюнкция отрезков будет равна 0

Объединяя найденные промежутки, получаем что искомый отрезок, обозначающий дизъюнкцию исходных отрезков – это отрезок [6,25] – зеленый цвет (рис. 2).

После разбора данного примера, можно дать учащимся попробовать найти различные сочетания логических операций – дизъюнкции, конъюнкции и отрицания. Например, даны два отрезка P=[-4,10] и Q=[5,30]. Найти отрезок, который будет обозначать следующие логические операции: , , (можно придумать и другие различные сочетания этих логических операций).

  1. решение (рис. 3). Для начала строим координатную прямую и отмечаем на ней отрезки, обозначающие исходные отрезки P=[-4,10] (синяя область) и Q=[5,30] (желтая область). Затем на прямой отмечаем промежутки, которые будут инверсией отрезка P (красные области). А теперь, пользуясь выше разобранным примером, смотрим, какие области будут отвечать за дизъюнкцию инверсии отрезка P и Q. Это будут промежутки и (зеленая область)

рис. 3

  1. решение (рис. 4). Аналогично выше рассмотренному решению строим координатную прямую и отмечаем исходные отрезки. Но в отличие от предыдущего примера, сначала строим инверсию отрезка Q (красные области). Далее вспоминая, как мы искали промежутки, которые будут конъюнкцией двух отрезков, отмечаем тот промежуток, который послужит решением для нашего примера. Это будет (зеленая область) – рис. 4

рис. 4

  1. решение (рис. 5). Решением для данного случая будут области и (10 — зеленая область

рис. 5

Когда разобраны все примеры, то у учащихся не возникнет трудностей с пониманием и решением задания №18 из экзаменационной работы единого государственного экзамена по информатике.

Приведем примеры решений нескольких заданий:

На числовой прямой даны два отрезка: P = [2,42] и Q =[22,62]. Выберите такой отрезок A, что формула

(xA) → ( (x P) → (xQ) ) тождественно истинна, то есть принимает значение 1 при любом значении переменной х. Возможные варианты ответов:

1) [3, 14] 2) [23, 32] 3) [43, 54] 4) [15, 45]

Решение (рис. 6): чтобы упростить понимание выражения, обозначим отдельные высказывания буквами — A: x А, P: x P, Q: x Q. Таким образом, получаем следующее выражение с учетом замены: → ( P →)=1. Равенство выражения 1 говорит о том, что какое бы значение переменной х мы не взяли, наше логическое выражение принимает значение 1, то есть на всей числовой прямой. Вспомним некоторые логические законы и равенства и преобразуем наше выражение: =1. В итоге получаем, что нам надо построить дизъюнкцию трех отрезков, два из которых нам известны. Их то мы и построим (рис. 7). Для начала, как и во всех выше приведенных примерах, мы должны построить инверсии отрезков P (оранжевый цвет) и Q (красный цвет). Затем из всего выражения мы можем определить промежутки дизъюнкции =1 (зеленые области рис. 7). Таким образом получаем, что у нас на координатной прямой есть «свободная» часть — . Эту часть прямой и должен перекрыть искомый отрезок А.

рис. 7

Рассмотрим варианты ответов:

  1. [3, 14] – не подходит этот вариант, так как он не принадлежит совсем «свободной» части — (рис. 8)

рис. 8

  1. [23, 32] – не подходит (рис. 9). Казалось бы, этот отрезок принадлежит «свободной» части — , но он не перекрывает его полностью. Остаются пустые части — [22, 23] и [32, 42]. Тем самым это не вариант решения задания.

рис. 9

  1. [43, 54] — случай аналогичен первому варианту. Этот отрезок не входит в «свободной» часть — (рис. 10)

рис. 10

  1. [15, 45]- этот вариант является верным ответом, так как полностью перекрывает «свободную» часть — (рис. 11), даже выходит за ее пределы, но это не противоречит определению дизъюнкции и является решением данного задания.

рис. 11

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

Задания для решений можно посмотреть на сайте Константина Полякова http://kpolyakov.narod.ru/school/ege.htm.

Литература

  1. http://kpolyakov.narod.ru/school/ege.htm.

infourok.ru

Задача 18 — разбор задания ЕГЭ по предмету Информатика

Решение №2

Можно предложить несколько более короткий подход. Обозначим наше высказывание как F = (A->(B->C)), где А — это высказывание «Х&25 не равно 0», В= «Х&17=0″ и C=»X&A не равно 0».

Раскроем импликации, пользуясь известным законом X->Y = не(Х) ИЛИ Y, получим F = A -> (не(В) ИЛИ C) = не(А) ИЛИ не(B) ИЛИ С. Распишем также двоичные значения констант 25 и 17:

25 = 11001

17 = 10001

Наше выражение — логическое ИЛИ от трёх высказываний:

1) не(А) — это значит, X&25 = 0 (биты 0,3,4 числа Х все равны 0)

2) не(B) — значит, X&17 не равно 0 (биты 0 и 4 числа Х хотя бы один равен 1)

3) C — знаит, X&A не равно 0 (биты, задаваемые маской A, хотя бы 1 равен 1)

Х  — произвольное число. Все его биты независимы. Поэтому требовать выполнения какого-то условия на биты произвольного числа можно только в одном единственном случае — когда речь идёт об одной и той же маске (наборе битов). Мы можем заметить, что двоичная маска 17 — почти то же самое, что и 25, только не хватает бита номер 3. Вот если бы дополнить 17 битом номер 3, то выражение (не(В) ИЛИ С) превратилось бы в не(неА), т.е. в А = (X&25 не равно 0). По-другому: допустим, А=8 (бит 3=1). Тогда требование (не(В) B или С) равносильно требованию: (Хотя бы один из битов 4,0 равен 1) ИЛИ (бит 3 равен 1) = (хотя бы один из битов 0,3,4 не равен 1) — т.е. инверсия не(А) = А = (Х&25 не равно 0).

В итоге мы заметили, что если А=8, то наше выражение принимает вид F = не(А) ИЛИ А, что, по закону исключённого третьего, всегда тождественно истинно. При других, меньших, значениях А независимость от значения Х получить не удаётся, т.к. маски выходят разные. Ну, а при наличии в старших битах А единиц в битах выше 4 ничего не меняется, т.к. в остальных масках у нас нули. Получается, что только при А=8 формула превращается в тавтологию для произвольного Х.

 

Дмитрий Лисин

newtonew.com

КАК НАУЧИТЬ РЕШАТЬ ЗАДАНИЕ 18 ЕГЭ ПО ИНФОРМАТИКЕ

Белова Т.В.
как научить решать задание 18 егэ по информатике

муниципальное бюджетное общеобразовательное учреждение «Лицей»,

г. Арзамас, ya.bellova.tatyana@yandex.ru

Перед тем как приступать к решению заданий 18 «Проверка истинности логического выражения» экзаменационной работы по информатике, нужно объяснить (или вспомнить) учащимся, что такое понятие «объединение» и «пересечение» нескольких множеств. И так как задание 18 связано с определением отрезков, то и лучше всего эти понятия объяснять на отрезках. Но связать необходимо эти понятия с понятиями алгебры логики – «конъюнкция» и «дизъюнкция», ну и, конечно же, «инверсия». Приведу это все на примере. Для начала рассмотрим инверсию отрезка, или, проще говоря, отрицание отрезка.

Дан отрезок P=[6,15]. Найти отрезки, которые будут инверсией отрезка P=[6,15]. Рассмотрим координатную прямую (рис. 1):

ﾧ

рис. 1

На прямой отмечаем отрезок P (синяя область), тогда понятно, что промежутки не P будут промежутки и (зеленая область) – рис. 1. Обращая внимание, что точки 6 и 15 в инверсию отрезка входить не будут.

Рассмотрим еще пример: даны два отрезка P=[6,15] и Q=[8,25]{приведены те же обозначения, что и в задании ЕГЭ, чтобы учащиеся сразу привыкали к обозначениям}. Найти отрезок, который будет обозначать конъюнкцию (объединение) и дизъюнкцию (пересечение) этих отрезков

Рисуем отрезки на координатной прямой (рис. 2):

15

8

25

рис. 2

Сначала отмечаем области на координатной прямой, которые обозначают отрезки P (синий цвет) и Q (желтый цвет). Затем определяем, какая часть координатной прямой будет служить конъюнкцией этих двух отрезков. Здесь вспоминаем, что конъюнкция – это логическая операция, которая объединяем два простых высказывания в сложное с помощью логической связки «и», и сложное высказывание будет приобретать значение «истина» тогда и только тогда, когда истины оба исходных простых высказывания. Таким образом, получаем, что нужно найти области, где и отрезок P и отрезок Q имеют место, а такая область только одна – отрезок [8,15] (красный цвет). Более подробно исследуем все отрезки прямой, чтобы учащимся было нагляднее и понятнее воспринимать материал, итак:

  1. — на этом промежутке отрезки имеют следующие значения («равно 1» – ставим, если любая точка, взятая в этом промежутке будет принадлежат рассматриваемому отрезку, и «равно 0» – если точка не принадлежит отрезку) P=0, Q=0, следовательно, и конъюнкция этих отрезков будет также равна 0.

  2. — P=1, Q=0, конъюнкция отрезков будет равна 0

  3. — P=1, Q=1, конъюнкция отрезков будет равна 1 – это искомый нами отрезок (красный цвет) – рис. 2

  4. — P=0, Q=1, конъюнкция отрезков будет равна 0

  5. — P=0, Q=0, конъюнкция отрезков будет равна 0

Теперь аналогичным образом разберемся с дизъюнкцией этих отрезков. Опять же обратимся к определению этой логической операции – «дизъюнкцией называется логическая операция, которая в соответствии двум и более логическим высказываниям ставит новое, которое истинно тогда и только тогда, когда истинно хотя бы одно из входящих исходных высказываний». То есть другими словами, нам надо найти на координатной прямой такие промежутки, где есть хотя бы один из исходных наших отрезков, этот искомый промежуток будет [6,25] – зеленый цвет (рис. 2). Также разберем каждый из промежутков и покажем, что это действительно так:

  1. — на этом промежутке отрезки имеют следующие P=0, Q=0, следовательно, и дизъюнкция этих отрезков будет также равна 0.

  2. — P=1, Q=0, дизъюнкция отрезков будет равна 1 – искомый промежуток

  3. — P=1, Q=1, дизъюнкция отрезков будет равна 1 – искомый промежуток

  4. — P=0, Q=1, дизъюнкция отрезков будет равна 1 – искомый промежуток

  5. — P=0, Q=0, дизъюнкция отрезков будет равна 0

Объединяя найденные промежутки, получаем что искомый отрезок, обозначающий дизъюнкцию исходных отрезков – это отрезок [6,25] – зеленый цвет (рис. 2).

После разбора данного примера, можно дать учащимся попробовать найти различные сочетания логических операций – дизъюнкции, конъюнкции и отрицания. Например, даны два отрезка P=[-4,10] и Q=[5,30]. Найти отрезок, который будет обозначать следующие логические операции: , , (можно придумать и другие различные сочетания этих логических операций).

  1. решение (рис. 3). Для начала строим координатную прямую и отмечаем на ней отрезки, обозначающие исходные отрезки P=[-4,10] (синяя область) и Q=[5,30] (желтая область). Затем на прямой отмечаем промежутки, которые будут инверсией отрезка P (красные области). А теперь, пользуясь выше разобранным примером, смотрим, какие области будут отвечать за дизъюнкцию инверсии отрезка P и Q. Это будут промежутки и (зеленая область)

рис. 3

  1. решение (рис. 4). Аналогично выше рассмотренному решению строим координатную прямую и отмечаем исходные отрезки. Но в отличие от предыдущего примера, сначала строим инверсию отрезка Q (красные области). Далее вспоминая, как мы искали промежутки, которые будут конъюнкцией двух отрезков, отмечаем тот промежуток, который послужит решением для нашего примера. Это будет (зеленая область) – рис. 4

рис. 4

  1. решение (рис. 5). Решением для данного случая будут области и (10 — зеленая область

рис. 5

Когда разобраны все примеры, то у учащихся не возникнет трудностей с пониманием и решением задания №18 из экзаменационной работы единого государственного экзамена по информатике.

Приведем примеры решений нескольких заданий:

На числовой прямой даны два отрезка: P = [2,42] и Q =[22,62]. Выберите такой отрезок A, что формула

(xA) → ( (x P) → (xQ) ) тождественно истинна, то есть принимает значение 1 при любом значении переменной х. Возможные варианты ответов:

1) [3, 14] 2) [23, 32] 3) [43, 54] 4) [15, 45]

Решение (рис. 6): чтобы упростить понимание выражения, обозначим отдельные высказывания буквами — A: x А, P: x P, Q: x Q. Таким образом, получаем следующее выражение с учетом замены: → ( P →)=1. Равенство выражения 1 говорит о том, что какое бы значение переменной х мы не взяли, наше логическое выражение принимает значение 1, то есть на всей числовой прямой. Вспомним некоторые логические законы и равенства и преобразуем наше выражение: =1. В итоге получаем, что нам надо построить дизъюнкцию трех отрезков, два из которых нам известны. Их то мы и построим (рис. 7). Для начала, как и во всех выше приведенных примерах, мы должны построить инверсии отрезков P (оранжевый цвет) и Q (красный цвет). Затем из всего выражения мы можем определить промежутки дизъюнкции =1 (зеленые области рис. 7). Таким образом получаем, что у нас на координатной прямой есть «свободная» часть — . Эту часть прямой и должен перекрыть искомый отрезок А.

рис. 7

Рассмотрим варианты ответов:

  1. [3, 14] – не подходит этот вариант, так как он не принадлежит совсем «свободной» части — (рис. 8)

рис. 8

  1. [23, 32] – не подходит (рис. 9). Казалось бы, этот отрезок принадлежит «свободной» части — , но он не перекрывает его полностью. Остаются пустые части — [22, 23] и [32, 42]. Тем самым это не вариант решения задания.

рис. 9

  1. [43, 54] — случай аналогичен первому варианту. Этот отрезок не входит в «свободной» часть — (рис. 10)

рис. 10

  1. [15, 45]- этот вариант является верным ответом, так как полностью перекрывает «свободную» часть — (рис. 11), даже выходит за ее пределы, но это не противоречит определению дизъюнкции и является решением данного задания.

рис. 11

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

Задания для решений можно посмотреть на сайте Константина Полякова http://kpolyakov.narod.ru/school/ege.htm.

Литература

  1. http://kpolyakov.narod.ru/school/ege.htm.

kopilkaurokov.ru

Презентация «Теория и практика решения задания 18 ЕГЭ по информатике» скачать

Автор:

учитель информатики МБОУ «Лицей»

первой квалификационной категории

Мурзина Ольга Ивановна

МБОУ «Лицей» г. Арзамас

МКУ ГИМК

Теория и практика решения задания 18 ЕГЭ по информатике

Арзамас, 2017

Мнемоническое правило

Один из ее главных принципов – дополнение до целого (дополнение противоположностью)

Соционика – это информационная психология

Решающая формула

А  ¬А = 1

А  ¬А = 0

В алгебре логики есть формула дополнения до целого:

В некоторых задачах мы будем использовать вместо этой формулы умножение противоположностей:

Типы задания 18

  • Задания на отрезки
  • Задания на множества
  • Задания на поразрядную конъюнкцию
  • Задания на условие делимости

Задания на отрезки

(№ 376) На числовой прямой даны два отрезка: P=[4,15] и Q=[12,20]. Укажите наименьшую возможную длину такого отрезка A, что формула ((x ∈ P) ∧ (x ∈ Q)) → (x ∈ A)

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

Источник — сайт Полякова К.Ю.

Решающая формула

А  ¬А = 1

Для выбора решающей формулы важно внимательно прочитать требование задачи.

В нашей задаче в требовании сказано:

принимает значение 1 при любом значении переменной х.

Выбор решающей формулы очевиден:

Решение задачи на отрезки

  • Легенда
  • Формализация условия
  • Решение логического уравнения
  • Интерпретация полученного результата

Разделим решение задачи на этапы:

Решение задачи на отрезки

Решение задачи на отрезки

2) Формализация условия – перепишем формулу из условия задачи в соответствие с легендой.

Было:

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

Стало:

(P ∧ Q) → A = 1

Решение задачи на отрезки

3) Решение логического уравнения –вначале это, возможно, самый сложный этап в решении задачи. Но позже, при накоплении опыта, он уже не будет казаться таким уж сложным 

Рассмотрим решение логического уравнения по шагам.

Решение задачи на отрезки

3.1. Представим логическое следование в базовых логических операциях по формуле: А → В = ¬А  В:

(P ∧ Q) → A = 1

¬(P ∧ Q)  A = 1

Решение задачи на отрезки

3.2. Сведем получившееся выражение к решающей формуле: А  ¬А = 1 (в алгебре логики справедлив закон коммутативности, т.е. А  ¬А = ¬А  А) :

¬(P ∧ Q)  A = 1, отсюда

¬А = ¬(P ∧ Q)

Ответом в логическом уравнении будет:

А = P ∧ Q.

Решение задачи на отрезки

4) Интерпретация полученного результата.

Наш ответ: А = P ∧ Q.

В алгебре логики это выражение означает пересечение объемов двух логических объектов. По условию нашей задачи – это пересечение отрезков P и Q.

Решение задачи на отрезки

Пересечение отрезков P и Q можно визуализировать: P=[4,15] и Q=[12,20].

4

12

15

20

По условию нашей задачи, нам нужна минимальная длина отрезка А. Находим ее: 15 – 12 = 3.

Ответ: 3.

Ответ на сайте Полякова К.Ю.: 3

Задания на отрезки

(№ 360) На числовой прямой даны три отрезка: P=[10,25], Q=[15,30] и R=[25,40]. Какова максимальная длина отрезка A, при котором формула ((x ∈ Q) → (x ∉ R) ) ∧ (x ∈ A) ∧ (x ∉ P)

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

Источник — сайт Полякова К.Ю.

Решающая формула

А  ¬А = 0

Для выбора решающей формулы важно внимательно прочитать требование задачи.

В нашей задаче в требовании сказано:

принимает значение 0 при любом значении переменной х.

Выбор решающей формулы очевиден:

Решение задачи на отрезки

  • Легенда
  • Формализация условия
  • Решение логического уравнения
  • Интерпретация полученного результата

Решение задачи на отрезки

R = x  R

Q = x  Q

A = x  A

P = x  P

Решение задачи на отрезки

2) Формализация условия

Было:

((x ∈ Q) → (x ∉ R) ) ∧ (x ∈ A) ∧ (x ∉ P) = 0

Стало:

( Q → ¬R ) ∧ A ∧ ¬ P = 0

Решение задачи на отрезки

3) Решение логического уравнения

( Q → ¬R ) ∧ A ∧ ¬ P = 0

3.1. Представим логическое следование в базовых логических операциях по формуле: А → В = ¬А  В, и переставим множители согласно закону коммутативности умножения:

A ∧ (¬ Q  ¬R ) ∧ ¬ P = 0

Решение задачи на отрезки

3) Решение логического уравнения

A ∧ (¬ Q  ¬R ) ∧ ¬ P = 0

3.2. Сведем получившееся выражение к решающей формуле: А  ¬А = 0 и найдем, чему равно ¬А :

¬А = (¬ Q  ¬R ) ∧ ¬ P

Решение задачи на отрезки

3) Решение логического уравнения

¬А = (¬ Q  ¬R ) ∧ ¬ P

3.3. Упростим выражение для ¬А по закону де Моргана ¬А¬В=¬(АВ):

¬А = ¬ (Q  R ) ∧ ¬ P,

и по другому закону де Моргана ¬А¬В=¬(АВ):

¬А = ¬ (Q  R  P)

Решение задачи на отрезки

3) Решение логического уравнения

¬А = ¬ (Q  R  P)

3.4. Очевидно, что

А = Q  R  P

Решение задачи на отрезки

4) Интерпретация полученного результата

А = Q  R  P

Отрезок А – это пересечение отрезков Q и R и его объединение с отрезком Р.

Решение задачи на отрезки

Пересечение отрезков R и Q можно визуализировать: Q=[15,30] и R=[25,40].

15

25

30

40

Отрезок P=[10,25] нанесем на наш чертеж и объединим с пересечением:

15

25

30

40

10

Решение задачи на отрезки

15

25

30

40

10

По условию нашей задачи, нам нужна максимальная длина отрезка А. Находим ее: 30 – 10 = 20.

Ответ: 20.

А = Q  R  P

Ответ на сайте Полякова К.Ю.: 20

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

(№ 386) Элементами множеств А, P, Q являются натуральные числа, причём P={1,2,3,4,5,6}, Q={3,5,15}. Известно, что выражение (x ∉ A) → ((x ∉ P) ∧ (x ∈ Q)) ∨ (x ∉ Q)

истинно (т.е. принимает значение 1 при любом значении переменной х. Определите наименьшее возможное количество элементов в множестве A.

Источник — сайт Полякова К.Ю.

Решение задачи на множества

  • Легенда
  • Формализация условия
  • Решение логического уравнения
  • Интерпретация полученного результата

Решение задачи на множества

  • Легенда

    • A = x ∈ A

    P = x ∈ P

    Q = x ∈ Q

Решение задачи на множества

2) Формализация условия

Было:

(x ∉ A) → ((x ∉ P) ∧ (x ∈ Q)) ∨ (x ∉ Q) = 1

Стало:

¬ A → (¬P ∧ Q)  ¬ Q = 1

Решение задачи на множества

3) Решение логического уравнения

¬ A → (¬P ∧ Q)  ¬ Q = 1

3.1. Представим логическое следование в базовых логических операциях и сгруппируем:

A  ((¬P ∧ Q)  ¬ Q) = 1

Решение задачи на множества

A  ((¬P ∧ Q)  ¬Q) = 1

3.2. Сведем получившееся выражение к решающей формуле:

А  ¬А = 1

и найдем, чему равно ¬А :

¬А = (¬P ∧ Q)  ¬Q

Решение задачи на множества

¬А = (¬P ∧ Q)  ¬Q

3.3. Упростим выражение для ¬А, раскрыв скобки по закону дистрибутивности сложения:

¬А = (¬P  ¬Q)  (Q  ¬Q)

Q  ¬Q = 1

¬А = (¬P  ¬Q)

Решение задачи на множества

¬А = (¬P  ¬Q)

По закону де Моргана:

¬А = ¬(P  Q)

3.4. Очевидно, что

А = P  Q

Решение задачи на множества

А = P  Q

4) Интерпретация полученного результата

Искомое множество А представляет собой пересечение множеств P и Q.

Решение задачи на множества

Искомое множество А есть пересечение множеств

P = 1, 2, 3, 4, 5, 6 и Q ={3, 5,15}, таким образом A ={3, 5}

и содержит только 2 элемента.

Ответ: 2

Ответ на сайте Полякова: 2

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

(№ 368) Элементами множеств А, P, Q являются натуральные числа, причём P={2,4,6,8,10,12} и Q={4,8,12,116}. Известно, что выражение (x ∈ P) → (((x ∈ Q) ∧ (x ∉ A)) → (x ∉ P))

истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A.

Источник — сайт Полякова К.Ю.

  • Легенда
  • Формализация условия
  • Решение логического уравнения
  • Интерпретация полученного результата

Решение задачи на множества

  • Легенда

    • A = x ∈ A

    P = x ∈ P

    Q = x ∈ Q

Решение задачи на множества

2) Формализация условия

Было:

(x ∈ P)→(((x ∈ Q) ∧ (x ∉ A))→(x ∉ P)) = 1

Стало:

P → ((Q ∧ ¬A) → ¬P) = 1

Решение задачи на множества

Решение задачи на множества

3) Решение логического уравнения

P → ((Q ∧ ¬A) → ¬P) = 1

3.1. Представим первое логическое следование (в скобках) в базовых логических операциях :

P → (¬(Q ∧ ¬A)  ¬P) = 1

Решение задачи на множества

P → (¬(Q ∧ ¬A)  ¬P) = 1

Представим второе логическое следование в базовых логических операциях, применим закон де Моргана и перегруппируем:

¬P (¬(Q ∧ ¬A)  ¬P) = 1

¬P ¬Q  A  ¬P = 1

Решение задачи на множества

A  (¬P ¬Q  ¬P) = 1

3.2. Сведем получившееся выражение к решающей формуле:

А  ¬А = 1

и найдем, чему равно ¬А :

¬А = (¬P ¬Q  ¬P)

Решение задачи на множества

¬А = ¬P ¬Q  ¬P

3.3. Упростим выражение для ¬А по формуле А  А = А:

¬А = ¬P ¬Q

Далее, по закону де Моргана получаем:

¬А = ¬(P Q)

Решение задачи на множества

¬А = ¬(P Q)

3.4. Очевидно, что

А = P Q

4) Интерпретация полученного результата

Искомое множество А представляет собой пересечение множеств P и Q.

Решение задачи на множества

Искомое множество А есть пересечение множеств

P = 2, 4, 6, 8, 10, 12 и

Q ={4, 8, 12, 16}, таким образом

A ={4, 8, 12}

и содержит только 3 элемента, сумма которых 4+8+12=24 .

Ответ: 24

Ответ на сайте Полякова: 24

3. Задания на поразрядную конъюнкцию

(№ 379) Обозначим через m&n пораз-рядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14 & 5 = 11102 & 01012 = 01002 = 4. Для какого наименьшего неотрицательного целого числа А формула (x & 29 ≠ 0) → ((x & 12 = 0) → (x & А ≠ 0))

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

  • Легенда
  • Формализация условия
  • Решение логического уравнения
  • Интерпретация полученного результата

Решение задачи на поразрядную конъюнкцию

  • Легенда

    • Легенда для задач на поразрядную конъюнкцию отличается от всех остальных случаев:

    B = (x & 29 ≠ 0) 

    C = (x & 12  ≠  0)

    A = (x & А ≠ 0)

Решение задачи на поразрядную конъюнкцию

Мы принимаем за истинное высказывание поразрядную конъюнкцию, отличную от нуля, иначе поразрядная конъюнкция теряет свой логический смысл, т.к. всегда можно представить Х всеми нулями.

Решение задачи на поразрядную конъюнкцию

2) Формализация условия

Было:

(x & 29 ≠ 0)→((x & 12 = 0)→(x & А ≠ 0))=1

Стало:

В → (¬С → А) = 1

Решение задачи на поразрядную конъюнкцию

3) Решение логического уравнения

В → (¬С → А) = 1

В → (С А) = 1

(¬В  С) А = 1

¬А = ¬В  С

¬А = ¬(В ¬ С)

Очевидно, что

А = В ¬ С

Решение задачи на поразрядную конъюнкцию

Решение задачи на поразрядную конъюнкцию

4) Интерпретация полученного результата

Искомое двоичное значение поразрядной конъюнкции А – это двоичное значение поразрядной конъюнкции значения В и инверсии двоичного значения С.

Решение задачи на поразрядную конъюнкцию

B = (x & 29 ≠ 0)

В или 29 = 111012 

C = (x & 12  ≠  0)

12 = 11002

¬С или инверсия 12 = 00112

Решение задачи на поразрядную конъюнкцию

В или 29 = 111012 

¬С или инверсия 12 = 00112

А = В ¬ С

х111012

00112

100012

А = 100012 = 17

Ответ на сайте Полякова: 17

3. Задания на поразрядную конъюнкцию

(№ 375) Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответ-ствующими битами двоичной записи). Определите наименьшее натуральное число A, такое что выражение (X & 49 ≠ 0) → ((X & 33 = 0) → (X & A ≠ 0))

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

  • Легенда
  • Формализация условия
  • Решение логического уравнения
  • Интерпретация полученного результата

Решение задачи на поразрядную конъюнкцию

  • Легенда

    • Легенда для задач на поразрядную конъюнкцию отличается от всех остальных случаев:

    B = (x & 49 ≠ 0) 

    C = (x & 33 ≠  0)

    A = (x & А ≠ 0)

Решение задачи на поразрядную конъюнкцию

2) Формализация условия

Было:

(X & 49 ≠ 0) → ((X & 33 = 0) → (X & A ≠ 0))=1

Стало:

В → (¬С → А) = 1

Решение задачи на поразрядную конъюнкцию

3) Решение логического уравнения

В → (¬С → А) = 1

В → (С  А) = 1

(¬В  С)  А = 1

¬А = (¬В  С)

Очевидно:

А = В ¬С

Решение задачи на поразрядную конъюнкцию

Решение задачи на поразрядную конъюнкцию

4) Интерпретация полученного результата

Искомое двоичное значение поразрядной конъюнкции А – это двоичное значение поразрядной конъюнкции значения В и инверсии двоичного значения С.

Решение задачи на поразрядную конъюнкцию

B = (x & 49 ≠ 0)

В или 49 = 1100012 

C = (x & 33  ≠  0)

33 = 1000012

¬С или инверсия 33 = 0111102

Решение задачи на поразрядную конъюнкцию

В или 49 = 1100012

¬С или инверсия 33 = 0111102

А = В ¬ С

х1100012

0111102

0100002

А = 100002 = 16

Ответ на сайте Полякова: 16

4. Задания на условие делимости

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

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

Источник — сайт Полякова К.Ю.

  • Легенда
  • Формализация условия
  • Решение логического уравнения
  • Интерпретация полученного результата

Решение задачи

на условие делимости

Решение задачи

на условие делимости

Легенда простая: А = ДЕЛ(x,А)

21 = ДЕЛ(х,21)

35 = ДЕЛ(x,35)

2) Формализация условия

Решение задачи

на условие делимости

Было:

¬ДЕЛ(x,А) → (¬ДЕЛ(x,21) ∧ ¬ДЕЛ(x,35))

¬А → (¬21 ∧ ¬35) = 1

тождественно истинна (то есть принимает значение 1)

Стало:

3) Решение логического уравнения

Решение задачи

на условие делимости

¬А → (¬21 ∧ ¬35) = 1

А (¬21 ∧ ¬35) = 1

¬А = ¬21 ∧ ¬35

Очевидно, что

А = 21  35

4) Интерпретация полученного результата

А = 21  35

В данной задаче это самый сложный этап решения. Нужно понять, что же представляет из себя число А – НОК или НОД или …

Решение задачи

на условие делимости

4) Интерпретация полученного результата

А = 21  35

Итак, наше число А таково, что Х делится на него без остатка, тогда и только тогда, когда Х делится без остатка на 21 или на 35. В этом случае ищем

А = НОД (21, 35) = 7

Решение задачи

на условие делимости

Ответ на сайте Полякова: 7

4. Задания на условие делимости

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

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

Источник — сайт Полякова К.Ю.

  • Легенда
  • Формализация условия
  • Решение логического уравнения
  • Интерпретация полученного результата

Решение задачи

на условие делимости

  • Легенда

    • А = ДЕЛ(x,А)

    6 = ДЕЛ(x,6)

    4 = ДЕЛ(x,4)

Решение задачи

на условие делимости

2) Формализация условия

Решение задачи

на условие делимости

Было:

¬ДЕЛ(x,А) → ((ДЕЛ(x,6) → ¬ДЕЛ(x,4))

тождественно истинна (то есть принимает значение 1

Стало:

¬А → (6 → ¬4) = 1

3) Решение логического уравнения

¬А → (6 → ¬4) = 1

¬А → (¬ 6  ¬4) = 1

А  (¬ 6  ¬4) = 1

¬А = ¬ 6  ¬4

Очевидно:

А = 64

Решение задачи

на условие делимости

4) Интерпретация полученного результата

А = 64

Итак, А таково, что Х делится на него без остатка тогда и только тогда, когда Х делится без остатка и на 6, и на 4. Т.е. А = НОК(6, 4) = 12

Ответ на сайте Полякова: 12

Решение задачи

на условие делимости

Рефлексия

Оцените, пожалуйста, свой уровень понимания, достигнутый на занятии, по шкале от 0 до 10.

Сможете ли Вы теперь объяснить решение задания 18 своим ученикам или друзьям?

(да, нет, не знаю).

Спасибо за внимание!

uchitelya.com