Тема 12.2.Логические операции над предикатами

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

Определение:Пусть– предикат, определённый на.Отрицаниемпредикатаназывается предикат, обозначаемый, определённый наследующим образом:

Пример 12.4:

= «Натуральное числоделится (без остатка) на натуральное число».

= «Натуральное числоне делится (без остатка) на натуральное число».

,.

,.

Определение:Пустьипредикаты, определённые на. Дизъюнкцией (конъюнкцией, импликацией, эквиваленцией) предикатовиназывается предикат, определённый на, обозначаемый, (,,) и определённый следующим образом:

Таким образом, для предикатов справедливы, и имеют тот же смысл, ранее рассмотренные логические операции. Например, «ЕСЛИ Маша любит кашу, ТО Саша любит кашу».

Определение:Предикатыи, определённые на, называютсяравносильными, еслидля любого наборапредметных переменных на.

Отметим, что если формулы иравносильны в соответствии с этим определением, то формулаявляется тождественно истинной.

Теорема: (Свойства логических операций для предикатов)Множество - местных предикатов, определённых на , образуют булеву алгебру предикатов (т.е. для них справедливы основные законы и тождества булевой алгебры).

Тема 12.3.Кванторы

Но есть и две новые операции, специфические. Они называются несколько вызывающе – операциями навешивания кванторов. Эти операции соответствуют фразам «для всех» – квантор общности и «некоторые» – квантор существования. Следует немного сказать о значках, которые при этом используются, в силу их экзотичности. Квантор общности произошёл от английского «All» и обозначается буквой A, перевернутой вверх ногами (). Квантор существования произошёл от английского Exist и обозначается буквой E, которую вверх ногами переворачивать бесполезно, поэтому её повернули кругом ().

Пусть предикат, определённый на множестве. Высказывание «для всехистинно» обозначаетсяили. Здесь множествовходит в обозначение, но когда оно ясно из контекста пишут просто.

Высказывание «существует такое значение , чтоистинно» обозначаетсяили. Переход от предикатак выражениям видаилиназываетсясвязываниемпеременной, а такженавешиванием кванторана переменную(или на предикат). Переменная, на которую навешен квантор, называетсясвязанной, несвязанная переменная называетсясвободной.

Смысл связанных и свободных переменных в предикатах принципиально различен. Свободная переменная – это обычная переменная, которая может принимать различные значения из множества ; выражение– переменное высказывание, зависящее от значения. Выражениене зависит от переменнойи имеет вполне определённое значение. Это, в частности, означает, что переименование связанной переменной, то есть переход от выраженияк выражениюи наоборот не меняет истинности выражения. Переменные, являющиеся, по существу, связанными, встречаются не только в логике.

Пример 12.5:В выраженияхилипеременнаясвязана: при фиксированной функциипервое выражение равно определённому числу, а второе становится функцией от пределов интегрирования.

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

Пример 12.6:

Пусть предикат «чётное число». Тогда высказываниеистинно на любом множестве чётных чисел и ложно, если множествосодержит хотя бы одно нечётное число. Высказываниеистинно на любом множестве, содержащем хотя бы одно чётное число и ложно на любом множестве нечётных чисел.

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