Главная страница
Навигация по странице:

  • Решение: введём обозначения: Z 20 =


  • Решение (2 способ, Н.Г. Неуймина, г. Екатеринбург): введём обозначения: P =

  • Основные понятия математической логики


    Скачать 2.32 Mb.
    НазваниеОсновные понятия математической логики
    Дата16.02.2022
    Размер2.32 Mb.
    Формат файлаdoc
    Имя файлаege15.doc
    ТипЗакон
    #363571
    страница10 из 50
    1   ...   6   7   8   9   10   11   12   13   ...   50

    Ещё пример задания:


    Р-21. Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наибольшее натуральное число a, такое что выражение

    (x & a 0 ) ((x& 20 = 0) (x&5 0))

    тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной x)?

    Решение:

    1. введём обозначения:

    Z20 = (x & 20 = 0), Z5 = (x& 5 = 0), A = (x&a= 0)

    1. перепишем исходное выражение и преобразуем его, используя свойство импликации и закон де Моргана :



    1. преобразуем это выражение в импликацию, избавившись от инверсии:



    1. заменим на :

    20 = 10100

    5 = 00101

    20 or 5 = 10101 = 21

    1. таким образом, нужно обеспечить истинность выражения при всех x

    2. это возможно только тогда, когда множество единичных битов числа a входит во множество единичных битов числа 21

    3. поэтому максимальное amax = 101012 = 21

    4. Ответ: 21.

    Решение (2 способ, Н.Г. Неуймина, г. Екатеринбург):

    1. введём обозначения:

    P = (X & 20 = 0), Q = (X & 5 = 0), A = (X & A = 0)

    1. перепишем исходное выражение и преобразуем его, используя свойство импликации :



    1. чтобы формула была тождественно истинной для любых Х необходимо, чтобы при было А=1

    2. имеем тогда и только тогда, когда ;

    3. посмотрим, какими свойствами должен обладать X для того, чтобы было

    4. если , то есть, (X & 5 = 0), имеем

    номер бита 4 3 2 1 0

    X = ab0d0

    5 = 00101

    X & 5 = 00000

    это значит, что биты {2, 0} – нулевые

    1. если одновременно , то есть, (X & 20 = 0), имеем

    номер бита 4 3 2 1 0

    X = 0b0d0

    20 = 10100

    X & 20 = 00000

    это значит, что бит 4 в X – обязательно нулевой

    1. так как биты {3,1} числа X могут быть ненулевыми, в этих разрядах числа A должны стоять нули, а вот биты {4,2,0} в X – нулевые, поэтому в числе A эти биты могут быть равны 1

    2. поскольку нужно найти наибольшее подходящее A, получаем ответ 24 + 22 + 20 = 21

    3. Ответ: 21.
    1   ...   6   7   8   9   10   11   12   13   ...   50


    написать администратору сайта