При різних значеннях істинності і хибності змінної х 3 і фіксованих значеннях змінних х 1 і х 2 значення функції однакові. Отже, х 3 - фіктивна змінна. Істотними є змінні х 1 і х 2. Порівнюючи другу і четверту рядки табл. 3.9, виявляємо, що при однакових значеннях істинності змінних х 1 = 1 х 3 = 0 і різних значеннях х 2 (1,0). Значення функції різні, тобто f (1,1,0) = f (1,0,0), отже, х 2 - істотна змінна. Порівнюючи четверту і восьму рядки таблиці отримаємо f (1,0,0) ≠ f (0,0,0), тобто х 1 - істотна змінна.
В тому. що х 3 - фіктивна змінна можна переконатися перетворенням формули S.
S = (x 2 → x 1 x 2 x 3) x 1 x 2 = (x
2 x 3) x 1 x 2 = = 1 x 1 x 2 = x 1 x 2
Цією формулою відповідає функція g, що отримується з f
видаленням фіктивної змінної х 3 (табл. 3.10).
Випишемо всі функції від двох змінних. очевидно їх
Очевидно, введені раніше зв'язки. →. ↔ є відповідно функції f 8. f 14. f 11. f 9. Як зв'язок використовуються і інші функції, зокрема
F 7 - штрих Шеффера х 1 х 2,
F 1 - знак Лукашевича х 1 ↓ х 2,
F 6 - розділова диз'юнкція х 1 х 2. відповідна роздільним союзу "або".
3.6. Повні системи зв'язок
Система зв'язок логіки висловлювань називається повною. якщо будь-яка формула логіки висловлювань рівносильна деякої формулою, що містить лише зв'язки цієї системи.
Використовуючи формули, рівносильні імплікації і подвійний імплікації, отримаємо, що диз'юнкція, кон'юнкція, заперечення утворюють повну систему зв'язок. Використовуючи закон де Моргана, приходимо до того, що (-), (-) - повні системи зв'язок.
Справді з трьох зв'язок. можна виключити диз'юнкцію: А В = А В або кон'юнкцію: А В = А В.
Більш того, будь-яку формулу алгебри висловлювань можна записати однією зв'язкою - штрихом Шеффера, що і пропонується зробити читачеві.
Набір таких зв'язок як заперечення і подвійна імплікація - неповний, також як і.
Проілюструвати повноту зв'язок (.) На прикладах:
S 1 = xy (y → x) S 2 = x ↔ y z
Очевидно, в даних формулах потрібно замінити всі зв'язки, крім
а) Перетворимо S 1:
S 1 = xy (y → x) = xy y x
Застосовуючи формулу поглинання отримаємо
xy x = х. тобто S 1 = х y.
б) S 2 = x ↔ y z = x (y z) x (y z). де x (y z) = x y z за законом де Моргана, так само як і
Формула S 2 стала більш громіздкою, але представлена тільки двома зв'язками.
1. Наступне висловлювання може бути інтерпретовано як складне висловлювання: "Невірно, що першим прийшов Петро або Павло". Які складові його елементарні висловлювання?
а) А: "Невірно, що першим прийшов Петро" В: "Невірно, що першим прийшов Павло";
б) А: "Першим прийшов Петро"
В: "Невірно, що першим прийшов Павло"; в) А: "Першим прийшов Петро"
В: "Першим прийшов Павло".
2. Який з формул може бути записано вислів попереднього питання?
а) А В; б) А В; в) А В.
3. Чи буде висловлювання S = (А → В) (В → С) → (А → С):
а) тотожно істинним; б) тотожне хибним; в) змінним.
4. Яке значення Х, яке визначається рівнянням Х А Х А = В?
5. Чому рівносильна кон'юнкція контроппозіціі і її конверсії? а) імплікації; б) конверсії імплікації;
в) подвійний імплікації.
6. У висловлюванні S: "Трикутники рівні тільки тоді, коли рівні їх боку". Рівність кутів в трикутнику є:
а) необхідною умовою; б) достатня умова;
в) необхідною і достатньою умовою.
8. Яка з змінних х 1. х 2. х 3 є фіктивною у формулі f, де f задана умовою f (0,0,1) = f (0,0,0)? На інших наборах значень змінних f приймає значення істинно.
а) х 1; б) х 2; в) х 3.
9. Які з змінних х 1. х 2 у функції f 15 (табл. 3.11) є фіктивними?
а) х 1 - істотна змінна; б) х 1 - істотна змінна;
в) обидві змінні х 1 і х 2 - фіктивні.
10. Які з пар зв'язок утворюють повну систему зв'язок?
Розділ 4. Перевірка правильності міркувань. Нормальні форми формул алгебри висловлювань
4.1. Логічні відносини
Розглянемо взаємини двох висловлювань P і Q:
1. Ставлення слідства. Кажуть, що з P слід Q, а якщо Q істинно щоразу, коли істинно P; Q називають наслідком P.
Нехай P і Q - складні висловлювання, складені з елементарних висловлювань A, B наступним чином Q = A → B, P = A ↔ B.
парадоксально. Справді, висловлювання "Якщо я не прийду на лекцію, то річка впадає в Біле море" звучить парадоксально. Між посилкою і висновком в цих випадках не існує відносини слідства.
Між якими парами висловлюванні, наведених нижче, існує відношення слідства?
S 1. Якщо пряма перпендикулярна радіусу кола і проходить через точку перетину радіуса з колом, то вона - дотична до кола.
S 2. Пряма є дотична до кола тоді і тільки тоді, коли вона перпендикулярна до радіуса кола і проходить через точку перетину радіуса з колом.
S 3. Якщо пряма перпендикулярна до радіуса кола, але не проходить через точку перетину радіуса з колом, то вона не є дотичною до кола.
S 4. Якщо пряма проходить через точку перетину радіуса з колом, але не є дотичною, то прямо не перпендикулярна до радіуса кола.
Введемо елементарні висловлювання:
A: Пряма перпендикулярна до радіуса кола.
B: Пряма проходить через точку перетину радіуса з окружно-
C: Пряма - дотична до кола.
Запишемо формули наведених висловлювань.