Sunday, July 30, 2017

Информатика23.рф задачи 165,163,173,168 (детальный разбор)


   165)

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

   Conversion into Z(k)
  
   (( ┐Z(13) + ┐A) => ┐Z(13)) + ( ┐A&Z(39))

   (Z(13)&A + ┐Z(13)) + ( ┐A&Z(39))
   ( ┐Z(13) + Z(13)&A) + ( ┐A&Z(39))

   **************************************************************
   Используем  A1 v (B1 & C1) = (A1 v B1) & (A1  v  C1)
   **************************************************************
 
   (Z(13) + ┐Z(13)&(A+ ┐Z(13)) +  ( ┐A&Z(39))
   A + ┐Z(13) + ( ┐A&Z(39))

 ***************************************************************
  Используем  A1 v (B1 & C1) =(A1 v B1) & (A1  v  C1)
 ***************************************************************
 
   A +  (┐A&Z(39))  ┐Z(13)
   (A + ┐A)&(A + Z(39))  ┐Z(13)
   Z(13) => A +Z(39)

   Применим Утверждение  10 из http://kpolyakov.spb.ru/download/bitwise2.pdf
  

  Если Z(13) => Z(39) is False , тогда утверждения
  Z(13) => A + Z(39) and  Z(13) => A  равносильны
  Следовательно,  А(max) = 13

 163)    Z(13) + Z(39) + (┐A┐Z(13))
            Z(13) + (┐A┐Z(13)) + Z(39)
            (Z(13)+┐A)(Z(13) + ┐Z(13)) + Z(39)
            Z(13) + ┐A + Z(39)
            A => Z(13) + Z(39)

    По Утверждению 9 http://kpolyakov.spb.ru/download/bitwise2.pdf
   
           А(min) = min(13,39) = 13


173)

  ((x&30 = 0)v(x&43 = 0) => ((x&19 != 0) = 0) => (x&A = 0))

  (Z(30) + Z(43)) => (┐Z(19) => A)

Побитная  конъюнкция 30 и 43

43 = 101011
30 = 011110
&
---------------------
10  = 001010

Z(10) => (Z(19) + A)
(Z(10) => Z(19)) + (Z(10)=>A)

A(max)= 10

168)

((x&20 !=0)v(x&55 !=0) => ((x&7 =0)=>(x&A !=0))

(┐Z(20) + ┐Z(55)) => (Z(7) => ┐A)
┐(Z(20)Z(55))=> (Z(7) => ┐A)
Z(20)Z(55) + ┐Z(7) + ┐A
┐(Z(7)A) + Z(20)Z(55)
(Z(7)A) => Z(20)Z(55)
Z(7)A   => Z(55)

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

55= 110111
20= 010100
v
----------------------
55 =110111
7  = 000111

Добавляем via А недостающие единицы

A (min) = 110000 = 48

Tuesday, July 25, 2017

Bitwise2 versus Решение задания №18. ЕГЭ по информатике - 2017 Демоверсия ФИПИ (Информатик БУ)

Actually,  you have two options

1.)  Watch for instance one of the best videos by Informatik BU https://www.youtube.com/watch?v=o1AYXrXHK_w

  

  Notice that Informatik BU states in the very beginning of video above that  there is no universal approach to solve such kind of problems and every particular case  requires particular consideration.

   However, I strongly believe that BU is pretty much wrong about that and will refer following articles  been written by Konstantin Polyakov

  1. http://kpolyakov.spb.ru/download/bitwise2.pdf dated February 19-th 2017.
  2. http://kpolyakov.spb.ru/download/inf-2015-10.pdf  dated October 2015.

2.)  Read  and understand http://kpolyakov.spb.ru/download/bitwise2.pdf

Z(51) v ((Z(41) => ┐A) =1
Z(51) v ( ┐Z(41) ┐A) = 1
Z (51) v  ┐(Z(41)A) = 1
┐(Z(41)A) v Z(51) = 1
 (Z(41)A) => Z(51) = 1

 51 = 110011 (binary)
 41 = 101001 (binary)

 A is supposed to add at least fourth and first bit to  41
 A(min)=2^4 +2^1 =18

 One more sample


   Z(43) + (Z(50) => ┐A) = 1
   Z(43) + (┐Z(50) +  ┐A) = 1
 ┐(Z(50)A) + Z(43) = 1
   (Z(50)A) => Z(43) = 1

   50 = 110010
   43 = 101011

    A is supposed to add at least third and zero bits to 50
    Thus A(min) = 2^3 + 1 = 9

*******************************************************************
General Polyakov's approach vs BU
http://kpolyakov.spb.ru/download/inf-2015-10.pdf
*******************************************************************


   https://www.youtube.com/watch?v=oOo_sSA2GBo

   ┐A^D(21) => ┐D(14) = 1
   A  + ┐D(21) + ┐D(14) =1
   A = ┐(┐D(21) + ┐D(14)) = D(21)^D(14)
   A= НОК(21,14) = 42

**************************************************************************************
Here goes a word in word quote from bitwise2.pdf  (Поляков && Здвижковa)
I deliberately quote in Russian.
**************************************************************************************
  Идея метода решения, предложенная А.В. Здвижковой, состоит в следующем:

1) упростить логическое выражение так, чтобы свести его к импликации и
избавиться от всех инверсий;

2) применить утверждения 3-7 с целью свести задачу к форме,
в которой можно использовать утверждение 2.
Упрощение может привести к нескольким разным формам выражения,
например, 

1) (Z(K)*A) =>Z(N)
2) Z(K) => A
3) Z(K) => (A + Z(N))
4) Z(K) => (A(k)*Z(N) )

В первом случае Z(K)*A = Z(K or a) , так что с помощью числа a
можно добавить в левую часть единичные биты числа N,
которых нет во множестве единичных битов числа K.

Во втором случае согласно утверждению 2 число a должно быть выбрано так,
чтобы все его единичные биты входили во множество единичных битов числа K.

В третьем случае с помощью утверждений 6 и 7 можно либо свести задачу
ко второму случаю, либо придти к выводу от том,что число a можно выбрать произвольно.

В четвёртом случае решение не всегда существует: с помощью числа a можно добавить в правую часть единичные биты, но нельзя их убрать.
Поэтому если множество единичных битов числа N не является
подмножеством единичных битов числа K, задача не имеет решения
(при любом выборе a выражение будет ложно при некоторых значениях x). 

Quoting finished

See also Информатика23.рф tasks 165,163 detailed solutions via Z(k) approach

*******************************************
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 [ 2 ]

    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 [ 2 ]  are satisfied :-

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

    Answer is 21


Reference provided bellow is supposed to demonstrate that approach been
developed in bitwise2.pdf is flexible enough to solve a bunch of different
samples  of tasks related with per bit's conjunction.

References

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

Tuesday, July 11, 2017

Техника Полякова "Множества и логика в задачах ЕГЭ " как универсальный подход к решению задач типа 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
Мирончик Е. А.

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

В статье рассматривается метод решения задания № 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

Thursday, July 6, 2017

Задача 18 ВКонтакте от 06/07/17



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

  Analyze when  ( ┐(x&120 != 0) v (┐(x&96 !=0)) is False

  ┐(x&120 != 0) = False (1)
  ┐(x&96 !=0)   =  False (2)

   (x&120 != 0) = True
   (x&96 !=0)   =  True


   120 = 1111000 ( binary)
   96   = 1100000  (binary)

Let's say that x is called  jeopardizing if it makes
    ┐(x&120 != 0)   =  False (1)
    ┐(x&96!  =  0)   =  False  (2)


Thus

   1   1   1  1 0  0 0  = 120 (decimal)
x
   x7x6x5x4x3x2x1

shouldn't be 0

   1   1   0  0  0 0  0   =96 (decimal)
x
   x7x6x5x4x3x2x1

shouldn't  be 0

   Consider jeopardizing bits in 120 and 96

   So for first equation { x7,x6,x5,x4 } should have  at least one bit equal 1
        for second equation { x7,x6 } should have at least one bit equal 1
 
  The minimal A (96) should have x7=1 x6=1 due to jeopardizing
  x might have 1 on position x7 or x6 and another 0.   
  First condition would also be satisfied when 

  x=11***** (binary) where "*' may be 1 or 0.
    or
  x=01*****(binary)
   or
 x=10***** (binary)

 if x7 and x6 are both equal 0 then

   1   1   0  0  0 0  0   =96 (decimal)
x
   x7x6x5x4x3x2x1

would  be equal 0. What breaks condition (2)

  So we must defend by 1 any of two  first  positions  in number A 
  and filed the rest positions with 0 to minimize A.

  Thus    A= 1100000 (binary) = 96 (decimal)

  I believe we are done with task 18

*************************
Another task
*************************

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

Proceed as follows :-

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

  Analyze when  ( ┐(x&120 != 0) v (┐(x&96=0)) is False
  ┐(x&120 != 0) = False (1)
  ┐(x&96 =0)   =  False (2)

   (x&120 != 0) = True
   (x&96 =0)   =  True


   120 = 1111000 ( binary)
   96   = 1100000  (binary)

Let's say that x is called  jeopardizing if it makes
    ┐(x&120 != 0)   =  False (1)
    ┐(x&96  =   0)   =  False (2)

Thus

   1   1   1  1 0  0 0  =  120 (decimal)
x
   x7x6x5x4x3x2x1

shouldn't be 0

   1   1  0  0  0 0  0   = 96 (decimal)
x
   x7x6x5x4x3x2x1

should  be 0


   Thus  for any of  jeopardizing x we should have (x&A != 0), otherwise we don't
  have any problem because at least one of (1) or (2) is True


      Consider jeopardizing bits in 120 and 96

   So for first equation { x7,x6,x5,x4 } should have  at least one bit equal 1
        for second equation { x7,x6 } should have x7=0 and x6=0

  So A=0011000 = 11000 (binary) = 24 (decimal)

Wednesday, July 5, 2017

Решение методом отображений Задачи 23 ВКонтакте от 11/08/17

 




  Equivalent system
    
  ┐(x1~x2)^┐(x1~x3) = 0
  ┐(x2~x3)^┐(x2~x4) = 0 
  ┐(x3~x4)^┐(x3~x5) = 0 
  . . . . . . . 
  ┐(x8~x9)^┐(x8~x10) = 0 

  Convert to next system

     (x1~x2)v(x1~x3) =1
     (x2~x3)v(x2~x4) =1
     (x3~x4)v(x3~x5) =1
     . . . . . . 
     (x8~x9)v(x9~x10) =1

Applying  mapping