Высказывательная форма Q2 следует из высказывательной формы Q1, если импликация Q1→Q2 обращается в истинное высказывание при любых наборах значений переменных, входящих в нее. Для операции логического следования принято обозначение .
Пусть даны предикаты Q1(x1, х2, …, хn) и Q2(x1, х2, …, хn), а их множества истинности соответственно T(Q1) и T(Q2). Поскольку , то если , т.е. Q1 истинна, то должна быть истинна Q2, т.е. . Поскольку такое свойство должно быть у любого элемента из T(Q1), то это определение подмножества. Итак, .
Пусть даны два предиката, определенные на одном множестве. Высказывательные формы Q1 и Q2 назовем равносильными, если при любом наборе значений переменных, входящих в них, высказывательные формы принимают одинаковые значения истинности: . Очевидно, что если , a то . Тогда T(Q1) = T(Q2). т.е. множества истинности равносильных предикатов также совпадают.
Пример.
Пусть высказывательные формы заданы на множестве действительных чисел R.
и х2 - 5х + 6 = 0 не являются равносильными.
и Зх + 8 = 0 являются равносильными.
ln (х - 1) + ln (х + 1) = 2 и ln (х2 - 1) = 2 не являются равносильными.
их+3 = (х-1)2 не являются равносильными.
и (4 - 8х)(2 + х) > 0 не являются равносильными.
и (4 - 8х)(2 + х) > 0 являются равносильными.
и не являются равносильными.
В математике нарушение цепочки тождественных преобразований при решении уравнений или неравенств влечет за собой потерю имеющихся или приобретение посторонних корней, т.е. изменение множества истинности исследуемого предиката.
Можно доказать, что отношение равносильности высказывательных форм обладает известными свойствами, а именно, оно рефлективно и симметрично. В том случае, когда одинаковые переменные в каждой из исследуемых форм принимают значения из одного множества, отношение равносильности будет обладать также и свойством транзитивности.
Тогда назовем равносильным преобразованием высказывательной формы Q1 ее замену на равносильную форму Q2. Две равносильные высказывательные формы с одинаковым набором переменных, для которых установлен одинаковый порядок, определяют один и тот же предикат.
Эти свойства предиката используются при решении уравнений и неравенств, которые тоже являются некоторыми высказывательными формами. Так, решение любого уравнения или неравенства предусматривает установление множества его истинности, т.е. множества истинности соответствующего ему предиката. В процессе поиска множества истинности производят замену одного предиката другим, равносильным данному, с целью упрощения имеющихся высказывательных форм.
Пример.
2х - 13 + х2 - (6х2 - 4х + 5 - 6х2) = 0 <=> 6х = 18 <=> х = 3, т. е. множество истинности каждого из этих уравнений состоит из одного числа 3.
Рассмотрим примеры, для которых областью определения является множество действительных чисел: D = Е.
Пример.
Для двух высказывательных форм — уравнений (х - 2)(х - 3) = 0 (Q1) и х - 3 = 0 (Q2) — из х - 3 = 0 следует, что (х - 2)(х - 3) = 0, т.е. верна запись . Однако из (х- 2)(х- 3) = 0 не следует х - 3 = 0. Например, х = 2 является корнем первого уравнения, но не второго.
Пример.
Из уравнения (х - 5)(х - 2) = 0 следует неравенство х > 0, так как корни уравнения — числа 2 и 5 — удовлетворяют также и неравенству.
Пример.
Тождественно-истинное высказывание х2 + 5 > 0 может следовать из любой высказывательной формы Q, имеющей непустое множество истинности , т.е. форма Q→ (х2 + 5 > 0) истинна при любых значениях х.
Отношения следования и равносильности для высказывательных форм, вообще говоря, зависят от того множества, на котором оно рассматривается.
Пример.
Высказывательная форма х > 9 следует из неравенства 8 < х < 12, если D = {2, 0, 4, 5, 7, 9, 10, 11, 13}, но не следует, если D(Q) = N. Действительно, при D = {2, 0, 4, 5, 7, 9, 10, 11}T(Q1) = {9, 10, 11}, a T(Q2) = {9, 10, 11, 13} и выполняется , т.е. форма Q1 → Q2 истинна.
Во втором случае (D(Q) = N), T(Q1) = {8, 9, 10, 11}, a T(Q2) = {9, 10, 11, 12, 13, 14 ...}, но отношение T(Q1) с T(Q2) не выполняется, поскольку .
Правила вывода исчисления предикатов:
Правило заключения (modus ponens) — правило, аналогичное тому, которое введено в исчислении высказываний.
Правило обобщения (-введения, ug-правило) R2:, где G(x) содержит свободные вхождения х, тогда как F не содержит свободных x.
Правило -введения (eg-правило) R3:
Нарушение этих требований может привести к ложным выводам, полученным из истинных высказываний.
Пример.
Даны предикаты Р(х): «натуральное х делится на 15», Q(x): «х делится на 5». Высказывание Р(х)→Q(x) истинно для любых хN. Применим для него правило обобщения. Имеем Р(х) →x Q(x): «Если х делится на 15, то каждое число х делится на 5». Получили ложное утверждение, так как правило -введения применимо к 0-местным, а не к одноместным, как Р(х), предикатам.
Можно доказанные теоремы делать новыми правилами вывода. Так, помимо правил - и -введения можно ввести правила удаления кванторов.
Пусть выведена или дана формула xF(x), например «Существуют студенты, работающие по специальности». Из предметного множества всех студентов выберем такого, о котором действительно известно, что он работает по специальности, и для него введем константу а. Поэтому xF(x) → F(a). Это так называемое правило -удаления, или es-правило (правило выбора).
Правило -удаления снимает квантор общности, осуществляя переход от xF(x) к произвольным формулам F(a), F(y) и др. с учетом того, что эти переменные свободны от х в Fx.
Пример.
Из высказывания «Каждый студент колледжа владеет компьютером» будет следовать, что конкретный студент Максимов тоже владеет компьютером, и произвольно выбранный некоторый студент у владеет компьютером, и всякий студент z тоже владеет компьютером. При этом необходимо помнить, что предметные переменные у и z не должны быть связанными.
Правило -удаления называют правилом универсальной конкретизации, или us-npaвилом.
Примеры.
1. «Все металлы (М) — плавятся (П). Цинк (Ц) — металл. Значит, цинк плавится». Формализация в логике предикатов примет вид: x(M(x) →П(х)) x(Ц(x)→ М(х))├ x(Ц(x)→ М(х)). Снятие квантора общности: (М(х) → П(х)) (Ц(х) → П(х)); тогда на основании транзитивности импликации имеем (Ц(х) →М(х)), (М(х) → П(х)) ├ Ц(х) → П(х).
Вывод x(Ц(x) →П(х)) — обобщение по R2 — верен.
2. «Все студенты (С) проходят практику (П). Некоторые студенты работают в фирме (Ф), значит, некоторые работающие в фирме — проходят практику». Формализация примет вид: x(C(x) → П(х)) х(С(х) Ф(х)) ├ х(Ф(х) П(х)). Уберем кванторы по правилам us и es. Имеем (С (a) → П(а))(С(a)Ф(а)) (С (а) → П(а))С (а)Ф(a) П(а)Ф(а).
Вывод: х(П(х)Ф(х)), т.е. существуют студенты, которые проходят практику в фирме.
Свойства отношения классификации
Рассмотрим непустое множество U. Пусть дана одноместная высказывательная форма Ф с переменной, которая принимает значения из U, проявляя свойство некоторых объектов из него и соответствуя некоторому предикату Q. Множество истинности T(Q) таких объектов является подмножеством Uкак универсального множества.
Пример.
Пусть дано Ux = {5, 6, 7, 8, 9, 10, 11, 12, 13, 14 ...}.
Высказывательной форме «5 < х < 12» соответствует подмножество
T1(Q) = {5, 6, 7, 8, 9, 10, 11} (T(Q1)U1).
Из множества U2 = {1, 3, 5, 7, 9, 11, 13, 15} та же высказывательная форма выделяет множество истинности Т2( Q) = {5, 7, 9, 11},
из U3 = {5, 6, 7, 8, 9, 10, 11} - T3 (Q) = U3,
из U4 = = {12, 13, 14, 15} рассматриваемая высказывательная форма выделяет пустое подмножество истинности T4(Q) = .
Эта высказывательная форма выражает на множестве U единственное свойство, характерное для рассматриваемого предиката на заданном множестве U, т. е. одноместный предикат Q (в данном случае «5 < х < 12») задает свойство данного множества. Тогда множество элементов, обладающих таким свойством Q, будем называть объемом этого свойства.
Если на множестве U задан предикат, выражающий некоторое свойство Р, то множество U можно разбить на два подмножества Т(Р) и UT(P). Такое разбиение на непересекающиеся подмножества мы называем классификацией множества U по основанию Р.
Пример.
Так, в предыдущем примере Т(Р) = {5, 6, 7, 8, 9, 10, 11} множество истинности предиката Р: «5 < х < 12» из множества U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}. UT(P) = {1, 2, 3, 4, 12, 13, 14, 15}.
Пусть на множестве U задано еще одно свойство Q. Тогда все множество U, разбиваясь на четыре подмножества, представляет новую классификацию. С помощью логических операций такую классификацию записывают в виде: .
Замечание. Это аналогично разложению булевой функции по двум переменным (см. подразд. 4.7), с той разницей, что каждое слагаемое должно иметь вид , так как мы разлагаем формулу исчисления предикатов, имеющую вид тавтологии.
Пример.
Так, в предыдущем примере Т(Р) = {5, 6, 7, 8, 9, 10, 11} множество истинности предиката Р: «5 < х < 12» из множества U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}. UT(P) = {1, 2, 3, 4, 12, 13, 14, 15}.
Пусть в нашем примере предикат Q выражает новое свойство — «быть нечетным числом». Тогда эти два свойства одновременно классифицируют множество U на подмножества:
Т(Р)T(Q) = {5, 7, 9, 11}, выполнено Р(х)∙Q(x);
= {6, 8, 10}, выполнено ;
= {1, 3, 13, 15}, выполнено ,
= {2, 4, 12, 14}, выполнено .
Уточним понятие «отношение» с помощью понятия «предикат». Во всех n-местных предикатах (n > 2) устанавливаются некоторые отношения между переменными.
Примеры.
1. Высказывательная форма «х — друг у» выделяет из всего множества людей пары х и у, которые связаны между собой отношением дружбы.
2. Высказывательная форма «х ┴ у» выделяет из множества пар прямых, например на плоскости, те пары, которые связаны отношением перпендикулярности.
3. Высказывательная форма «х2 + у2 + z2 = 16» выделяет из всего множества троек координат те, которые связаны отношением «точка с координатами (х; у; z) лежит на сфере с центром в начале координат и радиусом R = 4».
Отрицания в исчислении предикатов
В разговорной речи для построения отрицания обычно перед сказуемым ставят частицу не.
Пример,
1а «Студент х учится на факультете программирования» имеет отрицание
16 «Студент х не учится на факультете программирования».
? Но всегда ли построенное таким образом отрицание истинно?
Утверждения 2а «Все выпускники колледжей продолжили образование в вузе» и 2б «Все выпускники колледжей не продолжили образование в вузе» не являются отрицанием друг друга, так как они оба ложны.
Пары утверждений За «Некоторые выпускники колледжей продолжили образование в вузе» и 36 «Некоторые выпускники колледжей не продолжили образование в вузе» тоже не служат отрицанием друг друга, так как они оба истинны.
Вторая и третья пары утверждений отличаются от первых тем, что содержат кванторные слова «все» и «некоторые». А при построении отрицаний для предложений, содержащих кванторы, прием введения отрицания не перед сказуемым не срабатывает.
Можно воспользоваться другим, универсальным, приемом построения отрицаний предложений, содержащих кванторы, добавив общее отрицание неверно, что... Тогда во втором примере «Неверно, что все выпускники колледжей продолжили образование в вузе» совпадает по смыслу с утверждением «Некоторые выпускники колледжей не продолжили образование в вузе». Таким образом, отрицанием предложения 2а служит 36, а отрицанием За служит 26.
Символически общее отрицание принято записывать с помощью либо общей черты, либо отрицания самого квантора.
Для отрицания предложения_возможны записи , или , или : ;
для отрицания аналогично: , или ,
или : .
Эти равносильности являются обоснованием метода построения отрицаний высказываний, содержащих кванторы. Для построения отрицания высказываний, содержащих квантор , достаточно заменить его на другой квантор и взять отрицание выражения, на которое этот квантор был «навешен».
Для многоместных кванторов также применяется это правило: осуществляется последовательный перенос отрицания с кванторного слова на предложение, стоящее за квантором, а сам квантор заменяют на двойственный.
Например, для формулы построим отрицание: . В подразд. 4.8 была показана булева двойственность конъюнкции и дизъюнкции. Поэтому для сложных высказываний, состоящих из простых, разделенных операциями конъюнкции и дизъюнкции, отрицание строится следующим образом: нужно все кванторы заменить на , и наоборот; все связки и () заменить на или (), и наоборот; и взять отрицание утверждения.
Контрольные вопросы
1. Что называется предикатом? Приведите примеры предикатов.
2. Какой предикат называется разрешимым, тождественно истинным. Тождественно ложным?
3. Перечислите операции, которые можно осуществить над предикатами. Как применяются предикаты в алгебре? Что такое множество истинности предиката?
4. Из чего состоит алфавит логики предикатов? Что такое квантор?
5. Что называется формулой логики предикатов?
6. Сформулируйте основные правила построения формул.
7. В чем состоит смысл термина «интерпретация» в логике предикатов?
8. Сформулируйте основные правила перехода к новым равносильным формулам.
9. Какая формула называется непротиворечивой, противоречивой, общезначимой?
10. Какая формула называется приведенной? Что такое приведенная форма?
11. Какая формула называется нормальной формой? Сформулируйте алгоритм приведения формулы к нормальной форме.
12. Что называют исчислением предикатов?
13. Сформулируйте аксиомы исчисления предикатов.