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

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

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

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

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

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

Преобразуем выражение по законам алгебры логики:

¬Х → (Y → ¬Z) = Х + (Y → ¬Z) = Х + ¬Y + ¬Z = X + ¬(YZ) = YZ → X.

Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте) без дополнительных пояснений.

Имеем импликацию Z₁₇Z_A → Z₂₅ или Z_{(17 or A)} → Z₂₅. Запишем число 25 в двоичной системе счисления: 25₁₀ = 11001₂. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поскольку 17₁₀ = 10001₂, двоичная запись искомого числа А должна содержать единичный бит в третьем разряде (как обычно, считая справа налево, начиная с нуля).

Тем самым, наименьшее А = 1000₂ = 8₁₀.

Приведём другое решение.

Решим задание с помощью языка программирования PascalABC методом перебора:

for A := 0 to 31 do begin

if not (((x and 25) = 0) or ((x and 17) <> 0) or ((x and A) <> 0)) then

Приведём решение на языке Python.

Заметим, что можно не перебирать числа, большие 31, поскольку для записи чисел 25 и 17 хватит пяти разрядов. Программа выведет ответ 8.

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

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

Преобразуем выражение по законам алгебры логики:

¬Х → (Y → ¬Z) = Х + (Y → ¬Z) = Х + ¬Y + ¬Z = X + ¬(YZ) = YZ → X.

Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте), без дополнительных пояснений.

Имеем импликацию Z₁₂Z_A → Z₂₉ или Z_{(12 or A)} → Z₂₉. Запишем число 29 в двоичной системе счисления: 29₁₀ = 11101₂. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поскольку 12₁₀ = 01100₂, двоичная запись искомого числа А должна содержать единичные биты в нулевом и четвертом разрядах (как обычно, считая справа налево, начиная с нуля).

Тем самым, наименьшее А = 10001₂ = 17₁₀.

Приведём другое решение.

Решим задание с помощью языка программирования PascalABC методом перебора:

for A := 0 to 31 do begin

if not (((x and 29) = 0) or ((x and 12) <> 0) or ((x and A) <> 0)) then

Приведём решение на языке Python.

Заметим, что можно не перебирать числа, большие 31, поскольку для записи чисел 29 и 12 хватит пяти разрядов. Программа выведет ответ 17.

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.

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

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

Преобразуем выражение по законам алгебры логики:

(¬Х + ¬Y) → (W → ¬Z) = ¬(¬Х + ¬Y) + (¬W + ¬Z) = ХY + ¬(WZ) = WZ → XY.

Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте), без дополнительных пояснений.

Имеем импликацию Z₁₇Z_A → Z₂₈Z₄₅ или Z_{(17 or А)} → Z_{(28 or 45)}. Поскольку 28₁₀ = 11100₂, 45₁₀ = 101101₂, для побитовой дизъюнкции имеем: 28or45 = 111101. Тогда Z_{(17 or А)} = Z₆₁.

Импликация принимает вид Z_{(17 or A)} → Z₆₁. Единичные биты двоичной записи числа 61, должны являться единичными битами левой части. Поэтому в побитовой дизъюнкции 17orA единицы должны стоять на нулевой, второй, третьей, четвертой и пятой позициях (как обычно, считая справа налево, начиная с нуля). Запишем числа 17, А и 61 в двоичной системе счисления, и выясним, что наименьшее число, дающее при поразрядной дизъюнкции единицы на указанных позициях:

Приведём другое решение.

Решим задание с помощью языка программирования PascalABC методом перебора:

for A := 0 to 63 do begin

if not (((x and 28) = 0) and ((x and 45) = 0) or ((x and 17) <> 0) or ((x and A) <> 0)) then

Приведем аналогичную программу на языке Python.

Заметим, что можно не перебирать числа, большие 63, поскольку для записи чисел 28, 45 и 17 хватит шести разрядов. Программа выведет ответ 44.

Источник

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

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.

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

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

Преобразуем выражение по законам алгебры логики:

Х + (Y → Z) = Х + (¬Y + Z) = Х + Z + ¬Y = Y → (X + Z) = (Y → X) + (Y → Z).

Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте), без дополнительных пояснений.

Заметим, что первое слагаемое логической суммы является импликацией Z₄₁ → Z₅₁, которая не является истинной для всех х (см. ниже). Тогда необходимо и достаточно, чтобы второе слагаемое логической суммы было тождественно истинным.

Действительно, например, для х = 2 поразрядная конъюнкция с числом 41 дает 0, а с числом 51 дает 2. Поэтому импликация (2&41) → (2&51) принимает вид 1 → 0 — ложь.

2&41: 000000, то есть 2&41 = 0. Высказывание 2&41 = 0 истинно.

2&51: 000010 = 2, то есть 2&51 = 2. Высказывание 2&51 = 0 ложно.

Итак, импликация Z₄₁ → Z_A должна быть тождественно истинной. Запишем число 41 в двоичной системе счисления: 41₁₀ = 101001₂. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поэтому в правой части единичными битами независимо друг от друга могут быть (а могут не быть) только нулевой, третий и пятый биты (как обычно, считая справа налево, начиная с нуля). Поскольку искомое A — наименьшее неотрицательное целое число, в его записи нет единичных битов.

Тем самым, наименьшее А = 000000₂ = 0₁₀.

Приведем другое решение.

Выражение x&51 = 0 ∨ (x&41 = 0 → x&А = 0) истинно, если истинной является импликация x&41 = 0 → x&А = 0. Импликация является истинной, если истинна ее правая часть, то есть x&А = 0. Поразрядная конъюнкция с нулем равна 0 для любого числа, поэтому при А = 0 выражение тождественно истинно. В задании требуется найти наименьшее неотрицательное число А, при котором выражение тождественно истинно, следовательно, 0 удовлетворяет этому условию.

Приведём другое решение.

Решим задание с помощью языка программирования PascalABC методом перебора:

for A := 0 to 63 do begin

if not (((x and 51) = 0) or ((x and 41) <> 0) or ((x and A) = 0)) then

Приведём аналогичное решение на языке Python.

Заметим, что можно не перебирать числа, большие 63, поскольку для записи чисел 41 и 51 хватит шести разрядов. Программа выведет ответ 0.

Источник

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

На числовой прямой задан отрезок A. Известно, что формула

тождественно истинна при любом вещественном x. Какую наименьшую длину может иметь отрезок A?

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

будет иметь решения для любых вещественных чисел.

Чтобы решениями системы были все вещественные числа, необходимо и достаточно, чтобы решениями каждой из совокупностей были все вещественные числа.

Решениями неравенства являются все числа из отрезка [−10; 10]. Чтобы совокупность выполнялась для всех вещественных чисел, числа x, не лежащие на указанном отрезке, не должны принадлежать отрезку A. Следовательно, отрезок A не должен выходить за пределы отрезка [−10; 10].

Аналогично, решениями неравенства являются числа из лучей и Чтобы совокупность выполнялась для всех вещественных чисел, числа x, не лежащие на указанных лучах, должны лежать на отрезке A. Следовательно, отрезок A должен содержать в себе отрезок [−8; 8].

Тем самым, наименьшая длина отрезка A может быть равна 8 + 8 = 16.

О длине отрезка написано в примечании к задаче 11119.

Источник

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

На числовой прямой задан отрезок A. Известно, что формула

тождественно истинна при любых вещественных x и y. Какую наибольшую длину может иметь отрезок A?

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

будет иметь решения для любых вещественных чисел.

Чтобы решениями системы были все вещественные числа, необходимо и достаточно, чтобы решениями каждой из совокупностей были все вещественные числа.

Решениями неравенства являются все числа из отрезка [−9; 9]. Чтобы совокупность выполнялась для всех вещественных чисел, числа x, не лежащие на указанном отрезке, не должны принадлежать отрезку A. Следовательно, отрезок A не должен выходить за пределы отрезка [−9; 9].

Аналогично, решениями неравенства являются числа из лучей и Чтобы совокупность выполнялась для всех вещественных чисел, числа у, не лежащие на указанных лучах, должны лежать на отрезке A. Следовательно, отрезок A должен содержать в себе отрезок [−6; 6].

Тем самым, наибольшая длина отрезка A может быть равна 9 + 9 = 18.

Рекомендуем сравнить эту задачу с задачей 15955.

Источник

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

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 12&6 = 1100₂&0110₂ = 0100₂ = 4.

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

х&А → (x&36 = 0 → х&6)

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

Преобразуем выражение по законам алгебры логики:

¬Х → (Y → ¬Z) = Х + (Y → ¬Z) = Х + ¬Y + ¬Z = X + ¬(YZ) = YZ → X.

Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте), без дополнительных пояснений.

Имеем импликацию Z₃₆Z₆ → Z_A или Z_{(36 or 6)} → Z_A. Запишем числа 36 и 6 в двоичной системе счисления: 36₁₀ = 100100₂, 6₁₀ = 110₂, найдем побитовую дизъюнкцию: 100110. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поэтому в правой части единичными битами независимо друг от друга могут быть (а могут не быть) только первый, второй или пятый биты (как обычно, считая справа налево, начиная с нуля).

Тем самым, наибольшее А = 100110₂ = 38₁₀.

Приведём другое решение.

Решим задание с помощью языка программирования PascalABC методом перебора:

for A := 0 to 63 do begin

if not (((x and 6) <> 0) or ((x and 36) <> 0) or ((x and (63-A)) = 0)) then

Приведём аналогичное решение на языке Python.

Заметим, что можно не перебирать числа, большие 63, поскольку для записи чисел 6 и 36 хватит шести разрядов. Программа выведет ответ 38.

Источник