Техника Полякова "Множества и логика в задачах ЕГЭ " как универсальный подход к решению задач типа 18

Обновление от 26.04.2019
==========================================================
Смотри работы
1. http://kpolyakov.spb.ru/download/mea18bit.pdf
2. https://mapping-metod.blogspot.com/2019/01/18.html
3. https://mapping-metod.blogspot.com/2018/12/bitwise2.html
4. https://mapping-metod.blogspot.com/2019/02/2017-versus-bitwise2-1-2.html

5. https://www.kpolyakov.spb.ru/download/mea-2019-03.pdf

Мирончик Е. А.

АЛГЕБРА ПРЕДИКАТОВ И ПОСТРОЕНИЕ ГЕОМЕТРИЧЕСКИХ МОДЕЛЕЙ НА ЕГЭ ПО ИНФОРМАТИКЕ

В статье рассматривается метод решения задания № 18 ЕГЭ по информатике и ИКТ. Основная идея метода состоит в записи условия задачи на языке формальной логики с использованием элементарных предикатов. Полученное сложное логическое выражение по законам логики преобразовывается в выражение, по которому строится геометрическая модель, позволяющая записать ответ. Изложенный алгоритм позволяет задание высокой сложности свести к простому.

 Перечисленные статьи касаются применения Алгебры предикатов (логики 1- порядка) к задачам ЕГЭ Информатика, тем самым доводя идеи оригинальной работы http://kpolyakov.spb.ru/download/inf-2015-10.pdf до достаточной полноты в контексте  требований формальной логики к работе с множествами.
Это ни в коей мере не умаляет важности упомянутой статьи К.Ю. Полякова. В сущности, давшей толчок для разработок с применением Алгебры Предикатов.  .
==========================================================

  
В обилии роликов выложенных в сети отсутствуют базовые понятия
теории множеств и их связь с математической логикой.
На мой взгляд, это делает ситуацию не более а как раз менее понятной,
чем в статье  "Множества и логика в задачах ЕГЭ "

Отполированная Поляковым идея Здвижковой (Армавир),которая в свою очередь исходит из идеологии Полякова 2015 года исключительно продуктивна.

На мой взгляд Bitwise2.pdf являтся типично совместной работой.
Определение Z(k)={ x: x&k=0 } позволяет эффективно оперировать
алгеброй Z(k)-ых. В сочетании с идеей Здвижковой (стр 7,8 Bitwise2.pdf)
придают статье Bitwise2.pdf законченный характер.

Следуем http://kpolyakov.spb.ru/download/inf-2015-10.pdf

   Обозначим через D[N] множество натуральных чисел, для которых побитовая конъюнкция с числом N дает ненулевое значение

                     D[N] = {x: x & N != 0}

Введем множества : D(N) = (x  ∈ D[N])), A = (x ∈ D[A]).
Исходная постановка :-

(x&120 != 0) => ((x&96! =0) => (x&A !=0))

Преобразуем исходное выражение,используя свойство импликации

                                               A => B= ┐A v B

D(120) => (D(96) => A) = D(120) => (┐D(96) v A) = ┐D(120) v ┐D(96) v A

Последнее приводит к базовой задаче 1 смотри inf-2015-10.pdf, где
                               B = ┐D(120) v ┐D(96)
Следовательно,

D(A(min)) = ┐(┐D(120) v ┐D(96) = D(120)^D(96)

Множество D(120) определяется условием  среди битов (6,5,4,3) есть ненулевые,считая крайний правый бит номером 0.
Множесто D(96) определяется условием  среди битов (6,5) есть ненулевые,считая крайний правый бит номером 0.

Следовательно D(120)^D(96) определяется  свойством среди битов (6,5) есть ненулевые. Для всех чисел из D(120)^D(96) найдется число А имеющие "1" в битах 6 и 5 такое что x&A != 0

Откуда следует A(min)=1100000 (binary) = 96 (decimal)

*****************************************************************************************
Решение той же задачи техникой  http://kpolyakov.spb.ru/download/bitwise2.pdf  В этой работе метод существенно продвинут и формализован с точки зрения математической строгости. 
*****************************************************************************************
 Определим :

 Z(k) = {x : x&k =0}   ┐Z(k) = {x : x&k != 0}

¬Z(120) => ( ¬Z(96) => ¬A)

 Z(120) + Z(96) + ¬A

Конвертиртируем в импликацию ( по утверждению 8 ) получим :-

 A => ( Z(120) + Z(96)) =(A =>Z(120)) + (A => Z(96)) =1

 A(min) = 96 утверждение 9 стр. 4 из bitwise2.pdf

***********************
Решая задачу
***********************

(x&120 != 0) => ((x&96 =0) => (x&A !=0))

D(120) => (┐D(96) => A) = D(120) => (D(96) v A) = ┐D(120) v D(96) v A

Получим D(A(min)) = ┐(┐D(120) v D(96)) = D(120)^┐D(96)
То есть 6 и 5 бит должны быть 0. Биты {4,3} содержат хотя бы одну 1.

Откуда A(min) = 11000 (binary) = 24 (decimal)

******************************************************************************************
Решение той же задачи техникой  http://kpolyakov.spb.ru/download/bitwise2.pdf
******************************************************************************************

¬Z(120) => ( Z(96) => ¬A)

 Z(120) + ¬Z(96) + ¬A


 Z(96) A =>  Z(120)

Z (96 or a)  => Z(120)

 Добавляем к 96 недостающие биты
 
120 =1111000
96   =1100000  => 1111000

A(min) =  11000 (binary) = 24 (decimal)

******************************************************************************************
Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K
(логическое «И» между соответствующими битами двоичной записи).
Определите наименьшее натуральное число А, такое что выражение

(x & 30 = 0)v((x & 57 =  0) => (x & A ≠  0))

тождественно истинно (то есть принимает значение 1 при любом
натуральном значении переменной x)?
*******************************************************************************************
 ┐D(30)v(┐D(57) => A )
 ┐D(30)v(D(57)vA)
 ┐D(30)vD(57)vA

************************************
Применяем базовую задачу 1
***********************************
D(A(min)) = ┐(┐D(30)vD(57))
D(A(min)) = (D(30)^ ┐D(57))

57 = 111001  => ┐D(57) характеризуется тем, что {5,4,3,0} все равны 0
30 = 011110  => D(30)  характеризуется тем, что из битов {4,3,2,1} хотя бы один
был равен 1

(D(30)^ ┐D(57)) требует,чтобы биты 5,4,3 все были равны 0.
Таким образом, нападающие (jeopardizing) {x} могут иметь
во втором и первом битах 01,10,11

Следовательно, A(min)=110 = 6 (decimal)

******************************************
Теперь, используя технику Bitwise2
******************************************
Z(30)+(Z(57) => ┐A) = 1

Z(30) + (┐Z(57) + ┐A) = 1
 ┐(Z(57)A) + z(30) = 1
(Z(57)A) => Z(30) = 1

57 = 111001
30 = 011110

Следовательно (cтр.7 строка 1 http://kpolyakov.spb.ru/download/bitwise2.pdf )
А(min) =110 (binary) = 6 (decimal)

Сравни с https://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=10&ved=0ahUKEwikp6XmpKXVAhXlQJoKHUilBMwQFghmMAk&url=http%3A%2F%2Fpedagog.mosreg.ru%2Fmedia%2Fdownload%2FF157B6C1C2301B5A3966F829DA205CF2&usg=AFQjCNHwCKtQyR7vbsnRYTFCEkyEHELoyw&cad=rjt

стр. 10,11 ( классический подход)

*****************************
Задачи на делимость
*****************************

D[N] - множество чисел, делящихся на N
D(N) ={ x : x ∈ D[n])  A = { x: x ∈ D(A)}

******************************
Сайт К.Ю. Полякова
******************************

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

ДЕЛ(x,А) → (¬ДЕЛ(x,21) ∨ ДЕЛ(x,35))

A => ( ¬D(21) v D(35 )

¬A v ¬D(21) v D(35)

Согласно базовой задаче 2

A(min) = ¬D(21) v D(35) = ¬(D(21)^¬D(35))

Либо

¬(A^ D(21)) v D(35)
   A^D(21)  => D(35)

Следовательно, А(min) = 5


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

¬ДЕЛ(x,А) → (ДЕЛ(x,6) → ¬ДЕЛ(x,4))

тождественно истинна для всех х

A v (¬D(6) v ¬D(4))

Согласно базовой задаче 1

A(max) = ¬(¬D(6) v ¬D(4)) = D(6)^D(4)
Следовательно, А(max) = 12

Следующее сравнение

    С другой стороны используем элементы теории множеств по Полякову

     D(18) => (┐A => ┐D(12))

    ┐D(18) v (A v ┐D(12))
     A v ( ┐D(18) v ┐D(12))

    ****************************************************** 
     Условия соответствуют базовой Теореме 1
    ******************************************************

     А = ┐(┐D(18) v  ┐D(12))  = D(18)^D(12)

    Ответ:  A(min) = 36

    Следующие примеры  из новостной ленты ВКонтакте

   (A^D(12) =>(D(42)v┐D(12))

  ┐Av┐D(12)vD(42)v┐D(12) = ┐Av┐D(12)vD(42) = ┐(A^D(12)vD(42) =
                                       
                                      (A^D(12)) => D(42)

Что означает - если число делится на А и на 12 то оно должно делится
и на 42. Следовательно, A(min) = 7
 

    (D(40) v D(64)) => A
    ┐(D(40) v D(64))) v A

    A v (┐D(40)^┐D(64))
 
  *****************************************************
   Условия соответствуют базовой Теореме 1
  ****************************************************

   A(max) =  ┐(┐D(40)^┐D(64)) = (D(40) v D(64))
   A(max) = НОД(40,64) = 8 
   
************************************************************************
Относительно сложный пример с побитовой конъюнкцией
************************************************************************

 Обозначим через D[N] множество натуральных чисел, для которых побитовая конъюнкция с числом N дает ненулевое значение

                     D[N] = {x: x & N != 0}

Введем множества : D(N) = (x  ∈ D[N])), A = (x ∈ D[A]).

***************************************************************
Найти наименьшее А , что для любого х :-
***************************************************************

((x&28 != 0)v(x&45!=0)) => ((x&17=0) => (x&A != 0))

Конвертируем уравнение к принятому синтаксису ( по Полякову)

(D(28)vD(45)) => ( ┐D(17) => A)

   (┐D(28) ^ ┐D(45))v(D(17) v A) = A v (D(17)v ((┐D(28) ^ ┐D(45)))

   

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

 Условия соответствуют базовой Теореме 1
 ************************************************

  D(A(min)) =  ┐(D(17) v  ((┐D(28) ^ ┐D(45)))
  D(A(min)) =  ┐D(17) ^ ┐((┐D(28) ^ ┐D(45))
  D(A(min)) =  ┐D(17) ^ ( D(28)vD(45))

  45 = 101101 (binary) (1)
  28 = 11100 (binary)   (2)
  17 = 10001 (binary)   (3)

From  (1)  {5,3,2,0} bits have at least one bit equal 1
From  (2)  {4,3,2} bits have at least one bit equal 1
From  (3)  {4,0} bits are both 0

Таким образом , {5,3,2,} bits have at least one bit equal 1
Тогда A(min) = 2^5 + 2^3 + 2^2 = 44

Это гарантирует , что для любого x  ∈ D(A(min)) = ┐D(17) ^ ( D(28) v D(45))
побитовая конъюнкция x&A != 0

******************************************************************************************
Решение той же задачи техникой  http://kpolyakov.spb.ru/download/bitwise2.pdf
******************************************************************************************

(┐Z(28) + ┐Z(25)) => (Z(17) => ┐A) =
Z(28)Z(45) + ┐Z(17) + ┐A =
Z(28)Z(45) + ┐(Z(17)A)     =
(Z(17)A) => Z(28)Z(45)
Z(17 or a) => Z(28)Z(45)

Побитная дизъюнкция  28 и 45

45 = 101101 (binary)
v
28 = 011100 (binary)
----------------------
61 = 111101

Недостающие биты в 17

61 = 111101
17 = 010001
=>{5,3,2 }

Согласно утверждению 2 статьи bitwise2.pdf

A(min) = 101100 = 2^5 + 2^3 +2^2 =44 (decimal)

***************************************************************
Найти наибольшее  А , что для любого х :-
***************************************************************
(x&A !=0) => ((x&37=0) =>(x&6 !=0))


┐Av( ┐D(37) => (x&6 != 0))
┐Av( D(37)vD(6) )

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

 Условия соответствуют базовой Теореме 2
 ***************************************************

 D(A(max)) = D(37)vD(6)

 37 = 100101 (binary)
   6 =       110 (binary)

A(max) есть побитовая дизъюнкция 100011 и 110
A(max) = 100111 = 2^5 + 2^2 + 2^1 + 1 = 32 + 4 +2 +1 = 39

********************
Альтернативно
********************

┐A => (Z(37) => ┐Z(6)) =1
┐A => (┐Z(37) + ┐Z(6)) = 1
A + ┐Z(37) + ┐Z(6) = 1
┐((Z(37)Z(6)) + A = 1
Z(37)Z(6) => A = 1

37 = 100101
v
6  = 000110
-----------------
39 = 100111

A(max) = 2^5 + 2^2 +2^1 + 1 = 32 + 4 + 2 + 1 = 39


Метод существенно продвинут и формализован с точки зрения математической строгости и формулировки алгоритмов в полностью
законченной форме в работе 2016 года  http://kpolyakov.spb.ru/download/bitwise2.pdf

*********************************************************************************
Решение примера  5 (А.Г. Гильдин) отличное от предложенного в
оригинальной статье 
********************************************************************************

(x&19 = 0)^(x&38 !=0) v ((x&43 =0) => ((x&A =0) ^(x&43 =0))) = 1

Z(19) ^ ┐Z(38) + (Z(43) => A ^ Z(43))

Z(19) ^ ┐Z(38) + (Z(43) => A) ^ (Z(43) => Z(43))
Z(19) ^ ┐Z(38) + (Z(43) => A)
Z(19) ^ ┐Z(38) + ┐Z(43) + A
z(43) => ( A + Z(19) ^ ┐Z(38))
((z(43) => A ) + (Z(43) => Z(19) ^ ┐Z(38))
Z(43) => A is True due to (Z(43) => Z(19) ^ ┐Z(38)) is False

Thus A(max) = 43


Рассмотрим примеры, которых либо нет в последней статье
либо они содержат другие данные. Это не суть. Просто демонстрация
метода и ничего более того. Раньше или позже они появятся на VK's
news wire.  Примеры взяты из   http://информатика23.рф/

Z(k) = {x : x&k =0}   ┐Z(k) = {x : x&k != 0}

 (x&26) v ( x&13) => ((x&78 != 0) =>(x&A = 0))
 (Z(26) + Z(13)) => ( ┐Z(78) => A )

  Z(26&13) => (Z(78) + A)

26 = 11010
     &
13 = 01101

Получаем 1000(binary) = 8 (decimal)

Z(8) => (Z(78) + A) = (Z(8) => Z(78))  +  (Z(8) => A)

Ответ:  A(max) = 8 


(x&A !=0) => ((x&56 = 0) => (x&20 != 0)

┐A => (Z(56) => ┐Z(20))
┐A => ( ┐Z(56) +  ┐Z(20))
A  + ┐Z(56) +  ┐Z(20)
┐( ┐Z(56) +  ┐Z(20)) => A
Z(56)Z(20) => A

Побитная дизъюнкция

56 = 111000
v
20 = 010100
-----------------------------
60 = 111100

Овет: A(max) = 60

((x&13 !=0) ^ (x&39 !=0)) => ((x&A !=0) ^ (x&13 != 0)

(┐Z(13) ^ ┐Z(39)) =>(┐A ^ ┐Z(13))

Z(13) + Z(39) + ┐A ^ ┐Z(13) = Z(13) + ┐A ^ ┐Z(13) + Z(39)

*****************************************************************************
Используем  (A1 v B1) & (A1  v  C1) = A1 v (B1 & C1)
          Z(13) =A1 , ┐A=B1, ┐Z(13)=C1 
   Следовательно,
       Z(13) + ┐A&┐Z(13) = (Z(13) + ┐A) & (Z(13) + ┐Z(13)) = (Z(13) + ┐A)
*****************************************************************************
(Z(13) + ┐A)^(Z(13) + ┐Z(13)) + Z(39) = (Z(13) + ┐A)^1 + Z(39)
(Z(13) + ┐A) + Z(39) = ┐A + Z(13) + Z(39) = A => Z(13) + Z(39)
(A => Z(13)) + (A => Z(39))

Ответ:  A(min) = 13

****************************************************************************
На мой взгляд одни из наиболее сложных примеров в Информатика23.рф.
Решения нет в оригинальном документе ( в Bitwise2.pdf решение 165 есть,
виноват 01.08.17 )
Информатика23.рф задача 165,163 (детальный разбор)
****************************************************************************

Определите наибольшее натуральное число A, такое что выражение
(X & 56 <> 0) -> ((X & 24 <> 0) -> (X & A <> 0))
тождественно истинно (то есть принимает значение 1 при
любом натуральном значении переменной X)? (Сборник Евич задача 18)

Конвертируем к Z(k) - ым

 ┐Z(56) => ((┐Z(24) => ┐A)

 ┐Z(56) => (Z(24) +  ┐A)
  Z(56) + Z(24) + ┐A
  A => (Z(24) + Z(56))
 (A => Z(24)) + (A => Z(56))

Thus A(max) = 56  

*******************************************
Another sample with line segments :-
*******************************************
https://vk.com/informatics_100?z=video-40390768_456239963%2F9c2fa5c518b46912ba%2Fpl_wall_-40390768


     Wouldn't the rest to be a fair enough, that Set Theory and Boolean Algebra
    do work in concert as noticed here http://kpolyakov.spb.ru/download/inf-2015-10.pdf

    P => ((Q^┐A) => ┐P) = 1
    P => ((┐QvA)v┐P) = 1
    ┐Pv ((┐QvA)v┐P)  = 1
    ┐QvAv┐P = 1

 Thus condition of Base Theorem 1 from http://kpolyakov.spb.ru/download/inf-2015-10.pdf  are satisfied :-

    A(min) = ┐(┐Qv┐P) = Q^P = [150,171]

    Answer is 21

References
1. http://kpolyakov.spb.ru/download/bitwise2.pdf
2. http://информатика23.рф/
3. https://vk.com/doc274136_438160388?hash=73a282e68021a356fd&dl=e038bf74bee1c54811