книги из ГПНТБ / Архаров В.И. Арифметические и логические основы цифровых вычислительных машин учеб. пособие

Формула с ограниченными кванторами, где свободная перемен­ ная 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

х, у, а М — как ось ох этой плоскости. В этом случае точка х является проекцией точки (х, у). Поэтому множество Е Р, отвечающее логи­ ческой функции F (х), равной (gp) Р (х, у), совпадает с обычной ортогональной проекцией множества Ер на ось ох. Обозначая про­ екцию какого-нибудь множества Я на М символом ПрхН, мы мо­ жем записать, что

Ер = прхЕр.

Чтобы установить теоретико-множественный смысл квантора общности, применим закон действия отрицания на квантор. Пусть

F (х) = у (Р) (х, у). Тогда (у) Р (х, у) = (ду) Р (х , у). Операции отрицания, как известно, соответствует теоретико-множественная операция дополнения. Отсюда Е Р ---= СпрхСЕр, т. е. множество, отвечающее функции (у) Р (х, у), есть дополнение к проекции на М дополнения к Ер. Справедливо и обратное положение: всякое мно­ жество R, являющееся проекцией на М множества V, принадлежа­

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

Если R' — дополнение к проекции V, то R' соответствует, оче­

видно, предикату (у) Р (х, у). В самом деле, предикату (у) Р (х, у) соответствует множество СпрхСЕ-, но СЕ- = Е = V, следова­

тельно, СпрхСЕ- = С xV, очевидно кванторы связаны с операцией

проектирования, а проектирование имеет указанный геометриче­ ский смысл.

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

Вопросы и задачи для самопроверки

1.Какие из следующих выражений можно рассматривать как предикаты при определенном выборе области изменения входящих в них переменных:

а) 5—3 = 2;

б) х включается в у,

в) х при делении на у дает остаток г?

2.Для каждого приведенного ниже высказывания найти предикат (одно­ местный или многоместный), который обращается в данное высказывание при замене предметных переменных некоторыми аргументами:

-а) конъюнкция, б) дизъюнкция, в) импликация, г) эквивалентность дан­ ных предикатов?

163

Л И Т Е Р А Т У Р А

Часть I

Главы первая, вторая, третья

1.К а р ц е в М. А. Арифметические устройства электронных цифровых машин. Физматгиз, 1968 г.

2.П а п е р н о в А. А. Логические основы цифровых машин и программи­ рования. Изд-во «Наука», 1965 г.

3.А. И. К и т о в , Н. А. К р и н и ц к и й. Электронные цифровые ма­

Часть И

Глава четвертая

1.П о с п е л о в Д. А. Логические методы анализа и синтеза схем. Изд-во

«Энергия», 1964.

2.Г о л ы ш е в Л. К- Структурная теория цифровых машин. М. «Энер­ гия», 1971.

3.К о л д у э л л С. Логический синтез релейных устройств. Пер. с англий­ ского под ред. М. А. Гаврилова И. Л ., 1962.

4.П а п е р н о в П. А. Логические основы ЦВТ. М. Изд-во «Советское радио», 1972.

Глава седьмая

1.Н о в и к о в П. С. Элементы математической логики. Физматгиз, 1959.

2.Г л у ш к о в В. М. Введение в кибернетику, 1964.

165

О Г Л А В Л Е Н И Е

166