Знак - називається квантором загальності

Запис "х р(х) означає, що коли М обмежена (М= {a₁..a_n}), то "xр(x)~ .

Висловлення: «Існує таке х із m, що р(х) істинне» позначається $ х р(х). Знак $ - називається квантором існування. Для скінченної множини М= {a₁..a_n} визначено

$хр(х) ~ .

Перехід від р(х) до "х р(х) та $ х р(х) називається зв’язуванням змінної х або ж навішуванням квантора ($,") на змінну х або на предикат р(х). Змінна, на яку навішено квантор називається зв’язаною, незв’язана змінна називається вільною.

Вільна змінна приймає довільні істинності значення із М. Якщо вираз р(х) – змінне висловлення, яке визначається х, то вирази "х р(х), $ х р(х) не залежить від х і при заданих р(x) і М мають цілком визначенні істинності значення. При застосування кванторів виникають закони де Моргана:

(1)

(2)

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

"´"у р(х,у)~"у "х р(х,у)

 

$´$у р(х,у)~$у $х р(х,у)

Перестановка різних кванторів " та $ не є еквівалентною операцією.

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

Відмітимо, що предикат представляється двохзначною функцію, адже після підстановки конкретних значень p,q,r…ÎМ, він може приймати лише два значення "0" та "1", як висловлення.

Приклад: в програмуванні, при організації циклів, часто необхідно завершити цикл коли або х=у бо ж кількість циклів досягла наприклад 100.

Тоді, якщо «і» лічильник, то висловлювання по завершенню циклу виглядає так (х=у) (і>100) або так: цикл повторювати поки .

 

 

Приклад.

Висловлення "у$(х) (х³у) твердить, що для довільного “y” існує “x”, який не перевищує “y “. Це висловлення істинне(=1) для довільної не порожньої числової множини.

 

Відмітимо, що перестановка кванторів матиме зовсім інший зміст $х"у (х³у) це означає, що існує “х” такий, що для усіх “у” реалізується (х³у) це не вірно, висловлення хибне. Тобто переставляти квантори не можна.

Істинні формули і еквівалентні відношення.

При інтерпретації формул логіки предикатів можливі три випадки.

1. Якщо в області М для формули F існує такий набір аргументів при якому вона істинна, то функція F являється виконаною. Тобто, якщо на множині М тобто F(x_i)=1, для х_і Î М, то говорять, що F реалізується на М.

2. Якщо формула F на множині М виконується при довільному наборі аргументів, то вона тотожно істинна на М, тобто .

3. Якщо F не виконується ні для жодного набору змінних х_іÎМ, то вона є тотожно хибною на М.

Наприклад. Формули для х,уÎМ та формула , для довільних «х»ÎМ є тотожно істинними.

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

Велика множина співвідношень є еквівалентними. Тому є дуже важливим дослідження властивостей предикатів.

При дослідженні виникають дві проблеми:

1. отримання істинних формул.

2. перевірка формул на істинність.

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

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