UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75850
останнє поновлення: 2016-12-08
за 7 днів додано 17

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваФормули. Рiвносильнiсть формул. Тотожно iстиннi формули (реферат)
Авторdimich
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось1081
Скачало145
Опис
ЗАКАЧКА
Замовити оригінальну роботу

РЕФЕРАТ

 

На тему:

 

Формули. Р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

-----> Page:

0 [1] [2] [3]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ