Конверський А. Є. Логіка (традиційна та сучасна)

Подождите немного. Документ загружается.

Книга друга. СУЧАСНА ЛОГІКА

321

Таблиця істинності для кожної з цих формул і схожих з

ними результатом матиме одне значення «х» («хибу»):

p p ∨ q p ∨ q p & (p ∨ q)

ііх і х х

іхх х і х

хіі і х х

хх і і х х

Тотожно-хибні формули є протилежними тотожно-істин-

ним формул. Це означає, що заперечення тотожно-істинної

формули дає тотожно-хибну формулу і навпаки.

І, нарешті, третім видом формул за семантичними озна-

ками є виконувані, або нейтральні, формули.

Виконуваною фомулою в S

називається така форму-

ла, яка при одних наборах значень пропозиційних змін-

них є істинною, а при інших – хибною. Їх іноді назива-

ють фактичними істинами.

Наприклад: p & (q ⊃ r), p ⊃

s , (p ∨ q) ⊃ p, тощо. Пере-

свідчитися у тому, що наведені формули є виконуваними

допомагають таблиці істинності для цих формул.

p ∨ q (p ∨ q) ⊃ p

іі іі

іх і і

хі іх

хх х і

Тавтології і протиріччя називають L-

детермінованими виразами (логічно детермінованими,

логічно спричиненими), а виконувані формули L-

недетермінованими (логічно недетермінованими).

Уміння розпізнавати і диференціювати формули за се-

мантичними ознаками передує розгляду різноманітних

відношень між формулами у системі S

4. Рівносильні формули

При аналізі множини формул в S

нерідко зустрічають-

ся ситуації, коли різні за структурою формули при одна-

кових наборах значень пропозиційних змінних приймають

однакове значення.

А. Є. Конверський. ЛОГІКА

322

Наприклад, візьмемо дві формули : (p ⊃ q) i ( p ∨ q). По-

будуємо для них таблиці істинності.

p ⊃ q

ііі

іхх

хі і

хх і

p p ∨ q

ііхі

іххх

хі і і

ххі і

Ці формули (та їм подібні) називають р і в н о с и л ь -

н и м и.

Дефініція. «Нехай А і В – формули, а х

, х

,... х

список усіх пропозиційних змінних, що входять, в край-

ньому разі, до складу однієї із них. При наявності цих

вихідних даних вважається, що формули А і В – рів-

носильні, якщо при будь-яких наборах значень х

, х

,... х

логічні значення формул А і В співпадають».

З цього визначення випливає, що рівносильними будуть

не тільки ті формули, до складу яких входять одні й ті са-

мі пропозиційні змінні, але й такі, в яких пропозиційні

змінні різняться. Наприклад:

p & (p ⊃ q) i 2) p ⊃ ( p & r)

pqr

pp ⊃ q p & (p ⊃ q) p & r

p ⊃ (

p & r)

іііхіххх

іхіххххх

ііххі ххх

і ххх х х х х

хііі і і і і

хх і і і і і і

хіхі і і х і

ххх і і і х і

Книга друга. СУЧАСНА ЛОГІКА

323

Незважаючи на те, що формули 1 і 2 різняться змінни-

ми q i r, їхні таблиці істинності співпадають. Це дає під-

ставу стверджувати, що логічні значення формули А не

залежать від пропозиційної змінної х

, якщо для будь-

якого набору логічних значень решти пропозиційних змін-

них у таблиці істинності для А логічне значення А одне й

те саме, коли х

хибне і коли х

істинне.

Для відношення рівносильності характерними є:

1) Рефлексивність (А рівносильне А);

2) Симетричність (якщо А рівносильне В, то В рівно-

сильне А);

3) Транзитивність (якщо А рівносильне В і В рівно-

сильне С, то А рівносильне С).

Термін «рівносильно» є виразом метамови. Якщо поєд-

нати дві рівносильні формули знаком еквіваленції, то

отримаємо тотожно-істинну формулу або закон логіки.

Тобто, якщо А і В рівносильні, то формула А∾ В буде

логічним законом, що записується так:

|= А ∾ В (або #А ∾ В).

Законів логіки (тобто тавтологій) в S

може бути скіль-

ки завгодно. Але можна виділити кілька десятків тавтоло-

гій, за допомогою яких здійснюються всі дії в системі S

Ці вирази легко можна перевірити за допомогою таблиць

істинності.

Разом з тим, побудова таблиць істинності досить громіз-

дка справа для визначення завжди істинних формул.

Розв’язання цієї задачі досягається в еквівалентних пере-

твореннях вихідних формул за допомогою законів логіки.

Розглянемо основні закони логіки висловлювань, які

записані засобами метамови в S

1. Закон подвійного заперечення:



AA ≡ (читається: те, що не є не-А є те ж саме, що А).

2. Закон комутативності:

Назва цього закону походить від латинського слова

commutativus, що у перекладі означає змінюваність, той,

що піддається переміщенню. Суть цього закону полягає у

тому, що результат операції з двома елементами не

залежить від порядку, в якому беруться ці елементи.

Властивість комутативності притаманна операціям & i ∨.

A & B ≡ B & A

(читається: А і В є те саме, що й В і А)

А ∨ В ≡ В ∨ А

(читається: А або В є те саме, що й В або А).

А. Є. Конверський. ЛОГІКА

324

3. Закон асоціативності:

Назву цьому закону дає латинське слово associatio, що у

перекладі означає з’єднання. Суть закону асоціативності

полягає в тому, що при подвійному здійсненні операції

над трьома висловлюваннями можна з’єднати (асоцію-

вати) перше і друге висловлювання, виконати операцію

над ними, а потім цю ж операцію провести над отри-

маним результатом і третім висловлюванням. Рівно-

цінним є й такий порядок здійснення операцій: з’єднати

друге і третє висловлювання, провести операцію над

ними, а потім цю ж операцію провести над отриманим

результатом і першим висловлюванням.

Асоціативність властива для & i ∨.

(А & В) & С ≡ А & (В & С)

(читається: (А і В) і С є те саме, що й А і (В і С)).

(А ∨ В) ∨ С ≡ А ∨ (В ∨ С) (читається: (А або В)

або С є те ж саме, що й А або (В або С)).

4. Закон дистрибутивності:

Назва цього закону походить від латинського слова

distributio, що у перекладі означає розміщення, розподі-

лення. Із формули закону видно, що тут відбувається

розподілення, розміщення першого висловлювання сто-

совно другого, а потім першого відносно третього. Ре-

зультати цього розміщення об’єднуються через (∨).

Існує два варіанти цього закону:

 «закон дистрибутивності кон’юнкції відносно

диз’юнкції»:

A & (B ∨ C) ≡ (A & B) ∨ (A & C)

(читається: А і (В або С) є те саме, що й (А і В) або (А і С)).

 «закон дистрибутивності диз’юнкції по відношен-

ню до кон’юнкції»:

А ∨ (В & С) ≡ (А ∨ В) & (А ∨ С)

(читається: А або (В і С) є те саме,

що й (А або В) і (А або С)).

5. Закон ідемпотентності:

Назва цього закону походить від латинського слова

idempotens, що у перекладі означає зберігаючий той самий

степінь. Суть цього закону полягає в тому, що якщо

кон’юнкцією чи диз’юнкцією сполучаються дві однакові

змінні, то одну змінну можна виключити:

А & А ≡ А (читається: А і А є те саме, що й А);

А ∨ А ≡ А (читається: А або А є те саме, що й А).

Книга друга. СУЧАСНА ЛОГІКА

325

Розглянемо чотири закони відносно завжди істинних і

завжди хибних формул.

Завжди істинну формулу (або тавтологію) позначи-

мо символом (⊤), а завжди хибну формулу – (⊥).

6. Закон виключення тавтології із кон’юнкції.

Суть цього закону полягає в тому, що кон’юнктивне

приєднання до виконуваної (нейтральної, або довільної)

формули А тавтології не додає до цієї формули ніякої

нової інформації. Тобто, згідно з природою (&), значення

формули А & ⊤ цілком залежить від значень формули А:

А & ⊤ ≡ A.

7. Закон перетворення кон’юнкції в протиріччя.

Цей закон виражає, що в силу природи кон’юнкції,

якщо один із кон’юнктів завжди хибний (⊥), то вся

кон’юнкція стає завжди хибною:

А & ⊥ ≡ ⊥.

8. Закон перетворення диз’юнкції в тавтологію.

Відомо, що коли один із диз’юнктів завжди істинний,

то вся диз’юнкція зажди буде істинною (⊤):

А ∨ ⊤ ≡ ⊤.

9. Закон виключення протиріччя із диз’юнкції.

Якщо приєднати диз’юнктивно до довільної формули

А завжди хибну формулу, то в силу природи диз’юнкції

значення утвореної формули А ∨ ⊥ залежатиме від до-

вільної формули А:

А ∨ ⊥ ≡ А.

10. Перший закон де-Моргана, або заперечення кон’ю-

нкції:

.& BABA ∨≡

11. Другий закон де-Моргана, або заперечення диз’ю-

нкції:

.)( BABA ∨≡∨

Суть законів де-Моргана полягає в перенесенні запе-

речень, застосованих до складних висловлювань, на про-

сті висловлювання, що їх складають.

А. Є. Конверський. ЛОГІКА

326

12. Закон виразу кон’юнкції через диз’юнкцію:

.)(& BABA ∨≡

13. Закон виразу диз’юнкції через кон’юнкцію:

.)&( BABA ≡∨

14. Закон виключення імплікації:

А ⊃ В ≡

∨ В.

15. Закон заміни еквіваленції:

А ∾ В ≡ (А ⊃ В) & (B ⊃ A).

16. Закон заміни сильної диз’юнкції:

А ∨ В ≡ (А ∨ В) & (

∨

«Закони виявлення»:

17.

() ()

BABAABA &&& ∨≡∨

18.

() ()

BABAABA ∨∧∨≡∧∨

19.

()

CBCABACABA ∨∨∨≡∨ &&&&

20.

()

CBCABACABA &&&&& ∨∨≡∨

«Закони поглинання»:

21.

()

BBABA ≡∨∨ &

22.

()

AABA ≡∨ &

23.

()

AABA ≡∨&

«Нехай А – деяка формула, і А′ отримується із А за-

міною хоча б одного входження підформули В у форму-

лу А на В′. Тоді, якщо В′ рівносильна В, то формула А′

рівносильна А». Це правило називається «правилом за-

міни рівносильності».

Застосовуючи це правило, можна переходити від одних

формул до інших, які їм рівносильні.

Наведені закони 1–23 обгрунтовуються таблицями іс-

тинності. Але, використовуючи ці закони, не звертаючись

до таблиць істинності, а керуючись правилом заміни, мо-

жна встановити рівносильність будь-якої формули.

Наприклад, візьмемо формулу

.)( CBA ⊃∨

Книга друга. СУЧАСНА ЛОГІКА

327

Відповідно до другого закону де-Моргана (11) замінимо

у цій формулі антецедент:

.)&( CBA ⊃

Отримана формула рівносильна вихідній. Згідно з законом

виключення імплікації (14) замінимо цю формулу рівно-

сильною їй:

.)&( CBA ∨

Підформулу )&( BA замінимо згідно з першим законом

де-Моргана (10):

.CBA ∨∨

Тепер застосуємо закон подвійного заперечення (1):

А ∨ В ∨ С.

В силу транзитивності відношення рівносильності отри-

мана формула є рівносильною всім попереднім.

Користуючись правилом заміни, будь-яку формулу

можна перетворювати в рівносильну їй таким чином,

щоб вона не містила одних логічних сполучників, але

містила інші.

Наприклад, використовуючи закони 14, 15, 16 за пра-

вилом заміни формулу, яка містить знаки ⊃, ∾, ∨, можна

перетворити на формулу, в якій відсутні ці знаки. Таким

способом, підбираючи відповідні закони, можна отримува-

ти формули, які містять лише & і , або ∨ і , або ⊃ і .

5. Логічні відношення між формулами

Поряд із виділенням логічних законів у системі S

розв’язується ще одна задача, яка встановлює логічні від-

ношення (за істинністю і хибністю) між формулами.

В якості фундаментальних логічних відношень у S

виділяють:

 відношення сумісності за істинністю;

 відношення сумісності за хибністю;

 відношення логічного слідування.

Дефініція: «Формули деякої множини Γ

є сумісними

за істинністю в S

тоді і тільки тоді, якщо в S

існує

Г – це метазнак, який використовується для позначення множини довіль-

них формул.

А. Є. Конверський. ЛОГІКА

328

інтерпретація нелогічних символів, які входять до

складу вказаних формул, при якій кожна формула із

приймає значення «істина». У протилежному випадку

формули будуть несумісними за істинністю».

Дефініція. «Формули із множини

є сумісними за

хибністю в S

тоді і тільки тоді, якщо в S

існує інтер-

претація нелогічних символів, що входять до складу

вказаних формул, при якій кожна формула із Г приймає

значення «хиба». У протилежному випадку ці формули

будуть несумісними за хибністю».

Найбільш важливим є відношення логічного слідування.

Дефініція. «Із множини формул

логічно слідує фор-

мула В у S

тоді і тільки тоді, якщо в S

не існує ін-

терпретації нелогічних символів, що входять до

і до

В, при якій кожна формула із

приймає значення «іс-

тина», а формула В – значення «хиба». У протилеж-

ному випадку В не слідує із Г».

Твердження «Із Г слідує В» записується так:

Г |= В.

Щоб краще зрозуміти логічні відношення між форму-

лами в S

звернемося до прикладів.

Візьмемо формули p ∨ q, q ⊃ r, p ∨ r і побудуємо для

них спільну таблицю істинності, щоб розглянути названі

логічні відношення.

pqr

р ∨ qq ⊃ r р ∨ r

іііііі

ііх

іхі

іхіііі

іххііі

хііііі

хіхіхх

ххі хі і

ххх

хіх

Розглянемо, які ж логічні відношення мають місце між

наведеними формулами. Критерієм сумісності за істинніс-

тю, хибністю та логічним слідуванням будуть вище наве-

дені дефініції.

Якщо в спільній таблиці істинності знайдеться, у

крайньому разі, один рядок, в якому кожна формула

Книга друга. СУЧАСНА ЛОГІКА

329

приймає значення істинності «і», то ці формули вва-

жаються сумісними за істинністю. У протилежному

випадку вони не будуть сумісними за істинністю.

Якщо у спільній таблиці істинності знайдеться хоча

б один рядок, де кожна формула приймає значення хиб-

ності «х», то ці формули сумісні за хибністю. У про-

тилежному випадку вони не будуть сумісні за хибніс-

тю.

Якщо потрібно з’ясувати, чи слідує із формул А

, ... А

формула В, будується спільна таблиця істин-

ності. Якщо у побудованій таблиці відсутній рядок в

якому формули А

, А

,... А

одночасно істинні, а форму-

ла В – хибна, то А

, А

,... А

|= В.

Із складеної таблиці істинності очевидно, що формули

p ∨ q, q ⊃ r, p ∨ r сумісні за істинністю. Свідченням цьо-

го є рядки: 1, 3, 4 і 5.

Але ці формули несумісні за хибністю, оскільки немає

жодного рядка, де б кожна формула приймала значення

«х».

Формула p ∨ r логічно слідує із формул p ∨ q, q ⊃ r,

оскільки в таблиці істинності немає жодного рядка де б

p ∨ q i q ⊃ r приймали значення «і», а формула p ∨ r –

«х». Записується це так:

(p ∨ q, q ⊃ r |= p ∨ r)

Формула p ∨ q не слідує із формул q ⊃ r i p ∨ r, оскі-

льки у сьомому рядку наведеної таблиці істинності форму-

ли q ⊃ r i p ∨ r істинні, а формула p ∨ q – хибна. Запису-

ється це так:

(q ⊃ r, p ∨ r  |= p ∨ q)

Таким способом можна розглядати логічні відношення

між будь-якими формулами в системі S

6. Нормальні форми логіки висловлювань

Серед нормальних форм логіки висловлювань виді-

ляють:

а) кон’юнктивну нормальну форму (КНФ);

б) диз’юнктивну нормальну форму (ДНФ);

в) досконалу кон’юнктивну нормальну форму (ДКНФ);

г) досконалу диз’юнктивну нормальну форму (ДДНФ);

д) скорочену кон’юнктивну нормальну форму (СКНФ);

е) скорочену диз’юнктивну нормальну форму (СДНФ).

А. Є. Конверський. ЛОГІКА

330

Кожна із цих формул має свій власний спосіб утворення

і розв’язує характерні для неї задачі.

а) Кон’юнктивна нормальна форма (КНФ)

Перш ніж аналізувати КНФ зробимо одне зауваження.

У сучасній логіці існує таке поняття як «проблема

розв’язання». Воно уточнюється стосовно кожного розділу

сучасної логіки. В алгебраїчній системі логіки висловлю-

вань цю проблему можна визначити так:

«Проблема розв’язання – це встановлення ефектив-

ної процедури, яка кінцевим числом кроків дозволяє

встановити чи є дана формула тотожно-істинною, чи

тотожно-хибною, чи виконуваною».

У S

такими процедурами є:

1) побудова таблиць істинності і

2) зведення формули до КНФ і ДНФ.

Про таблиці істинності йшлося вище. Розглянемо КНФ.

Кон’юнктивною нормальною формою (КНФ) є

кон’юнкція елементарних диз’юнкцій.

КНФ записується так:

1) (А ∨ В) ∧ (

A ∨ С),

2) (А ∨ В) ∧ С тощо.

У другій формулі кон’юнктивний член С розглядається

як вироджена диз’юнкція з одним диз’юнктом. Будь-яку

формулу логіки висловлювань можна звести до КНФ.

Для того щоб звести формулу до КНФ необхідно ви-

конати такі дії:

1. За допомогою відповідних законів треба звільнити-

ся від ∨, ∾, ⊃, якщо вони наявні у вихідній формулі.

2. Усунути загальне заперечення і подвійне запере-

чення відповідно конкретних законів.

3. До отриманої формули застосувати закон дис-

трибутивності диз’юнкції по відношенню до кон’юнкції.

За допомогою КНФ розв’язуються такі задачі:

1) є дана формула тотожно-істинною чи ні;

2) чи є формула С наслідком із формул А

, А

,... А

Розглянемо зведення формули до КНФ на такому при-

кладі:

()

[]

BCACBA ∨∧⊃⊃∧ )( .

До цієї формули застосовуємо закон виключення імплі-

кації:

()

[]

BCACBA ∨∧⊃⊃∧ )( .