Bitwise2 vs Examer.com on solution task 18 for per bit conjunction

   
Решение задачи техникой      http://kpolyakov.spb.ru/download/bitwise2.pdf
¬Z(120) => (Z(96) => ¬A) =1
Z(120) + ¬Z(96) + ¬A =1
Z(96)^A => Z(120) =1
Z(96 or a) => Z(120) =1

Добавляем к 96 недостающие биты
120 =1111000
96   =1100000  => 1111000
================================
A(min) =  11000 (binary) = 24 (decimal)

Далее следует решение по https://examer.ru/app/inf/egenum/350/quiz

  

  

В действительности, решaется совсем другая задача

(X &120 ≠ 0) → ((X &96 ≠ 0) → (X &A ≠ 0)) ≡ 1

а именно :-

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

Bitwise2 shut
================================
Z(120) v Z(96) v ¬A  ≡ 1
A => ( Z(120) + Z(96))  ≡ 1
(A=>Z(120) v (A=>Z(96))  ≡ 1
A(min) = 96
================================

Возвращаемся к Examer.com "out dated logic"

  Преобразуем исходное выражение, выразив импликацию через дизъюнкцию: (X &120 ≠ 0) → ((X &96 ≠ 0) → (X &A ≠ 0)) ≡

≡ ¬(X &120 ≠ 0) ∨ ¬(X &96 ≠ 0) ∨ (X &A ≠ 0) ≡

≡ (X &120 = 0) ∨ (X &96 = 0) ∨ (X &A ≠ 0).

Переведём заданные числа в двоичную систему счисления 12010 = 11110002, 9610 = 11000002.

Определим те значения X, при которых истинно выражение (X &120 = 0):
В десятичной системе     В двоичной системе
X     ∗ ∗ ∗ ∗ ∗ ∗ ∗
120     1 1 1 1 0 0 0
0     0 0 0 0 0 0 0

Расставим в этом выражении вместо символов «*» цифры 0 или 1 на тех местах, где результат побитового умножения определяется однозначно. Получим
В десятичной системе     В двоичной системе
X     0 0 0 0 ∗ ∗
120     ∗1 1 1 1 0 0 0
0     0 0 0 0 0 0 0

Числа X , удовлетворяющие выражению (X &120 = 0), в двоичной системе счисления должны иметь вид 0000 ∗ ∗∗, где вместо «*» могут стоять 0 или 1.

Теперь определим те значения X , при которых истинно выражение X &96 = 0:
В десятичной системе     В двоичной системе
X     0 0 ∗ ∗ ∗ ∗ ∗
96     1 1 0 0 0 0 0
0     0 0 0 0 0 0 0

Числа X , удовлетворяющие выражению (X &96 = 0), в двоичной системе счисления должны иметь вид 00 ∗ ∗ ∗ ∗∗, где вместо «*» могут стоять 0 или 1.

Таким образом, числа, удовлетворяющие дизъюнкции (X &120 = 0) ∨ (X &96 ≠ 0), имеют вид 00 ∗ ∗ ∗ ∗∗.

Обозначим через S минимальное множество чисел X , при котором истинно выражение (X &A ≠ 0).

Следовательно, чтобы истинным было выражение (X &120 = 0) ∨ (X &96 = 0) ∨ (X &A ≠ 0),

множество S должно состоять из элементов вида: 10 ∗ ∗ ∗ ∗∗, 01 ∗ ∗ ∗ ∗∗, 11 ∗ ∗ ∗ ∗∗.

Для найденных значений X определим те значения A, при которых истинно выражение X &A ≠ 0 (так как побитовая конъюнкция должна быть отлична от нуля, то на тех местах, где в числе X находятся 1, в числе A также должна быть хотя бы одна 1). То есть числа A должны иметь вид: 1 ∗ ∗ ∗ ∗ ∗ ∗, ∗1 ∗ ∗ ∗ ∗∗, 11 ∗ ∗ ∗ ∗∗.

Из найденных чисел A выберем наименьшее, при котором выражение X &A ≠ 0 будет истинным для всех X ∈ S. Таким числом A в двоичной системе является 1100000.

11000002 = 9610.
Ответ: 96

Solution of one task type 23 from VK's News Wire 10.03.18 via mapping method

     Attempt to work via mapping method
 
    ((x1~x3)v(x2~x4))^(¬((x1~x3)^¬(x2~x4))) = 0
    ((x2~x4)v(x5~x7))^(¬((x2~x4)^¬(x5~x7))) = 0
    ((x5~x7)v(x6~x8))^(¬((x5~x7)^¬(x6~x8))) = 0
    ((x6~x8)v(x9~x10))^(¬((x6~x8)^¬(x9~x10))) = 0
    ((x1~x3)=>(x2~x4))=>((x6~x8)v¬(x9~x10)) = 1

   ((x1~x3)v(x2~x4))^((¬(x1~x3)v(x2~x4))) = 0
   ((x2~x4)v(x5~x7))^((¬(x2~x4)v(x5~x7))) = 0
   ((x5~x7)v(x6~x8))^((¬(x5~x7)v(x6~x8))) = 0
   ((x6~x8)v(x9~x10))^((¬(x6~x8)v(x9~x10))) = 0
   ((x1~x3)=>(x2~x4))=>((x6~x8)v¬(x9~x10)) = 1

  ((x1~x3)v(x2~x4))^((x1~x3)=>(x2~x4)) = 0
  ((x2~x4)v(x5~x7))^((x2~x4)=>(x5~x7)) = 0
  ((x5~x7)v(x6~x8))^((x5~x7)=>(x6~x8)) = 0
  ((x6~x8)v(x9~x10))^((x6~x8)=>(x9~x10)) = 0
  ((x1~x3)=>(x2~x4))=>((x9~x10)=>(x6~x8)) = 1


    ((x1 = x3) v (x2 = x4)) ^ ((x1 = x3) => (x2 = x4)) =0


    Build diagrama based on first equation which would work
   for first four equations. Notice that transition pairs are x2x4 , x5x7 , x6x8
   In fact adding 
         ((x1~x3)=>(x2~x4))=>((x9~x10)=>(x6~x8)) = 1 
   would add  ( 0 => 0) => (0 =>0)  =1 on lines "01" and "10"
   e.g. True => True = 1 . So adding  this 5-th equation won't decrease number      of solutions of original sytem 

   

    Passing Polyakov's Control

  

   

  Thus answer is 64

VK's Weekly test Informatics Variant 13 by Eugene Jobs

Source  180226 Информатика - Пробный вариант №13.pdf

 

Решение задачи 23 Демо версии ЕГЭ Информатика 2017 Методом отображений vs Метод битовых масок vs Информатик БУ Видео

Задача 23 Демо версии ЕГЭ Информатика 2017 хорошо известна  ролик
Информатика БУ  https://www.youtube.com/watch?v=uQtANwb_-Qs
Информатик БУ не использует дистрибутивность импликации по
отношению к конъюнкции, что влечет за собой меньшую прозрачность в получении результата.

   Строим диаграмму  генерации матрицы на основании уравнения
                         (x1 => (x2^y1)) ^ (y1 => y2) =1

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

  Метод битовых масок
******************************

В силу дистрибутивности импликации по отношению к конъюнкции

(x1 => (x2^y1))^(y1 => y2) =1  <=> (x1=>x2)^(x1=>y1)^(y1=>y2) =1
(x2 => (x3^y2))^(y2 => y3) =1  <=> (x2=>x3)^(x2=>y2)^(y2=>y3) =1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

и так для каждого уравнения
Получаем эквивалентную и хорошо известную систему

(x1 => x2)^(x2 => x3)^ . . . . . ^(x5 => x6) = 1
(y1 => y2)^(y2 => y3)^ . . . . . ^(y5 => y6) = 1
(x1 => y1)^(x2 => y2)^ . . . . . ^(x5 => y5)^(x6 => y6) = 1

Остается применить стандартную схему сцепления двух
верхнетреугольных битовых масок.  

x1 x2 x3 x4 x5 x6 

-------------------
1  1   1  1  1  1   1
0  1   1  1  1  1   2
0  0   1  1  1  1   3     Число конкатенаций 
0  0   0  1  1  1   4     каждого кортежа {x} строка номер j
0  0   0  0  1  1   5     c кортежами {y} ( с 1-го по j - ый)
0  0   0  0  0  1   6
0  0   0  0  0  0   7  Total = 1+2+3+ . . . .+7 = 28

y1 y2 y3 y4  y5 y6 

-------------------
1  1   1  1  1  1
0  1   1  1  1  1
0  0   1  1  1  1
0  0   0  1  1  1
0  0   0  0  1  1   x4=>y4 = False
0  0   0  0  0  1
0  0   0  0  0  0

Решение одной системы уравнений в булевских переменных Методом отображений вместо битовых масок ВК 09.02.18

     Конвертируем в эквивалетную систему

     (x1=>x2)^(y1=>y2) =1
     (x2=>x3)^(y2=>y3) =1
     . . . . . . . . .
     (x5=>x6)^(y5=>y6) =1
     x1=>y1 =1
  
    и применим метод отображений

  

Решение задач №13 и 14 из "Сколько различных решений имеет система уравнений.pdf" с помощью битовых масок versus Метод Отображений

   Источник 1Сколько различных решений имеет система уравнений.pdf

   13)  Запишем эквивалентную систему

          (x4 => x3) => (x2=>x1) =1
          (x6 => x5) => (x4=>x3) =1
          (x8 => x7) => (x6=>x5) =1
          (x10 => x9) => (x8=>x7) =1


         z1 = x2 =>x1
         z2 = x4 =>x3
         z3 = x6 =>x5
         z4 = x8 => x7
         z5 = x10 => x9


         z2 => z1 =1
         z3 => z2 =1
         z4 => z3 =1
         z5 => z4 =1


         z5  z4 z3 z2 z1
        ============
         1    1   1   1   1          3^5
         0    1   1   1   1          3^4
         0    0   1   1   1          3^3
         0    0   0   1   1          3^2
         0    0   0   0   1          3^1
         0    0   0   0   0          3^0


       Результат   (3^6 - 1) /2  =364

       14)

          (x3 => x4) => (x1=>x2) =1
          (x5 => x6) => (x3=>x4) =1
          (x7 => x8) => (x5=>x6) =1
          (x9 => x10) => (x7=>x8) =1
          (x1=>x2) => (x9 => x10) =1

         z1 = x1 =>x2
         z2 = x3 =>x4
         z3 = x5 =>x6
         z4 = x7 => x8
         z5 = x10 => x9


         z2 => z1 =1
         z3 => z2 =1
         z4 => z3 =1
         z5 => z4 =1
         z1 => z5 =1

        z5 z4 z3 z2 z1
       ===========
        1   1   1   1  1                3^5
        0   0   0   0  0                3^0

       Результат   243 + 1 = 244
         

       Метод отображений для задачи 14

 
   Сравни с https://www.youtube.com/watch?v=KNpJsN3smQg

Системный подход к решению задачи 18 (ДЕЛ(х,А)) ЕГЭ Информатика 2018

Наиболее сложный случай , когда уравнение сводится к импликации :-
    D(X,A)^D(X,S) => D(X,N) =1
Тогда A(min) есть  произведение простых делителей Q(j) числа N, начиная с наименьшего, которые не являются делителями S с учетом их кратности для N. Если Q есть общий делитель кратности N1 для N и кратности  N2
N2 для S то cмотри детали
http://egekp.unoforum.pro/?1-4-0-00000169-000-0-0-1515330726

Notice1
======
Допустим N и S содержат общий простой  делитель Q причем 
N в степени N1, а  S  в степени N2 и  N1 > N2.
Пусть А содержит Q в степени N3.  Пусть Х произвольное натуральное, делящееся на А и Q^N2. Импликация выше означает, что если  Х 
делится A и на Q^N2, то Х делится на Q^N1. 
Если N2 < N1, то в этом случае N3 (должно быть) >= N1. Чтобы минимизировать А необходимо положить  N3=N1

   138)

        D(A) => (¬D(28) v D(42)) = 1
        ¬D(A) v ¬D(28) v D(42) = 1
       D(A)^D(28) => D(42) = 1

        28 = 7*2*2
        42 = 7*2*3

     A(min) = 3
      
   139)

      (D(A)^D(21) => D(18)

      18 = 2*3^2
      21 = 3*7
 
  Per Notice1

    A(min) =18


  140)
          ((D(A) ^ ¬D(36)) => ¬D(12) = 1
          ¬D(A) v D(36) v ¬D(12) = 1
          ¬((D(A)^D(12)) v D(36) =`1
          D(A)^D(12) => D(36) = 1

 
  Per Notice1

           12 = 2^2*3
           36 = 2^2*3^2

  A(min) = 9


141)
        (D(A) ^ ¬D(50)) => ( ¬D(18) v D(50)) =1
        ¬D(A) v D(50) v ¬D(18) = 1
        ¬(D(A) v D(18)) v D(50) = 1
        D(A)^D(18)  => D (50) = 1

       18=2*3^2
       50=2*5^2
       5 имеет кратность 2

  A(min) = 25

  

   144)

     (D(A) ^ D(24) ^ ¬D(16)) => ¬D(A) = 1

    ¬D(A) v ¬D(24) v D(16) = 1

     (D(A)^D(24)) => D(16) = 1

        24 = 3*2^3

        16 = 2^4

    Per Notice1

      

     A(min) = 16

   145)

     (D(34) ^ ¬D(51)) => (¬D(A) v D(51)) = 1
     ¬D(34) v D(51) v ¬D(A) v D(51) = 1
    ¬((D(A)^D(34)) v D(51) = 1
    D(A)^D(34) => D(51) =1

    17 - общий делитель

     34 =17*2
     51 =17*3

   A(min) =3

146)

  ((D(15)^¬D(21)) =>(¬D(A) v ¬D(15)) =1
  ¬D(15) v D(21) v ¬D(A) v ¬D(15) =1
  ¬((D(15)^D(A)) v D(21) = 1
 D(15)^D(A) => D(21) = 1

    15=3*5
    21=3*7

 A(min) = 7

  131)

  (D(A)^D(12)) => (D(42) v ¬D(12)) = 1
  ¬D(A) v ¬D(12) v D(42) v ¬D(12) = 1
  ¬(D(A)^D(12)) v D(42) = 1
 D(A)^D(12) => D(42) = 1

 12 = 2^2*3
 42 = 2*3*7

 В этом случае N2(=2) > N1(=1) - нет проблемы

 A(min) = 7

*****************************************************************************
Можно ли доверять сайту https://bingoschool.ru/ege/informatics/
*****************************************************************************

Рассмотрим пример 8 из https://bingoschool.ru/ege/informatics/tasks/18/     и предложенное решение 

     (D(X,A)^¬D(X,100)) => (¬D(X,18) v D(X,100) ) = 1

     Решение

     ¬D(Х,A) v D(Х,100) v ¬D(Х,18) v D(Х,100) = 1
     ¬((D(Х,A)^D(Х,18)) v D(Х,100) = 1
     D(Х,A)^D(Х,18) => D(Х,100) =1
    
        18 = 2*3^2
        100 = 2^2*5^2

    Таким образом А = 100
    Контр-пример   к 50  есть 450
     
      
  
References
1. http://информатика23.рф/
2. http://egekp.unoforum.pro/?1-4-0-00000169-000-0-0-1515330726