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

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

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

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

Приклад 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льки тих bM, для яких одном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...

 
 

Цікаве