Дискретная математика без формул
Шрифт:
Конструктивисты относительно сложного высказывания "Теорема Ферма верна ИЛИтеорема Ферма НЕверна" говорят, что это сложное высказывание не может быть истинным хотя бы потому, что признав его истинность мы окончательно делаем неразрешимым вопрос «Так верна она или нет?!». Более человеколюбивые логики в качестве аргумента приводят сложные высказывания типа: "Человек почти лысый ИЛИ НЕ ВЕРНО, что человек почти лысый". Утверждают, что определить истинность этого сложного высказывания не только невозможно, но и просто бестактно.
Логика высказываний, и алгебра высказываний в частности, как уже ранее говорилось, бурно расцветали на заре вычислительной техники. Одно из важнейших алгебраических преобразований – это минимизация сложных высказываний. То есть было создано множество методик получения из исходного высказывания равносильного, но имеющего наименьшее возможное число логических операций. А в соответствии с таким высказыванием можно построить и максимально простое техническое устройство. И всем заинтересованным лицам будет хорошо и выгодно от результатов, полученных с помощью науки.
Лекция 9. ЛОГИКА ПРЕДИКАТОВ
«Предикат» с английского переводится как сказуемое. Но говорить «логика сказуемых» – себя не уважать. Формально предикатом называется функция, аргументами которой могут быть ПРОИЗВОЛЬНЫЕ ОБ'ЕКТЫиз некоторого множества, а значения функции «истина» или «ложь». Предикат можно рассматривать как расширение понятия высказывания.
Пример. Вместо трех высказываний
«Маша любит кашу»
«Даша любит кашу»
«Саша любит кашу» можно написать один предикат
«Икс любит кашу» и договориться, что вместо неизвестного Икс могут быть либо Маша, либо Даша, либо Саша.
Подстановка вместо Икс имени конкретного ребенка превращает предикат в обычное высказывание.
Для предикатов справедливы, и имеют тот же смысл, ранее рассмотренные логические операции. Например,
" ЕСЛИМаша любит кашу, ТОСаша любит кашу".
Но есть и две новые операции, специфические. Они называются несколько вызывающе – операциями НАВЕШИВАНИЯ КВАНТОРОВ. Эти операции соответствуют фразам «для всех» – квантор общности и «некоторые» – квантор существования. Мы договорились не писать формул, но все-таки следует сказать о значках, которые здесь используются, в силу их экзотичности. Квантор общности произошел от английского Allи обозначается буквой A, перевернутой вверх ногами. Квантор существования произошел от английского Existи обозначается буквой E, которую вверх ногами переворачивать бесполезно, поэтому ее повернули кругом.
Наш предикат, после навешивания каждого из кванторов, также превращается в высказывание, которое может быть истинно или ложно!
" ВСЕлюбят кашу"
" НЕКОТОРЫЕлюбят кашу"
Это, кстати, был (до навешивания кванторов) одноместный предикат (одноместная функция). Но предикаты могут быть не только одноместные. Это просто проиллюстрировать, если представить, что дети могут любить не только кашу… «Икс любит Игрека» – двухместный предикат. " ВСЕлюбят Игрека" – одноместный предикат. " ВСЕлюбят КОЙ-КОГО[некоторого]" – нульместный предикат, то есть высказывание.
Интересно посмотреть, как ведут себя кванторы в присутствии операции отрицания. Возьмем отрицание предиката " ВСЕлюбят кашу": " НЕ ВЕРНО, что ВСЕлюбят кашу". Это равносильно (по закону Де Моргана!) заявлению: " НЕКОТОРЫЕ НЕлюбят кашу. То есть отрицание"задвинули" за квантор, в результате чего квантор сменился на противоположный.
А теперь сделаем одно из самых важных заявлений:
ИЗ ФОРМАЛИЗОВАННЫХ ЯЗЫКОВ МАТЕМАТИКИ ЯЗЫК ПРЕДИКАТОВ – САМЫЙ БЛИЗКИЙ К ЕСТЕСТВЕННОМУ. Поэтому работы по искусственному интеллекту тяготеют к использованию этого языка. В сравнении с естественным, это очень во многих смыслах ограниченный язык. Но лучшего за 100 лет не придумано, если не считать так называемого «синтаксического сахара», когда вместо соответствующей символики используются, например, слова естественного языка. (Вроде того, как мы пытаемся это делать).
В хорошо формализованных системах даже наоборот, дополнительно ограничивают этот язык для удобной реализации на компьютерах. Примером тому язык (логического) программирования
ПРОЛОГ – ПРОграммирование на ЛОГике.
Так вот, язык предикатов наследует пороки языка логики высказываний, которые обуславливают изначальное несоответствие естественного и логического языков.
На языке предикатов можно описать далеко не все, хотя и многое. Но даже в этом ограниченном пространстве подчас приходится применять хитрости и уловки, которые бы больше пристали ремеслу или искусству. Хотя об'яснения, в конце концов, обычно бывают строго формальные.
Вот некоторые «классические примеры».
Если мы желаем сказать на языке предикатов «Все студенты отличники», то рекомендуется конструкция
" ДЛЯ ВСЕХиксов справедливо: ЕСЛИикс студент, ТОикс отличник"
Но если хотим сказать «Некоторые студенты отличники», то это следует записать
" ДЛЯ НЕКОТОРЫХиксов справедливо: икс студент И икс отличник" Конструкция ЕСЛИ…, ТОв данном случае не подходит. И вот почему: стоит затесаться в компанию одному иксу-нестуденту и он сделает этот предикат истинным, даже если там нет ни одного отличника!
И еще высказывание «Собакам и кошкам вход воспрещен».
Конструкция
" ДЛЯ ВСЕХиксов справедливо: ЕСЛИикс – собака Иикс – кошка, ТОиксу вход запрещен"
Ясно что таких иксов, которые бы были одновременно собакой и кошкой не существует! Как, впрочем, и таких игреков. Поэтому
" ДЛЯ ВСЕХиксов справедливо: ЕСЛИикс – собака ИЛИикс – кошка, ТОиксу вход запрещен"