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

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

  • OK = False break if OK: print( a ) break

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


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

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

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

    ( x & 125  1) ((x & 34 2) (x & a =0))

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


    Решение:

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



    где Z124 = (x & 124 = 0), Z1 = (x & 1 = 0), Z2 = (x & 2 = 0), A = (x & a = 0)

    1. раскроем импликацию по формуле :



    1. применим закон де Моргана :



    1. перейдём к импликации, в которой нет выражений с инверсиями (операциями «НЕ»):







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



    так что

    1. используя свойство импликации , получаем



    1. представим числа в двоичной системе счисления:

    124 = 11111002, 1 =12, 2 =102

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



    в том смысле, что найдутся такие значения x, при которыхэти выражения ложны.

    1. тогда для истинности заданного выражения остаётся обеспечить истинность при всех x, а это условие будет выполняться тогда и только тогда, когда все единичные биты двоичной записи числа a входят во множество единичных битов числа 124 = 11111002; таким образом, минимальное подходящее положительное значение a – 22 = 4, а максимальное – 124.

    2. Ответ: 4.

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

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

    def f( x, a ):

    return (x & 125 != 1) or ((x & 34 == 2) <= (x & a == 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 )

    break

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

    for a in range(1, 1000):

    OK = 1

    for x in range(1,1000):

    OK *= (x & 125 != 1) or ((x & 34 == 2) <= (x & a == 0))

    if not OK: break

    if OK:

    print( a )

    break

    1. Ответ: 4.
    1   2   3   4   5   6   7   8   9   10   ...   50


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