Реферат на тему:

Лог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

Похожие записи