Математика ЕГЭ
Русский язык ЕГЭ
Математика 5-7
Математика ОГЭ
Информатика
Физика
Обществознание
Кликните, чтобы открыть меню

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

1. Вспоминай формулы по каждой теме
2. Решай новые задачи каждый день
3. Вдумчиво разбирай решения

Истинностные значения

Задание 1 #9814


Для какого целого \(X\) истинно высказывание:
\(\neg \left(\left(X>3 \right)\rightarrow \left(X>4 \right) \right)?\)


По правилу преобразования импликации имеем:
\(\neg \left(\left(X>3\right)\rightarrow \left(X>4\right)\right)\,\,=\,\, \neg \left(\neg \left(X>3\right) \bigvee \left(X>4\right)\right). \)
По закону де Моргана:
\(\neg \left(\neg \left(X>3\right) \bigvee \left(X>4\right)\right)\,\,=\,\,\neg\left(\neg\left(X>3\right)\right)\bigwedge \neg \left(X>4\right)\,\,=\,\, \left(X>3\right) \bigwedge \neg \left(X>4\right) \,\,=\,\, \left(X>3\right) \bigwedge \left(X\leq4\right). \)
Конъюнкция истинна, когда истинны все утверждения, которые ее составляют. Поэтому \(X\) лежит в полуинтервале \((3;4].\) Единственное целое значение на данном промежутке \(X=4.\)
Замечание.
При решении мы воспользовались следующими формулами:
\(A\rightarrow B \,\,=\,\, \neg A \bigvee B ,\)
\(\neg \left( A \bigvee B \right) \,\,=\,\, \neg A \bigwedge \neg B.\)

Ответ: 4

Задание 2 #9815


Каково наибольшее целое \(X,\) при котором истинно высказывание:
\(\left(50<X \cdot X \right)\rightarrow \left(50> \left( X+1\right) \cdot \left( X+1\right) \right)?\)


По правилу преобразования импликации имеем:

\(\left(50<X \cdot X \right)\rightarrow \left(50> \left( X+1\right) \cdot \left( X+1\right) \right) \,\,=\,\, \neg \left(50<X \cdot X \right) \bigvee \left(50> \left( X+1\right) \cdot \left( X+1\right) \right). \)

Построим отрицание для первой скобки:

\(\neg \left(50<X \cdot X \right) \bigvee \left(50> \left( X+1\right) \cdot \left( X+1\right) \right) \,\,=\,\, \left(50 \geq X \cdot X \right) \bigvee \left(50> \left( X+1\right) \cdot \left( X+1\right) \right) \)

Решим отдельно каждое неравенство:

1. \(50 \geq X \cdot X,\)
\( - 5\sqrt{2} \leq X \leq 5\sqrt{2}.\)

2. \(50> \left( X+1\right) \cdot \left( X+1\right),\)
\( - 5\sqrt{2} < X+1 < 5\sqrt{2},\)
\(-1- 5\sqrt{2} < X < -1+5\sqrt{2}.\)

А затем найдем объединение их решений, так как дизъюнкция истинна, когда истинно хотя бы одно из утверждений:
Получаем, что \(X \in (-1-5\sqrt{2} ; 5\sqrt{2}].\)

Чтобы найти наибольшее целое \(X,\) при котором истинно исходное высказывание, оценим значение правой границы:
\({X_r}^2 = 50,\)
\(49<50<64,\)
\(7<X_r<8.\)
Значит, наибольший возможный \(X=7.\)

Замечание.
При решении мы воспользовались формулой:
\(A\rightarrow B \,\,=\,\, \neg A \bigvee B.\)

Ответ: 7

Задание 3 #9816


Сколько различных решений имеет уравнение:
\(\left( \left( K \bigvee L \right)\bigwedge \left(M \bigvee N \right) \right) = 1,\)
где \(K, L, M\) и \(N\) — логические переменные?


Конъюнкция истинна, когда истинны все составляющие ее утверждения. То есть одновременно должны выполняться условия \(K\bigvee V =1\) и \(M \bigvee N = 1.\)
Дизъюнкция верна, когда истинно хотя бы одно из составляющих ее утверждений. Значит, \(K\bigvee V = 1\) в трех случаях: если \(K = 1, V = 0; K = 0, V=1; K = 1, V = 1.\) Аналогично можно получить, что \(M \bigvee N =1\) тоже в трех случаях.
Так как на каждый вариант для первого утверждения приходится по три варианта для второго утверждения, общее количество вариантов равно \(3\cdot3=9.\)

Ответ: 9

Задание 4 #9818


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


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

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

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

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

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

Ответ: 17

Задание 5 #9819


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


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


Чтобы \(y=69-2x\) целиком лежала в \((A \leq x) \bigvee (A \leq y),\) должно выполняться условие:
\(A=69-2A,\)
\(A=23.\)
Наибольшее целое \(A,\) при \(y=69-2x\) целиком лежит в \(U.\)
\(A=22.\)

Ответ: 22

Задание 6 #9820


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


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


Чтобы \(y=99-2x\) целиком лежала в \((A \leq x)\bigvee (A \leq y),\) должно выполняться условие:
\(A=99-2A,\)
\(A=33.\)
Наибольшее целое \(A\) при \(y=99-2x\) целиком лежит в \(U\) \(A=32.\)

Ответ: 32

Задание 7 #9821


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


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


Если прямая \(y=A-2x\) имеет единственную точку с \(U,\) то:
\(20=A-2\cdot30,\)
\(A=80.\)
Наименьшее целое \(A,\) при котором \(y=A-2x\) не имела общих точек с \(U\) \(A=81.\)

Ответ: 81