Ррр. Основные понятия математической логики
Скачать 2.23 Mb.
|
Ещё пример задания:Р-24. Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число a, такое что выражение( (x & 28 0) (x & 45 0)) ((x & 48 =0) (x & a 0))тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной x)?Решение: Введём обозначения: Z28 = (x & 28 = 0), Z45 = (x& 45 = 0), Z48 = (x& 48 = 0), A = (x&a= 0) перепишем исходное выражение и преобразуем его, используя свойство импликации: перейдем к импликации, используя закон де Моргана: преобразуем выражение в правой части по формуле , выполнив поразрядную дизъюнкцию (операцию ИЛИ): 28 = 011100 45 = 101101 or 45 = 111101 = 61 получаем для того, чтобы выражение было истинно для всех x, нужно, чтобы двоичная запись числа 48 or a содержала все единичные биты числа 61. Таким образом, с помощью числа a нужно добавить те единичные биты числа 61, которых «не хватает» в числе 48: 48 = 110000 a = **11*1 61 = 111101 биты, обозначенные звездочками, могут быть любыми. поскольку нас интересует минимальное значение a, все биты, обозначенные звездочкой, можно принять равными нулю. получается A = 23 + 22 + 20 = 13 Ответ: 13. Ещё пример задания (М.В. Кузнецова): Р-23. Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наибольшее натуральное число a, такое что выражение |