Особливості контролю знань логіки предикатів

Предикати. Логічні операції над предикатами

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

Позначаються предикати великими літерами з індексами або без, наприклад . Довільне висловлення є 0-місним предикатом. Предикат можна вважати функцією п змінних, областю визначення якої є множина М, а множиною значень – логічні значення 1 (істина) та 0 (хиба).

Вираз, яким записується предикат – висловлювальна форма. Нехай Р (х, у)= «х + у= 4» – двомісний предикат, визначений на множині N ×N, тоді логічні значення відповідних висловлень записують, наприклад, як і т.д. При конструюванні предикатів часто використовують функціональні символи. Тут таким символом є «+» або «сума (x, у)», а Р – предикатний символ «дорівнює 4».

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

Оскільки значеннями предикатів є висловлення, то над предикатами можна виконувати ті ж логічні операції, що і над висловленнями: заперечення, кон'юнкцію, диз'юнкцію, імплікацію та еквіваленцію.

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

Якщо– множина істинності (сукупність всіх наборів М, для кожного з яких ) предиката Р, то множина істинності предиката буде

Нехай деякий m-місний предикат заданий на множині, причому всі змінні та різні.

Кон'юнкцією двох предикатів Р та Q називається (п+т) – місний предикат , заданий на множині M×L, якийперетворюється в істинне висловлення для всіх тих і тільки тих значень змінних, при яких перетворюються в істинне висловлення обидва задані предикати.

Якщо предикати Р та Q мають k спільних змінних, то місність кон’юнкції буде s = п + т – k, а загалом max.

Означення диз’юнкції, імплікації та еквіваленції аналогічне. [2, ст. 17]

Якщо і – множини істинності предикатів Р та Q, визначених на одній множині М, то множини істинності предикатів ,, та можна записати у вигляді:

;

;

;

;

Крім вказаних операцій над предикатами виконують кванторні операції (квантифікацію).

Зв «язуванням квантором загальності одномісного предиката Р(х) називається операція, яка предикату Р(х) ставить у відповідність висловлення («для будь-якого х має місце Р(х)»), яке істинне тоді і тільки тоді, коли предикат тотожно істинний. Отже,

=

Наприклад, висловлення на множині дійсних чисел істинне, а - хибне.

Зв'язуванням квантором існування одномісного предиката Р(х) називається операція, яка предикату Р(х) ставить у відповідність висловлення («існує х, що має місце Р(х)»), яке хибне тоді і тільки тоді, коли предикат тотожно хибний. Отже,

= Р(х) – тотожно хибний предикат.

Наприклад, висловлення на множині дійсних чисел хибне, а – істинне.

При формулюванні тверджень мовою предикатів часто зустрічаються речення чотирьох типів, які в арістотелевій логіці називаються категоричними судженнями і мають зміст та символічний запис:

А: загальностверджувальне судження «всі S суть Р» (всі елементи х, які мають властивість S, мають і властивість Р) – ;

Е: загальнозаперечувальне судження «будь-яке S не є Р» (будь-який елемент х, який має властивість S, не має властивості Р) – ;

I: частково стверджувальне судження «деякі S суть Р» (деякі елементи х, які мають властивість S, мають і властивість Р) – ;

О: частково заперечувальне судження «деякі S не є Р» (деякі елементи х, які мають властивість S, не мають властивості Р) – ;

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

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

Зв’язування квантором загальності чи існування за деякою змінною х, n-місного предиката приводить до (n-1) – місного предикатачи, який залежить від змінних.При цьому висловлення істинне тоді і тільки тоді, коли предикаттотожно істинний на множині, а висловлення хибне тоді і тільки тоді, коли предикат тотожно хибний на.

Далі можна по черзі зв’язувати різними кванторами інші змінні. Коли всі змінні будуть зв’язані, отримується висловлення. Наприклад, тримісний предикат , заданий на множині дійсних чисел, можна перетворити на двомісний, одномісний, предикати або ж на істинне висловлення , Якщо Р – 0-місниЙ предикат (висловлення), то записи та означають те саме, що і Р.

Входження змінної в предикат називається зв'язаним, якщо вона є змінною квантора або знаходиться в області дії квантора за цією змінною. Інакше входження вільне. У складних предикатах область дії квантора виділяється дужками.

Предикати та , задані на одній множині М, називаються рівносильними (Р Q), якщо = (один з них перетворюється в істинне висловлення на всіх тих наборах , на яких і інший перетворюється в істинне висловлення). Предикат називається логічним наслідком предиката (P Q), якщо .

• Класифікація формул логіки предикатів. Логічне слідування
• Рівносильні формули. Нормальні форми
• Метод резолюцій
• Приклади розв’язання практичних завдань до підрозділів модуля логіки предикатів
• Класифікація формул логіки предикатів. Логічне слідування
• Методика тестування студентів при вивченні модуля "логіка предикатів"

Рекомендуємо почитати:

Мотивація учбової діяльності та її формування на різних вікових етапах
Учбова діяльність, як і будь-яка інша діяльність людини, характеризується насамперед суб’єктністю, активністю, предметністю, цілеспрямованістю і усвідомленістю. Д.Б. Ельконін, вважаючи учбо ...

Особливості сучасного патріотичного виховання в позаурочній діяльності
Національне виховання в українській державі формується нині, на думку О.Вишневського, з урахуванням двох факторів: розпаду СРСР та проголошення України самостійною державою; утворення нашої ...

Вимоги до приміщень та розташування робочих місць із ПК
Приміщення, призначені для роботи з ПК, повинні мати природне освітлення. Орієнтація вікон повинна бути на північ або північний схід, вікна повинні мати жалюзі, які можна регулювати, або шт ...