Головна Головна -> Реферати українською -> Логіка -> Формули. Рiвносильнiсть формул. Тотожно iстиннi формули

Формули. Рiвносильнiсть формул. Тотожно iстиннi формули

Назва:
Формули. Рiвносильнiсть формул. Тотожно iстиннi формули
Тип:
Реферат
Мова:
Українська
Розмiр:
11,30 KB
Завантажень:
58
Оцінка:
 
поточна оцінка 4.7


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2  3 
Формули. Рiвносильнiсть формул. Тотожно iстиннi формули

Наведемо iндуктивне означення поняття формули логiки предикатiв (предикатної формули або просто формули ) на предметнiй областi M.

1. Усi предикати P(x1,x2,...,xn) на множинi M є формулами. Такi формули називають елементарними, або атомарними.

2. Якщо A i B - формули, то (A), (B), (AB), (AB), (AB), (A~B) теж є формулами.

3. Якщо A - формула, а x - вiльна змiнна в A, то (x(A)) i (x(A)) теж формули.

4. Iнших формул, крiм утворених за правилами 1-3, немає.

Це означення дозволяє твердити, що усi формули алгебри висловлень є формулами логiки предикатiв, оскiльки висловлення - це нульмiснi предикати.

За допомогою наведеного означення неважко також переконатись, що вирази (x(y(A(x,y))(B(x)(z(C(x,z))))) i (x(y(A(x,y)B(x))(y(C(x,y)))) є формулами логiки предикатiв, а вираз (x(A(y)(x(B(x))))) не є формулою, оскiльки у виразi (A(y)(x(B(x)))), який є правильною формулою, змiнна x є зв'язаною, тобто не є вiльною змiнною i квантор 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во).

Нехай F(x1,x2,...,xn) - деяка формула логiки предикатiв на множинi M. При логiчнiй (iстинностнiй) iнтерпретацiї формули F можливi такi три основнi ситуації.

1. Iснує набiр значень змiнних, для якого формула F перетворюється на iстинне висловлення. У цьому разi формула F називається виконуваною в областi M.

Якщо для F iснує область M, в якiй F є виконуваною, то формула F називається просто виконуваною.

2. Якщо формула F приймає значення 1 (тобто є виконуваною) для всiх наборiв значень з M, то вона називається тотожно iстинною в M. Формула, тотожно iстинна у будь-яких M, називається тотожно iстинною або логiчно загальнозначущою (скорочено - лзз).

3. Якщо формула F є невиконуваною в M, то вона називається тотожно хибною в M. Формула, невиконувана в усiх M, називається тотожно хибною, або суперечнiстю.

Приклад 5.7. Формула xA(x,y)xA(x,y) є виконуваною i вона ж є тотожно iстинною в усiх одноелементних областях M. Формула F(x1,x2,...,xn)F(x1,x2,...,xn) тотожно iстинна, а формула F(x1,x2,...,xn)F(x1,x2,...,xn) тотожно хибна. Тотожно iстинними будуть формули xP(x)P(y) i P(y)xP(x).

Формули F1 i F2 називаються рiвносильними (еквiвалентними), якщо при всiх можливих пiдстановках значень замiсть їх змiнних вони набувають однакових значень; позначається F1 = F2.

Наприклад, усi тотожно iстиннi (усi тотожно хибнi) формули рiвносильнi мiж собою. Очевидно також, що коли F1 i F2 рiвносильнi, то формула F1~F2 є тотожно 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альний алгоритм, що породжує шукану множину T тотожно iстинних формул. Послiдовно будуємо всi формули, кожну з них за вiдомою процедурою перевiряємо на тотожну iстиннiсть i вносимо до множини T т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 



Реферат на тему: Формули. Рiвносильнiсть формул. Тотожно iстиннi формули

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок