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

Отрицание предиката . Пусть предикат P(x 1 , x 2 , ..., x n) задан на множествах M 1 , M 2 , ..., M n . Предикат R(x 1 , x 2 ,..., x n) называется отрицанием предиката P(x 1 , x 2 , ..., x n) тогда и только тогда, если при одних и тех же кортежах (a 1 , a 2 , ... , a n), где а 1 M 1 , а 2 M 2 , ..., аn M n , высказывание P(a 1 , a 2 , ..., a n) истинно, когда R(a 1 , a 2 , ..., a n) - ложно и наоборот. Обозначение

R(x 1 , x 2 , ..., x n) ù P(x 1 , x 2 , ..., x n)

Например, предикат "n - четное число" есть отрицание предиката "n - нечетное число" на множестве целых чисел.

Конъюнкция предикатов . Пусть на множествах M 1 , M 2 , ..., M n заданы два n - местных предиката P(x 1 , x 2 , ..., x n) и R(x 1 , x 2 , ..., x n). Конъюнкцией этих предикатов называется предикат

Q(x 1 , x 2 , ..., x n) P(x 1 , x 2 , ..., x n) R(x 1 , x 2 , ..., x n),

который истинен для одних и тех же кортежей только тогда, когда оба предиката и P(x 1 , x 2 , ..., x n) и Q(x 1 , x 2 , ..., x n) истинны.

Например, конъюнкция предикатов "x 2 + y 2 1" и "x 0", где x, y - вещественные числа определяет предикат "точки правой половины единичного круга" (см. рис.2.2).

Дизъюнкция предикатов P(x 1 , x 2 , ..., x n) и R(x 1 , x 2 , ..., x n), есть новый предикат S(x 1 , x 2 , ..., x n) = P(x 1 , x 2 , ..., x n) R(x 1 , x 2 , ..., x n), который имеет значение "ложь" для тех и только тех кортежей из M 1 M 2 ... M n , для которых оба предиката и P(x 1 , x 2 , ..., x n) и R(x 1 , x 2 , ..., x n) имеют значение "ложь". На рис.2.3 иллюстрируется дизъюнкция предиката "x 2 + y 2 1" и "x 0" - (заштрихованная область).

Импликация предикатов P(x 1 , x 2 , ..., x n) и R(x 1 , x 2 , ..., x n), есть новый предикат T(x 1 , x 2 , ..., x n) = P(x 1 , x 2 , ..., x n) R(x 1 , x 2 , ..., x n), который имеет значение "ложь" для тех и только тех кортежей из M 1 M 2 ... M n , для которых предикат P(x 1 , x 2 , ..., x n) имеет значение "истина", а предикат R(x 1 , x 2 , ..., x n) имеет значение "ложь". Например, импликация "n делится на 4" " n делится на 2" есть предикат: "если n делится на 4, то n делится на 2".

Эквивалентность предикатов P(x 1 , x 2 , ..., x n) и R(x 1 , x 2 , ..., x n), есть новый предикат V(x 1 , x 2 , ..., x n) = P(x 1 , x 2 , ..., x n) R(x 1 , x 2 , ..., x n), который имеет значение "истина" для тех и только тех кортежей из M 1 M 2 ... M n , для которых предикат P(x 1 , x 2 , ..., x n) и предикат R(x 1 , x 2 , ..., x n) имеют одинаковые значение или оба "истина" или оба "ложь". Два предиката заданных на одних и тех же множествах называются равносильными , если при всех наборах входящих в них предметных переменных эти предикаты принимают одинаковые значения. Равносильность называют также логической эквивалентностью . Например, эквивалентность предикатов P(n) = "n делится на 6" и R(n) = "n делится на 2 и n делится на 3" есть предикат V(n) = P(n) R(n): "если n делится на 6, то n делится на 2 и на 3". Предикаты P(n) и R(n) логически эквивалентны.

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

Квантор всеобщности есть операция, которая предикат P(x) превращает в высказывание: "все x обладают свойством P(x)". Знак квантора всеобщности " ". Он заменяет фразы: "для всех", "каждый", "любой" и т.п. Обозначение x: P(x) читается так: "для всех x таких, что P от x". Например, “P(x) = x>0 , где x - вещественное число”, есть предикат "x - положительное число". Тогда x: P(x) есть высказывание "каждое число - положительно". Это ложное высказывание. Если же x - любое натуральное число (x N), то x: P(x) есть выражение: "каждое натуральное число - положительно" - истинное высказывание.

Квантор всеобщности можно рассматривать как обобщение серии конъюнкций единичных высказываний. Пусть M - множество очков, которое может выпасть при бросании игральной кости, т.е. M ={1,2,3,4,5,6} и P(x) - предикат: "при бросании игральной кости один раз выпадает x очков", где x M. Применение квантора всеобщности позволяет вместо сложного высказывания P(1) P(2) P(3) P(4) P(5) P(6) записать равносильное ему компактное высказывание x: P(x), x M: "при бросании игральной кости один раз может выпасть любое из шести первых натуральных чисел".

Квантор существования есть операция, которая предикат P(x) превращает в высказывание: "существует хотя бы один x из M, обладающий свойством P(x)". Знак квантора существования " ". Он заменяет фразы: "существует, хотя бы один", "найдется", "некоторый" и т.п. Обозначение x: P(x) читается так: "существует хотя бы один x такой, что P от x". Например, P(x) - предикат: "x - студент", где x - элемент множества жителей Москвы. Тогда выражение x: P(x) есть высказывание "хотя бы один житель Москвы является студентом".

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

P(а 1) P(а 2) ... P(а n) ( x M): P(x).

Кванторы обладают свойствами, являющимися аналогами законов де Моргана:

ù( x: P(х)) х:ù P(х),

ù( х: P(х)) х: ùP(х).

С помощью кванторов можно выражать ряд часто используемых на практике отношений между множествами. Например, высказывание "все объекты х из данного множества, обладающие свойством P(х), обладают также и свойством R(х)" формально можно записать так; х: (P(х) R(х)).

Переход от P(х) к х:P(х) или х:P(х) называется квантификацией или связыванием переменнойх . Связанная переменная фактически не является переменной, т.е. переход от х: P(х) к y:P(y) или от х:P(х) к y: P(y) не меняет истинности выражений. Навешивание переменной на многоместный предикат уменьшает в нем число свободных переменных и превращает его в предикат от меньшего числа переменных.

Рассмотрим пример. На множестве чисел задан двухместный предикат P(х,y)="число х делится на число y". Связывая одну переменную, можно получить следующие одноместные предикаты:

Х: P(х,y) = "каждое число делится на y" - ложь;

X: P(x,y) = "существует число, которое делится на y"- истина;

Y: P(х,y) = "число х делится на любое число" - ложь;

Y: P(х,y) = "существует число на которое делится х" - истина.

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

Х, y:P(х,y)="каждое число делится на любое число" - ложное высказывание,

Х, y:P(х,y)="существует число, на которое делится любое число" - истина, т.к. такое число есть 1,

Х, y:P(х,y)="существует число, которое делится на любое число" - ложное высказывание,

Х, y: P(х,y)="существует число, которое делится на какое-нибудь число" - истинное высказывание.

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

Определение 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.

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

Предикатом называется любое выражение содерж переменную при подстановке значений которых оно обращается в высказывание которое принимает значение 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) и “ложь” (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 Отрицание предложений с кванторами.

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

Рассмотрим выражение «х –– простое число». Подставляя вместо х числа 3, 4, получаем высказывания, причем в первом случае оно будет истинным, а во втором –– ложным. Таким образом, каждому натуральному числу соответствует значение «И» и «Л» в зависимости от того, является оно простым или нет.

Следовательно, выражение «х –– простое число» определяет функцию одной переменной (одноместную), заданную на множестве натуральных чисел со значениями в множестве {И, Л}.

Аналогично, подставляя в выражение «х Подобным образом выражение «х и у –– родители z» определяет функцию трех переменных (трехместную) на множестве людей со значениями в множестве {И, Л}. Выражение х1 + х2 + … + хn = 0 определяет функцию n переменных (n–местную), заданную на множестве действительных чисел со значениями в множестве {И, Л}:

Такие функции называются предикатами.

Определение 1. n–местным предикатом на множестве М называется n–местная функция, аргументы которой принимают значения из множества М, а область значений есть множество {И, Л}.

Короче, n–местным предикатом на множестве М называется функция типа Мп→{И, Л}.

Для обозначения предикатов используют либо большие латинские буквы, либо символы: А(х, у), В(х), Р(х1, х2,…, хn) и т.д. (к предикантным символам А, В, Р добавляют в скобках символы переменных, от которых зависят данные предикаты). При этом, например, выражение А(10, 8) служит для обозначения (постоянного) высказывания, которое получается, если переменным х, и у предиката А(х, у) придать соответственно значения 10 и 8. Некоторые предикаты записывают с помощью тех или иных знаков, имеющих в теории определенный смысл, например: х = у, х > у, х + у = z и т.д.

При n = 1 n–местный предикат называют унарным, при n = 2 –– бинарным, а при n = 3 –– тернарным.

Определение 2. Пусть Р(х1, х2,…, хn) –– n–местный предикат, определенный на множестве М. Множеством истинности этого предиката называется совокупность таких упорядоченных n–ок (х1, …, хn), для которых Р(х1, х2,…, хn) принимает значение И.

Определение 3. Два предиката Р(х1, …, хn) и Q(х1, …, хn), определенные на одном и том же множестве М, называются равносильными на множестве М, если они принимают одинаковые значения И или Л при любых значениях х1, …, хn из множества М.

Таким образом, два предиката Р(х1, …, хn) и Q(х1, …, хn) на множестве М называются равносильными на множестве М, если множества истинности этих предикатов совпадают.

Определение 4. Предикат Р(х1, …, хn), определенный на множестве М, называется тождественно–истинным (тождественно–ложным) на М, если при подстановке вместо х1, …, хn любых элементов из множества М он принимает значение И (Л), т.е. множество истинности этого предиката Мn (пустое).

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

Пример. Пусть Р(х) и Q(х) –– два одноместных предиката, определенных на множестве М. Тогда Р(х) Ù Q(х) –– предикат на множестве М. Он является истинным для тех и только тех элементов из М, для которых оба предиката Р(х) и Q(х) истинны, т.е. множество истинности предиката Р(х) Ù Q(х) равно пересечению множеств истинности предикатов Р(х) и Q(х).

Аналогично определяется Р(х) U Q(х). Предикат Р(х) U Q(х) задан на том же множестве М и является истинным для тех и только тех элементов х из М, для которых истинен хотя бы один из предикатов Р(х) и Q(х), т.е. множество истинности предиката Р(х) U Q(х) равна объединению множеств истинности предикатов Р(х) и Q(х).

Предикат определен на множестве М и истинен для тех и только тех элементов х из М, для которых Р(х) ложен. Другими словами, множество истинности предиката –– дополнение в М множества истинности предиката Р(х).

Подобным образом вводятся предикаты Р(х) ? Q(х), Р(х) Û Q(х).

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

Пусть Р(х, у) и Q(х, у) –– два двухместных предиката, определенных на множестве М. Тогда Р(х, у) Ù Q(y, z) –– трехместный предикат на множестве М, он принимает значение И для тех и только тех упорядоченных троек (х, у, z) множества М, для которых Р(х, у) и Q(y, z) одновременно принимают значения И.

Отметим еще, что Р(х, у) Ù Q(х, у) –– двухместный, а Р(х, у) Ù Q(z, v) –– четырехместный предикаты, определенные на множестве М.

Если Р(х) и Q(х) –– два одноместных предиката, то не следует смешивать предикаты Р(х) Ù Q(х) и Р(х) Ù Q(у). Первый из них –– одноместный, а второй –– двухместный предикаты.

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

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

Часть в выражении называется квантором общности (всеобщности). Выражение читается «для любого х Р(х)». Символ –– перевернутая первая буква слова all (англ.), allе (нем.).

Пусть Р(х) –– предикат «х –– простое число», определенный на множестве натуральных чисел. Тогда высказывание (х –– простое число) ложно на множестве натуральных чисел. Это же высказывание (х –– простое число) истинно на множестве простых чисел.

Определение 6. Пусть Р(х) –– одноместный предикат, определенный на множестве М. Символом $ обозначим высказывание, которое истинно, когда в множестве М существует такой элемент х0, что Р(х0) = И, и ложно в противоположном случае, т. е. $ –– истинное высказывание, если множество истинности предиката Р(х) непустое; в противном случае $ –– ложное высказывание.

Выражение $ читается «существует х такое, что Р(х)», а часть $х в выражении $ называют квантором существования. Например, высказывание $х (х –– простое число) на множестве натуральных чисел истинно, высказывание $ на множестве действительных чисел ложно.

Символ $ –– перевернутая первая буква слова exist (англ.), existieren (нем.), exister (фр.).

Замечание 1. Применение квантора превращает одноместные предикаты в высказывания (не зависящие от х). Совершенно аналогично применяются кванторы к любому предикату с большим числом переменных. В результате применения квантора к n –– местному предикату (при n > 0) получается (n – 1) –– местный предикат.

Замечание 2. К одному и тому же предикату можно применять кванторы несколько раз. Например, применив к предикату Р(х, у) квантор существования по х, мы получим одноместный предикат $, к которому опять можем применить квантор существования или квантор общности по переменной у. В результате получим высказывание

$у($ или у($.

Скобки обычно опускают, получая при этом выражения

$у$ или у$.

Замечание 3. Одинаковые кванторы можно переставлять, получая при этом эквивалентные высказывания, т.е. истинные эквиваленции.