Решение одгой системы уравнений в булевских переменных Метод Отображений и техника таблиц перекрестных ссылок

Толчком для демонстрации гибкости МО в сочетании техникой перекрестных ссылок для двух или трехместных предикатов образующих саму систему послужили некоторые системы из числа последних, пополнивших ege23.doc. Здесь совершенно все равно какая логическая операция связывает предикаты уравнения . Мощности попарного пересечения множеств истинности и ложности каждого из двух предикатов, образуюших систему однозначно определяют саму таблицу перекрестных ссылок. Количество переменных от  которых зависит предикат ( от 2 до 4 ) также не приводит к необходимости писать код для алгоритма МО.

Оригинальная система

((x1=>x2)=>x3) v ((x4≡x5)≡x6)≡1
((x4=>x5)=>x6) v ((x7≡x8)≡x9)≡1
((x7=>x8)=>x9) v ((x10≡x11)≡x12)≡1

Генерация матрицы

    Контроль

  

Решение задачи #T4834 Яндекс Репетитор Методом Отображений 10.2019

Оригинальная система

Эквивалентная система

(x1=>y1)^(x1⊕x2)=1
(x2=>y2)^(x2⊕x3)=1
(x3=>y3)^(x3⊕x4)=1
. . . . . .
(x8=>y8)^(x8⊕x9)=1
x9=>y9=1

Генерация диаграммы

Решение задачи #T29796 Яндекс Репетитор Методом Отображений с использованием таблицы перекрестных ссылок

Оригинальное уравнение

 Генерация диаграммы. В действительности, для любой пары двуместных предикатов с той же таблицей перекрестных ссылок результат будет тем же самым.

Chains of tie nodes of a multi-part graph && reverse pass to center per Helen Mironchick's "MAPPING METHOD - VISIBLE PART OF ICEBERG " - Computer science at school №10 2019

Original system

System 1

((x1^x2=>x3)^x4)=>x5=1
((y1^y2=>y3)^y4)=>y5=1
((z1^z2=>z3)^z4)=>z5=1
((x1=>y3))=>z4=1

For X-LINE

#2 is (x1^x2)
#3 is (x1^x2)=>x3
#4 is ((x1^x2)=>x3)^x4
#5 is (((x1^x2)=>x3)^x4)=>x5

For Y-LINE and Z-LINE replace x by y and x by z correspondingly

*******************
Chaining order
*******************
1) We get x3 via reverse pass to center
2) Getting y3 via reverse pass to center
3) Getting z4  via reverse pass to center

System 2

(x1^x2=>x3)^x4=>x5=1
(y1^y2=>y3)^y4=>y5=1
(z1^z2=>z3)^z4=>z5=1
(x3⊕y3)^(y4⊕z4)=1

For X-LINE

#2 is (x1^x2)
#3 is (x1^x2)=>x3
#4 is ((x1^x2)=>x3)^x4
#5 is (((x1^x2)=>x3)^x4)=>x5

For Y-LINE and Z-LINE replace x by y and x by z correspondingly

*******************
Chaining order
*******************
1) We get x3 via reverse pass to center
2) Getting y3 via direct XOR
3) Getting y4  via reverse pass to center
    Here we calculate y1^y2=>y3 (#3) Y-LINE.
    Perform move from y5 to #4 in the opposite direction.
    Now calculate y4 as usual.
4) Getting z4 via direct XOR
5) Completing Z-LINE having z4  (on line-0 112 , on line-1-200)

Метод обратного прохода по графу (ИВШ №10 2019 техника Е.А. Мирончик) и решение задачи 23 Информатиком БУ Стрим #60 2020

"Не стреляйте в пианиста - он играет, как умеет"
                                                                                  Оскар Уайльд
В оригинале звучит
Please do not shoot the pianist. He is doing his best.


Смотри :-
https://www.youtube.com/watch?v=oQKx0kc0TrQ (1 час 55 мин)
Последний линк может изменится при сохранении на ютуб через 24 часа и более . Если это произойдет то актуальный линк будет в  "UPDATE"

    Решение методом обратного прогона

 

Решение системы булевских уравнений равносильное решению Р50 ( ege23.pdf ) Методом отображений

В самой структуре систем, типа Р50 уже есть жесткое ограничение - это просто сдвиг на 1 по индексу, иначе  не возможно cдвигать битовые маски. "Метод Исключения" (Джобс) в отличие от "Метода Отображения", в принципе, применим к очень узкому классу систем типа Р50. Цель этого положить "МО" c большим числом переменных связи. При этом сдвиг на 1 по индексу как-то незаметно для авторов развязывает руки "МО", делая очень простым построение диаграмм истинности.
Решение Джобса для аналогичной задачи
https://www.youtube.com/watch?v=es1iCfN0eoA&t=6526s    1 час 23 мин.

Исходная ( эквивалентная Р50 ) система

(x1⊕x2=>x3)v(x5=>x4) =1
(x2⊕x3=>x4)v(x6=>x5) =1
(x3⊕x4=>x5)v(x7=>x6) =1
(x4⊕x5=>x6)v(x8=>x7) =1

Заметим , что исходящие биты х2х3х4 должны совпадать
с принимающими х2х3х4, что позволяет построить диаграмму для Метода Отображений относительно быстро.
Здесь важно заметить, что для любой из 16-ти строк исходящей колонки битовых комбинаций проанализировать надо только две из принимающих строк правой колонки в силу совпадения бит х2х3х4 (как и сказано выше) . Таким образом, число проверок 32 , а не 16*16=256 если мы имеем дело с клоном Р-50 , имеющим просто единичный сдвиг по индексу.  На настоящий момент у Джобса нет примера, который не клонировал бы идеологию Р-50 и действительно представлял бы проблему для Метода Отобажений.
 

На основании 1-го уравнения правильно  посчитаны 4-ки перехода х2х3х4х5

На основании 2-го уравнения правильно  посчитаны 4-ки перехода х3х4х5х6

На основании 3-го уравнения правильно  посчитаны 4-ки перехода х4х5х6х7

На основании 4-го уравнения правильно  посчитаны общее число  х5х6х7х8 тех и только тех кортежей, где 
х2х3х4х5 удовлетворяют  уравнению 1,  
х3х4х5х6 удовлетворяют  уравнению 2, 
х4х5х6х7 удовлетворяют  уравнению 3

Ссылки
1. С.С. Крылов,Т.Е. Чуркина Информатика и ИКТ Типовые экзаменационные варианты 2020, стр.56

Решение задания 23 из варианта 06042020 Евгения Джобса Методом Отображений VS Метод исключения (Джобс)

    Решение системы методом отображений
   

    Я затрудняюсь назвать эту диграмму сложной , трудной для построения на битовых тройках. Заметьте, что исходящие и принимающие биты х2х3 должны совпадать, то есть 2*8=16 проверок как на обычной системе с парами
Сила Метода Отображений в его общности. Он не меняется при переходе от одной задачи к другой.

    

Когда Евгений Джобс опубликует разбор 06042020 на ютуб я сделаю комментарии к его решению №23 и тех недостатков, которые я вижу при конвертации его подхода в универсальную систему решения задания №23.
======================
Добавлено 18/04/2020
======================
Разбор Джобса   
https://www.youtube.com/watch?v=es1iCfN0eoA&t=4609s

В самой структуре систем, которые предлагает Джобс уже есть жесткое ограничение - это просто сдвиг на 1 по индексу, иначе он не сможет cдвигать битовые маски. "Метод Исключения" в отличие от "Метода Отображения", в принципе, применим к очень узкому классу систем типа Р50. Цель этого положить "МО" c большим числом переменных связи. При этом сдвиг на 1 по индексу как-то незаметно для авторов развязывает руки "МО", делая очень простым построение диаграмм истинности.