Автор неизвестен - Бионика интелекта информация язык интеллект№ 3 (77) 2011научно-технический журналоснован в октябре 1967 г - страница 22

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 

v(x10x22 v x11 x21)y21 уз0 v (в)

(x20У20 vx22y21)x11 уз1)У10 vУз0)) = 1.

Дополнять уравнение (в) уравнениями (а) в данном случае нет необходимости, поскольку они не приняли участия при преобразовании уравне­ния (б) в уравнение (в). Обратим внимание на то, что формульное представление предиката f, по­лученное в примере, неизмеримо компактнее та­бличного. Усеченная таблица значений предиката f должна была бы содержать з-з-2-2-2=72 столбца. Уравнение же, выражающее предикат f, содержит всего 26 узнаваний букв. Определим, например, с помощью уравнения (в) выходное слово алфавит­ного оператора F для входного слова 12. Имеем x1=1, x2=2. Подставляем значения x1.и x2 в уравне­ние (в):

((10y20v12y21)(20y30v21y31)v(1022v1121)y21y30v(20y20v v22У21)11Уз1l0v1222Уl1У20Уз0))=1. Из полученного уравнения исключаем констан­ты. В результате получаем уравнение у10у21уз1=1, откуда находим: y10=1, y21=1, Уз1=1. Таким обра­зом, y1=0, y2=1, уз=1. Выходное слово равно 011.

Располагая уравнением, описывающим алфа­витный оператор F, можно решать обратную за­дачу: по заданному выходному слову отыскать со­ответствующее ему для оператора F входное слово. Рассмотрим пример. Для алфавитного оператора, введенного в предыдущем примере, по выходному слову 100 требуется найти соответствующее ему входное слово. Имеем y1=1, y2=0, Уз=0. Подстав­ляем значения y1, y2, уз в уравнение (в) и произво­дим упрощения. В результате получаем: x12x22=1, входное слово равно 22. Если в качестве выходно­го слова взять слово 010, то для него уравнение (в) принимает вид:

Xl2Xз0VXl0X22VXl 1X21 1.

Согласно последнему уравнению, выходному слову 010 соответствует три входных слова: 20, 02 и 11. Беря же в качестве выходного слова 101 и под­ставляя y1=1, y2=0, уз=1 в уравнение (в), получаем в его левой части 0; мы приходим к равенству 0=1, то есть к противоречию. Следовательно, не суще­ствует ни одного входного слова, которому бы ал­фавитный оператор F ставил в соответствие выход­ное слово 101.

Уравнение универсальной алгебры, описываю­щее алфавитный оператор F, можно использовать при решении различного рода логических задач, в которых фигурирует оператор F. Рассмотрим при­мер одной из указанных задач. В ней для того же алфавитного оператора, который рассматривался в предыдущих примерах параграфа, требуется най­ти входное и выходное слова, если известно, что обе буквы входного слова одинаковы, а первые и последние буквы выходного слова различны. По условию имеем x1=x2 и у1*уз. Условие x1=x2 запи­шем в виде высказывания: «x1=0 и x2=0, или x1=1 и x2=1, или x1=2 и x2=2», которое, в свою очередь, математически описывается следующим уравне­нием универсальной алгебры:

x10x20vx11 x21 vx12x

12

11

12

22

12

1.

(г)

Условие у1*уз представим в виде равносильного ему высказывания «y1=1 и уз=0, или y1=0, уз=1» а затем — в виде уравнения

Уl1Уз0vУl0Уз1=1. (д)

Решим совместно уравнения (б), (г) и (д). Для этого запишем все три уравнения в виде единого канонического уравнения:

(Xl0X20Уl0У20Уз0VXl0X21Уl0У20Уз1VXl0X22Уl0У21Уз0V

VXl1X20Уl0У20Уз1V VXl1X21Уl0У21Уз0VXl1X22Уl0У21Уз1VXl2X20Уl0У21Уз0V VXl2X21Уl0У21Уз1VXl2X22Уl1У20Уз0)(Xl0X20VXl1X21V VXl^CFlVvyl'V^l,в левой части которого раскрываем скобки и про­изводим упрощения, пользуясь законами ложности [1, (19)]. В результате получаем x12x22y11y^y30=1, откуда находим x1=x2=2, y1=1, y2=y3=0. Таким об­разом, условию задачи удовлетворяет единственная пара слов: входное слово 22 и соответствующее ему выходное слово 100 алфавитного оператора F.

Перейдем к рассмотрению второго метода представления алфавитных операторов. Метод по­зволяет осуществить неявное задание алфавитного оператора системой уравнений, число которых со­впадает с числом букв выходного слова этого опе­ратора. Когда указывают некоторый конечный ал­фавитный оператор y1y2^yq=F(xl, x2,..., xp), то тем самым задают систему

y1 =      x2...xp),

y2 = Fq (x1 x2...xp X

(30)

yq = Fq (x1 x2... xp )

алфавитных операторов F1, F2, ..., Fq, каждый из ко -торых формирует в зависимости от входного слова x1x2^xp соответственно одну букву y1, y2, yq вы­ходного слова y1y2^yq алфавитного оператора F. За­писывая для каждого из алфавитных операторов (30) соответствующее ему уравнение (29) универсальной алгебры, получаем аналитическое представление ал­фавитного оператора виде следующей системы, состоящей из q уравнений:

V    xf1 x^2..^1 = 1,

F (f1f2...f p )=E1

V    xf1 xf2...xfpy22 = 1,

F (f1f2...f p )=E2

(31)

V

F (f1f2...f p )=Eq

x1 1 x2 .

.xpyq

Рассмотрим пример аналитического представ­ления алфавитного оператора по второму методу. Описываем тот же оператор, что и в предыдущих примерах. По табл. 1 составляем три уравнения типа (31):

Vx20y10 v x10x21 y10 v x10x22y10 v x11 x20y10 V vx11 x21 y10 v x11x22y10 v x12x20 y10 V x12x21 y10 v x12x22 y11 = 1, x10x20y20 v x10x21 y20 v x10x22y21 v x11 x20 y20 v

v x11 x21 y21 v x11 x22 y21 v x12 x20 y21 v vx12 x21 y21 v x12 x22 y20 = 1, x10x20 y30 v x10x21 y31 v x10x22y30 v x11 x20 y31 v vx11 x21 y30 v x11 x22 y31 v

(е)

Записанная система уравнений равносильна уравнению (б), полученному для того же алфавит­ного оператора по первому методу. При сравнении описаний (б) и (е) видим, что в данном конкрет­ном примере первый метод дает более простое представление алфавитного оператора, чем второй (45 узнаваний буквы против 81), однако каждое из уравнений (е) проще, чем уравнение (б) (27 узнава­ний буквы против 45).

Заметим, что нетрудно перейти от описания ал­фавитного оператора одним уравнением к описа­нию того же оператора системой уравнений. Для получения описания функции y=F(x1x2...xp), где 1<i<q, нужно все узнавания букв для переменных y b..., yt_ 1, yi+1,..., yq в исходном уравнении положить равными 1. Например, подставляя 1 в уравнение (б) вместо y20, y21, y30, y31, находим первое из урав­нений (е). Для перехода от описания алфавитного оператора системой уравнений к описанию того же оператора одним уравнением надо образовать конъюнкцию всех уравнений системы. Например, образуя конъюнкцию левых частей всех уравне­ний (е) и приравнивая ее логическому значению 1, выведем уравнение, равносильное уравнению (б). Попытаемся упростить левые части уравнений (е). Осуществляя в них вынос за скобки некоторых из узнаваний и применяя усеченные законы истин­ности (а) и вытекающие из них усеченные законы отрицания, а также используя сокращения с помо­щью знаков - и ©, перепишем систему (е) в более компактном виде:

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

Автор неизвестен - Беседы на книгу бытие

Автор неизвестен - Беседы на шестоднев

Автор неизвестен - Богословие

Автор неизвестен - Божественность христа