Рівнює кон’юнкції взаємно обер)

нених імплікацій, утворених з цих висловлень.

Доведення цієї властивості проведемо з допомогою таблиці

значень логічної вартості.

А В А ∼ В

1 1 1

1 0 0

0 1 0

0 0 1

А В А ∼ В А⇒В В⇒А (А⇒В) ∧ (В⇒А)

1 2 3 4 5 6

1 1 1 1 1 1

1 0 0 0 1 0

0 1 0 1 0 0

0 0 1 1 1 1

Співставивши значення логічної вартості висловлень в ко_

лонках під номерами 3 і 6, встановлюємо, що вони рівні. А отже,

властивість доведена.

Розглянемо приклад еквіваленції.

Нехай дано два висловлення:

А: “число 15 ділиться на 5”,

В: “число 15 закінчується цифрою 0”. А=1, В=0.

Утворимо з допомогою слів “тоді і тільки тоді”, або “рівно_

сильне” складені висловлення з даних висловлень:

А ⇔ В:“Число 15 ділиться на 5 тоді і тільки тоді, коли воно

закінчується цифрою 0”, або ж

А ⇔ В:“Число 15 ділиться на 5 рівносильне тому, що воно

закінчується цифрою 0”.

Обидва складені висловлення є еквіваленцією простих вис_

ловлень, з яких перше істинне, а друге хибне, а згідно означен_

ня еквіваленції остання є хибною. (1⇔0=0).

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

Вище подано окремі властивості операцій над висловлен_

нями і їх доведення з допомогою таблиць значень логічної вар_

тості. Узагальнимо відомі властивості (закони) і розглянемо нові

закони, які зв’язують певні логічні операції.

1. Закон подвійного запер A еч = ен A ня висловлення:

.

2. Закон протиріччя: А ∧ A = 0.

Цей закон зв’язує висловлення з його запереченням опера_

цією кон’юнкції. В класичній формальній логіці його формулю_

ють так: судження, утворене з двох протилежних суджень, з до_

помогою сполучника “і”, завжди хибне. Інше формулювання за_

кону протиріччя: два протилежні судження не можуть бути од_

ночасно істинними.

3. Закон виключеного третього: А ∨ A = 1

Цей закон зв’язує висловлення з його запереченням опера_

цією диз’юнкції і у формальній логіці читається так:

з двох протилежних тверджень завжди одне є істинним.

Тому й говорять, що третього бути не може, бо або суджен_

ня істинне, а його заперечення хибне, або, навпаки, судження

хибне, а його заперечення істинне.

4. Закони комутативності диз’юнкції і кон’юнкції:

А ∨ В = В ∨ А;

А ∧ В = В ∧ А.

5. Закони асоціативності диз’юнкції і кон’юнкції:

( А ∨ В) ∨ С = А ∨ (В ∨ С);

(А ∧ В) ∧ С = А ∧ (В ∧ С).

Дистрибутивні закони, які зв’язують диз’юнкцію і ко)

Н’юнкцію.

Таких законів є чотири, але перш, ніж їх записати, нагадає_

мо, що в арифметиці дійсних чисел є два дистрибутивні (роз_

подільні) закони дії множення відносно додавання, а саме:

а) (а + в)•с = а•с + в•с, де а,в,с _ довільні дійсні числа.

Це правий дистрибутивний закон множення відносно дода_

вання, оскільки знак дії множення стоїть справа від знака дії до_

давання.

б) а•(в + с) = а•в + а•с _ лівий дистрибутивний закон мно_

ження відносно додавання.

Легко переконатись, що операції додавання і множення не є

рівноправними в цих законах, тому що, помінявши місцями

знаки операцій в рівностях (а) і (б), не одержимо нових пра_

вильних рівностей (законів). Справді, в арифметиці дійсних чи_

сел немає, наприклад, правого дистрибутивного закону дода_

вання відносно множення, бо

(а•в) + с ≠ (а + с)•(в + с).

Наприклад, (2•3) + 5 ≠(2 + 5)•(3 + 5), бо 11 ≠ 56.

Повернемось до логічних операцій. В математичній логіці

операції кон’юнкції і диз’юнкції рівноправні. Це означає, що коли

кон’юнкцію розглядати як операцію, аналогічну до множення, а

диз’юнкцію _ операцію, аналогічну до додавання, то мають місце

не тільки правий і лівий дистрибутивні закони кон’юнкції віднос_

но диз’юнкції, але й правий і лівий дистрибутивні закони диз’_

юнкції відносно кон’юнкції. Наведемо ці закони:

1) (А ∨ В) ∧ С = (А ∧ С) ∨ (В ∧ С) _правий дистрибутивний закон

кон’юнкції відносно диз’юнкції;

2) А ∧ (В ∨ С) = (А ∧ В) ∨ (А ∧ С) _ лівий дистрибутивний закон

кон’юнкції відносно диз’юнкції;

3) (А ∧ В) ∨ С = (А ∨ С) ∧ (В ∨ С) _ правий дистрибутивний закон

диз’юнкції відносно кон’юнкції;

4) А ∨ (В ∧ С) = (А ∨ В) ∧ (А ∨ С) _ лівий дистрибутивний закон

диз’юнкції відносно кон’юнкції.

Співставляючи закони 1) і 3) (для короткості не будемо

наводити повної їх назви, а скористаємось лише їх номера_

ми в поданому вище переліку), очевидно, що кожен з них може

бути одержаний з іншого (перший _ з третього, а третій _ з

першого) шляхом заміни знаків операцій: диз’юнкції (∨) на

кон’юнкції (∧) і навпаки.

Аналогічно закони 2) і 4) можуть бути отримані один з одно_

го таким самим способом. Це свідчить про рівноправність ло_

гічних операцій кон’юнкції і диз’юнкції, яку слід розуміти так:

якщо в правильних рівностях, які стосуються однієї операції,

замінити знак цієї операції на знак іншої, то одержимо нову

правильну рівність відносно іншої операції. В цьому можна пе_

реконатись на законах комутативності і асоціативності. Крім

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

операції кон’юнкцію і диз’юнкцію, поміняти знаки операцій (∨

на ∧ і ∧ на ∨), то одержимо нові правильні рівності.

Правило заміни знаків логічних операцій для одержання но_

вих правильних рівностей називається законом контрапозиції.

(За законом контрапозиції, власне, з одних дистрибутивних

законів одержуються інші).

Наведемо доведення одного з дистрибутивних законів, на_

приклад закону 4), а всі інші закони пропонуємо читачеві дове_

сти самостійно.

А ∨ (В ∧ С) = (А ∨ В) ∧ (А ∨ С)

Очевидно, що висловлення в п’ятій і восьмій колонках, які

отримані в результаті вказаних логічних операцій відповідно у

А В С В ∧ С А ∨ (В ∧ С) А ∨ В А ∨ С (А ∨ В) ∧ (А ∨ С)

1 2 3 4 5 6 7 8

1 1 1 1 1 1 1 1

1 1 0 0 1 1 1 1

1 0 1 0 1 1 1 1

1 0 0 0 1 1 1 1

0 1 1 1 1 1 1 1

0 1 0 0 0 1 0 0

0 0 1 0 0 0 1 0

0 0 0 0 0 0 0 0

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

ної вартості. А отже, справедливість лівого дистрибутивного

закону диз’юнкції відносно кон’юнкції доведена.

Ми доводили закон 4) шляхом співставлення на останньому

етапі результатів, отриманих окремо в лівій і правій частинах

рівності. (Аналогічно доводили інші властивості в процесі ознай_

омлення з логічними операціями). Але часто для завершення

доведення законів, властивостей чи формул користуються опе_

рацією еквіваленцією, яку виконують над висловленнями, отри_

маними в лівій і правій частинах рівності. Для цього доповнюють

таблицю ще однією колонкою, зверху якої записують формулу,

що доводять, причому знак = в ній замінюють на знак еквіваленції

(рівносильності): ∼ (або ⇔), а потім записують значення логічної

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

мо, еквіваленція може бути істинною чи хибною. Якщо в резуль_

таті еквіваленції висловлень, отриманих в лівій та правій части_

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

ведливість закону чи формули. Легко переконатись, що, допов_

нивши попередню таблицю істинності колонкою під номером 9),

в якій була б записана формула 4) у вигляді:

А ∨ (В ∧ С) ⇔ (А ∨ В) ∧ (А ∨ С), то всі значення логічної вартості

висловлення в тій колонці дорівнюють 1.

Формула, яка приймає істинні значення при всіх можливих зна_

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

називається тотожно істинною формулою, або тавтологією.

Всі вище розглянуті закони алгебри висловлень є тавтолог_

іями (тотожно істинними формулами). Зауважимо також, що

якщо при всіх можливих значеннях логічної вартості простих

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

цю формулу, приймає тільки хибні значення, то таку формулу

називають тотожно хибною, або суперечністю.

Закони де Моргана.

Шотландський математик Августус де Морган (1806_1871)

вперше сформулював закони, які стосуються операції запере_

чення диз’юнкції та кон’юнкції двох висловлень.

Є два закони де Моргана:

1) Заперечення диз’юнкціїї двох висловлень дорівнює кон’_

юнкції заперечень цих висловлень.

A ∨ B = A ∧ B

2)Заперечення кон’юнкції двох висловлень дорівнює диз’_

юнкції заперечень цих висловлень.

A ∧ B = A ∨ B

Доведемо один з цих законів (наприклад, другий) з допо_

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

рацію еквіваленції висловлень, одержаних в результаті виконання

вказаних операцій в кожній з частин рівності.

Колонка під номером 8 в таблиці свідчить про те, що при

всіх значеннях логічної вартості простих висловлень, які вхо_

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

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

А отже, формула є тотожно істинною, тобто тавтологією.

Перший закон де Моргана пропонується довести самостійно.

Зразки розв’язування вправ з теми “Висловлення і дії