Алгебра предикатов и классические примеры задач ЕГЭ Информатика № 18

Практически важнейшей сферой применения логики предикатов к логико-математической практике является сфера построения доказательств различных теорем, основывающаяся на теории логического следования. Более сложное строение формул логики предикатов, по сравнению с формулами логики высказываний, дает возможность проводить более сложные доказательства и в результате получать более тонкие заключения. [1] 

Подход к решению задач принципиально отличается от стандартов, исходящих из оригинальной работы
http://kpolyakov.spb.ru/download/inf-2015-10.pdf , 
а именно, мы используем Предикатную логику 1-го порядка. Смотри https://ru.wikipedia.org/wiki/Логика_первого_порядка

Всюду в дальнейшем N+ означает множество неотрицательных
целых чисел.По умолчанию х всегда принадлежит N+

По сути все клоны классической задачи 18 иcпользуют

Утверждение 01
**************************************************************
Пусть P и Q два одноместных предиката, определенных
На множестеве Х любой природы.
Если ∀ x ∈ Х : P(x) => Q(x) = True (*),то область истинности
предиката $(P) вложена в область истинности предиката $(Q)
**************************************************************
Допустим  ∃ y : (P(y)=1)^(Q(y) = 0 ) =1. Тогда P(y) => Q(y) = False
Что противоречит условию (*) и $(P) вложено в $(Q)
Отсюда также следует , что максимальная область истинности P ($(P)) есть область истинности Q ($(Q)), поскольку при Q(z)=1, мы можем не теряя общности считать P(z)=1, а минимальная область истинности Q ($(Q)) есть область истинности P ($(P)).
 
Определение А(мах) или А(мин) просто зависит от порядка
предикатов в импликации. Если А справа, то опреляется
минимальная область истинности, если слева то максимальная

Предварительно докажем также следующие теоремы

Обозначим через R множество всех действительных чисел

(Ср.Задачи 1,2 из http://kpolyakov.spb.ru/download/inf-2015-10.pdf )

***************

Теорема 1

***************
Пусть  A(x),B(x) одноместные предикаты,определенные на R
причем  ∀ x∈R : ¬A(x)vB(x) = 1
Тогда максимальная область истинности предиката А ($(A))
совпадает областью истинности предиката В ($(B))
*********************
Доказательство
*********************
Если B(z) = 1 то не теряя общности мы можем
считать A(z)=1,то есть $(B) вложено в $(A).
Известно, что
  ∀ x∈R : ¬A(x)vB(x) <=> A(x) => B(x)
Тогда
  ∀ x∈R : A(x)=> B(x) = 1 (*)
Допустим
  ∃ y∈ R: (A(y)=1)^(B(y)=0) = 1
Откуда
  ∃ y∈ R: A(y)=> B(y) = 0
что противоречит (*), таким образом $(A) вложено $(B)
Окончательно имеем $(A)=$(B)

****************
Теорема 2

****************
Пусть  A(x),B(x) одноместные предикаты,определенные на R
причем  ∀ x∈R : A(x)vB(x) = 1
Тогда минимальная область истинности предиката А ($(A))
содержит область истинности предиката ¬В ($(¬B))
*********************
Доказательство
*********************
∀ x∈R : A(x)vB(x) = A(x)v¬(¬B(x))
∀ x∈R : A(x)vB(x) = ¬B(x)=> A(x)
∀ x∈R : ¬B(x)=> A(x) = 1 (*)

Допустим
  ∃ y∈ R: (¬B(y)=1)^(A(y)=0) = 1
Откуда
  ∃ y∈ R: ¬B(y)=> A(y) = 0
что противоречит (*)
Тогда $(¬B) вложено в $(A)
То есть минимальная область истинности А ($(A)) содержит
область истинности ¬В  ($(¬B))

Следующий пример из http://kpolyakov.spb.ru/download/inf-2015-10.pdf
Ниже следует примеры решения задачи №3,5,6 использующий алгебру предикатов :-

    A(x) = { 1; x ∈ [x1;x2];
                  0; x !∈ [x1;x2]
                } 
   P(x) =  { 1; x ∈  [37;60] ;
                 0; x !∈ [37;60]
               }
   Q(x) = { 1; x ∈  [40;77] ;
                 0;  x !∈ [40;77]
               }
F(x) = P(x) => ((Q(x)^¬A(x)) => ¬P(x) ;

Определить наименьшую длину области истинности А(х)
   ∀ x: F(x)= P(x) => (((Q(x)^¬A(x)) => ¬P(x)) = True

  P(x) => (((Q(x)^¬A(x)) => ¬P(x) )<=> ¬P(x)v(¬Q(x)vA(x)v¬P(x)) 
  P(x) => (((Q(x)^¬A(x)) => ¬P(x)) <=>(¬P(x)v¬Q(x)vA(x))
  ∀ x :  ¬P(x)v¬Q(x)vA(x) = 1 

  ∀ x :  P(x)^Q(x) => A(x) = 1 (*)
  Допустим
  ∃ y :  (P(y)^Q(y) = 1) ^(A(y) = 0) = 1
  Тогда
  ∃ y : P(y)^Q(y) => A(y) = 0
  мы получаем противоречие с (*)

Наименьшая  область истинности A(x) есть пересение областей истинности P(x)  и  Q(x) , то есть [37;60]∩[40;77]=[40;60]
  

P(x) = { 1; x ∈ [2,4,6,8,10,12] ;
             0; x!∈ [2,4,6,8,10,12]
           }
Q(x) = { 1; x ∈ [4,8,12,116] ;
             0; x!∈ [4,8,12,116]
           }
Определить область истинности предиката А(х),
как множество натуральных чисел таким образом,что
∀ x: P(x) => ((Q(x)^¬A(x)) => ¬P(x)) = 1

∀ x: ((Q(x)^¬A(x)) => ¬P(x)) <=> (¬Q(x)vA(x)v¬P(x))
∀ x: ¬P(x)v¬Q(x)vA(x) = 1 
∀ x: P(x)^Q(x) => A(x) = 1 (*)
Допустим
∃ y :  (P(y)^Q(y) = 1) ^(A(y) = 0) = 1
Тогда
∃ y : P(y)^Q(y) => A(y) = 0
мы получаем противоречие с (*)

Наименьшая область истинности предиката А(х) есть
пересечение областей истинности  P(x) и Q(x) :-
  [2,4,6,8,10,12]∩[4,8,12,116] = [4,8,12]
Ответ : 24

P(x) = { 1; x ∈ [2,4,6,8,10,12,14,16,18,20] ;
             0; x!∈ [2,4,6,8,10,12,14,16,18,20]
           }

Q(x) = { 1; x ∈ [3,6,9,12,15,18,21,24,27,30] ;
              0; x!∈ [3,6,9,12,15,18,21,24,27,30]
           }

Определить наибольшую область истинности предиката А(х),
как множество натуральных чисел таким образом,что
∀ x: (A(x) => ¬P(x))^(¬Q(x) => ¬A(x)) = 1

∀ x: (A(x) => ¬P(x))^(¬Q(x) => ¬A(x)) <=> (¬A(x)v¬P(x))^(Q(x)v¬A(x))
∀ x: (¬A(x)v¬P(x))^(Q(x)v¬A(x)) <=> ¬A(x)v¬P(x)^Q(x)
∀ x: ¬A(x)v¬P(x)^Q(x) = 1
Если  ¬P(z)^Q(z)=1 то не теряя общности
мы можем считать A(z)=1 то есть $(¬P^Q) вложено в $(A)

∀ x: A(x) => ¬P(x)^Q(x)) = 1 (*)
Тогда  $(A) вложена в $(¬P^Q) (Утверждение 01)
Допустим
∃ y : (A(y)=1)^(¬P(y)^Q(y) = 0 ) = 1
Тогда
∃ y : A(y) => ¬P(y)^Q(y)  = 0
мы получаем противоречие с (*)
Наибольшая область истинности предиката А(х) есть
множество элементов области истинности Q(x), не принадлежащих
области истинности P(x) :-
   [3,6,9,12,15,18,21,24,27,30]\[2,4,6,8,10,12,14,16,18,20] =
           = [3,9,15,21,24,27,30] 

Определим предикаты:-

P(x) = { 1; x ∈ [10,25] ;
             0; x!∈ [10,25]
          }
Q(x) = { 1; x ∈ [15,30] ;
             0; x!∈ [15,30]
          }
R(x) = { 1; x ∈ [25,40] ;
             0; x!∈ [25,40]
           }

Определить наибольшую область истинности предиката А(х),
такого что
∀ x: (Q(x) => ¬R(x))^A(x)^¬P(x) = 0
∀ x: (¬Q(x)v¬R(x))^A(x)^¬P(x)   = 0
∀ x: (Q(x)^R(x))v¬A(x)vP(x)     = 1
∀ x: A(x) => (Q(x)^R(x)vP(x))  = 1 (*)
Если Q(z)^R(z)vP(z)=1 то не теряя общности
мы можем считать A(z)=1 то есть $(Q^RvP) вложено в $(A)
По Утверждению 01 $(A) вложена в $(Q^RvP)    
Допустим
∃ y : (A(y)=1)^(Q(y)^R(y))vP(y) = 0) = 1
Тогда
∃ y : A(y) => (Q(y)^R(y))vP(y)) = 0
Пoлучаем противоречие с (*)
Таким образом если обозначить области истинности
предикатов через $(A),$(P),$(Q),$(R) то А(х) будет
равен (Q(x)^R(x))vP(x)
и максимальной областью истинности предиката A(x)
будет $(A) = ($(Q)∩$(R))∪$(P) =
= ([15,30]∩[25,40]))∪[10,25] = [10,30]

Рассмотрим задачу Р02 из файла ege18.pdf

Сформулируем ее следующим образом. Вместо "R"  из условия

используем "S". "R" будет обозначать множество всех вещественных чисел.

**************

Задача 01

**************

Определим следующие одноместные предикаты

Определим предикаты
Р(x) = { 1; x ∈ [10;15];
             0; x !∈ [10;15]
           }
Q(x) = { 1; x ∈ [5;20] ;
            0; x !∈ [5;20]
           }
S(x) = { 1; x ∈  [15;25] ;
            0; x !∈ [15;25]
           }
Найти наименьшую область истинности предиката А(х) такого,что∀ x∈R :  (A(x)vP(x))⊕(¬Q(x)vS(x)) = 1

************************

Решение задачи 01

************************

Область истинности предиката Х в дальнейшем будем обозначать как и прежде  $(X).
Поскольку
    ∀ x∈R :  (A(x)vP(x))⊕(¬Q(x)vS(x)) = 1
       то $(AvP)∩$(¬QvS) = ∅
в противном случае
    ∃ y∈ $(AvP)∩$(¬QvS) : (A(y)vP(y))⊕(¬Q(y)vS(y)) = 0
поскольку  (A(y)vP(y))=1 и (¬Q(y)vS(y))=1

c другой стороны $(AvP)∪$(¬QvS) = R
так как в противном случае
   ∃ y∈ R\($(AvP)∪$(¬QvS)) :  (A(y)vP(y))⊕(¬Q(y)vS(y)) = 0
поскольку  (A(y)vP(y))=0 и (¬Q(y)vS(y))=0

Таким образом мы получаем :-
   $(AvP)∩$(¬QvS) = ∅
   $(AvP)∪$(¬QvS) = R

Следовательно,
    $(AvP) = R\$(¬QvS)
 Так как
   ∀ x∈$(P)∪$(Q) : P(x)vQ(x) = 1
   ∀ z ∈R\($(P)∪$(Q)) : P(z)vQ(z) =0
то $(¬QvS) = (-∞;5]∪[15;+∞),откуда следует,что
    $(AvP) = [5;15]
Следовательно, минимальная область истинности предиката А
    $(A)= [5;15]\[10;15] = [5;10]

Рассмотри задачу Р-28 из файла ege18.pdf

Определим предикаты

A(x) = { 1; x ∈  [70;90] ;
             0; x !∈ [70;90]
           }
B(x) = { 1; x ∈  [40;60] ;
              0; x !∈ [40;60]
           }
C(x) = { 1; x ∈  [0;N] ;
              0; x !∈ [0;N]
           }

F(x) = (¬A(x)=>B(x))^(¬C(x)=>A(x))
При каком наименьшем N область истинности F(x) содержит более 30 целых чисел

∀ x: (¬A(x)=>B(x))^(¬C(x)=>A(x)) <=> (A(x)vB(x))^(C(x)vA(x))
∀ x: (A(x)vB(x))^(C(x)vA(x)) <=> A(x)vB(x)^C(x)

Область истинности А(х) содержит 21 целое число.
Область истинности В(х)^C(x) есть [40;60]∩[0;N] и должна содержать не менее 11 целых чисел

Если N ∈ [40;60] то [40;60]∩[0;N]=[40;N]

При  N-40+1 = 10 => N=49 ∈[40;60] область истинности 
F(x) = A(x)vB(x)^C(x) содержит 31 целое число так как является объединением областей истинности А(х) и В(х)^C(x)

Рассмотрим задачу Р12 из файла ege18.pdf

Определим следующие одноместные предикаты на R :-
Р(x) = { 1; x ∈ [10;39];
             0; x !∈ [10;39]
           }
Q(x) = { 1; x ∈  [23;58] ;
             0; x !∈ [23;58]
           }
Наити наибольшую область истинности
предиката А(х) такого,что
∀ x∈R : P(x)^A(x) => Q(x)^A(x) = 1
Решение
∀ x∈R :¬P(x)v¬A(x)vQ(x)^A(x) = 1
∀ x∈R :¬P(x)v¬A(x)vQ(x) = 1
∀ x∈R : A(x) => ¬P(x)vQ(x) = 1
По Утверждению 01 максимальная область
истинности предиката А :-
  $(A)=$(¬PvQ)
Таким образом
  $(A) = ((-∞;10]∪[39;+∞))∪[23;58] = (-∞;10]∪[23;+∞)
Минимальная область истинности ¬A :-
  $(¬A) = [10;23]

Ответ : (3)

Определим следующие одноместные предикаты на R :-
Р(x) = { 1; x ∈ [14;34];
             0; x !∈ [14;34]
           }
Q(x) = { 1; x ∈  [24;44]
             0; x !∈ [24;44]
           }
Наити наибольшую область истинности
предиката А(х) такого,что
∀ x∈R : A(x) => (P(x) ≡ Q(x)) = 1

Решение
∀ x∈R : A(x) => (P(x)*Q(x)v¬P(x)*¬Q(x)) = 1 
По Утверждению 01 максимальная область
истинности предиката А :- 
$(A) = {$(P)∩$(Q)}∪{$(¬P)∩$(¬Q)}
$(P)∩$(Q) = [24;34]
$(¬P)∩$(¬Q) = (-∞; 14]∪[44; +∞)
$(A) = (-∞; 14]∪[24;34]∪[44; +∞)

Ответ : (4)

Пусть D,C.A одноместные предикаты на вещественной оси.
Области истинности D,C определены ниже

D(x) = { 1; x ∈ [10;41];
              0; x !∈ [10;41]
           }
C(x) = { 1; x ∈ [20;95] ;
              0; x !∈ [20;95]
           }
Найти минальную область истинности А такого что
∀ x∈R : D(x) =>(C(x) =>A(x)) = 1

Решение

∀ x∈R : ¬D(x) v ¬C(x) v A(x) = 1
∀ x∈R: ¬(D(x)^C(x)) v A(x)  = 1
∀ x∈R:    D(x)^C(x) => A(x) = 1

По Утверждению 01 минимальная область истинности А
есть $(A) = $(C)∩$(D) то есть пересечение
                    [10;41] ∩ [20;95] =[20;41]
*********************************************************
Пример задачи когда множество истинности
предиката А(х) не является связным
*********************************************************
Определим предикаты
Р(x) =  { 1; x ∈  [5;30] ;
               0; x !∈ [5;30]
            }
Q(x) = { 1; x ∈  [14;33] ;
            0; x !∈  [14;33]
            }

Определить наибольшее множество истинности предиката А(х)
определенного на множестве действительных чисел R такого,что
      ∀ x∈R : (P(x)≡Q(x)) => ¬A(x)=True
Решение.
Поскольку   (P(x)≡Q(x)) => ¬A(x) ≡ 1 то
    (P(x)⊕Q(x)) v ¬A(x) ≡ 1
    ∀ x∈R : A(x) => P(x)⊕Q(x) = 1 (*)
Если P(z)⊕Q(z)=1 то не теряя общности можно считать A(z)=1,
то есть $(P⊕Q) вложено в $(A)
Допустим
   ∃ y : (A(y)=1)^(P(y)⊕Q(y) = 0 ) = 1
Тогда
   ∃ y : A(y) => P(y)⊕Q(y)  = 0
мы получаем противоречие с (*) откуда $(A) вложено $(P⊕Q) 
Таким обазом , наибольшее множество истинности предиката А(х)
есть ([5;30]\[14;33])∪([14;33]\[5;30]) = [5;14]∪[30;33]
 
 
Ссылки
1. http://mathhelpplanet.com/static.php?p=primeneniye-logiki-predikatov