Метод отображений и задача Р-26 файл ege23.doc

Исходная формулировка

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

   Диграмма генерирующая матрицу от х1х2 до х5х6 
  

Диграмма перехода от х5х6 к у5у6

 

   

Метод отображений и задача 7768 сайта "Сдам ЕГЭ "

Оригинальная идея исходит из техники Е.А. Мирончик, изложенной в документе ege23.doc на сайте К.Ю. Полякова. Конкретная задача отличается диспозицией нулей при генерации матрицы первых 5-ти уравнений и деревом решений при завершении подсчета окончательного числа решений с учетом 2-ух последних уравнений. Исходное уравнение взято на https://inf-ege.sdamgia.ru/test?theme=264. Этот пост демонстрирует применение метода отображений в ситуации существенно более сложной, чем этого обычно требуют задачи ЕГЭ 23.  Мы преднамеренно игнорируем известную битовую маску для {x} и решение представленное в видео Информатика БУ  (2015 Демо Версия ЕГЭ Информатика)
https://www.youtube.com/watch?v=MDL5Mym5Aac

(x1 ∨ x2)∧((x1 ∧ x2) =>x3)∧¬(x1 ∧ y1) = 1
(x2 ∨ x3)∧((x2 ∧ x3) =>x4)∧¬(x2 ∧ y2) = 1
...
(x5 ∨ x6)∧((x5 ∧ x6) =>x7)∧¬(x5 ∧ y5) = 1
(x6 ∨ x7)∧¬(x6 ∧ y6) = 1
x7 ∧ y7 = 0

Конвертация :-

(x1 ∨ x2)∧((x1 ∧ x2) =>x3)∧(x1 => ¬y1) = 1
(x2 ∨ x3)∧((x2 ∧ x3) =>x4)∧(x2 => ¬y2) = 1
...
(x5 ∨ x6)∧((x5 ∧ x6) =>x7)∧(x5 => ¬ y5) = 1
(x6 ∨ x7)∧(x6 => ¬y6)∧¬(x7 ∧ y7) = 1
 
Дерево решений:

Отображение уравнений 1-5
Наличие у1 {0,1} удваивает
число путей из 01 {x1,x2} в 10 и 11 {x2,x3}

x1	x2	x3	y1
0	1	0	1
			0
		1	1
			0
1	0	0	0
		1	0
	1	1	0

 
 Дерево решений:
 (x6 ∨ x7)∧(x6 => ¬y6)∧¬(x7 ∧ y7) = 1

x6	x7	y6	y7
0	1	1	0
		0	0
1	0	0	1
			0
	1	0	0

 

Алгебра предикатов и сложные задачи №18 с дискретными множествами и отрезками

Ниже мы используем следующее

Утверждение 01
***********************************************************
Пусть P и Q два одноместных предиката, определенных
На множестеве Х любой природы.
Если ∀ x ∈ Х : P(x) => Q(x) = True (*),то область истинности
предиката $(P) вложена в область истинности предиката $(Q)
***********************************************************
Допустим  ∃ y : (P(y)=1)^(Q(y) = 0 ) =1. Тогда P(y) => Q(y) = False
Что противоречит условию (*) и $(P) вложено в $(Q)
Отсюда также следует , что максимальная область истинности P ($(P)) есть область истинности Q ($(Q)), поскольку при Q(z)=1, мы можем не теряя общности считать P(z)=1, а минимальная область истинности Q ($(Q)) есть область истинности P ($(P)).
 
Определение А(мах) или А(мин) просто зависит от порядка
предикатов в импликации. Если А справа, то опреляется
минимальная область истинности, если слева то максимальная

Обозначим через R множество всех действительных чисел 

   Сформулируем задачу в соответствии с требованиями формальной логики и алгебры предикатов.

Пусть D,C.A одноместные предикаты на вещественной оси . Области истинности D,C определены ниже

D(x) = { 1; x ∈ [10;41];
              0; x !∈ [10;41]
           }
C(x) = { 1; x ∈ [20;95] ;
              0; x !∈ [20;95]
           }

Найти минальную область истинности А такого что

  ∀ x∈R : D(x) =>(C(x) =>A(x)) = 1 

Решение

  ∀ x∈R : ¬D(x) v ¬C(x) v A(x) = 1
  ∀ x∈R: ¬(D(x)^C(x)) v A(x)  = 1 
  ∀ x∈R:    D(x)^C(x) => A(x) = 1
По Утверждению 01 минимальная область истинности А 
есть $(A) = $(C)∩$(D) то есть пересечение 
                    [10;41] ∩ [20;95] =[20;41]

Рассмотрим еще 2 задачи, где использование Алгебры предикатов приводит к кратким, ясным и безупречным результатам с точки зрения формальной логики

Определим предикаты P(x) и Q(x) на множестве целых чисел
P(x) = { 1 : x ∈ {1,2,3,4,5,6} ;
             0 : x ! ∈ {1,2,3,4,5,6}
           }
Q(x) = { 1 : x ∈ {2,4,6,8,10} ;
              0 : x ! ∈ {2,4,6,8,10}
           }
Найти наименьшую область истинности предиката А такого что
   ∀ x ∈ N : ¬A(x) => (P(x)≡Q(x)) = 1
Последнее равносильно
   ∀ x ∈ N : (P(x)⊕Q(x)) => А(х) = 1
По Утверждению 01 наименьшая область истинности
    $(A) = $(P⊕Q) = {1,3,5,8,10}
Ответ: 5

Рассмотрим задачу Р02 из файла ege18.doc

Сформулируем ее следующим образом

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

Задача 01

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

Определим следующие одноместные предикаты

Определим предикаты
Р(x) = { 1; x ∈ [10;15];
             0; x !∈ [10;15]
           }
Q(x) = { 1; x ∈ [5;20] ;
            0; x !∈ [5;20]
           }
S(x) = { 1; x ∈  [15;25] ;
            0; x !∈ [15;25]
           }
Символ "R" в условии  заменим на  "S". "R" - означает как всегда
множество всех вещественных чисел.
Найти наименьшую область истинности предиката А(х) такого,что
∀ x∈R :  (A(x)vP(x))⊕(¬Q(x)vS(x)) = 1

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

Решение задачи 01

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

Область истинности предиката Х в дальнейшем

будем обозначать $(X)
Поскольку
∀ x∈R :  (A(x)vP(x))⊕(¬Q(x)vS(x)) = 1
       то $(AvP)∩$(¬QvS) = ∅
 в противном случае
∃ y∈ $(AvP)∩$(¬QvS) : (A(y)vP(y))⊕(¬Q(y)vS(y)) = 0
так как (A(y)vP(y))=1 и (¬Q(y)vS(y))=1

c другой стороны $(AvP)∪$(¬QvS) = R
в противном случае
∃ y∈ R\($(AvP)∪$(¬QvS)) :  (A(y)vP(y))⊕(¬Q(y)vS(y)) = 0
так как (A(y)vP(y))=0 и (¬Q(y)vS(y))=0

Таким образом мы получаем :-
$(AvP)∩$(¬QvS) = ∅
$(AvP)∪$(¬QvS) = R

Следовательно,
    $(AvP) = R\$(¬QvS)
Поскольку
   ∀ x∈$(P)∪$(Q) : P(x)vQ(x) = 1
   ∀ z ∈R\($(P)∪$(Q)) : P(z)vQ(z) =0
то $(¬QvS) = (-∞;5]∪[15;+∞),откуда
    $(AvP) = [5;15]
Следовательно, минимальная область истинности предиката А
    $(A)= [5;15]\[10;15] = [5;10]

Ответ на задачу Р02 соответственно будет (3)

 

Solution system P-46 via Helen A. Mironchick's approach for P-45 (ege23.doc)

The technique suggested  in 
http://kpolyakov.spb.ru/download/mea-2016-8.pdf
is still not very popular. Although examples of its application
to the P-45 and P-46 clearly demonstrate that working with 
couples is not always the dominant approach in terms of transparency and speed of obtaining results. The same goes for the post 
https://mapping-metod.blogspot.com/2019/03/blog-post.html
Moreover, all Helen Mironchick's strategies are pure mathematics,
where it is not necessary to understand how a deep result has been obtained
in order to successfully apply it, and often in various fields 

Original system

We utilize core technique developed in
 http://kpolyakov.spb.ru/download/mea-2016-8.pdf

I just believe that it is a successful follow up Helen Mironchick's 
original idea proposed by her in P-45 solution.
********************************
Now convert to equivalent
********************************
x1⊕x2=1
x3⊕x4=1
x5⊕x6=1
x7⊕x8=1 
x9⊕x10=1  
x11+x12=1  
(x1⊕x3)*(x4⊕x8)*(x2⊕x12) =0

Due to :-

x3⊕x4=1 attracts x3+x4 =1
x5⊕x6=1 attracts x5+x6 =1
x7⊕x8=1 attracts x7+x8 =1
x9⊕x10=1 attracts x9+x10 =1

System 01

x1⊕x2=1
x3⊕x4=1
x5⊕x6=1   has 2^5*3 = 32*3 =96 solutions
x7⊕x8=1 
x9⊕x10=1  
x11+x12=1  

****************************************
Now define number  of solutions
System 02
****************************************

x1⊕x2=1
x3⊕x4=1
x5⊕x6=1
x7⊕x8=1 
x9⊕x10=1  
x11+x12=1  
(x1⊕x3)*(x4⊕x8)*(x2⊕x12) =1

******************************************
Change the sequence  of equations
******************************************

x7⊕x8=1 
x8⊕x4=1  <= from last row
x4⊕x3=1
x3⊕x1=1  <= from last row
x1⊕x2=1 
x2⊕x12=1 <= from last row
x12+x11=1
x5⊕x6=1
x9⊕x10=1

 Final answer would be 96 - 12 =84

Метод Отображения с обратным просчетом

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

Основой метода отображений, используемого для вычисления количества решений логического уравнения или систем логических уравнений является выстраивание зависимости при добавлении уравнений или изменении самого уравнения. Получив схему перехода – имеем многодольный ориентированный граф. По которому можно найти любое решение и найти количество различных решений. Изменение всех дуг на противоположные в построенном графе не изменит количество «маршрутов продвижения» которые можно построить, но может оказаться полезным для решения задач.
Для комфортного чтения кликнете на первом снапшоте и Вы войдете в режим полно-экранного просмотра обоих 

Algebra of predicates and problems 277-282 from Polyakov's file ege18.doc

Let us start from snapshot

Consider problem 281 from pending queue for Informatics BU stream to provide an answer.

***********
Theorem 01
***********
Let P and Q be two single predicates defined
on the set of X of any nature.
If ∀ x ∈ X: P(x) =>Q(x) = True (*), then the region of truth
the predicate $(P) is embedded in the truth domain of 
the predicate $(Q).
Suppose that ∃ y: (P (y) = 1) ^ (Q (y) = 0) = 1.
Then P (y) => Q (y) = False
Which contradicts the condition (*) so $(P) is embedded in $(Q)
It also follows that the maximal truth domain P ($(P)) is the truth domain Q ($(Q)), since for Q(z)=1, we can assume
without loss of generality that P(z)=1, and the minimal the truth
domain of Q ($(Q)) is the truth domain of P ($(P)).

*********************************************************
Consider for instance problem 281 from ege18.doc
********************************************************
Redefine conditions of problem as follows below invoking
concepts of Algebra of predicates

Roots of the equation  x^2-16x-57=0  are x1=-3 and x2=19
When x∈ [-3;19] : x^2-16x-57 =< 0

Roots of the equation  x^2-4x-21=0   are x1=-3 and x2=7
When x∈ [-3;7] : x^2-4x-21 =< 0

Define predicates P(x) and Q(x)

P(x) = { 1 ; x ∈ [-3;19]
            0 ; x!∈ [-3;19]
          }
Q(x) = { 1 ; x ∈ [-3;7]
             0 ; x!∈ [-3;7]
           }
Determine the predicate A(x) largest truth domain,
which satisfy the conditions

∀ x∈R : A(x) => P(x) = 1  (1)
∀ x∈R : Q(x) => A(x) = 1 (2)

Remind that we defined $(Z) The Truth domain of predicate Z(x)
Due to Theorem 01 :   $(Q) ⊂ $(A) ⊂ $(P)
Thus largest Truth Domain of predicate A is [-3;19]


It is also quite obvious that, for example, task 277 can be formulated for two spheres in a three-dimensional space and can use a predicate algebra to formulate the problem.
It reminds me pretty much the situation with my post

https://vk.com/bderzhavets?z=photo209645472_456240189%2Falbum209645472_00%2Frev 

Which refers to my blog post 
https://informatics-ege.blogspot.com/2018/06/xy2z-120-x-y-z-1.html 

Just proceed as follows
***********************************************************
Problem 277 formulated in reasonable complexity
***********************************************************
Define two triple predicates P and Q

P(x,y,z) = { 1 : x^2+y^2+z^2 =< 100 ;
                  0 : x^2+y^2+z^2  > 100
                }

Q(x,y,z) = { 1 : x^2+y^2+z^2 =< 16 ;
                  0 : x^2+y^2+z^2 >  16
               }

Find the smallest and largest truth domain
of the triple predicate A(x,y,z) satisfying the conditions
    ∀ x,y,z ∈ R^3 : Q(x,y,z) => A(x,y,z) = 1 (1)
    ∀ x,y,z ∈ R^3 : A(x,y,z) => P(x,y,z) = 1 (2)

Due to Theorem 01 : $(Q)⊂$(A)⊂$(P)
So,largest Truth Domain of predicate A 
       is {x,y,z : x^2+y^2+z^2 =< 100 }
  smallest Truth Domain of predicate  A  
      is {x,y,z : x^2+y^2+z^2 =< 16  }
 

Unbreakable Mapping Method on it's way to the best approach for solving the systems of boolean equations (P-45)

In the example below, the last condition I managed to implement
changing three truth tables (three arrow charts)
in the process of finding solutions for the system

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

Original system

   Solve this system the first
   (x1 ≡ x2) v x3^x4  = 0
   (x3 ≡ x4) v x5^x6  = 0
   (x5 ≡ x6) v x7^x8  = 0
   (x7 ≡ x8) v x9^x10  = 0

   Solve this system in second order

   (x1 ≡ x2) v x3^x4  = 0

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

   which is equivalent to system below

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

  Thus original system

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

  has 42 solutions

  Passing Polyakov's control
  

  

Метод Отображений - уроки преподанные Е.А. Мирончик в рамках форума ЕГЭ Информатика

Решение оригинальной смстемы 115 из файла ege23.doc

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

Мы инициируем пару перехода не меняя уравнений

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