Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп’ютерні науки
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Навчальний посібник
Предмет:
Дискретна математика
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
«ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Я.П. Романчук
ДИСКРЕТНА МАТЕМАТИКА
Конспект лекцій
Розглянутий на засіданні кафедри АСУ
як навчальний посібник для студентів
базового напрямку 050101 «Комп’ютерні науки»
денної та заочної форм навчання (протокол № 1-10/11 від 31 серпня 2010 р.)
Львів − 2010
УДК 519.1+519.6
Я.П. Романчук. Дискретна математика: Конспект лекцій для студентів напряму комп’ютерні науки спеціальності Інформаційні управляючі системи та технології. – Львів: НУЛП, 2010. – 210 с.
У конспекті викладено теорію множин і відношень; алгебру логіки і алгебру логіки висловлень і предикатів, теорію графів, моделі алгоритмів і програм, формальні граматики й мови, основи теорії кодування та шифрування.
Кожен розділ складається з основних визначень, властивостей, операцій і теорем; має значну кількість розв’язаних і ілюстрованих прикладів з об’єктами дискретної природи; містить вправи для аудиторної та самостійної роботи студентів.
Конспект лекцій може бути корисним для студентів інших спеціальностей, які бажають вивчати методи дискретної математики для використання їх у природничих і гуманітарних науках із залученням інформаційних технологій.
Рецензент:
І.М. Дронюк, кандидат фізико-математичних наук, доцент кафедри АСУ.
Відповідальна за випуск:
З.Я. Шпак, кандидат технічних наук, доцент кафедри АСУ.
Лекція 3
4.6. Похідна від булевої функції.
У класичній математиці для з’ясування характеру зміни функції використовують поняття похідної. У дискретній математиці, що оперує логічними функціями змінних, котрі, як і самі функції, приймають значення 0 або 1, поняття похідної вводиться таким чином.
Означення 4.17. Одиничною залишковою функцією змінної називається функція, одержувана шляхом надання змінній значення одиниця:
Означення 4.18. Нульовою залишковою функцією змінної називається функція, одержувана шляхом надання змінній значення нуль:
.
Означення 4.19. Похідна першого порядку від булевої функції змінних є функція, одержувана додаванням за модулем 2 одиничних і нульових залишкових функцій змінної :
.
Дотримуючись означення 4.19, для знаходження похідної від булевої функції необхідно скласти одиничну і нульову залишкові функції, додати їх за модулем 2 і, використовуючи основні еквівалентності булевих функцій або таблиці істинності, по можливості спростити отримані вирази.
Приклад 4.23. Маємо функцію трьох змінних . Знайти , , .
Розв’язок: ;
;
.
Для спрощення отриманих виразів, складемо їхні таблиці істинності:
0
0
0
0
0
1
0
0
1
0
1
0
0
1
0
0
1
0
1
0
0
1
0
1
1
0
1
1
1
1
1
1
1
1
1
1
Остаточно маємо: , , .
Приклад 4.24. Маємо функцію . Знайти .
Розв’язок: За умовою змінна є фіктивною. Тому і одинична, і нульова залишкові функції змінної будуть однакові і збіжаться з . Оскільки , одержимо
.
Отже, похідна від булевої функції за фіктивною змінною тотожно дорівнює нулю.
Похідні вищих порядків від булевої функції знаходять як і похідні першого порядку відповідно до означення 4.19, але послідовно, причому в якості наступної функції виступає вже знайдений і спрощений вираз попередньої похідної.
Приклад 4.25. Маємо функцію трьох змінних . Знайти , , , , , , .
Розв’язок: ;
;
.
Спростимо отримані вирази за допомогою їх таблиць істинності:
0
0
0
0
0
0
0
0
1
0
1
0
0
1
0
0
1
1
1
0
1
1
0
1
1
0
0
1
1
0
1
1
1
1
1
0
Отже, використовуючи таблиці істинності, можемо записати ДДНФ отриманих функцій:
, , .
Знайдемо похідні вищих порядків:
, бо в виразі похідної функції змінна фіктивна;
;
;
.
Вправи:
1. Знайти похідні першого порядку , , від булевих функцій трьох змінних :
а) ; б) ;
в) ; г) ;
д) ; е) ;
ж) ; з) ;
и) ; к) .
Спростити отримані вирази.
2. Знайти похідні , , , , , , від булевих функцій трьох змінних :
а) ; б) ;
в) ; г) ;
д) ; е) .
ж) ; з) ;
и) ; к) .
Спростити отримані вирази.
4.7. Комутаційні схеми.
Ще в 1938 р. Клод Шеннон помітив зв’язок між таблицями істинності логічних функцій і електричних ланцюгів. Розглянемо найпростіші електричні ланцюги, що складаються із джерела живлення, електричної лампочки, і двох перемикачів, увімкнутих в електричний ланцюг послідовно (рис. 4.1,а) і паралельно (рис. 4.1,б).
//
(а) (б)
Рис. 4.1.
Присвоїмо значення 1 перемикачам, коли вони з’єднані і 0, якщо роз’єднані. Електричній схемі присвоїмо значення 1, коли лампочка горить (тобто через неї проходить електричний струм), і 0, коли лампочка не горить, тобто електричний струм через неї не проходить. Домовимося, що при описуванні комутаційних схем символи (, , ~) замінюватимемо символами (◦, +, ‘) відповідно.
Очевидно, що при послідовному з’єднанні перемикачів лампочка горить тільки тоді, коли ввімкнуті обидва перемикачі. Тобто електричній схемі присвоюється значення 1 тільки тоді, коли і приймають значення 1. Отже, така електрична схема відповідає висловленню , а сама схема називається схемою логічного множення або логічним елементом p і q. Цей логічний елемент надалі будемо зображувати символом, поданим на рис. 4.2,б.
При паралельному з’єднанні перемикачів лампочка горить в тому випадку, якщо з’єднати хоча б один перемикач. Тобто електричній схемі присвоюється значення 1 тільки тоді, коли або , або приймають значення 1. Отже, така електрична схема відповідає висловленню , а сама схема називається схемою логічного додавання або логічним елементом p або q. Цей логічний елемент надалі будемо зображувати символом, поданим на рис. 4.2,а.
Припустимо, що існує схема, з одним перемикачем , що має наступну властивість: лампочка горить тоді і тільки тоді, коли перемикач розімкнуто. Тобто електричній схемі присвоюється значення 1, коли приймає значення 0, і, навпаки, електричній схемі присвоюється значення 0, коли приймає значення 1. Отже, така електрична схема відповідає висловленню , а сама схема називається інвертором або логічним елементом не p. Цей логічний елемент надалі будемо зображувати символом, поданим на рис. 4.2,в.
/ / /
(а) (б) (в)
Рис. 4.2.
Приклад 4.26. Побудувати комутаційну схему, що відповідає булевому виразу .
Розв’язок: Шукана схема являє собою заперечення (інверсію) логічного додавання елементів і . Вона має вигляд:
/
Приклад 4.27. Побудувати комутаційну схему, що відповідає булевому виразу .
Розв’язок: Шукана схема містить з’єднання логічних елементів і і не . Вона має вигляд:
/
Приклад 4.28. Побудувати комутаційну схему, що відповідає булевому виразу .
Розв’язок: Шукана схема має вигляд:
/
Звернувшись до табл. 4.2, можемо помітити, що логічна функція штрих Шеффера має ту ж таблицю істинності, що і функція , тому її використовують як логічне зв’язування не-і; а логічна функція стрілка Пірса має ту ж таблицю істинності, що і функція , тому її використовують як логічне зв’язування не-або. Логічний елемент не-і будемо зображувати символом, поданим на рис. 4.3,а; а логічний елемент не-або будемо зображувати символом, поданим на рис. 4.3,б.
/ /
(а) (б)
Рис. 4.3.
Використання цих символів найчастіше спрощує запис комутаційних схем. Так, замість схеми, розглянутої в прикладі 4.26, можна використати символьний запис, представлений на рис. 4.3,б.
Приклад 4.29. Запишіть булеву формулу, що відповідає комутаційній схемі:
/
Розв’язок: булева формула, що відповідає представленій комутаційній схемі має вигляд .
Для скорочення запису комутаційних схем можна також використати наступний символьний запис. Для позначення булевої формули замість схеми, представленої на рис. 4.4,а можна використати схему, представлену на рис. 4.4,б; а для запису булевої формули замість схеми на рис. 4.4,в, можна використати схему на рис. 4.4,г.
/ / / /
(а) (б) (в) (г)
Рис. 4.4.
Приклад 4.30. Побудувати комутаційну схему, що відповідає булевому виразу .
Розв’язок: Використовуючи наведені на рис. 4.4 спрощення, зобразимо шукану схему:
/
Вправи:
1. Побудуйте комутаційну схему, що відповідає булевому виразу:
а) ; б) ;
в) ; г) ;
д) ; е) ;
ж) ; з) ;
и) ; к) .
2. Напишіть булеву формулу, що відповідає комутаційній схемі:
а)
/
б)
/
в)
/
г)
/
д)
/
е)
/
ж)
/
з)
/
і)
/
к)
/
5. ЛОГІКА ПРЕДИКАТІВ
5.1. Основні означення.
Логіка предикатів, як і формальна логіка, розділяє елементарне висловлення на суб’єкт (буквально – підмет) і предикат (буквально – присудок). Вона є розширенням логіки висловлень за рахунок використання предикатів у ролі логічних функцій. Ці функції відрізняються від булевих функцій тому, що булеві функції однорідні (їхня область значень і зміни аргументів та сама – логічна, котра приймає значення «істинне» або «хибне»), а предикатні функції неоднорідні (їхня область значень – логічна, а область зміни аргументів – предметна). Логіка висловлень дозволяє описати, проаналізувати складні висловлення, встановити їх істиннісне значення, у той час як логіка предикатів дозволяє описати внутрішню структуру простих висловлень, які не містять логічних сполучень.
Означення 5.1. Предикатом називається оповідальне висловлення, що містить предметні змінні, визначені на відповідних множинах. Заміна предметних змінних конкретними значеннями із зазначених множин перетворює предикат у висловлення, що приймає значення «істинне» або «хибне».
Означення 5.2. вимірний предикат – це функція від предметних змінних , які приймають значення з деяких заданих предметних областей так, що , , …, , а сама функція приймає два логічних значення із множини «істинне», «хибно». Тобто, предикат є функцією вигляду
або .
Як приклад, розглянемо наступну ситуацію. Нехай нам відомо, що Андрій захоплюється футболом, Ганна − плаванням, Костянтин віддає перевагу шахам, Сергій займається легкою атлетикою, а Ігор і Олена заняттям спортом віддають перевагу навчанню в музичній школі по класу фортепіано. Складемо наступні висловлення:
«Ганна займається спортом»;
«Олена займається спортом»;
«Сергій займається спортом”.
Висловлення і істинні, а висловлення хибно.
Замість висловлень ми могли б увести одномісний предикат , предметна змінна якого приймає значення із предметної області ={Андрій, Ганна, Костянтин, Сергій, Ігор, Олена}, а сама предикатна функція мала б вигляд:
=“ займається спортом”.
Розглянемо наступні висловлення
«Олена займається футболом»;
«Костянтин займається шахами»;
«Сергій займається музикою».
Висловлення і хибні, а висловлення істинне.
Замість висловлень ми можемо ввести двомісний предикат , предметні змінні , якого приймають значення із предметних областей ={Андрій, Ганна, Костянтин, Сергій, Ігор, Олена} і ={футбол, плавання, шахи, легка атлетика, музика}, а сама предикатна функція матиме вигляд:
=« займається ».
Оскільки предикати приймають тільки два істиннісних значення, їх можна розглядати як висловлення і за допомогою логічних зв’язувань поєднувати в різні логічні формули – предикатні формули. Предметом розгляду логіки предикатів саме і є встановлення істинності предикатних формул.
Прикладами предикатних формул можуть бути вирази вигляду:
, , і т.п.
Означення 5.2. При заміщенні предметної змінної предметною постійною , предикат від n змінних перетворюється в від /-ї змінної. При наданні конкретних значень всім предметним змінним предикатної функції отримуємо предикатну константу , до якої застосовні всі закони логіки висловлень.
Розглянемо предикат від трьох змінних« добуток і », де предметні змінні визначені на множині натуральних чисел. Нехай у процесі деяких обчислень змінна прийняла конкретне значення . Тоді предикат від трьох змінних перетворюється у предикат від двох змінних:
«20 добуток і ».
Коли і , одержимо одномісний предикат від однієї змінної:
«20 добуток 2 і ».
Якщо додати умову , то вихідний предикат стає предикатом нульової розмірності (константою) або висловленням, яке в цьому випадку є істинним:
«20 добуток 2 і 10» ;
у випадку, наприклад, одержуємо хибне висловлення:
«20 добуток 2 і 8» .
Приклад 5.1. Нехай предикат ділення: « ділиться на »; предикат суми: « сума і »; предикат добутку: « добуток і ». Дати словесні формулювання наступних складних висловлень:
а) ;
б) ;
в) .
Розв’язок:
а) «якщо добуток і , то ділиться на і ділиться на »;
б) «від перестановки співмножників і добуток не змінюється» (властивість комутативності арифметичної дії множення);
в) «число не є ні сумою, ні добутком чисел і ».
5.2. Квантори.
Функціональна природа предиката потребує введення ще одного поняття – квантора. Його роль покажемо на наступних прикладах:
а) «Всі люди мають здатність мислити. Я людина. Отже, я маю здатність мислити»;
б) «Деякі люди зробили геніальні відкриття. Я людина. Отже, я зробив геніальне відкриття».
Якщо перше висловлення не викликає у нас питань стосовно істинності, то в другому прикладі ми відчуваємо хибність висновку, тому що потрапити до числа геніальних людей малоймовірно.
Ключовими словами в наших прикладах є «всі» і «деякі».
Означення 5.3. Термін «всі » позначається і називається квантором загальності або загальності (символ перевернена буква А англійського слова All – «всі»). Висловлення «для всіх із , що істинне» позначається як .
Означення 5.4. Термін «деякі » або «існує хоча б одне значення » позначається і називається квантором існування (символ перевернена буква Е англійського слова Exist «існувати»). Висловлення «існує таке з , що істинно» позначається як .
Означення 5.5. Перехід від до або називається зв’язуванням змінної , або навішуванням квантора на змінну (або на предикат ).
Означення 5.6. Змінна, на яку навісили квантор, називається зв’язаною змінною, незв’язана квантором змінна називається вільною.
Навішувати квантори можна не тільки на предметні змінні, але й на багатовимірні предикати, і на будь-які логічні висловлення.
Означення 5.7. Висловлення, на яке навішується квантор існування або загальності, називається областю дії квантора.
Приклад 5.2. Нехай змінна визначена на великій кількості людей , а предикат « має маму», предикат « має дочку». Дати словесне формулювання предикатних формул , .
Розв’язок: «у кожної людини є мама»;
«у деяких людей є дочка».
Приклад 5.3. Нехай змінні , визначені на деякій великій кількості людей , а предикат « кохає ». Розглянути всі варіанти навішування кванторів на обидві змінні і дати словесну інтерпретацію отриманих висловлень.
Розв’язок: Позначимо предикат « кохає » як КОХАЄ . Проілюструємо всі можливі варіанти навішування кванторів на предметні змінні. Для наочності змінні і показані на різних множинах, хоча очевидно, що в дійсності вони повинні збігатися.
а) КОХАЄ «для будь-якої людини існує така людина , яку вона кохає»:
/
б) КОХАЄ «для будь-якої людини існує така людина , що її кохає»:
/
в) КОХАЄ «існує така людина , яку кохають всі »:
/
г) КОХАЄ «існує така людина , яка кохає всіх людей»;
/
д) КОХАЄ «всі люди кохають всіх людей»;
/
е) КОХАЄ «існує людина , що кохає якусь людину ».
/
Приклад 5.4. Нехай предикат « валюта (грошова одиниця) країни », де множині грошових одиниць, а множині країн. Розглянути всі варіанти навішування кванторів на обидві змінні, дати словесну інтерпретацію отриманих висловлень і визначити їхню істинність.
Розв’язок:
однозмінний предикат (змінне висловлення) «будь-яка грошова одиниця є валютою країни ». Таке змінне висловлення хибне.
однозмінний предикат «будь-якої країни грошова одиниця є валютою ». Дане змінне висловлення хибне.
однозмінний предикат «існує така грошова одиниця , що є валютою країни ». Таке змінне висловлення істинне для будь-якого значення вільної змінної .
однозмінний предикат «існує така країна , валютою якої є грошова одиниця». Таке змінне висловлення істинне для будь-якого значення вільної змінної .
Далі йдуть предикати нульової розмірності: , «валютою будь-якої країни є будь-яка грошова одиниця». Дане висловлення є хибним.
висловлення «існує така грошова одиниця , що є валютою будь-якої країни». Дане висловлення є хибним.
висловлення «у будь-якої країни існує своя грошова одиниця». Таке висловлення істинне.
висловлення «для будь-якої грошової одиниці існує така країна, де вона є її валюта». Дане висловлення істинне.
висловлення «існує така країна, валютою якої є всі існуючі грошові одиниці». Дане висловлення хибне.
, висловлення «існує така грошова одиниця і існує така країна , що є валютою країни ». Дані висловлення істинні.
Приклад 5.5. Нехай задане на множині таблицею.
а
а
а
b
B
b
c
c
c
a
b
c
a
B
c
a
b
c
1
0
0
1
0
0
1
0
0
Визначити істинність наступних формул: , , .
Розв’язок: Формула істинна, тому що для кожного із множини випливає наступне:
.
Формула істинна, тому що існує такий набір змінних, при якому змінне висловлення .
Формула хибна, тому що не існує такого значення , щоб для всіх випливало .
Приклад 5.6. Визначити, чи є дані висловлення формулами логіки предикатів. Якщо так, то визначити вільні і зв’язані змінні:
а) ;
б) ;
г) .
Розв’язок:
а) дане висловлення є формулою логіки предикатів. Змінні зв’язані, а змінна вільна.;
б) дане висловлення не є формулою логіки предикатів, тому що змінна в першій частині формули є зв’язаною, а в другій − є вільною;
в) дане висловлення є формулою логіки предикатів, тому що змінні зв’язані, а змінна вільна.
5.3. Операції над предикатами і кванторами.
Еквівалентні співвідношення.
Розглянемо предикатні функції, що мають тільки зв’язані змінні, тобто функції, аргументи яких зв’язані або квантором загальності, або квантором існування.
Висловлення «для всіх властивість істинна» еквівалентне висловленню «кон’юнкція всіх значень предикатної функції дорівнює 1». Тобто, квантор загальності означає кон’юнкцію всіх значень предикатної функції:
Висловлення «існує хоча б одне таке значення , що властивість істинна» еквівалентне висловленню «диз’юнкція всіх значень предикатної функції дорівнює 1». Тобто, квантор існування означає диз’юнкцію всіх значень предикатної функції:
Квантори існування і загальності можна заперечувати і визначати один через інший використовуючи правила де Моргана:
;
.
Звідси випливає, що: ; .
Проілюструємо висловлене вище на наступному прикладі.
Приклад 5.7. Нехай ми маємо предикат « парне число», який визначений на множині натуральних чисел. Виконати заперечення кванторів існування і загальності, а також дати словами інтерпретацію отриманих висловлень.
Розв’язок:
Оскільки , то предикатна функція приймає як істинні, так і хибні значення:, , , , …
Переконаємося в справедливості формули для заперечення квантора загальності: «не всі парні числа” «існують такі, які є непарними числами» .
Обидва висловлення істинні.
Переконаємося в справедливості формули для заперечення квантора існування: «немає жодного , котре було б парним числом» «усі є непарними числами» .
Обидва висловлення хибні.
Нарешті, зауважимо, що кон’юнктивна природа квантора загальності і диз’юнктивна природа квантора існування з погляду відношення еквівалентності накладають певні обмеження на використання їх разом із диз’юнкцією і кон’юнкцією як логічними операціями.
Легко переконатися в справедливості тотожностей:
;
.
Приклад 5.8. Довести тотожність .
Розв’язок: Нехай для визначеності предметна область предикатів складається із двох елементів і (у загальному випадку для областей, що містять елементів, представлене доведення буде таким ж, але більш громіздким). Тоді:
.
Друга тотожність доводиться аналогічно (перевірити самостійно).
Якщо кожен із предикатів замінити висловленням, то справедливими виявляються наступні співвідношення:
; .
Приклад 5.9. Довести тотожність .
Розв’язок: Доведемо другу тотожність (доведення першої читачеві пропонується зробити самостійно):
. Оскільки імплікація може бути подана через диз’юнкцію, то вірним є таке співвідношення: .
Доведемо його:
.
Щоб зберегти відношення еквівалентності (при винесенні за дужки квантора існування при кон’юнкції і квантора загальності при диз’юнкції), коли дані два різних предикати, введемо додаткову змінну:
.
Подібним чином поступимо й у випадках:
;
;
.
В останньому з наведених співвідношень відзначимо наступне: квантори і можна переставляти місцями тільки тоді, коли вони незалежні, тобто відносяться до незалежних однозмінних предикатів!
Стосовно двозмінних предикатів зауважимо, що за допомогою законів комутативності і асоціативності для кон’юнкції і диз’юнкції, можна довести справедливість наступних тотожностей:
; .
Приклад 5.10. Довести тотожність .
Розв’язок:
Вправи:
1. Записати (використовуючи прийняті позначення для предикатів суми, добутку і рівності відповідно) предикатною формулою пропозицію, що надає для довільних наступні властивості арифметики натуральних чисел:
а) комутативність додавання;
б) комутативність множення;
в) асоціативність додавання;
г) асоціативність множення;
д) дистрибутивність додавання щодо множення;
е) дистрибутивність множення щодо додавання;
ж) транзитивність рівності.
2. Записати предикатною формулою наступні пропозиції:
а) «кожна людина прагне знайти свою половину»;
б) «деякі люди мають витончений смак»;
в) «для всякого потенційного поля ротор дорівнює нулю»;
г) «сума довжин двох сторін трикутника завжди більша за довжину його третьої сторони»;
д) «всі сторони ромба рівні»;
е) «будь-яка людина має батька».
3. Розглянути всі можливі варіанти навішування кванторів на предикат «книга з бібліотеки ». Дати словесні формулювання отриманих висловлень і визначити їхню істинність.
4. Нехай і предикати суми і добутку відповідно, певні:
на множині натуральних чисел з нулем ;
на множині всіх цілих чисел .
З’ясувати, який зміст мають наступні формули, і на якій (із перерахованих) множині вони істинні:
а) ; б) ;
в) ; г) .
5. Визначити, чи є дані вирази формулами логіки предикатів. Якщо так, то визначити вільні і зв’язані змінні:
а) ; б) ;
в) ; г) ;
д) ; е) .
ж) .
6. Нехай предикат задано на множині таблицею (по варіантах):
а)
с
с
с
1
0
1
0
1
0
1
0
1
б)
с
с
с
0
0
1
0
0
1
0
0
1
в)
с
с
с
1
1
1
0
0
0
1
1
1
г)
с
с
с
0
1
0
0
1
1
1
0
0
Визначити істинність наступних формул:
, , , , , , , , , , , , , .
7. Довести тотожності:
а) ; б) ;
в) .
5.4. Логічна інтерпретація формул логіки предикатів.
Як і в логіці висловлень, нас буде цікавити істиннісне значення формул логіки предикатів. При логічній інтерпретації формул логіки предикатів можливі наступні ситуації: формула може бути здійсненною, загальнозначущою або суперечливою. Дамо відповідні означення.
Означення 5.8. Формула називається здійсненною в області , якщо в даній області існує такий набір констант , які відповідають змінним , що формула стає істинним висловленням. Формула називається просто здійсненною, якщо існує така область , де формула здійсненна.
Означення 5.9. Формула називається тотожно істинною (ТІ) в області , якщо вона здійсненна в області при будь-яких підстановках констант. Якщо формула тотожно істинна в будь-якій області , то її називають загальнозначущою.
Означення 5.10. Формула називається тотожно помилковою (ТП) в області , якщо формула нездійсненна в області при будь-яких підстановках констант. Якщо формула тотожно помилкова в будь-яких областях , то її називають суперечливою.
Задача визначення загальнозначущості формул логіки предикатів набагато складніша, ніж у логіці висловлень, тому що в загальному випадку потужність множини областей нескінченна , і метод перечислення можливих ситуацій тут недієздатний. Тобто у логіці предикатів виникає проблема можливості розв’язання: необхідно вказати ефективний спосіб установлення загальнозначущості формул, тобто їх здійсненності у всіх областях . У загальному випадку ця проблема логіки предикатів нерозв’язна!
Теорема Черча. У логіці предикатів не існує алгоритму, який для будь-якої формули встановлює, загальнозначуща вона чи ні.
Зауваження. В окремих випадках ця проблема має розв’язок. Наприклад, для формул логіки предикатів, які містять тільки однозмінні предикати, такий алгоритм існує.
Розглянемо інтерпретацію формул логіки предикатів не на всіх існуючих областях , а на конкретних моделях M.
Означення 5.11. Моделлю M у логіці предикатів називається множина основна множина моделі M, разом із заданою на ньому сукупністю предикатів , яку називають сигнатурою моделі M.
Наприклад, модель M називають арифметикою натуральних чисел. Її основна множина множина натуральних чисел, а сигнатура включає предикати суми , добутку і рівності .
Аналогічно означенням 5.8 5.10 виявляють здійсненність, загально значимість і суперечливість формул на моделі M.
Приклад 5.11. Визначити істинність, хибність або здійсненність на моделі M наступних формул:
а) ; б) ; в) .
Розв’язок:
а) формула здійсненна на моделі M, тому що виявляє існування натурального значення . Очевидно, що дана формула істинна тільки при підстановках парних натуральних чисел замість вільної змінної , і хибна при підстановці непарних чисел. Наприклад, формула істинна (у цьому випадку ), а формула хибна (тому що і не може в області натуральних чисел бути непарним числом);
б) формула ТІ на моделі M, тому що виявляє існування суми двох натуральних чисел. При підстановці будь-якого числа замість вільної змінної формула істинна: (тут ), (тут );
в) формула ТІ на моделі M, тому що виявляє тільки одне значення суми двох чисел. Дійсно, якщо і , то . Для підтвердження цього твердження розглянемо різні варіанти наборів чисел, значення предикатів і формули в цілому на цих наборах :
істинна;
істинна;
істинна;
істинна.
Приклад 5.12. Визначити істинність, хибність або здійсненність наступних формул: а) ; б) ; в) .
Розв’язок:
а) формула здійсненна. Наприклад, на моделі арифметики натуральних чисел M . Якщо трактувати предикат як предикат суми , то формула істинна при натуральне число, і хибна – у протилежному випадку. Якщо трактувати предикат як предикат добутку , то формула істинна при натуральне число, і хибно – у протилежному випадку.
б) формула ТІ формула, тому що вона істинна в будь-якій області . Довести це легко, згадавши про кон’юнктивну природу квантора загальності. При підстановці будь-якої константи з будь-якої області у формулу предикат може приймати або істинне , або хибне значення. Тоді
.
в) формула ТП-формула, тому що вона помилкова в будь-якій
19.02.2013 18:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора