Для решения этого задания необходимы знания алгебры логики. Вам сюда.
Первый тип задания - числовые отрезки.
Пример задания.
На числовой прямой даны два отрезка: P=[8,50] и Q=[27,76]. Определите наименьшую возможную длину отрезка А, при котором выражение
¬(x ϵ A) → ¬(¬(x ϵ P) → (x ϵ Q))
тождественно истинно, то есть принимает значение 1 при любом значении переменной х.
Первое, что необходимо сделать - преобразовать выражение - избавиться от импликации, а также заменить выражение (x ϵ A) на А, (x ϵ P) на Р, (x ϵ Q) на Q:
¬A→ ¬(¬ P → Q)=A v¬(¬ P → Q)=A v¬(P v Q)=A v ¬P & ¬ Q
Итак, мы получили более понятное выражение. Так как выражение должно быть истинным на протяжении всей числовой прямой, необходимо посмотреть какие участки не закрыты P и Q, и именно они должны быть закрыты отрезком А.
На рисунке 1 отображены отрезки Р и Q.
На рисунке 2 отображен результат выражения ¬P & ¬ Q. Обратите внимание, что точки "выколоты", так как в отрезки они входят, а под отрицанием получаем "все кроме" данного отрезка. Кроме того, так как в выражении конъюнкция нужная нам область - пересечение двух областей - показано штриховкой.
Анализируя рисунок заметно, что остался не закрыт отрезок [8,76], таким образом получаем, что А=[8,76] и наименьшая возможная длина отрезка А=76-8=68
Ответ 68.
Второй тип задания - функция делимость.
Пример задания.
Обозначим через ДЕЛ(n, m) утверждение "натуральное число n делится без остатка на натуральное число m". Для какого наибольшего натурального числа А формула
¬ДЕЛ(x, A) → (ДЕЛ(x, 4) → ¬ДЕЛ(x, 10))
истинна при любом натуральном значении x?
Также, как и в предыдущем задании сначала преобразуем выражение:
¬ДЕЛ(x, A) → (ДЕЛ(x, 4) → ¬ДЕЛ(x, 10))= ДЕЛ(x, A) v (ДЕЛ(x, 4) → ¬ДЕЛ(x, 10))=
ДЕЛ(x, A) v (¬ДЕЛ(x, 4) v ¬ДЕЛ(x, 10))=ДЕЛ(x, A) v ¬(ДЕЛ(x, 4) & ДЕЛ(x, 10))
Проанализируем выражение под отрицанием:
(ДЕЛ(x, 4) & ДЕЛ(x, 10))
То есть число х должно одновременно делиться и на 4 и на 10, поэтому нам необходимо найти НОК 4 и 10. НОК (4,10)=20.
Получаем: (ДЕЛ(x, 4) & ДЕЛ(x, 10)) = (ДЕЛ(x, 20)
Полное выражение теперь примет вид:
ДЕЛ(x, A) v ¬ (ДЕЛ(x, 20)
Выражением ¬ (ДЕЛ(x, 20) выбраны все такие х, которые не делятся на 20, а чтобы выражение стало истинным при любом х, то нам необходимо захватить оставшиеся значения - которые делятся на 20, получаем, что А=20
Ответ 20.
Примечание. По сути задание сводится к тому, чтобы найти НОК двух чисел.
Третий тип задания - поразрядная конъюнкция.
Теория.
При поразрядной конъюнкции важно помнить, что выражение будет истинным, только в том случае, когда при умножении единицы получается там же, где и они стоят в первом числе:
*11001
11010
11000
Ложь, так как в последнем разряде получился ноль.
А вот это выражение будет истинным:
*10001
11 1 11
10001
Пример задания
Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 12&6 = 11002&01102 = 01002 = 4
Для какого наименьшего неотрицательного целого числа A формула
(X & A = 0) & ¬(X & 35 ≠ 0 → X & 52 ≠ 0)
тождественно ложна (то есть принимает значение 0 при любом неотрицательном значении переменной X)?
И снова преобразование:
(X & A = 0) & ¬(X & 35 ≠ 0 → X & 52 ≠ 0) =(X & A = 0) & ¬(X & 35 = 0 v X & 52 ≠ 0)=
(X & A = 0) & (X & 35 ≠ 0 & X & 52 = 0)
Чтобы найти А, сначала найдем все х, которые охвачены известными числами. Для этого переведем все числа в двоичную систему:
35= 1000112
52=1101002
Построим маски:
для того, чтобы X & 35 ≠ 0 было истинным, необходимо, чтобы там, где стоят в числе 35 единицы и в числе, а следовательно и нашей маске стояли единицы:
100011
1ххх11
для того, чтобы X & 52 = 0 было истинным, необходимо, чтобы там, где стоят в числе 52 единицы и числе х, а следовательно и нашей маске стояли нули:
1 1 0 1 0 0
0 0 х 0 x x
Объединим маски:
1 х х х 1 1
0 0 х 0 x x
А теперь небольшая хитрость при наложении масок - там где мы видим в масках 1->x или наоборот, x->1 должны стоять единицы.
1 х х х 1 1
0 0 х 0 x x
Так как нам необходимо найти наименьшее неотрицательное целое число A, то в остальных разрядах поставим нули:
0000112=310.
Ответ 3.
Внимание!
если X & A = 0, там, где мы видим 1->x или наоборот, x->1 должны стоять единицы
если X & A ≠ 0, там, где мы видим 0->x или наоборот, x->0 должны стоять нули
Пример:
для X & A = 0
1 х х х 1 1
0 0 х 0 x x
0 0 0 0 1 1
112=3
для X & A ≠ 0
1 х х х 1 1
0 0 х 0 x x
0 1 0 1 0 0
101002=20