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

Практически важнейшей сферой применения логики предикатов к логико-математической практике является сфера построения доказательств различных теорем, основывающаяся на теории логического следования. Более сложное строение формул логики предикатов, по сравнению с формулами логики высказываний, дает возможность проводить более сложные доказательства и в результате получать более тонкие заключения. [1]. Смотри таже
  2.  Техника исчисления базисных предикатов по Е.А. Мирончик 2017 и ЕГЭ Задача 18 ( поразрядная конъюнкция ) 
  3.  Shooting problems P-22,P-23,P-25 via "Calculus of basic predicates" by E.A.Mironchick 2017

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



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

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)

Следующие примеры из работы
  К.Ю. Поляков Множества и логика в задачах ЕГЭ 2015
Ниже следуют решения задач №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)v¬Q(x))=>A(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)v¬Q(x)) => A(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
∀ x: A(x) => ¬P(x)^Q(x)) = 1 (*)

Допустим
∃ 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 (*)
Допустим
∃ 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]
*********************************************************
Пример задачи когда множество истинности
предиката А(х) не является связным
*********************************************************
Определим предикаты
Р(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 (*)

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

Таким обазом , наибольшее множество истинности предиката А(х)
есть ([5;30]\[14;33])∪([14;33]\[5;30]) = [5;14]∪[30;33]


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

Утверждение 01
Пусть P и Q два одноместных предиката, определенных
На множестеве Х любой природы.
Если ∀ x ∈ Х : P(x) => Q(x) = True ,то область истинности
предиката P вложена в область истинности предиката Q  

Ссылки
1. http://mathhelpplanet.com/static.php?p=primeneniye-logiki-predikatov