М10 - 1. Логические операции над высказываниями и предикатами. Кванторы. Законы логики. Строение и виды математических теорем. Необходимые и достаточные условия.

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

Опр 1. Высказывание это повествовательное предложение, о котором можно сказать истинно оно или ложно.

Высказывания подчиняются двум законам

Закон противоречия. Никакое высказывание не может одновременно быть истинным или ложным.

Закон исключённого третьего. Всякое высказывание либо истинно, либо ложно (третьего не дано). Высказ. имеет истинностное значение "и" или "л"

Высказывания бывают простые (А, В, С) и сложные, сложные высказывания образуются из простых с логических операций. Сложные АС, АВ и т. д.

Опр 2. Конъюнкцией высказываний А, В называется сложное высказывание АВ, истинное тогда и только тогда, когда истины оба высказывания А, В. ( соответствует «и»)

Опр 3. Дизъюнкцией высказываний А и В называется сложное высказывание АВ, истинное тогда и только тогда, когда хотя бы одно из высказываний истинно ( соответствует «или»)

Опр 4. Импликацией высказываний А, В называется сложное высказывание АВ, ложное тогда и только тогда. Когда А истинно, а В ложно ( соответствует «если …то»)

Опр 5. Отрицанием высказывания А называется такое высказывание , истинное тогда и только тогда, когда А ложно (-- соответствует « не верно что»).

Их истинностные значения зависят от значений А и В и определяются по таблицам истинности:

А	В	АВ	АВ	АВ
и	и	и	И	и
и	л	л	И	л
л	и	л	И	и
л	л	л	Л	и

Логические операции позволяют определить истинностные значения сложных высказываний.

Предикаты.

Опр 6. Предикат- это повествовательное предложение с переменными, которое становится высказыванием, если вместо переменных подставит их значения из некоторого множества.

Бывают одноместные, двуместные и т.д. формы. Обозначаются Р(х) , Q(x;y), P(x1, x2,…xn).

Множество истинности предикатов:

Опр 7. Пусть предикат Р(х) задан на множестве М. Тогда множество истинности предиката Р(х) называют множество всех значений переменной хМ, при котором [P(x)]=и.

Обозн. Мх(Р). Тогда Мх(Р)={xМ/ [P(x)]=и}.

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

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

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

Импликацией предикатов называется операция, в результате которой из предикатов Р(х) и Q(х)образуется предикат Р(х)→Q(х), принимающий значение «Л» при тех и только тех значениях хМ, при которых [Р(х)]=И, а [Q(х)]=Л.

Отрицанием предиката называется операция, в результате которой из предиката Р(х) образуется предикат (х), принимающий значение «И» при тех и только тех значениях хМ, при которых [Р(х)]=Л.

Теорема 1(о множестве истинности). Пусть Р(х) и Q(x) заданы на некотором множестве М. Мх(Р) и Мх(Q) множество истинности Р(х) и Q(x), тогда выполняются следующее равенства: Мх(РQ)= Мх(Р)Мх(Q); Мх(РQ)= =Мх(Р)Мх(Q); Мх()= СМх(Р); Мх(РQ)= Мх()Мх(Q).

Дк-во: Докажем эту теорему «методом двух включений». Докажем, что М_х(РQ)= М_х(Р) М_х(Q)

Пусть Р(х) и Q(x) – высказывание формы, заданные на множестве М; М_х(Р) и М_х(Q) – их множества истинности, соответственно. Возьмем произвольный элемент х₀М.Пусть х₀ М_х(РQ), тогда [Р(х₀)  Q(х₀)] = и; отсюда [Р(х₀)]= и и [Q(х₀)]= и; значит х₀ М_х(Р) и х₀ М_х(Q); поэтому х₀М_х(Р) М_х(Q).

В силу произвольности х₀ , любой элемент, принадлежащий М_х(РQ), принадлежит М_х(Р) М_х(Q). Следовательно М_х(РQ)  М_х(Р) М_х(Q). Пусть х₀М_х(Р) М_х(Q), тогда х₀М_х(Р) и х₀ М_х(Q), отсюда [Р(х₀)]= и и [Q(х₀)]= и; значит [Р(х₀)  Q(х₀)] = и ,поэтому х₀ М_х(РQ). В силу произвольности х₀ , любой элемент из М_х(Р) М_х(Q) принадлежит М_х(РQ). Следовательно М_х(Р) М_х(Q)  М_х(РQ).Показано: М_х(РQ)  М_х(Р) М_х(Q) и М_х(Р) М_х(Q)  М_х(РQ). Отсюда следует, что М_х(РQ)= М_х(Р) М_х(Q). Теорема даказана.2-4 доказывается аналогично.

Множество решений уравнения (неравенства) есть множество истинности соответствующей высказывательной формы, решить уравнение (неравенство) – найти это множество истинности.

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

Законы логики.

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

Опр8. Две формулы называются равносильными, если они принимают одинаковые истинностные значения в каждой строке таблицы истинности.

Равносильность двух формул можно проверить с помощью таблиц истинности.

Для доказательства неравносильности двух формул достаточно привести контрпример, т.е. найти хотя бы одну строку таблицы истинности (хотя бы один набор значений высказ-х переменных), в которой формулы принимают различные истинностные значения

Законы логики: позволяют производить преобразования формул алгебры высказываний

Законы де Моргана

1) 2)

2. Закон устранения импликации

3.Отрицание импликации

4. Закон двойного отрицания

5. Закон контрапозиции

6. Закон противоречия

7. Закон исключённого третьего

8.Законы поглощения

1) АИ  И 2) АИ  А 3) АА  А

4) АА  А 5) АЛ  А 6) АЛ  Л

9. Арифметические свойства конъюнкции дизъюнкции

1) АВВА, АВВА (законы коммутативности)

2) (АВ)СА(ВС), (АВ)СА(ВС) (законы ассоциативности)

3) (АВ)С(АВ)(АС),

(АВ)С(АВ)(АС) (законы дистрибутивности)

Кванторы

1.Квантор существования (существует, имеется, есть хотя бы один) – обозн. Например: Существует такое х, что х-четное число.

2.Квантор общности (любой, всякий, каждый) обозн.-. Например: Любое х-четное число.

Символически 1.(х)P(х) 2.(х)P(х) Чтобы определить истинность высказывания с квантором нужно ответить на вопрос: правда ли то, что утверждает квантор.

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

[(х)P(х)]=и, если [P(х)]=и при всех хМ.

[(х)P(х)]=л, если P(х) истинно не при всех хМ (т.е. найдется хотя бы одно значение хМ, при котором [Р(х)]=л)

[(х)P(х)]=и, если существует хотя бы одно значение хМ, при котором [Р(х)]=и [(х)P(х)]=л, если не существует такого значения хМ, при котором [Р(х)]=и (т.е. [P(х)]=л при всех хМ).

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

Запись (х)P(х) – существует единственное значение х, такое что P(х).

Кванторные законы

1.Законы де Моргана

Перестановка одноимен. кванторо

Важно! Разноименные кванторы менять местами нельзя

Строение и виды математических теорем.

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

В общем виде ВУП выглядит так (хМ)(А(х) В(х)), где (хМ) - разъяснительная часть, А(х)-условие, В(х)-заключение.

Пример: «Диагонали ромба перпендикулярны» (АВСД-черырёхугольник)((АВСД-ромб) (диагонали АВСД перпендикулярны)).

(АВСД-черырёхугольник)- разъяснительная часть, (АВСД-ромб)- условие, (диагонали АВСД перпендикулярны)- заключение.

Виды ВУП

Прямое (хМ)(А(х) В(х))

Обратное(хМ)(В(х) А(х))

Противоположное (М)(

Контрапозиционным (

Прямое и контрапозиционным ВУП равносильны, точно также как обратное и противоположное по закону контропозиции.

Правило контрпримера для ВУП

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

Пусть требуется доказать, что [(хМ)(А(х) В(х))]=л. Для этого достаточно найти элемент такой, что[А(а) В(а)]=л, т.е. [А(а)]=и, а [В(а)]=л. Найденное значение и будет контрпримером, доказывающим ложность васказавания (хМ)(А(х) В(х))

Необходимые и достаточные условия

Опр9.Если истинно высказывание АВ, то А называют достаточным условием для В, а В называют необходимым условием для А.

Различные формулировки необходимости:

«Если А, то В», «А выполняется только тогда, когда выполняется В», «Для того, чтобы выполнялось А, необходимо, чтобы выполнялось В»,

Достаточности:

«Если А, то В», «В выполняется тогда, когда выполняется А», «Для того, чтобы выполнялось В, достаточно, чтобы выполнялось А»,

Если истинны оба высказ. АВ и ВА, то В является необходимым и достаточным для А, в этом случае также А необходимо и достаточно для В.

«Если А, то В и если В, то А»,

«Для того, чтобы выполнялось А, необходимо и достаточно, чтобы выполнилось В», «А выполняется тогда и только тогда, когда выполняется В»

М10 - 2. Алгоритмы в математике. Основные черты алгоритмов. Числовые функции и алгоритмы их вычисления.

Перечислимые множества.

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

Вычислимые функции.

Функция называется вычислимой, если существует алгоритм, её вычисляющий, т. е. такой алгоритм А, что: - если f(x) определено для некоторого , то алгоритм А останавливается на входе x и печатает f(x); - если f(x) не определено, то алгоритм А не останавливается на входе x.

Пример: .

Разрешимые множества.

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

Свойства множеств:

1. Пересечение, объединение и разность разрешимых множеств разрешимы:

Если X и Y разрешаются алгоритмами А и В, то их пересечение разрешается алгоритмом С, который имея на входе n, выполняет алгоритм А и если результат положительный, то выполняет В, иначе выводит отрицательный ответ. Если результат выполнения алгоритма В положительный, то выводится положительный ответ, иначе – отрицательный.

2. Любое конечное множество разрешимо.

Конечное множество всегда можно перебрать, сравнивая результаты с n перечислимых множеств Свойство: Пересечение и объединение перечислимых множеств перечислимы.

Если Х и Y перечисляются алгоритмами А и В, то их объединение перечисляется алгоритмом С, который параллельно выполняет по шагам А и В (сначала 1 элемент выводится алгоритмом А, затем элемент выводится алгоритмом В и т. д.) и печатает всё, что печатают А и В. Т. о. все элементы, принадлежащие хотя бы одному из множеств Х или Y, и только они, будут напечатаны алгоритмом С. Итак, С перечисляет множество XY.

алгоритм С, который параллельно выполняет по шагам А и В (сначала 1 элемент выводится алгоритмом А, затем элемент выводится алгоритмом В и т. д.) накапливает результаты работы А и В и каждый новый элемент сверяет с накопленными до этого. Если равенство выполнилось, то последний элемент печатается. Т. о. алгоритм С напечатает все элементы принадлежащие XY, и только их. Итак, С перечисляет множество XY.

Дополнение перечислимого множества не обязано быть перечислимым.