Математика ЕГЭ
Русский язык ЕГЭ
Математика 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