Предикаты и логические операции над ними. Предикат. Операции над предикатами. Классы рекурсивных функций

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 и Т .

Рассмотрим выражение «х –– простое число». Подставляя вместо х числа 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. Одинаковые кванторы можно переставлять, получая при этом эквивалентные высказывания, т.е. истинные эквиваленции.

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

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

ОПРЕДЕЛЕНИЕ 5. ДИЗЪЮНКЦИЕЙ предикатов, заданных на множестве Х, называется предикат А(х) В(х), обращающийся в истинное высказывание при тех и только тех значениях х из множества Х (х Х), при которых хотя бы один из предикатов А(х) и В(х) обращается в истинное высказывание.

Width:="" auto="">

Можно заметить, что множеством истинности дизъюнкции предикатов является объединение множеств ТА и Т В, т. е. Т А В =ТА ТВ. Докажем это предположение.

1). Сначала докажем, что множество Т А В является подмножеством множества ТА ТВ (Т А В ТА ТВ). Пусть x = a – произвольный элемент из множества ТА В, т. е. а ТА В. Следовательно, А(а) В(а) – «и» высказывания. По определению, А(а) В(а) – «и» только тогда, когда А(а) – «и» или В(а) – «и. »

Если А(а) – и, то а ТА, если В(а) - и, то а ТВ. Т. к. А(а) В(а) – и, то а ТА или а ТВ –, это значит, что а ТА ТВ. а - произвольный элемент из ТА В, следовательно, все элементы множества ТА В принадлежат множеству ТА ТВ, т. е. ТА В ТА ТВ, ч. т. д.

2). Докажем, что множество ТА ТВ является подмножеством множества Т А В (ТА ТВ Т А В). Пусть х = в – произвольный элемент из ТА ТВ, в ТА ТВ, по определению, в ТА или в ТВ А(в) – «и» или В(в)- «и» А(в) В В(в)- «и» в ТА В.

Следовательно, если в ТА ТВ, то в ТА В. т. к. Т. К. в – произвольный элемент из ТА ТВ, то ТА ТВ Т А В, ч. т. д.

Из пунктов 1 и 2 по определению равных множеств следует справедливость равенства Т А В = ТА ТВ Заметим, что полученное правило справедливо и для предикатов, содержащих более одной переменной.

ПРИМЕР. Предикаты: А(х)- «х-делитель числа 15» и В(х) - «х –делитель числа 16» . Множество истинности А(х)- ТА ={1, 3, 5, 15 }, множество истинности В(х) -ТВ ={1, 2, 4, 8, 16}. Множество истинности дизъюнкции предикатов Т А В = {1, 2, 3, 4, 5, 8, 15, 16}.

ОПРЕДЕЛЕНИЕ 6. ОТРИЦАНИЕМ предиката А(х), заданного на множестве Х, называется предикат А(х) (« не А(х) »), определенный на том же множестве и истинный при тех и только тех значениях переменной х из множества Х (х Х), при которых предикат А(х) обращается в ложное высказывание.

ПРИМЕР. Предикат А(х)- « х - четное число » . Отрицание предиката: А(х) «х - нечетное число» . Пусть область определения предиката А(х) - Х={х, х N, х

Множество истинности предиката А(х) - все нечетные числа, меньшие 10: ТА = {1, 3, 5, 7, 9}. Из примера видно, что ТА = Х ТА = ТА т. е. множество истинности предиката « не А(х) » является дополнением к множеству истинности предиката А(х). Х = ТА

КВАНТОР – общее название для логических операций, которые по предикату Р(х) строят высказывание, характеризующее область истинности предиката Р(х). В математической логике наиболее употребительны квантор всеобщности (х), квантор существования (х) и квантор единственности существования (! х).

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

Высказывание, полученное из предиката Р(х) при помощи квантора общности, записывается в виде (х Х) Р(х) Высказывание, полученное из предиката Р(х) при помощи квантора существования, записывается в виде (х Х) Р(х) Высказывание «существует одно и только одно х X, для которого истинно Р(х) обозначают (!х X) Р(х)

Для того чтобы получить высказывание из многоместного предиката надо связать кванторами каждую переменную. Например, если Р (х, у) – двухместный предикат, то (х Х)(у Y) Р(х, у) – высказывание. ПРИМЕР. Задан предикат Р(х, у): «х>у» . Для получения высказывания надо связать кванторами обе переменные: например, (Х)(у) х>у или (у)(х) х>у.

ОПРЕДЕЛЕНИЕ ИСТИННОСТИ ВЫСКАЗЫВАНИЯ С КВАНТОРАМИ ИСТИННОСТЬ высказывания с квантором общности устанавливается путем доказательства. Чтобы убедиться в ложности таких высказываний (опровергнуть их) достаточно привести контрпример. .

Истинность высказывания с квантором существования устанавливается при помощи конкретного примера. Для опровержения такого высказывания необходимо провести доказательство. Для чего нужны кванторы?

ВЫВОД. ПРЕДИКАТ обращается в ВЫСКАЗЫВАНИЕ двумя способами: 1). По определению, подставив вместо переменных их конкретные значения из области определения предиката; 2). Связать кванторами переменные, содержащиеся в предикате. Если предикат содержит несколько переменных, необходимо связать квантором каждую переменную.

ПРИМЕР. Пусть дано высказывание А: « Любые четные числа кратны 3» . Высказывание А: « Не любые четные числа кратны 3» или высказывание А: «Неверно, что любые четные числа кратны 3» , другими словами это можно сказать так: «существуют (есть) четные числа не кратные 3» . 8, 10, …

Для построения отрицания высказываний с кванторами надо: 1) квантор общности заменить на квантор существования, а квантор существования на квантор общности; 2) предложение, стоящее после квантора, заменить его отрицанием. (х Х) А(х) = (х Х) А (х) (х Х) А(х) = (х Х)А (х). Таким образом, получаем две равносильности. Или перед данным высказыванием ставят слова: «неверно, что» .

Это правило сохраняется и в том случае, если высказывание содержит не один, а несколько кванторов, например: (х Х)(х Y) А(х, y) = (х Х) (х Y) А (х, y) Для построения отрицания полезны следующие формулы: А(х) В(х) = А(х) В(х) , А(х) В(х)=А(х) В(х)

Рассмотрим два предиката А (х) и В (х). Пусть А (х) – «х: 6» ; В (х) – «х: 3» . Образуем импликацию предикатов «Если х: 6, то х: 3» . Множества истинности предикатов А(х) – ТА= {6, 12, 18, …}; В(х) – ТВ = {3, 6, 9, 12, 15, 18, … }. Из того, что «х: 6» всегда следует, что «х: 3» .

В этом случае говорят, что предикат В(х) логически следует из предиката А(х), а предикаты А(х) и В(х) находятся в отношении логического следования.

В этом случае множество истинности импликации таких предикатов совпадает с ее областью определения Т А В = Х. Отношение логического следования обозначается всегда А(х) => В (х).

Предикат А(х) называют достаточным условием для В(х), а предикат В(х) называют необходимым условием для предиката А(х). Это возможно тогда и только тогда, когда ТА ТВ. .

Src="https://present5.com/presentation/3/-42558499_158059721.pdf-img/-42558499_158059721.pdf-32.jpg" alt="Пример. Предложение «х: 6» => «х: 3» в этом случае читают так: чтобы «х:"> Пример. Предложение «х: 6» => «х: 3» в этом случае читают так: чтобы «х: 3» – достаточно, чтобы «х: 6» , а чтобы «х: 6» необходимо, чтобы «х: 3» .

Src="https://present5.com/presentation/3/-42558499_158059721.pdf-img/-42558499_158059721.pdf-33.jpg" alt="Логическое следование: достат. необход. А(х) => B(x), TА ТВ "> Логическое следование: достат. необход. А(х) => B(x), TА ТВ

Src="https://present5.com/presentation/3/-42558499_158059721.pdf-img/-42558499_158059721.pdf-34.jpg" alt="Пример: Предложение «х: 4» => «х: 2» в этом случае читают так: чтобы «х:"> Пример: Предложение «х: 4» => «х: 2» в этом случае читают так: чтобы «х: 2» – достаточно, чтобы «х: 4» , а для того чтобы «х: 4» необходимо, чтобы «х: 2» .

Если из А(х) следует В(х) и из В(х) следует А(х), то предикаты А(х) и В(х) называют равносильными или эквивалентными и записывают А(х) В(х). Это возможно тогда и только тогда, когда ТА= ТВ.

В этом случае А(х) является необходимым и достаточным условием для В(х), а В(х) – необходимым и достаточным условием для А(х). При этом А(х) => В(х) и В(х) =>А (х). ПРИМЕР. А(х)- «число х делится на 9» , В(х)- «сумма цифр числа х делится на 9» . А(х) В(х)

Теорема –это предложение (утверждение), истинность которого может быть доказана. Теоремы часто формулируются в виде импликаций: если А(х), то В(х) для каждого х, т. е. (х х)А(х) => В(х).

Src="https://present5.com/presentation/3/-42558499_158059721.pdf-img/-42558499_158059721.pdf-39.jpg" alt="(х х)А(х) => В(х). Чаще всего ее записывают так А => В (1)"> (х х)А(х) => В(х). Чаще всего ее записывают так А => В (1) Для всякой теоремы (1) можно сформулировать предложение: «Если В, то А» - обратное данному. Но не всегда это предложение является теоремой.

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

Но если обратное предложение – истинно, то оно наз. обратной теоремой. Например: Т 1: « Если треугольник прямоуг. , то квадрат гипотенузы равен сумме квадратов катетов» Обратное: « Если в треугольнике квадрат одной стороны равен сумме квадратов двух других, то треуг. – прямоуг. » Это -истина, поэтому оно наз. Теоремой, обратной данной.

Если в теореме Для всякой теоремы « Если А, то В» можно сформулировать предложение: « Если не А, то не В» . (если А, то В) Это предложение наз. Противоположным данному. Всегда ли оно будет теоремой? Пример. В том случае, если предложение является теоремой, то его наз. теоремой, противоположной данной. Если

Итак, если для теоремы «Если А, то В» сформулировать предложение, обратное или противоположное ей, то их надо доказывать и только тогда они будут наз. теоремой, обратной или противоположной данной. , если их истинность будет доказана

Для всякой теоремы « Если А, то В» можно сформулировать предложение « Если не В, то не А» «Если В, то А» - обратным противоположному. «Если углы -вертикальные, то они равны» и « если углы не равны, то они и не вертикальные» . Эти предложения всегда истинны, т. е всегда теорема. (А В В А). Эту равносильность наз. законом контрапозиции

Примеры: 1. Если четырехугольник – ромб, то его диагонали взаимно перпедикулярны. 2. Если каждое слагаемое - четное число, то и сумма - четная.

Это предложение наз. Противоположным данному. Всегда ли оно будет теоремой? Пример. В том случае, если предложение является теоремой, то его наз. теоремой, противоположной данной. Итак, если для теоремы «Если А, то В» сформулировать предложение, обратное или противоположное ей, то их надо доказывать и только тогда они будут наз. теоремой, обратной или противоположной данной.

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

Например, в рассуждении «Всякий ромб – параллелограмм; AВCD – ромб; следовательно, AВCD – параллелограмм» посылки и заключение являются элементарными высказываниями логики высказываний и с точки зрения этой логики рассматриваются как целые, неделимые, без учета их внутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.

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

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

Логика предикатов, как и традиционная формальная логика, расчленяет элементарное высказывание на субъект (буквально – подлежащее, хотя оно и может играть роль дополнения) и предикат (буквально – сказуемое, хотя оно может играть и роль определения).

Субъект – это то, о чем что-то утверждается в высказывании; предикат – это то, что утверждается о субъекте.

Например, в высказывании «7 – простое число», «7» – субъект, «простое число» – предикат. Это высказывание утверждает, что «7» обладает свойством «быть простым числом»

Если в рассмотренном примере заменить конкретное число 7 переменной х из множества натуральных чисел, то получим высказывательную форму «х – простое число». При одних значениях х (например. х = 13, х = 17) эта форма дает истинные высказывания, а при других значениях х (например, х = 10, х = 18) эта форма дает ложные высказывания.

Ясно, что эта высказывательная форма определяет функцию одной переменной х, определенной на множестве N, и принимающую значения из множества {1,0}. Здесь предикат становится функцией субъекта и выpaжает свойство субъекта.

Определение. Одноместным предикатом Р(х) нaзывается произвольная функция переменного х, определенная на множестве М и принимающая значения из множества {1,0}.

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

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

Так. предикат Р(х) – «х – простое число» определен на множестве N, а множество для нeгo есть множество всех простых чисел. Предикат Q(x) – «» определен на множествеR, а eгo множество истинности. Предикат F(x) «Диагoнали параллелогpамма х перпендикулярны» определен на множестве всех параллелограммов, а eгo множеством истинности является множество всех ромбов.

Приведенные при меры одноместных предикатов выражают свойства предметов.

Определение. Предикат Р(х), определенный на множестве М, называется тождественно истинным (тождественно ложным), если .

Естественным обобщением понятия одноместного предиката является понятие многоместного предиката, с помощью котopoгo выражаются отношения между предметами.

Примером бинарного отношения (отношения между двумя предметами) является отношение «меньше». Пусть это отношение введено на множестве Z целых чисел. Оно может быть охарактеризовано высказывательной формой «x<у », где, то есть является функцией двух переменных Р(х,у), определенной на множествес множеством значений {1,0}.

Определение. Двухместным предикатом Р(х, у) называется функция двух переменных х и y, определенная на множествеИ принимающая значения из множества {1,0}.

Аналогично определяется n-местный предикат.