Символи, формули, аксіоми числення висловів.
Правила виведення
Розглянемо формальну аксіоматичну систему, в деякому сенсі адекватну алгебрі висловлювань. Назвемо цю систему обчисленням висловлювань.
Щоб побудувати обчислення, потрібно визначити алфавіт обчислення, поняття формули, клас формул, які називаються аксіомами, правила виведення даного числення.
Великі латинські літери А, В, С. X, Y, Z. які назвемо змінними висловлюваннями.
Символи операцій обчислення Ù, Ú, ®, ¾ (знак кон'юнкції, диз'юнкції, проходження і заперечення).
Інших символів система числення висловів не містить.
Формулою в обчисленні висловлювань є деяка послідовність символів. Але не всяка послідовність символів є формула. Наприклад, послідовності А → В (С →) і (А В) не є формулами. Визначення формули в численні висловів задається наступним чином:
1. Будь-яке змінне висловлювання є формула.
2. Якщо a, b є формули, то вирази виду (aÙb),. . (aÚb), (a®b) також є формулами.
Задамо в обчисленні висловлювань клас вихідних істинних формул-аксіом.
Правила виведення дозволяють з даної системи аксіом отримувати інші справжні формули обчислення висловлювань. Назвемо формулу обчислення висловлювань помилковою, якщо її заперечення істинно. Будемо позначати справжні формули буквою R, помилкові - F.
До основних правил виведення відносяться два:
1) Правило висновку.
Якщо a і (a®b) - справжні формули, то b також істинна. Ця пропозиція можна записати у вигляді
2) Правило підстановки
Нехай деяка формула a містить змінне висловлювання А. Тоді, замінивши вислів А всюди, де воно зустрічається, будь формулою b, отримаємо справжню формулу. Ця пропозиція записується у вигляді.
Формула називається виведеної в обчисленні висловлювань, якщо її можна отримати, застосовуючи правила виводу до аксіом числення висловів. Твердження, що формула b виведена, записують так:
Процес отримання формул з аксіом числення висловів називається формальним висновком. Формальний висновок складається з вказівки того, які правила, в якому порядку і до якими формулами застосовується для виведення цієї формули.
Доведемо, що виведена формула А®А, тобто А®А.
1. Запишемо аксіому 2 з групи I.
2. Застосуємо до неї правило підстановки. тобто
3. Зауважимо, що a є справжня формула, як аксіома з групи I, тобто маємо справжні формули a і a®b. Застосуємо правило укладення і отримаємо (А ®) ® (А®А).
4. Застосуємо правило підстановки до отриманої формулі, замінивши вислів В на:
5. Але. є аксіома 2 з групи IV. Застосуємо до отриманої формулою правило ув'язнення. тобто -А®А.
Кажуть, що формула b виведена з формул a1. a2. an. якщо формулу b можна вивести шляхом правила укладання, прийнявши за вихідні формули a1. a2. an і всі справжні в обчисленні висловлювань формули. Виводимість формули b з формул a1. a2. an записують у вигляді a1. a2. an. b.
Якщо формула b виведена з формул a1. a2. an. то виведеної є формула a1 ® (a2 ® (. (an ®b).)), тобто
Теорема дедукції дає можливість встановити виводимість різних формул обчислення висловлювань простішим шляхом, ніж прямий вихід цих формул з аксіом за допомогою правил виведення. За допомогою теореми дедукції виводяться основні правила обчислення висловлювань:
1. Правило силогізму. Якщо формули (a®b) і (b®g) істинні, то формула (a®g), тобто
2. Правило перестановки посилок. Якщо формула (a® (b®g)) істинна, то істинної є формула (b® (a®g)), тобто ;
3. Правило з'єднання посилок. Якщо істинної є формула (a® (b®g)), то істинної буде формула (aÙb®g), тобто .
Проблеми несуперечності, повноти,
незалежності аксіом числення висловів
Використовуємо алгебру висловлювань як деяку модель обчислення висловлювань. Формули обчислення висловлювань будемо трактувати як формули алгебри висловлювань. Для цього всі букви, що входять в алфавіт числення висловів, будемо вважати змінними висловлюваннями в змістовному сенсі, тобто змінними, які приймають значення І та Л. Символи алфавіту Ù, Ú, ®, ¾. - будемо розуміти як логічні зв'язки алгебри висловлювань.
При цьому справедлива наступна теорема.
Всі аксіоми числення висловів є тотожно істинні формули алгебри висловлювань. Всі формули, що виводяться з аксіом числення висловів, є тотожно істинні формули алгебри висловлювань.
Доказ першої частини теореми можна провести безпосередній перевіркою.
У справедливості другої частини теореми можна переконатися, довівши, що, застосовуючи правило укладення та правило підстановки до тотожно істинною формулою алгебри висловлювань, отримуємо тотожне справжню формулу. Отже, будь-яка виведена в обчисленні висловлювань формула є тотожно істинна формула алгебри висловлювань.
При розгляді будь-якої формальної логічної системи, в тому числі обчислення висловлювань, виникає три проблеми: несуперечливість, повнота, незалежність системи аксіом числення.
Логічне числення вважається несуперечливим, якщо в ньому не виводяться ніякі дві формули, з яких одна є запереченням іншого.
Проблема несуперечності полягає в тому, що слід з'ясувати, є дане обчислення несуперечливим.
Якщо в обчисленні можна вивести деяку формулу a і її заперечення. то таке обчислення буде суперечливим. Якщо логічне числення суперечливо, в ньому буде виведена будь-яка формула. Таке обчислення не представляє цінності, тому що воно не здатне відображати в собі відмінність між істиною і брехнею.
Для доказу несуперечності логічного обчислення досить знайти в ньому хоча б одну невиводимість формулу. У численні висловів проблема несуперечності вирішується так.
Теорема I. Обчислення висловлювань несуперечливо.
Справедливість цього твердження випливає з попередньої теореми. Справді, нехай a - деяка виведена в обчисленні висловлювань формула. Отже, вона тотожно істинна, якщо її розглядати як змістовну формулу алгебри висловлювань. Тоді - тотожне помилкова, тобто не виводиться при всіх значеннях вхідних в неї змінних. Отже, a і не можуть бути разом виведеними в обчисленні висловлювань.
Отже, будь-яка виведена формула в обчисленні висловлювань є тотожно істинною, якщо цю формулу обчислення висловлювань розглядати як змістовну формулу алгебри висловлювань. Виникає зворотне завдання.
Чи буде будь-яка тотожно істинна формула алгебри висловлювань виводиться з аксіом числення висловів.
Це завдання є проблему повноти обчислення висловлювань в широкому сенсі.
Для будь-якої логічної системи визначення повноти в широкому сенсі слова можна сформулювати наступним чином: логічне числення називається повним, якщо будь-яку справжню в змістовному сенсі формулу можна вивести за правилами обчислення з аксіом числення.
Для обчислення висловлювань проблема повноти вирішується позитивно.
Теорема II. Система числення висловів є повною.
Не менш важливим є визначення повноти логічної системи у вузькому сенсі слова. Логічне числення називається повним у вузькому сенсі слова, якщо додавання до системи аксіом деякої невиводимість в цьому обчисленні формули робить обчислення суперечливим. Обчислення висловлювань є повним також у вузькому сенсі слова.
Для будь-якої логічної системи виникає проблема незалежності аксіом даного обчислення. Задамося питанням, чи можна будь-яку аксіому обчислення вивести з інших аксіом за допомогою правил виведення даної системи. Якщо це можливо, то аксіому, виведену з інших аксіом, можна викреслити зі списку аксіом даного обчислення. Аксіома, не виводиться з інших аксіом, називається незалежної з цих аксіом. Система аксіом, в якій жодна аксіома не виводиться з інших, називається незалежною системою аксіом.
Ця проблема для обчислень вирішується позитивно.
Теорема III. Система аксіом числення висловів незалежна.
Проблема незалежності системи аксіом логічного обчислення є дуже важливою математичної проблемою, яка призводить іноді до питання про заміну будь-якої аксіоми її запереченням. Як приклад можна привести питання про незалежність п'ятого постулату Евкліда в системі аксіом геометрії, питання про незалежність аксіоми Цермело в системі аксіом теорії множин. Питання ці мали велике значення в розвитку математики.
Для визначення поняття предиката розглянемо такі приклади.
1. Нехай N - безліч натуральних чисел, і буквою P позначено властивість натурального числа бути простим. Якщо x є довільний елемент з N, тоді вираз «натуральне число x є простим», яке можна записати у вигляді P (x), вже не є висловлюванням, тому що значення істинності цього твердження залежить від x. По суті P (x) означає змінну (невизначений) висловлювання, яке стає певним, коли x замінено певним елементом з N. Наприклад, P (3) = 1, P (4) = 0. Інакше кажучи, P (x) являє собою функцію, певну на безлічі натуральних чисел і приймаючу тільки два значення: 0 і 1.
2. Нехай Z - безліч цілих чисел і P - властивість пари чисел мати однаковий знак. Тоді P (x, y) буде означати: «цілі числа x і y мають однаковий знак». Це невизначений вислів стає певним, якщо x і y замінити конкретними числами. Наприклад, P (2,3) = 1, P (-1,5) = 0. Невизначений висловлювання P (x, y) представляє собою функцію двох змінних.
3. Нехай A і B - безліч точок, C - безліч прямих на евклідової площини, а P (a, b, c) позначає: «пряма c проходить через точки a і b». У цьому прикладі ми маємо справу з функцією трьох змінних, причому a і b приймають значення з безлічі точок, а c приймає значення з безлічі прямих евклідової площини.
Визначення 1. Предикатом називається функція, що відображає безліч довільної природи в безліч, або (помилково, істинно).
Звернемося тепер до визначення предиката в загальному випадку.
Визначення 2. Нехай N = 1, N2, N3, ..., Nn> - кінцевий набір множин. Будь-яка функція P (X1, ..., Xn), що ставить у відповідність кожному набору з n елементів 1, a2, ..., an), де ai ÎNi. будь-якої з елементів булевої алгебри називається n-місцевим предикатом на N. Безліч Ni називається предметною областю для змінної xi. Змінні x1, ..., xn називаються предметними змінними. Деякі з безлічі Ni можуть збігатися.
Якщо при відображенні P чином набору (a1, a2, ... an) є одиниця, то записують.
і кажуть, що значення предиката P для набору (a1, ..., an) є істинним. Якщо ж чином (a1, ..., an) є нуль, то записують
і кажуть, що значення предиката P для набору (a1, ..., an) є помилковим.
n - місцевий предикат при n = 1 називається унарним, при
n = 2 - бінарним і при n = 3 тернарного. Для спільності введемо ще поняття 0-місцевого предиката, а саме, 0- місцевим предикатом називається любе істинне або помилкове висловлювання.
Оскільки предикати приймають значення з (0,1), то над ними можна робити все логічні операції, що розглядаються нами в алгебрі висловлювань (-, Ù, Ú, ®, «), зберігаючи за ними ті ж визначення. Крім операцій алгебри висловлювань, ми будемо вживати ще дві нові операції, які пов'язані з особливостями предикатів і висловлюють собою затвердження загальності та існування.
Нехай P (x) - одномісний предикат, заданий на деякій множині M. Якщо змінна x позначає будь-який елемент з безлічі M, то P (x) є невизначеним висловом.
Операція "ставить у відповідність невизначеному висловом P (x) висловлювання" xP (x), яке читається так: «для будь-якого x має місце P (x)» і за визначенням є істинним тоді і тільки тоді, коли P (x) істинно для будь-якого елементу xÎM. Перехід від невизначеного висловлювання P (x) до вислову "xP (x) називається операцією навішування квантора спільності за предметним змінним x.
Операція $ ставить у відповідність невизначеному висловом P (x) висловлювання $ xP (x), яке читається так: «існує таке x, що має місце P (x)» і за визначенням є істинним тоді і тільки тоді, коли P (x) істинно хоча б для одного елемента xÎM. Перехід від невизначеного висловлювання P (x) до висловлення $ xP (x) називається операцією навішування квантора існування за предметним змінним x.
У першому випадку ми говоримо, що предметна змінна x пов'язана в предикате P (x) квантором загальності, у другому випадку - квантором існування.
Визначимо операції навішування квантора для загального випадку n-місного предиката P (x1, ..., xn). Операції навішування кванторів "і $ по змінному x1 (в загальному випадку по змінному xi. Де I =) ставить у відповідність предикату P (x1, ..., xn) (n-1) - місцеві предикати
Істинності значення цих предикатів визначаються для фіксованих наборів значень предметних змінних x2, ..., xn наступним чином:
У загальному випадку, якщо k Розглянемо предикат Д (x1, x2) - «число x1 ділиться на число x2», певний на безлічі натуральних чисел. Тоді операція навішування кванторів приводить до наступних тверджень: 1. "x1 Д (x1, x2) -« для будь-якого x1 має місце Д (x1, x2) », тобто будь-яке x1 ділиться на x2. Цей предикат приймає значення істини тільки для х2 = 1. 2. $ x1 Д (x1, x2) - «існує x1, яке ділиться на x2». Цей предикат приймає значення істини для будь-якого значення x2. 3. "x1" x2 Д (x1, x2) - «для всякого x1 і для будь-якого x2 має місце подільність x1 на x2. Це висловлювання є хибним. 4. $ x1 "x2 Д (x1, x2) -« існує x1. Яке ділиться на кожне x2 »- хибне висловлювання.Схожі статті