Техника исчисления базисных предикатов по Е.А. Мирончик 2017 vs Bitwise2

Ниже мы следуем технике предложенной в работе

http://kpolyakov.spb.ru/download/mea18bit.pdf

 

   Найти нименьшее  A чтбы для целых всех положительных "x"

   (x&24 != 0)⊕(x&9 != 0) => (x&A != 0)*(x&8 =0)

 

  Выдержка из статьи mea18bit.pdf

   Пусть Et(х)–предикат, множеством истинности которого являются все x, для которых x&t≠0.Если t является степенью двойки, то такой предикат будем называть базисным.Базисный предикат описывает (фиксирует) единственную единицу в двоичной записи числа. Далее для краткости предикат Et(х) будем обозначать Е(t) также будем обозначать и множество истинности этого предиката. 
Выдержка закончена

 Код ниже использует без предупреждения  

 ¬A + A*B = (¬A + A)*(¬A + B) = ¬A + B ;  A + A*B = A

Продолжим следующим образом 

 

(E(24)*¬E(9) + ¬E(24)*E(9)) => E(A)*¬E(8) = 1

  ¬(E(24)*¬E(9) + ¬E(24)*E(9)) + E(A)*¬E(8) = 1

 (¬E(24) + E(9))*(E(24) + ¬E(9)) + E(A)*¬E(8) = 1

 ¬E(9)*¬E(24) + E(9)*E(24) + E(A)*¬E(8) = 1

Избавимся от двойного вхождения ¬E (8) в первом слагаемом

 

¬E(16)*¬E(8)*¬E(1) + E(9)*E(24) + E(A)*¬E(8) = 1
E(9)*E(24)= (E(8) + E(1))*(E(16) + E(8)) =
    = E(8) + E(8)*E(16) + E(1)*E(16) + E(1)*E(8)

Применим принцип поглощения

 

  ¬E(16)*¬E(8)*¬E(1) + (E(8) + E(1)*E(16)) +  E(A)*¬E(8) = 1
  ((¬E(16)*¬E(1) + E(A))*¬E(8) + E(8) + E(1)*E(16) = 1
  (¬E(17) + E(A)) + E(8) + E(1)*E(16) = 1

Откуда  A(min)=17

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

Bitwise2 Решение

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

¬Z(24)⊕¬Z(9) => ¬A*Z(8) = 1
¬Z(24)¬Z(9) + Z(24)*Z(9) + ¬A*Z(8) = 1
¬(Z(24) + Z(9)) + Z(25) + ¬A*Z(8) = 1
¬Z(24&9) + Z(17)*Z(8) + ¬A*Z(8) = 1

Во-первых :-
24 = 11000
& - побитная конъюнкция
9 = 01001
==========
8 = 01000

Во-вторых, так как
Z(24)*Z(9) = Z(25) = Z(17)*Z(8)

17= 10001
"v"- побитная дизъюнкция
08= 01000
===========
25 = 11001

Продолжим :-
¬Z(8) + Z(17)*Z(8) + ¬A*Z(8) = 1
¬Z(8) + Z(17) + ¬A = 1
(A=> Z(17)) + (A=> ¬Z(8)) = 1

Откуда A(min) = 17 

Другой пример
**************************************************
Техника исчисления базисных предикатов
по Е.А.Мирончик  E(56)⊕E(25) => E(A)*¬E(24) = 1

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

E(56)⊕E(25) => E(A)*¬E(24) = 1
¬E(56)*¬E(25) + E(56)*E(25) + E(A)*¬E(24) = 1

¬E(32)*¬E(16)*¬E(8)*¬E(1) +
  + (E(32) + E(16) + E(8))*(E(16) + E(8) + E(1)) + E(A)*¬E(24) = 1

¬E(32)*¬E(16)*¬E(8)*¬E(1) +
  + E(32)*(E(16) + E(8) + E(1)) + E(16) + E(8) +
  + E(A)*¬E(16)*¬E(8) = 1

¬E(32)*¬E(1) + E(32)*(E(16) + E(8) + E(1)) + E(16) + E(8) + E(A) = 1
¬E(33) + E(32)*(E(16) + E(8) + E(1)) + E(16) + E(8) + E(A) = 1
E(33) => E(32)*(E(16) + E(8) + E(1)) + E(16) + E(8) + E(A) = 1
(E(33) => E(A)) + (E(33) => E(32)*(E(16) + E(8) + E(1)) +
         + (E(33) =>E(16)) + (E(33) => E(8))  = 1

Откуда следует A(min) = 33

**************************
Bitwise2 Решение
**************************
¬Z(56)⊕¬Z(25) => ¬A*Z(24) = 1
¬Z(56)¬Z(25) + Z(56)*Z(25) + ¬A*Z(24) = 1
¬(Z(56) + Z(25)) + Z(57) + ¬A*Z(24) = 1
¬Z(56&25) + Z(33)*Z(24)  + ¬A*Z(24) = 1

56 = 111000
& - побитовая конъюнкция
25 = 011001
===========
24 = 011000

33 = 100001
v - побитовая дизъюнкция
24 = 011000
============
57 = 111001

56 = 111000
v - побитовая дизъюнкция
25 = 011001
===========
57 = 111000

Таким образом мы получаем :-
    Z(56)*Z(25) = Z(57) = Z(33)*Z(24)
Продолжаем :-

 ¬Z(24) + Z(33)*Z(24)  + ¬A*Z(24) = 1
¬Z(24) + Z(33)  + ¬A = 1
(A => Z(33)) + (A => ¬Z(24)) = 1

Откуда следует A(min) = 33 

 

Графика , использующая круги и универсальное множество , в оригинальной статье Е.А. Мирончик также позволяет реализовать  альтернативные решения достаточно эффективно.

Литература

1. Множества в задачах с анализом битовых цепочек /Л.Л.Босова, Е.А. Мирончик//Информатика в школе /2017. No 7(130). С. 45-48.