Нормальные формы.Множество всех формул, в построении которых участвуют переменные высказывания, некоторые из символов &, Ъ,®, ~ , -и констант 0 и 1, называются языком над данными символами и константами. Равенства (1) - (7) показывают, что для всякой формулы в языке над &, Ъ,®, ~ , -,0, 1 найдётся равная ей формула в языке над &, Ъ, -,0, 1, например
Особую роль в последнем языке играет класс формул, которые могут быть записаны в виде Б
1ЪБ
2Ъ...ЪБ
s, 0 или 1, где
s³
1,и каждое Б
i- либо переменное высказывание, либо его отрицание, либо конъюнкция таковых, при этом каждое Б
iне содержит одинаковых сомножителей и не содержит сомножителей вида Х и
одновременно и все Б
i- попарно различны. Здесь скобки опускаются, т. к. предполагается, что операция конъюнкции связывает «сильнее», чем дизъюнкция, т. е. при вычислении по заданным значениям переменных следует сначала вычислить значения Б
i.Эти выражения называются дизъюнктивными нормальными формами (днф). Каждую формулу Б, реализующую функцию, отличную от константы, в языке над &, Ъ, ®, ~ ,
-, 0, 1 при помощи равенств (1) - (7) можно привести к равной ей днф, содержащей все переменные формулы Б и любое число других переменных, причем каждое Б в этой днф содержит одни и те же переменные. Такая днф называется совершенной днф формулы Б. Возможность приведения к совершенной днф лежит в основе алгоритма, устанавливающего равенство или неравенство двух наперёд заданных формул.
Важную роль в А. л. и её приложениях играет т. н. сокращённая днф. Днф называется сокращённой, если выполнены следующие условия: 1) в ней нет таких пар слагаемых Б iи Б j, что всякий сомножитель из Б iимеется и в Б I; 2) для всяких двух таких слагаемых Б iи Б i,из которых один содержит сомножителем некоторое переменное, а другой - отрицание этого переменного (при условии, что в данной паре слагаемых нет другого переменного, для которого это же имеет место), имеется (в этой же днф) слагаемое Б i, равное конъюнкции остальных сомножителей этих двух слагаемых. Всякая днф при помощи равенства (1) - (7) может быть приведена к равной ей сокращённой днф. Например, сокращённой днф для формулы ((X ~ (Y®Z)) ® (X&Z)) является
Кроме днф, употребляются также конъюнктивные нормальные формы (кнф). Так называют выражения, которые можно получить из днф путём замены в них знаков Ъ на &, а & на Ъ. Например, из днф
получается кнф
Операция (или функция) f называется двойственной для операции y, если таблица, задающая f получается из таблицы, задающей y, путём замены в ней всюду 0 на 1 и 1 на 0 (включая замену значений функций). Например, конъюнкция и дизъюнкция двойственны между собой, отрицание двойственно самому себе, константы 1 и 0 двойственны друг другу и т. д. Преобразованием формул, при котором знаки всех операций в выражении заменяются на знаки двойственных им операций, константа 0 заменяется на 1, а 1 - на 0, называются преобразованием двойственности. Если верно равенство Б = В и Б* двойственно Б, а В* двойственно В ,то верно Б* = В*, называемое двойственным предыдущему. Это т. н. принцип двойственности. Примерами двойственных равенств являются пары законов (1), (2), (3); равенство (5) двойственно равенству (6), каждая кнф двойственна некоторой днф. Совершенная кнф и сокращённая кнф определяются как такие кнф, что двойственные им выражения являются соответственно совершенной днф и сокращённой днф.
Следствия. Гипотезы. Минимизация.Совершенные и сокращённые днф и кнф используются для решения задачи обзора всех гипотез и всех следствий заданной формулы. Под гипотезой формулы Б понимается такая формула В, что (В®Б) =1, а под следствием формулы Б - такая формула В, что (Б®В) = 1. Гипотеза формулы Б называется простой, если она есть конъюнкция переменных или их отрицаний и после отбрасывания любого из её сомножителей перестаёт быть гипотезой формулы Б. Аналогично, следствие формулы называется простым, если оно есть дизъюнкция переменных или их отрицаний и после отбрасывания любого из её слагаемых перестаёт быть следствием формулы Б. Решение задачи обзора гипотез и следствий основано на указании алгоритма, строящего все простые гипотезы и следствия для заданной формулы и в получении из них при помощи законов (2) - (7) всех остальных гипотез и следствий.
Сокращённая днф имеет важные приложения. Следует отметить прежде всего задачу минимизации функций А. л., являющуюся частью т. н. задачи синтеза управляющих систем. Минимизация функций А. л. состоит в построении такой днф для заданной функции А. л., которая реализует эту функцию и имеет наименьшее суммарное число сомножителей в своих слагаемых, т. е. имеет минимальную «сложность». Такие днф называются минимальными. Каждая минимальная днф для заданной отличной от константы функции А. л. получается из сокращённой днф любой формулы, реализующей эту функцию, выбрасыванием некоторых слагаемых Б i, из этой сокращённой днф.
Языки. Интерпретации.В языке над &, Ъ, ®, ~, 0, 1, + , где знак + интерпретируется как сложение по модулю два, устанавливаются следующие соотношения:
Эти равенства позволяют переводить формулы в языке над &, Ъ, ®, ~, -, 0, 1 в равные им формулы в языке над &,+, 1 и обратно. Тождественные преобразования в последнем языке осуществляются при помощи равенств, установленных для конъюнкции и дополнительных:
(11) Х +Y=Y+ X;
(12) (Х+Y) + Z = Х+(Y + Z);
(13) Х&(Y + Z) = X&Y + X&Z;
(14) Х&Х = Х, X + (Y + Y) =X, X&1 = X,
здесь по-прежнему считается, что конъюнкция связывает «сильнее», чем знак +. Этих равенств достаточно для того, чтобы из них при помощи тождественных преобразований, так же как и при рассмотрении языка над &, Ъ, ®, ~, -, 0, 1, можно было вывести любое верное равенство в языке над &, +, 1. Выражение в этом языке называется приведённым полиномом (п.п.), если оно либо имеет вид Б 1+Б 2+ ... Б s, где каждое Б iесть или 1, или переменное, или конъюнкция различных переменных без отрицаний, Б i¹Б jпри i¹ j и s³1, либо равно 1 + 1. Например, выражение XYZ + XY+1 является п. п. Всякую формулу А. л. можно привести к п. п.
Кроме рассмотренных языков, существуют и др. языки, равносильные им (два языка называются равносильными, если при помощи некоторых правил преобразования каждая формула одного из этих языков переводится в некоторую равную ей формулу в другом языке и обратно). В основу такого языка достаточно положить любую систему операций (и констант), обладающую тем свойством, что через операции (и константы) этой системы можно представить всякую функцию А. л. Такие системы называются функционально полными. Примерами полных систем являются
и т. п. Существует ,который по произвольной конечной системе функций А. л. устанавливает её полноту или неполноту. Рассматриваются и такие языки, в основе которых лежат системы операций, не являющихся функционально полными, и таких языков бесконечно много. Среди них имеется бесконечно много попарно неравносильных языков (в смысле отсутствия переводимости при помощи тождественных преобразований с одного языка на другой). Однако для всякого языка, построенного на основе тех или иных операций А. л., существует такая конечная система равенств этого языка, что всякое равенство этого языка выводимо при помощи тождественных преобразований из равенств этой системы. Такая система равенств называется дедуктивно полной системой равенств (п. с. р.) языка.
Рассматривая тот или иной из упомянутых выше языков вместе с некоторой п. с. р. этого языка, иногда отвлекаются от табличного задания операций, лежащих в основе этого языка, и от того, что значениями его переменных являются высказывания. Вместо этого допускаются различные интерпретации языка, состоящие из той или иной совокупности объектов (служащих значениями переменных) и системы операций над объектами этого множества, удовлетворяющих равенствам из п. с. р. этого языка. Так, язык над &, Ъ, -, 0, 1 в результате такого шага превращается в язык т. н. булевой алгебры, язык над &, +, 1 превращается в язык т. н. булевого кольца (с единицей), язык над &, Ъ в язык дистрибутивной структуры и т. п.
А. л. развивается главным образом под влиянием задач, встающих в области её приложений. Из них самую важную роль играют приложения А. л. в теории электрических схем. Для описания последних в некоторых случаях приходится отказываться от пользования лишь обычной двузначной А. л. и рассматривать те или иные её многозначные обобщения (см. ) .
Лит.:Гильберт Д. и Аккерман Б., Основы теоретической логики, пер. с нем., М., 1947; Тарский А., Введение в логику и методологию дедуктивных наук, пер. с англ., М., 1948; Клини С. К., Введение в метаматематику, пер. с англ., М., 1957; Новиков П. С., Элементы математической логики, М., 1959.
В. Б. Кудрявцев.
Алгебраическая геометрия
Алгебраи'ческая геоме'трия,раздел математики, изучающий алгебраические многообразия. Так называются множества точек в n-мерном пространстве, координаты которых (x 1, x 2,...,x n) являются решениями системы уравнений:
F 1(X 1, Х 2..., X n) = 0,
F m(X 1, x 2, ..., X n) = 0,
где F i,..., F m -многочлены от неизвестных x 1, ..., x n. Каждое алгебраическое многообразие имеет определённую размерность,которая является числом независимых параметров, определяющих точку на многообразии. Алгебраические многообразия, имеющие размерность 1, называются алгебраическими кривыми, имеющие размерность 2 - алгебраическими поверхностями. Примерами алгебраических кривых могут служить .
Два алгебраических многообразия называются бирационально эквивалентными, если координаты каждой точки одного многообразия выражаются при помощи рациональных функций через координаты точки другого многообразия, и наоборот. В А. г. алгебраические многообразия обычно изучаются с точностью до бирациональной эквивалентности, поэтому одной из основных задач А. г. является построение бирациональных инвариантов для алгебраических многообразий. Наиболее важные из известных бирациональных инвариантов строятся с помощью средств математического анализа (т. н. трансцендентных методов), в особенности при помощи кратных интегралов по алгебраическому многообразию. Кроме трансцендентных методов, в А. г. часто применяются геометрические методы ,а также топологические методы (см. ) .Последнее вызвано тем, что некоторые важные бирациональные инварианты, например род кривой (см. ниже), алгебраических многообразий носят топологический характер. Особенно большую роль играет связь А. г. с топологией в свете теоремы японского математика Хиронака, согласно которой всякое алгебраическое многообразие бирационально эквивалентно многообразию, не имеющему особых точек.
Наиболее разработанная часть А. г. - теория алгебраических кривых. Основным бирациональным инвариантом алгебраической кривой является её род. Если алгебраическая кривая плоская, т. е. задаётся в декартовых координатах уравнением F(х, у) = 0, то род кривой g = (m - 1)(m - 2)/2 - d, где m -порядок кривой, а d -число её двойных точек. Род кривой всегда есть целое неотрицательное число. Кривые рода нуль бирационально эквивалентны прямым, т. е. параметрически могут быть заданы при помощи рациональных выражений. Кривые рода 1 могут быть параметризованы и поэтому называются эллиптическими кривыми. Кривые рода больше 1 могут быть параметризованы с помощью .Каждая кривая рода g ,большего 1, с точностью до бирациональной эквивалентности однозначно определяется 3g - 3 комплексными параметрами, которые сами пробегают некоторое алгебраическое многообразие.
В многомерном случае наиболее изученный класс алгебраических многообразий образуют абелевы многообразия. Это - замкнутые подмногообразия проективного пространства, являющиеся одновременно ,причём так, что умножение задаётся рациональными выражениями. Умножение на таком многообразии автоматически оказывается коммутативным. Алгебраическая кривая является абелевым многообразием тогда и только тогда, когда она имеет род 1, т. е. является эллиптической кривой.
Теория алгебраических кривых и теория абелевых многообразий тесно связаны между собой. Всякая алгебраическая кривая рода, большего 0, канонически погружается в некоторое абелево многообразие, называемое якобиевым многообразием для данной кривой. Якобиево многообразие является важным инвариантом кривой и почти полностью определяет самоё кривую.
Исторически А. г. возникла из изучения кривых и поверхностей низких порядков. Классификация кривых третьего порядка была дана И. Ньютоном (1704). В 19 в. А. г. постепенно переходит от изучения специальных классов кривых и поверхностей к постановке общих проблем, относящихся ко всем многообразиям. Общая А. г. была построена в конце 19 и начале 20 вв. в трудах немецкого математика М. Нётера, итальянских математиков Ф. Энрикеса, Ф. Севери и др. Своего расцвета А. г. достигает в 20 в. (работы французского математика А. Вейля, американского математика С. Лефшеца и др.). Крупные достижения в А. г. имеют советские математики Н. Г. ,И. Г. ,И. Р. .
А. г. является одним из наиболее интенсивно развивающихся разделов математики. Методы А. г. оказывают огромное влияние на такие смежные с А. г. разделы математики, как теория функций многих комплексных переменных, теория чисел, а также на более далёкие от А. г. разделы математики - такие, как уравнения в частных производных, алгебраическая топология, теория групп и др.
Лит.:Ван-дер-Варден Б. Л., Современная алгебра, пер. с нем., [2 изд.], ч. 1-2, М. - Л., 1947; Чеботарев Н. Г., Теория алгебраических функций, М. - Л., 1948; Ходж В., Пидо Д., Методы алгебраической геометрии, пер. с англ., т. 1-3, М., 1954 - 55; Алгебраические поверхности, М., 1965; WeiI A.. Foundations of algebraic gйometry, N. Y., 1946.
Б. Б. Венков.
Алгебраическая кривая
Алгебраи'ческая крива'я,кривая, задаваемая в декартовых координатах алгебраическим уравнением. См. .
Алгебраическая поверхность
Алгебраи'ческая пове'рхность,поверхность, задаваемая в декартовых координатах алгебраическим уравнением. См. .
Алгебраическая функция
Алгебраи'ческая фу'нкция,функция, удовлетворяющая .А. ф. принадлежат к числу важнейших функций, изучаемых в математике. Из них многочлены и частные многочленов [например,
называются рациональными, а прочие А. ф. - иррациональными. Простейшими примерами последних могут служить А. ф., выражаемые с помощью радикалов [например,
Однако существуют А. ф., которые невозможно выразить через радикалы [например, функция у= f( х), удовлетворяющая уравнению: y 5+ 3 ух 4+ x 5= 0]. Примерами неалгебраических, т. н. , встречающихся в школьном курсе алгебры, являются: степенная x a(если a -иррациональное число), показательная а х ,логарифмическая и т. д. Общая теория А. ф. представляет обширную математическую дисциплину, имеющую важные связи с теорией (А. ф. составляют специальный класс аналитических функций), алгеброй и .Самая общая А. ф. многих переменных u= f( x, у, z, ...) определяется как функция, удовлетворяющая уравнению вида:
Р о( х, у, z, ...) u n+ P 1( x, y, z, ...) u n-1+ … + P n( x, y, z, ...) = 0, (1)
где Р 0, Р 1, ..., P n -какие-либо многочлены относительно х, у, z,... . Всё выражение, стоящее в левой части, представляет некоторый многочлен относительно х, у, z,... и n. Его можно считать неприводимым, т. е. не разлагающимся в произведение многочленов более низких степеней; кроме того, многочлен P 0можно считать не равным тождественно нулю. Если n= 1, то u представляет рациональную функцию ( u= - P 1/ P 0), частным случаем которой - целой рациональной функцией - является многочлен (если P 0= const ¹ 0). При n> 1 получается иррациональная функция; если n= 2, то она выражается через многочлены с помощью квадратного корня; если n= 3 или n= 4, то для u получается выражение, содержащее квадратные и кубические корни.
При n ³ 5 число каких бы то ни было корней из многочленов. Иррациональная А. ф. всегда многозначна, а именно (при наших обозначениях и предположениях) является n-значной аналитической функцией переменных х, у, z,...
Лит.:Чеботарев Н. Г., Теория алгебраических функций, М. - Л., 1948.
Алгебраическое выражение
Алгебраи'ческое выраже'ние,выражение, составленное из букв и цифр, соединённых знаками действий сложения, вычитания, умножения, деления, возведения в целую степень и извлечения корня (показатели степени и корня должны быть постоянными числами). А. в. называется рациональным относительно некоторых букв, в него входящих, если оно не содержит их под знаком извлечения корня, например
рационально относительно a, b и с. А. в. называется целым относительно некоторых букв, если оно не содержит деления на выражения, содержащие эти буквы, например 3а/с + bc 2- 3ас/4 является целым относительно а и b. Если некоторые из букв (или все) считать переменными, то А. в. есть .
Алгебраическое дополнение
Алгебраи'ческое дополне'ние,см. в ст. .
Алгебраическое уравнение
Алгебраи'ческое уравне'ние,уравнение, получающееся при приравнивании двух .А. у. с одним неизвестным называется дробным, если неизвестное входит в знаменатель, и иррациональным, если неизвестное входит под знаком радикала. Всякое А. у. может быть преобразовано без потери корней к виду a 0x n+ a 1x n-1+ ... + a n= 0. О решении таких уравнений см. и .
Д. К. Фаддеев.
Алгебраическое число
Алгебраи'ческое число',число а, удовлетворяющее алгебраическому уравнению a 1a n+ ... + акa +a n+1= 0, где n ³ 1, a 1, ..., a n, a n+1- целые (рациональные) числа. Число a называется целым А. ч., если a 1= 1. Если многочлен f(x) = a 1x n+ ... + a nx + a n+1не является произведением двух др. многочленов положительной степени с рациональными коэффициентом, то число n называется степенью А. ч. a. Простейшие А.ч. - корни двучленного уравнения x n= а, где а -рациональное число. Например, А. ч. будут рациональные числа, числа
целыми А. ч. будут целые числа, числа
С понятием А. ч. тесно связаны два больших направления в теории чисел. 1) Арифметика А. ч. (алгебраическая теория чисел), созданная Э. в середине 19 в., изучает свойства А. ч. Целые А. ч. обладают рядом свойств, аналогичных свойствам целых рациональных чисел, однако теорема об единственности разложения числа на простые множители не имеет места в теории целых А. ч. Для сохранения единственности разложения Куммер ввёл в рассмотрение т. н. «идеальные» числа (см. ) .2) Теория приближения А. ч. изучает степень приближения А. ч. рациональными числами или алгебраическими же числами. Первым результатом в этом направлении была теорема Ж. ,показывающая, что А. ч. «плохо» приближаются рациональными числами, точнее: если a - А. ч. степени n ,то при любых целых рациональных р и q имеет место неравенство [a - p/q] > C/q n, где С = С(a) > 0 - постоянная, не зависящая от р и q, отсюда следует, что легко построить произвольное количество неалгебраических - .
Лит.:Гекке Э., Лекции по теории алгебраических чисел, пер. с нем., М. - Л., 1940; Гельфонд А. О., Трансцендентные и алгебраические числа, М., 1952; Боревич З. И., Шафаревич И. P., Теория чисел, М., 1964.
А. А. Карацуба.
Алгебры основная теорема
А'лгебры Основна'я теоре'ма,название теоремы о существовании комплексных корней алгебраического уравнения a 0x n+ a 1x n-1+ ... +a n= 0 с комплексными коэффициентами. См. .
Алгол
Алго'л,сокращённое название ряда .Образовано из начальных букв английских слов algorithmic (алгоритмический) и language (язык). Разработан группой учёных разных стран в 1958-60. Окончательный вид языка, принятый на международной конференции в Париже (январь 1960), получил название «Алгол-60» (в отличие от первоначального вида, названного «Алгол-58»).
Основными символами А. являются десятичные цифры, строчные и заглавные латинские буквы, знаки препинания, знаки математических и логических операций, прочие специальные знаки и некоторые английские слова (в частности, begin и end). Из основных символов в А. по определённым правилам образуются конструкции - числа и выражения (арифметические, логические и др.), описания, примечания и ,которые, в свою очередь, в сочетании с основными символами образуют более сложные операторы и т. д. Алгоритм, заданный на А., называется алгол-программой. С помощью специальной программы он преобразуется в программу на языке конкретной цифровой вычислительной машины.
Лит.:Алгоритмический язык АЛГОЛ-60, пер. с англ., М., 1965; Лавров С. С., Универсальный язык программирования (АЛГОЛ-60), 2 изд., М., 1967.
Алголь
Алго'ль,b Персея, затменная переменная звезда, переменность которой открыта в 1669. Блеск А. изменяется от 2,2 до 3,5 визуальной звёздной величины с периодом 2,867 суток. Расстояние от Солнца - 36 парсек. Переменные звёзды с кривой изменения блеска, как у А., составляют класс звёзд типа Алголя.
Алгонкинские языки
Алгонки'нские языки',одна из основных семей языков североамериканских индейцев. В результате истребления племён А. я. сохранились лишь в немногих местах в США и Канаде, главным образом в районе Великих озёр и южнее. Распадаются на 5 основных групп: языки т. н. «черноногих» индейцев; чейенн; арапахо; центральная и восточная группы; калифорнийская группа. Наиболее обширны центральная и восточная группы, к которым относятся языки собственно алгонкинский, оджибве, оттава (в районе озера Верхнего и Гурон), кри (на Лабрадоре), делаварский (в Пенсильвании и в штатах Нью-Йорк и Нью-Джерси), фокс (долина Миссисипи), а также ныне исчезнувшие языки могикан, массачусетский и др. Языки т. н. «черноногих» индейцев (блэкфут) распространены в Канаде, у подножия Скалистых гор и в северной части Монтаны; шейен - в юго-восточной части Миннесоты и северо-восточной части Южной Дакоты; арапахо - в восточной части Северной Дакоты и в южной части Монтаны; калифорнийская группа (Калифорния) представлена двумя языками - вийот и юрок. В грамматическом отношении А. я. характеризуются ярко выраженной инкорпорацией (см. ) .В А. я. элементы, соответствующие второстепенным членам предложения, зависящие от глагольного сказуемого, входят в состав последнего как морфы, в результате чего одна словоформа соответствует целому предложению.
Лит.:Boas Fr., Handbook of American Indian languages, pt I, Wash., 1911: Pilling J. С., Bibliography of the Algonquian languages. Wash., 1891.
Алгонкины
Алгонки'ны,группа родственных по языку (см. ) индейских племен, древнейших насельников Северной Америки, охотников, рыболовов и ранних земледельцев, живших в прошлом на большом пространстве от Атлантического побережья до Скалистых гор. Территориально различаются 4 группы А.: северо-восточная ( ,монтанье, ,микмаки и др.); приатлантическая (абенаки, наррагансеты, массачусеты, поухатаны и др.), почти полностью уничтоженная на первых же этапах колонизации материка европейцами: центральная ( , ,майами, иллинойсы, оттавы, , , собственно алгонкины, и др.), оставившая о себе память в топонимике; западная («черноногие»,