Список літератури. 1. Селлерс Ф. Методы обнаружения ошибок в работе ЭВМ

Основна

1. Селлерс Ф. Методы обнаружения ошибок в работе ЭВМ. – М.: Мир, 1974. - С.32-41.

Додаткова

2. Бохман Д., Постхоф Х. Двоичные динамические системы. М.: Энергоатомиздат, 1986. - С.66-167.

Для практичних занять

3. Методичні вказівки і завдання до контрольних робіт з дисципліни «Основи дискретної математики» для студентів очної та заочної форм навчання фахів 6.0804, 6.0915 / О.М. Мартинюк. – Одеса: ОНПУ, 2001. – С.45-50.

Лекція 36. Логіка предикатів

Вступ

Лекція має за мету навести базові поняття логікі предикатів. Розглянути висловлення предикатів, аргументи-терми, квантори, зміни арності предикатів, а також правила використання кванторів. Звернено увагу до наведених форм, формул, та використання предикатів.

У лекції присутні три підрозділи:

36.1. Висловлення предикатів

36.2. Логіка предикатів

36.3. Правила застосування кванторів

36.1. Висловлення предикатів

Нехай А и В - деякі висловлення, що можуть бути вірними («1») чи помилковими («0»). Якщо позначити літерами прості висловлення, можна представити складне висловлення за допомогою відповідних логічних операцій.

Приклад. А - «Я піду в театр»,
В - «Я зустріну друга»,
А&В - «Я піду в театр і зустріну друга».

Якщо висловлення вірне, то його заперечення помилкове. Звичайно висловлення виражають властивості одного чи декількох об'єктів.

Приклад. А - «Тиск масла на кульку клапана більше тиску пружини»,
В - «Масло відкриває клапан»,
С - «Масло перетікає з нагнітальної порожнини у впускну» А→В→С.

Змістовна частина висловлення відіграє роль визначальної властивості сукупності об'єктів, для яких це висловлення вірне, і називається предикатом. Предикат являє собою логічну функцію Р(х), що як і булеві функції може приймати значення «0» чи «1», але на відміну від них значення аргументу можуть вибиратися з деякої множини М об'єктів, яку називають областю визначення, тобто хÎМ.

У загальному випадку така функція може бути залежною від багатьох змінних х₁, х₂,..., х_n, що приймають значення з тої самої множини X чи різних множин X₁, X₂,…, і може записуватися як Р(х₁, х₂,..., х_n).

36.2. Логіка предикатів

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

Визначення. N-місцевим предикатом називається неоднорідна двозначна логічна функція від n аргументів вигляду Р(х₁, х₂,.., х_n) з областю значень {0, 1}.

Аргументи N-місцевого, або N-арного предиката являють собою об'єкти з деякої області визначення Х (хÎХ) і називаються предметними змінними. Конкретні значення змінних називаються предметними постійними. Предметні змінні та предметні постійні утворюють клас логічних понять, які називають термами.

Визначення. Термом є: а) деяка предметна змінна або константа;
b) f(f₁, f₂,... f_n), якщо f – функціональна літера та f₁, f₂,... f_n – терми;
c) деякій вираз, коли це слідує з правил a), b).

Приклад. Р(х₁, х₂) - «х₁, х₂ - парні числа», де х₁, х₂ÎХ, Х - множина натуральних чисел. У тому випадку Р(2, 3)=0, тобто ложно, а Р(2, 4)=1, тобто істинно

При заміщенні аргументу «х_і» деякім його значенням «а» N-місцевий предикат Р(х₁, х₂,..., х_n) перетворюється в (N-1)- місцевий предикат Р(х₁, х₂,..., а,..., х_n) і від змінної х_і вже не залежить. N-місцевий предикат, у якому всі х₁, х₂,…,х_n змінних замінені постійними значеннями, перетворюються у висловлення, яке можна розглядати як 0-місцевий предикат.

Приклад. Р(х₁, х₂, х₃) - «х₁ є сумою х₂ і х₃», 3-місцевий,

Р(5, х₂, х₃) - «5 є сумою х₂ і х₃», 2-місцевий,

Р(5, 3, х₃) - «5 є сумою 3 і х₃», 1-місцевий,

Р(5, 3, 2) = 1 - «5 є сумою 3 і 2», - 0-місцевий вірний,

Р(5, 3, 1) = 0 - «5 є сумою 3 і 1» - 0-місцевий помилковий.

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

Визначення. Твердження, що всі хÎХ мають властивість Р(х), записується за допомогою квантора спільності " у вигляді "хÎC Р(х) чи "х Р(х), що читається як «для всіх хÎХ Р(х) - предикат від х - вірний».

Визначення. Твердження, що існує хоча б один об'єкт хÎC, що володіє властивістю Р(х), записується за допомогою квантора існування $ у вигляді $хÎХ Р(х) чи $х Р(х), що читається як «існує хÎC, що Р(х) - предикат від х - вірний».

Квантори ²"² і ²$² зв'язують перемінну х і перетворюють одномісний предикат у висловлення. Очевидно, «"х Р(х)», розглянуте як висловлення, істинне тільки за умови, що Р(х) - тотожно вірний предикат, у всіх інших випадках це висловлення помилкове. «$хР(х)», розглянуте як висловлення, завжди вірне, крім єдиного випадку, коли Р(х) - тотожно помилковий предикат.

Приклад. Нехай Р(х) - «х - просте число», де хÎC і Х - множина натуральних чисел, тоді висловлення:

а) "х Р(х)=0 - «усі натуральні числа прості» - помилкове;
б) $х Р(х)=1 - «існує просте натуральне число» - вірне.

Застосування квантора до N-місцевого предиката перетворює останній у (N-1)- місцевий предикат та знижує його арність. У загальному випадку можливе застосування до одного N-місцевого предиката декількох кванторів. Якщо до N-місцевого предиката застосувати
k-кванторів, де k≤n, то предикат перетворюється в (N-k)- місцевий предикат, якщо k=n, то предикат перетворюється у висловлення. Змінні, до яких застосовуються квантори, називаються зв'язаними, інші змінні називаються вільними.

Приклад: "хР(х, у) - 1-місцевий предикат, "х$уР(х, у) – 0-місцевий предикат, або висловлення.

36.3. Правила застосування кванторів

1. Однойменні квантори можна переставляти місцями

"х "у Р(х, у) = "у "х Р(х, у);

$х $у Р(х, у) = $у $х Р(х, у)

2. Різнойменні квантори в загальному випадку переставляти не можна

"х $у Р(х, у) ¹ $у "х Р(х, у)

3. Між кванторами спільності ²"² і існування ²$² мають місце співвідношення, що узагальнюють закони деМоргана.

ù("х Р(х)) = $хù(Р(х));

ù($х Р(х)) = "х ù(Р(х))

Вираження, які можна утворювати застосуванням до предикатів зв'язувань і кванторів, являють собою формули логіки предикатів. Під логічними зв'язуваннями розуміються слова «не», «і», «чи», «якщо..., то...», «якщо і тільки якщо...». Оскількі предикати - це двозначні логічні функції, то кожному з цих зв'язувань відповідає своя логічна операція - заперечення, кон'юнкції, диз'юнкції, імплікації, еквівалентності відповідно.

Визначення. Предикатною формулою є: a) деяка елементарна формула; b) кожен з виразів А°В та "хÎM(A(x)), якщо А і В формули та х – предметна змінна (° - зв'язка послідовності висловлень); c) деякій вираз, коли це випливає з правил a), b).

У математиці предикати і формули логіки предикатів широко використовуються для символізації запису властивостей, визначень, відношень. Переклад пропозицій з якої-небудь розмовної мови на символічну мову логіки предикатів є нетривіальним через відсутність «механічних» правил. Цей переклад заснований не стільки на формі звичайних пропозицій, скільки на виявленні їхнього зв'язку значень.

Приклад. Нехай Р(х₁, х₂) - бінарне відношення j, визначене на множині Х. При розгляді його як двомісного предиката можна записати властивості відношень:

а) рефлективність: "х Р(х, х) чи "х (хjх);

б) симетричність: "х₁ "х₂(Р(х₁, х₂)ÞР(х₂, х₁₎)

чи "х₁ "х₂((х₁jх₂)Þ(х₂jх₁));

в) транзитивність: "х₁ "х₂ "х₃((Р(х₁, х₂)&Р(х₂, х₃))ÞР(х₁, х₃))

чи "х₁ "х₂ "х₃(((х₁j х₂)&(х₂j х₃))Þ(х₁j х₃)).

Формули логіки предикатів, у яких заперечення відносяться тільки до елементарних предикатів чи висловлень, причому з логічних операцій містяться тільки операції булевого базису {Ú, Ù, ù}, називаються приведеними чи майже нормальними формами.

Приклад. "х₁ "х₂(Р(х₁, х₂)ÞР(х₂, х₁)) - неприведена формула;
ù("х Р(х)) - не приведена формула;
"х ù(Р(х, х)) - приведена формула;
"х₁ "х₂ (Р(х₁, х₂)ÙùР(х₂, х₁))Ú ù (Р(х₁, х₂)ÙР(х₂, х₁)) – не- приведена формула.

За допомогою предикатів можна здійснити запис функцій.

Приклад. Для n-входового кон'юнктора (схеми, що реалізує кон'юнкцію від n змінних) y=Ù(x₁, x₂,…,x_i,…,x_n) запис за допомогою предикатів виглядає

"х_і P(x_i) Þ P(y).

Для n-входового диз'юнктора (схеми, що реалізує диз'юнкцію від n змінних) y=Ú(x₁, x₂,…,x_i,…,x_n) запис за допомогою предикатів виглядає

$х_і P(x_i) Þ P(y).

Для функції y = ùx₁ x₂ Ú x₂ x₄ запис за допомогою предикатів, хоч і трохи громіздко, але виглядає

$ (x₁, x₂) (((ùP(x₁) і P(x₂)) чи (P(x₂) і P(x₄))) Þ P(y).

Для n-входової схеми нерівнозначності (схеми, що реалізує складення по модулю “2” від n змінних) y=Å(x₁, x₂,…,x_i,…,x_n) запис за допомогою предикатів такий:

("(х_і1, х_і2,..., х_і2k+1) P(x_im))&("(х_j1, х_j2,..., х_j2r) P(x_jt))ÞùP(y),
де m<2k+1<n та t<2r<n.

Контрольні запитання

1. Що є предикатом, чи є предикат булевою функцією, від кількох аргументів може бути предикат?

2. Що є предметними змінними та предметними постійними, яка між ними різниця?

3. Що є термом, які три правила формально визначають терм?

4. Які операції використовують у логіці предикатів, як виконати перехід від неформального словесного опису к предикатній формулі?

5. Яка різниця між кванторами спільності та існування?

6. Що є зв'язаними та вільними змінними?

7. Що мають на увазі, коли кажуть, що квантори зв'язують перемінну, скільки може бути таких зв'язувань?

8. Чи можна застосовувати до предиката декількох кванторів?

9. Які базові правила перетворень можна застосувати до кванторів?

10. Що є предикатною формулою, які три правила формально визначають формулу?

11. Що є приведеною або майже нормальною формою для предикатів?