рефераты конспекты курсовые дипломные лекции шпоры

Раздел Математика
/
Некоторые схемы доказательства теорем.

Реферат Курсовая Конспект

Выберите учебное заведение

Некоторые схемы доказательства теорем.

Некоторые схемы доказательства теорем. - раздел Математика, КУРС ЛЕКЦИЙ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ Многие Теоремы В Математике Имеют Форму Импли...

Многие теоремы в математике имеют форму импликации . В этом случае условие называют достаточным для условия , а условие – необходимым для условия .

Рассмотрим для примера известную из планиметрии теорему: «Если в треугольнике боковые стороны равны, то в этом треугольнике углы при основании равны». Разобьём формулировку теоремы на два высказывания: = «В треугольнике боковые стороны равны», = «В треугольнике углы при основании равны». Тогда видно, что данная теорема имеет вид импликации . Пусть - множество всех треугольников, - любой элемент из множества . Тогда последнюю импликацию можно обобщить для произвольного треугольника:

. (1)

(1) – логическая структура теоремы.

Кроме прямой теоремы рассматриваются ещё три:

(2)

(3)

(4)

Если (1) – прямая теорема, (2) – обратная к теореме (1). Если имеет место теорема (1), то это не значит, что теорема (2) также имеет место. Теорема (3) является противоположной к теореме (1). Теорема (4) – теорема, обратная к противоположной.

В силу закона контрапозиции: , теоремы (1) и (4), а также (2) и (3) попарно равносильны. Поэтому вместо теоремы (1) можно доказывать равносильную ей теорему (4). В силу закона двойного отрицания, теоремы (2) и (4) являются взаимно противоположными.

Для некоторых предикатов и может оказаться, что имеют место и теорема (1), и теорема (2). Тогда эти две теоремы можно объединить в эквивалентность:

. (5)

Такое объединение правомочно в силу следующего закона: . Это правило показывает, что теорема (5) состоит из двух теорем: (1) и (2). Для того, чтобы доказать теорему (5), нужно доказать теорем (1) и (2) (необходимость и достаточность). Для прямой теоремы (1) принята следующая терминология: выполнение свойства необходимо влечёт выполнение свойства . Или: свойство является необходимым условием свойства . Прямая теорема (1) часто называется необходимым условием теоремы (5). Доказательство теоремы (1) называется доказательством необходимости. Для обратной теоремы (2) принята своя терминология: свойство является достаточным условием выполнения свойства . Условие называется достаточным условием теоремы (5). Её доказательство – это доказательство достаточности. Существует другой способ доказательства теорем вида . Для доказательства находят последовательность эквивалентностей вида , ,…, . На основании закона транзитивности отсюда можно сделать вывод об истинности данной теоремы. Кроме того, иногда доказательство теоремы «равносильно » заменяют доказательством противоположной теоремы «не равносильно не ».

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

КУРС ЛЕКЦИЙ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ... ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ... имени ВЛАДИМИРА ДАЛЯ...

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

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ
(для студентов специальности “Прикладная математика”) У т в е р ж д е н о на заседании кафедры прикладной математики

Отрицание – обозначается ,читается:«не » или «неверно, что ».
2) Дизъюнкция (логическое сложение), обозначаемое(читается «

Упражнения для самостоятельной работы.
1. Даны следующие высказывания: P = «Данное число – целое», Q = «Данное число – положительное», R = «Данное число – простое», S = «Данное число

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

Доказательство.
Необходимость: Пусть формулы и

Упражнения для самостоятельной работы.
1. Определить, является ли данная последовательность символов формулой: 1)

Совершенные нормальные конъюнктивные и дизъюнктивные формы. Полные системы логических связок.
Определение 1:Элементарной конъюнкцией называется конъюнкция переменных, каждая из которых стоит под знаком отрицания или без него. Например:

Определение 4: Формула, представленная в виде конъюнкции элементарных дизъюнкций, называется совершенной нормальной конъюнктивной формой (СНКФ).
Замечание: Каждая элементарная конъюнкция (дизъюнкция), входящая в СНДФ (в СНКФ), должна содержать все пропозиционные буквы, входящие в исходную формулу. Только в этом случае м

Алгоритм преобразования произвольной формулы в СНДФ.
1) Выразить все логические операции через конъюнкцию, дизъюнкцию и отрицание. 2) Используя дистрибутивные законы, преобразовать формулу так, чтобы все конъюнкции выполнялись раньше дизъюнк

Замечание о представлении произвольной формулы многочленом Жегалкина.
Введём следующие обозначения: , .

Упражнения для самостоятельной работы.
1. Привести к СНДФ данные формулы: 1) , 2)

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

Определение 3: Множество всех значений таких, что предикат при этих значениях принимает значение «истина», называется областью истинности предиката.
Определение 4: Предикат , определённый на множестве

Упражнения для самостоятельной работы.
1. Прочитать следующие высказывания. Какие из них принимают истинные значения? 1) ; 4)

Формулы и тавтологии логики предикатов.
При введении определения формул логики предикатов будем использовать следующие обозначения (алфавит): 1)

Упражнения для самостоятельной работы.
1. Записать следующие высказывания в виде формул логики предикатов. 1) Всякое натуральное число, делящееся на 12, делится на 2, 4 и

Рассмотрим некоторые схемы доказательства теорем.
1) Пусть и - одноместные предикаты,

Упражнения для самостоятельной работы.
1.Записать на языке логики предикатов аксиому математической индукции. 2. Записать на языке логики предикатов следующую те

Формальный язык логики высказываний.
Таблицы истинности в логике высказываний позволяют ответить на многие вопросы. Например, является ли данная формула тавтологией, противоречием или выполнимой формулой; влечёт ли она

Упражнения для самостоятельной работы.
1. Указать свободные и связные вхождения переменных в следующих формулах: 1)

Свойства теорий первого порядка.
Все результаты этого параграфа относятся к произвольной теории первого порядка. Всяк

Теоремы о полноте.
Теорема 1: Во всяком исчислении предикатов первого порядка всякая теорема является логически общезначимой. Доказательство:

Определение 4: Всякий терм, не содержащий переменных, называется замкнутым термом.
Счётная интерпретация теории будет и

Формальная арифметика. Система аксиом.
Пусть - теория первого порядка, в число предикатных букв которой входит

Принцип двойственности.
Пусть – некоторое подмножество множества булевых функций:

Линейные функции. Монотонные функции.
Рассмотрим систему функций: ,

Теорема Поста.
В предыдущем параграфе были рассмотрены некоторые классы булевых функций. В каждый класс попадают функции, обладающие определённым свойством. Для удобства введём сле

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