Зв’язки між формулами алгебри висловлень і формулами числення висловлень

Носієм алгебри висловлень є множина так званих простих висловлень.

Просте (елементарне) висловлення (висловлювання) - це просте твердження, тобто розповідне речення, щодо змісту якого доречно ставити питання про його правильність або неправильність.

Прості висловлення, в яких виражено правильну думку, називатимемо істинними, а ті, що виражають неправильну, - хибними.

Поняття простого (елементарного) висловлення, поняття істинності і хибності належать до первинних невизначальних понять математики, тобто вони не можуть бути означені через інші більш прості терміни та об’єкти, а пояснюються на прикладах, апелюючи до нашої уяви та інтуїції. До таких понять в математиці належать поняття «число», «пряма», «точка», «площина» тощо.

Наведемо декілька прикладів елементарних висловлень:

1) Київ - столиця України.

2) Число 7 є простим.

3) Число 10 більше від числа 3.

4) Усі натуральні числа є простими.

5) Множина всіх простих чисел є скінченною.

Перші три висловлення є істинними, а два останніх - хибними.

У той же час речення «Хай живе математична логіка!» або «Уважно прочитайте весь цей розділ» не є висловленнями.

Розглядаючи висловлення, виходитимо з двох основних припущень:

1) кожне висловлення є або істинним, або хибним (закон виключення третього);

2) жодне висловлення не є одночасно істинним і хибним (закон виключення суперечності).

Приймаючи ці припущення, ми стаємо на точку зору класичної (традиційної) двозначної логіки. У ХХ столітті виникли і продовжують досліджуватись так звані некласичні логіки: багатозначна логіка, інтуїціоністська (конструктивна) логіка, модальна логіка. У подальшому ми додержуватимемося принципів класичної логіки, в рамках якої проводитимуться всі математичні міркування.

Позначатимемо елементарні висловлення малими латинськими літерами: a, b, c,... (можливо, з індексами), а значення висловлень «Iстинно» і «Хибно» - відповідно символами 1 і 0 або I і Х.

Крім того, розглядатимемо так звані змінні висловлення, які позначатимемо латинськими літерами x, y, z,... (можливо, з індексами) і називатимемо також пропозиційними змінними. Після підстановки замість пропозиційної змінної певного елементарного висловлення ця змінна набуде відповідного значення: 0 або 1.

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

У таблиці 1 наведені різні назви та позначення, які використовують для зазначених операцій.

Назва

Позначення

Кон’юнкція Логічне множення Логічне «І»

Ù & ×

Диз’юнкція Логічне додавання Логічне «АБО»

Ú

Заперечення Логічне «НІ»

Ø - ¢

Імплікація Логічне слідування

® É

Ù

Ú

Ø

®

Застосовуючи до елементарних висловлень і пропозиційних змінних означені операції, діставатимемо складені висловлення, яким відповідатимуть так звані формули або вирази алгебри висловлень. Для запису цих формул, дослідження їхніх властивостей і співвідношень між формулами та висловленнями використовують формальні мови, тобто певні множини слів у деякому алфавіті.

Алфавіт найбільш поширеної формальної мови алгебри висловлень складається з трьох груп символів:

1) символи елементарних висловлень та пропозиційних змінних: a, b, c,... і x, y, z,... (можливо з індексами);

2) символи операцій: Ù,Ú,Ø,®;

3) допоміжні символи - круглі дужки: (і).

З пропозиційних змінних і елементарних висловлень за допомогою операцій і дужок будуються пропозиційні формули або просто формули алгебри висловлень за такими індуктивними правилами:

1) всі пропозиційні змінні та елементарні висловлення є формулами;

2) якщо A і B - формули, то вирази (A Ù B), (A Ú B), (Ø A), (A ® B) також є формулами;

3) інших формул, ніж побудовані за правилами 1) і 2), немає.

Традиційно формули алгебри висловлень позначають великими готичними літерами, але для зручності позначатимемо їх великими латинськими літерами.

Кожна формула A зображує форму або схему складеного висловлення: вона перетворюється у висловлення якщо замість її пропозиційних змінних підставити будь-які висловлення. Оскільки кожне з підставлених висловлень має значення 0 або 1, то послідовно обчислюючи значення всіх підформул формули A, одержимо значення формули A на цьому наборі висловлень, яке дорівнюватиме 0 або 1. Підставляючи у формулу A замість її пропозиційних змінних інший набір висловлень, аналогічним чином обчислимо нове значення формули A і т.д. Оскільки кожне з висловлень набору повністю характеризується своїм значенням (істинно або хибно, тобто 1 або 0), то замість пропозиційних змінних у формулу можна підставляти не самі висловлення, а їхні значення - 1 або 0.

Нехай p ₁, p ₂,..., p_n - це всі пропозиційні змінні, що входять у формулу A; будемо позначати цей факт A (p ₁, p ₂,..., p_n). Формулі A (p ₁, p ₂,..., p_n) поставимо у відповідність функцію f (p ₁, p ₂,..., p_n), що означена на множині Bⁿ (B ={0,1}) і приймає значення у множині B, тобто функцію типу Bⁿ ® B. Значення функції f на наборі значень a ₁, a ₂,..., a_n її змінних p ₁, p ₂,..., p_n дорівнює значенню формули A (p ₁, p ₂,..., p_n) при підстановці в неї замість пропозиційних змінних p ₁, p ₂,..., p_n значень a ₁, a ₂,..., a_n відповідно.

Зауважимо, що кількість елементів в області визначення функції f дорівнює 2 ⁿ, тобто |Pr₁ f |=2 ⁿ.

Функцію f називають функцією істинності для формули A або відповідного складеного висловлення. Для функції істинності може бути побудована так звана таблиця істинності цієї функції (див.таблицю 3).

p 1 p 2 ...... pn -1 pn	f (p 1, p 2,..., pn -1, pn)
0 0... 0 0 0 0... 0 1 0 0... 1 0 0 0... 1 1 ......................... 1 1... 1 0 1 1... 1 1	f (0,0,...,0,0) f (0,0,...,0,1) f (0,0,...,1,0) f (0,0,...,1,1) ..................... f (1,1,...,1,0) f (1,1,...,1,1)

Серед формул алгебри висловлень особливе місце займають ті формули A (p ₁, p ₂,..., p_n), які на всіх наборах (a ₁, a ₂,..., a_n) значень своїх змінних набувають значення 1.

Формула алгебри висловлень A (p ₁, p ₂,..., p_n) називається тавтологією тоді і тільки тоді, коли їй відповідає функція істинності, яка тотожно дорівнює 1.

Тавтології ще називають тотожно істинними формулами, або законами алгебри висловлень. Аналогом тавтології у природній мові є поняття істинного твердження.

Числення висловлень (ЧВ) згідно з поданою у розділі 1 схемою означається таким чином.

1. Алфавіт числення висловлень складається з елементарних і змінних висловлень (пропозиційних змінних): a, b, c, d,..., x, y, z (можливо з індексами), знаків логічних операцій Ú,Ù,Ø,® і круглих дужок (та).

2. Поняття формули означається аналогічно алгебрі висловлень.

а) всі пропозиційні змінні та елементарні висловлення є формулами;

б) якщо A і B - формули, то вирази (слова) (A Ù B), (A Ú B), (Ø A), (A ® B) також є формулами;

в) інших формул, ніж побудовані за правилами а) і б) немає.

Відзначимо важливу властивість даного означення. Можна довести, що існує формальна процедура, яка, будучи застосована до будь-якого слова у розглядуваному алфавіті, за скінченну кількість кроків встановить, чи є дане слово формулою, чи ні. Більш того, за записом формули ця процедура дасть повний її синтаксичний розбір, тобто дасть опис послідовності кроків побудови формули за означеними вище правилами.

Зауважимо також, що з метою зменшення кількості (економії) дужок у формулах вводять порядок виконання (або пріоритети, старшинство) операцій. Зокрема, звичайно, опускають зовнішні дужки формул та замість (Ø A) записують Ø A;

3. Аксіомами числення висловлень будуть такі формули:

A 1. a ®(b ® a)

A 2. (a ® b)®((a ®(b ® c))®(a ® c))

A 3. (a Ù b)® a

A 4. (a Ù b)® b

A 5. (a ® b)®((a ® c)®(a ®(b Ù c)))

A 6. a ®(a Ú b)

A 7. b ®(a Ú b)

A 8. (a ® c)®((b ® c)®((a Ú b)® c))

A 9. (a ®Ø b)®(b ®Ø a)

A 10. ØØ a ® a

4. Правилами виведення є:

1) правило підстановки. Якщо A - вивідна формула, яка містить літеру p (позначимо цей факт A (p)), то вивідною є і формула A (B), що здобувається з A заміною всіх входжень літери p на довільну формулу B; записується

A (p)

A (B)

2) правило висновку (modus ponens). Якщо A і A ® B - вивідні формули, то вивідною є й формула B; записується

A, A ® B

B

У поданому описі числення висловлень аксіоми є формулами числення (відповідними до означення формули); формули, що використовують у правилах виведення (A, A ® B тощо), є метаформулами, або так званими схемами формул.

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

Наприклад, для схеми формул A ® B, якщо замінити A на p, а B - на p Ù q, то з даної схеми отримаємо формулу числення p ®(p Ù q); якщо ж метазмінну A замінити на p ® q, а B - на (p Ù q)® p, то дістанемо формулу (p ® q)®((p Ù q)® p) тощо.

Використання схем формул можна поширити і на всі аксіоми. Наприклад, якщо в системі аксіом пропозиційні змінні a, b, c замінити метазмінними A, B, C, то отримаємо десять схем аксіом, що задають десять нескінченних множин аксіом. Таким чином приходимо до іншого способу побудови числення висловлень: з нескінченною множиною аксіом (що задається скінченним числом схем аксіом), але без правила підстановки, оскільки воно неявно міститься у поясненні (інтерпретації) схем аксіом.

Перший спосіб є більш послідовно конструктивним: всі його засоби явно зафіксовані і скінченні; при введенні числення в ЕОМ (наприклад, для автоматизації доведень теорем та побудови виведень для заданих формул) він виглядає природнішим.

З іншого боку, другий спосіб більш відповідає математичній традиції тлумачення (інтерпретації) формул: наприклад, алгебраїчна тотожність (a + b)²= a ²+2 ab + b ² або відомі логарифмічні чи тригонометричні тотожності тлумачаться саме як схеми тотожностей, а не конкретні тотожності, справедливі лише для конкретних літер. Правило підстановки при цьому мається на увазі і присутнє неявно. Втім, досить очевидно, що перехід від одного способу побудови числення до іншого є нескладним.

Аксіоми числення висловлень разом з правилами виведення повністю визначають поняття довідної (вивідної) формули у ЧВ, або теореми ЧВ.

Вивідними формулами, або теоремами числення висловлень є ті і тільки ті формули, які можуть бути виведені з аксіом за допомогою означених правил виведення.