Вход

Элементы математической логики

Рекомендуемая категория для самостоятельной подготовки:
Реферат*
Код 284899
Дата создания 05 октября 2014
Страниц 17
Мы сможем обработать ваш заказ (!) 29 марта в 12:00 [мск]
Файлы будут доступны для скачивания только после обработки заказа.
1 150руб.
КУПИТЬ

Описание

нет
...

Содержание

Содержание

Введение 3
Основные понятия алгебры высказываний. Логические высказывания, логические операции над высказываниями 4
Строение теорем. Необходимое и достаточное условия 8
Булева алгебра 10
Предикаты. Кванторы всеобщности и существования 12
Применение математической логики в алгоритмизации, теории автоматов, языках и грамматике 15
Литература 17

Введение

Введение
Логика — наука, изучающая с формальной точки зрения понятия, методы их определения и преобразования, суждения о них и структуры доказательных рассуждений. Ее создание сделало возможным развитие европейской науки, а ее переход на стадию математической логики оказал большое влияние на всю европейскую научную мысль.
Логика имеет уникальную историю. Она была создана в классической Греции, практически одним человеком – Аристотелем.
Логику Аристотеля часто называют философской либо формальной. Она стала неотъемлемым компонентом образования европейских философов, юристов, теологов, т. е. людей, длительное время составлявших подавляющую и самую влиятельную часть образованного слоя общества.
Древние математики заметили, что логика могла бы стать математической наукой. Предвестники нового этапа в логике появились в работах Лейбница, когда традиционная задача математики: «заменить вычисления рассуждениями» была инвертирована и превратилась в задачу математической логики: «заменить рассуждения вычислениями». Аппарат для этого начал возникать в трудах логиков XIX века, прежде всего английской школы – де Моргана, Буля, и американского логика Пирса. Но настоящее развитие математической логики пошло лишь в XX веке, когда математика доросла до того, чтобы применять свои методы для анализа своей собственной структуры. Появилась новая наука – математическая логика, унаследовавшая задачи философской логики, но использовавшая для их решения математический аппарат. Как сформулировал А. А. Марков: «Математическая логика – логика по предмету, математика по методу» [1].

Фрагмент работы для ознакомления

Это утверждение может быть справедливым, и тогда оно называется теоремой, обратной для теоремы X→Y, которая, в свою очередь, называется прямой теоремой. Если же утверждение не выполняется, то говорят, что обратная теорема для теоремы неверна. Таким образом, при доказательстве теоремы нужно четко выделять, каково ее условие и что доказывается. Доказательство прямой теоремы не дает оснований для вывода о том, что и обратная теорема также верна. Обратная теорема требует специальной проверки. Это обусловлено тем, что формулы X→Y и Y→X, выражающие структуры прямой и обратной теорем, не равносильны. Их неравносильность можно усмотреть также из таблиц истинности данных формул [5].Необходимое и достаточное условияС понятиями прямой и обратной теорем тесно связан вопрос о необходимых и достаточных условиях. Если некоторая математическая теорема имеет структуру, выражаемую формулой X→Y, то высказывание Y называется необходимым условием для высказывания X (другими словами, если X истинно, то Y с необходимостью должно быть также истинным), а высказывание X называется достаточным условием для высказывания Y (другими словами, для того чтобы Y было истинным, достаточно, чтобы истинным было высказывание X). Одно и то же утверждение может иметь несколько необходимых условий. Аналогично, одно и то же утверждение может иметь несколько достаточных условий. После того как доказана теорема X→Y, возникает вопрос, будет ли верно утверждение Y→X, называемое обратным по отношению к теореме X→Y [5].Если справедливы утверждения X→Y и Y→X, т. е. справедливо X↔Y, то считают, что X – необходимое и достаточное условие для Y, и, наоборот, что Y — необходимое и достаточное условие для X, или же что Y является критерием для X. Математическая наука изобилует утверждениями вида X→Y, представляющими собой необходимые и достаточные условия, и их приходится отыскивать в самых разных ее областях. Происходит это приблизительно следующим образом. Предположим, требуется найти необходимое и достаточное условие для некоторого утверждения X. Начинают с отыскания ряда необходимых условий для X, т.е. утверждений Y1,Y2,Y3,… ,следующих из X:X→Y1,X→Y2,X→Y3,…. При этом каждый раз пытаются анализировать, не окажется ли то или иное найденное условие или какая-либо их совокупность (конъюнкция) достаточным условием для X, т. е. окажется ли истинной какая-либо из импликаций [5]:Y1→X, Y2→X, Y3→X,Y1∧Y2→X, Y1∧Y3→X, Y2∧Y3→X, Y1∧Y2∧Y3→X,…Булева алгебраБулевой алгеброй называется непустое множество A с двумя бинарными операциями (дизъюнкция, конъюнкция), унарной операцией (инверсия) и двумя выделенными элементами: 0 (ложь) и 1 (истина) [4]. В булевой алгебре операции выполняются над высказываниями, представленными двоичными переменными. В результате получаются сложные высказывания. Эти сложные высказывания записываются в виде формул. Двоичная переменная в булевой алгебре определяется следующими аксиомами: A=1, если A≠0; A=0, если A≠1. Основные операции в булевой алгебре: дизъюнкция, конъюнкция, инверсия [3].Операция дизъюнкции обозначается знаком ∨. Вместо знака ∨ можно писать знак обычного арифметического сложения. Операция дизъюнкции определена следующими аксиомами: 0+0=0; 0+1=1; 1+0=1; 1+1=1 [3].Операция конъюнкция обозначается знаками: ⋅, ∧. Операция конъюнкции (логическое умножение) определяется следующими аксиомами: 0⋅0=0; 0⋅1=0; 1⋅0=0; 1⋅1=1 [3].Инверсия (отрицание) определяется аксиомами: 0=1; 1= 0.Свойства дизъюнкции и конъюнкции:A+B=B+A; A⋅B=B⋅A – коммутативность;(A+B)+C=A+(B+C), (A⋅B)⋅C = A⋅(B⋅C) – ассоциативностьA⋅(B+C)=A⋅B + A⋅C; A+B⋅C=A+BA+C – дистрибутивностьA+A=A; A⋅A=A – идемпотентностьДля дизъюнкции, конъюнкции и инверсии справедливы теоремы:А+0=А; А⋅0=0; А+1=1; А⋅1=А; А+А=А; А⋅А=А; А+А=1; А⋅А=0; А=АЕсли булева формула записана в виде дизъюнкции выражений, каждое из которых представляет собой либо отдельный аргумент (с инверсией или без инверсии), либо конъюнкцию некоторых аргументов, то эта формула является представленной в дизъюнктивной нормальной форме (ДНФ). Например, выражения A⋅B+C⋅D, A+B+C⋅D⋅E представлены ДНФ [3].Если булева формула записана в виде конъюнкции выражений, каждое из которых представляет собой либо отдельный аргумент (с инверсией или без инверсии), либо дизъюнкцию некоторых аргументов, то эта формула является представленной в конъюнктивной нормальной форме (КНФ). Например, выражения A+B⋅C+A+D, A⋅B⋅C+D+E представлены в КНФ [3].Законы де Моргана:A⋅B=A+B и A+B=A⋅BТеоремы поглощения:A+A⋅B=A, A⋅A+B=AТеоремы склеивания:A⋅B+A⋅B=A, A+B⋅A+B=AПеременная x называется булевой, если она способна принимать только два значения 0 и 1. Функция f(x1,x2,…,xn) называется булевой, если все ее аргументы xi являются булевыми, а сама функция также может принимать только два значения 0 и 1 [3].Способы задания булевой функции:Аналитический – в виде математического выражения с использованием букв и логических операций.Табличный – в таблице перечисляются все возможные наборы значений аргументов и для каждого набора указывается значение функции. Такую таблицу называют таблицей соответствия или таблицей истинности [3].Предикаты. Кванторы всеобщности и существованияПонятие предикатаЛогика предикатов – это расширение возможностей логики высказываний, позволяющее строить высказывания с учетом свойств изучаемых объектов или отношений между ними. Логика предикатов расчленяет элементарное высказывание на субъект и предикат [2]. Например, в высказывании «7 - простое число», «7» – субъект, «простое число» – предикат. Это высказывание утверждает, что «7» обладает свойством «быть простым числом» [2].Одноместным предикатом Px называется произвольная функция переменного x, определенная на множестве M и принимающая значения из множества 1,0 (истина, ложь). Область определения предиката Px – множество М, на котором определен предикат Px(множество М, из которого принимают значения переменные). Область истинности Ip – множество всех элементов x∈M, при которых предикат принимает значение истина Ip=xx∈M, Px=1 [2].Примеры одноместных предикатов:«»; область определения: x∈R; область истинности: -4. «х – столица Англии»; область определения: x∈Города; область истинности: Лондон.Двуместный предикат Px,y – функция двух переменных х и у (субъекты предиката), определенная на множестве M=M1×M2(x∈M1,y∈M2) и принимающая значения из множества 1,0.

Список литературы

Литература
1. Непейвода Н.Н. Прикладная логика/ Н.Н. Непейвода. – Изд. НГУ, 2000. – 494 с.
2. Шатурная О.С. Математическая логика и теория алгоритмов. Конспект лекций/ О.С. Шатурная – Саратов.: СГТУ, 2003. – 26 с.
3. Шевелёв Ю. П. Дискретная математика/ Ю. П. Шевелёв. – Томск, 2003. – 119 с.
4. Википедия. Интернет [электронный ресурс] – Режим доступа. – URL: http://ru.wikipedia.org/wiki
5. Математический форум Math Help Planet. Приложение алгебры высказываний к доказательству теорем. Интернет [электронный ресурс] – Режим доступа. – URL: http://mathhelpplanet.com
6. Каширин И. Теория автоматов. Интернет [электронный ресурс] – Режим доступа. – URL: http://teorya.hut.ru/page2.htm
7. Области применения математической логики. Интернет [электронный ресурс] – Режим доступа. – URL: http://ulfek.ru/
Очень похожие работы
Пожалуйста, внимательно изучайте содержание и фрагменты работы. Деньги за приобретённые готовые работы по причине несоответствия данной работы вашим требованиям или её уникальности не возвращаются.
* Категория работы носит оценочный характер в соответствии с качественными и количественными параметрами предоставляемого материала. Данный материал ни целиком, ни любая из его частей не является готовым научным трудом, выпускной квалификационной работой, научным докладом или иной работой, предусмотренной государственной системой научной аттестации или необходимой для прохождения промежуточной или итоговой аттестации. Данный материал представляет собой субъективный результат обработки, структурирования и форматирования собранной его автором информации и предназначен, прежде всего, для использования в качестве источника для самостоятельной подготовки работы указанной тематики.
bmt: 0.00379
© Рефератбанк, 2002 - 2024