15. Алгебра высказываний

Истинностные значения (страница 2)

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела 15. Алгебра высказываний:

Это старая версия каталога задач

Нажмите для перехода на новую версию

Решаем задачи
Задание 8 #9822


Для какого наибольшего целого неотрицательного числа \(A\) выражение
\(\left( y+2x \neq 70 \right) \bigvee (x<y) \bigvee (A<x)\)
тождественно истинно (т.е. принимает значение 1 при любом неотрицательном целом значении переменной \(x\) и \(y)?\)

Показать решение


Чтобы выяснить, при каких \(A\) данное выражение точно истинно, рассмотрим, когда \(\left( y+2x \neq 70 \right) \bigvee (x<y) = 0\) или \( \left( y+2x = 70 \right) \bigwedge (x\geq y) = 1.\) Пары значений \(x\) и \(y,\) при которых это выполняется соответствуют пересечению части плоскости \(U,\) образованной прямыми \(y=0, y=x,\) находящимися в первом координатном секторе (так как нас интересуют только целые неотрицательные значения, будем строить графики в первой координатной четверти), с прямой \(y= 70 - 2x.\)
Если \(A<x,\) то дизъюнкция будет истинной. Значит, нужно подобрать \(A\) таким образом, чтобы при \(A \geq x\) координаты \(x\) и \(y\) не попадали на пересечение \(\left( y+2x = 70 \right) \bigwedge (x\geq y).\)


В точке пересечения прямых \(\left( y=70-2x \right) \) и \( y=x:\)
\(y + 2y =70,\)
\(y = 23 \frac{1}{3}.\)
Ближайшее целое значение, при котором \( \left( y+2x \neq 70 \right) \bigvee (x<y)\) целиком находится в \((A<x)\) это \(A=23.\)

Ответ: 23
Задание 9 #9823


Обозначим через \(m\&n\) поразрядную конъюнкцию неотрицательных целых чисел \(m\) и \(n.\) Так, например, \(14\&5=1110_2 \& 0101_2=0100_2=4.\)
Для какого наибольшего неотрицательного целого числа \(A\) формула
\(x \& A \neq 0 \rightarrow \left( \left( x\& 17=0 \bigwedge x\& 5=0 \right) \rightarrow x\&3 \neq 0 \right) \)
тождественно истинно (т.е. принимает значение 1 при любом неотрицательном целом значении переменной \(x)?\)

Показать решение


По правилу преобразования импликации имеем: \[\begin{aligned} x \& A \neq 0 \rightarrow \left( \left(x\& 17=0 \bigwedge x\& 5=0 \right) \rightarrow x\&3 \neq 0 \right) \,\,\,\equiv\,\,\, \\ x \& A \neq 0 \rightarrow \left(\neg \left( x\& 17=0 \bigwedge x\& 5=0 \right) \bigvee x\&3 \neq 0 \right) \,\,\,\equiv\,\,\, \\ \neg \left(x \& A \neq 0\right) \bigvee \neg \left( x\& 17=0 \bigwedge x\& 5=0 \right) \bigvee x\&3 \neq 0.\end{aligned}\] По закону де Моргана: \[\begin{aligned} \neg \left(x \& A \neq 0\right) \bigvee \neg \left( x\& 17=0 \bigwedge x\& 5=0 \right) \bigvee x\&3 \neq 0 \,\,\,\equiv\,\,\, \\ \neg \left(x \& A \neq 0\right) \bigvee \neg \left( x\& 17=0 \right) \bigvee \neg \left(x\& 5=0 \right) \bigvee x\&3 \neq 0 \,\,\,\equiv\,\,\, \\ x \& A = 0 \bigvee x\& 17 \neq 0 \bigvee x\& 5 \neq 0 \bigvee x\&3 \neq 0.\end{aligned}\] Дизъюнкция ложна, только когда ложны все утверждения, составляющие ее. Выражения во всех скобках, кроме первой, зависят только от \(x,\) поэтому можно определить, при каких значениях переменной они одновременно будут ложными. После этого подберем \(A\) таким образом, чтобы для этих значений \(x\) утверждение в первой скобке было правдой.
Рассмотрим отдельно каждую скобку:

\( \left( x \& 17 \neq 0 \right) = 0 \,\,\,\equiv\,\,\, x \& 17 = 0 .\)
\(17_{10} = 1+16=2^0+2^4=10001_2,\)
значит, поразрядная конъюнкция будет равна 0, если в числе \(x\) будут стоять 0 в тех разрядах, где в двоичном представлении числа 17 стоят 1. То есть последние 5 знаков числа \(x\) должны иметь вид:
\(0 \_ \; \_ \; \_ 0,\)
где на месте \(\_\) может стоять и 0, и 1:
Повторим те же рассуждения для чисел 5 и 3.
\( \left( x \& 5 \neq 0 \right) = 0 \,\,\,\equiv\,\,\, x \& 5 = 0 .\)
\(5_{10} = 1+4=2^0+2^2=101_2.\)
Последние 5 знаков числа \(x\) должны иметь вид:
\(0 \; \_ \; \_ \; \_ \; 0.\)

\( \left( x \& 3 \neq 0 \right) = 0 \,\,\,\equiv\,\,\, x \& 3 = 0.\)
\(3_{10} = 1+2=2^0+2^1=11_2.\)
Последние 5 знаков числа \(x\) должны иметь вид:
\(0 \; \_ \; \_ \; \_ \; 0.\)

Чтобы эти условия условия точно выполнялись одновременно, число \(x\) должно заканчиваться:
\(0 \_ 0 0 0.\)

Гарантированно \(x\&A = 0\) для не более, чем пятизначного числа вида:
\(\_ 0 \_ \; \_ \; \_.\)
Наибольшее значение для числа такого вида соответствует \(10111_2=2^4+2^2+2^1+2^0=16+4+2+1=23.\)

Ответ: 23
Задание 10 #9839


Обозначим через \(m\&n\) поразрядную конъюнкцию неотрицательных целых чисел \(m\) и \(n.\) Так, например, \(14\&5=1110_2 \& 0101_2=0100_2=4.\)
Для какого наименьшего неотрицательного целого числа \(A\) формула
\(x \& 39 = 0 \bigvee \left( x\& 41=0 \rightarrow x\&A \neq 0 \right) \)
тождественно истинно (т.е. принимает значение 1 при любом неотрицательном целом значении переменной \(x)?\)

Показать решение


По правилу преобразования импликации имеем:
\(\left( x \& 39 = 0\right) \bigvee \neg \left( x\& 41=0 \right) \bigvee \left( x\&A\neq0 \right) \,\,\,\equiv\,\,\, \left( x \& 39 = 0\right) \bigvee \left( x\& 41 \neq 0 \right) \bigvee \left( x\&A\neq 0 \right).\)

Дизъюнкция ложна, только когда ложны все утверждения, составляющие ее. Выражения в первой и второй скобках зависят только от \(x,\) поэтому можно определить, при каких значениях переменной они одновременно будут ложными. После этого подберем \(A\) таким образом, чтобы для этих значений \(x\) утверждение в последней скобке было истинно.
Рассмотрим отдельно каждую скобку:

\( \left( x \& 39 = 0 \right) = 0 \,\,\,\equiv\,\,\, x \& 39 \neq 0 .\)
\(39_{10} = 1+2+4+32=2^0+2^1+2^2+2^5=100111_2,\)
значит, поразрядная конъюнкция будет отлична от 0, если в числе \(x\) хотя бы одна единица будет стоять на том же месте, что и в двоичном представлении числа 39. То есть последние 6 цифр числа \(x\) в двоичной системе будут иметь вид:
\(* \_ \; \_ * * *,\)
где вместо \(\_\) может стоять и 0 и 1.

\(\left( x\& 41 \neq 0 \right) = 0 \,\,\,\equiv\,\,\, x\& 41 = 0.\)
\(41_{10}=1+8+32=2^0+2^3+2^5=101001_2,\)
поэтому поразрядная конъюнкция будет равна 0, если в числе \(x\) в тех разрядах, где в двоичном представлении числа 41 стоят 1, будут стоять 0. Тогда последние 6 цифр числа \(x\) должны иметь вид:
\(0 \_ 0 \_ \; \_ 0.\)

Чтобы первое и второе условия точно выполнялись одновременно, последние 6 цифр числа \(x\) должны иметь вид:
\(0 \_ 0 * *\, 0,\)
где вместо хотя бы одной * стоит 1.

Гарантированно \(x\&A\neq 0,\) если в А есть единицы в разрядах, отмеченных * в числе \(x:\)
\(A = \_ \; \_ \; \_11\_ ,\)
Наименьшее значение для числа такого вида соответствует \(110_2=2^1+2^2=6.\)

Ответ: 6
1

2

Рулетка
Вы можете получить скидку в рулетке!