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

• Название: Основные понятия математической логики
• Дата: 02.02.2022
• Размер: 2.32 Mb.
• Имя файла: ege15.doc
• Тип: Закон; #349239
• страница: 12 из 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. 
   перейдем к более простым обозначениям
   

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

3. 
   для выполнения условия при любом x необходимо, чтобы для всех x, для которых , то есть
   
4. 
   множество – это все 8-битовые цепочки, которые начинаются с 1 и оканчиваются НЕ на 000
   
5. 
   поскольку всего битов 8, структура всех таких цепочек имеет вид 1****???, где * обозначает любой из двух символов (0 или 1) , а ??? – трёхбитное окончание, не совпадающее с 000
   
6. 
   всего может быть 2³ = 8 комбинаций из трёх битов, одно из них, 000, запрещено для окончания, поэтому остаётся еще 7 разрешённых вариантов
   
7. 
   общее количество подходящих цепочек находим по правилам комбинаторики, перемножив количество вариантов для каждой части цепочки (1 для первого бита, по 2 для следующих четырёх и 7 для трёхбитного окончания) 1 · 2 · 2 · 2 · 2 · 7 = 112
   
8. 
   Ответ: 112.
   

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

1. 
   упростим исходное выражение и получим: А  ¬Р  Q = 1
   
2. 
   всё множество всех 8-битовых цепочек расположено на отрезке от 0 до 255
   
3. 
   минимальное число множества Р начинающегося с 10000000₂ = 128, следовательно, все множество Р занимает часть отрезка от 128 до 255; длина этой части отрезка равна 255 – 128 + 1 = 128.
   
4. 
   Q – множество всех 8-битовых цепочек, оканчивающихся на 000, которые имеют вид ****000, где * обозначает любой из двух символов (0 или 1); количество таких чисел в множестве равно 2⁴ = 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. 
   минимальное число множества Р начинающегося с 10000000₂ = 128.
   

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

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

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

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

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

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

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

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

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

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

print(len(P-Q))

7. 
   Ответ: 112.