Логические операции над предикатами. Предикаты и кванторы Доказательство теорем методом от противного

Отношение порядка. Упорядоченные множества

Определение. Отношение R на множестве Х называется отношением порядка, если оно транзитивно и асимметрично или антисимметрично.

Определение. Отношение R на множестве Х называется отношением строгого порядка, если оно транзитивно и асимметрично.

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

Определение. Отношение R на множестве Х называется отношением нестрогого порядка, если оно транзитивно и антисимметрично.

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

Определение. Множество Х называют упорядоченным, если на нем задано отношение порядка.

Пример . На множестве Х = {1; 2; 3; 4; 5} заданы два отношения: «х £ у » и «х – делитель у ».

Оба эти отношения обладают свойствами рефлексивности, антисимметричности и транзитивности (постройте графы и проверьте свойства самостоятельно), т.е. являются отношением нестрогого порядка. Но первое отношение обладает свойством связности, а второе – нет.

Определение. Отношение порядка R на множестве Х называется отношением линейного порядка, если оно обладает свойством связности.

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

Контрольные вопросы

1. Дайте определение бинарного отношения на множестве Х .

2. Как записать утверждение о том, что элементы х и у находятся в отношении R ?

3. Перечислите способы задания отношений.

4. Сформулируйте свойства, которыми могут обладать отношения. Как данные свойства отражаются на графе?

5. Какими свойствами должно обладать отношение, чтобы оно являлось отношением эквивалентности?

6. Как отношение эквивалентности связано с разбиением множества на классы?

7. Какими свойствами должно обладать отношение, чтобы оно являлось отношением порядка?

Глава 5. Предикаты и теоремы

В математике часто встречаются предложения, содержащие одну или несколько переменных, например: «х + 2 = 7», «город стоит на Волге». Эти предложения не являются высказываниями, т.к. о них нельзя сказать, истинны они или ложны. Однако при подстановке конкретных значений переменной х они обращаются в истинные или ложные высказывания. Так, в первом примере при х = 5 получаем истинное высказывание, а при х = 3 – ложное высказывание.

Определение . Предложение с переменными, которое при конкретных значениях переменных обращается в высказывание, называется высказывательной формой или предикатом.

По числу входящих в предикат переменных различают одноместные, двухместные и т.д. предикаты и обозначают А (х ), В (х;у )…

Пример : А (х ): «х делится на 2» – одноместный предикат, В (х ; у ): «прямая х перпендикулярна прямой у » – двухместный предикат.

Следует иметь в виду, что в предикате переменные могут содержаться неявно: «число делится на 2», «студент получил отличную оценку на экзамене по математике».

Задание предиката, как правило, предполагает и задание множества, из которого выбираются значения переменных, входящих в предикат.

Определение . Множеством (областью) определения предиката называется множество Х , состоящее из всех значений переменных, при подстановке которых в предикат последний обращается в высказывание.

Так, предикат «х > 2» можно рассматривать на множестве натуральных чисел или действительных чисел.

Каждый предикат А (х ), х Î Х определяет множество Т Ì Х , состоящее из элементов, при подстановке которых в предикат А (х ) вместо х получается истинное высказывание.

Определение . Множество, состоящее из всех тех значений, при подстановке которых в предикат получается истинное высказывание, называется множеством истинности предиката (обозначается Т ).

Пример . Рассмотрим предикат А (х ): «х < 5», заданный на множестве натуральных чисел. Т = {1; 2; 3; 4}.

Предикаты, как и высказывания, бывают элементарными и составными. Составные предикаты образуются из элементарных при помощи логических связок.

Пусть Т А А (х ), Т В – область истинности предиката В (х ).

Определение . Конъюнкцией предикатов А (х ) и В (х ) называется предикат А (х ) Ù В (х х Î Х , для которых оба предиката истинны.

Покажем, что Т А Ù В = Т А ÇТ В .

Доказательство . 1) Пусть а Î Т А Ù В Þ А (а ) Ù В (а ) – истинное высказывание. По определению конъюнкции имеем: А (а ) – истинно, В (а ) – истинно Þ а Î Т А Ù а Î Т В Þ а Î Т А Ç Т В Þ Т А Ù В Ì Т А Ç Т В.

2) Пусть b Î Т А Ç Т В Þ b Î Т А Ù b Î Т В Þ А (b ) – истинно, В (b ) – истинно Þ по определению конъюнкции А (b ) Ù В (b ) – истинное высказывание Þ b Î Т А Ù В Þ Т А Ç Т В Ì Т А Ù В .

Т.к. Т А Ù В Ì Т А Ç Т В и Т А Ç Т В Ì Т А Ù В , то по свойству равенства множеств Т А Ù В = Т А ÇТ В , что и требовалось доказать.

Заметим, что полученное правило справедливо и для предикатов, содержащих более одной переменной.

Пример . Рассмотрим предикаты А (х ): «х < 10», В (х ): «х А (х ) Ù В (х ): «х < 10 и делится на 3».

Т А = {1; 2; 3; 4; 5; 6; 7; 8; 9; 10}, Т В = {3; 6; 9; 12; 15; …}, тогда Т А Ù В = {3; 6; 9}.

Определение . Дизъюнкцией предикатов А (х ) и В (х ) называется предикат А (х ) Ú В (х ), который истинен для тех и только тех значениях х Î Х , для которых истинен хотя бы один из предикатов.

Можно доказать (самостоятельно), что Т А Ú В = Т А ÈТ В .

Пример . Рассмотрим предикаты А (х ): «х делится на 2 », В (х ): «х делится на 3», заданные на множестве натуральных чисел. Найдем область истинности предиката А (х ) Ú В (х ): «х делится на 2 или на 3».

Т А = {2; 4; 6; 8; 10;…}, Т В = {3; 6; 9; 12; 15; …}, Т А Ú В = {2; 3; 4; 6; 8; 9; …}.

Определение . Отрицанием предиката А (х ) называется предикат . Он истинен для тех и только тех значениях х Î Х , для которых предикат А (х ) ложен и наоборот.

Заметим, что = .

Определение . Импликацией предикатов А (х ) и В (х ) называется предикат А (х ) Þ В (х ) (читают: «Если А (х ), то В (х )»). Он обращается в ложное высказывание при тех значениях х Î Х , для которых предикат А (х ) истинен, а предикат В (х ) ложен.

Из определения имеем, что предикат А (х ) Þ В (х ) ложен на множестве Т А Ç , а следовательно истинен на дополнении к этому множеству. Воспользовавшись законами операций над множествами, имеем: .

Контрольные вопросы

1. Что называется высказывательной формой или предикатом?

2. Какие различают предикаты по числу входящих в них переменных? Приведите примеры.

3. Какое множество называют областью определения предиката?

4. Какое множество называют множеством истинности предиката?

5. Что называют конъюнкцией предикатов? Докажите равенство, связывающее область истинности конъюнкции предикатов с областями истинности этих предикатов.

6. Дайте определения дизъюнкции, отрицания, импликации предикатов. Запишите равенства, связывающие области истинности конъюнкции предикатов с областями истинности этих предикатов.

1 . Операция отрицания.

Отрицанием предиката Р(х), заданного на множестве Х, называется предикат , заданный на том же множестве и истинный при тех и только тех значениях х Х, при которых предикат Р(х ) принимает значение лжи.

2 . Операция конъюнкции.

Конъюнкцией предикатов Р(х) и Q(x) , заданных на множестве Х , называется предикат Р(х) Q(x ), заданный на том же множестве и обращающийся в истинное высказывание при тех и только тех значениях х Х, при которых оба предиката принимают значения истины.

Если обозначить ТР Р(х) , Т Q - множество истинности предиката Q(х) , а множество истинности их конъюнкции TPÙQ, то, по всей видимости, TPÙQ = TP Ç TQ.

Докажем это равенство.

1. Пусть а Х и известно, что а Î TPÙQ . По определению множества истинности это означает, что предикат Р(х) Q(x ) обращается в истинное высказывание при х = а , т.е. высказывание Р(а) Q(а ) истинно. Так как данное высказывание конъюнкция, то по определению конъюнкции получаем, что каждое из высказываний Р(а) и Q(а) также истинно. Это означает, что а ТР и а ТQ . Таким образом, мы показали, что TPÙQ Ì ТР Ç ТQ .

2. Докажем обратное утверждение. Пусть а - произвольный элемент множества Х и известно, что а Î TP Ç TQ . По определению пересечения множеств это означает, что а ТР и а ТQ , откуда получаем, что Р(а) и Q(а) - истинные высказывания, поэтому конъюнкция высказываний Р(а) Q(а ) также будет истинна. А это означает, что элемент а принадлежит множеству истинности предиката Р(х) Q(x ), т.е. а Î TPÙQ .

Из 1 и 2 в силу определения равных множеств вытекает справедливость равенства TPÙQ = ТР Ç ТQ , что и требовалось доказать.

Наглядно это можно изобразить следующим образом.

3. Операция дизъюнкции.

Дизъюнкцией предикатов Р(х) и Q(x ) называется предикат Р(х) Q(x Х и обращающийся в истинное высказывание при тех и только тех значениях х Х, при которых принимает значение истины хотя бы один из предикатов Р(х ) или Q(x).

Аналогично доказывается, что TPÚQ = TP È TQ.

4 . Операция импликации.

Импликацией предикатов Р(х) и Q(x) , заданных на множестве Х , называется предикат Р(х) Q(x ), определенный на том же множестве Х и обращающийся в ложное высказывание при тех и только тех значениях х Х, при которых Р(х) принимает значение истины, а Q(x) - значение лжи.

5 .Операция эквиваленции.

Эквиваленцией предикатов Р(х) и Q(x) , заданных на множестве Х , называется предикат Р(х) Q(x ), определенный на том же множестве Х и принимающий значение истины при тех и только тех значениях х Х, при которых значения каждого из предикатов либо истинны либо ложны. Множество истинности в таком случае выглядит так:

TPÛQ = .

Пример . На множестве М={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20} заданы предикаты: А(х) - «число х не делится на 5 », В(х) - «х - число четное», С(х) - «х - число простое», D(x) - «число х кратно 3 ». Найти множество истинности следующих предикатов:

a) А(х) В(х); b) A(x) ; c) C(x)A(x); d) B(x)D(x) и изобразить их при помощи диаграмм Эйлера-Венна.

Решение: a) Найдем множество истинности предикатов.

А(х): T = {1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19};

В(х): Т = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}.

Множество истинности конъюнкции А(х) В(х) есть истинности T и Т .

Предикатом называется любое выражение содерж переменную при подстановке значений которых оно обращается в высказывание которое принимает значение 0 или 1.

Множество различных наборов значений входящих в предикаты называют областью определения предиката.

Предикат принимает значение:

1) Тождеств истинно – это предикат который принимает значение 1 при любых наборах значений входящих в него переменных.

2) Тожд ложн – это предикат который принимает значение 0 при любых наборах значений входящих в него переменных.

3) Выполнимый – это предикат который принимает значение 1 хотя бы на одном наборе значений входящих в него переменных.end

Множество значений на которых предикат равен 1 назыв областью определения истинности предиката.

Предикаты называютcя равносильными если они принимают одинаковое значение при соответствующих значениях переменных.

Над предикатами можно выполнять все действия что и над функциями. (отриц, \/.,/\, =>, <=>)

Конъюнкция двух предикатов тождественно истинна тогда и только тогда, когда оба данных предиката тождественно истинны.(остальные операции аналогично)

Квантор существования можно применять к многомерным предикатам. Однократное применение квантора к одной из n переменных а- мерного предиката порождает (n-1)- мерный предикат.

Пусть А(х,у)=(х+у > 1) двухместный предикат определённый на множестве R.

Тогда из него связыванием переменных х и у можно получить восемь высказываний:

1 "х "у(х + у > 2) х и у их сумма больше двух”.

2 "у "х(х + у > 2) – “Для всяких действительных чисел у и х их сумма больше двух”.

3 $х $у(х + у > 2) х и у , сумма которых больше двух”.

4 $у $х(х + у > 2) – “Существуют действительные числа у и х , сумма которых больше двух”.

5 "х $у(х + у > 2) х существует действительное число у, что их сумма больше двух”.

6 "у $х(х + у > 2) – “Для всякого действительного числа у существует

действительное число х , что их сумма больше двух”.

7 $х "у (х+у>2) х , что для всякого действительного числа у их сумма больше двух ”.

8 х (х+у>2) – “Существует действительное число у , что для всякого

действительного числа х их сумма больше двух ”.

Законы де Моргана для кванторов

2) ;

Законы пронесения кванторов через конъюнкцию

1) x(A (x )·B (x ))=(xA (x ))·(xB (x ));

2)x (A (x )·P )=(xA (x ))·P .

Законы пронесения кванторов через дизъюнкцию

1) = ;

2) = ;

Законы пронесения кванторов через импликацию

1) = ;

2) = ;

3) = ;

4) = ;

Законы коммутативности для кванторов

Машина Тьюринга

Машина Тьюринга есть математическая (вообразимая) машина, а не машина физическая. Машина Тьюринга состоит из ленты, управляющего устройства и считывающей головки.

Лента разбита на ячейки. Во всякой ячейке в каждый момент времени находится в точности один символ из внешнего алфавита А={а 0 ,а 1 ,…а n -1 } , n 2. Некоторый символ алфавита А называется пустым, любая ячейка, содержащая в данный момент пустой символ, называется пустой ячейкой.

Управляющее устройство в каждый момент времени находит в некотором состоянии q i , принадлежащее множеству Q{q 0 ,q 1 ,…,q r -1 }, r 1 . Множество Q называется внутренним алфавитом. Работа машины Тьюринга определяется программой. Программа состоит из команд. Каждая команда представляет собой выражение одного из следующего вида:

1) q i a j →q k a e ;

2) q i a j →q k a e R;

3) q i a j →q k a e L.

Команда 1 заключается в том, что содержимое a j обозреваемой на ленте ячейки стирается, а на его место дописывается символ a e (который может совпадать с a j ), машина переходит в новое состояние q k (оно может совпадать с предыдущим состоянием q i ). Команда 2 работает аналогично команде 1, и дополнительно сдвигает считывающую головку в соседнюю справа ячейку.Команда 3 работает аналогично команде 1, и дополнительно сдвигает считывающую головку в соседнюю слева ячейку.

Если считывающая головка находится в крайней справа (слева) ячейки ленты и происходит ее сдвиг вправо (влево), то к ленте пристраивается новая ячейка в пустом состоянии.

Машинным словом или конфигурацией называется слово вида

где А, q k Q.

Если машина Тьюринга выходит на заключительное состояние, то она называется остановившейся.

Функция называется вычислимой по Тьюрингу, если существует ма-шина Тьюринга, вычисляющая её.

Композиция машины Тьюринга

Поскольку машина Тьюринга-алгоритм, то операции композиции применимы и к машинам Тьюринга. Рассмотрим основные из них, а именно: произведение, возве-дение в степень, итерацию.

Тезис Тьюринга. Для нахождения значений функции, заданной в некотором алфавите, тогда и только тогда существует какой нибудь алгоритм, когда функция явл вычислимой по Тьюрингу то есть когда она может вычисляться на подходящей машине Тьюрингаю.
Пусть заданы машины Тьюринга Т1 и Т2, имеющие какой-то общий внешний алфавит А = {а0, а1,..., аm} и внутренние алфавиты Q1 = {q0, q1,..., qn} и cоответственно Q2 = {q0,q1,…,qt}. Композитом, или произведением, машины Т1 на машину T2 будем называть машину Т с тем же внешним алфавитом А= {а0, а1,..., аm}, внутренним алфавитом Q = {q0, q1,...,qn, qn+1, ...,qn+t} и программой, получающейся следующим образом. Во всех командах Т1 содержащих заключитель-ный символ q0, заменяем его на символ qn+1. Все остальные символы в командах T1 оставляем неизменными. В командах Т2, напротив, символ q0 оставляем неизменным, но зато каждый из остальных символов заменяем символом qn+j. Совокупность всех команд Т1 и Т2, измененных указанным способом, и будет программой композита или произведения машин T1 и T2.
Произведение машины T1 на машину Т2 обозначается через Т = T1 T2, или
Т = T1 * Т2.
Таким образом, машина Т есть произведение машин Т1 и T2, если последовательная работа этих двух машин эквивалентна работе одной машины Т

Классы рекурсивных функций

В дальнейшем под множеством натуральных чисел N будем понимать множество N = {0,1,2,…,k,…}

Пусть y = f(x 1 , x 2 ,…, x n) – функция от n переменных. Обозначим D(y) – область определения функции y = f(x 1 , x 2 ,…, x n), E(y) – область значений функции y = f(x 1 , x 2 ,…, x n).

Функция y = f(x 1 , x 2 ,…, x n) называется числовой функцией, если:

1) D(y)=N ×∙ N ∙× …×∙ N = ;

2) E(y) N

Функция y = f(x 1 , x 2 ,…, x n) называется частично числовой функцией, если:

1) D(y) N ×∙ N∙×…×∙N = ;

2) E(y) N.

Следующие числовые функции мы будем называть простейшими:

1) O(x) = 0 – нуль-функция

2) (x 1 , x 2 ,…, x n) = x m , 1 ≤ m ≤ n – функция повторяющая значение своих аргументов;

3) S(x) = x+1 – функция следования.

Определим следующие три операции: суперпозиции, примитивной рекурсии и минимизации.

Операция суперпозиции

Будем говорить, что n – местная функция φ получается из m – местной функции ψ и n – местныхфункций f 1 ,f 2 ,…,f m с помощью операции суперпозиции, если для всех x 1 ,x 2 ,…,x n справедливо равенство:

φ (x 1 ,x 2 ,…,x n) = ψ(f 1 (x 1 , x 2 ,…, x n),…, f m (x 1 , x 2 ,…, x n))

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

Определение 1

Предикат - утверждение, которое содержит переменные, принимающие значение $1$ или $0$ (истинно или ложно) в зависимости от значений переменных.

Пример 1

Например, выражение $x=x^5$ является предикатом, т.к. оно является истинным при $x=0$ или $x=1$ и ложным при всех остальных значениях $x$.

Определение 2

Множество, на котором предикат принимает только истинные значения, называется множеством истинности предиката $I_p$.

Предикат называется тождественно-истинным , если на любом наборе аргументов он принимает истинное значение:

$P (x_1, \dots, x_n)=1$

Предикат называется тождественно-ложным , если на любом наборе аргументов он принимает ложное значение:

$P (x_1, \dots, x_0)=0$

Предикат называется выполнимым , если хотя бы на одном наборе аргументов он принимает истинное значение.

Т.к. предикаты могут принимать только два значения (истинно/ложно или $0/1$), то к ним можно применять все операции алгебры логики: отрицание, конъюнкция, дизъюнкция и т.д.

Примеры предикатов

Пусть предикат $R(x, y)$: $«x = y»$ обозначает отношение равенства, где $x$ и $y$ принадлежат множеству целых чисел. В этом случае предикат R будет принимать истинное значение для всех равных $x$ и $y$.

Другой пример предиката -- РАБОТАЕТ($x, y, z$) для отношения «$x$ работает в городе y в компании $z$».

Еще один пример предиката -- НРАВИТСЯ($x, y$) для «x нравится y» для $x$ и $y$, которые принадлежат $M$ -- множеству всех людей.

Таким образом, предикатом является все то, что утверждается или отрицается о субъекте суждения.

Операции над предикатами

Рассмотрим применение операций алгебры логики к предикатам.

Логические операции:

Определение 3

Конъюнкция двух предикатов $A(x)$ и $B(x)$ -- предикат, который принимает истинное значение при тех и только тех значениях $x$ из $T$, при которых каждый из предикатов принимает истинное значение, а ложное значение -- во всех остальных случаях. Множество истинности $T$ предиката -- пересечение множеств истинности предикатов $A(x)$ и $B(x)$. Например: предикат $A(x)$: «$x$ -- чётное число», предикат $B(x)$: «$x$ делится на $5$». Таким образом, предикатом будет выражение «$x$ -- чётное число и делится на $5$» или «$x$ делится на $10$».

Определение 4

Дизъюнкция двух предикатов $A(x)$ и $B(x)$ -- предикат, который принимает ложное значение при тех и только тех значениях $x$ из $T$, при которых каждый из предикатов принимает ложное значение и принимает истинное значение во всех остальных случаях. Множество истинности предиката -- объединение областей истинности предикатов $A(x)$ и $B(x)$.

Определение 5

Отрицание предиката $A(x)$ -- предикат, который принимает истинное значение при всех значениях $x$ из $T$, при которых предикат $A(x)$ принимает ложное значение и наоборот. Множество истинности предиката $A(x)$ -- дополнение $T"$ к множеству $T$ в множестве $x$.

Определение 6

Импликация предикатов $A(x)$ и $B(x)$ -- предикат, который является ложным при тех и только тех значениях $x$ из $T$, при которых $A(x)$ -- истинно, а $B(x)$ -- ложно, и принимает истинное значение во всех остальных случаях. Читается: «Если $A(x)$, то $B(x)$».

Пример 2

Пусть $A(x)$: «Натуральное число $x$ делится на $3$»;

$B(x)$: «Натуральное число $x$ делится на $4$».

Составим предикат: «Если натуральное число $x$ делится на $3$, то оно делится и на $4$».

Множество истинности предиката -- объединение множества истинности предиката $B(x)$ и дополнения к множеству истинности предиката $A(x)$.

Над предикатами помимо логических операций можно выполнять квантовые операции: применение квантора всеобщности, квантора существования и т.д.

Кванторы

Определение 7

Кванторы -- логические операторы, применение которых к предикатам превращает их в ложные или истинные высказывания.

Определение 8

Квантор -- логические операции, которые ограничивают область истинности предиката и создают высказывание.

Чаще всего используют кванторы:

квантор всеобщности (обозначается символом $\forall x$) -- выражение «для всех $x$» («для любого $x$»);

квантор существования (обозначается символом $\exists x$) -- выражение «существует $x$ такое, что... »;

квантор единственности и существования (обозначается $\exists !x$) -- выражение «существует точно одно такое $x$, что... ».

В математической логике существует понятие связывание или квантификация , которые обозначают приписывание квантора к формуле.

Примеры применения кванторов

Пусть -- предикат «$x$ кратно $7$».

С помощью квантора всеобщности можно записать следующие ложные высказывания:

любое натуральное число делится на $7$;

каждое натуральное число делится на $7$;

все натуральные числа делятся на $7$;

который будет иметь вид:

Рисунок 1.

Для записи истинных высказываний используем квантор существования :

существуют натуральные числа, которые делятся на $7$;

найдётся натуральное число, которое делится на $7$;

хотя бы одно натуральное число делится на $7$.

Запись будет иметь вид:

Рисунок 2.

Пусть на множестве $x$ простых чисел задан предикат: «Простое число является нечетным». Поставив перед предикатом слово «любое», получим ложное высказывание: «Любое простое число является нечетным» (например, $2$ является простым четным числом).

Поставим перед предикатом слово «существует» и получим истинное высказывание: «Существует простое число, которое является нечетным» (например, $x=3$).

Таким образом, предикат можно превратить в высказывание, если поставить перед предикатом квантор.

Операции над кванторами

Для построения отрицания высказываний, которые содержат кванторы, применяется правило отрицания кванторов :

Рисунок 3.

Рассмотрим предложения и выделим среди них предикаты, указав область истинности каждого из них.

Предикаты так же, как высказывания, могут принимать два значения: “истина” (1) и “ложь” (0), поэтому к ним применимы все операции логики высказываний, в результате чего из элементарных предикатов формируются сложные предикаты (как и в логике высказываний, где из элементарных высказываний формировались сложные, составные). Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов. Эти операции в логике предикатов сохраняют тот же смысл, который был им присвоен в логике высказываний.

Пусть на некотором множестве M определены два предиката P(x) и Q(x).

Определение 1.

Конъюнкцией двух предикатов P(x) и Q(x) называется новый (сложный) предикат , который принимает значение “истина” при тех и только тех значениях , при которых каждый из предикатов принимает значение “истина”, и принимает значение “ложь” во всех остальных случаях.

Очевидно, что областью истинности предиката является общая часть области истинности предикатов P(x) и Q(x), т.е. пересечение .

Так, например, для предикатов P(x): “x – четное число” и Q(x): “x кратно 3” конъюнкцией является предикат “x – четное число и x кратно трем”, т.е. предикат “x делится на 6”.

Определение 2.

Дизъюнкцией двух предикатов P(x) и Q(x) называется новый предикат , который принимает значение “ложь” при тех и только тех значениях , при которых каждый из предикатов принимает значение “ложь”, и принимает значение “истина” во всех остальных случаях.

Ясно, что областью истинности предиката является объединение области истинности предикатов P(x) и Q(x), т.е. .

Определение 3.

Отрицанием предиката P(x) называется новый предикат или , который принимает значение “истина” при всех значениях , при которых предикат P(x) принимает значение “ложь”, и принимает значение “ложь” при тех значениях , при которых предикат P(x) принимает значение “истина”.

Очевидно, что , т.е. множество истинности предиката является дополнением к множеству I P .

Определение 4.

Импликацией предикатов P(x) и Q(x) называется новый предикат , который является ложным при тех и только тех значениях , при которых одновременно P(x) принимает значение “истина”, а Q(x) – значение “ложь”, и принимает значение “истина” во всех остальных случаях.

Поскольку при каждом фиксированном справедлива равносильность , то .

Определение 5.

Эквиваленцией предикатов P(x) и Q(x) называется новый предикат , который обращается в “истину” при всех тех и только тех , при которых P(x) и Q(x) обращаются оба в истинные или оба в ложные высказывания.

Для его множества истинности имеем:

Кванторные операции.

Рассмотрим операции, преобразующие предикаты в высказывания.

Пусть имеется предикат Р(х) определенный на множестве М. Если “а” – некоторый элемент из множества М, то подстановка его вместо х в предикат Р(х) превращает этот предикат в высказывание Р(а). Такое высказывание называют единичным . Например, r(x): “х – четное число” – предикат, а r (6)- истинное высказывание, r (3) – ложное высказывание.

Это же относится и к n – местным предикатам: если вместо всех предметных переменных х i , i= подставить их значения, то получим высказывание.

Наряду с образованием из предикатов высказываний в результате таких подстановок в логике предикатов рассматриваются еще две операции, которые превращают одноместный предикат в высказывание. Эти операции называются операциями квантификации (или просто квантификацией, или связыванием кванторами, или навешиванием кванторов). При этом рассматриваются, соответственно, два типа так называемых кванторов.

1.1 Квантор всеобщности.

Пусть Р(х) – предикат , определенный на множестве М. Под выражением понимают высказывание , истинное, когда Р(х) истинно для каждого элемента х из множества М, и ложное в противном случае. Это высказывание уже не зависит от х. Соответствующее ему словесное выражение звучит так: “Для всякого х Р(х) истинно ”.

Символ называют квантором всеобщности (общности). Переменную х в предикате Р(х) называют свободной (ей можно придавать различные значения из М), в высказывании же х называют связанной квантором всеобщности.

1.2 Квантор существования.

Пусть P(x) -предикат определенный на множестве М. Под выражением понимают высказывание , которое является истинным, если существует элемент , для которого P(x) истинно, и ложным – в противном случае. Это высказывание уже не зависит от x. Соответствующее ему словесное выражение звучит так: “Существует x, при котором P(x) истинно.” Символ называют квантором существования. В высказывании переменная x связана этим квантором (на нее навешен квантор).

Кванторные операции применяются и к многоместным предикатам. Пусть, например, на множестве М задан двухместный предикат P(x,y). Применение кванторной операции к предикату P(x,y) по переменной x ставит в соответствие двухместному предикату P(x,y) одноместный предикат (или одноместный предикат ), зависящий от переменной y и не зависящий от переменной x. К ним можно применить кванторные операции по переменной y, которые приведут уже к высказываниям следующих видов:

Рассмотрим предикат P(x) определенный на множестве M={a 1 ,…,a n }, содержащем конечное число элементов. Если предикат P(x) является тождественно - истинным, то истинными будут высказывания P(a 1),P(a 2),…,P(a n). При этом истинными будут высказывания и конъюнкция .

Если же хотя бы для одного элемента P(a k)окажется ложным, то ложными будут высказывание и конъюнкция . Следовательно, справедлива равносильность .

Численные кванторы.

В математике часто встречаются выражения вида “по меньшей мере n” (“хотя бы n”), “не более чем n”, “n и только n” (“ровно n”), где n – натуральное число.

Эти выражения, называемые численными кванторами , имеют чисто логический смысл; они могут быть заменены равнозначными выражениями, не содержащими числительных и состоящими только из логических терминов и знака или ~, означающего тождество (совпадение) объектов.

Пусть n=1. Предложение “По меньшей мере один объект обладает свойством P” имеет тот же смысл, что и предложение “Существует объект, обладающий свойством P”, т.е. (*)

Предложение “не более чем один объект обладает свойством P” равнозначно предложению “Если есть объекты, обладающие свойством P, то они совпадают”, т.е. (**) Предложение “один и только один объект обладает свойством P” равнозначно конъюнкции вышеуказанных предложений (*) и (**).

1.3 Отрицание предложений с кванторами.

Известно, что часто для отрицания некоторого предложения достаточно предпослать сказуемому этого предложения отрицательную частицу “не”. Например, отрицанием предложения “Река х впадает в Черное море.” является предложение “ Река х не впадает в Черное море ”. Годится ли этот прием для построения отрицаний предложений с кванторами? Рассмотрим пример.