Реферат: Краткая методичка по логике

Постраничныйперечень понятий и теорем.

 

Логика.Язык. Высказывание. Истинное высказывание. Ложное высказывание. Истина. Ложь.Обозначение для истины. Обозначение для лжи. Истинностное значение высказывания.Равносильные высказывания. Синонимы для истинного высказывания. Доказательство.Правило вывода. Обозначение для конструктивного правила. Компонентыконструктивного правила. Посылки конструктивного правила. Заключение конструктивногоправила. Индуктивная последовательность объектов. Правила порождения индуктивнойпоследовательности. Формальный язык. Логические знаки. Вспомогательные знаки.n-местные функциональные знаки. n-местные предикатные знаки. Переменные. Алфавитныйпорядок знаков. Выражение. Синонимы для выражения. Обозначения для нульместныхфункциональных знаков. Обозначения для функциональных знаков. Обозначения дляпредикатных знаков. Обозначения для выражений. Обозначения для переменных.Обозначение для соединения выражений. Терм. Правила порождения термов. Обозначениядля термов. Индуктивная последовательность термов.

Высказывание.Синонимы для высказывания. Правила порождения высказываний. Индуктивнаяпоследовательность высказываний. Обозначения для высказываний. Соглашения обупразднении скобок. Константа. Квантор всеобщности. Квантор существования.Предикат. Элементарное высказывание. Компонента высказывания. Синоним для компонентывысказывания. Пропозициональная компонента высказывания. Интерпретацияформального языка. Универсум интерпретации. Синоним для универсума. Значение переменной.Значение функционального знака. Значение предикатного знака. Значение терма.Значение высказывания. Денотаты термов и высказываний. Индуктивное определениезначения терма. Индуктивное определение значения высказывания. Обобщение высказыванияпо данной переменной. Синонимы для выражения обобщения. Подтверждение высказыванияпо данной переменной. Синонимы для выражения подтверждения. Отрицание высказывания.Синонимы для выражения отрицания. Конъюнкция высказываний.

Конъюнкты.Синонимы для выражения конъюнкции. Дизъюнкция высказываний. Дизъюнкты. Синонимыдля выражения дизъюнкции. Импликация высказываний. Посылка импликации.Заключение импликации. Синонимы для выражения импликации. Эквиваленциявысказываний. Левая и правая части эквиваленции. Синонимы для выражения эквиваленции.

Замечаниео языковой смеси. Замечание об использовании знака равенства для высказываний.Пропозициональная логика. Синоним для пропозициональной логики. Логические(пропозициональные) операции. Истинностная таблица высказываний. Входные и результирующиестолбцы истинностной таблицы. Тавтология и ее синоним. Тавтологическоеследствие. Теорема об отрицании отрицания. Теорема об отрицании конъюнкции.Теорема об отрицании дизъюнкции. Теорема об исключении импликации. Теорема об исключенииэквиваленции. Теорема об устранении альтернативы. Теорема о коммутативности…Теорема о равносильности. Теорема о тавтологическом следствии. Арифметическаязапись высказываний. 12 равенств. Правило отделения. Теорема о выводе впропозициональной логике. Теорема о самодостаточной выразительностипропозициональной логики.

Кванторнаялогика. Синоним для кванторной логики. Кванторные операции. Кванторологическиистинное высказывание. Кванторологическое следствие. Связанное вхождениепеременной. Свободное вхождение переменной. Результат подстановки в высказываниетерма вместо переменной и его обозначение. Допустимый заменитель. Замкнутоевысказывание. Открытое высказывание.

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

Эгалитарнаялогика. Синоним для эгалитарной логики. Эгалитарная интерпретация. Логическоеследствие. Обозначение для логического следствия. Логически истинноевысказывание. Обозначение для логически истинного высказывания. Правилотождества. Правило равенства. Правило неотличимости. Теорема об эгалитарнойзамене. Теорема о транзитивности логического следствия. Теорема о расширениисписка гипотез. Теорема о конъюнктивизации гипотез. Теорема дедукции. Теорема овыводе в эгалитарной логике. Теорема о сравнительной силе выводов. Алгоритм.Теорема о неразрешимости проблемы логического следствия. Теорема о неразрешимостипроблемы логической истинности. Замечание о слове ЛОГИКА.

Формальныетеории. Аксиомы формальной теории. Теоремы формальной теории. Доказательныйтекст. Девять основных правил вывода.

Способыкомпактизации доказательных текстов. Операционная форма записи для двухместныхфункциональных и предикатных знаков. Соглашение об упразднении скобок.Соглашение о сравнительной силе связи логических и нелогических знаков. Специальныеначертания знаков. Знаковые фигуры.

Определяющаяаксиома для нового предикатного знака. Определяющая аксиома для нового функциональногознака. Теорема об определениях. Правило отделения конъюнкта. Правилоприсоединения дизъюнкта. Теорема о методе от противного. Формальная арифметика.Определяющие аксиомы для 2 3 4 5 > ≤ ≥≠.

Множество.Элемент множества. ХÎА. ХÏА.Подмножество. АÌВ. AËB.{аôр}.Пустое множество и его обозначение. {Х1,… Хn,}.Объединение двух множеств и его обозначение. Пересечение двух множеств и егообозначение. Дополнение множества В относительно множества А, его обозначение исиноним. Обозначение для множества натуральных, целых и действительных чисел.Упорядоченная n-ка, ее обозначение и синонимы. k-ая компонента упорядоченногонабора, ее обозначение и синоним. Декартово произведение множеств и егообозначение. К-ая проекция n-мерного множества и ее обозначение Аn.

Функция.Область определения функции, ее синоним и обозначение. Область значенийфункции, ее синоним и обозначение. Значение функции F в х и его обозначение. Образмножества относительно функции и его обозначение.

Отображениемножества в множество. Отображение множества на множество. F:А ®В. Сужение функции. Расширение функции. Обратная функция. Симметричность понятияобратной функции. n-аргументная функция. Обозначение F ((Х1,…., Хn)).Однозначная функция. Многозначная функция. Взаимнооднозначная функция и еесиноним. Последовательность. n-ый член последовательности. Бесконечноемножество. Конечное множество.

Тема1. Предмет и основные понятия логики.

 

Логика- наука о мышлении, наука о языковом выражении мыслей. Язык — знаковая система,предназначенная для фиксации, передачи и переработки информации. Высказывание — языковое выражение, о котором представляется естественным спросить, истинно оноили ложно. Высказывание является истинным, если его содержание соответствуетдействительности; в противном случае высказывание является ложным. Т. о. любоевысказывание является либо истинным либо ложным и тем самым служит обозначениемлибо истины либо лжи, которые мы можем рассматривать как два различныхумозрительных объекта, обозначаемых обычно буквами И, Л и называемыхистинностными значениями высказываний: И есть истинностное значение истинноговысказывания, Л есть истинностное значение ложного высказывания. Высказывания содинаковыми истинностными значениями называются равносильными. Про истинноевысказывание говорят, что оно справедливо, верно, имеет место. Доказательствомназывается конечная последовательность высказываний, в которой каждоевысказывание получается из некоторых предыдущих по какому-либо правилу вывода.Правила вывода — это конструктивные операции над высказываниями, сохраняющиесвойство истинности, т. е. такие операции, в результате которых из истинныхвысказываний получаются истинные высказывания. Конструктивное правилопреобразования объектов u1,..,un-1в объект unбудем записывать в виде Du1,....,un.При этом u1,....,unназываются компонентами, последняя из которых называется заключением, аостальные посылками. Последовательность объектов называется индуктивнойотносительно некоторого набора правил, если каждый ее член получается из предыдущихпо какому-либо из этих правил, которые называются правилами порождения даннойпоследовательности. Например, возрастающая последовательность всех нечетныхчисел и последовательность 1, 3, 1, 5, 7, 3 являются индуктивными относительноправил D1и Dх,х+2, а последовательность 1, 3, 7 не является индуктивной относительно этогонабора правил.

Тема2. Унификация языка.

Длячеткого выражения мыслей ученые придумали формальный язык, в котором всеосмысленные выражения строятся по определенным правилам из следующих знаков,символов:

 

Логическиезнаки " $ ØÙÚÞÛ

вспомогательныезнаки ( ),

нульместныефункциональные знаки f/> f/> f/> f/> …

одноместныефункциональные знаки f/> f/> f/> f/>…

…………………………

нульместныепредикатные знаки g/> g/> g/> g/>…

одноместныепредикатные знаки g/> g/> g/> g/>…

…………………………

переменныеc0c1c2c3…

Порядокв котором здесь перечислены знаки, называется алфавитным порядком.

Выражением,знакосочетанием, символосочетанием в этом формальном языке называется несколькозаписанных друг за другом в направлении слева на право знаков.

c, c0,c1,… обозначают нульместные функциональные знаки.

f, f0,f1,… обозначают функциональные знаки.

g, g0,g1,… обозначают предикатные знаки.

u, v,w, u0,v0,w0,u1,v1,w1,… обозначают выражения.

х,y, z, х0, y0, z0, х1, y1,z1, … обозначают переменные.

uvобозначает результат написания выражения v после выражения u.

 

Термаминазываются знакосочетания с такими порождающими правилами:

Dх

Dc

Du1,…,un, f (u1,… ,un). f n-местный,n¹0.

 

Обозначениядля термов: a, b, a0, b0, a1,b1, …

 

Примериндуктивной последовательности термов:

f/>

c1

f/> (c1,f/>)

f/> (c1,c1,f/>(c1,f/>))

c2

f/>(c1,f/>,f/>(c1,f/>),c2)

f/>(c2)

f/>(f/>(c2))

 

Высказываниями, соотношениями,формулами называются знакосочетания с такими правилами порождения:

Dg здесьg нульместный

Dg(а1,…, аn)здесь gn-местный, n¹0

Du, «x(u)

Du, $x(u)

Du, Ø(u)

Du, v, (u)Ù(v)

Du, v, (u)Ú(v)

Du, v, (u)Þ(v)

Du, v, (u)Û(v)

 

Примериндуктивной последовательности формул (на основе термов из предыдущего примера)

g/>(f/>,c1)

g/>

»c5(g/>)

$c1(g/>(f/>,c1))

Ø(«c5(g/>))

g/>

(g/>)Ú(»c5(g/>))

g/>(f/>(c1,f/>),c2,c2)

Обозначениямидля высказываний: p, q,r, s,t, p0,q0,r0,s0,t0,…

Сцелью удобства обозрения формул некоторые скобочные диады можно опускать,принимая соглашение о правосторонней группировке скобок для несколькиходинаковых логических знаков и соглашение об убывании силы связи в алфавитномпорядке логических знаков. Пример: pÞqÞrозначает (p)Þ((q)Þ(r)), а запись Ø$xpÚqÙrпонимается как (Ø($x(p)))Ú((q)Ù(r)).Следует помнить, что любое высказывание с пропущенными парами скобок неявляется высказыванием формального языка, оно является лишь обозначением соответствующеговысказывания.

 

Нульместныефункциональные знаки называются константами. Знакосочетание «xназывается квантором всеобщности по х, а $х — кванторомсуществования по х. Начинающееся с предикатного знака высказывание называетсяпредикатом. Высказывание называется элементарным, если оно начинается сквантора или предикатного знака. Высказывание q называется подвысказыванием иликомпонентой высказывания р, если q есть часть р. Элементарная компонента qвысказывания р называется его пропозициональной компонентой, если q имеет хотябы одно такое вхождение в р, которое не является вхождением в какую-нибудьдругую элементарную компоненту высказывания р. Например, высказывание $c5(g/>Ùg/>)Þg/> имеет пять компонент: $c5(g/>Ùg/>), g/>, g/>, g/>Ùg/>, $c5(g/>Ùg/>)Þg/>, из которых только первыетри являются элементарными, первые две — пропозициональными, только g/> и g/> - предикатными.

 

Интерпретацияформального языка. Переменная выражает, нотирует, обозначает произвольныйобъект из некоторого не пустого множества, которое называется денотарием илиуниверсумом данной интерпретации и элементы которого тем самым являются денотатамиили значениями переменной. n-местный функциональный знак обозначает n-местнуюоперацию на универсуме. n-местный предикатный знак обозначает изначальнуювзаимосвязь между любыми nобъектами универсума. Термы обозначают объекты универсума, а высказыванияобозначают истину или ложь, т. е. денотатами термов являются объектыуниверсума, а денотатами высказываний являются истина и ложь. Задать интерпретациюформального языка значит задать ее универсум и связанные с ним значения всехнужных нам функциональных и предикатных знаков; тогда значения всех нужныхтермов и формул при любых значениях фигурирующих в них переменных определяютсяиндукцией по их построению с учетом такой интерпретации логических знаков:

»xp- обобщение высказывания р по х является истинным тттк р является истинным длявсех значений переменной х; синонимы: р для каждого х, р для любого х, р длявсех x, р для произвольногох.

$xp- подтверждение высказывания р по х является истинным тттк р является истиннымхотя бы для одного значения переменной х; синонимы: существует х т.ч. р, р длянекоторого х.

Øp- отрицание высказывания р является истинным тттк р является ложным; синонимы:не р, неверно что р.

pÙq- конъюнкция высказываний р, q является истинной тттк оба ее конъюнкта р, q являютсяистинными; синонимы: р и q, и р и q.

pÚq- дизъюнкция высказываний p, q является ложной тттк оба ее дизъюнкта р, q являютсяложными; синонимы: р или q, или р или q.

pÞq- импликация высказываний p, q является ложной тттк посылка р является истинной,а заключение q является ложным; синонимы: р только если q, если р то q, q еслир, р тогда q, q когда р, для того чтобы р необходимо чтобы q, для того чтобы qдостаточно чтобы р, р следовательно q, из того что р следует что q.

pÛq- эквиваленция высказываний р, q является истинной тттк ее части р, q обе являютсяистинными или обе являются ложными; синонимы: р если и только если q, р тогда итолько тогда когда q, для того чтобы р необходимо и достаточно чтобы q, рэквивалентно q.

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

Замечание.Введение обозначений для высказываний порождает двусмысленность в использованиизнака равенства, поскольку сами высказывания являются некоторыми обозначениями,а именно обозначениями истины или лжи. При наличии иерархии обозначений такуюдвусмысленность обычно снимают соглашением о том, что равенство понимается какравенство между исходными объектами. Т. о. равенство p=q означает, что р и qимеют одинаковые истинностные значения т. е. являются равносильными.

Пример.Каждый кулик свое болото хвалит.

Универсум- множество куликов и болот

g/>(x) — х есть кулик

g/>(x) — х есть болото

g/>(x, у) — х хвалит у

g/>(x, у) — у свое для х

«c1((((g/>(c1))Ù(g/>(c2)))Ù(g/>(c1,c2)))Þ(g/>(c1,c2)))

         

Пример.Сумма квадратов двух положительных чисел меньше квадрата их суммы.

Универсум- множество положительных чисел.

f/>(x)- квадрат числа x

f/>(x,y) — сумма чисел x,y

g/>(x,y) – xменьше y

g/>(f/>(f/>(c1),f/>(c2)),f/>(f/>(c1,c2)))

Можнозаписать по-другому:

универсум- множество действительных чисел

f/> -число 0

((g/>(f/>, c1))Ù(g/>(f/>, c2)))Þ(g/>(f/>(f/>(c1),f/>(c2)),f/>(f/>(c1,c2)))

Пример.Только я один знаю об этом.

Универсум– множество людей

f/> -я

g/>(x)- x знает об этом

g/>(x,y) — xидентичен y

(g/>(f/>))Ù(»c1((Ø(g/>(c1,f/>)))Þ(Ø(g/>(c1))))

Никтоне знает об этом: «c1(Ø(g/>(c1)))

Всезнают об этом: „c1(g/>(c1))

Кто-нибудьзнает об этом: $c1(g/>(c1))

         

Пример.Здесь холодно, но не сыро: (g/>)Ù(Ø(g/>))

Пример.Ни p ни q:Øpи Øq

Пример.Еслиp то qиначе r: (pÞq)Ù(ØpÞr)

Пример.p либо q:pÙØqÚØpÙq

Пример.p поэтому q:pÙ(pÞq)

 

Пример.Чай без сахара не сладкий и не вкусный.

g/> -чай содержит сахар

g/> -чай сладкий

g/> - чай вкусный

(Ø(g/>))Þ((Ø(g/>))Ù(Ø(g/>)))

Возможендругой перевод:

((Ø(g/>))Þ(Ø(g/>)))Ù((Ø(g/>))Þ((Ø(g/>)))

 

Пример.Его отец слесарь, а все братья токари.

Универсум– множество мужчин

f/> - он

f/>(x)- отец для x

g/>(x)- x есть слесарь

g/>(x)- x есть токарь

g/>(x,y) — xидентичен y

(g/>(f/>(f/>)))Ù(“c1(((Ø(g/>(c1,f/>)))Ù(g/>(f/>(c1),( f/>(f/>))))Þ(g/>(c1))))

Тема 3. Пропозициональная логика

илилогика элементарных высказываний изучает свойства логических операций Ø,Ù,Ú,Þ,Û,которые по смыслу их введения являются операциями над истинностными значениями:

p

q

Øp

pÙq

pÚq

pÞq

pÛq

Л Л И Л Л И И Л И И Л И И Л И Л Л Л И Л Л И И Л И И И И

Есливысказывания р, q различны и элементарны, то эта таблица называется истинностнойтаблицей высказываний (p,q,) Øp,pÙq,pÚq,pÞq,pÛq. В общем случае при составлении истинностной таблицы какого-либо перечнявысказываний надо поместить на ее вход все различные пропозициональныекомпоненты этих высказываний, сделать полный перебор истинностных значений вовходных столбцах и записать соответствующие истинностные значения врезультирующих столбцах.

Пример.В комнате без окон темно и неуютно.

Универсум- множество комнат

g/>(c1)-  c1 имеет окно                      p- комната имеет окно

g/>(c1)- в c1темно                             q- в комнате темно

g/>(c1)– в c1уютно                           r- в комнате уютно

/>/>/>(Ø(g/>(c1)))Þ((g/>(c1))Ù(Ø(g/>(c1))))          ØpÞqÙØr

        p                 q                 r

p

q

r

Øp

Ør

qÙØr

ØpÞqÙØr

Л Л Л И И Л Л Л Л И И Л Л Л Л И Л И И И И Л И И И Л Л Л И Л Л Л И Л И И Л И Л Л Л И И И Л Л И И И И И И Л Л Л И

Тавтологияили тавтологически истинное высказывание — это высказывание со сплошными И вего столбце его истинностной таблицы. Высказывание q называется тавтологическимследствием (из) высказываний p1,…,pn,если в истинностной таблице высказываний p1,…,pn,,qстолбец q содержит И в любой строке, которая содержит И во всех столбцах p1,…,pn.Например, построенная выше таблица показывает, что:

ØpÞqÙØr- есть тавтологическое следствие из Øp,qÙØr;

Ør, qявляются тавтологическими следствиями из qÙØr;

 rесть тавтологическое следствие из p, Øp.

         

Теоремаоб отрицании отрицания: ØØp= p

Теоремаоб отрицании конъюнкции: Ø(pÙq)= ØpÚØq

Теоремаоб отрицании дизъюнкции: Ø(pÚq)= ØpÙØq

Теоремаоб исключении импликации: pÞq= ØpÚq

Теоремаоб исключении эквиваленции: pÛq= pÙqÚØpÙØq

Теоремаоб устранении альтернативы: pÚØpÙq= pÚq,ØpÚpÙq= ØpÚq

Теоремао коммутативности конъюнкции: pÙq= qÙp

Теоремао коммутативностидизъюнкции: pÚq= qÚp

Теоремаоб ассоциативности конъюнкции: pÙ(qÙr)= (pÙq)Ùr

Теоремаобассоциативностидизъюнкции: pÚ(qÚr)= (pÚq)Úr

Теоремао дистрибутивностиконъюнкции: pÙ(qÚr)= (pÙq)Ú(pÙr)

Теоремаодистрибутивности дизъюнкции: pÚ(qÙr)= (pÚq)Ù(pÚr)

Теоремао равносильности: р = q тогда и только тогда когда pÛq= И

Теорема о тавтологическом  следствии:  q  является тавтологическим

следствиемиз р1,…,pn<sub/> ттткр1Ù…ÙрÞq является тавтологией. Эти три теоремы

легкодоказываются с помощью истинностных таблиц.

Арифметическийспособ записи высказываний: исключаются знаки Þ,Û

ивместо Л, И, Øp, pÙq,pÚqупотребляются соответственно 0, 1, `p,p q,p + q.

Например,арифметической записью высказывания (rÚpÞqÙr)будет  />.

Приарифметической записи высказываний с ними можно обращаться так, как будто ониобозначают числа 0, 1, а.  Логический плюс отличается от арифметического толькотем, что 1 + 1 = 1. При этом полезно помнить следующие равенства:

p Þq = `p + q                                                />

p Ûq = p q + `p `q                                        pp = p

/>                                                    p+ p = p

/>                                                       p`p= 0

p + `p q = p + q                                               p+`p = 1

p +  p q = `p+ q                                              1 + p = 1

Равенствав левой колонке представляют собой другую запись уже доказанных выше теорем, аравенства в правой колонке устанавливаются непосредственной проверкой с учетомравенств 0 = 1, 1 = 0.

 

Пример. Доказательствотавтологичности высказываний:

pÞqÞp=`p + (qÞp)=`p +`q+ p =`p+ p +`q= 1 +`q= 1

pÞqÞpÙq=`p +`q+ p q =/> + p q = 1

(ØpÞØq)Þ(ØqÞp)Þq= /> +q =`qp +`q`p+ q = `q (p +`p)+ q =`q + q = 1

Пример. Выразительнаядостаточность пар ØÙ, ØÚ, ØÞ.

pÙq= Ø(ØpÚØq)= Ø(pÞØq)

pÚq= Ø(ØpÙØq)= ØpÞq

pÞq= Ø(pÙØq)= ØpÚq

pÛq= Ø(Ø(pÙq)ÙØ(ØpÙØq))

pÛq= Ø(ØpÙq)ÙØ(pÙq)

pÛq= Ø((pÞq)ÞØ(qÞp))

Доказательствопоследнего равенства:

pÛq= p q +`p`q

Ø((pÞq)ÞØ(qÞp))= /> = (`p+ q)(q +`p) = `p`q+`p p +`qq + q p =`p`q+ 0 + 0 + q p = p q +`p`q

Пример.Упрощение высказываний.

         

(ØpÚØqÚØr)Ù(qÚØp)Ú(pÞq)Ùq= (`p +`q+`r)(q +`p)+ q(`p + q) = (`p+ q)(`p +`q+`r + q) = (`p+ q)(1 +`p + `r)= `p + q = pÞq

(pÞq)Þp= /> + p = p`q+ p = p(`q + 1) = p 1 = p

Пример.Доказательство равносильности высказываний.

[ØpÞØqÙØr]= `p Þ`q`r= `p +`q`r= p +`q`r

{(ØpÞØq)Ù(ØpÞØr)}= (`pÞ`q)(`pÞ`r)= (p +`q)(p +`r)= p + p`r +`qp +`q`r= p(1 +`r +`q)+`q`r= p +`q`r

Т.о. […] = {…} т. е. являютсяравносильными два полученных ранее перевода высказывания «чай …».

Правиломотделения называется правило Dp, (p)Þ(q),q

Теоремао выводе в пропозициональной логике: высказывание  p0является тавтологическим следствием из p1,…,pnтттк его можно получить из p1,…,pn с помощью правилаотделения и нижеследующих пятнадцати беспосылочных правил:

DpÞqÞp

D(pÞpÞq)Þ(pÞq)

D(pÞq)Þ((qÞr)Þ(pÞr))

DpÙqÞp

DpÙqÞq

D(pÞq)Þ((pÞr)Þ(pÞqÙr))

DpÞpÚq

DqÞpÚq

D(pÞr)Þ((qÞr)Þ(pÚqÞr))

D(pÛq)Þ(pÞq)

D(pÛq)Þ(qÞp)

D(pÞq)Þ((qÞp)Þ(pÛq))

D(pÞq)Þ(ØqÞØp)

DpÞØØp

DØØpÞp

Другимисловами, какое–либо высказывание p0является тавтологическим следствием из p1,…,pn<sub/> ттткp0можно сделать членом последовательности высказываний, которая являетсяиндуктивной относительно этих шестнадцати правил и правил Dp1,…, Dpn. Теорема не исключаетслучай n = 0.

 

Теоремао самодостаточной выразительности пропозициональной логики: для любойистинностной таблицы с nвходными столбцами p1,…,pnи любого распределения истинностных значений в ее результирующем столбце можносоставить соответствующее этому столбцу высказывание: справа от всех строк систиной в результирующем столбце записываем конъюнкцию p1…pn, затем над некоторыми pkставим черту отрицания так, чтобы все эти конъюнкции для всех строк были истинными,затем составляем дизъюнкцию из получившихся конъюнкций. Например:

p                 q                r                  ?

0                 0                0                 0

0                 0                1                 0

0                 1                0                 1                 p q`r

0                 1                1                 0

1                 0                0                 1                 p`q`r

1                 0                1                 0

1                 1                0                 1                 p q`r

1                 1                1                 0

`pq`r + p`q`r+ p q`r = `pq`r + p`r(`q+ q) =`p q`r+ p`r =`r(`pq + p) =`r(p + q) = ØrÙ(pÚq)

Замечание.Если в результирующем столбце содержится только Л, то в качестве искомоговысказывания можно взять p1ÙØp1.

 

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

p – житель говорит правду

q – эта дорога ведет в столицу

r – высказывание для вопроса

p

q

r

Нужный ответ

 

1 Нет `p`q 1 Да 1 Нет 1 1 1 Да p q

r =`p`q+ p q= pÛqт. e. турист должен спросить: верно ли,что Вы скажите правду если и только если эта дорога ведет в столицу.

Примерпроверки рассуждения «(Профсоюзы поддержат президента на предстоящих выборах |p) только если (он подпишетзаконопроект о повышении заработной платы ½q).(Фермеры окажут президенту поддержку ½r)только если (он наложит вето на законопроект ½s).Очевидно, что он не подпишет законопроекта или не наложит на него вето.Следовательно президент потеряет голоса профсоюзников или голоса фермеров».

(pÞq)Ù(rÞs)Ù(ØpÚØs)Þ ØpÚØr= /> +`p+`r =`pq + rs + qs +`p+`r = /> + qs = /> + qs =`p+`q +`r+`s +qs =`p+`r + /> + qs = `p+`r+1 = 1– тавтология, т.е. рассуждение правильное.

          Примерпроверки рассуждения «(В бюджете возникнет дефицит |p), если (не повысят пошлины |Øq).Если в бюджете будет дефицит, то (государственные расходы на общественные нуждысократятся | r).Значит, если повысят пошлины, то государственные расходы на общественные нуждыне сократятся».

(ØqÞp)Ù(pÞr)Þ(qÞØr)= /> +`q+ `r =`q`p+ p`r+`q +`r= `q(`p+1) +`r(p+ 1) =`q+`r = /> - не тавтология, т.е.нельзя сказать, что рассуждение правильно.

Примерпроверки рассуждения «Если (подозреваемый совершил эту кражу |p), то (она была тщательноподготовлена | q)или (он имел соучастника | r).Если бы кража была подготовлена тщательно, то, если бы был соучастник, украденобыло бы гораздо больше. Значит, подозреваемый невиновен».

(pÞqÚr)Ù(qÞ(rÞØp))ÞØp= /> +`p= p`q`r+ p qr +`p= q r+`q`r+`p

–не тавтология.

Примерпроверки рассуждения «(Если наступит мир | p),то (возникнет депрессия | q),разве что (страна проведет программу перевооружения | r) или осуществит грандиознуюсоциальную программу | s).Но договориться о целях такой грандиозной программы невозможно. Следовательноесли наступит мир и не будет депрессии, то будет осуществляться программаперевооружения».

(pÞqÚØqÙ(rÚs))ÙØsÞpÙØqÞr= /> = />

т.е.рассуждение правильное.

Примерсокращения текста «Члены финансового комитета должны избираться среди членовдирекции. Нельзя быть одновременно членом дирекции и членом библиотечногосовета, не будучи членом финансового комитета. Член библиотечного совета неможет быть членом финансового комитета».

p – он является членом финансовогокомитета

q – он является членом дирекции

r – он является членом библиотечногофонда

(pÞq)Ù(ØpÞØ(qÙr))Ù(rÞØp)= (`p + q)(p+`q +`r)(`r+`p) = (`p+q)/> = (`p+ q)/>=(`p+ q)(`p`q+`r) = (`p+ q)(`p+ q)`q+`r) = (`p+ q)(`q+`r) = (pÞq)ÙØ(qÙr)

Такимобразом, можно отбросить подчеркнутую часть текста.

Примеранализа рассуждения «(это преступление совершено в Кустанае |q). (Петров во время совершенияпреступления находился в Ростове | r).Следовательно (Петров не совершал этого преступления |Øp)».

qÙrÞØp– не тавтология

«Преступлениесовершено в Кустанае. Поэтому если Петров совершил это преступление, то (он вовремя совершения преступления находился в Кустанае |s).Но Петрова в это время в Кустанае не было. Значит, Петров не совершал этого преступления».

qÙ(qÞpÞs)ÙØp= … =1 – тавтология т.е. рассуждение правильное.

Рассуждениеостанется правильным, если из него выбросить первое предложение и ссылку нанего во втором предложении:

(pÞs)ÙØsÞØp= /> +`p= /> +`p= p + s +`p = 1 + s = 1

Задача.Выяснить, кто из четверых виновен на основе информации «Петров виновен, толькоесли виновен Кулагин. Неверно, что виновность Родионова влечет виновностьСидорова и что Кулагин виновен, а Сидоров нет».

p,q, r,s – виновен Петров, Кулагин,Родионов, Сидоров.

(pÞq)ÙØ(rÞs)ÙØ(qÙØs)= (`p + q)/> =(`p + q) r`s(`q+ s) = (`p + q)`rs`q = `p`qr`s

т.е.Родионов виновен, остальные не виновны.

 

ЗадачаКислера. Обвиняемые в подделке налоговых документов Браун,Джонс и Смит дают под присягой такие показания.

Браун:Джонс виновен, а Смит не виновен.

Джонс:Если Браун виновен, то виновен и Смит.

Смит:Я не виновен, но хотя бы один из них двоих виновен.

Вопрос1: Совместимы ли данные показания?

Вопрос2: Какое показание следует из другого?

Вопрос3: Если все виновны, то кто лжесвидетельствует?

Вопрос4: Если все сказали правду, то кто виновен?

Вопрос5: Если невинный говорит правду, а виновный лжет, то кто виновен, а ктоневиновен?

Б– виновен Браун.

Д– виновен Джонс.

С– виновен Смит.

Б

Д

С

ØБ

ØД

ØС

БÚД

ДÙØС

БÞС

ØСÙ(БÚД)

Л Л Л И И И Л Л И Л Л Л И И И Л Л Л И Л Л И Л И Л И И И И И Л И И И Л Л И Л И Л И Л Л Л И И И Л Л И И Л И Л И Л И Л И Л И И Л Л Л И И И Л И И И И Л Л Л И Л И Л Показания Брауна Джонса Смита

1.  Да,только за счет третьей строки.

2.  Изпервого третье.

3.  Брауни Смит.

4.  Джонсвиновен,  остальные невиновны.

5.  Джонсневиновен, остальные виновны.

Тема4. Кванторная логика.

 

илилогика предикатов является расширением пропозициональной логики путем изученияопераций », $. Из определения этих операцийследует, что значения высказываний «хp,$хp,понимаются соответственно как конъюнкция p1Ùp2Ùp3Ù…и дизъюнкция p1Úp2Úp3Ú…значений высказывания pдля всевозможных значений переменной х. Высказывание pназывается кванторологически истинным при любой интерпретации.

Из определений следует, что тавттологически истинноевысказывание является кванторологически истинным. Обратное вообще говоря неверно: высказывание „хpÞ$хpявляется кванторологически истинным, но не является тавтологически истинным.

Истинностнаятаблица.

“хp

$хp

»хpÞ$хp

Л Л И Л И И И Л Л И И И

Истинностнаясхема.

p1, p2, p3…

"хp

 p1Ùp2Ùp3Ù…

$хp

p1Úp2Úp3Ú…

"хpÞ$хp

ЛЛЛ… Л Л И ЛЛЛ… Л И И ……… … … … ИИИ… И И И

Высказываниеqназывается кванторологическим следствием (из) высказываний р1,…,pn,если p является истинным  в любойинтерпретации, в которой истинными являются p1,…,pn.

Вхождениемпеременной c в высказывание pназывается связанным, если оно является вхождением в некоторое подвысказываниевида «х(q)или вида $х(q);в противном случае это вхождение называется свободным.

Например, первое и второе вхождения c1 в высказывание

((g/>(c1))Ù(g/>(c1, c2)))Þ($ c1(g/>(c1)))

являются свободными, а третье ичетвертое – связанными.

Через р{х, а} обозначается результатподстановки терма, а вместо всех свободных вхождений переменной х ввысказывание р, причем, если при такой подстановке все вхождения переменных иза остаются свободными, то терм а называется допустимым заменителем для х в р.Например, терм f/>(c5) являетсядопустимым заменителем для c6 в высказыванииg/>((c5, (c6), и не является

допустимым заменителем для c6 в высказывании $c5 (g/>(c5, c6)). Высказывание р называется замкнутым (открытым),если оно не имеет свободных (связанных) вхождений переменных.

Теоремао всезначности переменной: р = И тттк „хр = И

Теорема об отрицании обобщения иподтверждения:

Ø“хр равносильно $хØр

Ø$хр равносильно „хØр

Теорема о взаимоисключении кванторов:

“хр равносильно Ø$хØр

$хр равносильно Ø»хØр

Теорема о перестановочности кванторов:

«х»ур равносильно «у»хр

$х$ур равносильно $у$хр

Типовые кванторы. Запись "qхр обозначает высказывание «х(qÞр), а запись $qхр обозначает высказывание $х(qÙр).

Теорема о равносильнойзамене: пусть q есть результат замены в высказываниир какого-либо вхождения подвысказывания r1 на высказывание r2; тогда если r1 и r2равносильны, то р и q тоже равносильны.

Позитивным высказыванием называется такое,которое не имеет вхождений знака Ø. Позитивной формой высказывания р называется любоеравносильное ему позитивное высказывание .

Теорема о позитивнойформе: еслиотрицания предикатных компонент высказывания р имеют равносильные себе предикаты,то р равносильно некоторому позитивному высказыванию q; высказывание qможно построить с помощью теоремы о равносильной замене, теорем об исключенииопераций Þ, Û и теорем об отрицании для операций », $, Ø, Ù, Ú.

Пример построения позитивнойформы отрицания высказывания: «для каждогоположительного числа е существует положительное число d т.ч. для каждого числа х из х<d следует, что х<е или х£1».

Ø«е$d»х(х<dÞх<еÚх£1 = $e«d$хØ(х<dÞх<eÚх£1) = $e»d$хØ(Øх<dÚх<eÚх£1) = $e«d$х(х<dÙØх<eÙØх£1) = $e»d$х(х<dÙх³eÙх>1) = « существует положительноечисло е т.ч. для каждого положительного числа  d существует число х т.ч. х<d и х³e и х>1».

Теорема о выводе в логике предикатов:нижеследующие шесть правил преобразования высказываний образуют достаточныйнабор правил вывода в логике предикатов т.е. р0являетсякванторологическим следствием из p1,…,pn тттк р0может быть получено из р1,…, рn с помощью этих шестиправил:

Dt – правило тавтологии

Ds, sÞ r,r – правило отделения

D«хрÞp{x,a} – правило обобщения

Dp{x,a} Þ$xp – правило подтверждения

DqÞr,q Þ»хr– правило общевнесения

DrÞq,$ xrÞq– правило сущевнесения

гдеt есть тавтология, qне имеет свободных вхождений x,терм а является допустимым заменителем для х в р. Теорема не исключает случай n= 0.

 

Тема 5. Эгалитарная логика

 

или логика предикатов сравенством, т.е. с двухместным предикатным символом g20, которыйинтерпретируется как знак равенства. Т.о. в эгалитарной логике предикат g20(a,b) выражает то, что мы привыкли выражать в виде a = b и понимать как констатациютого, что объекты с обозначениями a, b являются  одинаковыми, равными,неотличимыми, идентичными. Эгалитарной интерпретацией формального языканазывается такая, в которой g/> интерпретируется как знак равенства. Запись p1,…, pn│=q1, …, qm означает, что каждое извысказываний q1, …, qm является логическим следствием извысказываний p1, …, pn т.е. что оно является истинным влюбой эгалитарной интерпретации, в которой оказываются истинными     p1,…, pn. Высказывание p называется логически истинным, если  │=pт.е. если p является истинным в любой эгалитарной интерпретации.

Правилами тождества, равенства, неотличимости называются следующие триправила соответственно:

Dg/>(x, x)

Dg/>(x1, y1)Ù…Ù g/>(xn, yn)Þg/>(f(x1, …,<sub/>xn),f(y1, …,<sub/>yn))

Dg2 (x1, y1)Ù…Ù g/>(xn, yn)Þ(g f(x1, …,<sub/>xn)Þ(y1, …,<sub/>yn))

Теорема об эгалитарной замене: пусть  qесть результат замены в p некоторых вхождений терма a термом b; тогда есливыражение g20(a, b) является истинным, то p равносильноq.

Теорема о транзитивности логическогоследствия: если p1, …, pn│=q1,…,qm             и    q1, …, qm│= r1, …, re, то p1,…, pn│= r1, …, re.

Теорема о расширении списка гипотез: если p1,…, pn│= q, то p0, …, pn│= q.

Теорема дедукции: если высказывания p1,…, pn являются замкнутыми, то p1, …, pn│=p тогда и только тогда когда ê= p1Ù…Ù pnÞp.

Теорема о конъюнктивизации гипотез: p1,…, pn│= p тттк p1Ù…Ùpn│= p.

Теорема о выводе  в эгалитарной логике:правила тавтологии, отделения, обобщения, подтверждения, общевнесения,сущевнесения, тождества, равенства, неотличимости образуют достаточный наборправил вывода в эгалитарной логике, т.е. p1, …, pn│=p тттк p может быть получено из p1, …, pn с помощью этогонабора правил.

Теорема о сравнительной силе выводов. Если pявляется тавтологическим следствием из p1, …, pn, то pявляется кванторологическим следствием из p1, …, pn. Еслиp является кванторологическим следствием из р1,…, рn, то p является логическим следствиемиз р1,…, рn.

Алгоритм – это…

Теорема о неразрешимости проблемы логическогоследствия (логической истинности): нельзя придумать алгоритм, который для любыхвысказываний p0, …, pn позволял бы разрешить вопрос отом, является или нет p0логическим следствием из p1, …,pn. Полезно обратить внимание на то, что проблема тавтологического следствия является разрешимой с помощью истинностных таблиц.

Замечание последние семь теорем не исключаютслучай n = 0.

Замечание если не оговорено противное, словологика понимается как эгалитарная логика.

Тема 6. Формальные теории

 

предназначены для четкогоизложения и развития тех или иных отраслей человеческих знаний. Задатьформальную теорию – значит задать ее функциональные и предикатные символы, атакже аксиомы, т. е. некоторые из высказываний, которые являются истинными вданной отрасли знаний. Развивать формальную теорию – значит пополнять запас еетеорем, т. е. таких высказываний, которые являются логическими следствиямиаксиом.

Изложение любой формальной теории в принципеможно оформить в виде книжек с доказательными текстами:

1

a1 — × — × — × — × — × — × — × — × — × —

ü индуктивная

ý последовательность

þ термов

… ×××××××××××××××××××××××××××××××××××××××××××××××××××××× k

ak — × — × — × — × — × — × — × — × — × —

k+1

r1 — × — × — × — × — × — × — × — × — × —

ü индуктивная

ý последовательность формул

þ на основе a1,…, ak

… ×××××××××××××××××××××××××××××××××××××××××××××××××××××× k+е

re — × — × — × — × — × — × — × — × — × —

k+е+1

s1 — × — × — × — × — × — × — × — × — × —

ü аксиомы

ý s1,…, sm есть

þ среди r1,…, re

… ×××××××××××××××××××××××××××××××××××××××××××××××××××××× k+е+m

sm — × — × — × — × — × — × — × — × — × —

k+е+m+1

t1   — × — × — × — × — × — × — × — × — × —

ü индуктивная

ý последовательность теорем

þ  t1,…, tn есть среди r1,…, re

… ×××××××××××××××××××××××××××××××××××××××××××××××××××××× k+е+m+n

tn<sub/>- × — × — × — × — × — × — × — × — × —

Здесь штрих-пунктирнаялиния обозначает пояснение о том, с помощью какого правила порождения полученосоответствующее знакосочетание. Для удобства таких пояснений знакосочетания a1,…, tn нумеруются последовательно от 1 до k+е+m+n. Вспомним, что правила порождениятеорем являются правилами вывода, что конечная индуктивная последовательностьтеорем является доказательством и что следующие девять правил, называемыхосновными, образуют достаточный набор правил вывода из аксиом: правилатавтологии, отделения, обобщения, подтверждения, общевнесения, сущевнесения,тождества, равенства, неотличимости.

Такая форма изложенияделает доказательство легко проверяемым, но практически не применяется из-за еегромоздкости.

Способы более компактного изложенияформальной теории.

1. Последовательность a1,…, re не записывается, потому что при достаточном навыке термы и формулыраспознаются без построения их индуктивных последовательностей.

2. В последовательность t1,…, tn включаются теоремы из других доказательных текстов.

3. Для двухместногофункционального или предикатного знака v используется операционная форма записи: вместо v(a,b) пишут (a)v(b).

4. Приоперационной форме записи принимается соглашение об упразднении некоторых парскобок в соответствии с соглашением об убывании силы связи в последовательности:одноместный функциональный знак, двухместный функциональный знак, одноместныйпредикатный знак, двухместный предикатный знак, логический знак.

5. Используютсяспециальные начертания для функциональных и предикатных знаков. Например втеории чисел: 0, 1, 2, 3 — нульместные функциональные знаки; Ö, sin, cos — одноместныефункциональные знаки; +, -, ´, /,­ — двухместные функциональные знаки; <, >, £, ³ — двухместные предикатные знаки.

6. Используются знаковыефигуры. Например, åх=3х обозначает сумму 3+4+5.

7. Вводится определяющаяаксиома g(х1,..., х11)Û р для нового n-местного предикатного символа g. Здесь переменные х1,..., хn<sub/>попарно различны, а высказывание р неимеет свободных вхождений переменных, отличных от х1,..., хn.

8. Вводится определяющаяаксиома р{х, ¦( х1,..., хn)} для нового n — местногофункционального символа ¦ в тех случаях, когда формула $рх является теоремой. Здесь переменные х, х1,..., хn<sub/>попарно различны, а р не имеетсвободное вхождение переменных, отличных от х, х1,..., хn.

Теорема об определениях: если теория Т2получена из теории Т1 путем добавления определяющей аксиомы длянового функционального или предикатного символа v то для каждой теоремы теории Т2 существуетравносильная ей теорема теории<sub/>Т1.

9. Кроме девяти основныхприменяются дополнительные правила вывода, например правило отделения конъюнктаD pÙg, р и правило присоединения дизъюнкта Dр, pÚg.

10. Применяются известные методыдоказательства. Обоснование таких методов дается в учебниках логики. Напримерметод доказательства от противного основан на следующей теореме.

Теорема о доказательстве  методом отпротивного: если формальная теория Т2 получена путем добавленияаксиомы Øр к аксиомам теории Т1 иесли формулы q, Øq являются теоремами теории Т2, то формула рявляется теоремой теории Т1.

Формальная арифметика формализует систему знаний о целых неотрицательных числах, использует в качестве исходных четыре функциональных идва предикатных знака

¦/>

¦/>

¦/>

¦/>

g/>

g/>

1 + × = <

интерпретируемых в соответствии с ихизвестными со школы специальными начертаниями, имеет такие аксиомы

Ø1=0

х + 1= y + Þ x = y

x + 0 = x

x + (y + 1) =(x + y) + 1

x×0 = 0

x×(y + 1) = x×y + x

Øx < 0

x < y + 1 Û x < y Ú x = y

p íx, 0ýÚ"(pÞíx, x + 1ý)Þ p

Здесь при записи аксиомиспользованы ранее перечисленные соглашения о компактизации изложения иизвестное соглашение о том, что знак умножения связывает сильнее знакасложения. Если такие соглашения не принимать, то к примеру первую аксиому следовалобы записать в виде Ø(g/>(¦/>,¦ />)).

Пример определяющих аксиом для новыхнульместных функциональных знаков 2, 3, 4, 5 и новых двухместных предикатныхзнаков >, £ ,³ ,¹ :

2 = 1 + 1

c1>c2  Û c2<c1

3 = 2 + 1

c1£c2 Û c1 < c2 Ú c1 = c2

4 = 3 + 1

c1³c2 Û c1 > c2 Ú c1 = c2

5 = 4 + 1

c1¹c2 Û Øc1 = c2

Заметим, что знак < можно было бы не включать в переченьисходных знаков формальной арифметики, а ввести его с помощью определяющейаксиомы                                 c1<c2  Û $c3(Øc3= 0 Ù c1+c3 = c2).

Пример доказательного текста в формальнойарифметике (k = 3, е = 6, m = 1, n =3):

1

¦/> ----------------------------------------------

Константа 2

¦/> —

Константа 3

c1<sub/>-----------------------------------------

Переменная 4

g/>(¦/>, ¦/>)--------------------------------

Предикат от 2,1 5

Ø(g/>(¦/>, ¦/>))-----------------------------

Отрицание 4 6

g/>(c1, ¦/>)---------------------------------

Предикат от 3,1 7

Ø(g/>(c1, ¦/>))-----------------------------

Отрицание 6 8

$c1(g/>(c1, ¦/>)))---------------------------

Подтверждение 7 по c1

9

(Ø(g/>(¦/>, ¦/>)))Þ$c1(Ø(g/>(c1, ¦/>))))---

Импликация 5,8 10

Ø(g/>(¦/>, ¦/>))-----------------------------

5: аксиома 11

(Ø( g/>(¦/>,¦ />)))Þ$c1(Ø(g/>(c1,¦/>))))---

9: пр. подт. 7, c1, 2

12

Ø(g/>(¦/>, ¦/>))-----------------------------

5: аксиома 10 13

$c1(Ø( g/>(c1, ¦/>)))-----------------------

8: пр. отделения для 12, 11

Компактизированный текст:

11

Ø1 = 0 Þ$c1Øc1 = 0---------------------

Правило подтверждения 12 Ø1 = 0------------------------------------- Аксиома 13

$c1Øc1 = 0--------------------------------

Правило отд. для 12, 11

Словесный вариант: «Если единица неравна нулю, то тем самым существует не равное нулю число. Но единица не равнанулю. Следовательно, существует число, не равное нулю».

Тема 7. Множества и функции.

 

В этой теме A, B, C, D,E, F, G, X, Y, Z, X1, Z1,…, Xn, Yn,Zn обозначают попарно различные переменные. Множество – этосовокупность различных объектов, мыслимая как единый новый объект. Различныеобъекты, из которых составлено множество, называются его элементами.Соотношение xÎAозначает, что объект х есть элемент множества A. Отрицание соотношения xÎA записывается в виде xÏA. Соотношение АÌВ означает, что А есть подмножествомножества В, т.е. что каждый элемент множества А является элементом множестваВ. Отрицание соотношения АÌВ записывается в виде АËВ. Множество, элементами которого являются все те и только теобъекты вида а, для которых истинно соотношение p, обозначается через {a|p}.Множество {x|«A(xÏA)} называется пустым множеством иобозначается символом Ø. Множество {x|x = x1Ú…Úx = xn} обозначается через {x1,…,xn}.Множество {x|xÎAÚxÎB} называется объединением множеств А, В и обозначается черезАÈВ. Множество {x|xÎAÙxÎB} называется пересечением множеств А, В и обозначается черезАÇВ. Множество {x|xÎAÙxÏB} называется дополнением множества В относительно А или результатомудаления из множества А элементов множества В и обозначается через А\В.

 

Простейшиетеоремы: 3Ï{9, 7, 3}, {x+5|x2 = 4} = {3,7], AÏA, AÌA, …

Обозначения  для некоторых множеств:

N — множество натуральных чисел

Z - множество целых чисел

R — множество действительных чисел

Упорядоченная n-ка объектов x1,…,xnобозначается через (x1,…,xn) и определяется так:     (x1)= x1

(x1, x2)= {{x1}, { x1, x2}}

(x1, x2, x3)= ((x1, x2), x3)

(x1, x2, x3,x4)= ((x1, x2, x3), x4)

………………………………..

Упорядоченная n-каназывается еще n-мерным упорядоченным набором, вектором, точкой, кортежем.Объект x1 называется k-той компонентой или координатой n-мерногонабора (x1,…,xn) и обозначается через koor/>(x1,…,xn).Множество {x1,…,xn| x1Îz1Ù…Ù xnÎzn} называется декартовым произведением множеств z1,…,znи обозначается через z1´…´zn. Если А — множество упорядоченных n-ок, то множество {xk|(x1,…,xnÎA} называется k-той проекциейn-мерного множества А и обозначается через π/>А. Через Аn обозначаетсямножество А´…´А (n множителей). Соглашение: знаки ´, Ç, связывают сильнее чем È, \.

Простейшие теоремы: (x1,…,xn) = (y1,…,yn)Û x1= y1Ù…Ù xn= yn,  (9, 9,9)¹(9, 9), p/>(A´B´C´D´E) = C, {5. 7}2= {(5, 5), (5, 7), (7, 5), (7, 7)}, koor/>(5, 7, 9) = 9, koor/>(5, 7, 9) = koor/>(5, 7, 9) = koor/>(5, 7, 9) = H, {7}´{8, 5}´{9} = {(7, 8, 9), (7,5,9)}. {4}5 = {(4, 4, 4, 4, 4)}, p/>{(1, 2, 3), (1, 3, 2), (2,3, 4)} = {2, 3}.  A´B´C = (A´B)´C.

Функцией называется множество, любой элементкоторого есть упорядоченная двойка. Множество π/>F называется областью определения илидоменом функции F и обозначается  dom F. Множество π/>F называется областью значений илиранжиром функции F и обозначается ran F. Если (x,y)ÎF, то y называется значением функцииF в x и обозначается F(x). Если АÌ domF,то множество {y|$ÎAÙ(x, y)ÎF)} называется образом множества Аотносительно функции F и обозначается F[А].Функция F в случае dom F = A и ran FÌB / ranF=B называется еще отображением множества Ав/на множество В. Запись F: А®В означает что F есть отображение множества А в множество В. Функция Fназывается сужением функции G (на множество dom F), а функция G называетсярасширением функции F (на множество dom G), если F есть результат удаления из Gвсех тех (x, y), для которых xÏ dom F. Если F есть функция, то {(y, x)ï (x, y)ÎF} тоже есть функция, называемаяобратной по отношению к F. Очевидно, что если функция G является обратной поотношению к функции F, то F является обратной по отношению к G. Если dom F естьмножество упорядоченных n-ок, то функция F называется n-аргументной и вместоF((x1,…,xn)) используют более короткое обозначение F(x1,…,xn).Функция F называется однозначной, если из (x, y)ÎF и      (x, z)ÎF следует y=z. Функция называется взаимно однозначной илибиективной, если она сама и обратная к ней функция являются однозначными.Последовательностью называется однозначная функция F т.ч. dom F = N. ЕслиF есть последовательность и nÎN,то F(n) называется n-м членом последовательности и обычно обозначается через Fn.

Множество А называетсябесконечным, если существует биективное отображение множества N вмножество А. Множество называется конечным, если оно не является бесконечным.

Простейшие теоремы: cos(0)=1, cos[{0}] =  {1}, Аrccos  и cos обратны друг к другу, функцияarccos не является обратной к cos и является обратной к сужению функции cos намножество ran arccos.