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

Главная

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

Логічні операції над предикатами. Рівносильні формули. Приклади розв’язання практичних завдань до підрозділів модуля логіки предикатів. Тестові завдання для контролю знань і вмінь з модуля. Організація та методика проведення тестування з математики.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Нехай є деяка множина п-місним предикатом, заданим на множині М, називається речення, що містить змінних (предметні змінні), яке перетворюється на висловлення при підстановці замість цих змінних відповідних конкретних значень М (предметні константи).
Позначаються предикати великими літерами з індексами або без, наприклад . Довільне висловлення є 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) якщо - 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 і Р.
Дві формули А і В називаються рівносильними , якщо кожна з них є логічним наслідком іншої.
Можна довести, що тоді і тільки тоді, коли ?.
В логіці предикатів рівносильними будуть формули, отримані з рівносильних формул алгебри висловлень підстановкою замість пропозиційних змінних довільних формул логіки предикатів (окремі випадки). Наприклад, рівносильними будуть формули
бо вони отримані з рівносильностей і за допомогою різних підстановок.
Крім окремих випадків у логіці предикатів є рівносильності, пов'язані з операцією навішування кванторів. Деякі рівносильності можна записати із тавтологій, що містять головну операцію , доведення яких здійснено у попередньому пункті. Варто пам'ятати рівносильності, що часто використовуються при рівносильних перетвореннях формул та при зведенні їх до нормальних форм:
2) -закони де Моргана для кванторів;
3) -дистрибутивні закони (і тільки такі два!);
4) -закони перенесення кванторів через кон'юнкцію, тут і далі Qне містить вільного x;
5) -закони пронесення кванторів через диз'юнкцію;
-закони пронесення кванторів через імплікацію.
Зведеною формою для формули логіки предикатів називається така рівносильна їй формула, яка або елементарна, або містить лише операції , причому заперечення стосується лише елементарних підформул.
Випередженою нормальною формою для формули логіки предикатів називається така її зведена форма, яка або не має кванторних операцій, або всі вони виконуються останніми.
Випереджена нормальна форма (ВНФ) довільної формули А логіки предикатів має вигляд , де -довільна сукупність кванторів (префікс формули А), а В-формула, яка не містить кванторів (матриця формули А).
Теорема . Для кожної формули логіки предикатів існує зведена та випереджена нормальна форми.
Щоб отримати зведену форму, потрібно скористатися законами, що дозволяють виразити через , , та законами де Моргана. Після застосування дистрибутивних законів та законів пронесення кванторів через логічні операції (винесення кванторів за дужки) отримують випереджену форму. Тут буває необхідно перейменовувати змінні у області дії кванторів, але робити це треба так, щоб не трапилось «колізії». Для перейменовування краще використовувати імена змінних, які у формулі не зустрічаються. Потрібно пам'ятати, що вільні змінні не перейменовуються, а одна і та ж змінна у областях дії різних кванторів може перейменовуватись на різні змінні. Наприклад,
зведена форма даної формули. Квантор загальності та існування не можна винести за дужки (пронести через диз'юнкцію), бо змінна х входить в усі доданки. Перейменуємо в області дії першого квантора хнау, а в області другого на z. Далі по черзі пронесемо квантори через диз'юнкцію:
випереджена нормальна форма, яка рівносильна даній формулі.
При аналізі формул логіки предикатів на виконуваність зручно мати формулу, яка не містить кванторів існування, а її матриця представлена у кон'юнктивній нормальній формі (кнф). Вилучення кванторів існування із префікса ВНФ проводять за допомогою введення сколемівських сталих та сколемівських функцій за правилом:
1. Знайти перший зліва на право квантор існування. Якщо він знаходиться у префіксі на першому місці, то замість змінної, яка зв'язана цим квантором, скрізь у матриці поставити деяку сколемівську сталу, яка у формулі ще не зустрічалась, а квантор існування видалити.
2. Якщо квантор існування не на першому місці префікса, наприклад то замість змінної х і скрізь у матриці поставити деяку сколемівську функцію f(х 1 х 2 ,… х п ), яка у формулі ще не зустрічалась, а квантор існування видалити.
3. Перейти до пункту 1, аж поки не видалиться останній квантор існування. У результаті таких перетворень отримується нова формула:, яка називається сколемівською стандартною формулою (ССФ).
Наприклад, розглянемо крок за кроком сколемізацію формули
2. Комбінація кванторів читається «для довільних у та z існує і може трактуватись, як означення деякої функції. Після підстановки цієї функції у матрицю отримаємо нову формулу:
3. Комбінація кванторів рівносильна існуванню функції f=g (y, z, w). Вилучаємо останній квантор існування і маємо ССФ для А:.
У ССФ сколемівські функції і сталі вибираються довільно, тому у загальному випадку формули А та не рівносильні. Але при дослідженні типу формули корисне твердження:
Теорема. Формула А є суперечністю тоді і тільки тоді, коли її сколемівська стандартна форма є суперечністю.
Основна ідея методу резолюцій, який розглядається у логіці висловлень, зберігається і у логіці предикатів. Нагадаємо основні означення і факти.
Бінарною резольвентою R(D l , D 2 ) двох диз'юнктів D l і D 2 називається диз'юнкція літералів, що залишається після видалення пари контрарних.
Наприклад, якщо D l = р 1 , D 2 =, то R(D 1 , D 2 ) = q. Тут резольвента є висновком, який отримується за правилом modus ponens з посилок р та . Аналогічно резольвента D 1 = і D 2 = ілюструє правило силогізму: R(D 1 , D 2 ) =. Отже, правило резолюції, яке відкрив Дж. Робінсон (1965 p.), є сильнішим з усіх схем логічного висновку, якими користується людина. Це випливає з теореми, яка справедлива у самому загальному випадку.
Теорема. Якщо для диз'юнктів D l і D 2 існує резольвента R(D 1 , D 2 ), то вона є логічним наслідком цих диз'юнктів: D l , D 2 R(D 1 , D 2 ).
Множина диз'юнктів D l , D 2 ,… D n називається невиконуваною, якщо формула тотожно хибна.
Якщо можна встановити, що деяка формула F хибна, то можна відповісти, чи є логічне слідування А 1 , А 2 , …, А n B, оскільки для цього потрібно дослідити, чи буде формула хибною.
Методом резолюцій називається послідовне отримання бінарних резольвент із заданих диз'юнктів та з усіх тих, що утворюються. [2, ст. 30]
Застосовуючи метод резолюцій, можна отримати резольвенту, у якій не залишиться жодного літерала. Кажуть, що отримали порожній диз'юнкт ?.
Теорема (про повноту методу резолюцій) Множина диз'юнктів S не виконувана тоді і тільки тоді, коли у результаті застосування методу резолюцій до множини S отримується порожній диз'юнкт ?.
Є багато різних процедур для реалізації методу резолюцій: локрезолюція, метод насичення рівня, стратегія викреслювання тощо.
У логіці предикатів для дослідження невиконуваності множини диз'юнктів потрібно провести додаткову процедуру уніфікації формул. Тут літералом є елементарна формула, терми якої можуть містити змінні, сталі або вирази із функціональних символів і термів. P (x, f(y), b), приклади літералів.
Підстановкою у літерали термів замість змінних можна отримати різні частинні випадки (приклади) літерала. Наприклад, частинними випадком першого літерала можуть бути P (z, f(a), b), P (g(z), f(c), b), P (с, f(a), b). Останній частинний випадок називається атомом, бо не містить змінних. Підстановку терма t замість змінної х позначають Одночасно можна виконати кілька замін. їх групують у підстановку. Наприклад, перший частинний випадок отримано у результаті підстановки другий - , третій . У загальному випадку де всі - різні змінні, - терми. Застосування підстановки до літерала позначають Р 0 . Послідовне виконання двох підстановок та дає третю .
Множина літералів {L 1 , L 2 ,… L n } називається уніфікованою, якщо існує така підстановка , що Підстановка називається уніфікатором множини літералів {L i }. Уніфікатор множини формул називається найзагальнішим, якщо для кожного уніфікатора цієї множини існує підстановка, що .
Існує алгоритм уніфікації, який починає роботу з порожньої підстановки і крок за кроком знаходить множину неузгодженості в літералах і будує найзагальніший уніфікатор, якщо він є. Наприклад, для літералів L 1 =P (x, f(y), b) та L 2 =P (a, f(b), b) перша множина неузгодженості W 1 =(x, a). Щоб ліквідувати неузгодженість, робимо підстановку =P {a, f(y), b), =P (a, f(b), b). Друга множина неузгодженості W 2 ={y, b}. Після підстановки у новоутворені літерали отримаємо однакові літерали. Отже, є найзагальнішим уніфікатором. Кожен елемент множини неузгодженості повинен бути термом або літералом. Якщо множина неузгодженості не містить змінних, то така множина літералів не уніфікується. [2, ст. 32]
Нехай деякий диз'юнкт D містить літерали для яких існує спільний уніфікатор. Тоді замість к літералів залишають один і така процедура називається склейкою.
Нехай є два диз'юнкти і і всі змінні у них різні. Диз'юнкт , містить літерал , а диз'юнкт містить літерал , причому існує уніфікатор такий, що . Бінарною резольвентою і у логіці предикатів називається диз'юнкція літералів, які залишаються після викреслювання уніфікованих.
Перед побудовою резольвент спочатку виконують склейку у кожному диз'юнкті (якщо це можливо). У логіці предикатів теж справедлива теорема про повноту методу резолюцій. Наприклад, для перевірки логічного слідування ? методом резолюцій потрібно:
1. Утворити формулу. При цьому у кожній посилці та висновку змінні перейменувати, позначивши усі різними буквами, оскільки вони можуть мати різний зміст.
2. Знайти сколемівську стандартну форму цієї формули і записати її матрицю у кон'юнктивній нормальній формі ;
3. До множини диз'юнктів застосувати метод резолюцій провівши, за необхідності, уніфікацію літералів. Якщо у результаті побудови всіх можливих резольвент отримується порожній диз'юнкт ?, то множина диз'юнктів невиконувана, формули і тотожно хибні, отже, є логічне слідування.
2. Методична розробка з модуля «логіка предикатів»
Приклад 1 . Які з наведених речень є предикатами (для предикатів вказати місність):
a) «х паралельна прямій l (х - довільна пряма на площині);
b) «х є притокою у» (х, у - назви всіх можливих рік);
c) «деякі парні числа діляться на натуральне число у»;
d) «всі непарні числа діляться на 2»;
e) «х або Україна і Росія» (х - назва країни);
h) «для довільного х0 існує п, що ху = 1».
> а ) l-місний предикат, який перетворюється в істинне висловлення на множині всіх прямих, які паралельні до фіксованої прямої l. b ) 2 - місний предикат, який може перетворюватися або в істинне висловлення (наприклад, Десна є притокою Дніпра), або в хибне (Десна є притокою Волги). с ) 1-місний предикат, який перетворюється завжди в істинне висловлення (тотожно істинний), оскільки існують парні числа виду 2у, 4у, 6у, які діляться на y. d ) 0-місний предикат, який є хибним висловленням, е ), f ) Не предикати, оскільки при довільній підстановці замість змінних конкретних значень речення не можуть бути висловленнями. g ) 2-місний предикат, який перетворюється в хибне висловлення при будь-яких дійсних х та у (тотожно хибний). h ) 0-місний предикат, який є істинним висловленням.
Приклад 2. Знайти множину істинності предикатів:
c) Р(х) = «відрізок АВ видно з точки х під прямим кутом»;
d) Р(х) = «точка х рівновіддалена від точокА і В»;
>а ) Множина істинності даного предиката - це множина розв'язків нерівності, яка перетворюється у істинне висловлення лише тоді, коли 1, отже. b ) = [-8; 2]. c ) Множина істинності - множина точок кола, яке побудоване на відрізку АВ як на діаметрі, крім самих точок А та В. d ) Множина істинності - всі точки серединного перпендикуляра для відрізка АВ. е ) Множина істинності - всі точки координатної площини, що знаходяться у другому (утворюється еквіваленція двох хибних висловлень) та четвертому (еквіваленція двох істинних висловлень) квадрантах та на координатних осях.
Приклад 3 . Прочитати висловлення та визначити, які з них істинні, а які хибні, вважаючи, що всі змінні належать множині дійсних чисел:
> а ) Навішування квантора загальності по х приведе до істинного висловлення, якщо одномісний предикат на множині дійсних чисел тотожно істинний. При довільному висловленняістинне, оскільки предикат виконуваний (він перетворюється в істинне висловлення при). Отже, предикат А(х) тотожно істинний, тому висловлення , яке читається так: «Для довільного дійсного х існує дійсне у, що x + y = 3», істинне. b ) Висловлення «Існує дійсне у, що його сума з довільним дійсним х дорівнює 3» очевидно хибне. Дійсно, предикат тотожно хибний, бо для довільного предикат спростовний (перетворюється в хибне висловлення, наприклад, при ). с) Висловлення «Якщо сума двох довільних дійсних чисел дорівнює 3, то 2= 3» істинне, оскільки є імплікацією двох хибних висловлень. d ) Висловлення «Довільне дійсне число х дорівнює самому собі тоді і тільки тоді, коли воно або більше за 1, або менше за 2» є істинним, бо предикат є тотожно істинним як еквіваленція двох предикатівта» (х = х)», які перетворюються в істинне висловлення при довільних xR.
Приклад 4 . Дано предикати А(х) та В(х). Записати реченням висловленняС та В:
a) А(х) = «х-студент», В(х) - «х - склав іспити »,
b) А(х) = «х: - гриб », В(х)= « х - їстівний »,
c) А(х)= «х - наука », В(х) - «х - гуманітарна »,
> а) Висловлення С - частково заперечувальне (О): «Є студенти, які не склали іспити»; D - загальиостверджувальне (A): «Всі студенти склали іспити». b ). Висловлення С - частково заперечувальне (О): «Є неїстівні гриби»; D - загальнозаперечувальне (Е): «Всі гриби неїстівні». с ) Висловлення С - заперечення загальностверджувального: «Не всі науки гуманітарні», а це за змістом рівносильне твердженню «Існують негуманітарні науки», яке символічно записується як D - частково стверджувальне (I): «Існують гуманітарні науки».
Приклад 5 . Записати речення у символічній формі, ввівши доречні у кожному випадку предикати:
b) деякі журналісти були в космосі;
c) якщо число ділиться на 12, то воно ділиться на 2,4 і 6;
d) громадяни Бельгії обов'язково володіють або німецькою, або французькою мовою;
е) деякі студенти здали всі екзамени;
f) кожен студент не здав принаймні один екзамен;
g) кожна людина знає англійську мову, або має друга, який знає англійську мову.
а ) Якщо А(х) = «х - собака» - предикат, визначений на множині всіх тварин, а т - позначення клички Мухтар, то символічний записданого речення: А(т). b ) Визначимо на множині всіх людей предикати А(х) = «х - журналіст» та В(х) = «х - був у космосі». Зі змісту речення зрозуміло, що «дослівний» переклад такий: існують люди, які одночасно є журналістами і були у космосі. Тому можна записати: . Зауважимо, що запис не відповідає даному реченню, оскільки перетворюється в істинне висловлення навіть для тих x, які не є журналістами. Якби предикат В(х) був визначений на множині всіх журналістів, то речення можна було б записати коротко: . с) Задамо на множині натуральних чисел предикати А(х) = «х - ділиться на 12», В(х) = «x - ділиться на 12», C(х) = «х - ділиться на 4», D(x) = «х - ділиться на 6». Оскільки у реченні йдеться про довільне число, то застосуємо квантор загальності: . d) Після введення на множині всіх людей предикатів А(х)= «х-громадянин Бельгії», В(х)= «х - володіє німецькою», С(х)= «х - володіє французькою мовою» дане речення можна символічно записати: . е) Для опису відношень між різними об'єктами (студенти та екзамени) використовуються також і багатомісні предикати. Нехай А(х) =» х - студент», В(у)= «у - екзамен», С (х, у)= «х здав екзамен у». Тоді дане речення можна перефразувати «існують студенти х, що який би не був екзамену, вони його здали» і записати: . f ) Дане речення за змістом протилежне до попереднього, тому використаємо ті самі предикати. Потрібно записати, що «для кожного студента х існує екзамен у і він його не здав»: . g ) Введемо предикати А(х) = «х - знає англійську мову» та В (х, у) - «х друг у». Речення «для кожної людини х або вона знає англійську, або існує друг у, що знає англійську» символічно записується: .
Приклад 6 . Записати мовою логіки предикатів означення:
b) точки локального максимуму функції f(x);
> а) За означенням натуральне число х просте, якщо воно не дорівнює 1 і при довільному розкладі його на добуток натуральних чисел одне з них є саме цс х або 1. Це можна записати: . Після введення предикатівР (х, у)= «х =у» та Q (x, y, z)= «z=xy» цей вираз можна записати: ). b ) Точка з області визначення функції f(х) називається точкою локального максимуму, якщо існуєтакий її - окіл, що для всіх точок х з цього околу виконується f(x) а) Речення має такий самий зміст, як і речення «Існує xR такий, що В(х)» і має запис . b ) Речення має такий зміст: якщо довільні два елементиxR та yRмають властивість В, то вони рівні. Це має символічний запис: . с ) Речення рівносильне кон'юнкції речень з пунктів а ) та b ).
d ) Потрібно підкреслити, що існують елементиxR та yR, які мають одночасно властивість В і не рівні:. е ) Речення має такий зміст: якщо довільні три елементи xR, yR, zRмають властивість В, то принаймні два з них рівні. Це має символічний запис:.
Приклад 1. Визначити, які з наведених виразів є формулами логіки предикатів (для формул вказати тип (відкрита чи замкнута) і назвати вільні та зв'язані входження змінних):
> а ) Не формула, оскільки квантор загальності не навішується на формулу. b ) Формула, у якій головною є операція імплікація, в області дії квантора загальності - елементарна формула Р(х) Формула відкрита, бо містить вільне входження х у висновку імплікації, с) Не формула, оскільки вираз у дужках містить змінну х, яка вже не є вільною.
d ) Відкрита формула, у якій головною операцією є навішування квантора Існування по х, а змінна y є вільною, е ) Відкрита формула, у якій головна операція - імплікація, у посилці змінні х та у зв'язані, а у висновку х вільна. f ) Замкнута формула, оскільки всі змінні знаходяться в області дії кванторів за цими змінними. g ) Не формула, оскільки вираз не є формулою.
h ) Відкрита формула, у якій змінні х та z частково вільні (або частково зв'язані), а змінна y зв'язана. <
Приклад 2 . Якою є формула у кожній інтерпретації:
> а) Уданій інтерпретації формула перетворюється на двомісний предикат , визначений на множині дійсних чисел. Це не тотожність, але існує, наприклад, набір 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) є виконуваним, тому .
Визначити істинне значення кожної з формул при всіх значеннях вільної змінної:
> а) При кожному значенні вільної змінної у операцію навішування квантора загальності по х на скінченній множині замінимо кон'юнкцією:
b ) Аналогічно операцію навішування квантора існування замінимо диз'юнкцією:
Приклад 5. Пока
Особливості контролю знань логіки предикатів дипломная работа. Педагогика.
Реферат по теме Эволюция кооперативных принципов в России
Дипломная работа по теме Занимательное рисование в процессе художественного творчества дошкольников
Лабораторная Работа По Химии 8 Габриелян
Реферат по теме Аудит организации-банкрота
Курсовая работа по теме Юридический анализ состава разбоя
Домбра Одна Из Семи Чудес Казахстана Эссе
Реферат На Тему Цель
Сочинение Рассуждение Честь И Бесчестие Капитанская Дочка
Реферат Про Массаж
Реферат: Code Hero Essay Research Paper The Code
Дипломная работа по теме Формирование интеллектуальной готовности к обучению в школе
Творческая Работа На Тему Территория Кавказа
Сочинение 16 Лет
Доклад: Поражающие факторы ядерного взрыва
Воспитание Лучший Припас К Старости Эссе
Реферат по теме Особенности сценария документального телефильма
Курсовая Работа На Тему Применение Клиентски-Ориентированных Стандартов Обслуживания В Автосервисе
Основные Теории Государства Курсовая Работа
Курсовая работа: Інтерполювання функцій за формулою Лагранжа
Реферат На Тему Фронтальный Погрузчик Категории С
Виды запасов и их назначение - Маркетинг, реклама и торговля реферат
Языковые манипуляции в рекламе с точки зрения потребительского восприятия - Маркетинг, реклама и торговля курсовая работа
Эканоміка-геаграфічныя і гаспадарчыя апісанні, матэрыялы фіскальнага ўліку канца XVIII – першай паловы ХІХ ст - История и исторические личности реферат