Комбинаторная логика

Cтраница 1

Комбинаторная логика - одно из направлении в математической логике, занимающееся анализом понятий, к-рые в рамках классической математической логики принимаются без дальнейшего изучения. В классической математической логике пользуются правилами двух родов. Первые формулируются просто и используются без всяких ограничений. [1]

Комбинаторная логика - одно из направлений в математической логике, занимающееся анализом понятий, к-рые в рамках классической математической логики принимаются без дальнейшего изучения. В классической математической логике пользуются правилами двух родов. Первые формулируются просто и используются без всяких ограничений. [2]

Системы комбинаторной логики, определенные в предыдущем разделе, дают основу для вычисления Я-выражений во многом таким же способом, как это делают комбинаторы 5, К, I, В, С в гл. Однако представление Х - выражений в категорийной комбинаторной форме не только естественно в том отношении, что смысл таких выражений ясен, но также и в том, что примитивные операции, требуемые для механизма вычисления, вплотную соответствуют отдельным комбинаторам, формирующим выражение. Поэтому вычислитель наиболее просто определить в терминах преобразований некоторого состояния, представляющего частично вычисленное выражение по мере просмотра вычисляемого выражения. Это является основой категорийной абстрактной машины ( КАМ), [25, 64], спецификация которой напоминает SECD-ма-шину, рассмотренную в гл. [3]

В комбинаторной логике, условие, которое существует, когда два терма булевой функции ( В. [4]

Она основана на категориальной комбинаторной логике. Абстрактная машина для комбинаторной редукции этого типа, называемая категориальной абстрактной машиной ( КАМ), основана на прочном математическом фундаменте, способствующем достаточно высокой степени оптимизации. Интересно, что ее работа описывается в терминах переходов между состояниями, что очень напоминает операционную семантику SECD-машины. [5]

Существует, однако, сильная категорийная комбинаторная логика ККЛ, которая берет в качестве своих аксиом результаты теории декартовых замкнутых категорий, обсуждаемой в предыдущем разделе. Эти аксиомы, по существу, являются более абстрактной формой правил СККЛ в том смысле, что применения функций к переменным, представляющим контексты, заменены композициями с другими переменными функций. Это требует введения функции тождества Id вместе с двумя аксиомами, соответствующими ее композиции слева и справа. [6]

Набор правил переписывания, основанный на категорийной комбинаторной логике, редуцирует категорийные формы Я-вы-ражений к СЗНФ и формирует основу категорийной абстрактной машины. [7]

Правила, данные выше, фактически определяют слабую категориальную комбинаторную логику ( СККЛ), которая является слабой в том смысле, что не может редуцировать все Х - выра-жения ( или, точнее, результат применения comb к их версиям де Брейна) к их нормальной форме. СЗНФ и имеет нормальную форму Кх.х. Версия де Брейна для Q имеет вид: Я. [8]

На рис. 67, а приведена схема АЛУ в комбинаторной логике. Элементарная ячейка И собрана на элементе 2 И-ИЛИ-НЕ и функционирует в соответствии с таблицей на рис. 66, а. Для комбинации ( au a i 1) закрыт первый и открыт второй элемент И ( рис. 67, а), на выходе формируется аи - А - сигнал А; при инверсии ( ац a i 1) с выхода поступает инверсное значение Cj А. [9]

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

Динамический D-триггер на блокирующих элементах. [11]

Необходимо отметить, что микропроцессор можно реализовать на независимых базисных структурах: 1) на комбинаторной логике; 2) на матричной логике; 3) на регистрах или счетчиках. [12]

Мкл и NM, обозначаемая Мкл wNw - Подобным образом в Л - исчислении эквивалентность выражений, обозначаемая к, интерпретируется как рефлексивное транзитивное замыкание правил преобразования, данных в гл. В этом смысле комбинаторная логика может рассматриваться как модель Х - исчисления. [13]

Теорема Черча-Россера показывает, что сначала можно обрабатывать одну из двух частей, безразлично какую, а затем другую; порядок обработки никак не влияет на получаемые возможности. Соответствующая теорема доказана и в комбинаторной логике. В более широком смысле говорят, что любой язык, для которого существует понятие приводимости, обладает свойством Черча-Россера, или является конфлюентным, если для него справедлива теорема Черча - Россера. [14]

По-видимому, самые обнадеживающие сведения поступают сегодня из области таких дисциплин, как общая теория систем и некоторые менее известные направления современной формальной логики. Так, класс формализмов, называемый комбинаторной логикой, позволяет исследовать основания логики как таковой и иметь дело с феноменами вроде парадокса, неподвластными традиционной логике. Кроме того, существует новая логическая метадисциплина, называемая эпитеорией, которая позволяет разрабатывать бесконечное множество логик, соответствующих разным точкам зрения на мир. Я предчувствую, что на пути конвергенции этих дисциплин нас ожидает глубокое проникновение в сущность органического процесса. [15]

Страницы: 1 2