Колмогоров, Драгалин - Введение в математическую логику (947386), страница 22
Текст из файла (страница 22)
В случае интерпретируемости Т1 в Т, всякая модель Тэ порождает некоторую модель для Ть Таким образом, теория моделей Тэ позволяет судить о моделях теории Т,. 6. Для каждого натурального п)О определим теорию Е, — элементарную теорию векторного пространства размерности и. Это теория в языке Чес1. Нелогнческие аксиомы Е„распадаются на две группы, Первая группа — это просто аксиомы ц, относяшиеся к переменным х, у, г, ..., фоРму- 113 лам н термам Вх, х+у, х у, Оь х,=у.
Вторая группа — зна- комые аксиомы линейного пространства: 1) а+О~=а; 2) р+Ь=Ь+а; 3) (а+Ь)+с=а+ (Ь+с); 4) Я Ь(а+Ь=О~); 5) х (а+Ь) =х а+х.Ь; (х+у) а=х а+у а; 6) х (у а) = (х у) . а; 7) а 50=а; ' 6) ~а, ... а„~х1 ... х„(х1 а1+ ... +х,.а„= =01-эх~ =ОоЛ ". Лхв=Оо) ' 9) 7'а,.:.а.+, 3х, ... х.+,((х1ФОо~/ хо~Оо~/ .. ~/х.+~ФОо) Лх1 а1+ ... +х.,| а„+, — — 0,) .
Последние две аксиомы как раз выражают то обстоя- тельство, что размерность подразумеваемого пространства равна и. Естественной моделью теории Е, является н-мерное ли- нейное векторное пространство над полем вещественных чи- сел, Известно, что теория Е, полна и разрешима. 7. Теоретико-множественные надстройки элементарных теорий определяются однотипным образом.
Например, ариф- метика второго порядка Аг2 есть теория в языке Аг2, содер- жащая те же нелогические аксиомы, что н фг с той, однако, разницей, что в схеме аксиом индукции в качестве формулы А(х) можно брать теперь любую формулу полного языка Аг2. Кроме того, в число нелогических аксиом зачисляется схема аксиом свертывания: ДХ)ух (хеБХ= А (х) ), где Х не входит свободно в А (х).
Теоретико-множественная надстройка сразу сильно рас- ширяет выразительные возможности теории. Так, в теории Й2 интерпретируется теория Аг2. В отличие от К теория Я2 уже неполна и неразрешима. 8. Читатель может попробовать свои силы в формализа- ции математических теорий, самостоятельно определив фор- мальную аксиоматическую теорию — элементарную геомет- рию плоскости в стиле аксиоматики Гильберта. При естест- венной формаяизацни оказывается, что полученная теория будет полной и разрешимой.
Для облегчения этой работы наметим построение языка. В элементарной геометрии плоскости два сорта переменных: А, В, С, ... для:точек. а, Ь, с, ... для прямых. 114 Атомарные формулы теории могут выглядеть следующим образом: А= — «точка А совпадает с точкой В», а=Ь вЂ” «прямая а совпадает с прямой в», А~а — «точка А лежит на прямой а», (АВС] — «А, В, С вЂ” три различные точки, лежащие на одной прямой так, что точка В лежит между А и С».
Р(А, В, С, О) — «А~В, СФ0 и отрезки АВ и С0 конгруэнтны.» Наглядно эту формулу можно записывать в виде АВ=С0. Я(А, В, С, Аь Вь С1) — «А, В, С вЂ” три различные точки, не лежащие на одной прямой, равно как и Аь Вь Сь причем угол АВС равен углу А1В,С1». Наглядно эту формулу записывают в виде 4АВСж к А1В~Сь В этом языке можно естественно записать все аксиомы геометрии в аксиоматике Гильберта, кроме аксиомы Архи- меда и аксиомы непрерывности, Рассмотрим, например, сле- дующую аксиому Паша; Пусть А, В, С' — три точки, не лежащие на одной пря- мой, и а — прямая, не'проходящая ни через одну из точек А, В, С; если при этом прямая а проходит через одну из то- чек отрезка АВ, то она должна пройти через одну из точек отрезка АС илн через одну из точек отрезка ВС.
Ее символическая запись в пашен языке: Н Ь(А'~ЬЛВепЬЛСевЬ) ЛАМ аМ В4 аЛСЯаЛ ~0(0~а~4А0В)) ~ ~ Е (Е~аЛ ((АЕС74(ВЕС1) ). Именно соответствующая теория (без аксиомы Архимеда и ' аксиомы, непрерывности) и называется элементарной гео- метрией плоскости. Для формулировки двух последних упо- мянутых аксиом уже требуется надстройка языка теоретико- множественными средствами и средствами арифметики. Возникающая при этом теория — теория второго порядка геометрии плоскости — уже не является' ни полной, ни раз- решимой, но обладает гораздо большими выразительнымн возмажностями.
ать "Приложение 1 КОДИРОВАНИЕ С ИСПРАВЛЕНИЕМ ОШИБОК Интересным применением булевых колец является составление кодов с исправлением ошибок. Здесь мы излагаем начала теории кодов Хемминга, позволяющих исправлять одну ошибку. Подлежащая передаче информация состоит из двоичных слов У='У~Уз ... У» длины А. Они кодируются «кодовыми словами» Х=Х1ХЗ ... Х длины л~д. Предполагается, что вместо поданного отправителем кодового слова х получатель может принять слово х', отличающееся от х не более чем в одном знаке. При каких й.и й кодовые слова в числе 2" могут быть выбраны так, что по х' можно будет безошибочно восстановить х (а значит, и р) р Со словами длины и будем обращаться как с элементами кольца Р".
Введем норму ~~х1~, равную числу единиц в х, и будем считать величину 1~х+ х'11 расстоянием между элементами х и х'. Ясно, что наше требование будет выполнено, если расстояние между двумя кодовыми словами будет не менее трех, т. е. сферй радиуса единица с центрами в кодовых словах не будут пересекаться. Такие сферы в 0" имеют по л+1 элементов. Поэтому должно быть 2ь (и+1) ~2", При л=2'" — 1, 1=2 — гл — 1=п — т имеем равенство 2» (л+ 1) 2~ Хемминг показал, что при этих Аг и и поставленные задачи разрешимы.
116 Индексы хо 1«г „2 букв кодовых слов будем записывать по двоичной системе счисления г=11 ...1,„, где хотя бы' один знак й отличен от нуля. Вместо х, с г=1~ ...1 будем писать х. по..л Подчиним буквы ко)ювых слов х линейным условиям г,= '~~ х„.з =О, 1=1...,, лт. ' (а) Из теории линейных уравнений (примененной к случаю полн. О) вытекает, что п — т переменным х, можно с соблюдением этих условий придать произвольные значения.
Таким образом, получим 2"-'"=2' кодовых слов, удовлетворяющих условиям ('). Если слово х' отличается от х в знаке хл„з 1 при 1, =1, 0 при 1,=0. Это позволяет получателю найти и исправить ошибочную букву. Эффективность простейших кодов Хемминга показывает табличка т 2 3 4 5 й 1 4 11 27 и 3 7 15 31 При л=3 можно выбрать два кодовых слова 000 и 111. Для понимания механизма действия изложенной теории по- лезно выписать 16 кодовых слов длины 7. *Приложение 2 ПРИМЕНЕНИЯ К КОНТАКТНЫМ СХЕМАМ На рис. 2а изображена схема с шестью узлами и восемью контактами.
Поступающие на схему сигналы х, у и г принимают значения О и 1. Если и=1, то контакт, обозначенный и, замыкается (пропускает ток)с а контакт, обозначенный й, размыкается. Если и=О, то, напротив, считается замкнутым контакт й, контакт же й оказывается разомкнутым. Легко понять, что схема рис. 2а пропускает ток из узла 1 в узел 2 в том и только в том случае, если сигналы х, у, г удовлетворяют условию хуе() хунхуа() худ = 1, х+у+е=!. т.
е. о -у'-е — у о Рис. 2 1)8 Схемы такого типа с двумя выделенными узлами (на рис. 2а зто узлы 1 и 2) называются двухполюсными релейными схемами, или просто двухпоппюсниками. Каждый двухполюсник, на который подается и-сигналов хь ..., х„определяет некоторую булеву функцию ((хь ..., х,) от подаваемых сигналов. Эта функция называется функцией проводимости двухполюсника. Они описывает; при каких наборах входных сигналов ток проходит из одйого выделенного узла в другой. Из двухполюсников можно конструировать новые двухполюсники прн помощи параллельных (рис.
2б) и последовательных (рис. 2в) соединений. Так как. всякая булева функция представима в конъюнктив- ной и дизъюнктивной нормальной формах, то отсюда следу- ет, что этими двумя приемамн можно построить двухполюс- ник с любой наперед заданной проводимостью.
Однако .этот метод построения двухполюсников — далеко. не всегда самый экономичный. Так, на рис. 2,а указан двух- полюсник с проводимостью х+у+г, содержащий восемь кон- тактов. Мы воспользовались при этом «мостиковой» схемой, которую нельзя получить, итерируя последовательные и па- раллельные соединения элементов двухполюсников. Пусть дан двухполюсник с т узлами. Если даны значе-.
ния всех входных сигналов, то для -каждой пары узлов ! и 1 опредерено значение непосредственной проводимости ац, равное нулю нли единице. А именно ац= 1, если 1 и 1 соеди- нены контактом с проводимостью 1. Если ! и 1 не соединены, то мы считаем ац=О.
Всегда ач=! и ац=ан. Если заданы все,непосредственные проводимости ац, то. существует универсальный метод вычисления по ним «окон- чательных проводимостей» бц. Мы полагаем Ьц=! тогда и только тогда, когда ток проходит из узла 1 в узел ! при данном наборе значений сигналов. Для этого можно воспользоваться булевым умножением матриц: !)Сц!1= !!ац!!.!!йц!!, где сц=ацйц0а(»й»й ..1)ась~~ Для такого умножения матриц справедлива теорема: для любой матрицы А порядка т ее степени начиная с (т — 1)-й совпадают: А -1=А =А'"+'= ... =А". «Окончательная» степень А" матрицы непосредственных проводимостей и есть матрица окончательных проводимостей между узлами.
ЛИТБРЛТУРЛ 1. Кл и ни С. К. Введение в метаматематику. — Мл ИЛ, 1957. 2. Клики С. К. Математическая логика. — Мл Мир, 1973. 3. Мендельсон Э. Введение в математическую логику. — Мл Наука, 1971. 4. Шеи филд Дж. Математическая логика. — Мл Наука, 1975. 5. Гуде тейп Р. Л. Математическая логика. — Мл ИЛ, 1961. б. Гильберт Д., Бернайс П.
Основания математики, т. 1, 2, Мл Наука, 1979, 1982. 7. Новиков П. С. Элементы математической логики. — Мл Физматгиа, 1959. 8. Бурбаки Н. Теория множеств. — Мл Мнр, 1965. 9. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгорифмов.— Мл Наука, 1975. .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
