Властивості числення висловлювань
У численні висловлювань особливо увага приділяється тотожно-істинним висловлюванням, оскільки вони мають входити в будь-яку теорію як загально логічні закони.
Числення висловлювань визначається таким чином.
Задаються символи числення висловлювань: , , (, ), , , (), (~) і змінні (літерали) з цілими додатними числами як індексами: X1, X2, X3, … Символи та (заперечення й імплікації відповідно) – логічні символи;
Задаються формули:
а) усі змінні Xi – формули;
б) якщо A і В – формули, то та (A B) – також формули.
Для скорочення запису можна опустити у формул зовнішні дужки та ті пари дужок, без яких можна відновити формули.
Використовуються аксіоми числення висловлень. Які б не були формули A, B, C, такі формули є аксіомами:
А1. A (B A);
А2.( A (B C)) ((A B) (A C));
А3.
(
)
((
A)
B).
Вирази А1 – А3 називаються схемами аксіом, оскільки кожен з них породжує нескінченну множину формул, що є аксіомами числення висловлювань. Наприклад, формула X1 (X2 X1) є аксіомою, утвореною за схемою А1, формула ( A) (( A) A) (де A – будь-яка формула) – аксіома, утворена за схемою А3.
Застосовуються правила виведення.
Хоча для числення висловлювань вибрано тільки два логічні символи та , можна вводити й інші операції: , , ~.
Задачі до теми „Алгебра висловлювань”
Приклад 1. Довести еквівалентності:
p
q
=
q,
p
~ q
= (p
q)
(q
p). (1)
Розв’язування. Доведення проведемо за допомогою таблиці істинності:
p |
q |
|
p q |
q |
q p |
p ~ q |
(p q) (q p) |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
Формули (1) свідчать, що імплікація і еквівалентність виражаються через операції заперечення, диз’юнкції і кон’юнкції.
Приклад 2. Довести, що формула
(p q) (r p) (2)
є тавтологією.
Розв’язування.
Тавтологію (2) можна довести за допомогою
таблиці істинності. Однак застосуємо
метод еквівалентних перетворень. Маємо
(p
q)
(r
p)
(
)
(r
p)
r
p
= (
p)
(r
)
1
(r
)
1.
Приклад 3. Довести, що формула
((p q) (q r)) ( p r) (3)
є тавтологією.
Розв’язування. Скористаємося таблицею істинності:
p |
q |
r |
p q |
q r |
(p q) (q r) |
p r |
((p q) (q r)) ( p r) |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Отже, формула (3) є тавтологією.
Приклад 4. Довести, що формула
( ) ~ (p q)
є тавтологією.
Приклад 5. Нехай (p q) = 1. Що можна сказати про істиннісне значення висловлювання
( q) ~ (p q)?
Приклад 6. Нехай (p ~ q) = 0. Що можна сказати про істиннісне значення висловлювань p ~ і ~ q?
Приклад 7. Нехай (q q) = 1. Визначити, чи досить наведених даних, щоб встановити істиннісне значення висловлювань:
а) p (q r);
б) p (q q).
Приклад 8. За допомогою таблиць істинності і методом еквівалентних перетворень довести, що формули
1) q (p q);
2) (q (p r)) ((q p) (q r));
3) (q p) ((q r) (q (p r)));
4) (q p) q;
5) (q p) p;
6) (q r) ((p r) ((q p) r));
7) q (q p);
8) p (q p);
9) p (q (p q));
10) ( ) (( q) p)
є тавтологіями.
Розв’язування 8.3) а) Скористаємося таблицею істинності. Позначимо F = (q p) ((q r) (q (p r))).
p |
q |
r |
q p |
q r |
p r |
q (p r) |
(q r) (q (p r)) |
F |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Отже, формула F є тавтологією.
б) Застосуємо метод еквівалентних перетворень. Маємо
F
= (q
p)
((q
r)
(q
(p
r)))
=
((
)
(
(p
r)))
= (q
)
(q
)
(p
r)
= (q
)
(q
)
(p
r)
= (q
(
))
(p
r)
= q
(
)
+
(p
r)
(q
+
)
= q
(
+ (p
r))
+
(1
(p
r))
= (q
1) + (
1) = q
= 1.
Отже, формула F є тавтологією.
Приклад 9. Які з цих формул є тавтологіями
а) (B C) (D A) (B D (A C));
б) A C B D (B C) (A D);
в) (A С) (D A) (B D A C);
г) ((P R) ((Q R) ((P Q) R)));
д) ((P Q) ((P (Q R))) (P R));
е) ((P Q) ((Q R) (P R)));
є)
((
)
((
)
Q));
ж) (A B) ((A C) (C B)).