Глухов М. М. Алгебра том 1, страница 4

К предикатам, так же, как и к высказываниям, можно применить операции конъюнкции, дизъюнкции, импликации и отрицания. В результате из заданных предикатов будут получаться новые, более сложные предикаты. Так, например, дизъюнкцией предикатов "у < т", "т = = у" будет предикат "(х < у) Ч (т = у)", который короче записывается в виде "т < у". Приведем для указанных операций над предикатами теоретико-множественную интерпретацию. Для простоты ограничимся рассмотрением предикатов от одного переменного т на фиксированном множестве А.

Каждому такому предикату р(х) сопоставим подмножество его истинности Аф) = (а Е А: р(а) = и). Непосредственно из свойств логических и теоретико-можественных операций следуют соотношения: а) А(р1йр2) = А(р1) П А(р2), б) А(р1 Ч р2) = А(р1) 0 А(р2), в) А(р1 ~ р2) = А~(А(р1)~А(р2)) г) А(р~) = А~А(р1). Кроме указанных бинарных логических операций к предикатам часто применяются еще две унарные операции навешивания кванторов. Пусть р(х1,..., т„) — предикат, зависящий от переменных т1,..., т„ со значениями из множества А. Тогда из него можно построить новые предикаты: "Для всякого т1 Е А имеет место р(х1,..., т„)". "Существует т1 е А такое, что р(х1,..., т„)".

Говорят, что они получены из р(т1,..., т„) путем навешивания соответственно квантора всеобщности и квантора существования по переменному т1. Кратко они обозначаются в виде: Аналогично определяются операции навешивания кванторов по любо- му другому переменному т;,г Е 2,п. Заменив в (3), (4) переменные х2,..., т„соответственно элементами а2,..., а„е А, получим высказы- вания: Первое является истинным тогда и только тогда, когда высказывание р(а1,а2,..., а„) является истинным при любом а1 Е А. Второе истинно в том и только том случае, когда высказывание р(а1, а2,..., а„) истинно хотя бы при одном а1 из А. Таким образом, высказывания (3'), (4') не зависят от переменного т1, и потому (3), (4) являются предика- тами от и — 1 переменных т2,..., т„. К ним можно применять операции навешивания кванторов по любому из переменных т2,..., т„и т.

д. Следует помнить, что истинность высказывания, полученного из предиката путем навешивания кванторов по разным переменным, в общем случае зависит от порядка кванторов. Так, например, высказывание "Чт Е И, Зу е И: (т ( у)" истинно, а высказывание "3у Е И,Чт Е Е И: (т ( у)" ложно. С помощью логических операций й, Ч, ~, —, Ч, 3 можно из заданных высказываний и предикатов естественным образом строить выражения или формулы, которые будут задавать новые высказывания и предикаты.

Две формулы от одних и тех же переменных, принимающих значения из одного множества, называют равносильными или эквивалентными, если они принимают одинаковые значения (истину или ложь) при любых, одинаковых для обеих формул наборах значений переменных. Условимся равносильность формул обозначать знаком =. С помощью равносильностей формул можно записать свойства логических операций над предикатами. Приведем примеры: Чхр(х): — Эхр~х), Эхр(х) = Чхр(х). В =~ А. (А=~В) й (В=~А), которое записывают в виде: А~В (5) А=~В, (б) В =~ А А=~В (7) противоположным к (5). 20 21 Обратим особое внимание на следующие равносильности, которые часто используют при доказательствах: Справедливость выписанных равносильностей проверяется непосредственно с использованием определения логических операций.

Заметим, что логическая символика зачастую бывает полезной как в целях сокращения записи утверждений, так и с целью достижения их лучшей обозримости. Для примера запишем условия инъективности и сюръективности отображений ~: А — ~ В: Ча1, а2 Е А: иа1 ф а2) =~ ®а1) ф Да2))), Ч6 Е В, 3а Е А: (Да) = 6). ~ 3. О математических утверждениях и методах их доказательства Типичной формой математического утверждения, или теоремы, является импликация: которая читается как "Из А следует В", или "Если истинно А, то истинно В", или "А влечет В", или "А достаточно для В", или "В необходимо для А".

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

Приведите примеры. С другой стороны, из определений импликации и отрицания легко следует, что формула (5) равносильна формуле В =~ А. Значит, любая теорема равносильна противоположной к обратной ей теореме, и вместо доказательства импликации (5) можно доказывать импликацию: Так зачастую и поступают. В том случае, когда для теоремы (5) верной является и обратная теорема (б), их обычно объединяют в одно утверждение: и словесно читают в одной из следующих формулировок: "А имеет место тогда и только тогда, когда имеет место В"; "А выполняется в том и только в том случае, когда выполняется В"; "Для выполнения А необходимо и достаточно выполнение В"; "Для выполнения В необходимо и достаточно выполнение А" и т.

д. Доказать теорему (5) — значит установить истинность импликации (5). Подчеркнем, что в общем случае истинность импликации (5) не означает истинности В. Из определения операции импликации видно, что при ложном утверждении А импликация (5) истинна при любом (в частности, и при ложном) В, и в этом случае никакого доказательства не требуется, Значит, доказывать теорему (5) надо лишь в том случае, когда утверждение А истинно, и в этом случае для доказательства нужно установить истинность утверждения В. Не вдаваясь в строгие логические формулировки, можно сказать, что любое математическое доказательство представляет собой конечную последовательность логических умозаключений, основанных на известных ранее математических фактах и логических правилах ~законах логики).

Приведем, для примера, некоторые широко используемые в доказательствах правила логики, позволяющие из истинности одних утверждений получать истинность других. Если при этом из истинности утверждений А1,..., А„получается истинность утверждения В, то будем записывать это в виде: (А1,...,А„) =~ В. 1. Правило заключения: (А, А =~ В) =~ В. 2. Правило силлогизма: (А =~ В, В =~ С) =~ (А =~ С). 3. Правило контрапозиции: (А =~ В) =~ (В =~ А). 4. Правила двойного отрицания: А =~ А, А =~ А.

5. Правило сложения посылок: (А =~ С, В ~ С) =~ (А Ч В =~ С). б. Правило умножения заключений: (А =~ В,А =~ С) =~ (А =~ =~ ВйС). Отдельные доказательства явно выделяются своей спецификой. Укажем три типа таких доказательств. 1. Метод непосредственной проверки Этим методом обычно доказывают равенства или некоторые другие соотношения, а само доказательство заключается в осуществлении последовательности действий, существо и порядок которых определяются самой формулировкой доказываемого утверждения. Примером такого доказательства может служить доказательство формул сокращенного умножения.

Так, для доказательства формулы (а + 6иа — 6) = а — 6 достаточно перемножить многочлены а+ 6 и а — 6 привести подобные члены и сравнить результат с выражением а — 6 . 2. Метод доказательства "от противного" Для доказательства этим методом некоторого утверждения А допускают, что утверждение А ложно, то есть истинно его отрицание А. Далее, с использованием утверждения А доказывают некоторое заведомо ложное утверждение Г и из этого делают вывод о том, что сделанное предположение о ложности А неверно, и поэтому А — истинно. В основе этого метода лежит логическое правило (А =~ Г, Г = л) =~ А. В том случае, когда доказываемое утверждение имеет вид А =~ В и утверждение А истинно, в доказательстве методом "от противного" допускают, что верно утверждение В, и из А и В выводят некоторое ложное утверждение Г.

Отсюда делают вывод о том, что из истинности А следует истинность В. В этом случае используется логическое правило: (Ай В =~ Г, Г = л) =~ (А =~ В). 22 В некоторых случаях, исходя из А и В, доказывают утверждение А. В этой ситуации роль Г играет ложное утверждение Ай А. В качестве примера доказательства методом "от противного" приведем известное утверждение о действительных числах. "Произведение двух, отличных от нуля, действительных чисел отлично от нуля".