Cтраница 3
Конечно, понятие интерпретации выходит за рамки самого - исчисления. Оно относится к так называемой семантике исчисления, в отличие от понятий формулы, правил вывода, доказательства, которые относятся к синтаксису исчисления. [31]
Естественно рассматривать запросы такого вида семантически недопустимыми: ответы на запросы должны полностью определяться состоянием базы данных и не должны изменяться без изменения состояния базы данных. Именно для устранения таких семантически не корректных запросов введены в языке ALPHA понятия правильно определенной формулы, формулы с областью определения и понятия простого альфа-выражения. Часто эти ограничения либо слишком сильны, либо трудно проверяемы. [32]
Язык Pos позитивной выразимости получается из языка Par добавлением логической связки дизъюнкция V. Понятие терма в языке Pos совпадает с понятием терма в языке Par, а понятие формулы является очевидным обобщением понятия формулы в языке Par. Аналогично соответствующим понятиям языка Par вводятся понятия позитивной выразимости отношения и функции через функции множества Q, позитивного замыкания и позитивно замкнутого класса. [33]
Язык Pos позитивной выразимости получается из языка Par добавлением логической связки дизъюнкция V. Понятие терма в языке Pos совпадает с понятием терма в языке Par, а понятие формулы является очевидным обобщением понятия формулы в языке Par. Аналогично соответствующим понятиям языка Par вводятся понятия позитивной выразимости отношения и функции через функции множества Q, позитивного замыкания и позитивно замкнутого класса. [34]
Алфавит может выбираться при этом no - разному, но он обычно содержит, во-первых, буквы, называемые пропозициональными переменными ( число к-рых предполагается неограниченным); далее, в алфавит должны входить буквы, являющиеся знаками для логич. Так, если алфавит состоит из пропозициональных переменных, знаков конъюнкции ( &), дизъюнкции ( V), импликации (), отрицания () и скобок, то понятие формулы можно определить так: ( 1) Всякая пропозициональная переменная есть формула; ( 2) Если А и В - формулы, то ( А & В), ( А уВ), ( A iB) - формулы; если А есть формула, то ] А - тоже формула. [35]
По индукции определим понятие формулы над R. Одновременно всякой формуле над R будет сопоставлена булева функция, реализуемая этой формулой. [36]
Для обсуждения понятия разрешенной формулы исчисления доменов необходимо ввести типы переменных. Тип переменной х в формуле / - это или домен из 2), или неопределенная величина. Предположим опять для простоты изложения, что домены двух атрибутов не пересекаются или совпадают. Формально определять тип переменной и понятие разрешенной формулы мы не будем. Как и в исчислении кортежей, разрешенность - это просто требование согласования типов переменной в подформулах, а также требование, чтобы переменная, связываемая квантором, входила свободно в формулу, следующую за квантором. [37]
Для обсуждения понятия разрешенной формулы исчисления доменов необходимо ввести типы переменных. Тип переменной х в формуле / - это или домен из Ф, или неопределенная величина. Предположим опять для простоты изложения, что домены двух атрибутов не пересекаются или совпадают. Формально определять тип переменной и понятие разрешенной формулы мы не будем. Как и в исчислении кортежей, разрешенность - это просто требование согласования типов переменной в подформулах, а также требование, чтобы переменная, связываемая квантором, входила свободно в формулу, следующую за квантором. [38]
В тех случаях, когда число полюсов схемы не указывается, речь всегда будет идти о двухполюсных контактных схемах. Две контактные схемы называются эквивалентными, если они реализуют одну и ту же булеву функцию или одну и ту же систему функций. Сложностью контактной схемы называется число ее контактов. Контактная схема, имеющая наименьшую сложность среди всех эквивалентных ей схем, называется минимальной. Понятие формулы над множеством связок было определено в гл. [39]
Однако в этом случае труднее обстоит дело с определением соответствующей эквивалентности. Действительно, требуется уточнить понятие состояния и останется еще трудность, связанная с необходимостью предвидеть все возможные состояния. В математической логике имеется еще один - синтаксический - подход к определению той же эквивалентности формул, не требующий обращения к состояниям. Он основан на подходящем логическом исчислении. В каждом таком исчислении имеется понятие формулы, некоторые формулы объявляются аксиомами исчисления, и указываются правила вывода. Тогда две формулы и ж v объявляются эквивалентными, если формула ( и-у) Д f ( v - - u) выводима из аксиом. Доказывается, что и и v тогда и только тогда эквивалентны в указанном сейчас синтаксическом смысле, когда они семантически эквивалентны. Доказательство этой теоремы основано на серьезной теории ( см. § 2 гл. [40]