Файл: Архаров В.И. Арифметические и логические основы цифровых вычислительных машин учеб. пособие.pdf

Преобразования, которые вытекают из свойств операций ал­ гебры логики и не затрагивают свойств кванторов, применимы и к формулам исчисления предикатов. Особого рассмотрения требуют те преобразования, которые основаны на специфических свойствах кванторов. Из самого смысла кванторов общности и существования вытекают следующие эквивалентности.

1. Эквивалентности с отрицанием:

дхА (х) экв у х А (х),

у А (х) экв дхА (х),

на основании которых можно заменять у квантором 3 и наоборот. Эти эквивалентности являются аналогами:

A \\J А% экв. ЛХД Л 2,

ЛХД Л 2 экв. л х\ / л 2.

Применяя 1-ю эквивалентность к 3 yF (х, у), получим

(ух) Н (2 ) Д (G (xlt х2) V yyF (х, у)).

число конъюнкций (дизъюнкций), а также они указывают на опре­ деленную перестановочность однотипных операций, т. е. на пере­ становочность у с Д . Пример формул, которые не являются экви­ валентными:

Отсюда, если Л , (х) есть предикат «х есть четное число», а Л 2 (а:) есть предикат «х есть нечетное число», то первая из формул истинна,

вто время как вторая ложна.

Впрактике иногда требуется вынести константу из под знака квантора и наоборот.

Рассмотрим более подробно данную операцию. Пусть имеем формулу

ух {F(x)\JX(t) ^ G(x)/\x(t)}.

159

Необходимо вынести из под знака квантора относительную кон­ станту х {t). Для этого мы сначала приводим подкванторное выра­ жение к конъюнктивной нормальной форме с тем, чтобы можно было воспользоваться эквивалентностями (7.7, 7.8). После замены им­ пликации дизъюнкцией и отрицанием и применения теоремы де Моргана мы имеем:

yxlF (x)/\x(t)]\J[G(x)/\X (0],

ут 1( Щ V G (т)] Л [T(F) V X (01 Д ;

тогда

Л Й о у с ( т ) ] Л и Г ) у х ( / ) ] ) .

Здесь конъюнктивный член X (/) V X (t) равен 1 и поэтому может быть вычеркнут. Применение (7.7) дает:

ут [F (т) V G (т)] Д ух l(F (т) V X (/)] Д ух [X (/) V G (т)].

Применяя (7.7) к каждому из последних двух конъюнктивных членов, имеем:

ух [F (т) V G (т)] Д [ут? (т) V* (01Л \х (0 V VxG (т)].

Аналогичным образом выносятся константы из области опреде­ ления квантора у , для этого подкванторное выражение представ­ ляют в виде дизъюнкции конъюнкций.

§ 3. ПРЕДИКАТЫ С ОГРАНИЧЕННЫМИ КВАНТОРАМИ

Наряду с обычными кванторами по предметам у и g пользуются и так называемыми ограниченными кванторами.

соответствует выражению «для всякого х, которое меньше t, спра­ ведливо х (т)».

Ограниченные кванторы выражаются обычными формулами исчисления предикатов с участием специального предиката «%<Ду». Подобные формулы имеют вид:

З т [ т < / Д Х ( т ) ] , у т [ т < / -> Х(т)].

При правилах вывода ограниченные кванторы могут обозна­

160

Формула с ограниченными кванторами, где свободная перемен­ ная t, имеющая вхождения как граница квантора дт, а также как

аргумент предиката A (t), имеет вид:

и t. Данная формула содержит только одноместные предикатные переменные с ограниченными кванторами.

Пример 3. Рассмотрим, как в формуле (7.9) константа X (t) вы­ носится сначала за знак квантора у <7, а затем за знак квантора дт.

Нарушение эквивалентностей (7.7) и (7.8) для формул с огра­ ниченными кванторами можно иллюстрировать на следующем при­

При преобразовании формул с ограниченными кванторами воз­ можно использовать соотношения, вытекающие из специфики вы­

Большое место в математической науке занимает доказательство теорем. Доказательство есть последовательность утверждений, каждое из которых является или условием теоремы, или аксиомой, или ранее доказанной теоремой, или следствием предыдущих чле­ нов этой последовательности. Все члены этой последовательности можно записать формулами. Тогда доказательство превращается в последовательность формул. Чтобы придать доказательству бо­ лее формальный характер вводятся особые правила вывода.

161

Правило вывода есть некоторое выражение, образованное из формул, разделенных горизонтальной чертой. Формулы, стоящие над чертой, называются посылками, формула, стоящая под чертой, называется непосредственным следствием посылок по данному пра­ вилу вывода. Одним из основных правил вывода является правило отделения (modus ponens), которое имеет вид:

Ф , ф - > ф

Ф

Здесь две посылки: Ф и Ф - ф, формула ф есть их непосредст­ венное следствие. Доказательство с применением правил вывода обладает тем преимуществом, что оно исключает возможность до­ пущения ошибок. Построение формальных доказательств можно производить на вычислительной машине.

Логика предикатов может быть использована при построении таких разделов теории множеств, как алгебра подмножеств, теория бинарных отношений. Логика предикатов имеет то достоинство, что она облегчает изучение как исчисления предметов, так и абст­ рактных логических систем. Для теории и практики управления процессом в больших системах логика предикатов позволяет до­ статочно просто трансформировать n-мерные непрерывные прост­ ранства в n-мерные логические пространства, т. е. в пространство булевых векторов.

В настоящее время логические методы начинают использоваться для управления процессами в больших системах при решении мно­ гих частных задач, где в основном используется логика предикатов, так как они включают в себя все операции исчисления высказыва­ ний. В качестве предметной переменной предиката принимаются

Р(х) = ( зу ) Р( х , у).

Множество Ef , соответствующее предикату F, состоит из тех и только тех элементов поля М, для которых F (х), т. е. (ду) Р (х, у) истинно. Последнее выражение истинно для данного, если сущест­ вует такое у, что Р (х0у) истинно. Функции Р (х, у) отвечает часть Ер множества М 2. Итак, Ер состоит из всех тех элементов х поля М, для каждого из которых найдется пара (х, у), принадлежащая

Ег

Назовем х 0 проекцией любой пары (х 0, у), а проекцией множе­ ства — совокупность проекций принадлежащих ему пар. Легко видеть, что Ер есть проекция Ер. Пусть М — множество действи­ тельных чисел. В соответствии с аналитической геометрией будем представлять М 2 как плоскость, точки которой имеют координаты

162