Friday 13 December 2019

Drafting staff



((x1=x2)+x3)+x4+!x5=1
((x2=x3)+x4)+x5+!x6=1
((x3=x4)+x5)+x6+!x7=1
((x4=x5)+x6)+x7+!x8=1
Опускание на один уровень ниже должно,в принципе удваивать 
число листьев бинарного дерева, но необходимо убирать 
все ложные их 2,4,8,14

Старт 30 (2 ложных)
30*2-4=56
56*2-8=104
104*2-14=194

    

Контроль


Thursday 24 October 2019

Style 08.2016 on the go (Solving systems of Boolen Equations for USE Informatics)

Original system


(x1=>y1)^(x1 v x2)^¬(x1^x2)=1
(x2=>y2)^(x2 v x3)^¬(x2^x3)=1
(x3=>y3)^(x3 v x4)^¬(x3^x4)=1
(x4=>y4)^(x4 v x5)^¬(x4^x5)=1
(x5=>y5)^(x5 v x6)^¬(x5^x6)=1
(x6=>y6)^(x6 v x7)^¬(x6^x7)=1
(x7=>y7)=1

Notice first ( due to De Morgan rules ) :-

(x1 v x2)^¬(x1^x2)=(x1 v x2)^(¬x1 v ¬x2)=
=x1^¬x2 v x2^¬x1 = x1⊕x2

Convert to equivalent

(x1=>y1)^(x1⊕x2)=1
(x2=>y2)^(x2⊕x3)=1
(x3=>y3)^(x3⊕x4)=1
(x4=>y4)^(x4⊕x5)=1
(x5=>y5)^(x5⊕x6)=1
(x6=>y6)^(x6⊕x7)=1
(x7=>y7)=1

Fork 08.2016 chart to solve the system


Monday 21 October 2019

Solution of one USE Informatics system of Boolean equations in 08.2016 style

Original system


Orinal system
¬(x1≡x2)v¬(x1≡x3)^(x2≡x3)=1
¬(x3≡x4)v¬(x3≡x5)^(x4≡x5)=1
¬(x5≡x6)v¬(x5≡x7)^(x6≡x7)=1
¬(x7≡x8)v¬(x7≡x9)^(x8≡x9)=1

Convert to equivalent
  (x1≡x2) => (x1⊕x3)^(x2≡x3) =1
  (x3≡x4) => (x3⊕x5)^(x4≡x5) =1
  (x5≡x6) => (x5⊕x7)^(x6≡x7) =1
  (x7≡x8) => (x7⊕x9)^(x8≡x9) =1

   Here we have transition variables x3,x5,x7 rather then transition pairs
   between equations. Thus we would manage via 08.2016 charts.
  

Consider a bit more complex sample of similar system

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

Transition variables are x4 and x7. Fork 08.2016 chart for this system



The solution of one well-known problem from the USE Informatics forum in the format 08.2016 (Russian Federation)

Original wording in Helen Mironchikc's group

https://vk.com/club180658320?w=wall-180658320_64%2Fall



The first pass looks for the total number of solutions of the system, the second pass considers the number of false decisions. Answer: 448 - 32 = 416


Saturday 19 October 2019

Разбор СтатГрад 23.09.2019 Информатика ЕГЭ №23 vs решение в стиле 08.2016 той же задачи 23

Оригинальное решение

https://www.youtube.com/watch?time_continue=4&v=_Hf22YG3uU0

Разобрали по СтатГраду ответ 81 ( титанические усилия завершаются с ошибкой - "1" по строке "01" должна быть удалена так как y8=>x8=1 )

Решение в стиле 08.2016 ( с правильным ответом при этом еще и предоставляет foolproof by default )

(x1=>x2)^(y2=>y1)=1
(x2=>x3)^(y3=>y2)=1
(x3=>x4)^(y4=>y3)=1
(x4=>x5)^(y5=>y4)=1
(x5=>x6)^(y6=>y5)=1
(x6=>x7)^(y7=>y6)=1
(x7=>x8)^(y8=>y7)=1
(y8=>x8)=1


  

Thursday 17 October 2019

Algebra of predicates {D(k)} (Helen Mironchick ) versus Advanced Implication usage by Natalya Konina regarding problem 132 from ege18.doc

Original task

Solution bellow differs from the original one proposed by Helen Mironchick
to address question of Anastasia Stepanenko, however it is still based on algebra of {D(k)} ( see [1] ) .

Solution itself

D(A) v ¬D(24)^¬D(36) ≡1
D(24)≡ D(2^3)^D(3)
D(36)≡ D(3^2)^D(2^2)

¬D(24)^¬D(36)≡(¬D(2^3) v ¬D(3))^(¬D(3^2) v ¬D(2^2))≡
¬D(2^3)^¬D(3^2) v ¬D(2^3)^¬D(2^2) v ¬D(3)^¬D(3^2) v ¬D(3)^¬D(2^2)

Due to
¬D(3)^¬D(3^2)≡ ¬D(3)
¬D(2^3)^¬D(2^2)≡ ¬D(2^2)

Getting
¬D(2^3)^¬D(3^2) v ¬D(2^2) v ¬D(3) v ¬D(3)^¬D(2^2)≡ ¬D(2^3)^¬D(3^2) v ¬D(2^2) v ¬D(3)
because  ¬D(3) absorbs ¬D(3)^¬D(2^2)

Per De Morgan rules

¬D(2^3)^¬D(3^2) v ¬D(2^2) v ¬D(3)≡ ¬(D(2^3)vD(3^2) v ¬(D(2^2)^D(3))
¬(D(2^3)vD(3^2) v ¬(D(2^2)^D(3))≡ ¬(D(8) v D(9)) v ¬D(12)

Finally we obtain
D(А) v ¬(D(8) v D(9)) v ¬D(12) ≡1
Hence  A(min)=12

You might want to compare it with solution provided in
http://kpolyakov.spb.ru/download/ege18del.pdf 
for the task 132

References
1. E.A. Mironchick ALGEBRA OF PREDICATES AND RELATED GEOMETRIC MODELS CREATION IN REGARDS OF UNIFIED STATE EXAM IN INFORMATICS (RUSSIAN EGE) , Informatics in school #3 2019

Wednesday 16 October 2019

Решение задачи №132 из ege18.doc в Алгебре Предикатов {D(k)}

Условие

Алгебрa Предикатов {D(k)} определена в [1].

Решение

D(A) v ¬D(24)^¬D(36) ≡1
D(24)≡ D(2^3)^D(3)
D(36)≡ D(3^2)^D(2^2)

¬D(24)^¬D(36)≡(¬D(2^3) v ¬D(3))^(¬D(3^2) v ¬D(2^2))≡
¬D(2^3)^¬D(3^2) v ¬D(2^3)^¬D(2^2) v ¬D(3)^¬D(3^2) v ¬D(3)^¬D(2^2)

Так как
¬D(3)^¬D(3^2)≡ ¬D(3)
¬D(2^3)^¬D(2^2)≡ ¬D(2^2)

Получаем :-
¬D(2^3)^¬D(3^2) v ¬D(2^2) v ¬D(3) v ¬D(3)^¬D(2^2)≡ ¬D(2^3)^¬D(3^2) v ¬D(2^2) v ¬D(3)
поскольку  ¬D(3) поглощает ¬D(3)^¬D(2^2)

Два последних слагаемых сворачиваем по де Моргану
¬D(2^3)^¬D(3^2) v ¬D(2^2) v ¬D(3)≡ ¬(D(2^3)vD(3^2) v ¬(D(2^2)^D(3))
¬(D(2^3)vD(3^2) v ¬(D(2^2)^D(3))≡ ¬(D(8) v D(9)) v ¬D(12)

Окончательно имеем
D(А) v ¬(D(8) v D(9)) v ¬D(12) ≡1
Откуда  A(min)=12

Ссылки
1. Елена А. Мирончик АЛГЕБРА  ПРЕДИКАТОВ
И  ПОСТРОЕНИЕ  ГЕОМЕТРИЧЕСКИХ  МОДЕЛЕЙ
НА  ЕГЭ  ПО  ИНФОРМАТИКЕ , ИВШ №3 2019

Monday 14 October 2019

Решение одной задачи на побитную конъюнкцию в Алгебре Предикатов {E(k)}

Алгебра Предикатов {E(k}} определена в http://kpolyakov.spb.ru/download/mea18bit.pdf

Пусть {N(j)} j=1,2,...,m - конечное множество натуральных чисел.
Найти наименьшее А при котором имеет место следующее тождество
(E(N(1) =>(E(N(2) =>(E(N(3 )=> . . . .=>(E(N(m)) =>E(A)) . . . . ))) ≡1

Решение.

Преобразуем исходное выражение к виду:-
 m
 v (¬E(N(j) ) v E(A) ≡ 1
j=1
    m
¬( ^ E(N(j) ) v E(A) ≡ 1
   j=1
  m
( ^ E(N(j) ) => E(A) ≡ 1
 j=1

Эквивалентно
                     m
¬E(A) => ¬( ^ E(N(j) ) ≡ 1
                    j=1
Далее
                  m
¬E(A) => ( v ¬E(N(j) ) ≡ 1
                 j=1
В силу дистрибутивности импликации
по отношению к дизъюнкции :-
  m
  v (¬E(A) => ¬E(N(j) ) ≡ 1
 j=1

Эквивалентно
  m
  v ( E(N(j) => E(A) ) ≡ 1
 j=1


По теореме 1 в https://mapping-metod.blogspot.com/2019/02/2017-versus-bitwise2-1-2.html
получаем A(min)  =  min{N(j)}
                              j=1,2,..,m

Если нет ни одного N(j) все биты которого входят в А то последняя дизъюнкция не может быть равна тождественно 1 , так как каждое слагаемое дает бит, не входящий в А, строим двоичное число z0 , содержащие все эти биты (наличие совпадающих только упрощает ситуацию)
Тогда
  m
( v (E(N(j) => E(A))(z0) = 0
 j=1

то есть если А < A(min), то каждое N(j) имеет такой бит и найденное А(min) действительно минимально.
Следствие
Любая задача вида Е(M)=>(E(N)=>E(A)) ≡ 1 тривиальна  A=min{M,N}
Например



                                                                               

Sunday 13 October 2019

Predicates truth and false sets regarding solving problems 23 USE Informatics VK's News Wire

Original source



Intentionally consider more complicated system

(((x1∧y1)) ≡ (x2∧y2)) => (x3∧y3))=1
(((x2∧y2)) ∨ ¬(x3∧y3)) => (x4∧y4))=1
(((x3∧y3)) ≡ (x4∧y4)) => (x5∧y5))=1
(((x4∧y4)) ∨ ¬(x5∧y5)) => (x6∧y6))=1 

Introduce predicate z(x,y)= (x^y).
Power of false set is equal 3.
Power of truth set is equal 1.
Would you replace z(x,y)  with w(x,y)=(xVy).
Power of false set is equal 1.
Power of truth set is equal 3.
The general approach will stay the same - outgoing
numbers and initial values would be updated correspondingly,
but arrows charts would stay the same

Denote zj=xj^xj
Convert system into zj variables
(1)
(z1≡z2) => z3 =1
(z2∨¬z3) => z4 =1
(z3≡z4) => z5=1
(z4∨¬z5) => z6 =1

(2)
(z1≡z2) => z3 =1
(z3 => z2) => z4 =1
(z3≡z4) => z5=1
(z5 => z4) => z6 =1


Consider system

(((x1Vy1)) ≡ (x2Vy2)) => (x3Vy3))=1
(((x2Vy2)) ∨ ¬(x3Vy3)) => (x4Vy4))=1
(((x3Vy3)) ≡ (x4Vy4)) => (x5Vy5))=1
(((x4Vy4)) ∨ ¬(x5Vy5)) => (x6Vy6))=1

Denote wj=(xjVyj) . Notice that arrows charts are exactly the same.
Initial values and outgoing numbers has been updated due to different powers
of truth and false sets of predicate w(x,y)=(xVy), 3 and 1 correspondingly

(w1≡w2) => w3 =1
(w3 => w2) => w4 =1
(w3≡w4) => w5=1
(w5 => w4) => w6 =1




Saturday 12 October 2019

Solution via decomposition into basic predicates several problems 18-th currently posted to Informatics_100 News Wire


Solution via decomposition into basic predicates
E(77)=E(64) v E(8) v E(4) v E(1) ;
E(12)=E(8) v E(4)
Now original equation has been converted per De Morgan rules:-
¬E(77) v E(12) v E(A) ≡ 1;
¬E(64)^¬E(8)^¬E(4)^¬E(1) v E(8) v E(4) v E(A) ≡ 1
Suppress E(8) and E(4) in conjunction
¬E(64)^¬E(1) v E(12) v E(A) ≡ 1 ;
¬E(65) v E(12) v E(A) ≡ 1
Hence A(min) = 65


¬E(33)=>(E(45)=>E(A)) ≡ 1
E(33) v ¬E(45) v E(A) ≡ 1
E(33)=E(32) v E(1) ;
E(45)=E(32) v E(8) v E(4) v E(1)
E(32) v E(1) v ¬E(32)^¬E(8)^¬E(4)^¬E(1) v E(A) ≡ 1
Suppress E(32) and E(1) in conjunction
E(32) v E(1) v ¬E(8)^¬E(4) v E(A) ≡ 1;
E(33) v ¬(E(8) v E(4)) v E(A) ≡ 1
E(33) v ¬E(12) v E(A) ≡ 1
Hence
A(min)=12

Featured Post

Solution of one USE Informatics system of Boolean equations in 08.2016 style

Original system Orinal system ¬(x1≡x2)v¬(x1≡x3)^(x2≡x3)=1 ¬(x3≡x4)v¬(x3≡x5)^(x4≡x5)=1 ¬(x5≡x6)v¬(x5≡x7)^(x6≡x7)=1 ¬(x7≡x8)v¬(x7≡x9...