Cтраница 1
Область запрета может быть задана либо с помощью некоторого регулярного выражения, либо как совокупность слов - в алфавите Ж, не вошедших ни в одно из собв. Оба эти способа по существу эквивалентны между собой, поскольку от первого способа задания можно перейти ко второму и наоборот. [1]
Область запрета задана явно - в виде одного из регулярных выражений S, входящих в заданное множество регулярных выражений. [2]
Учитывая, что область запрета задается вторым из способов, описанных в предыдущем параграфе, находим, что неопределенным выходным сигналом является пустой сигнал, а неопределенным состоянием - пустое состояние. [3]
Все остальные слова составляют область запрета. [4]
Совокупность полученных элементарных конъюнкций описывает всю область запрета О: любой ее элемент принадлежит хотя бы одному из интервалов, задаваемых этими конъюнкциями. О - такой булевой функции, которая принимает значение 1 на множестве U и значение 0 на дополнительном множестве U. Каждый ее член представляет собой простую импликанту - элементарную конъюнкцию со следующими двумя свойствами: во-первых, она имплицирует функцию ф ( если конъюнкция принимает значение 1, то и функция тоже), во-вторых, она не имплицирует никакой другой конъюнкции, обладающей первым свойством. Если в ДНФ входят все простые импликанты ( как в данном случае), она называется сокращенной. [5]
Эта ДНФ описывает все ту же область запрета О, но в заметно более компактной форме. [6]
В качестве более наглядного способа описания области запрета можно рекомендовать матричный. [7]
Другое различие, которое мы осуществляем в области ритуальных запретов в нашем собственном обществе, это различие между священным и нечистым. К определенным вещам должно относиться с уважением потому, что они являются священными, к другим - потому что они являются нечистыми. Однако, как уже показали Робертсон Смит и сэр Джеймс Фрэзер, существует много обществ, в которых это различение совершенно неизвестно. Полинезийцы, например, не рассматривают вождя или храм как священное, а труп - как нечистое. Они все это рассматривают как опасные вещи. Один пример, относящийся к Гаваям, чтобы проиллюстрировать это фундаментальное тождество святости и нечистоты. Его присутствие было крайне опасным для всей общины, и так как он не мог очиститься, он должен был быть убит. Но если вождь высокого ранга, который в силу своего ранга, был, конечно, священным ( капу), женился на своей сестре, то он становился еще более священным. [8]
Закономерностям такого рода, выражаемым в виде областей запрета с достаточно простой формой, подчиняется и распределение материи в привычном для нас трехмерном пространстве. В результате проведенных астрономических исследований, направленных на изучение макроструктуры Вселенной, обнаружено существование областей, напоминающих громадные мыльные пузыри размером в миллионы и миллиарды световых лет, внутри которых не существует ни галактик, ни других сгустков материи - они как бы запрещены в этих областях, пронизываемых лишь слабым излучением далеких звезд. [9]
В графическом варианте нахождение минимальной ДНФ, описывающей область запрета, выглядит следующим образом: из сети выбрасывается любое звено, если только оно порождается некоторой отличной от этого звена проводящей цепочкой. Действительно, его всегда можно будет получить в качестве логического вывода. [10]
Происходит это, в частности, тогда, когда область запрета, образуемая совокупностью импликативных закономерностей, заведомо содержит некоторый объект обучающей выборки. [11]
Описанный выше алгоритм синтеза дает решение задачи при наличии области запрета. Однако при этом многие переходы в синтезированном автомате окажутся лишними в том смысле, что никогда не будут использоваться при реальной работе автомата. Задача состоит в том, чтобы выявить все такие переходы и построить вместо обычного ( вполне определенного) автомата частичный автомат, в таблицах переходов и выходов которого на местах запрещенных переходов стоят черточки. Переход к частичному автомату дает дополнительные возможности к последующему упрощению автомата. [12]
Рассмотрим теперь основные способы задания множеств допустимых слов и областей запрета, которые встречаются на практике. Для каждого из этих способов применительно к автоматам, полученным с помощью любого из описанных выше алгоритмов синтеза вполне определенных автоматов, укажем те выходные сигналы и состояния, которые будут при этом неопределенными. Правильность этих указаний легко проверить, анализируя соответствующие правила описанных алгоритмов синтеза. [13]
Представляя отдельные элементарные запреты сек-ционир Ьванными булевыми векторами, можно отобразить всю область запрета секционированной булевой матрицей. Задачи распознавания сводятся к выделению в ней некоторых миноров и проверке их на вырожденность. [14]
Очевидно, что эта задача эквивалентна рассмотренной ранее задаче минимизации ДНФ, задающей область запрета. [15]