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

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

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

Позначаються предикати великими літерами з індексами або без, наприклад . Довільне висловлення є 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), якщо .

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

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

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

Структура дидактичної гри
Дидактична гра має сталу структуру, що відрізняє її від інших видів ігрової діяльності. Основними елементами, які одночасно надають їй форми навчання і гри, є дидактичні та ігрові завдання, ...

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