WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаЛогіка → Логiка предикатiв. Квантори - Реферат

Логiка предикатiв. Квантори - Реферат

(6| x)) - хибні.
Важливу роль у лог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(P(x)) або x(P(x)) писати вiдповiдно xP(x) або xP(x).
Приклад 5.5. В усiх нижченаведених кванторних виразах область дiї квантора пiдкреслено.
x((3|x) (6|x)), x(3|x) (6|x), x((x2<9) (x<3)), x(x2<9) (x<3).
Перший і другий вирази, а також третій і четвертий відрізняються не лише областю дії квантора. Відмінність між ними є більш істотною, про що слід сказати окремо.
Розглянемо на унiверсальнiй множинi R всiх дiйсних чисел два вирази x2<10 i x(x2<10). Перший з них є предикатом, що залежить вiд змiнної x. Замiсть x у нього можна пiдставляти рiзнi дiйснi значення i отримувати певнi висловлення (iстиннi чи хибнi). Та сама предметна змiнна x входить у другий вираз iнакше. Якщо замiсть неї пiдставити будь-яке дiйсне значення, дiстанемо беззмiстовний вираз.
Нехай P(x) - деякий предикат на M. Перехiд вiд P(x) до xP(x) або xP(x) називається зв'язуванням змiнної x. Iншi назви - навiшування квантора на змiнну x (або на предикат P(x)), або квантифiкацiя змiнної x.
Змiнна x, на яку навiшено квантор, називається зв'язаною, у противному разi змiнна x називається вiльною.
Зв'язана змiнна, як було продемонстровано вище, вже не є змiнною укласичному розумiннi цього поняття. Вона потрiбна лише для iдентифiкацiї терма, вiд якого залежить вiдповiдна пропозицiйна форма. Вираз xP(x) не залежить вiд x i при фiксованих P i M має певне значення. Звiдси, зокрема, випливає, що можна здiйснювати перейменування зв'язаної змiнної (тобто перехiд вiд xP(x) до tP(t)) i воно не змiнює значення iстинностi виразу.
Зауважимо, що розглядувана ситуацiя не є винятком і доволі часто зустрічається в інших розділах математики. Наприклад, у виразах f(x)dx, x2 i dj параметри a, b, c, k i n - є змінними, замість яких можна пiдставляти певнi значення, а параметри x i j - це зв'язанi змiннi, пiдстановка замiсть яких будь-яких значень не має жодного смислу.
Навiшувати квантори можна й на багатомiснi предикати. Наприклад, застосовуючи квантори i до змiнних x i y двомiсного предиката A(x,y), отримаємо чотири рiзнi одномiснi предикати xA(x,y), xA(x,y), yA(x,y) i yA(x,y). У перших двох змiнна x є зв'язаною, а змiнна y - вiльною, а у двох останнiх - навпаки.
Вираз xA(x,y) (читається "для всiх x, A вiд x i y") є одномiсним предикатом B(y). Вiн є iстинним для тих i тiльки тих b M, для яких одномiсний предикат A(x,b) є iстинним для всiх x з M.
Приклад 5.6. Розглянемо двомiсний предикат A(x,y), визначений на множинi M = {a1,a2,a3,a4} за допомогою таблицi 5.5.
Таблиця 5.5.
x y a1 a2 a3 a4
a1 0 1 1 0
a2 0 1 1 1
a3 0 0 1 1
a4 0 0 1 0
Таблицi iстинностi для чотирьох вiдповiдних одномiсних предикатiв, що отримуються з A(x,y) шляхом навiшування одного квантора, наведенi у таблицi 5.6.
Таблиця 5.6.
y xA(x,y) y xA(x,y) x yA(x,,y) x yA(x,y)
a1
a2
a3
a4 0
0
1
0 a1
a2
a3
a4 0
1
1
1 a1
a2
a3
a4 0
0
0
0 a1
a2
a3
a4 1
1
1
1
У всiх чотирьох випадках до вiльної змiнної, що залишилась, можна застосовувати один з кванторiв i, зв'язавши таким чином обидвi змiннi, перетворити вiдповiднi предикати у висловлення.
Для предиката з останнього прикладу отримаємо такi висловлення:
x( yA(x,y)) = 0, y( xA(x,y)) = 0,
x( yA(x,y)) = 1, y( xA(x,y)) = 1,
y( xA(x,y)) = 1, x( yA(x,y)) = 0,
y( xA(x,y)) = 0, x( yA(x,y)) = 1.
Неважко переконатись, що висловлення, як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 є суттєвим.
Loading...

 
 

Цікаве