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

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

  • 1****

  • Решение (А.Н. Носкин) : упростим исходное выражение и получим: А  ¬Р  Q = 1

  • P = {i for i in range(128,256)} множество Р Q = {i for i in range(0,256,8)} множество Q print(len(P-Q))

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


    Скачать 2.35 Mb.
    НазваниеОсновные понятия математической логики
    Дата05.12.2022
    Размер2.35 Mb.
    Формат файлаdoc
    Имя файлаege15 (2).doc
    ТипЗакон
    #828321
    страница12 из 50
    1   ...   8   9   10   11   12   13   14   15   ...   50

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


    Р-18. Пусть P – множество всех 8-битовых цепочек, начинающихся с 1, Q – множество всех 8-битовых цепочек, оканчивающихся на 000, а A – некоторое множество произвольных 8-битовых цепочек. Сколько элементов содержит минимальное множество A, при котором для любой 8-битовой цепочки x истинно выражение

    ¬(x A)  (¬(x P)  (x Q))

    Решение:

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

    A: x А, P: x P, Q: x Q

    1. перейдем к более простым обозначениям



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



    1. для выполнения условия при любом x необходимо, чтобы для всех x, для которых , то есть

    2. множество – это все 8-битовые цепочки, которые начинаются с 1 и оканчиваются НЕ на 000

    3. поскольку всего битов 8, структура всех таких цепочек имеет вид 1****???, где * обозначает любой из двух символов (0 или 1) , а ??? – трёхбитное окончание, не совпадающее с 000

    4. всего может быть 23 = 8 комбинаций из трёх битов, одно из них, 000, запрещено для окончания, поэтому остаётся еще 7 разрешённых вариантов

    5. общее количество подходящих цепочек находим по правилам комбинаторики, перемножив количество вариантов для каждой части цепочки (1 для первого бита, по 2 для следующих четырёх и 7 для трёхбитного окончания) 1 · 2 · 2 · 2 · 2 · 7 = 112

    6. Ответ: 112.


    Решение (А.Н. Носкин):

    1. упростим исходное выражение и получим: А ¬Р Q = 1

    2. всё множество всех 8-битовых цепочек расположено на отрезке от 0 до 255

    3. минимальное число множества Р начинающегося с 100000002 = 128, следовательно, все множество Р занимает часть отрезка от 128 до 255; длина этой части отрезка равна 255 – 128 + 1 = 128.

    4. Q – множество всех 8-битовых цепочек, оканчивающихся на 000, которые имеют вид ****000, где * обозначает любой из двух символов (0 или 1); количество таких чисел в множестве равно 24 = 16, где 4 – число звездочек в числе Q

    5. из выражения видно, что множество ¬Р закрывает интервал от 0 до 127, следовательно, множество A должно перекрыть все числа во множестве Р (таких чисел 128), которые не перекрывают числа из множества Q

    6. минимальное множество A содержит 128 – 16 = 112 элементов.

    7. Ответ: 112.

    Решение (программа на Python, А.Н. Носкин):

    1. упростим исходное выражение и получим: А ¬Р Q = 1

    2. всё множество всех 8-битовых цепочек расположено на отрезке от 0 до 255

    3. минимальное число множества Р начинающегося с 100000002 = 128.

    Создадим это множество Р:

    P = {i for i in range(128,256)}

    1. Q – множество всех 8-битовых цепочек, оканчивающихся на 000, которые имеют вид ****000, где * обозначает любой из двух символов (0 или 1); таким образом разность между соседними числами множества равно 8.

    Создадим это множество Q:

    Q = {i for i in range(0,256,8)}

    1. из выражения видно, что множество ¬Р закрывает интервал от 0 до 127, следовательно, множество A должно перекрыть все числа во множестве Р (таких чисел 128), которые не перекрывают числа из множества Q это достигается разностью множеств: P-Q

    Тогда А это количество элементов разности множеств.

    1. Приведем программу:

    P = {i for i in range(128,256)} #множество Р

    Q = {i for i in range(0,256,8)} #множество Q

    print(len(P-Q))

    1. Ответ: 112.
    1   ...   8   9   10   11   12   13   14   15   ...   50


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