Основные понятия математической логики
 Скачать 2.32 Mb.
|
Ещё пример задания:Р-22. Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число a, такое что выражение (x & 49 0) ((x& 33 = 0) (x&a 0)) тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной x)? Решение (1 способ): введём обозначения: Z49 = (x & 49 = 0), Z33 = (x& 33 = 0), A = (x&a= 0) перепишем исходное выражение и преобразуем его, используя свойство импликации  и закон де Моргана  : переходим к импликации, избавляясь от инверсий:  чтобы это выражение было истинным, нужно, чтобы множество единичных битов числа 33or a перекрывало множество единичных битов числа 49; с помощью a можно добавить недостающие биты: 33 = 100001 a = *1**** 49 = 110001 чтобы выбрать минимальное a, биты, обозначенные звездочками, примем равными нулю; получаем число 100002 = 16 = 24. Ответ: 16. Решение (2 способ, Н.Г. Неуймина, г. Екатеринбург): введём обозначения: P = (X & 49 0), Q = (X & 33 = 0), A = (X & A 0) перепишем исходное выражение и преобразуем его, используя свойство импликации :P (Q A) =  + (Q A) =  чтобы формула была тождественно истинной для любых Х необходимо, чтобы при  было А=1имеем тогда и только тогда, когда  ; посмотрим, какими свойствами должен обладать X для того, чтобы было если  , то есть, (X & 33 = 0), имеемномер бита 5 4 3 2 1 0 X = 0bcde0 33 = 100001 X & 33 = 000000 это значит, что биты {5, 0} – нулевые если одновременно  , то есть, (X & 49 0), имеемномер бита 5 4 3 2 1 0 X = 0bcde0 49 = 110001 X & 49 = 0b0000 это значит, что бит 4 в X – обязательно ненулевой из 6 и 7 делаем вывод, что для выполнения условия A = (X & A 0) = 1 необходимо, чтобы, по крайней мере, бит 4 числа A был ненулевым (так как биты {3,2,1} в X могут быть нулевые!) поскольку нужно найти наименьшее подходящее A, получаем ответ 24 = 16 Ответ: 16. Решение (3 способ, А.В. Лаздин, НИУ ИТМО): если X & 49 = 0, то исходное выражение истинно, независимо от значения числа А; значит, значение числа А влияет на решение задачи только при выполнении условия: X &49 0. тогда исходное выражение может быть представлено в виде: 1 ((X & 33 = 0) (X & A 0)) (2) Для того чтобы это выражение было истинным, необходимо, чтобы выражение (X & 33 = 0) (X & A 0) было истинным, при этом, если X & 33 0, то это выражение истинно независимо от значения числа А (импликация из 0 в 1). следовательно, значение числа А влияет на принимаемое исходным выражением значение только при одновременном соблюдении двух условий: 1. X & 49 0 2. X & 33 = 0 исходное выражение принимает следующий вид: 1 (1 (X & A 0)) (3) для того чтобы это выражение приняло значение 1, необходимо, чтобы выполнилось третье условие: 3. X & A 0. 4910 = 1100012 3310 = 1000012 X 010000 условия 1 и 2 выполняются, если пятый бит числа Х равен 1. значит условие № 3 выполняется, если пятый бит числа А равен 1 число А минимально, если младшие разряды этого числа равны 0 Ответ: 16. Решение (4 способ, М.В. Кузнецова ): Введём обозначения: P = (X & 49 0), Q = (X & 33 0), A = (X & A 0) Перепишем исходное выражение и преобразуем его, используя свойство импликации : Чтобы формула была тождественно истинной для любых Х необходимо, чтобы при  было А=1, т.е  . Значит, A =1 тогда и только тогда, когда  .Запишем двоичное представление чисел 49 и 33, на их основе составим маски возможных значений числа х, таких, что . В маске «1» - соответствует возможному положению 1, «0» - обязательному положению 0 в двоичной записи числа х.
Ответ: 16. |
=1