Задача 18 к семинару
1(18-56) На числовой прямой даны два отрезка: P = [5, 15] и Q = [10,20]. Выберите такой отрезок A, что формула
(x Î P) /\ (x Ï Q) /\ (x Î A)
тождественно ложна, то есть принимает значение 0 при любом значении переменной х.
1) [0, 7] 2) [8, 15] 3) [15, 20] 4)[7, 20]
2(18-58) На числовой прямой даны два отрезка: P = [10, 20] и Q = [5,15]. Выберите такой отрезок A, что формула
((x Î Q) → (x Î P)) /\ (x Î A)
тождественно ложна, то есть принимает значение 0 при любом значении переменной х.
1) [0, 6] 2) [5, 8] 3) [7, 15] 4)[12, 20]
3(18-50). На числовой прямой даны три отрезка: P = [10, 40], Q = [5, 15] и R=[35,50]. Выберите такой отрезок A, что формула
((x Î P) → (x Î Q)) \/ ((x Î A) → (x Î R))
тождественно истинна, то есть принимает значение 1 при любом значении переменной х.
1) [10, 20] 2) [15, 25] 3) [20, 30] 4)[120, 130]
4(18-54). На числовой прямой даны три отрезка: P = [10,50], Q = [15, 20] и R=[30,80]. Выберите такой отрезок A, что формула
((x Î P) → (x Î Q)) \/ ((x Ï A) → (x Ï R))
тождественно истинна, то есть принимает значение 1 при любом значении переменной х.
1) [10,25] 2) [25, 50] 3) [40,60] 4)[50, 80]
5(18-59) На числовой прямой даны три отрезка: P = [15, 30], Q = [5,10] и R=[20,25]. Выберите такой отрезок A, что формула
((x Î P) → (x Î Q)) /\ ((x Ï A) → (x Î R))
тождественно ложна, то есть принимает значение 0 при любом значении переменной х.
1) [0, 20] 2) [0, 10] 3) [10, 15] 4)[25, 30]
6(18-85) На числовой прямой даны два отрезка: P = [20,70] и Q = [5,32]. Выберите из предложенных вариантов такой отрезок A, что логическое выражение
((x Î P) Ù (x Î A)) → ((x Î Q) Ù (x Î A))
тождественно истинна, то есть принимает значение 1 при любом значении переменной х.
1) [15, 35] 2) [20, 40] 3) [40, 65] 4) [75, 88]
Пример задания:
Р-24. Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число a, такое что выражение
((x &28¹ 0) Ú (x & 45 ¹ 0)) ® ((x & 48 = 0) ® (x & a ¹ 0))
тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной x)?
Решение:
1) Введём обозначения:
Z 28 = (x & 28 = 0), Z 45 = (x & 45 = 0), Z 48 = (x & 48 = 0), A = (x & a = 0)
2) перепишем исходное выражение и преобразуем его, используя свойство импликации:
3) перейдем к импликации, используя закон де Моргана:
4) преобразуем выражение в правой части по формуле 
, выполнив поразрядную дизъюнкцию (операцию ИЛИ):
28 = 011100
45 = 101101
28 or 45 = 111101 = 61
получаем 
5) для того, чтобы выражение было истинно для всех x, нужно, чтобы двоичная запись числа 48 or a содержала все единичные биты числа 61. Таким образом, с помощью числа a нужно добавить те единичные биты числа 61, которых «не хватает» в числе 48:
48 = 110000
a = **11*1
61 = 111101
биты, обозначенные звездочками, могут быть любыми.
6) поскольку нас интересует минимальное значение a, все биты, обозначенные звездочкой, можно принять равными нулю.
7) получается A = 23 + 22 + 20 = 13
8) Ответ: 13.
Ещё пример задания (М.В. Кузнецова):
Р-23. Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наибольшее натуральное число a, такое что выражение
(((x & a ¹ 0) Ù (x & 12 = 0)) ® ((x & a = 0) Ù (x & 21 ¹ 0))) Ú ((x & 21 = 0) Ù (x & 12 = 0))
тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)?
Решение:
1) Введём обозначения:
Z 12 = (X & 12 = 0), Z 21 = (X & 21 = 0), A = (X & a = 0)
2) перепишем исходное выражение и преобразуем его, используя свойство импликации:
Выражение в первой скобке упрощаем, используя следствие из распределительного закона 
Полученное выражение также можно упростить, используя ещё одно следствие из распределительного закона 
3) перейдем к импликации, избавившись от инверсии:
4) поскольку множество единичных битов числа 21 = 101012 не входит во множество единичных битов числа 12 = 11002, импликация 
ложна для некоторых x; поэтому нужно обеспечить истинность выражения 
5) выражение истинно при условии, что множество единичных битов числа a входит во множество единичных битов числа 12, поэтому в двоичной записи числа a ненулевыми могут быть только биты в разрядах 2 и 3
6) поэтому amax = 23 + 22 = 12.
7) Ответ: 12.