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

• Название: Основные понятия математической логики
• Дата: 05.12.2022
• Размер: 2.35 Mb.
• Имя файла: ege15 (2).doc
• Тип: Закон; #828321
• страница: 13 из 50

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

Р-17. Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа А формула

ДЕЛ(x, А)  (¬ДЕЛ(x, 21) + ДЕЛ(x, 35))

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

Решение:

1. 
   введём обозначения A = ДЕЛ(x, А), P = ДЕЛ(x, 21) и Q = ДЕЛ(x, 35)
   
2. 
   введём множества:
   

A –множество натуральных чисел, для которых выполняется условие A

P –множество натуральных чисел, для которых выполняется условие P

Q –множество натуральных чисел, для которых выполняется условие Q

3. 
   истинным для всех X должно быть выражение
   

4. 
   упростим это выражение, раскрыв импликацию по правилу :
   

5. 
   из этой формулы видно, что может быть равно 0 (и соответственно, A может быть равно 1) только там, где ; таким образом, наибольшее возможное множество A определяется как – множество всех чисел, которые делятся на 35 плюс множество чисел, которые не делятся на 21;
   
6. 
   заметим, что в точности такое множество нельзя получить с помощью функции ДЕЛ никаким выбором A;
   
7. 
   итак, нам нужно множеством A перекрыть все числа, которые делятся на 35, это можно сделать, например, выбрав в качестве A любой делитель числа 35 = 5 · 7
   
8. 
   в то же время нам нельзя перекрывать числа, которые не делятся на 35, но делятся на 21 = 3 · 7 (в этих точках , и если будет A = 1, то )
   
9. 
   предположим, что мы выбрали некоторое значение A; тогда выражение ложно в точках A·k, где k – натуральное число;
   
10. 
    если число A·k делится на 21, то есть A·k = 21·m при некотором натуральном числе m, то такое число должно (для выполнения условия ) делиться на 35;
    
11. 
    раскладываем 21 на простые сомножители: 21 = 3 · 7; для того, чтобы число
    

A·k = 3 · 7 · m

делилось на 35, в правой части нужно добавить сомножитель 5, это и есть искомое минимальное значение A (вообще говоря, А может быть любым числом, кратным 5)

12. 
    Ответ: 5.
    

Решение (М.В. Кузнецова):

1. 
   Введём обозначения A = ДЕЛ(x, А), D₂₁ = ДЕЛ(x, 21) , D₃₅ = ДЕЛ(x, 35) и D_N = ДЕЛ(x, N)
   
2. 
   Введём множества:
   

A –множество натуральных чисел, для которых выполняется условие A

D₂₁ –множество натуральных чисел, для которых выполняется условие D₂₁

D₃₅ –множество натуральных чисел, для которых выполняется условие D₃₅

…

3. 
   Запишем формулу из условия в наших обозначениях
   

4. 
   Раскроем импликацию по правилу :
   

5. 
   Чтобы формула была тождественно истинной необходимо, чтобы (т.е. А=0), когда . Тогданаибольшее множество определяется как
   
6. 
   Множество , точно соответствующее выражению с помощью функции ДЕЛ получить невозможно. Очевидно, что А_min = D₃₅, т.е. 35 – наибольшее из чисел, соответствующих условию задачи. Меньшим может быть делитель 35, не являющийся делителем 21.
   
7. 
   Чтобы делитель 35 был решением необходимо, чтобы ни для одного из чисел, кратных ему не выполнилось условие: .
   
8. 
   Разложим 35 и 21 на простые множители: 35= 5 ∙ 7, 21=3 ∙ 7.
   
9. 
   7 – общий делитель, не может быть решением.
   
10. 
    Проверим 5. Вычислим «опасное» число, принадлежащее множеству , это 5∙21=105, но 105 : 35 =3 (остаток 0), т.е. и для него , значит 5 соответствует условию задачи.
    
11. 
    Ответ: 5