Математическая логика и теория алгоритмов
|
       В исчислении высказываний (ИВ) важным было лишь истинностное значение высказываний, при этом внутреннее строение высказываний на рассматривалось. Выполняя, логические вычисления можно было определить истинностное значение сложных высказываний, в зависимости от истинности или ложности входящих в них простых высказываний. Однако при этом внутренний смысл высказываний не рассматривался. Возможности языка исчисления высказывания оказываются очень бедными для описания и изучения даже простейших заключений науки и практики.
       Рассмотрим простой пример. Из истинных высказываний «5 < 8» и «8 < 10» можно сделать вывод, что «5 < 10». При этом истинность следствия зависит не только от истинности посылок, но и от их внутреннего строения. Изменив вторую посылку на истинное высказывание «8 ≠ 10», уже нельзя сделать вывод, что «5 < 10». Таким образом, даже на таком простом примере видно, что существенную роль при логическом выводе играет внутреннее строение высказываний, а не только их значение истинности.
       Для того чтобы сделать более понятной структуру сложных высказываний, пользуются специальным языком – языком исчисления предикатов (ИП) первого порядка.
       Каждое высказывание представляет собой некоторое суждение о предмете высказывания (субъекте) или взаимосвязи нескольких субъектов. В предыдущем примере высказывания касались отношения порядка между определенными натуральными числами. Предметы (субъекты), о которых делается суждение, могут быть самой различной природы. Множество субъектов, о которых делаются высказывания, называется предметной областью
. Для обозначения субъектов будем использовать предметные переменные.
       Предикат – это языковое выражение, обозначающее какое-то свойство субъекта или отношение между субъектами. В современной логике предикатами называются функции, значениями которых служат высказывания. Предикатом мощности n (n-местным предикатом)
,определенным на предметной области
, называют отображение набора предметных переменных
во множество высказываний.
       Приведем примеры предикатов:
- Q ="5" - нульместный предикат,определенный на множестве натуральных чисел N;
- P(x1)="Натуральное число x1 четное" - одноместный предикат, определенный на множестве натуральных чисел N;
- D(x1,x2)="Натуральное число x1 делится (без остатка) на натуральное число x2" - двуместный предикат, определенный на множестве пар натуральных чисел NxN;
- M(x)="x-мужчина" - одноместный предикат, определенный на множестве всех людей.
       Придавая конкретные значения из предметной области переменным, участвующим в предикатах, можно получить высказывания, которые принимают логическое значение истина или ложь, в зависимости от значения переменных.
       Поскольку предикаты – это отображения со значениями во множестве высказываний, где введены логические операции, то эти операции естественным образом определяются и для предикатов. Пусть P ,
Q – предикаты мощности n ,
определенные на предметной области
.
Тогда логические операции для предикатов вводятся следующим образом:
       
Пример 1. Пусть в множестве натуральных чисел N определены два предиката:
- P(x)="Натуральное число х делится на 2";
- Q(x)="Натуральное число х делится на 3";
       Тогда:
= "Натуральное число х делится на 2 или на 3";
= "Натуральное число х делится на 6";
       Таким образом,
.
       Предикаты P, Q мощности n , определенные на предметной области
называются
логически эквивалентными (равносильными), если
для любого набора предметных переменных
.
Пример 2.Пусть предметная область – это множество слов {a, abbab, bbabb, aa}. На этом множестве заданы два предиката:
- P(x)="Слово x содержит букву b";
- Q(x)="Слово x имеет длину 5";
       На данном множестве эти два предиката равносильны.
Теорема. Справедливы
следующие логические эквивалентности для n -местных
предикатов (1 и 0 – тождественно истинный и тождественно ложный
предикаты соответственно)
Закон двойного отрицания
       
Законы коммутативности
       
Законы ассоциативности
       
Законы дистрибутивности
       
Законы идемпотентности
       
Законы де Моргана
       
Законы нуля и единицы
       
Законы поглощения
       
Закон противоречия
       
Закон исключенного третьего
       
       Теорема не требует доказательства.
       Существуют такие виды высказываний, которые нельзя записать в виде формулы исчисления высказываний. Например:
- Все дети должны смеяться.
- Все люди смертны.
- Никто не забыт,ничто не забыто.
       Корректность таких высказываний определяется не только истинностью соответствующих логических связок, но и пониманием таких слов, как «все», «всякий» и т.д. В логике предикатов наряду с операциями логики высказываний основную роль играют операции, называемые кванторами. Именно использование кванторов делает логику предикатов более богатой и гибкой по сравнению с логикой высказываний. Дадим определения операциям кванторов.
       Пусть P
– предикат мощности n ,
определенный на предметной области
.
Поставим ему в соответствие ( n -1)-местный
предикат
(«для всякого
»).
Этот ( n-1)-местный предикат
переменных
получен из исходного навешиванием квантора всеобщности. Говорят, что переменная xi связана
квантором всеобщности. В естественном языке предикату
соответствуют фразы:
- Для любого х (имеет место) А
- А(х) при произвольном х
- Для всех x (верно) A(x)
- A(x), каково бы ни было x
- Для каждого x (верно) A(x)
- Всегда имеет место A(x)
- Каждый обладает свойством A
- Свойство A присуще всем
- Всё удовлетворяет A
- Любой объект является A
- Всякая вещь обладает свойством A
       Пусть P– предикат мощности n ,
определенный на предметной области
.
Поставим ему в соответствие ( n -1)-местный
предикат
(«существует xi,
что
»).
Этот ( n -1)-местный предикат
переменных
получен из исходного навешиванием квантора существования. Говорят, что переменная xi связана
квантором существования. В естественном языке предикату
соответствуют фразы:
- Для некоторых x (имеет место) A(x)
- Для подходящего x (верно) A(x)
- Существует x, для которого (такой, что) A(x)
- Имеется x, для которого (такой, что) A(x)
- Найдется x, для которого (такой, что) A(x)
- У некоторых вещей есть признак A
- Хотя бы для одного x (верно) A(x)
- Кто-нибудь относится к (есть) A
- По крайней мере, один объект есть A
Пример 3. Пусть имеется предикат
на множестве натуральных чисел N .
Очевидно, что для любых х и у из данной предметной
области предикат D ( x , y )
– истинный, т.е.
.
Если данный предикат определить на множестве действительных
чисел, то
, но
.
Пример 4. Пусть имеется предикат
на множестве целых чисел Z . Тогда можно получить новые одноместные предикаты:
= "Для всякого y, x-y>0". Очевидно, что этот предикат тождественно ложный;
= "Существует x, x-y>0". Этот предикат тождественно истинный.
Пример 5. Записать в логической символике фразу: «Кто ищет, тот всегда найдет».
       Можно перефразировать данное предложение следующим образом – «Каждый, кто ищет, тот всегда найдет». Обозначим предикаты, определенные на предметной области, состоящей из всех людей:
- A(x) = "x ищет";
- В(x) = "x найдет";
       Тогда фраза в логической символике будет выглядеть следующим образом:
.