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

  • Решение (1 способ): введём обозначения: Z 49 =

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


  • Решение (3 способ, А.В. Лаздин, НИУ ИТМО)

  • Решение (4 способ, М.В. Кузнецова ): Введём обозначения: P =

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


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

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


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

    (x & 49 0) ((x& 33 = 0) (x&a 0))

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

    Решение (1 способ):

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

    Z49 = (x & 49 = 0), Z33 = (x& 33 = 0), A = (x&a= 0)

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



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



    1. чтобы это выражение было истинным, нужно, чтобы множество единичных битов числа 33or a перекрывало множество единичных битов числа 49; с помощью a можно добавить недостающие биты:

    33 = 100001

    a = *1****

    49 = 110001

    1. чтобы выбрать минимальное a, биты, обозначенные звездочками, примем равными нулю; получаем число 100002 = 16 = 24.

    2. Ответ: 16.

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

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

    P = (X & 49 0), Q = (X & 33 = 0), A = (X & A 0)

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

    P (Q A) = + (Q A) =

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

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

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

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

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

    X = 0bcde0

    33 = 100001

    X & 33 = 000000

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

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

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

    X = 0bcde0

    49 = 110001

    X & 49 = 0b0000

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

    1. из 6 и 7 делаем вывод, что для выполнения условия A = (X & A 0) = 1 необходимо, чтобы, по крайней мере, бит 4 числа A был ненулевым (так как биты {3,2,1} в X могут быть нулевые!)

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

    3. Ответ: 16.

    Решение (3 способ, А.В. Лаздин, НИУ ИТМО):

    1. если X & 49 = 0, то исходное выражение истинно, независимо от значения числа А; значит, значение числа А влияет на решение задачи только при выполнении условия:

    1. X &49  0.

    1. тогда исходное выражение может быть представлено в виде:

    1  ((X & 33 = 0)  (X & A  0)) (2)

    1. Для того чтобы это выражение было истинным, необходимо, чтобы выражение

    (X & 33 = 0)  (X & A  0)

    было истинным, при этом, если X & 33  0, то это выражение истинно независимо от значения числа А (импликация из 0 в 1).

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

    1. X & 49  0

    2. X & 33 = 0

    1. исходное выражение принимает следующий вид:

    1  (1  (X & A  0)) (3)

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

    3. X & A 0.

    4910 = 1100012

    3310 = 1000012

    X 010000

    1. условия 1 и 2 выполняются, если пятый бит числа Х равен 1.

    2. значит условие № 3 выполняется, если пятый бит числа А равен 1

    3. число А минимально, если младшие разряды этого числа равны 0

    4. Ответ: 16.

    Решение (4 способ, М.В. Кузнецова ):

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

    P = (X & 49  0), Q = (X & 33  0), A = (X & A  0)

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



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

    2. Значит, A =1 тогда и только тогда, когда .

    3. Запишем двоичное представление чисел 49 и 33, на их основе составим маски возможных значений числа х, таких, что . В маске «1» - соответствует возможному положению 1, «0» - обязательному положению 0 в двоичной записи числа х.




    Номер бита

    5

    4

    3

    2

    1

    0

    Вес разряда

    32

    16

    8

    4

    2

    1

    Двоичная запись 49

    1

    1

    0

    0

    0

    1

    Двоичная запись 33

    1

    0

    0

    0

    0

    1

    Маска мин. х, для P=1 (x & 49 ≠ 0)

    1

    1

    0

    0

    0

    1

    Маска мин. х, для =1 (x & 33 = 0)

    0

    1

    1

    1

    1

    0

    A = (x & 49 ≠ 0) and (x & 33 = 0)

    0

    1

    0

    0

    0

    0

    1. Ответ: 16.
    1   ...   5   6   7   8   9   10   11   12   ...   50


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