Реферат: Алгебра висловлень

Проблема розв’язності займає важливе місце в математичній логіці. До проблеми розв’язності зводиться багато різних задач математичної логіки.

Наприклад, до проблеми розв’язності може бути зведена обговорювана вище проблема перевірки рівносильності заданих формул A і B .

Легко довести таку теорему.

Теорема 1. Формули алгебри висловлень A і B рівносильні тоді і тільки тоді, коли формула ((A ®B )Ù(B ®A )) є тавтологією.

З метою скорочення запису формул, подібних до формули з наведеної теореми, до сигнатури алгебри висловлень вводять додаткову операцію, що позначається ~ і означається так: (A ~B ) є скороченим записом формули ((A ®B )Ù(B ®A )).

Отже, останню теорему можна сформулювати так.

Формули A і B рівносильні тоді і тільки тоді, коли формула (A ~B ) є тотожно істинною.

Разом з відношенням рівносильності на множині формул алгебри висловлень, яке є, як зазначалось, відношенням еквівалентності, розглядають також деякі інші відношення, що являють собою інтерес для логіки та її застосувань. Серед останніх виділимо відношення логічного слідування, яке є відношенням часткового порядку на множині формул алгебри висловлень.

Нехай A (p ₁ ,p ₂ ,...,p_n ) і B (p ₁ ,p ₂ ,...,p_n ) - дві формули алгебри висловлень. Будемо говорити, що формула B (p ₁ ,p ₂ ,...,p_n ) є логічним слідуванням формули A (p ₁ ,p ₂ ,...,p_n ), якщо B приймає значення 1 для всіх тих наборів значень пропозиційних змінних, для яких формула A істинна (тобто приймає значення 1); позначатимемо це A ÞB .

Це означає, що множина наборів значень змінних, для яких істинна формула A , є підмножиною множини наборів значень змінних, для яких істинна формула B , що є логічним слідуванням формули A .

Приклад 5.1. Формула B (x ,y ,z )=(x Úz ) є логічним слідуванням формули A (x ,y ,z )=((x Úy )Ùz ) , що випливає з відповідних таблиць істинності (див.табл.4).

Таблиця 4

x y z	A B
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1	0 0 0 1 0 0 1 1 0 1 1 1 0 1 1 1

Очевидно, що дві формули A і B є рівносильними тоді і тільки тоді, коли кожна з них є логічним слідуванням іншої, тобто A =B тоді і тільки тоді, коли A ÞB і B ÞA .

З означення випливає також, що будь-яка формула є логічним слідуванням тотожно хибної формули, а тотожно істинна формула (тавтологія) є логічним слідуванням довільної формули.