ГДЗ по информатике, 10 класс, Босова, номер 20.10: Преобразование логических выражений

Дано выражение: ((x&46=0)lor(x∉18=0))→((x&115≠0)lor(x&A=0)) Здесь используются побитовые операции: - & — конъюнкция (И), результат равен 0, если хотя бы один из операндов имеет нулевой бит в соответствующей позиции. - ∉ — обычно в таких задачах это опечатка или специфическая запись. В контексте ЕГЭ/ОГЭ по информатике часто встречается оператор & (И). Однако символ ∉ может означать проверку на отсутствие пересечения множеств битов, что эквивалентно (x&18=0). Если же это строгая математическая нотация принадлежности, то она не применима к числам напрямую без определения множества. Исходя из стандартных задач этого типа, предположим, что здесь имелась в виду операция побитового И с условием равенства нулю, то есть (x&18=0). Но давайте посмотрим внимательнее. Часто в таких задачах используется оператор & (AND). Запись x∉18 нестандартна. Возможно, это опечатка вместо x&18. Допустим, левая часть скобки означает: «биты числа x не пересекаются с битами числа 46 ИЛИ биты числа x не пересекаются с битами числа 18». Обозначим: L₁=(x&46=0) L₂=(x&18=0) (предполагаем исправление ∉ на &) R₁=(x&115≠0) R₂=(x&A=0) Выражение принимает вид: (L₁lorL₂)→(R₁lorR₂). Импликация P→Q ложна только тогда, когда P=1 и Q=0. Чтобы выражение было тождественно истинным, не должно существовать такого x, при котором antecedent (левая часть) истинен, а consequent (правая часть) ложен. То есть, для всех x, если (L₁lorL₂)=1, то обязательно (R₁lorR₂)=1. Это равносильно тому, что множество значений x, удовлетворяющих условию (L₁lorL₂)=1 и (R₁lorR₂)=0, пусто. Условие (R₁lorR₂)=0 означает, что оба слагаемых ложны: R₁=0⇒x&115=0 R₂=0⇒x&A≠0 Таким образом, нам нужно, чтобы не нашлось ни одного x, которое одновременно удовлетворяет трём условиям: 1. (x&46=0)lor(x&18=0) — ИСТИНА 2. x&115=0 — ИСТИНА 3. x&A≠0 — ИСТИНА Если такое x существует, то для него левая часть импликации равна 1, а правая равна 0 (так как R₁=0 и R₂=0), и вся импликация становится ложной. Значит, мы должны подобрать A так, чтобы любое x, удовлетворяющее условиям 1 и 2, автоматически нарушало условие 3 (то есть x&A=0). Иными словами: Для всех x, таких что [(x&46=0)lor(x&18=0)] и [x&115=0], должно выполняться x&A=0. Чтобы найти максимальное A, нужно рассмотреть все возможные биты числа x, которые могут быть единицами при выполнении условий 1 и 2. Число A не должно иметь единиц в тех позициях, где у допустимых x может стоять единица. Наоборот, A может иметь единицы только там, где у всех допустимых x гарантированно стоят нули. Но подождите, условие x&A=0 должно выполняться для ВСЕХ допустимых x. Это значит, что A не должен пересекаться ни с одним битом ни одного допустимого x. То есть A должен быть таким, что A&x=0 для любого x из множества допустимых. Это возможно только если A не содержит тех битов, которые встречаются в объединении всех допустимых x. Максимальное такое A будет состоять из всех битов, которые НЕ встречаются ни в одном допустимом x (в пределах разрядной сетки, обычно 7-8 бит для этих чисел). Давайте определим множество допустимых x. Условия на x: А) x&115=0 Б) (x&46=0)lor(x&18=0) Рассмотрим двоичные представления чисел. 115₁₀=64+32+16+2+1=1110011₂ 46₁₀=32+8+4+2=101110₂ 18₁₀=16+2=10010₂ Запишем их в виде таблиц битов (разряды от 0 до 6, так как 115<128): Разряды: 6 5 4 3 2 1 0 115: 1 1 1 0 0 1 1 46: 0 1 0 1 1 1 0 18: 0 0 1 0 0 1 0 Условие А: x&115=0. Это означает, что в тех разрядах, где у 115 стоит 1, у x ОБЯЗАТЕЛЬНО должен стоять 0. Разряды с 1 в 115: 6,5,4,1,0. Следовательно, для любого допустимого x: x₆=0,x₅=0,x₄=0,x₁=0,x₀=0. Оставшиеся свободные разряды для x: 3 и 2. То есть x может иметь ненулевые значения только в разрядах 3 и 2. Возможные значения x (в рамках этих разрядов): 0000000₂(0), 0000100₂(4), 0001000₂(8), 0001100₂(12). Проверим, какие из этих x удовлетворяют условию Б. Условие Б: (x&46=0)lor(x&18=0). Поскольку мы уже знаем, что x₆=x₅=x₄=x₁=x₀=0, проверим пересечение с 46 и 18 только по оставшимся разрядам 3 и 2. Число 46 в разрядах 3,2: 46=...1110₂. Разряды 3 и 2 у 46 равны 1 и 1 соответственно (8+4=12, остаток 34 делится на 16? Нет. 46=32+8+4+2. Разряд 5(32)=1, 4(16)=0, 3(8)=1, 2(4)=1, 1(2)=1, 0(1)=0$. Итак, маска 46 в интересующих нас разрядах (3,2): 1,1. Маска 18 в интересующих нас разрядах (3,2): 18=16+2. Разряд 4(16)=1, 3(8)=0, 2(4)=0, 1(2)=1, 0(1)=0$. Итак, маска 18 в разрядах (3,2): 0,0. Теперь переберем возможные варианты x (только разряды 3 и 2): 1. x=0 (x₃=0,x₂=0). x&46: разряды 3,2 дают 0&1=0. Остальные разряды x нулевые. Значит x&46=0. Условие Б выполнено (первая часть истина). 2. x=4 (x₃=0,x₂=1). x&46: разряд 2 у x равен 1, у 46 равен 1. Результат ≠0. Первая часть ложна. x&18: разряды 3,2 у 18 равны 0,0. Значит x&18=0. Вторая часть истинна. Условие Б выполнено. 3. x=8 (x₃=1,x₂=0). x&46: разряд 3 у x равен 1, у 46 равен 1. Результат ≠0. Первая часть ложна. x&18: разряды 3,2 у 18 равны 0,0. Значит x&18=0. Вторая часть истинна. Условие Б выполнено. 4. x=12 (x₃=1,x₂=1). x&46: разряды 3,2 дают 1&1=1. Результат ≠0. Первая часть ложна. x&18: разряды 3,2 дают 0. Результат 0. Вторая часть истинна. Условие Б выполнено. Вывод: Все возможные значения x, удовлетворяющие условию А (x&115=0), также удовлетворяют условию Б. То есть множество допустимых x полностью определяется условием А. Допустимые x имеют нули в разрядах 6,5,4,1,0. Они могут иметь единицы в разрядах 3 и 2. Нам нужно, чтобы для всех таких x выполнялось x&A=0. Это означает, что A не должен иметь единиц в тех разрядах, где хотя бы у одного допустимого x может стоять единица. Какие разряды могут быть единицами у допустимых x? Разряды 3 и 2. Следовательно, A должен иметь нули в разрядах 3 и 2. Какие разряды у A могут быть единицами? Те, где у ВСЕХ допустимых x гарантированно стоят нули. Из условия А мы знаем, что у всех допустимых x нули в разрядах 6,5,4,1,0. Значит, A может иметь единицы в разрядах 6,5,4,1,0. Чтобы A было наибольшим, ставим единицы во все эти разрешённые разряды. Разряды A: 6,5,4,3,2,1,0 Значения: 1,1,1,0,0,1,1 Переведем в десятичную систему: A=2⁶+2⁵+2⁴+2¹+2⁰ A=64+32+16+2+1 A=112+3 A=115 Проверка: Если A=115, то x&A=x&115. По условию А мы рассматриваем только те x, для которых x&115=0. Значит, для всех допустимых x условие x&A=0 выполняется. Импликация истинна. Можно ли взять больше? Следующее число, содержащее биты вне разрядов 3 и 2, например, добавив бит 3? Нет, бит 3 запрещён, так как есть допустимое x=8 (бит 3 равен 1), и тогда x&A≠0, что сделает правую часть импликации ложной (при условии, что R₁ тоже ложно, а оно ложно по построению множества). Если добавить бит 3 к A, то для x=8 получим 8&(115+8)=8≠0. Тогда правая часть (R₁lorR₂) станет (0lor0)=0? Нет, R₂=(x&A=0) станет ложью (0), но в формуле справа стоит дизъюнкция (R₁lorR₂). Подождите. Вернемся к структуре: Правая часть импликации: (x&115≠0)lor(x&A=0). Мы хотим, чтобы эта часть была ИСТИНОЙ для всех x, удовлетворяющих левой части. Левая часть истинна для всех x, где x&115=0 (как мы выяснили, подмножество). Для таких x первое слагаемое правой части (x&115≠0) ЛОЖНО (0). Значит, чтобы вся правая часть была ИСТИНОЙ, второе слагаемое (x&A=0) должно быть ИСТИНОЙ. То есть для всех x из множества допустимых должно выполняться x&A=0. Это ровно то условие, которое мы решали выше. Максимальное A, не пересекающееся ни с одним допустимым x, получается установкой единиц во все разряды, которые никогда не бывают единицами у допустимых x. Допустимые x имеют нули в разрядах 6,5,4,1,0. Единицы возможны в 3,2. Значит, A может иметь единицы в 6,5,4,1,0 и обязан иметь нули в 3,2. Максимальное A=1110011₂=115. Ответ: 115.