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

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

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


  • Решение (программа на Python, Г.М. Федченко): программа на Python, полный перебор: def f( x, a )

  • OK = True for x in range(1,1000): if not f(x, a): OK = False break if OK: print( a )

  • ((x a == 0) and (x 21 != 0)) ) or \ (x 21 == 0) and (x 12 == 0) if not OK: break if OK: print( a )

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


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

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

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

    ( (x & 28  0) (x & 45 0)) ((x & 48 =0) (x & a 0))

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


    Решение:

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

    Z28 = (x & 28 = 0), Z45 = (x& 45 = 0), Z48 = (x& 48 = 0), A = (x&a= 0)

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



    1. перейдем к импликации, используя закон де Моргана:



    1. преобразуем выражение в правой части по формуле , выполнив поразрядную дизъюнкцию (операцию ИЛИ):

    28 = 011100

    45 = 101101

    1. or 45 = 111101 = 61

    получаем

    1. для того, чтобы выражение было истинно для всех x, нужно, чтобы двоичная запись числа 48 or a содержала все единичные биты числа 61. Таким образом, с помощью числа a нужно добавить те единичные биты числа 61, которых «не хватает» в числе 48:

    48 = 110000

    a = **11*1

    61 = 111101

    биты, обозначенные звездочками, могут быть любыми.

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

    2. получается A = 23 + 22 + 20 = 13

    3. Ответ: 13.

    Ещё пример задания (М.В. Кузнецова):

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


    Решение:

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

    Z12 = (X & 12 = 0), Z21 = (X & 21 = 0), A = (X &a= 0)

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



    Выражение в первой скобке упрощаем, используя следствие из распределительного закона



    Полученное выражение также можно упростить, используя ещё одно следствие из распределительного закона



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



    1. поскольку множество единичных битов числа 21 = 10101­2 не входит во множество единичных битов числа 12 = 1100­2, импликация ложна для некоторых x; поэтому нужно обеспечить истинность выражения

    2. выражение истинно при условии, что множество единичных битов числа a входит во множество единичных битов числа 12, поэтому в двоичной записи числа a ненулевыми могут быть только биты в разрядах 2 и 3

    3. поэтому amax = 23 + 22 = 12.

    4. Ответ: 12.


    Решение (программа на Python, Г.М. Федченко):

    1. программа на Python, полный перебор:

    def f( x, a ):

    return ( ((x & a != 0) and (x & 12 == 0)) <= \

    ((x & a == 0) and (x & 21 != 0)) ) or \

    (x & 21 == 0) and (x & 12 == 0)

    for a in range(1, 1000):

    OK = True

    for x in range(1,1000):

    if not f(x, a):

    OK = False

    break

    if OK:

    print( a )

    1. вариант без функции:

    for a in range(1, 1000):

    OK = 1

    for x in range(1,1000):

    OK *= ( ((x & a != 0) and (x & 12 == 0)) <= \

    ((x & a == 0) and (x & 21 != 0)) ) or \

    (x & 21 == 0) and (x & 12 == 0)

    if not OK: break

    if OK:

    print( a )

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


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