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

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

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

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

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

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

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

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

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

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

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

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

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

for A := 0 to 31 do begin

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

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

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

Источник

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

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

Например, 14 & 5 = 1110₂ & 0101₂ = 0100₂ = 4.

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

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

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

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

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

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

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

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

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

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

for A := 0 to 127 do begin

for x := 0 to 127 do

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

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

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

Источник

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

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

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

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

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

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

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

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

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

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

Источник

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

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

Рассмотрим скобки раздельно, избавимся от → — импликации (логическое следование).

A→B = A vB => (x > 9) v (x 2 ≤ A) между скобками получилась операция дизъюнкция (логическая сумма), при данной операции истинна будет, если хотя бы одно из выражений истинно. При x>9 [(x > 9) v (x 2 ≤ A)] – уже будет истинным, но при x [0; 9] (диапазон от 0 потому что в условии сказано: при любых целых неотрицательных x и y) выражение в первой скобки станет ложным и возникает необходимость проверки выражения во второй (x 2 ≤ A). В этой ситуации от ложного результата и должна спасти переменная А.

Аналогично рассмотрим вторую часть выражения ((y⋅y ≤ A) → (y ≤ 9)) = 1

т. е. 81 ≤ A A = 99

Ответ: 99

Решение попробую объяснить на следующем примере:

(x^53≠0)=>((x^41=0)=>(x^A≠0)). Как обычно надо найти наименьшее значение А для истинности данного выражения.

Избавляемся от импликации (хоть с помощью переменных или без них):

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

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

(x^53=0) v (x^41≠0) = 0; (x^A≠0) = 1

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

Представим число 53 в двоичной системе счисления и найдем значение x при котором скобка будет истинной:

Представим число 41 в двоичной системе счисления и найдем значение x при котором скобка будет ложной:

Сопоставим полученные числа:

0 и 1 или 0 и х даст – 0; х и х – даст х; 1 и х – даст 1.

Соответственно получим следующее число: 0101х0, т.е. таковым и должно быть число А, но т.к. нам надо найти наименьшее, вместо х проставляем 0 и переводим полученное число в десятичную систему счисления: 010100 = 20

Источник

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

Обозначим через 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.

Источник