Математическая логика и теория алгоритмов

1.8 Понятие предиката

назад | оглавление | вперёд

 

       В исчислении высказываний (ИВ) важным было лишь истинностное значение высказываний, при этом внутреннее строение высказываний на рассматривалось. Выполняя, логические вычисления можно было определить истинностное значение сложных высказываний, в зависимости от истинности или ложности входящих в них простых высказываний. Однако при этом внутренний смысл высказываний не рассматривался. Возможности языка исчисления высказывания оказываются очень бедными для описания и изучения даже простейших заключений науки и практики.
       Рассмотрим простой пример. Из истинных высказываний «5 < 8» и «8 < 10» можно сделать вывод, что «5 < 10». При этом истинность следствия зависит не только от истинности посылок, но и от их внутреннего строения. Изменив вторую посылку на истинное высказывание «8 ≠ 10», уже нельзя сделать вывод, что «5 < 10». Таким образом, даже на таком простом примере видно, что существенную роль при логическом выводе играет внутреннее строение высказываний, а не только их значение истинности.

       Для того чтобы сделать более понятной структуру сложных высказываний, пользуются специальным языком – языком исчисления предикатов (ИП) первого порядка.
       Каждое высказывание представляет собой некоторое суждение о предмете высказывания (субъекте) или взаимосвязи нескольких субъектов. В предыдущем примере высказывания касались отношения порядка между определенными натуральными числами. Предметы (субъекты), о которых делается суждение, могут быть самой различной природы. Множество субъектов, о которых делаются высказывания, называется предметной областью . Для обозначения субъектов будем использовать предметные переменные.

       Предикат – это языковое выражение, обозначающее какое-то свойство субъекта или отношение между субъектами. В современной логике предикатами называются функции, значениями которых служат высказывания. Предикатом мощности n (n-местным предикатом) ,определенным на предметной области , называют отображение набора предметных переменных во множество высказываний.
       Приведем примеры предикатов:

       Придавая конкретные значения из предметной области переменным, участвующим в предикатах, можно получить высказывания, которые принимают логическое значение истина или ложь, в зависимости от значения переменных.
       Поскольку предикаты – это отображения со значениями во множестве высказываний, где введены логические операции, то эти операции естественным образом определяются и для предикатов. Пусть P , Q – предикаты мощности n , определенные на предметной области . Тогда логические операции для предикатов вводятся следующим образом:
       

Пример 1. Пусть в множестве натуральных чисел N определены два предиката:        Тогда:        Таким образом, .

       Предикаты P, Q мощности n , определенные на предметной области называются логически эквивалентными (равносильными), если для любого набора предметных переменных .

Пример 2.Пусть предметная область – это множество слов {a, abbab, bbabb, aa}. На этом множестве заданы два предиката:

       На данном множестве эти два предиката равносильны.

Теорема. Справедливы следующие логические эквивалентности для n -местных предикатов (1 и 0 – тождественно истинный и тождественно ложный предикаты соответственно)
  1. Закон двойного отрицания
           

  2. Законы коммутативности
           

  3. Законы ассоциативности
           

  4. Законы дистрибутивности
           

  5. Законы идемпотентности
           

  6. Законы де Моргана
           

  7. Законы нуля и единицы
           

  8. Законы поглощения
           

  9. Закон противоречия
           

  10. Закон исключенного третьего
           

       Теорема не требует доказательства.

       Существуют такие виды высказываний, которые нельзя записать в виде формулы исчисления высказываний. Например:

       Корректность таких высказываний определяется не только истинностью соответствующих логических связок, но и пониманием таких слов, как «все», «всякий» и т.д. В логике предикатов наряду с операциями логики высказываний основную роль играют операции, называемые кванторами. Именно использование кванторов делает логику предикатов более богатой и гибкой по сравнению с логикой высказываний. Дадим определения операциям кванторов.

       Пусть P – предикат мощности n , определенный на предметной области . Поставим ему в соответствие ( n -1)-местный предикат («для всякого »). Этот ( n-1)-местный предикат переменных получен из исходного навешиванием квантора всеобщности. Говорят, что переменная xi связана квантором всеобщности. В естественном языке предикату соответствуют фразы:


       Пусть P– предикат мощности n , определенный на предметной области . Поставим ему в соответствие ( n -1)-местный предикат («существует xi, что »). Этот ( n -1)-местный предикат переменных получен из исходного навешиванием квантора существования. Говорят, что переменная xi связана квантором существования. В естественном языке предикату соответствуют фразы: Пример 3. Пусть имеется предикат на множестве натуральных чисел N . Очевидно, что для любых х и у из данной предметной области предикат D ( x , y ) – истинный, т.е. . Если данный предикат определить на множестве действительных чисел, то , но .

Пример 4. Пусть имеется предикат на множестве целых чисел Z . Тогда можно получить новые одноместные предикаты: Пример 5. Записать в логической символике фразу: «Кто ищет, тот всегда найдет».
       Можно перефразировать данное предложение следующим образом – «Каждый, кто ищет, тот всегда найдет». Обозначим предикаты, определенные на предметной области, состоящей из всех людей:        Тогда фраза в логической символике будет выглядеть следующим образом: .
назад | оглавление | вперёд