Wednesday, April 15, 2020

Решение системы булевских уравнений равносильное решению Р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

No comments:

Post a Comment