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

Размещено на http://www.allbest.ru/

Курсовая работа

по дисциплине: Информатика

на тему: Основы математической логики

Содержание

Введение

1. Основные понятия формальной логики

2. Логические выражения и логические операции

3. Построение таблиц истинности для логических функций

4. Логические функции и их преобразования. Законы логики

5. Логические функции и таблицы

5.1 Логическое умножение или конъюнкция

5.2 Логическое сложение или дизъюнкция

5.3 Логическое отрицание или инверсия

5.4 Логическое следование или импликация

5.5 Логическая равнозначность или эквивалентность

6. Сложение по модулю 2

6.1 Булева алгебра

6.2 Булева алгебра в программировании

6.3 Связь с естественным языком

Заключение

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

Введение

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

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

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

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

1. Основные понятия формальной логики

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

В логике используется специально созданный формализованный язык, подчиняющийся своей системе анализа. Можно считать, что логика ищет и исследует схемы рассуждений, которые верны в силу одной их формы, независимо от содержания?. Фактически, логика -- это множество правил манипулирования формулами, представляющими формы рассуждений с игнорированием их смысла.

Отвлечение от содержания предложений языка в формальной логике есть результат применения операции абстрагирования? к рассуждениям естественного языка. Абстрагирование является основным этапом при построении математической модели, оно широко используется в науке для выборочного исследования некоторых аспектов исследуемой проблемы. Цель абстрагирования -- выделение тех аспектов, которые существенны для исследования и решения проблемы и игнорирование тех аспектов, которые несущественны, усложняют проблему, делают анализ менее общим или вообще невозможным.

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

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

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

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

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

Логика изучает формы мышления и способы их выражения в языке.

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

Поэтому логику можно рассматривать как множество правил манипулирования формулами, описывающими утверждения естественного языка?. В результате конкретизации (интерпретации) результатов и выводов формальной логики (новых полученных формул) мы получаем новые предложения естественного языка, можем оценить свойства исходных предложений и т.д. Следует ясно понимать, однако, при каких ограничениях выводы, полученные с помощью формализма математической логики, мы можем использовать в реальной жизни -- тогда и только тогда когда выполнены ограничения, обеспечивающие адекватность модели.

2. Логические выражения и логические операции

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

Простым высказыванием называют повествовательное предложение, относительно которого имеет смысл говорить, истинно оно или ложно.

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

Примеры высказываний:

1. Москва - столица России.

2. Число 27 является простым.

3. Волга впадает в Каспийское море.

Высказывания 1 и 3 являются истинными. Высказывание 2 - ложным , потому что число 27 составное 27=3*3*3.

Следующие предложения высказываниями не являются:

· Давай пойдем гулять.

· 2*x>8.

· a*x2+b*x+c=0.

· Который час?

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

Примеры высказываний:

1. Сегодня светит солнце.

2. Трава растет.

Каждое из этих высказываний характеризует свойства или состояние конкретного объекта (в пермом предложении - погоды, во втором - окружающего мира). Каждое из этих высказываний несет значение «истина» или «ложь». В математической логике не рассматривается конкретное содержание высказывания, важно только, истинно но или ложно. Поэтому высказывание можно представить некоторой переменной величиной, значением которой может быть только 0 или 1. Если высказывание истинно, то его значение равно 1, если ложно - 0.

Простые высказывания назвали логическими переменными, а сложные - логическими функциями. Значения логической функции также только 0 или 1. Для простоты записи высказывания обозначаются латинскими буквами А, В, С.

Однако определение истинности высказывания далеко не простой вопрос. Например, высказывание «Число 1 +22 = 4294 967297 -- простое», принадлежащее Ферма (1601-1665), долгое время считалось истинным, пока в 1732 году Эйлер (1707-1783) не доказал, что оно ложно. В целом, обоснование истинности или ложности простых высказываний решается вне алгебры логики. Например, истинность или ложность высказывания «Сумма углов треугольника равна 180°» устанавливается геометрией, причем в геометрии Евклида это высказывание является истинным, а в геометрии Лобачевского -- ложным.

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

Существуют разные варианты обозначения истинности и ложности логических переменных:

Истина	И	True	T	1
Ложь	Л	False	F	0

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

С помощью логических переменных и символов логических операций любое высказывание можно формализовать, то есть заменить логической формулой (логическим выражением).

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

Связки "НЕ", "И", "ИЛИ" заменяются логическими операциями инверсия, конъюнкция, дизъюнкция. Это основные логические операции, при помощи которых можно записать любое логическое выражение.

Введем перечисленные логические операции.

Конъюнкция - логическое умножение (от латинского conjunctio - союз, связь):

с в естественном языке соответствует союзу «И»;

с в алгебре высказываний обозначение «&»;

с в языках программирования обозначение «And».

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

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

3. Построение таблиц истинности для логических функций

Логическая функция - это функция, в которой переменные принимают только два значения: логическая единица или логический ноль. Истинность или ложность сложных суждений представляет собой функцию истинности или ложности простых. Эту функцию называют булевой функцией суждений f (a, b).

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

Порядок выполнения логических операций в сложном логическом выражении:

1. инверсия;

2. конъюнкция;

3. дизъюнкция;

4. импликация;

5. эквивалентность.

Для изменения указанного порядка выполнения операций используются скобки.

Алгоритм построения таблиц истинности для сложных выражений:

1. Определить количество строк:

количество строк = 2n + строка для заголовка,

n - количество простых высказываний.

2. Определить количество столбцов:

количество столбцов = количество переменных + количество логических операций;

· определить количество переменных (простых выражений);

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

3. Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности с учетом таблиц истинности основных логических операций.

4. Логические функции и их преобразования. Законы логики

1. Закон двойного отрицания (двойное отрицание исключает отрицание):

2. А =

3. 4.1 Переместительный (коммутативный) закон:

a) для логического сложения: А Ъ B = B Ъ A;

b) для логического умножения: A & B = B & A.

Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.

4. Сочетательный (ассоциативный) закон:

a) для логического сложения: (А Ъ B) Ъ C = A Ъ (B Ъ C);

b) для логического умножения: (A & B) & C = A & (B & C).

При одинаковых знаках скобки можно ставить произвольно или вообще опускать.

5. Распределительный (дистрибутивный) закон:

a) для логического сложения: (А Ъ B) & C = (A & C) Ъ (B & C);

b) для логического умножения: (A & B) Ъ C = (A Ъ C) & (B Ъ C).

Закон определяет правило выноса общего высказывания за скобку.

6. Закон общей инверсии (законы де Моргана):

a) для логического сложения: = &;

b) для логического умножения: = Ъ

7. Закон идемпотентности (от латинских слов idem -- тот же самый и potens -- сильный; дословно -- равносильный):

a) для логического сложения: А Ъ A = A;

b) для логического умножения: A & A = A .

Закон означает отсутствие показателей степени.

8. Законы исключения констант:

a) для логического сложения: А Ъ 1 = 1, А Ъ 0 = A;

b) для логического умножения: A & 1 = A, A & 0 = 0.

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

a) A & = 0.

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

10. Закон исключения третьего:

a) A Ъ = 1.

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

11. Закон поглощения:

a) для логического сложения: А Ъ (A & B) = A;

a) для логического умножения: A & (A Ъ B) = A.

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

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

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

5. Логические функции и таблицы

5.1 Логическое умножение или конъюнкция

Конъюнкция - это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное сложеное выражение ложно.
Обозначение: F = A & B.

Таблица истинности для конъюнкции:

A	B	F
1	1	1
1	0	0
0	1	0
0	0	0

5.2 Логическое сложение или дизъюнкция

Дизъюнкция - это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно тогда и только тогда, когда оба простых логических выраженныя ложны.
Обозначение: F = A + B.

Таблица истинности для дизъюнкции

A	B	F
1	1	1
1	0	1
0	1	1
0	0	0

5.3 Логическое отрицание или инверсия

Инверсия - это сложное логическое выражение, если исходное логическое выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное логическое выражение ложно, то результат отрицания будет истинным. Другими простыми слова, данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО.

Таблица истинности для инверсии

A	неА
1	0
0	1

5.4 Логическое следование или импликация

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

Таблица истинности для импликации

A	B	F
1	1	1
1	0	0
0	1	1
0	0	1

5.5 Логическая равнозначность или эквивалентность

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

Таблица истинности для эквивалентности

A	B	F
1	1	1
1	0	0
0	1	0
0	0	1

Порядок выполнения логических операций в сложном логическом выражении.

1. Инверсия;

2. Конъюнкция;

3. Дизъюнкция;

4. Импликация;

5. Эквивалентность.

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

6. Сложение по модулю 2

Сложемние по модулю 2 -- булевская функция, которая соответствует логическому «исключающему ИЛИ». Это означает, что результат выполнения операции является истинным только при условии, если является истинным в точности один из аргументов. Такая операция естественным образом возникает в кольце вычетов по модулю 2, откуда и происходит название операции.

Сложение по модулю 2 следует отличать от простого сложения, которое соответствует обыкновенному «неисключающему ИЛИ».

В теории множеств сложению по модулю 2 соответствует операция симметричной разности двух множеств.

Обозначения

Запись может быть префиксной ("польская запись") - знак операции ставится перед операндами, инфиксной - знак операции ставится между операндами и постфиксной - знак операции ставится после операндов. При числе операндов более 2-х префиксная и постфиксная записи экономичнее инфиксной записи. Чаще всего встречаются следующие варианты записи:

^ a ? b, .

6.1 Булева алгебра

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

Таблицы истинности:

для бинарного сложения по модулю 2

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

Для тернарного сложения по модулю 2

X	Y	Z		?(X,Y,Z)
0	0	0		0
1	0	0		1
0	1	0		1
1	1	0		0
0	0	1		1
1	0	1		0
0	1	1		0
1	1	1		1

6.2 Программирование

В языках C/C++ (а также Java, C#, Ruby, PHP, JavaScript и т. д.) эта операция обозначается символом «^», в языках Паскаль,Delphi, Ada - зарезервированным словом XOR, в языке ассемблера - одноимённой логической командой. Сложение по модулю 2 выполняется для всех битов левого и правого операнда попарно. Например,

если
a =
b =
то
a ^ b =

Выполнение операции XOR для значений логического типа (true, false) производится в разных языках программирования по-разному. Например в Delphi используется встроенный оператор XOR (пример: condition1 xor condition2). В языке C, начиная со стандарта C99, оператор «^» над операндами логического типа возвращает результат применения операции XOR. В С++ оператор «^» для логического типа bool возвращает результат согласно описанным правилам, для остальных же типов производится его побитовое применение. Перегрузка для стандартных типов невозможна, но операцию XOR над ними можно реализовать, исходя из принципа "исключающего ИЛИ". Выглядит это так:

(condition1 || condition2) && (!condition1 || !condition2)

при этом нет разницы, применяются ли побитовые операторы & и |, или же логические && и ||)

6.3 Связь с естественным языком

В естественном языке операция "сложение по модулю 2" эквивалентна двум выражениям:

1. "результат истинен (равен 1), если A не равно B (A?B)";

2. "если A не равно B (A?B), то истина (1)".

Часто указывают на сходство между сложением по модулю 2 и конструкцией «либо … либо …» в естественном языке. Составное утверждение «либо A, либо B» считается истинным, когда истинно либо A, либо B, но не оба сразу; в противном случае составное утверждение ложно. Это в точности соответствует определению операции в булевой алгебре, если «истину» обозначать как 1, а «ложь» как 0.

Эту операцию нередко сравнивают с дизъюнкцией потому, что они очень похожи по свойствам, и обе имеют сходство с союзом «или» в повседневной речи. Сравните правила для этих операций:

1. истинно, если истинно или , или оба сразу.

2. истинно, если истинно или , но не оба сразу.

Операция исключает последний вариант («оба сразу») и по этой причине называется исключающим «ИЛИ». Операция включает последний вариант («оба сразу») и по этой причине иногда называется включающим «ИЛИ». Неоднозначностьестественного языка заключается в том, что союз «или» может применяться в обоих случаях.

Заключение

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

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

1. Айзерман М.А., Гусев Л.А., Розоноэр Л.И., Смирнова И.М., Таль А.А. Логика, автоматы, алгоритмы. М.: ГИФМЛ, 2010

2. Гудстейн Р.Л. Математическая логика. М.: ИЛ, 2014

3. Фрейденталь X. Язык логики. М.: Наука, 2008

Размещено на Allbest.ru

...