Ррр. Основные понятия математической логики
Скачать 2.23 Mb.
|
Ещё пример задания:Р-18. Пусть P – множество всех 8-битовых цепочек, начинающихся с 1, Q – множество всех 8-битовых цепочек, оканчивающихся на 000, а A – некоторое множество произвольных 8-битовых цепочек. Сколько элементов содержит минимальное множество A, при котором для любой 8-битовой цепочки x истинно выражение ¬(x A) (¬(x P) (x Q)) Решение: введём обозначения A: x А, P: x P, Q: x Q перейдем к более простым обозначениям раскрываем импликацию по формуле : для выполнения условия при любом x необходимо, чтобы для всех x, для которых , то есть множество – это все 8-битовые цепочки, которые начинаются с 1 и оканчиваются НЕ на 000 поскольку всего битов 8, структура всех таких цепочек имеет вид 1****???, где * обозначает любой из двух символов (0 или 1) , а ??? – трёхбитное окончание, не совпадающее с 000 всего может быть 23 = 8 комбинаций из трёх битов, одно из них, 000, запрещено для окончания, поэтому остаётся еще 7 разрешённых вариантов общее количество подходящих цепочек находим по правилам комбинаторики, перемножив количество вариантов для каждой части цепочки (1 для первого бита, по 2 для следующих четырёх и 7 для трёхбитного окончания) 1 · 2 · 2 · 2 · 2 · 7 = 112 Ответ: 112. Решение (А.Н. Носкин): упростим исходное выражение и получим: А ¬Р Q = 1 всё множество всех 8-битовых цепочек расположено на отрезке от 0 до 255 минимальное число множества Р начинающегося с 100000002 = 128, следовательно, все множество Р занимает часть отрезка от 128 до 255; длина этой части отрезка равна 255 – 128 + 1 = 128. Q – множество всех 8-битовых цепочек, оканчивающихся на 000, которые имеют вид ****000, где * обозначает любой из двух символов (0 или 1); количество таких чисел в множестве равно 24 = 16, где 4 – число звездочек в числе Q из выражения видно, что множество ¬Р закрывает интервал от 0 до 127, следовательно, множество A должно перекрыть все числа во множестве Р (таких чисел 128), которые не перекрывают числа из множества Q минимальное множество A содержит 128 – 16 = 112 элементов. Ответ: 112. Решение (программа на Python, А.Н. Носкин): упростим исходное выражение и получим: А ¬Р Q = 1 всё множество всех 8-битовых цепочек расположено на отрезке от 0 до 255 минимальное число множества Р начинающегося с 100000002 = 128. Создадим это множество Р: P = {i for i in range(128,256)} Q – множество всех 8-битовых цепочек, оканчивающихся на 000, которые имеют вид ****000, где * обозначает любой из двух символов (0 или 1); таким образом разность между соседними числами множества равно 8. Создадим это множество Q: Q = {i for i in range(0,256,8)} из выражения видно, что множество ¬Р закрывает интервал от 0 до 127, следовательно, множество A должно перекрыть все числа во множестве Р (таких чисел 128), которые не перекрывают числа из множества Q это достигается разностью множеств: P-Q Тогда А это количество элементов разности множеств. Приведем программу: P = {i for i in range(128,256)} #множество Р Q = {i for i in range(0,256,8)} #множество Q print(len(P-Q)) Ответ: 112. |