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

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

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

Р-14. Элементами множества А являются натуральные числа. Известно, что выражение

(x {2, 4, 6, 8, 10, 12}) → (((x {4, 8, 12, 116})  ¬(x A)) → ¬(x {2, 4, 6, 8, 10, 12}))

истинно (т. е. принимает значение 1) при любом значении переменной х.

Определите наименьшее возможное значение суммы элементов множества A.

Решение:

1. 
   Заметим, что в задаче, кроме множества A, используются еще два множества:
   

P = {2, 4, 6, 8, 10, 12} Q = {4, 8, 12, 116}

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

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

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

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

5. 
   теперь используем закон де Моргана :
   

6. 
   поскольку это выражение должно быть равно 1, то A должно быть истинным везде, где ложно
   
7. 
   тогда минимальное допустимое множество A – это (по закону де Моргана)
   
8. 
   переходим ко множествам
   

= {4, 8, 12, 116}

= {2, 4, 6, 8, 10, 12}

9. 
   тогда – это все натуральные числа, которые входят одновременно в и ; они выделены жёлтым цветом: {4, 8, 12}
   
10. 
    именно эти числа и должны быть «перекрыть» множеством А_min, поэтому минимальный состав множества A – это А_min = {4, 8, 12}, сумма этих чисел равна 24
    
11. 
    Ответ: 24.
    

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

1. 
   на компьютерном ЕГЭ можно написать программу:
   

P = {2, 4, 6, 8, 10, 12} # множество P

Q = {4, 8, 12, 116} # множество Q

A = P & Q # пересечение множеств

print( sum(list(set(A))) )

2. 
   Ответ: 24.
   

Решение (3 способ, А.В. Лаздин, НИУ ИТМО):

1. 
   обозначим множества следующим образом:
   

L = {2, 4, 6, 8, 10, 12} M = {4, 8, 12, 116}.
тогда исходное выражение можно записать в упрощенной форме:

(x L) →(((x )  ¬(x A)) →¬(x L)) (1)

2. 
   если х не принадлежит множеству L, то выражение принимает значение 1, независимо от множества А (импликация из 0 всегда равна 1); таким образом, необходимо рассмотреть ситуацию, когда x L.
   
3. 
   Условие 1. x {2, 4, 6, 8, 10, 12}
   

В этом случае исходное выражение принимает следующий вид:

1 →(((x )  ¬(x A)) → 0) (2)

это выражение примет значение 0 только в том случае, если

(((x )  ¬(x A)) → 0) будет ложным.
Для этого выражение ((x )  ¬(x A)) должно быть истинным (импликация из 1 в 0).

4. 
   если х не принадлежит множеству М, то выражение 2 будет истинным не зависимо от множества А.
   
5. 
   таким образом множество А влияет на решение задачи только при одновременном соблюдении двух условий:
   

1. x {2, 4, 6, 8, 10, 12}

2. x {4, 8, 12, 116}

В этом случае исходное выражение принимает следующий вид:

1 →((1  ¬(x A)) → 0) (3)

6. 
   для того чтобы это выражение было истинным, выражение ¬(x A) обязательно должно быть ложным; для этого выражение x A должно быть истинным.
   
7. 
   значит, одновременно должны быть выполнены три условия:
   

1. 
   x {2, 4, 6, 8, 10, 12}
   
2. 
   x {4, 8, 12, 116}
   
3. 
   x A
   

для этого множеству А обязательно должны принадлежать числа 4, 8, 12.

8. 
   Ответ: 24.