Особливості контролю знань логіки предикатів
Наприклад, щоб довести, що, розглянемо довільну інтерпретацію з предикатом на деякій множині М, на якій ліва частина перетворюється в істинне висловлення (за першою схемою). Тоді. За означенням навішування квантора загальності предикат — спростовний, тоді — виконуваний. Отже, — права частина в цій інтерпретації теж перетворюється в істинне висловлення. Навпаки, якщо права частина у деякій… Читати ще >
Особливості контролю знань логіки предикатів (реферат, курсова, диплом, контрольна)
1. Основні теоретичні відомості з модуля логіки предикатів
1.1 Предикати. Логічні операції над предикатами
Нехай є деяка множина п-місним предикатом, заданим на множині М, називається речення, що містить змінних (предметні змінні), яке перетворюється на висловлення при підстановці замість цих змінних відповідних конкретних значень М (предметні константи).
Позначаються предикати великими літерами з індексами або без, наприклад. Довільне висловлення є 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-місниЙ предикат (висловлення), то записи та означають те саме, що і Р. [2, ст 23]
Входження змінної в предикат називається зв’язаним, якщо вона є змінною квантора або знаходиться в області дії квантора за цією змінною. Інакше входження вільне. У складних предикатах область дії квантора виділяється дужками.
Предикати та, задані на одній множині М, називаються рівносильними (Р Q), якщо = (один з них перетворюється в істинне висловлення на всіх тих наборах, на яких і інший перетворюється в істинне висловлення). Предикат називається логічним наслідком предиката (P Q), якщо .
1.2 Класифікація формул логіки предикатів. Логічне слідування
За допомогою логічних операцій можна конструювати як завгодно складні предикати. Їх записують у вигляді формул, абстрагуючись від конкретного змісту. Введемо індуктивні означення терма та формули.
Термом називається:
1) будь-яка предметна змінна або константа;
2) якщо — n-місний функціональний символ, атерми, то — терм;
3) ніяких інших, крім утворених за 1) та 2), термів немає.
Наприклад, нехай — 2-місний функціональний символ «сума (х, y)», а — 2-місний функціональний символ «степінь (x, y)», задані на множині натуральних чисел, тоді вирази (5, x), (3, y),((x, 2), 3),((х,у),3) є термами, які за допомогою алгебраїчних символів можна було б відповідно записати «5+x», ««, «+3», ««. Припідстановці замість змінних конкретних значень терм не перетворюється на висловлення, на відміну від формули.
Формулою називається:
1) якщо — n-місний предикатний символ, атерми, то, () — елементарна формула логіки предикатів;
1) якщо, А і В-формули логіки предикатів, то слова також є формулами логіки предикатів;
2) якщо, А — формула, а х — вільна змінна вА, то і також формули логіки предикатів;
3) всі інші слова, крім тих, що утворені за правилами пунктів 1 — 3 не є формулами логіки предикатів.
Як і валгебрі висловлень, деякі дужки можна опускати, пам’ятаючи про порядок виконання операцій. Якщо в області дії квантора знаходиться елементарна формула, дужки можна не писати. Формула називається замкнутою, якщо вона не має вільних входжень змінних, і відкритою, якщо є вільні змінні. Наприклад, — відкрита формула, бо є вільні входження змінної у. Якщо змінна зв’язана, в області дії квантора її можна перейменувати, при цьому всі її вільні входження залишаються без зміни. [2, ст 26]
Процес перетворення формули на висловлення і саме це висловленняназивають інтерпретацією формули логіки предикатів. Щоб побудувати інтерпретацію, потрібно:
1. Вибрати область інтерпретації М;
2. Задати в цій області конкретні предикати замість предикатних символів, що входять у формулу;
3. Якщо формула замкнута, то при підстановці заданих предикатів вона вже перетвориться на висловлення, якщо відкрита — на предикат. Щоб цей предикат перетворити на висловлення, потрібно замість вільних змінних підставити предметні константи з області М.
Одна і та ж формула в різних інтерпретаціях або в одній інтерпретації при різних заміщеннях вільних змінних константами може перетворюватися як в істинне, так і в хибне висловлення. Наприклад, замкнута формула перетворюється в істинне висловлення «Для довільного натурального числа існує число, більше за нього», якщо на множині натуральних чисел задати предикат і в хибне мисловлення «Кожен чоловік має сина», якщо на множині всіх чоловіків задати предикат Р (х, у) — «х батько у».
Формула називається істинною в даній інтерпретації, якщо вона перетворюється в істинне висловлення на будь-якому наборі елементів (констант) з області інтерпретації.
Аналогічно означаються хибна, виконувана та спростовна в даній інтерпретації формула.
Інтерпретація називається моделлю для деякої множини формул, якщо кожна формула даної множини істинна в даній інтерпретації.
Формула логіки предикатів може бути:
- логічно загальнозначущою (тавтологією), якщо вона істинна в будь — якій інтерпретації;
- суперечністю (тотожно хибною), якщо вона хибна в будь-якій інтерпретації;
- виконуваною, якщо вона виконувана хоча б в одній інтерпретації;
- спростовною, якщо вона спростовна хоча б в одній інтерпретації. Якщо формулаА тавтологія логіки предикатів, то це записують? А.
Окремим випадком формули, А алгебри висловлень називається формула логіки предикатів, одержана з, А підстановкою замість пропозиційних змінних довільних формул логіки предикатів.
Окремий випадок будь-якої тавтології алгебри висловлень єтавтологією логіки предикатів. Наприклад, формула тавтологія, бо є окремим випадком тавтології .
Формула В є логічним наслідком формули, А (А?В), якщо вона перетворюється в істинне висловлення на будь-якому наборі елементів з області довільної інтерпретації, на якому, А перетворюється в істинне висловлення.
Можна довести, що А? В тоді і тільки тоді, коли ?.Із тавтологій, що містять імплікацію (доведення далі), можна отримати деякі важливі схеми логічного слідування. Наприклад,? — правило універсальної конкретизації; - правило екзистенціального узагальнення. [1, cт.18]
Аналогічно, формула В є логічним наслідком формул (В), якщо вона перетворюється в істинне висловлення на будь-якому наборі елементів з області довільної інтерпретації, на якому всі одночасно перетворюються в істинне висловлення. Можна довести, щоВ тоді і тільки тоді, коли або формула є тотожно хибною.
Найбільш часто вживані схеми логічного висновку — силогізми Арістотеля. Це схеми, що складаються з трьох простих висловлень типуА, E, I та O, з яких перші два — посилки, а третє - висновок. У кожному з силогізмів розглядаються три властивості (предикати) S, М та Р. Перша (велика) посилка пов’язує М і Р, друга (мала) пов’язує М і S, а висновок пов’язує S і Р.
1.3 Рівносильні формули. Нормальні форми
Дві формули, А і В називаються рівносильними, якщо кожна з них є логічним наслідком іншої.
Можна довести, що тоді і тільки тоді, коли ?.
В логіці предикатів рівносильними будуть формули, отримані з рівносильних формул алгебри висловлень підстановкою замість пропозиційних змінних довільних формул логіки предикатів (окремі випадки). Наприклад, рівносильними будуть формули
бо вони отримані з рівносильностей і за допомогою різних підстановок.
Крім окремих випадків у логіці предикатів є рівносильності, пов’язані з операцією навішування кванторів. Деякі рівносильності можна записати із тавтологій, що містять головну операцію, доведення яких здійснено у попередньому пункті. Варто пам’ятати рівносильності, що часто використовуються при рівносильних перетвореннях формул та при зведенні їх до нормальних форм:
1) -закони перейменування змінних;
2) -закони де Моргана для кванторів;
3) -дистрибутивні закони (і тільки такі два!);
4) -закони перенесення кванторів через кон’юнкцію, тут і далі Qне містить вільного x;
5) -закони пронесення кванторів через диз’юнкцію;
6)
— закони пронесення кванторів через імплікацію.
Зведеною формою для формули логіки предикатів називається така рівносильна їй формула, яка або елементарна, або містить лише операції, причому заперечення стосується лише елементарних підформул.
Випередженою нормальною формою для формули логіки предикатів називається така її зведена форма, яка або не має кванторних операцій, або всі вони виконуються останніми.
Випереджена нормальна форма (ВНФ) довільної формули, А логіки предикатів має вигляд, дедовільна сукупність кванторів (префікс формули А), а В-формула, яка не містить кванторів (матриця формули А).
Теорема. Для кожної формули логіки предикатів існує зведена та випереджена нормальна форми.
Щоб отримати зведену форму, потрібно скористатися законами, що дозволяють виразити через, , та законами де Моргана. Після застосування дистрибутивних законів та законів пронесення кванторів через логічні операції (винесення кванторів за дужки) отримують випереджену форму. Тут буває необхідно перейменовувати змінні у області дії кванторів, але робити це треба так, щоб не трапилось «колізії». Для перейменовування краще використовувати імена змінних, які у формулі не зустрічаються. Потрібно пам’ятати, що вільні змінні не перейменовуються, а одна і та ж змінна у областях дії різних кванторів може перейменовуватись на різні змінні. Наприклад, зведена форма даної формули. Квантор загальності та існування не можна винести за дужки (пронести через диз’юнкцію), бо змінна х входить в усі доданки. Перейменуємо в області дії першого квантора хнау, а в області другого на z. Далі по черзі пронесемо квантори через диз’юнкцію:
випереджена нормальна форма, яка рівносильна даній формулі.
При аналізі формул логіки предикатів на виконуваність зручно мати формулу, яка не містить кванторів існування, а її матриця представлена у кон’юнктивній нормальній формі (кнф). Вилучення кванторів існування із префікса ВНФ проводять за допомогою введення сколемівських сталих та сколемівських функцій за правилом:
1. Знайти перший зліва на право квантор існування. Якщо він знаходиться у префіксі на першому місці, то замість змінної, яка зв’язана цим квантором, скрізь у матриці поставити деяку сколемівську сталу, яка у формулі ще не зустрічалась, а квантор існування видалити.
2. Якщо квантор існування не на першому місці префікса, наприклад то замість змінної хі скрізь у матриці поставити деяку сколемівську функцію f (х1х2,… хп), яка у формулі ще не зустрічалась, а квантор існування видалити.
3. Перейти до пункту 1, аж поки не видалиться останній квантор існування. У результаті таких перетворень отримується нова формула, яка називається сколемівською стандартною формулою (ССФ).
Наприклад, розглянемо крок за кроком сколемізацію формули
;
1. Замість х вводимо сталу а:;
2. Комбінація кванторів читається «для довільних у та z існує і може трактуватись, як означення деякої функції. Після підстановки цієї функції у матрицю отримаємо нову формулу:
;
3. Комбінація кванторів рівносильна існуванню функції f=g (y, z, w). Вилучаємо останній квантор існування і маємо ССФ для А:.
У ССФ сколемівські функції і сталі вибираються довільно, тому у загальному випадку формули, А та не рівносильні. Але при дослідженні типу формули корисне твердження:
Теорема. Формула, А є суперечністю тоді і тільки тоді, коли її сколемівська стандартна форма є суперечністю.
1.4 Метод резолюцій
Основна ідея методу резолюцій, який розглядається у логіці висловлень, зберігається і у логіці предикатів. Нагадаємо основні означення і факти.
Бінарною резольвентою R (Dl, D2) двох диз’юнктів Dl і D2 називається диз’юнкція літералів, що залишається після видалення пари контрарних.
Наприклад, якщо Dl = р1, D2=, то R (D1, D2) = q. Тут резольвента є висновком, який отримується за правилом modus ponens з посилок р та. Аналогічно резольвента D1= і D2= ілюструє правило силогізму: R (D1, D2) =. Отже, правило резолюції, яке відкрив Дж. Робінсон (1965 p.), є сильнішим з усіх схем логічного висновку, якими користується людина. Це випливає з теореми, яка справедлива у самому загальному випадку.
Теорема. Якщо для диз’юнктів Dl і D2 існує резольвента R (D1, D2), то вона є логічним наслідком цих диз’юнктів: Dl, D2R (D1, D2).
Множина диз’юнктів Dl, D2,… Dn називається невиконуваною, якщо формула тотожно хибна.
Якщо можна встановити, що деяка формула F хибна, то можна відповісти, чи є логічне слідування А1, А2, …, АnB, оскільки для цього потрібно дослідити, чи буде формула хибною.
Методом резолюцій називається послідовне отримання бінарних резольвент із заданих диз’юнктів та з усіх тих, що утворюються. [2, ст. 30]
Застосовуючи метод резолюцій, можна отримати резольвенту, у якій не залишиться жодного літерала. Кажуть, що отримали порожній диз’юнкт ?.
Теорема (про повноту методу резолюцій) Множина диз’юнктів S не виконувана тоді і тільки тоді, коли у результаті застосування методу резолюцій до множини S отримується порожній диз’юнкт ?.
Є багато різних процедур для реалізації методу резолюцій: локрезолюція, метод насичення рівня, стратегія викреслювання тощо.
У логіці предикатів для дослідження невиконуваності множини диз’юнктів потрібно провести додаткову процедуру уніфікації формул. Тут літералом є елементарна формула, терми якої можуть містити змінні, сталі або вирази із функціональних символів і термів. P (x, f (y), b), приклади літералів.
Підстановкою у літерали термів замість змінних можна отримати різні частинні випадки (приклади) літерала. Наприклад, частинними випадком першого літерала можуть бути P (z, f (a), b), P (g (z), f©, b), P (с, f (a), b). Останній частинний випадок називається атомом, бо не містить змінних. Підстановку терма t замість змінної х позначають Одночасно можна виконати кілька замін. їх групують у підстановку. Наприклад, перший частинний випадок отримано у результаті підстановки другий —, третій. У загальному випадку де всі - різні змінні, — терми. Застосування підстановки до літерала позначають Р0. Послідовне виконання двох підстановок та дає третю .
Множина літералів {L1, L2,… Ln} називається уніфікованою, якщо існує така підстановка, що Підстановка називається уніфікатором множини літералів {Li}. Уніфікатор множини формул називається найзагальнішим, якщо для кожного уніфікатора цієї множини існує підстановка, що .
Існує алгоритм уніфікації, який починає роботу з порожньої підстановки і крок за кроком знаходить множину неузгодженості в літералах і будує найзагальніший уніфікатор, якщо він є. Наприклад, для літералів L1=P (x, f (y), b) та L2=P (a, f (b), b) перша множина неузгодженості W1=(x, a). Щоб ліквідувати неузгодженість, робимо підстановку =P {a, f (y), b), =P (a, f (b), b). Друга множина неузгодженості W2={y, b}. Після підстановки у новоутворені літерали отримаємо однакові літерали. Отже, є найзагальнішим уніфікатором. Кожен елемент множини неузгодженості повинен бути термом або літералом. Якщо множина неузгодженості не містить змінних, то така множина літералів не уніфікується. [2, ст. 32]
Нехай деякий диз’юнкт D містить літерали для яких існує спільний уніфікатор. Тоді замість к літералів залишають один і така процедура називається склейкою.
Нехай є два диз’юнкти і і всі змінні у них різні. Диз’юнкт, містить літерал, а диз’юнкт містить літерал, причому існує уніфікатор такий, що. Бінарною резольвентою і у логіці предикатів називається диз’юнкція літералів, які залишаються після викреслювання уніфікованих.
Перед побудовою резольвент спочатку виконують склейку у кожному диз’юнкті (якщо це можливо). У логіці предикатів теж справедлива теорема про повноту методу резолюцій. Наприклад, для перевірки логічного слідування? методом резолюцій потрібно:
1. Утворити формулу. При цьому у кожній посилці та висновку змінні перейменувати, позначивши усі різними буквами, оскільки вони можуть мати різний зміст.
2. Знайти сколемівську стандартну форму цієї формули і записати її матрицю у кон’юнктивній нормальній формі ;
3. До множини диз’юнктів застосувати метод резолюцій провівши, за необхідності, уніфікацію літералів. Якщо у результаті побудови всіх можливих резольвент отримується порожній диз’юнкт ?, то множина диз’юнктів невиконувана, формули і тотожно хибні, отже, є логічне слідування.
2. Методична розробка з модуля «логіка предикатів»
2.1 Приклади розв’язання практичних завдань до підрозділів модуля логіки предикатів
2.2.1 Предикати. Логічні операції над предикатами
Приклад 1. Які з наведених речень є предикатами (для предикатів вказати місність):
a) «х паралельна прямій l (х — довільна пряма на площині);
b) «х є притокою у» (х, у — назви всіх можливих рік);
c) «деякі парні числа діляться на натуральне число у»;
d) «всі непарні числа діляться на 2»;
e) «х або Україна і Росія» (х — назва країни);
f) (х, у — дійсні числа);
g) (х, у — дійсні числа);
h) «для довільного х0 існує п, що ху = 1».
>а) l-місний предикат, який перетворюється в істинне висловлення на множині всіх прямих, які паралельні до фіксованої прямої l. b) 2 — місний предикат, який може перетворюватися або в істинне висловлення (наприклад, Десна є притокою Дніпра), або в хибне (Десна є притокою Волги). с) 1-місний предикат, який перетворюється завжди в істинне висловлення (тотожно істинний), оскільки існують парні числа виду 2у, 4у, 6у, які діляться на y.d) 0-місний предикат, який є хибним висловленням, е), f) Не предикати, оскільки при довільній підстановці замість змінних конкретних значень речення не можуть бути висловленнями.g) 2-місний предикат, який перетворюється в хибне висловлення при будь-яких дійсних х та у (тотожно хибний).h) 0-місний предикат, який є істинним висловленням.
Приклад 2. Знайти множину істинності предикатів:
a) ;
b) ;
c) Р (х) = «відрізок АВ видно з точки х під прямим кутом»;
d) Р (х) = «точка х рівновіддалена від точокА і В»;
e) .
>а) Множина істинності даного предиката — це множина розв’язків нерівності, яка перетворюється у істинне висловлення лише тоді, коли 1, отже. b) = [-8; 2]. c) Множина істинності - множина точок кола, яке побудоване на відрізку АВ як на діаметрі, крім самих точок, А та В.d) Множина істинності - всі точки серединного перпендикуляра для відрізка АВ.е) Множина істинності - всі точки координатної площини, що знаходяться у другому (утворюється еквіваленція двох хибних висловлень) та четвертому (еквіваленція двох істинних висловлень) квадрантах та на координатних осях.
Приклад 3. Прочитати висловлення та визначити, які з них істинні, а які хибні, вважаючи, що всі змінні належать множині дійсних чисел:
a) ;
b) ;
c) ;
d) ;
> а) Навішування квантора загальності по х приведе до істинного висловлення, якщо одномісний предикат на множині дійсних чисел тотожно істинний. При довільному висловленняістинне, оскільки предикат виконуваний (він перетворюється в істинне висловлення при). Отже, предикат А (х) тотожно істинний, тому висловлення, яке читається так: «Для довільного дійсного х існує дійсне у, що x + y = 3», істинне. b) Висловлення «Існує дійсне у, що його сума з довільним дійсним х дорівнює 3» очевидно хибне. Дійсно, предикат тотожно хибний, бо для довільного предикат спростовний (перетворюється в хибне висловлення, наприклад, при). с) Висловлення «Якщо сума двох довільних дійсних чисел дорівнює 3, то 2= 3″ істинне, оскільки є імплікацією двох хибних висловлень. d) Висловлення „Довільне дійсне число х дорівнює самому собі тоді і тільки тоді, коли воно або більше за 1, або менше за 2″ є істинним, бо предикат є тотожно істинним як еквіваленція двох предикатівта“ (х = х)», які перетворюються в істинне висловлення при довільних xR.
Приклад 4. Дано предикати А (х) та В (х). Записати реченням висловленняС та В:
a) А (х) = «х-студент», В (х) — «х — склав іспити»,
;
b) А (х) = «х: — гриб», В (х)= «х — їстівний»,
;
c) А (х)= «х — наука», В (х) — «х — гуманітарна»,
.
> а) Висловлення С — частково заперечувальне (О): «Є студенти, які не склали іспити»; D — загальиостверджувальне (A): «Всі студенти склали іспити». b). Висловлення С — частково заперечувальне (О): «Є неїстівні гриби»; D — загальнозаперечувальне (Е): «Всі гриби неїстівні». с) Висловлення С — заперечення загальностверджувального: «Не всі науки гуманітарні», а це за змістом рівносильне твердженню «Існують негуманітарні науки», яке символічно записується як D — частково стверджувальне (I): «Існують гуманітарні науки».
Приклад 5. Записати речення у символічній формі, ввівши доречні у кожному випадку предикати:
a) Мухтар — собака;
b) деякі журналісти були в космосі;
c) якщо число ділиться на 12, то воно ділиться на 2,4 і 6;
d) громадяни Бельгії обов’язково володіють або німецькою, або французькою мовою;
е) деякі студенти здали всі екзамени;
f) кожен студент не здав принаймні один екзамен;
g) кожна людина знає англійську мову, або має друга, який знає англійську мову.
а) Якщо А (х) = «х — собака» — предикат, визначений на множині всіх тварин, а т — позначення клички Мухтар, то символічний записданого речення: А (т).b) Визначимо на множині всіх людей предикати А (х) = «х — журналіст» та В (х) = «х — був у космосі». Зі змісту речення зрозуміло, що «дослівний» переклад такий: існують люди, які одночасно є журналістами і були у космосі. Тому можна записати:. Зауважимо, що запис не відповідає даному реченню, оскільки перетворюється в істинне висловлення навіть для тих x, які не є журналістами. Якби предикат В (х) був визначений на множині всіх журналістів, то речення можна було б записати коротко: .с) Задамо на множині натуральних чисел предикати А (х) = «х — ділиться на 12», В (х) = «x — ділиться на 12», C (х) = «х — ділиться на 4″, D (x) = „х — ділиться на 6″. Оскільки у реченні йдеться про довільне число, то застосуємо квантор загальності:. d) Після введення на множині всіх людей предикатів А (х)= „х-громадянин Бельгії“, В (х)= „х — володіє німецькою“, С (х)= „х — володіє французькою мовою“ дане речення можна символічно записати: .е) Для опису відношень між різними об'єктами (студенти та екзамени) використовуються також і багатомісні предикати. Нехай А (х) =“ х — студент», В (у)= «у — екзамен», С (х, у)= «х здав екзамен у». Тоді дане речення можна перефразувати «існують студенти х, що який би не був екзамену, вони його здали» і записати:. f) Дане речення за змістом протилежне до попереднього, тому використаємо ті самі предикати. Потрібно записати, що «для кожного студента х існує екзамен у і він його не здав»: .g) Введемо предикати А (х) = «х — знає англійську мову» та В (х, у) — «х друг у». Речення «для кожної людини х або вона знає англійську, або існує друг у, що знає англійську» символічно записується: .
Приклад 6. Записати мовою логіки предикатів означення:
a) простого натурального числа;
b) точки локального максимуму функції f (x);
> а) За означенням натуральне число х просте, якщо воно не дорівнює 1 і при довільному розкладі його на добуток натуральних чисел одне з них є саме цс х або 1. Це можна записати:. Після введення предикатівР (х, у)= «х =у» та Q (x, y, z)= «z=xy» цей вираз можна записати:).b) Точка з області визначення функції f (х) називається точкою локального максимуму, якщо існуєтакий її - окіл, що для всіх точок х з цього околу виконується f (x)
.
Приклад 7. Нехай xR, а В (х) — предикат, у якому стверджується, що хмає властивість В. Записати наступні речення мовою логіки предикатів:
a) існує хоча б один xRтакий, що В (х);
b) не більше одного xRмають властивість В (х);
c) існує один і тільки один xRтакий, що В (х);
d) існує два різних xRтаких, що В (х);
е) не більше двох xR мають властивість В (х).
> а) Речення має такий самий зміст, як і речення «Існує xR такий, що В (х)» і має запис .b) Речення має такий зміст: якщо довільні два елементиxR та yRмають властивість В, то вони рівні. Це має символічний запис:. с) Речення рівносильне кон’юнкції речень з пунктів а) та b).
d) Потрібно підкреслити, що існують елементиxR та yR, які мають одночасно властивість В і не рівні:.е) Речення має такий зміст: якщо довільні три елементи xR, yR, zRмають властивість В, то принаймні два з них рівні. Це має символічний запис:.
2.2.2 Класифікація формул логіки предикатів. Логічне слідування
Приклад 1. Визначити, які з наведених виразів є формулами логіки предикатів (для формул вказати тип (відкрита чи замкнута) і назвати вільні та зв’язані входження змінних):
a) ;
b) ;
c) ;
d) ;
e) ;
f) ;
g) ;
h) .
> а) Не формула, оскільки квантор загальності не навішується на формулу. b) Формула, у якій головною є операція імплікація, в області дії квантора загальності - елементарна формула Р (х) Формула відкрита, бо містить вільне входження х у висновку імплікації, с) Не формула, оскільки вираз у дужках містить змінну х, яка вже не є вільною.
d) Відкрита формула, у якій головною операцією є навішування квантора Існування по х, а змінна y є вільною, е) Відкрита формула, у якій головна операція — імплікація, у посилці змінні х та у зв’язані, а у висновку х вільна. f) Замкнута формула, оскільки всі змінні знаходяться в області дії кванторів за цими змінними. g) Не формула, оскільки вираз не є формулою.
h) Відкрита формула, у якій змінні х та z частково вільні (або частково зв’язані), а змінна y зв’язана. <
Приклад 2. Якою є формула у кожній інтерпретації:
а) ;
b) ;
c).
>а) Уданій інтерпретації формула перетворюється на двомісний предикат, визначений на множині дійсних чисел. Це не тотожність, але існує, наприклад, набір x=1, y=0 з області інтерпретації M, на якому отримується істинне висловлення. Отже, в даній інтерпретації формула виконувана. b) У даній інтерпретації формула перетворюється па двомісний предикат, визначений на інтервалі (0; 2]. Цей предикат рівносильний, який перетворюється в істинне висловлення, якщо або (тобто від'ємне), а це неможливо на даному інтервалі. Отже, в даній інтерпретації формула хибна. с) У даній інтерпретації формула перетворюється на двомісний предикат, визначений на інтервалі (0; 1). При довільній підстановці замість xта yзначень з даного проміжку отримуємо істинне висловлення, як сума двох додатних доданків. Отже, в даній інтерпретації формула істинна.
Приклад 3. Проінтерпретувати кожну з формул:
a) тана множиніМ = {Іван, Петро}, якщо Р (х) — 'ім'я х містить 5 букв", у = Іван;
b) та на множиніМ = N, якщо Р (х) — «х <2»;
c) та на множині M=N, якщо P (х) = «x<5″ та Q (x) =» x> 6″. [2, ст. 37]
>а) Підставляючи y= Іван замість вільного у маємо Отже, перша формула перетворюється у хибневисловлення. У другій формулі головна операція імплікація. Предикат Р (х) спростовний, тому і .b) Предикат Р (х) є виконуваним на М, тому. Предикат теж виконуваний, тому. c) Предикат тотожно хибний, тому перша формула перетворюється нахибне висловлення. Кожен з предикатів P (x) та Q (x) є виконуваним, тому .
Визначити істинне значення кожної з формул при всіх значеннях вільної змінної:
a); c);
b); d)
> а) При кожному значенні вільної змінної у операцію навішування квантора загальності по х на скінченній множині замінимо кон’юнкцією:
;
;
;
b) Аналогічно операцію навішування квантора існування замінимо диз’юнкцією:
;
;
c);
d)¦.<
Приклад 5. Показати, що при інтерпретації формули на довільній одноелементній множині завжди отримується істинне висловлення, а на двоелементній — не завжди.
> Нехай є одноелементна множина М = {а}. Оскільки множина значень довільного предиката складається з 0 та 1, то на цій множині можна задати лише два конкретних предикати: або .
Нехай є двоелементна множина М ={а, b}. На ній можна задати вже чотири різні предикати та так, що:. Усі можливі інтерпретації запишемо у таблиці:
Р | y | Р (y) | |||
а | |||||
b | |||||
а | |||||
b | |||||
а | |||||
b | |||||
а | |||||
b | |||||
Легко тепер наповнити інтерпретацію, у якій формула перетворюється на хибне висловлення, конкретним змістом. Нехай М = {5,6}, а. Тоді, і. <[26, ст. 48]
Приклад 6. Встановити, чи виконувані формули логіки предикатів:
a); e);
b); f);
c); g) ;
d); h) .
а) Якщо формула має простий вигляд, то для доведення її виконуваності достатньо навести приклад хоча б однієї інтерпретації, у якій вона перетвориться на істинне висловлення. Щоб формула була істинним висловленням, потрібно щоб предикат був тотожно істинним. Наприклад, при, матимемо, тому формула виконувана. b) Інколи потрібно провести аналіз формули, щоб отримати протиріччя або підказку, якою має бути інтерпретація. Припустимо, що дана замкнута формула виконувана, тобто існує деякий двомісний предикат, визначений на множині М, що формулаперетворюється у істинне висловлення: .
Навішування квантора існування дає істинне висловлення, якщо предикат виконуваний. Тобто існує, що. Навішування квантора загальності по удає істинне висловлення, якщо предикат тотожно істинний. Це означає, що він повинен перетворюватися у істинне висловлення при довільних, а, отже, і при. А це неможливо, Бо. Припущення про те, що формула виконувана, привело до протиріччя, отже, вона не виконувана і є суперечністю.с) Ця формула виконувана, оскільки вона виконувана у будь-якій інтерпретації з одноелементною множиною (див. приклад 5). d) Ця формула була б виконуваною, якби у деякій інтерпретації предикат був тотожно істинним. А це неможливо, оскільки при довільних значеннях з області інтерпретації висловлення. Отже, формула не виконувана. е) Нехай дана відкрита формула виконувана: існує предикат на множині М і елемент, що. Тоді за означенням кон’юнкції та. З другої умови випливає, що предикат тотожно істинний, тобто, перетворюється у істинне висловлення при всіх у, а, отже, і при, аз першої умови маємо. Отримали протиріччя, отже, формула не виконувана. f) Нехай формула виконувана, тобто існують предикати та, що. Це означає, що в області інтерпретації існує елемент х0, що висловлення, тобто предикат тотожно істинний. Тут нема протиріччя. Достатньо вибрати тотожно хибний предикат і буде тотожно істинним при довільному. Наприклад, при, визначених на множині дійсних чисел, та при довільному предикат В (у) тотожно істинний, бо при всіх матимем:. Отже, формула виконувана. g) Нехай виконувана: у деякій інтерпретації маємо
. Тобто предикат тотожно
істинний, при всіх з області інтерпретації. Це означає, що існує таке, що. Оскільки це виконується при всіх, то предикат тотожно істинний. Тоді і. Отримали протиріччя. Формула не виконувана. h) Нехай виконувана: у деякій інтерпретації маємо
. Звідси існує, що. Далі існує у0, що. Отже, предикат повинен бути таким, щоб для деяких та виконувалось: та. Це може бути довільний спростовний предикат, наприклад на множині натуральних чисел. Тоді існують, наприклад, та, що. Отже, дана формула виконувана і її можна у даній інтерпретації прочитати так: «Серед натуральних чисел є більші за 5 і не більші за 5».
Приклад 7. Встановити, які з формул є тавтологіями логіки предикатів:
a);
b) ;
c) ;
d) ;
e) ;
f) .
>а) Очевидно, що формула не тавтологія, бо перетворюється у хибне висловлення, коли предикат Р (х) виконуваний і спростовний, тобто якщо і. Наприклад, Р (х)= «х-парне число» на множині N.b) Припустимо, що формула не тавтологія: існує на деякій множині М предикат, що, тобто і. З першого висловлення за означенням квантора існування випливає, що існує таке, що звідки випливає, що предикат (*) тотожно істинний. З другого висловлення випливає, що існуєтаке, що, а це означає, що предикат (**) тотожно хибний. Оскільки та належать області інтерпретації, то з (*) маємо, а з (**) — що. Це протиріччя доводить, що формула тавтологія, с) Нехай Q (x, y)= «x, y» на множині натуральних чисел. Тоді (для кожного натурального числа існує більше за нього) і (не існує найбільшого натурального числа). У даній інтерпретації формула перетворюється у хибне висловлення, тому не є тавтологією.d) Нехай дана відкрита формула не тавтологія: існують предикати і, що. Звідси та. Предикат не тотожно істинний, тому існує, що. Не отримали протиріччя, але маємо підказку, що інтерпретація, у якій формула перетвориться у хибне висловлення, повинна бути такою, щоб, і .
Наприклад, можна на множині натуральних чисел задати .Тоді. Отже, формула не тавтологія, е) Якби у деякій інтерпретації формула була хибною, то посилка імплікації, а висновок хибний. Це означає, що одне з висловлень або істинне. Тобто, один з предикатів або тотожно істинний. Тоді їх диз’юнкція тотожно істинний предикат, а тому висновок імплікації. Отже, при істинній посилці висновок не може бути хибним. Формула є тавтологією. f) Розглянемо інтерпретацію на множині натуральних чисел = «х-парне» та = «x-непарне». Тоді посилка = ¦ «довільне число парне або непарне"¦ = 1, а висновок = «довільне число парне»? «довільне число непарне"|=. Формула у цій інтерпретації хибна, тому вона не тавтологія. <[25, ст. 36]
Приклад 8. Довести, що формули є тавтологіями логіки предикатів (тут формулаА не містить вільних «змінних):
a) ;
b) ;
c) ;
d) ;
e) ;
f) .
а) Припустимо, що формула не тавтологія. Тобто існує предикат на деякій множині М і елемент, що. Тоді
і. З першої умови випливає, що тотожно істинний предикат, що суперечить другій умові. Отже, припущення не вірне, формула тавтологія. b) Якщо формула містить еквіваленцію, то доведення того, що вона істинна в будь-якій інтерпретації, можна проводити одним із шляхів, залежно від вигляду лівої і правої частини.
Наприклад, щоб довести, що, розглянемо довільну інтерпретацію з предикатом на деякій множині М, на якій ліва частина перетворюється в істинне висловлення (за першою схемою). Тоді. За означенням навішування квантора загальності предикат — спростовний, тоді - виконуваний. Отже, — права частина в цій інтерпретації теж перетворюється в істинне висловлення. Навпаки, якщо права частина у деякій інтерпретації, то за означенням квантора існування виконуваний, отже, Р0(х) — спростовний і. Тоді ліва частина теж Отримали, що у довільній інтерпретації ліва та права частини еквіваленції мають однакове логічне значення, тому формула є тавтологією, с) Нехай ліва частина формули у деякій інтерпретації - Тоді предикат тотожно істинний, а це можливо, лише коли кожен з предикатів Р (х) та Q (x) тотожно істинний. Тоді обидва висловлення та істинні, тому їх кон’юнкція у правій частині формули теж істинна. Навпаки (за першою схемою) міркуємо аналогічно. d) Нехай у деякій інтерпретації ліва частина формули хибна:. Тоді предикат тотожно хибний. ОскількиА не містить вільних змінних, то вона може перетворюватися як у істинне, так і в хибне висловлення. Якщо, то з хибності випливає, що P (x) тотожно хибний. Тоді і права частина. Якщо, то для будь-якого предиката Р (х) права частина теж 0. Навпаки, якщо справа, то або — і тоді тотожно хибний предикат і, або — і тоді Р (х) тотожно хибний, тотожно хибний і ліва частина теж. За другою схемою обидві частини формули мають однакове значення істинності у будь-якій інтерпретації, тому маємо тавтологію. е) За першою схемою, якщо, то існує елемент, що. При повинно, тобто Р (х) спростовний, і. При права частина істинна завжди. Навпаки доводимо аналогічно. f) Якщо зліва, то предикат тотожно істинний. При повинен бути тотожно істинним, томуі справа При завжди матимемо. У другу сторону доводимо аналогічно.
Приклад 9. Перевірити, чи правильні міркування:
a) всі ромби є паралелограмами. Всі квадрати — ромби. Отже, всі квадрати — паралелограми;
b) кожний ромб є паралелограмом. Деякі паралелограми — квадрати. Отже, деякі ромби — квадрати;
c) кожний математик мислить логічно. Той, хто мислить логічно, не робить логічних помилок. Іван робить логічні помилки. Отже, Іван — не математик.
>а) Введемо предикати М (х)= «x — ромб», S (x)= «x-квадрат» та P (x)= «x — паралелограм». Формулою дані міркування можна записати так: ?. Маємо силогізм ААА першої фігури, який називають Barbara. Припустимо, що міркування не правильні (нема логічного слідування). Тобто, існує інтерпретація, у якій обидві посилки перетворюються в істинні висловлення, а висновок — у хибне, а
Тоді предикати татотожно істинні, а предикат спростовний. Тобто існує в області інтерпретації елемент, що, звідси, а Оскільки повинно бути, що то. Тоді, а це перечить тому, що предикат тотожно істинний. Отримане про тиріччя доводить правильність міркувань. b) За допомогою предикатів прикладу а) дані міркування запишуться формулами: ?. Тут встановлюється відношення між М та Sчерез Р. Це силогізм четвертої фігури AII. Припустимо, що міркування нелогічні. Тобто, існує інтерпретація, у якій, а Тоді
Предикат тотожно істинний, предикат виконуваний, а предикат тотожно хибний. З виконуваності предиката випливає, що існує в області інтерпретації елемент, такий що, звідси і. Оскільки повинно бути, що, то. Тоді. Суперечності не отримали. Тому правильне припущення про нелогічність таких міркувань. Висловлення посилок та висновку можна ілюструвати кругами Ейлера. З ілюстрації міркувань для прикладів а) та b) видно, що у першому випадку висновок очевидний, а у другому з двох даних посилок випливає, що ромби можуть не бути квадратами. Щоб отримати висновок про те, що деякі ромби — квадрати, потрібно вибрати інші посилки. с) Введемо М (х)= «х-математик», S (x)= «x-мислить логічно» та Р (х)= «x — робить логічні помилки», І=Іван. Формулою дані міркування можна записати так:
?. Нехай міркування нелогічні, тоді всі посилки істинні, а висновок хибний:, але. Звідси випливає, що предикатитатотожно істинні, і. Оскільки повинно, то. Тоді, а це суперечить тому, що предикат тотожно істинний. Отже, висновок у даних міркуваннях отримано правильно. Проілюструйте це за допомогою кругів Ейлера.
>а) Формули утворюють окремий випадок закону контрапозиції алгебри висловлень висловлень, тому вони рівносильні b) Оскільки фрмули рінносильні, якщоїх еквіваленція є тавтологією ?, то при доведенні можна користуватись однією із схем прикладу 8 попереднього параграфа. Нехай існує, інтерпретація, у якій ліва частинаЦе можливо, коди предикат Р (х)>Р (у0) спростовний. Тобто, існує елемент що. Звідси і. Отже предикат Р (x) спростовний і виконуваний. Але тодіі права частина, у цій інтерпретації. Тому формули не рівносильні. Далі для доведення рівносильності формул можна використовувати раніше виведені рівносильності і намагатись звести ліву і праву частини до однакового вигляду. Наприклад, a. Очевидно, що формули виду та не можуть бути рівносильними. с) Перетворимо ліву та праву частини: .
Очевидно, що формули не рівносильні. Легко навести приклад відповідної інтерпретації. Нехай Р (х)= «х>5», Q (x)= «x>10» — спростовні предикати на N. Тоді предикат Р (х)>Q (x) спростовний, бо перетворюється в хибне висловлення, наприклад, при х = 7. Тому ліва частина хибна, а права у цій же інтерпретації
Приклад 2. Записати зведену форму формул логіки предикатів та перетворити її на випереджену:
a) та ;
b) ;
с);
d);
e);
f);
g) .
> а) Виразимо імплікацію через диз’юнкцію та скористаємось законами де Моргана для кванторів: та. Отримали зведені форми даних формул. Винести квантор загальності за дужки у першій формулі не можна, оскільки нема дистрибутивного закону для диз’юнкції. Потрібно у одному з доданків перейменувати змінну х якоюсь іншою буквою:. Далі по черзі проносимо квантори загальності через диз’юнкцію: — ВНФ. У другій формулі використовуємо відповідний дистрибутивний закон для квантора існування: — ВНФ
b)
;
зведена форма. Квантор існування по х та zможна пронести через диз’юнкцію, а змінну у в області дії квантора перейменуємо на t:
.
с)
— зведена форма. Квантори поу та zможна винести за дужки, а змінну х в області дії квантора загальності перейменуємо:
— ВНФ.
d)
;
зведена форма. Щоб винести квантор загальності по y за дужки, в області дії цього квантора замінимо у на
z: — ВНФ.
е)
- зведена форма.
випереджена нормальна форма. Тут у перших дужках квантор існування пронесли через диз’юнкцію, а у другому множнику зробили заміну зиінних і пронесли усі квантори почергово через кон’юнкцію.
ВНФ, матриця якої записана у кон’юнктивній нормальній формі. Така форма називається клаузальною.
— ВНФ.
Приклад 3. Записати сколемівські стандартні форми (ССФ) для всіх формул з прикладу 2.
> а) Префікс не містить кванторів існування, тому сколемівська форма рівносильна самій формулі:. У другій формулі замість х підставимо деяку сталу а: .
b) Перші два квантори існування вилучаємо, замінивши змінні х та zдеякими сталими, а та b: .
с) Спочатку замість х вводимо сталу а:. Перед квантором існування по z є квантор загальності по у, тому замість z вводимо деяку сколемівську функцію z=f (y):
d).
e) .
f) Тут потрібно замість х ввести деяку функцію :
.
g) .<
Множина диз’юнктів не породжує жодної резольвенти. Отже, неможливо отримати порожній диз’юнкт, тому таке міркування не логічне.
c) Введемо предикати І(х) = «х — вміє обчислювати інтеграли»,
М (х) = «х — математик», З (х) = «х — маж математичні здібності»,
D (x) = «х — дитина». Тоді всі посилки та висновок можна записати:
? Далі:
Виписуємо диз’юнкти і резольвенти:
(1)
(2)
(3)
(4)
(5)
(6) із (1), (2) після
(7) із (1), (3) після
(8) із (2), (4) після
(9) із (3), (5) після
(10) із (1), (8) після
(11)? із (9), (10).
(12)
(13) Тут не виписані зайві диз’юнкти за методом насичення рівня, оскільки порожній диз’юнкт отримується очевидно. Отже, дане міркування логічне і правильне.
2.2 Тестові завдання для контролю знань і вмінь з даного модуля
І варіант
I рівень
(Виберіть ОДНУ правильну відповідь)
1. (п+т) — місний предикат, заданий на множині MЧL, який перетворюється в істинне висловлення для всіх тих і тільки тих значень змінних, при яких перетворюються в істинне висловлення обидва задані предикати називається:
А) диз’юнкцією двох предикатів Р і Q;
Б) запереченням двох предикатів Р і Q;
В) кон’юнкцією двох предикатів Р і Q;
Г) рівносильним для двох предикатів Р і Q.
2. Якщо і - множини істинності предикатів Р та Q, визначених на одній множині М, то множини істинності предикатів можна записати так:
А)
Б)
В)
Г)
3. Якщо і - множини істинності предикатів Р та Q, визначених на одній множині М, то множини істинності предикатів можна записати так:
А)
Б)
В)
Г)
4. Виберіть літеру, запис якої відповідає загальностверджувальному судженню «всі S суть Р» (всі елементи х, які мають властивість S, мають і властивість Р):
А)
Б)
В)
Г)
5. Для предикатів Р (х) = «» та Q (x) = «x=sin» справедливо, що А) Р (х) та Q (x) тотожно хибні;
Б) Q (x) є логічним наслідком P (x);
В) Р (х) та Q (x) рівносильні;
Г) Р (х) є логічним наслідком Q (x).
6. Нехай xR, а В (х) — предикат, у якому стверджується, що х має властивість В. Записати речення «існує хоча б один xRтакий, що В (х)» мовою логіки предикатів:
А)
Б)
В)
Г)
7. Якщо на множині натуральних чисел задано предикати Е (х) = «x — парне число», D (x, y) = «y ділиться на х», то висловлення українською мовою можна прочитати так:
А) будь-яке натуральне число ділиться на 2 і є парним;
Б) деяке натуральне число ділиться на 2 або є парним;
В) будь-яке натуральне число, яке ділиться на 2, є парним;
Г) деяке натуральне число, яке ділиться на 2, є парним.
8. Якщо формула істинна в будь — якій інтерпретації, то вона називається:
А) істинною в даній інтерпретації;
Б) виконуваною в даній інтерпретації;
В) логічно загальнозначущою в даній інтерпретації;
Г) суперечністю в даній інтерпретації.
9. Якщо формула виконувана хоча б в одній інтерпретації, то вона називається:
А) істинною в даній інтерпретації;
Б) виконуваною в даній інтерпретації;
В) суперечністю в даній інтерпретації;
Г) логічно загальнозначущою в даній інтерпретації.
10. Формула у інтерпретації М=[0; 2], є