Алгебра висловлень

Нехай A(p1,p2,...,pn) і B(p1,p2,...,pn) - дві формули алгебри висловлень. Будемо говорити, що формула B(p1,p2,...,pn) є логічним слідуванням формули A(p1,p2,...,pn), якщо 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 10 0

0 1

0 0

1 1

0 1

1 1

0 1

1 1

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

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