16 опис двомісних предикатів, що характеризують структуру системи. Предикати. Основні поняття. Поняття формули логіки предикатів
Ціль семінару:
Розглянути практичне застосування логіки предикатів.
План заняття:
Розглядається тема логіка предикатів, на яку відводиться 2 години семінарських занять.
Завдання 1.Яким відносинам та функціям відповідають наступні предикати, визначені на безлічі натуральних чисел:
1. Предикат тотожності Е:N 2 →B:
E(a 1 ,a 2)=1 і тоді, коли a 1 =a 2 .
2. Предикат порядку Q:N 2 →B:
Q(a 1 ,a 2)=1 тоді і лише тоді, коли a 1 ≤ a 2.
3. Предикат ділимості D:N 2 →B:
D(a 1 ,a 2)=1 і тоді, коли a 1 ділиться на а 2 .
4. Предикат суми S:N 3 →B:
S(a 1 ,a 2 ,a 3)=1 і тоді, коли a 1 +a 2 =a 3.
5. Предикат твору П:N 3 →B:
П(a 1 ,a 2 ,a 3)=1 і тоді, коли a 1 *a 2 =a 3 .
Рішення.
1. Двомісний предикат тотожності Е-“x 1 ”=”x 2 ” взаємно однозначно відповідають:
а) двомісне відношення R 1 - «Бути рівним», R 1 N 2: (a 1, a 2) R 1 тоді і тільки тоді, коли E (a 1, a 2) = 1;
б) одномісна функція (операція) тотожності f 1 (x 1) = x 2 а саме: f 1 (x) = x, f:N→N.
2. Двомісному предикату порядку Q-“x 1 ≤ x 2 ” взаємно однозначно відповідає двомісне відношення R 2 - «бути не більше», R 2 N 2:(a 1 ,a 2) R 2 тоді і тільки тоді, коли Q( a 1 ,a 2) = 1.
Однак функції f(x 1)=x 2 для предикату порядку Q(x 1 ,x 2) не існує, так як не виконано умову Р"(а 1 ,а 2 ,...а n ,а n +1)=0 при однакових значеннях змінної x 1 існує не тільки значення змінної x 2 при якому предикат Q істинний.Наприклад, Q(2,4)=1 і Q(2,6)=1, проте 4≠6.
3. Двомісному предикату ділимості D-“x 1 ділиться на х 2 ” взаємно однозначно відповідає двомісне відношення R 3 - “ділиться”, R 3 N 2:(a 1 ,a 2) R 3 тоді і лише тоді, коли D(a 1, a 2) = 1.
Однак функції f(x 1)=x 2 для предикату ділимості D(x 1 ,x 2) не існує, так як не виконано умову Р"(а 1 ,а 2 ,...а n ,а n +1)=0, наприклад D(6,2)=1 та D(6,3)=1, проте 2≠3.
4. Тримісному предикату суми S- "х 1 + х 2 = х 3" взаємно однозначно відповідають:
а) тримісне відношення R 4 N 3: (a 1 ,a 2, a 3) R 4 тоді і тільки тоді, коли S(a 1 ,a 2 ,a 3)=1;
б) двомісна функція (операція арифметики) - складання f 2 (x 1, x 2), а саме х 1 + х 2 = х 3 .
5. Тримісному предикату твору П- “x 1 *x 2 =x 3 ” взаємно однозначно відповідають:
а) тримісне відношення R 3 N 3: (a 1, a 2, a 3) R 5 тоді і тільки тоді, коли П (х 1, х 2, х 3) = 1;
б) двомісна функція (операція арифметики)- множення f 3 (x 1, x 2) = x 3, а саме х 1 * х 2 = х 3.
Взаємна однозначність відповідності між S і f 2 (П і f 3), обумовлена виконанням для предикату S(П) умови Р"(а 1 ,а 2 ,...а n ,а n +1)=0 для кожної системи елементів a 1 ,a 2 N існує єдиний елемент а 3 N такий, що S(a 1 ,a 2 ,a 3)=1 (відповідно для П(a 1 ,a 2 ,a 3)=1).
Завдання 2.Проілюструвати з прикладу предикату ділимості, визначеного задачі 1, поняття змінного висловлювання, істинного висловлювання, хибного висловлювання.
Рішення.
Предикат ділимості D(x 1 ,x 2)- це змінне (двомісне) висловлювання, предметною областю якого можуть бути будь-які безлічі дійсних чисел, наприклад безліч N.
D(6,2)- висловлювання, значення якого є істина, тобто. справжнє висловлювання.
D(5,2)- хибне висловлювання.
D(3,х), D(х,2)- змінні (одномісні) висловлювання, істинність яких залежить від цього, яким числом буде заміщено символ x, але D(а,1)- істинне висловлювання, оскільки будь-якого елемента а N має місце: D(а,1)=1 (будь-яке натуральне число ділиться на одиницю).
Завдання 3.Записати формулою логіки предикатів пропозицію, що відображає транзитивну властивість ділимості цілих чисел.
Рішення.
Складове висловлювання (пропозиції), що є формулюванням якості транзитивності відношення подільності цілих чисел.
«якщо ділиться на b і b ділиться на с, то а ділиться на с», складається з трьох простих висловлювань D(a,b), D(b,c) і D(a,c). Отже, транзитивну властивість подільності можна записати у вигляді складеного висловлювання (логічної формули):
«якщо D(a,b) і D(b,c), то D(a,с) або (D(a,b) & D(b,c)) → D(a,c).
Завдання 4.Дати словесні формулювання наступних складових висловлювань (пропозицій):
1. S(a,b,c) & D(a,d) & D(b,d)→D(c,d), де S та D- предикати суми та ділимості відповідно (див. приклад 1);
2. D(a,b) & S(a,b,c);
3. S(a,b,c) ~ S(b,a,c);
4. P 1 ~ P 2 де P 1 – предикат «число 3nє парним»; Р 2 - предикат «число nє парним».
Рішення.
1. «Якщо кожне доданок a,b суми цілих чисел ділиться на деяке число d, то сума з ділиться на це число»:
S(a,b,c) & D(a,d) & D(b,d)→D(c,d).
2. «Число а не ділиться на число b, і невірно, що їхня сума дорівнює з»: D(a,b) & S(a,b,c).
3. «Від перестановки місць доданків a і b сума не змінюється»- властивість комутативності арифметичної операції складання: S(a,b,c) ~ S(b,a,c).
4. «Число 3n є парним тоді і лише тоді, коли n є парним»: P 1 ~ P 2.
Еквівалентність може бути виражена й іншими словесними формулюваннями, зокрема:
· «Із того, що Р 1, випливає те, що Р 2 і назад»;
· «Із того, що Р 2 слід те, що Р 1 і назад »;
· «Умови Р 1 необхідно і достатньо для того, щоб Р 2»;
· «Р 2 необхідно і достатньо, щоб Р 1»;
· «Р 1, якщо і тільки якщо Р 2»;
· «Р 2, якщо і тільки якщо Р 1»;
· «Умови Р 1 і Р 2 еквівалентні»;
· «Р 2 і тоді, коли Р 1 » та інших.
Завдання 5.Нехай х визначено на множині людей М, а Р(х) - предикат «х-смертен». Дати словесне формулювання предикатної формули
Рішення.
Вираз означає «всі люди смертні». Воно залежить від змінної х, а характеризує всіх людей загалом, тобто. висловлює судження щодо всіх х множини М.
Завдання 6.Нехай Р(х)- предикат «х-парне число», визначений на множині М. Дати словесне формулювання висловлювання визначити його істинність.
Рішення.
Вихідний предикат Р(х)- «х-парне число» є змінним висловлюванням: при підстановці конкретного числа замість змінної х він перетворюється на просте висловлювання, що є істинним або хибним, наприклад при підстановці числа 5 перетворюється на висловлювання «5-парне число», є помилковим. Висловлювання означає «у М існує парне число». Оскільки безліч М, у якому заданий предикат Р(х), не визначено за умови (у разі кажуть, що завдання сформульована недостатньо коректно), довизначимо М.
Нехай предикат Р(х) визначено на множині натуральних чисел N, тобто. тоді висловлювання - істинно. У випадку висловлювання істинно будь-якій безлічі М, що містить хоча б одне парне число, і хибно будь-якій безлічі непарних чисел.
Завдання 7.Нехай N (х) - предикат "х-натуральне число". Розглянути варіанти навішування кванторів. Проінтерпретувати отримані висловлювання та визначити їхню істинність.
Рішення.
Висловлювання «всі числа-натуральні» істинно на будь-якій множині натуральних чисел і хибно, якщо М містить хоча б одне ненатуральне число, наприклад, ціле негативне;
Висловлювання «існує натурально х» істинно на будь-якій множині М, що містить хоча б одне натуральне число, і хибно - інакше.
Завдання 8.Записати предикатною формулою пропозицію «Будь-яка людина має батька».
Рішення.
Для побудови предикатної формули використовуємо два предикати «х-чоловік» і «батько х» і для зручності сприйняття позначимо їх відповідно: ЛЮДИНА (х) та БАТЬКО (у). Тоді пропозиція «Будь-яка людина має батька» у предикатній формі має вигляд:
Зауважимо, що якщо предикат БАТЬКО(у,х) визначений на безлічі людей, то вираз «будь-яка людина має батька» можна записати простіше:
Завдання 9.Нехай предикат Р(х,у) описує відношення «х любить у» на багатьох людей. Розглянути всі варіанти навішування кванторів на обидві змінні. Дати словесну інтерпретацію одержаних висловлювань.
Рішення.
Позначимо предикат «х любить у» через ЛЮБИТ (х, у). Пропозиції, що відповідають різним варіантам навішування
ЛЮБИТ(х,у)- «для будь-якої людини х існує людина, яку вона любить» або «всяка людина кого-небудь любить» (рис. а);
ЛЮБИТ (х,у)- «існує така людина, що її люблять всі х» (рис. б)ж
ЛЮБИТЬ (х,у)- «всі люди люблять всіх людей» (рис. в);
ЛЮБИТЬ (х,у)- «існує людина, яка кого-то любить» (рис. г);
ЛЮБИТЬ (х,у)- «існує людина, яка любить всіх людей» (рис. д);
ЛЮБИТЬ (х,у)- «для будь-якої людини існує людина, яка його любить» (рис. е).
З наведеного вище можна дійти невтішного висновку у тому, що перестановка кванторов спільності та існування змінює сенс висловлювання, тобто. Квантори спільності та існування не мають у загальному випадку властивість комутативності.
Завдання 10.Нехай Q(x,y)- предикат порядку "х≤у". Розглянути різні варіанти квантифікації його змінних. Визначити істинність одержуваних виразів різних випадків інтерпретації області визначення М предиката, х, у М.
Рішення.
Одномісний предикат від у: «для будь-якого х має місце х≤у». Якщо М- нескінченна безліч невід'ємних цілих чисел, цей предикат ложный; на будь-якій кінцевій множині натуральних чисел предикат істинний в єдиній точці, що представляє найбільше в М. При підстановці будь-якого іншого у М цей предикат звертається в помилкове висловлювання;
Одномісний предикат від х: «для будь-якого має місце х≤у». Якщо М-множина невід'ємних цілих чисел, цей предикат істинний в єдиній точці х=0 і кладений при підстановці замість х будь-якого числа з М;
Одномісний предикат від у: «існує число М, яке не більше у». Якщо М-будь-яке непусте безліч чисел, то даний предикат перетворюється на справжнє висловлювання при підстановці якого-небудь з М.
Одномісний предикат від х: «існує число М, яке не менше х». На будь-якій непорожній безлічі М чисел даний предикат перетворюється на справжнє висловлювання при підстановці якого-небудь х із М.
Висловлювання «для будь-яких х і у виконується х≤у» хибно на будь-якій множині, що складається більш ніж з одного елемента, і істинно на множині з одним елементом;
Висловлювання «існують такі х і у, що х≤у» істинно на будь-якій непустій множині;
Висловлювання «для будь-якого числа х існує число у, не менше ніж х» істинно на будь-якій непорожній множині;
Вислів «існує у такої, що для будь-якого х х≤у» стверджує, що М є єдиний максимальний елемент;
Вислів «існує х такий, що він не більше будь-якого у» стверджує, що в М є єдиний мінімальний елемент.
Висловлювання «для будь-якого числа у існує число х, не більше, ніж у» істинно на будь-якій непустій множині
Завдання 11.Розглянути всі можливі варіанти навішування кванторів на предикат D(х,у)- «х ділиться на у», визначений на безлічі натуральних чисел N. Дати словесні формулювання отриманих висловлювань та визначити їхню істинність.
Рішення.
Операції навішування кванторів призводять до наступних формул:
Одномісний предикат «будь-яке натуральне число з N ділиться на натуральне число з N»; істинний тільки одного значення вільної змінної у=1;
Змінне висловлювання «існує натуральне число, яке ділиться на у», істинне для будь-якого значення вільної змінної у, взятої з множини N;
Змінне висловлювання «натуральне число х ділиться на всяке натуральне число у», хибне будь-якого значення вільної змінної х, взятої з N;
Змінне висловлювання «існує натуральне число, яке ділить натуральне число х», істинне для будь-якого значення вільної змінної х;
Висловлювання «для будь-яких двох натуральних чисел має місце ділимість одного на інше» хибні;
Висловлювання «існують такі два натуральні числа, що перше ділиться на друге», істинні;
Висловлювання «існує натуральне число, яке ділиться на будь-яке натуральне», хибне;
Висловлювання «для будь-якого натурального числа знайдеться таке натуральне, яке ділиться на перше», істинне;
Остаточно отримаємо префіксну нормальну форму для вихідної предикатної формули.
Логіка висловлювань – дуже тонка логічна система. Існують такі типи логічних міркувань, які не можуть бути здійснені в рамках логіки висловлювань, наприклад:
- Будь-який друг особи А є друг особи В. З не є друг В, отже, С не є друг А.
- Просте число два – парне. Отже, є прості парні числа.
Коректність цих умов полягає в внутрішній структурі самих речень і сенсі слів «всякий» і «існує».
Розглянемо пропозиції, що залежать від параметрів, наприклад: « х- парне число", " хменше y», « x+y=z», « uі v– брати». Якщо у перших трьох реченнях замінити x,yі zдеякими числами, а останньому підставити імена членів деякої сім'ї, то отримані висловлювання може бути істинними чи хибними. Наприклад, для х=5, y=2, z=7, u- Петро, v– Іван отримаємо: «5 – парне число», «5 менше 2», «5+2=7», «Петро та Іван – брати».
Пропозиції такого типу називаються предикатами. Точніше, предикатом P(x 1 ,...,x n)називається функція, змінні якої набувають значення з деякої множини М, а сама вона приймає два значення: істинне (І) і хибне (Л), тобто. P (x 1, ..., x n): М (І, Л).
Предикат від n аргументів називають n-місцевим предикатом та позначають повністю P (n) (x 1, ..., x n)Якщо потрібно підкреслити кількість аргументів. Висловлювання вважають нуль-місцевими предикатами.
Над предикатами можна робити звичайні логічні операції. В результаті виходять нові предикати
Наприклад:
1. Нехай P (1) (x)означає предикат хділиться на 2», а Q (1) (х)– предикат « хділиться на 3». Тоді вираз P (1) (x) &Q (1) (х)означає предикат хділиться на 2 та хділиться на 3», тобто. визначає предикат ділимості на 6.
2. Нехай S (2) (х,у)означає предикат х=у». Він набуває значення І тоді і тільки тоді, коли х=у. У цьому випадку вираз ┐ S (2) (х,х) ÞS (2) (х,у)визначає предикат, що набуває значення І за будь-яких хі у.
Крім операцій логіки висловлювань застосовуватимемо ще операції зв'язування квантором.
Квантор загальності.Нехай Р(х)– предикат, що набуває значення І або Л для кожного хÎМ. Тоді під виразом " хР(х)будемо на увазі висловлювання істинне, коли Р(х)істинно для кожного елемента хз М, і хибне – інакше. Символ хназивається квантором загальності та запис " хР(х)читається так: «для всіх х Р(х)». Це висловлювання вже не залежить від х.
Квантор існування.Нехай Р(х)- Предікат. Під виразом $ х Р(х)будемо розуміти висловлювання істинне, якщо існує елемент множини М, для якого Р(х)істинно, і хибне – інакше. Символ $ хназивається квантором існування та запис $ хР(х)читається так: «існує х, таке, що (або для якого) Р(х)» .
Для предикатів, розглянутих трохи раніше, можемо записати:
- $х (P (1) (x) & Q (1) (х))- Справжнє висловлювання;
- " х (P (1) (x) & Q (1) (х))- хибне висловлювання;
- " х,у (┐S (2) (х,х) ÞS (2) (х,у))- Справжнє висловлювання.
Введемо тепер суворі визначення для обчислення предикатів.
(Чисте) обчислення предикатів (першого порядку) -це формальна теорія До, у якій визначено такі компоненти.
1. Алфавіт:
зв'язки основні ┐,
додаткові &,
службові символи (,) Î (, ’ , ’ ,)
квантори загальності
існування
предметні константи 
змінні
предметні предикати P, Q, . . .
функтори f, q,. . .
З кожним предикатом та функтором пов'язане деяке натуральне число, яке називається арністю,або іноді місцевістю.
2. Формули мають наступний синтаксис:
Формула = (атом
| ┐ (формула | (формула
(Формула) | (Змінна формула
| змінна формула
Атом = предикат (список термів)
Список термів = терм | терм,
Список термів терм = константа |
Змінна | функтор (список термів)
При цьому мають бути виконані такі контекстні умови: термі f (t 1 ,. . ., t n)функтор fповинен бути n- місцевим. В атомі(або атомарноїформулі) P(t 1 ,. . ., t n)предикат Рповинен бути n- місцевим.
Входження змінних до атомарної формули називаються вільними.Вільні входження змінних у формулах А і Взалишаються вільними у формулах Аі А Ст.У формулах x Аі x Аформула А,як правило має, вільні входження змінної х.Входження змінної ху формули x Аі x Аназиваються пов'язаними.Входження інших змінних (відмінних від x), які були вільними у формулі А,залишаються вільними та у формулах x Аі x А.Одна й та змінна може мати в одній і тій же формулі як вільні, так і пов'язані входження. Формула, що не містить вільних входження змінних, називається замкнутої.
Наприклад, розглянемо формулу x (Р(х) y Q(x,y))та її підформули. У підформулу y Q(x,y)змінна хвходить вільно, а обидва входження змінної упов'язані (квантором існування). Таким чином ця підформула не замкнена. З іншого боку, те саме входження змінної ху підформулу Q(x, y)є пов'язаним входженням у формулі x (Р(х) y Q(x,y)). У цій формулі всі входження всіх змінних пов'язані, тому формула замкнута.
Мова теорії L не містить кванторів, тому поняття вільного та пов'язаного входження змінних не застосовні безпосередньо. Зазвичай для зручності вважають, що це формули теорії L замкнуті.
Формули виду Ата ┐ А,де А -атом, називаються літеральнимиформулами (або літералами).У формулах x Аі x Апідформула Аназивається областю діїквантора по х.
Зазвичай зв'язки та квантори впорядковують за пріоритетом так: ┐, ,$, &, , . Зайві дужки у своїй опускають. Терм tназивається вільнимдля змінної ху формулі А,якщо ніяке вільне входження змінної ху формулу Ане лежить в області дії жодного квантора щодо змінної у,що входить у терм t.Зокрема, терм tвільний для будь-якої змінної у формулі Аякщо жодна змінна терма не є пов'язаною змінною формулою А.
Наприклад:
а) терм увільний для змінної ху формулі Р(x), але той самий терм уне вільний для змінної ху формулі y P(x).
б) терм f(x, z)вільний для змінної ху формулі y P(x,y) Q(x),але той же терм f(x, z)не вільний для змінної ху формулі
z y P(x,y) Q(x).
Перехід від предикату Р(х)до " х Р(х)або $ х Р(х)називається зв'язуваннямзмінної х, або навішуванням кванторана змінну х, або квантифікацієюзмінної х.
Вираз " х Р(х)та $ х Р(х)не залежать від хі при фіксованих Р і предметної множини М має цілком певні значення, представляючи цілком конкретні висловлювання щодо всіх ху предметній області М.
Повертаючись до визначення предикату, можна відзначити, що висловлювання є просто нуль місцевий предикат.
Навішуючи квантори на багатомісні предикати і взагалі будь-які логічні висловлювання, ми цим і визначаємо область дії квантора $ хабо " хі всі входження ху ці висловлювання є зв'язковими.
Розглянемо розв'язання деяких прикладів.
Приклад 4.4.Нехай N(х)– предикат « х- натуральне число". Розглянути варіанти навішування кванторів, інтерпретувати та визначити їхню істинність.
Рішення."х N(х)-«Всі числа натуральні». Це висловлювання істинно на будь-якій безлічі натуральних чисел і хибно, якщо М містить хоч одне ненатуральне число (наприклад, ціле негативне).
Приклад 4.5.Нехай предикат Р(х,у)описує ставлення « хлюбить у» на багатьох людей. Проаналізувати варіанти навішування кванторів та дати інтерпретацію.
Рішення. Використовуючи взаємно однозначну відповідність між відносинами предикатами, можна проілюструвати рішення схемами (рис. 4.1).
Рис. 4.1. Ілюстрація впливу кванторів
Інтерпретація:
" х$y Р(х,у)– «для будь-кого хіснує у, якого він любить».
$ у " х Р(х,у)– «існує такий у, якого люблять усі х».
" х "уР(х,у) - "Усе хлюблять усіх у».
$ х $ у Р(х,у)- « знайдеться х, який любить когось із у» або «знайдеться людина, яка когось любить».
$ х" у Р(х,у)– «існує х, який любить усіх у».
" у$ х Р(х,у)– «для будь-якого узнайдеться х, що його любить».
Аксіоми (логічні): будь-яка система аксіом обчислення висловлювань, плюс
P 1: x A(x) A(t),
P 2: A(t) x A(x),
де терм tвільний для змінної ху формулі А.
Правила виведення:
де формула Амістить вільні входження змінної х,а формула Вїх не містить.
Обчислення предикатів, яке не містить предметних констант, функторів, предикатів та власних аксіом, називається чистим.Обчислення предикатів, яке містить предметні константи та/або функтори та/або предикати та пов'язують їх власні аксіоми, називається прикладним.
Обчислення предикатів, у якому квантори можуть пов'язувати лише предметні змінні, але можуть зв'язувати функторы чи предикати, називається обчисленням першого порядку.Обчислення, у яких квантори можуть пов'язувати як предметні змінні, а й функторы, предикати чи інші безлічі об'єктів, називаються обчисленнями найвищих порядків.Практика показує, що прикладного обчислення предикатів першого порядку достатньо для формалізації змістовних теорій у всіх розумних випадках.
Відповідність між предикатами, відносинами та функціями
n – місцевий предикат можна як функцію Р(х 1 ,…х n) від n змінних х i Î М i, де М i- предметні області, а РВВ = (0,1) = (І, Л).Таким чином, предикат Р(х 1 ,…х n) є функцією типу Р: М 1 ´М 2 ´… ´М n ®В, або якщо предметна область єдина для всіх змінних, то маємо Р: М n ®В.
З розглянутого очевидно, що для будь-яких М та n існує однозначна відповідність між n-місцевими відносинами R ІМ nта предикатами Р(х 1 ,…х n) , М n ®В:
Кожному n – місцевому відношенню Rвідповідає предикат Р(х 1 ,…х n) такий, що Р(а 1 ,…а n)=1, якщо і тільки якщо ( а 1 ,…а n)ÎR;
Будь-який предикат Р(х 1 ,...х n) визначає відношення Rтаке, що ( а 1 ,…а n)Î Rякщо і тільки якщо Р(а 1 ,…а n) = 1.
При цьому Rставить область істинності предикату P.
Розглянемо тепер функцію f(х 1 ,…, х n), f: М n ®M. Тоді можна бачити, що будь-якої функції f: М n ®Mвідповідає предикат Р(х 1 ,…х n +1), Р: М n +1 ®В, такий що Р(а 1, ... а n +1) = 1якщо і тільки якщо f(а 1 ,…а n)= а n+1.
Поняття предикату ширше за поняття функції (див. рис. 4.1.), тому зворотна відповідність (від ( n+1)-місцевого предикату до n-місцевої функції) можливо не завжди, а тільки для таких предикатів, для яких виконується умова, пов'язана з однозначністю функції:
Р(а 1 ,…а n +1)=0 ® ("а¢ n +1 ÎМ|а¢ n +1 ¹а n +1 Р(а 1,…а¢ n +1)=0.(4.3.)
Аналогічна відповідність є між підмножиною відносин (R¢)Ì(R)і безліччю функцій (f). Для цього класу відносин виконується умова
(а 1 ,…а n +1)ÎR¢ ® (" а¢ n +1 ÎМ| а¢ n +1 ¹ а n +1 ( а 1 ,…а¢ n +1)ÎR¢). (4.4.)
Приклад 4.6.Яким відносинам та функціям відповідають предикати, визначені на множині натуральних чисел?
1. Предикат суми S: N 3 ®В:
S(х 1 ,х 2 ,х 3)=1тоді і лише тоді, коли х 1 +х 2 =х 3 .
2. Предикат порядку Q:N 2 ®В:
Q ( х 1 ,х 2) = 1 тоді і тільки тоді, коли х 1 £ х 2 .
Розглянемо пропозицію
Ця пропозиція не є висловлюванням, тому що про неї не можна сказати, істинно вона чи хибно. Воно називається предикатом чи умовою (на х і у). Наведемо інші приклади пропозицій зі змінними:
Є просте число;
Є парне число;
Менше у,
Є спільний дільник, z.
Вважатимемо, що допустимими значеннями змінних у і z є натуральні числа. Якщо у реченнях замінити змінні їх допустимими значеннями, то вийдуть висловлювання, які можуть бути як істинними, і помилковими. Наприклад,
2 є просте число;
3 є парне число;
5 менше 7;
3 є спільний дільник 6 та 12.
ВИЗНАЧЕННЯ. Пропозиції зі змінними, що дають висловлювання внаслідок заміни вільних змінних їх допустимими значеннями, називаються предикатами.
Пропозиції можуть бути прикладами предикатів.
За кількістю вхідних вільних змінних розрізняють предикати одномісні, двомісні, тримісні тощо. буд. Предикати (2) і (3) - одномісні, предикати (1) і (4) - двомісні, предикат (5) - тримісний. Висловлювання вважатимемо нульмісцевими предикатами.
Замінюючи в одномісному предикаті (2) змінну натуральними числами, отримуватимемо висловлювання:
0 є просте число;
1 є просте число;
2 є просте число;
3 є просте число і т.д.
Деякі їх є істинними. Таким чином, даний одномісний предикат виділяє серед натуральних чисел ті, при підстановці яких замість змінної виходить справжнє висловлювання, і його можна розглядати як умову значення вільної змінної, що входить в предикат. У разі числа, задовольняють цій умові, - прості.
Одномісний предикат можна як умова на об'єкти цього виду; двомісний - як умова на пари об'єктів цього виду тощо.
Предикати можна ставити різними способами. В алгебрі часто розглядають предикати, задані за допомогою рівнянь, нерівностей, а також систем рівнянь чи нерівностей. Наприклад, нерівність визначає одномісний предикат, рівняння - двомісний, а система рівнянь - тримісний у, z - раціональні змінні).
Позначати предикати будемо великими літерами латинського алфавіту (можливо, з нижніми індексами) із зазначенням у дужках усіх вільних змінних, які входять у цей предикат. Наприклад, - позначення двомісного предикату, - тримісного та - позначення -місцевого предикату.
Надалі ми говоритимемо про істиннісне значення довільного предиката на тому чи іншому наборі вільних змінних, що входять до нього, розуміючи під цим істиннісне значення висловлювання, яке виходить в результаті заміни вільних змінних відповідними їм значеннями з аналізованого набору.
Висловлювання, яке виходить при підстановці в предикат набору допустимих значень замість його змінних, будемо позначати Якщо це вислів істинний (хибний), кажуть, що набір значень задовольняє
п-місцевий предикат- це функція Р(х 1 х 2,х п) від п змінних, що приймають значення з деяких заданих предметних областей, так що функція P набуває двох логічних значень – «істинно» або «хибно».
Таким чином, предикат Р(х 1, х 2, ..., х п) є функцією типу , де множини називаються предметними областями предикату; х 1, х 2, ..., х п -предметними змінними предикату; У = (1,0).
Відповідності між предикатами, відносинами та функціями:
1. Для будь-яких М і п існує взаємно однозначна відповідність між n-місцевими відносинами u n-місцевими предикатами Р(х 1, х 2, ..., х п), :
кожному n-місцевому відношенню R відповідає предикат Р(х 1, х 2, ..., х п), такий, що Р(a 1, a 2, ..., a п) = 1, якщо і тільки якщо (a 1 , a 2, ..., a п) Î R;
Будь-який предикат Р(х 1, х 2, ..., х п) визначає відношення Rтаке, що (a 1, a 2, ..., a п) Î R, якщо тільки якщо Р(a 1, a 2, ..., a п) = 1.
При цьому R визначає область істинності предикату Р.
2. Будь-якої функції f(х 1, х 2, ..., х п) відповідає предикат Р (х 1, х 2, ..., х п, х п +1) = 1такий, що Р (a 1, a 2, . .., a п, a п+1)=1, якщо і тільки якщо f(a 1, a 2, ..., a п) = a n +1.
Зворотне відповідність (від ( n+1)-місцевого предикату (рис. 2.17) до n-місцевої функції) можливо не завжди, а тільки для таких предикатів Р' для яких виконується умова (пов'язана з вимогою однозначності функції): Р(a 1, a 2, ..., a п, a п+1) = 1, то для будь-кого
a ' п +1 ≠a п +1 Р(a 1, a 2, ...,a п, a ' п +1) = 0 (1)
Аналогічна відповідність (взаємно однозначна) є між підмножиною відносин (R") (R) і безліччю функцій ( f}.
Для цього класу відносин виконується аналогічна умова: якщо (a 1, a 2, ..., a п, a п+1) Î R ' то для будь-якого a ' п+1 ≠a п+1 , (a 1, a 2, ..., a п, a п+1) R '
Вираз Р(a 1, a 2, ..., a п) розумітимемо як вислів «Р(a 1, a 2, ..., a п) = 1», а вираз Р(х 1, х 2, ..., х п) - як змінне висловлювання, істинність якого визначається підстановкою елементів множини М замість змінних (х 1, х 2, ..., х п).
Для позначення двомісних предикатів крім префіксного запису Р(х 1, х 2) використовується нерідко інфіксний запис х 1 Рх 2
Яким відносинам та функціям відповідають наступні предикати, визначені на безлічі натуральних чисел:
1. Предикат тотожності E:N 2 →В: Е(а ], а 2) = 1 і тоді, коли а ]= а 2
Двомісний предикат тотожності Е – «x ]= x 2 » взаємно однозначно відповідають:
а) двомісне відношення R 1, - «Бути рівним», , Тоді і тільки тоді, коли Е ( a 1 ,а 2) = 1;
б) одномісна функція (операція) тотожності f 1 (x 1)=х 2, а саме:.
2. Предикат ділимості D: N 2 →В: D (а], а 2) = 1 і тоді, коли а ] ділиться на а 2:
Двомісний предикат ділимості D – «х 1 ділиться на х 2 » взаємно однозначно відповідає двомісному відношенню R 2– «ділитися», тоді і лише тоді, коли D ( a 1 ,а 2) = 1. Проте функції f 1 (x 1)=х2для предикату подільності D ( x 1 , x 2) не існує, тому що не виконана умова (1), наприклад D(6, 2) = 1 та D(6, 3) = 1, проте 2≠3.
3. Предикат суми S:N 3 →В: S(а 1, а 2, а 3) = 1 і тоді, коли а 1 +a 2 = a 3 .
Тримісному предикату суми S – «x 1 +x 2 =x 3 »взаємно однозначно відповідають:
а) тримісне відношення: тоді і лише тоді, коли S(а 1, а 2, а 3) = 1;
б) двомісна функція (операція арифметики) – додавання f(х 1 х 2) = х 3, а саме: х 1 + х 2 = х 3.
В алгебрі логіки висловлювання розглядаються як нероздільні цілі і лише з погляду їхньої істинності чи хибності.
Ані структура висловлювань, ані тим більше їх зміст не торкаються. У той самий час й у науці, й у практиці застосовуються висновки, істотно залежать як від структури, і від змісту які у них висловлювань.
Наприклад, у міркуванні “Кожен ромб – паралелограм; АВСD – ромб; отже, АВСD - паралелограм ” посилки та висновок є елементарними висловлюваннями логіки висловлювань і з погляду цієї логіки розглядаються як цілі, неподільні, без урахування їхньої внутрішньої структури. Отже, алгебра логіки, будучи важливою частиною логіки, виявляється недостатньою в аналізі багатьох міркувань.
У зв'язку з цим виникає потреба у розширенні логіки висловлювань, у побудові такої логічної системи, засобами якої можна було б досліджувати структуру тих висловлювань, які в рамках логіки висловлювань розглядаються як елементарні.
Такою логічною системою є логіка предикатів, що містить всю логіку висловлювань як свою частину.
Логіка предикатів розчленовує елементарне висловлювання на суб'єкт (буквально – підлягає, хоча може грати роль доповнення) і предикат (буквально – присудок, хоча може грати роль визначення). Суб'єкт – те, що щось стверджується у висловлюванні;
предикат - те, що стверджується про суб'єкт. Наприклад, у висловлюванні “7 – просте число”, “7” – суб'єкт, “просте число” – предикат. Це висловлювання стверджує, що “7” має властивість “бути простим числом”.
Якщо в розглянутому прикладі замінити конкретне число 7 змінної х із множини натуральних чисел, то отримаємо висловлювальну форму "х - просте число". При одних значеннях (наприклад, х = 13, х = 17) ця форма дає справжні висловлювання, а при інших значеннях х (наприклад, х = 10, х = 18) ця форма дає помилкові висловлювання.
Ясно, що ця висловлювальна форма визначає функцію однієї змінної х, визначеної на множині N, і приймає значення з множини (1; 0) (або (і; л)). Тут предикат стає функцією суб'єкта та виражає властивість суб'єкта.
Визначення 1.
Одномісним предикатом Р(x) називається довільна функція змінного x, визначена на множині M і що приймає значення з множини (1; 0).
Безліч М, у якому визначено предикат Р(x), називається областю визначення предикату Р(x).
Безліч всіх елементів , у яких предикат приймає значення “істина” (1), називається безліччю (областю) істинності предиката Р(x), тобто. безліч істинності предиката Р(х)- це безліч .Так, наприклад, предикат Р(x) - "x - просте число" визначено на безлічі N, а безліч істинності I P для нього є безліч всіх простих чисел.
Предикат Q(x) – “sinx=0” визначено на безлічі R, яке безліччю істинності є
Предикат F(x) – “діагоналі паралелограма x взаємно перпендикулярні” визначено безлічі всіх паралелограмів, яке безліччю істинності є безліч всіх ромбів.
З наведених прикладів бачимо, що одномісні предикати виражають властивості предметів (суб'єктів).
Визначення 2.
Предикат Р(х), визначений на множині М, називається тотожно істинним, якщо його безліч істинності збігається з областю визначення, тобто I p = M.
Визначення 3.
Предикат Р(х), визначений на множині М, називається тотожно хибним, якщо його безліч істинності є порожньою множиною, тобто I p =0.
Природним узагальненням поняття одномісного предикату є поняття багатомісного предикату, з якого виражаються відносини між предметами
Прикладом бінарного відношення, тобто відносин між двома предметами, є відношення “менше ”. Нехай це відношення введено на множині Z цілих чисел. Воно може бути охарактеризовано висловлювальною формою “х Визначення 4. Двомісним предикатом Р(x,y) називається функція двох змінних x і y, визначена на множині М = М 1 хМ 2 і приймає значення з множини (1; 0). Серед прикладів двомісних предикатів можна назвати такі предикати: Q(x, y) – “x=y” - предикат рівності, визначений на множині RхR=R 2 ; F(x,y) - "х паралельний y", "пряма х паралельна прямий y", визначений на безлічі прямих, що лежать на даній площині. Абсолютно аналогічно вводиться поняття тримісного предикату. Наведемо приклад тримісного предикату (функції трьох змінних): S(x,y,z) – “x+y=z”. Підстановка в нього х=3 перетворює його на двомісний предикат: S(y,z) – “3+y=z”, а підстановка х=3, z=2 – на одномісний предикат S(y) – “3+y= 2”. Підстановка ж S(2,3,5) перетворює їх у справжнє висловлювання, а S(1,7,4)– на хибне. Аналогічно визначається і n-місцевий предикат (функція n змінних). Приклад n-місцевого предикату: R(x 1 , x 2 ,…,x n): a 1 x 1 +…+a n x n =0, який, як бачимо, є алгебраїчним рівнянням з n невідомими. При n=0 матимемо нульмісцевий предикат – це логічна (пропозиціональна) змінна, що приймає значення з множини (1; 0).
