Основные понятия математической логики
 Скачать 2.32 Mb.
|
Ещё пример задания:Р-21. Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наибольшее натуральное число a, такое что выражение (x & a 0 ) ((x& 20 = 0) (x&5 0)) тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной x)? Решение: введём обозначения: Z20 = (x & 20 = 0), Z5 = (x& 5 = 0), A = (x&a= 0) перепишем исходное выражение и преобразуем его, используя свойство импликации  и закон де Моргана  : преобразуем это выражение в импликацию, избавившись от инверсии:  заменим  на  :20 = 10100 5 = 00101 20 or 5 = 10101 = 21 таким образом, нужно обеспечить истинность выражения  при всех xэто возможно только тогда, когда множество единичных битов числа a входит во множество единичных битов числа 21 поэтому максимальное amax = 101012 = 21 Ответ: 21. Решение (2 способ, Н.Г. Неуймина, г. Екатеринбург): введём обозначения: P = (X & 20 = 0), Q = (X & 5 = 0), A = (X & A = 0) перепишем исходное выражение и преобразуем его, используя свойство импликации : чтобы формула была тождественно истинной для любых Х необходимо, чтобы при  было А=1имеем тогда и только тогда, когда  ; посмотрим, какими свойствами должен обладать X для того, чтобы было если  , то есть, (X & 5 = 0), имеемномер бита 4 3 2 1 0 X = ab0d0 5 = 00101 X & 5 = 00000 это значит, что биты {2, 0} – нулевые если одновременно  , то есть, (X & 20 = 0), имеемномер бита 4 3 2 1 0 X = 0b0d0 20 = 10100 X & 20 = 00000 это значит, что бит 4 в X – обязательно нулевой так как биты {3,1} числа X могут быть ненулевыми, в этих разрядах числа A должны стоять нули, а вот биты {4,2,0} в X – нулевые, поэтому в числе A эти биты могут быть равны 1 поскольку нужно найти наибольшее подходящее A, получаем ответ 24 + 22 + 20 = 21 Ответ: 21. |