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

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

 https://ru.wikipedia.org/wiki/Логика_первого_порядка

По сути все клоны классической задачи 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)).
 
Определение А(мах) или А(мин) просто зависит от порядка
предикатов в импликации. Если А справа, то опреляется
минимальная область истинности, если слева то максимальная

Определим предикаты
Р(x) =  { 1; x ∈ [15;28] ;
              0; x !∈ [15;28]
            }
Q(x) = { 1; x ∈  [5;9] ;
              0; x !∈ [5;9]
           }

Определите максимальную область истинности  предиката А(х) такого,что

∀ x∈R :  A(x) => (P(x) ~ ¬Q(x)) = 1
∀ x∈R :  ¬A(x) v (P(x)⊕Q(x)) = 1
   Откуда следует вложение $(P⊕Q) в  $(A)
∀ x∈R :  A(x) => (P(x)⊕Q(x)) = 1 (*)


Область истинности  P(x)⊕Q(x)  есть $(P⊕Q)
Тогда $(P⊕Q) =  [15;28]\[5;9]∪[5;9]\[15;28]=[5;9]∪[15,28]
Допустим

∃ y∈R : (A(y)=1)^(P(y)⊕Q(y) = 0 ) = 1
Тогда
∃ y∈R : A(y) => P(y)⊕Q(y)  = 0

мы получаем противоречие с (*) , то есть $(A) вложено в $(P⊕Q)
Следовательно максимальная область истинности А(х)
есть область истинности  P(x)⊕Q(x) то есть  $(P⊕Q)
Максимальная длина связной компоненты [5;9]∪[15,28]
есть 28-15 = 13 

  
Определим предикаты
Р(x) =  { 1; x ∈ [11;21] ;
              0; x !∈ [11;21]
            }
Q(x) = { 1; x ∈  [15;40] ;
              0; x !∈ [15;40]
           }


Определите максимальную область истинности  предиката А(х) такого,что

∀ x∈R :  A(x) =>¬ (P(x)~Q(x)) = 1
∀ x∈R :  ¬A(x) v (P(x)⊕Q(x)) = 1
 Откуда следует вложение $(P⊕Q) в  $(A)
∀ x∈R :  A(x) => (P(x)⊕Q(x)) = 1 (*)

Область истинности  P(x)⊕Q(x)  есть $(P⊕Q)
Тогда $(P⊕Q) =  [11;21]\[15;40]∪[15;40]\[11;21]=[11;15]∪[21,40]
Допустим

∃ y∈R : (A(y)=1)^(P(y)⊕Q(y) = 0 ) = 1
Тогда
∃ y∈R : A(y) => P(y)⊕Q(y)  = 0

мы получаем противоречие с (*) ,то есть $(A) вложено в $(P⊕Q)
Следовательно максимальная область истинности А(х)
есть область истинности  P(x)⊕Q(x) то есть  $(P⊕Q)

Максимальная длина связной компоненты [11;15]∪[21,40]
есть 40 - 21 =19

*****************************************************************************
Пример решение той же задачи по http://labs.org.ru/ege-18-practice/
*****************************************************************************

Официальное решение

Теперь сформулируем эту же задачу следуя 

 https://ru.wikipedia.org/wiki/Логика_первого_порядка

Определите предикаты P(x) и Q(x), А(х) как одноместные
предикаты , то есть отображения вещественной оси во
множество {0,1} или {True,False} следующим образом

Р(x) =  { 1; x ∈ [11;21] ;
              0; x !∈ [11;21]
            }
Q(x) = { 1; x ∈  [1540] ;
             0; x !∈ [15;40]
           }

и найдите максимальный связный экстент в  области истинности  предиката А(х),как некоторого подмножества R  такого,что

∀ x∈R :  A(x) =>¬ (P(x)~Q(x)) = 1
 что равносильно
∀ x∈R :  A(x) => (P(x)⊕Q(x)) = 1  (*)

************
Решение
************
Обозначим область истинности  P(x)⊕Q(x)  через $(P⊕Q) 
    ∀ x∈R :  A(x) =>¬ (P(x)~Q(x))  = 1
    ∀ x∈R : ¬ A(x) v (P(x)⊕Q(x))   = 1  
          Откуда следует вложение $(P⊕Q) в  $(A)  
Заметим,что $(P⊕Q) =  [11;21]\[15;40]∪[15;40]\[11;21]=[11;15]∪[21,40]
Допустим
    ∃ y∈R : (A(y)=1)^(P(y)⊕Q(y) = 0 ) = 1
Тогда
    ∃ y∈R : A(y) => P(y)⊕Q(y)  = 0
мы получаем противоречие с (*)
Следовательно, максимальная область истинности А(х)
есть область истинности  P(x)⊕Q(x) то есть  $(P⊕Q)
Максимальная длина связной компоненты [11;15]∪[21,40]
 есть 40 - 21 =19 

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

Сформулируем ее следующим образом

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

Задача 01

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

Символ "R" в условии  заменим на  "S". "R" - означает как всегда
множество всех вещественных чисел.

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

Определим предикаты
Р(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]

Ответ на задачу Р02 соответственно будет (3)

Краткое пояснение