Реферат на тему Логiка предикатiв. Квантори - Логіка - Реферати - Каталог статей

Реферат на тему: Логiка предикатiв. Квантори. Як з елементарних висловлень за допомогою логiчних операцiй можна утворювати складенi висловлення, так i, використовуючи простi (елементарнi) предикати i логiчнi зв’язки (операцiї), можна будувати складенi предикати або предикатнi формули. Як правило, основнi логiчнi операцiї , , , , ~ означають для предикатiв, що заданi на однiй i тiй самiй предметнiй областi M i залежать вiд тих самих змiнних. Нехай P(x1,x2,...,xn) i Q(x1,x2,...,xn) - n-мiснi предикати на множинi M. Кон’юнкцiєю P(x1,x2,...,xn)Q(x1,x2,...,xn) називають предикат R(x1,x2,...,xn), який набуває значення 1 на тих i тiльки тих наборах значень термiв, на яких обидва предикати P(x1,x2,...,xn) i Q(x1,x2,...,xn) дорiвнюють 1. Очевидно, що область iстинностi предиката R(x1,x2,...,xn) = P(x1,x2,...,xn)Q(x1,x2,...,xn) збiгається з теоретико-множинним перетином областей iстинностi предикатiв P(x1,x2,...,xn) i Q(x1,x2,...,xn). Диз’юнкцiєю P(x1,x2,...,xn)Q(x1,x2,...,xn) називають предикат T(x1,x2,...,xn), який набуває значення 1 на тих i тiльки тих наборах значень термiв, на яких або предикат P(x1,x2,...,xn), або предикат Q(x1,x2,...,xn) дорiвнює 1. Областю iстинностi предиката T(x1,x2,...,xn) буде об’єднання областей iстинностi предикатiв P(x1,x2,...,xn) i Q(x1,x2,...,xn). Запереченням P(x1,x2,...,xn) предиката P(x1,x2,...,xn) називають предикат S(x1,x2,...,xn), який дорiвнює 1 на тих i лише тих значеннях термiв, на яких предикат P(x1,x2,...,xn) дорiвнює 0. Область iстинностi предиката S(x1,x2,...,xn) = P(x1,x2,...,xn) - це доповнення (до множини Mn) областi iстинностi предиката P(x1,x2,...,xn). Аналогiчним чином вводять й iншi логiчнi операцiї , ~ тощо. Як правило, кожнiй iз цих операцiй вiдповiдає певна теоретико-множинна операцiя над областями iстинностi предикатiв-операндiв. Неважко узагальнити означення всiх введених операцiй для предикатiв P(x1,x2,...,xn) i Q(y1,y2,...,ym), що залежать вiд рiзних змiнних i мають рiзну мiснiсть. Знаючи, як виконуються окремi операцiї, можна утворювати вирази або формули, операндами яких є предикати. Наприклад розглянемо формулу P1(x)(P3(x,z)P2(y,x,z)), що задає деякий предикат Q(x,y,z). Значення предиката Q неважко обчислити для будь-якого набору значень його термiв x, y, z, виходячи зi значень предикатiв P1, P2, P3 на цьому наборi. Квантори Додатково в логiцi предикатiв використовують двi спецiальнi операцiї, якi називають кванторами. За допомогою цих операцiй, по-перше, пропозицiйнi форми можна перетворювати у висловлення, i по-друге, теорiя предикатiв стає значно гнучкiшою, глибшою i багатшою, нiж теорiя висловлень. Саме тому логiку предикатiв iнодi називають теорiєю квантифiкацiї. Найпопулярнiшими i найбiльш часто вживаними виразами у математицi є фрази або формулювання типу «для всiх» i «iснує». Вони входять до бiльшостi промiжних i остаточних тверджень, висновкiв, лем або теорем при проведеннi математичних мiркувань або доведень. Наприклад: «для всiх дiйсних чисел x виконується рiвнiсть sin2x+cos2x = 1», «для заданих натуральних a i b завжди iснує натуральне число d, яке є бiльшим від чисел a i b», «для всiх натуральних n справедливе твердження: якщо n дiлиться нацiло на 6 i на 15, то n дiлиться на 30» тощо. Поняття, що вiдповiдає словам «для всiх», лежить в основi квантора загальностi, який означається таким чином. Нехай P(x) - предикат на множинi M. Тодi квантор загальностi - це операцiя, що ставить у вiдповiднiсть P(x) висловлення «для всiх x з M P(x) iстинно». Для позначення цiєї операцiї використовують знак , який i називають квантором загальностi. Останнє висловлення у математичнiй логiцi записують так: xP(x) (читається: «для всiх x P вiд x»). Iснує й iнший квантор, що є у певному смислi двоїстим до квантора загальностi i називається квантором iснування. Позначається вiн знаком . Якщо Q(x) - деякий предикат на множинi M, то висловлення «існує в множинi M елемент x такий, що Q(x) iстинно» записується у виглядi xQ(x) i читається скороченно «iснує такий x, що Q вiд x» або «є такий x, що Q вiд x». Походження обраних позначень пояснюється тим, що символ  є перевернутою прописною першою лiтерою нiмецького слова «alle» або англiйського слова «all», що перекладається «усi». А символ  вiдповiдає першiй лiтерi слiв «existieren» (нiм.) або «exist» (англ.) - iснувати. Вираз x читають також як «всi x», «для кожного x», «для довiльного x», «для будь-якого x», а вираз x - як «деякий x», «для деякого x», «знайдеться такий x» тощо. Зазначимо також, що, окрiм введених символiчних позначень кванторiв, використовують й iншi позначення. Так, замiсть x iнодi пишуть (x), (x) або x, а замiсть x вiдповiдно - (x), (Ex) або x.Приклад 5.4. Розглянемо два бінарні предикати на множині натуральних чисел: предикат "x менше y" і предикат "x ділить y". Перший з них будемо записувати у традиційній формі - xНеважко переконатись, що висловлення, якi мiстять однаковi квантори, рiвносильнi. Обидва висловлення x(yA(x,y)) і y(xA(x,y)) є iстинними тодi i тiльки тодi, коли предикат A(x,y) приймає значення 1 на всiх кортежах значень (a,b) з M2. Висловлення x(yA(x,y)) i y(xA(x,y)) iстиннi тодi i тiльки тодi, коли iснує принаймнi одна пара (a,b) така, що A(a,b) = 1. У той же час усi чотири висловлення з рiзнойменними кванторами є, взагалi кажучи, не рiвносильними. Особливо слiд пiдкреслити, що суттєвим є порядок слiдування рiзнойменних кванторiв. Висловлення x(yA(x,y)) i y(xA(x,y)), взагалi кажучи, нерiвносильнi. Наприклад, у термiнах табличного задання предиката A(x,y), iстиннiсть першого висловлення x(yA(x,y)) означає, що кожен рядок таблицi iстинностi мiстить принаймнi одну одиницю. А друге висловлення y(xA(x,y)), iстинне тодi i лише тодi, коли у таблицi є стовпчик, що складається тiльки з одиниць. Неважко поширити всi наведенi вище мiркування i висновки на предикати бiльшої арностi. Навiшування одного квантора завжди зменшує число вiльних змiнних i арнiсть предиката на одиницю. Застосування кванторiв до всiх змiнних предиката перетворює його у висловлення (iнодi таку предикатну формулу називають замкненою формулою). Порядок слiдування рiзнойменних кванторiв у фîрмулi є суттєвим.
1 2 3 4 5 Категория: Логіка \| Добавил: Aspirant (22.07.2013)
Просмотров: 511 \| Рейтинг: 0.0/0

Всего комментариев: 0


Имя *:
Email *:

Код *: