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

15-е задание: «Основные законы алгебры логики» Уровень сложности — повышенный, Требуется использование специализированного программного обеспечения — нет, Максимальный балл — 1, Примерное время выполнения — 5 минут.

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

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

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

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

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

выражения в скобках,
операции «НЕ»,
операции «И»,
операции «ИЛИ»,
операции «импликация»
операции «эквиваленция»

Математическая логика и теория множеств

пересечение множеств соответствует логическому умножению, а объединение – логическому сложению;
пересечением двух множеств называется новое множество, состоящее из элементов, принадлежащих одновременно обеим множествам:

Пример:

Пример разности множеств:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обозначим:
Для решения методом, предложенным А.В. Здвижковой, пригодится использование следующих свойств:

На деле, это означает, что если имеем:
то сначала введем замену:
а затем, используя свойство 3, определим истинность высказывания Z29 → Z5:
таким образом, получили:

Так, например, если в задании имеем:
то сначала введем замену и, используя свойство 4, получим:

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

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

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

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

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

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

Введем обозначения:
Выполним преобразования:
Разделим выражение на две части — известную часть и неизвестную. Чтобы неизвестная часть ( А ) была непременно истинной, необходимо, чтобы известная часть была ложна:
То есть получаем:
Таким образом имеем пересечение (умножение) двух множеств Q и P . То есть необходимо выбрать элементы, которые встречаются в обоих множествах одновременно:
Сумма элементов:

Ответ: 12

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

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

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

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

Введем обозначения:
Выполним преобразования:
Разделим выражение на две части — известную часть и неизвестную. Чтобы неизвестная часть ( А ) была непременно истинной, необходимо, чтобы известная часть была ложна:
То есть получаем:
Таким образом имеем пересечение (умножение) двух множеств Q и P . То есть необходимо выбрать элементы, которые встречаются в обоих множествах одновременно:
Сумма элементов:

Ответ: 18

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

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

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

Введем обозначения:
Выполним преобразования:
Разделим выражение на две части — известную часть и неизвестную. Чтобы неизвестная часть ( А ) была непременно истинной, необходимо, чтобы известная часть была ложна:
То есть получаем:
Таким образом имеем разность двух множеств Q и P . То есть это новое множество, элементы которого принадлежат P , но не принадлежат Q :
Количество элементов = 7

Ответ: 7

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

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

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

Введем обозначения:
Выполним преобразования:
Разделим выражение на две части — известную часть и неизвестную. Чтобы неизвестная часть ( А ) была непременно истинной, необходимо, чтобы известная часть была ложна:
То есть получаем:
Таким образом имеем пересечение двух множеств Q и P :
Количество элементов = 1

Ответ: 1

Задания с отрезками на числовой прямой

Отрезки на числовой прямой:

На числовой прямой даны два отрезка: P=[44,48] и Q=[23,35].

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

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

✍ Решение:

Упростим формулу, избавившись от ‘x ϵ‘:
Теперь преобразуем импликацию в скобках:

Результат: 4 ✎ Решение 2 (программирование): Внимание! этот способ подходит НЕ для всех заданий с отрезками! Python:

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) # сами точки отрезка и длина

PascalABC.net:

С подробным аналитическим решением задания 15 ЕГЭ по информатике можно ознакомиться по видео:

📹 Видеорешение на RuTube здесь Отрезки на числовой прямой:

На числовой прямой даны два отрезка: P = [10,20] и Q = [30,40].

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

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

✍ Решение:

Упростим выражение, введя обозначения:
Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно истинной:
Избавимся от импликации:
Используем закон Де Моргана для последующего преобразования:
А — наше неизвестное, а выделенную часть формулы можно найти. Необходимо, чтобы А = 1. Значит, предположим, что ¬А = 0, тогда P ∧ ¬Q = 1 (если P ∧ ¬Q = 0, то ¬А может равняться и 0 и 1, так как имеет место операция логического сложения ∨)
Значит, имеем P ∧ ¬Q = 1. Кроме того, в данном случае имеет место операция конъюнкция, которую проще вычислить, если выражение равно 1 (так как для конъюнкции существует один единственный случай истинности: 1 & 1 = 1). Таким образом имеем утверждения:
Т.е. A истинно (=1) на промежутке пересечения отрезков P и ¬Q.
Отобразим отрезки на числовой прямой, чтобы найти искомое значение:

Результат: 10

Отрезки на числовой прямой:

На числовой прямой даны два отрезка: P = [3, 20] и Q = [6, 12].

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

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

✍ Решение:

Упростим выражение, введя обозначения:
Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно истинной:
Избавимся от импликации:

Далее возможно 2 способа решения.

✎ 2 способ: После того, как мы избавились от импликации, имеем:

Результат: 8

С решением задания 15 вы также можете ознакомиться, посмотрев видео (аналитическое решение):

📹 Видеорешение на RuTube здесь Отрезки на числовой прямой:

На числовой прямой даны два отрезка: P = [11, 21] и Q = [15, 40].

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

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

✍ Решение:

Упростим выражение, введя обозначения:
Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно истинной:
Избавимся от импликации:
А — наше неизвестное, тогда как выделенную часть формулы можно найти. Введем предположение, что А = 1. Значит, ¬А = 0 (т.е. А = 1), тогда ¬(P

Результат: 19
Задания с ДЕЛ Поиск наибольшего А, известная часть Дел ∨ Дел = 1
Для какого наибольшего натурального числа А формула

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

✍ Решение:

Введем обозначения:

Перепишем исходную формулу, согласно введенным обозначениям. Укажем, что формула должна быть тождественно истинна (по условию):

Избавимся от импликации:

Разделим данную формулу на две части: в одной из них — искомое A, а в другой — часть формулы с x, которую можно найти:

В полученной формуле необходимо, чтобы искомая часть с A в конечном счете было истинно.

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

Решение с помощью логических рассуждений:

Решение с помощью кругов Эйлера:

Результат: 8

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

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 )

PascalABC.net:

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.

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

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

✍ Решение:

Избавимся от импликации:

✎ Решение 2 (программирование). Язык Python, Pascal:

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

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

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.

Результат: 3

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

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

✍ Решение:

Введем обозначения:

Перепишем исходную формулу, согласно введенным обозначениям. Укажем, что формула должна быть тождественно истинна (по условию):

Избавимся от импликации:

Разделим данную формулу на две части: в одной из них - искомое A, а в другой - часть формулы с x, которую можно найти:

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

Результат: 285
Задания с поразрядной конъюнкцией
Для какого наименьшего неотрицательного целого числа A формула

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

✍ Решение:

Удалим из формулы X&, чтобы сократить ее запись:

Обратим внимание, что внешней операцией является конъюнкция - логическое умножение:

Разделим общее выражение на две части относительно внешней операции. Первая часть - неизвестная, искомая, а вторая - известная, ее можно вычислить:

Выполним некоторые преобразования во второй части формулы:

Зная свойство импликации, преобразуем формулу (избавимся от импликации в скобках):

Ответ: 3

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

Произвести замену (x & K = 0) на Zk

Выполнить преобразования по свойству импликации и закону Де Моргана.

Стремиться прийти к выражению с конъюнкциями без отрицаний типа: Zk * Zm .

Все выражения типа Zk * Zm преобразовать по свойству Zk * Zm = Zk or m .

Путем преобразований прийти к импликации: Zk → Zm .

Условие Zk → Zm истинно для любых натуральных значений x тогда и только тогда, когда все единичные биты двоичной записи числа M входят во множество единичных битов двоичной записи числа K.

Результат: 3

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

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

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

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

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

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

✍ Решение:

Результат: 38

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

📹 Видеорешение на RuTube здесь Способ 2:

📹 Видеорешение на RuTube здесь Поразрядная конъюнкция:

Определите наименьшее натуральное число А из интервала [43, 55], такое, что выражение

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

✍ Решение:

Кратко изложенное решение *:

Результат: 48

Определите набольшее натуральное число A, такое что выражение

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

✍ Решение:

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

Таким образом, получим следующее выражение:

Упростим выражение по свойству импликации для второй скобки:

Упростим левую часть, используя свойство 2 ( Zk + Zm = Zk and m ):

То есть получили z26 ∨ z13 = z8

По правилу импликации: все единичные биты двоичной записи результата (z78 ∨ A) должны входить во множество единичных битов двоичной записи z8.

Рассмотрим:

Для А единичными битами должны быть общие единичные биты для z8 (10002). Т.е. в нашим случае - это один бит - 3-й:

Результат: 8
Задания на поиск наибольшего или наименьшего числа А
Поиск наибольшего или наименьшего числа А:

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

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.

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 (теоретическое решение):

Условно разделим исходное выражение на части:

(импликация 0 → 0 = 1)

Результат: 99

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

📹 Видеорешение на RuTube здесь Поиск наибольшего или наименьшего числа А:

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

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

✍ Решение:

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.

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 (теоретическое решение):

Определим основные части выражения, выделив отдельно неизвестную часть - с А, и, так сказать, известную часть, то есть остальную.

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

Сначала важно рассмотреть вторую часть выражения, известную, так как от нее будет зависеть значение A. Если вторая часть истинна, то А может быть как = 1, так и = 0. Такой вариант нам не подходит:

Соответственно, рассмотрим вариант, когда вторая часть ложна, тогда часть выражения с неизвестным А будет обязательно истинной, т.е.:

Дизъюнкция ложна, когда оба операнда ложны, т.е. из второго пункта имеем:

Для того, чтобы перекрыть все x и все y, возьмем наибольшие из возможных значений: x = 20, y = 40.

Выразим А:

Поскольку требуется найти наименьшее значение А, то имеем А = 101 .

Результат: 101

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

📹 Видеорешение на RuTube здесь Поиск наибольшего или наименьшего числа А:

Для какого наибольшего целого неотрицательного числа А выражение

✎ Решение 2 (программное): Python:

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

Результат: 15

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

📹 Видеорешение на RuTube здесь Поиск наибольшего или наименьшего числа А:

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

✎ Решение 2 (программное): Python:

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

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

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

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

(2y + 5x 100) ∨ (3x – 2y > 70)

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

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

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.

Результат: 171

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

📹 Видеорешение на RuTube здесь Поиск наибольшего или наименьшего числа А:

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

(3y – x > A) ∨ (2x + 3y ✎ Решение 1 (теоретическое):

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

Смотрите решение подобного задания № 296 (К. Поляков):

📹 Видеорешение на RuTube здесь
Рубрики:
Спасибо. Все понятно!
Светлана Noname
Почему в первой задаче длина отрезка 4,если в отрезок входят: 44,45,46,47,48. Т.е. пять цифр.
Игорь
я думал, что я один такой умный. Замечание правильное. Ответ = 5 . Потому что в задании сказано промежуток, а не отрезок. Крылов с Чуркиной тоже ошиблись 😉 Промежуток (математика) Промежуток, или более точно, промежуток числовой прямой — множество вещественных чисел, обладающее тем свойством, что вместе с любыми двумя числами содержит любое, лежащее между ними. В задаче имеется в виду конечно же промежуток не вещественных, а целых чисел.
admin
Спасибо) значит, исправим само задание: вместо «промежуток» укажем «отрезок»
Аноним
18_10 видео не соответствует задаче.
Аноним Галина
26 в 10-ой =11010 в 2-ой А в целом большое спасибо!
admin Аноним
Последняя задача (18_14.) не соответствует задаче в прикреплённом видеоролике, но ответ указан от задания в видео. Можно узнать правильный ответ?
admin
Там написано, что в видео объясняется подобное задание № 296 К. Полякова
Алекс
Простите, я не понимаю… В примере 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) и логические операции (логическое «или», логическое «и»). Вообще круто было бы ещё и нейтральные элементы обозначать по-разному, хотя бы для булевой алгебры множеств и всего остального.
📎📎📎📎📎📎📎📎📎📎