Решение заданий 18 егэ по информатике

19.01.2024

1. Пример из демонстрационного варианта

(первая буква согласная → вторая буква согласная) / (предпоследняя буква гласная → последняя буква гласная)

1) КРИСТИНА 2) МАКСИМ 3) СТЕПАН 4) МАРИЯ

Набросок решения Импликация a → b равносильна выражению ¬a / b.

Первая импликация верна для слов КРИСТИНА и СТЕПАН. Из этих слов вторая импликация верна только для слова КРИСТИНА.

Ответ: 1. КРИСТИНА

2.Еще два примера

Пример 1 (открытый сегмент банка ФИПИ)

Какое из приведённых имён удовлетворяет логическому условию:

(первая буква согласная → первая буква гласная) / (последняя буква гласная → последняя буква согласная)

1. ИРИНА 2. МАКСИМ 3. АРТЁМ 4. МАРИЯ

Набросок решения . Импликация a → b равносильна выражению ¬a / b. Это выражение истинно если или выражение a ложно, или оба выражения a и b истинны. Поскольку в нашем случае ни в одной из импликаций оба выражения одновременно истинными быть не могут, то должны быть ложными утверждения «первая буква согласная» и «последняя буква гласная», то есть нам нужно слово, у которого первая буква гласная, а последняя - согласная.

Ответ: 3. АРТЁМ.

Пример 2. Для какого из указанных значений числа X истинно высказывание

(X < 4)→(X >15)

1) 1 2) 2 3) 3 4) 4

Решение. Никакое число не может быть одновременно меньше 4 и больше 15. Поэтому импликация истинна только, если посылка X < 4 ложна.

Ответ 4.

2. Задачи в формате ЕГЭ 2013-2014 гг.

2.1. Демо-версия 2013 г.

На числовой прямой даны два отрезка: P = и Q = .

Выберите такой отрезок A, что формула

1) 2) 3) 4)

2.2. Демо-версия 2014 г.

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

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

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

Варианты ответов: 1) 2) 3) 4)

Решение. Преобразуем выражение, используя . Имеем:

¬((x ∈ P) → ¬ (x ∈ Q)) ∨ (¬ (x ∈ А)) - замена импликации дизъюнкцией;

¬(¬(x ∈ P) ∨ ¬ (x ∈ Q)) ∨ (¬ (x ∈ А)) - замена импликации дизъюнкцией;

((x ∈ P) ∧ (x ∈ Q)) ∨ (¬ (x ∈ А)) - правило де Моргана и снятие двойного отрицания;

(x ∈ А) → ((x ∈ P) ∧ (x ∈ Q)) - замена дизъюнкции импликацией

Последнее выражение является тождественно истинным тогда и только тогда, когда A ⊆ P∩ Q = ∩ = (см. ). Из четырех данных отрезков этому условию удовлетворяет только отрезок - вариант №2.

Ответ: - вариант №2

3. Задачи в формате ЕГЭ 2015-2016 гг.

3.1. Задача 1.

На числовой прямой даны два отрезка: P = и Q = .

Известно, что границы отрезка A - целочисленные точки и для отрезка A, формула

((x ∈ А) → (x ∈ P)) \/ (x ∈ Q)

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

Какова наибольшая возможная длина отрезка A?

Правильный ответ: 10

Решение:

Преобразуем выражение – заменим импликацию дизъюнкцией. Получим:

(¬(x ∈ А)) \/ ((x ∈ P)) \/ (x ∈ Q)

Выражение ((x ∈ P)) \/ (x ∈ Q) истинно для тех только тех x, которые лежат либо в P, либо в Q, иными словами – для x ∈ R = P ∪ Q = ∪ . Выражение

(¬(x ∈ А)) \/ (x ∈ R)

тождественно истинно тогда и только тогда, когда A ∈ R. Так как A – отрезок, то A ∈ R тогда и только тогда, когда A ∈ P или A ∈ Q. Так как отрезок Q длиннее отрезка P, то наибольшая длина отрезка A достигается, когда A = Q = . Длина отрезка A в этом случае равна 30 – 20 = 10.

3.2. Задача 2.

Обозначим через m &n поразрядную конъюнкцию неотрицательных целых чисел m и n . Так, например, 14&5 = 1110 2 &0101 2 = 0100 2 = 4. Для какого наименьшего неотрицательного целого числа А формула

x &25 ≠ 0 → (x &33 ≠ 0 → x &А ≠ 0)

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

Правильный ответ: 57

Решение:

Преобразуем выражение – заменим импликации дизъюнкциями. Получим:

¬(x &25 ≠ 0) ∨ (¬(x &33 ≠ 0) ∨ x &А ≠ 0)

Раскроем скобки и заменим отрицания неравенств равенствами:

x &25 = 0 ∨ x &33 = 0 ∨ x &А ≠ 0 (*)

Имеем: 25 = 11001 2 и 33 = 100001 2 . Поэтому формула

x &25 = 0 ∨ x &33 = 0

ложна тогда и только тогда, когда двоичная запись числа x содержит 1 хотя бы в одном из следующих двоичных разрядов: 100000 (32), 10000 (16), 1000 (8) и 1.

Чтобы формула (*) была истинна при всех таких x необходимо и достаточно, чтобы двоичная запись числа A содержала 1 во всех этих разрядах. Наименьшее такое число – это число 32+16+8+1 = 57.

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

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

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

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

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

Арзамас, 2017

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

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

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

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

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

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

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

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

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

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

тождественно истинна, то есть принимает значение 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

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

А  ¬А = 1 (в алгебре логики справедлив закон коммутативности, т.е. А  ¬А = ¬А  А) :

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

¬А = ¬(P ∧ Q)

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

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

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

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

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

Пересечение отрезков P и Q можно визуализировать: P= и Q=.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Легенда

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

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

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

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

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

(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= и R=.

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

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

По условию нашей задачи, нам нужна максимальная длина отрезка А. Находим ее: 30 – 10 = 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.

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

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

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

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

Легенда

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

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. Сведем получившееся выражение к решающей формуле:

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

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

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

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

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

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

¬А = (¬P  ¬Q)

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

¬А = (¬P  ¬Q)

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

¬А = ¬(P  Q)

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

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

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

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

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

и содержит только 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.

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

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

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

Легенда

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

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. Сведем получившееся выражение к решающей формуле:

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

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

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

¬А = ¬P ¬Q  ¬P

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

¬А = ¬(P Q)

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

¬А = ¬(P Q)

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

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

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

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

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

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

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

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

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

(№ 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 = 00112

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

В или 29 = 111012

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

А = В ¬ С

А = 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 = 0111102

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

В или 49 = 1100012

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

А = В ¬ С

011110 2

А = 100002 = 16

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

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

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

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

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

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

Легенда

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

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

Легенда простая: А = ДЕЛ(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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Легенда

А = ДЕЛ(x,А)

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

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

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

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

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

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

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

¬А → (6 → ¬4) = 1

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

¬А → (6 → ¬4) = 1

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

А  (¬ 6  ¬4) = 1

¬А = ¬ 6  ¬4

Очевидно:

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

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

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

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

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

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

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

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

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

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

Для решения этой задачи нам потребуется сделать несколько логических умозаключений, поэтому "следите за руками".

От нас хотят, чтобы мы нашли минимальное целое неотрицательное А, при котором выражение всегда истинно.
Что из себя представляет выражение в целом? Что-то там импликация что-то там в скобках.
Давайте вспомним таблицу истинности для импликации:
1 => 1 = 1
1 => 0 = 0
0 => 1 = 1
0 => 0 = 1
Значит, возможно три варианта, когда это будет истинно. Рассматривать все эти три варианта — это убиться и не жить. Давайте подумаем, можем ли мы пойти "от противного ".
Давайте вместо того, чтобы искать А, попробуем найти x, при котором это выражение ложно.
То есть, возьмём некоторое число А (пока не знаем какое, просто какое-то). Если вдруг мы найдём такое x, при котором всё высказывание ложно, значит, выбранное А — плохое (потому что в условии требуется, чтобы всегда выражение было истинным)!
Таким образом мы сможем получить какие-то ограничение на число А.
Итак, давайте пойдём от противного и вспомним, когда импликация бывает ложной? Когда первая часть истинна, а вторая — ложна.
Значит
\((\mathrm{x}\&25\neq 0)= 1 \\ (\mathrm{x}\&17=0\Rightarrow \mathrm{x}\&\mathrm{A}\neq 0) = 0\)
Что означает, что \((x\&25\neq 0) = 1\) ? Это означает, что действительно \(\mathrm{x}\&25\neq 0\) .
Давайте переведём 25 в двоичную. Получим: 11001 2 .
Какие ограничения это накладывает на x? Раз не равно нулю, значит, при поразрядной конъюнкции должна где-то получиться единица. Но где она может быть? Только там, где в 25 уже есть единица!
Значит, в числе x хотя бы в одном кресте должна быть единица: XX**X.
Отлично, теперь рассмотрим второй множитель: \((\mathrm{x}\&17=0\Rightarrow \mathrm{x}\&\mathrm{A}\neq 0) = 0\)
Это выражение из себя также представляет импликацию. При этом оно так же ложно.
Значит, его первая часть обязана быть истинной, а вторая — ложной.
Значит
\((\mathrm{x}\&17=0) = 1 \\ ((\mathrm{x}\&\mathrm{A}\neq 0) = 0) = 0\)
Что означает, что \(\mathrm{x}\&17=0\) ? То, что на всех местах, где в 17 стоят единицы, в x должны стоять нули (иначе в результате не получится 0).
Переведём 17 в двоичную: 10001 2 . Значит, в x на последнем с конца и на 5 с конца месте должны стоять нули.
Но стоп, мы же в пункте 13 получили, что на последнем ИЛИ на 4 с конца ИЛИ на 5 с конца должна быть единица.
Раз согласно строке 19 на последнем или 5 с конца местах единицы быть не может, значит, она обязана быть на 4 с конца месте.
То есть, если мы хотим, что при нашем x всё выражение было ложным, на 4 с конца месте обязана стоять единица: XX...XX1XXX 2 .
Отлично, рассмотрим теперь последнее условие: \((\mathrm{x}\&\mathrm{A}\neq 0) = 0\) . Что это означает?
Это означает, что неверно, что \(\mathrm{x}\&\mathrm{A}\neq 0\) .
То есть, на самом деле, \(\mathrm{x}\&\mathrm{A}=0\) .
Что мы знаем про x? Что на 4 с конца месте там единица. Во всём остальном x может быть практически любым.
Если мы хотим, чтобы исходное выражение в условии задачи было всегда истинным, то мы не должны найти х, который бы удовлетворял всем условиям. Ведь, действительно, если бы мы нашли такой x, получилось бы, что исходное выражение не всегда истинно, что противоречит условию задачи.
Значит, вот это самое последнее условие просто обязано не выполняться.
А как оно может не выполняться? Если только мы будем уверены на 100%, что при поразрядной конъюнкции где-то останется единица.
И это возможно: если в А тоже на 4 месте с конца будет единица, то в результате поразрядной конъюнкции на 4 с конца месте останется единица.
Какое минимально возможное двоичное число имеет единицу на 4 с конца месте? Очевидно, что 1000 2 . Значит, это число и будет ответом.
Осталось только перевести его в десятичную: \(1000_2=0\times 2^0 + 0\times 2^1 + 0\times 2^2 + 1\times 2^3=8\)

Ответ: минимально возможное A, удовлетворяющее условиям, равно 8 .

Евгений Смирнов

Эксперт в IT, учитель информатики

Решение №2

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

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

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

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 формула превращается в тавтологию для произвольного Х.

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

Задание 18 Каталог заданий. Логические высказывания

1. Задание 18 № 701. Для какого имени ложно высказывание:

(Первая буква имени гласная → Четвертая буква имени согласная).

1) ЕЛЕНА

2) ВАДИМ

3) АНТОН

4) ФЕДОР

Пояснение.

Импликация ложна тогда и только тогда, когда посылка истинна, а следствие ложно. В нашем случае - если первая буква имени гласная и четвертая буква гласная. Этому условию удовлетворяет имя Антон.

Примечание.

Тот же результат следует из следующих преобразований: ¬ (A → B) = ¬ (¬ A ∨ B) = A ∧ (¬ B).

Правильный ответ указан под номером 3.

2. Задание 18 № 8666. На числовой прямой даны два отрезка: P = и Q = . Укажите наибольшую возможную длину промежутка A, для которого формула

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

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

Пояснение.

Преобразуем данное выражение:

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

((x A) ∨ (x P)) → ((x не A) ∨ (x Q))

¬(( x принадл A ) ∨ ( x принадл P )) ∨ (( x не принадл A ) ∨ ( x принадл Q ))

( x не принадл A ) ∧ ( x не принадл P ) ∨ ( x принадл A ) ∨ ( x не принадл Q )

( x не принадл A ) ∨ ( x принадл Q )

Таким образом, либо x должен принадлежать Q, либо не принадлежать A. Это значит, что для достижения истинности для всех x, необходимо, чтобы A полностью содержался в Q. Тогда максимум, каким он сможет стать, это всем Q, то есть длиной 15.

3. Задание 18 № 9170. На числовой прямой даны два отрезка: P = и Q = .

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

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

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

Пояснение.

Преобразуем данное выражение.

(( x € A ) → ¬( x принадл P )) → (( x принадл A ) → ( x принадл Q ))

(( x не принадл A ) ∨ ( x не принадл P )) → (( x не принадл A ) ∨ ( x принадл Q ))

¬((x не принадл A) ∨ (x не принадл P)) ∨ ((x не принадл A) ∨ (x принадл Q))

Верно, что A ∧ B ∨ ¬A = ¬A ∨ B. Применим это здесь, получим:

(x принадл P) ∨ (x не принадл A) ∨ (x принадл Q)

То есть либо точка должна принадлежать Q, либо принадлежать P, либо не принадлежать А. Это значит, что А может покрывать все точки, которые покрывают P и Q. То есть A = P Q = = . |A| = 48 - 10 = 38.

4. Задание 18 № 9202. Элементами множеств А, 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) при любом значении переменной х.

5. Задание 18 № 9310. Элементами множеств А, P, Q являются натуральные числа, причём P = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}, Q = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50}.

Известно, что выражение

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

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

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

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

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

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

(Задание М. В. Кузнецовой)

7. Задание 18 № 9768. Обозначим через m & n m и n 2 & 0101 2 = 0100 2 А формула

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

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

8. Задание 18 № 9804. Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n . Так, например, 14 & 5 = 1110 2 & 0101 2 = 0100 2 = 4. Для какого наименьшего неотрицательного целого числа А формула

x & 29 ≠ 0 → (x & 17 = 0 → x & А ≠ 0)

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

9. Задание 18 № 723. Для какого имени истинно высказывание:

Третья буква гласная → ¬ (Первая буква согласная \/ В слове 4 гласных буквы)?

1) Римма

2) Анатолий

3) Светлана

4) Дмитрий

Пояснение.

Применим преобразование импликации:

Третья буква Согласная ∨ (Первая буква Гласная ∧ В слове НЕ 4 гласных буквы)

Дизъюнкция истинна, когда истинно хотя бы одно высказывание. Следовательно, подходит только вариант 1.

10. Задание 18 № 4581. Какое из приведённых имён удовлетворяет логическому условию:

(первая буква согласная → последняя буква согласная) /\ (первая буква гласная → последняя буква гласная)?

Если таких слов несколько, укажите самое длинное из них.

1) АННА

2) БЕЛЛА

3) АНТОН

4) БОРИС

Пояснение.

Логическое И истинно только тогда, когда истинны оба утверждения.(1)

Импликация ложна только тогда,когда из истины следует ложь.(2)

Вариант 1 подходит по всем условиям.

Вариант 2 не подходит из за условия (2).

Вариант 3 не подходит из за условия (2).

Вариант 4 подходит по всем условиям.

Необходимо указать самое длинное из слов, следовательно, ответ 4.

Задания для самостоятельного решения

1. Задание 18 № 711. Какое из приведенных названий стран удовлетворяет следующему логическому условию: ((последняя буква согласная) \/ (первая буква согласная)) → (название содержит букву «п») ?

1) Бразилия

2) Мексика

3) Аргентина

4) Куба

2. Задание 18 № 709. Какое из приведённых имен удовлетворяет логическому условию:

(Первая буква гласная) ∧ ((Четвёртая буква согласная) ∨ (B слове четыре буквы))?

1) Сергей

2) Вадим

3) Антон

4) Илья

№3