Дискретная математика и ее роль в жизни человека

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

Департамент образования и науки Кемеровской области

Государственное бюджетное образовательное учреждение

среднего профессионального образования

«Прокопьевский промышленно - экономический техникум»

РЕФЕРАТ

По дисциплине: «Дискретная математика»

на тему: «Дискретная математика и ее роль в жизни человека»

Выполнил:

студент 3 курса, гр. КСК-13

Литвинович Михаил Геннадьевич

Проверила:

Скоробогатая О.В.

г. Прокопьевск

2015



Содержание

Введение

1. Множества

1.1 Множества, операции над множествами

1.1.1 Основные определения

1.1.2 Сравнение множеств

1.1.3 Операции над множествами

1.1.4 Свойства операций над множествами

1.2 Отношения

1.2.1 Упорядоченные пары

1.2.2 Прямое произведение множеств

2. Комбинаторика

2.1 Основные законы комбинаторики

2.1.1 Правило суммы

2.1.2 Правило произведения

2.2 Формулы комбинаторики

2.2.1 Перестановки

2.2.2 Размещения

2.2.3 Сочетания

3. Логика высказываний

3.1 Введение

3.2 Основные понятия

3.3 Логические операции

3.4 Составные высказывания

3.5 Формулы логики высказываний

3.6 Законы логики (свойства логических операций)

Заключение

Список использованной литературы



Введение

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

Дискретная (конечная) математика - это раздел математики, не связанный с понятиями предела, непрерывности и бесконечности.

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

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

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

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

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

Стремление к строгости математических рассуждений и анализ рабочего инструмента математики - логики привели к выделению ещё одного важного раздела математики - математической логики (19-20 вв.). Однако наибольшего развития Д. м. достигла в связи с запросами практики, приведшими к появлению новой науки - кибернетики и её теоретической части - математической кибернетики (20 в.).

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

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

Так, прикладные вопросы, требующие большой числовой обработки, стимулировали появление сильных численных методов решения задач, оформившихся затем в вычислительную математику, а анализ понятий "вычислимость" и "алгоритм" привёл к созданию важного раздела математической логики - теории алгоритмов. Растущий поток информации и связанные с ним задачи хранения, обработки и передачи информации привели к возникновению теории кодирования; экономические задачи, задачи электротехники, равно как и внутренние задачи математики, потребовали разработки теории графов; задачи конструирования и описания работы сложных управляющих систем составили теорию функциональных систем и т. д. В то же время математическая кибернетика широко использует результаты Д. м. при решении своих задач.



1. Множества

1.1 Множества, операции над множествами

1.1.1 Основные определения

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

Понятие множество принадлежит к числу фундаментальных неопределяемых понятий математики.

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

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

q должно существовать правило, позволяющее определить, принадлежит ли некоторый элемент множеству;

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

Множества обычно обозначают большими латинскими буквами (например, A, S, D), а их элементы - строчными (например, a, s, d).

Если элемент х принадлежит множеству А, то это обозначается: хА; в противном случае говорят, что элемент не принадлежит множеству, это обозначается: хА.

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

1. Множество N - множество натуральных чисел. 1N. -1N.

2. Множество L - множество букв русского алфавита. фL. vL.

Множество не содержащие элементов называется пустым. Это множество обозначается .

Множества можно задавать следующими способами.

1. Перечисление элементов:

P={точка, прямая, плоскость, тело}, S={0,1,2}.

2. Задание характеристического свойства:

L={n|nN и n<7}.

1.1.2 Сравнение множеств

Множество А содержится во множестве В (множество В включает множество А, множество А является подмножеством В), если каждый элемент множества А является элементом множества В. Обозначение: АВ.

АВ хА хВ.

Два множества называются равными, если они являются подмножествами друг друга. Обозначение: А=В.

А=В АВ и ВА.

Если непустое множество А является подмножеством В и множества А и В не являются равными, то А является собственным подмножеством В.

Пример:

М={4, 6, 8, 10}, К={6, 8}; КМ, МК, МК,

К - собственное подмножество М.

Для множеств существует понятие мощность. Для конечных множеств мощность совпадает с количеством элементов.

Пример:

||=0, |{}|=1, |{1, 2, 3, 4}|=4.

1.1.3 Операции над множествами

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

АВ={x| хА или хВ}.

Пересечение двух множеств А и В - это новое множество, элементами которого являются элементы, принадлежащие множеству А и множеству В. Обозначение: АВ.

АВ={x| хА и хВ}.

Разность двух множеств А и В - это новое множество, элементами которого являются элементы, принадлежащие множеству А и не принадлежащие множеству В. Обозначение: А \ В.

А \ В={x| хА и хВ}.

Обычно элементы множеств выбираются из некоторого достаточно широкого множества U, которое называется универсум. В связи с этим понятием можно ввести операцию дополнение.

Дополнением множества А называется множества, которое состоит из элементов универсума, не принадлежащих множеству А. Обозначение: .

=U \ A

Или

={x| хА и хU}.

Пример:

U={1, 2, 3, 4, 5, 6, 7}, A={1, 2, 3, 4, 5}, В={2, 4, 6}.

АВ = {1, 2, 3, 4, 5, 6} АВ = {2, 4} А \ В = {1, 3, 5}

В \ А = {6} = {6, 7} = {1, 3, 5, 7}

1.1.4 Свойства операций над множествами

1. Идемпотентность пересечения, объединения.

АА = А АА = А

2. Коммутативность пересечения, объединения.

АВ = ВА АВ = ВА

3. Ассоциативность пересечения, объединения.

(АВ) С = А (В С) (АВ) С = А (В С)

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

(АВ) А = А (АВ) A = А

5. Свойства пустого множества.

А = А = А

6. Свойства универсума.

А U = A АU = U

7. Инволютивность.

= А

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

9. Свойства дополнения.

А = А = U

10. Выражения для разности.

А \ В = А

1.2 Отношения

1.2.1 Упорядоченные пары

Если a и b - объекты, то через (a,b) обозначим упорядоченную пару. Равенство упорядоченных пар определяется следующим образом:

(a, b) = (c, d) a=с и b=d.

Т. е.

(a, b) (b, a),

Если

ab.

Пример:

(3,4) (4,3).

1.2.2 Прямое произведение множеств

Пусть A и B - два множества. Прямым (декартовым) произведением двух множеств A и B называется множество упорядоченных пар, в котором первый элемент каждой пары принадлежит A, а второй принадлежит B.

AB = {(a, b) | aA, bB}.

Пример: точка на плоскости может быть задана упорядоченной парой координат, т.е. двумя точками на координатных осях. Т.о.,

R² = RR.

Метод координат ввел в употребление Рене Декарт (1596 - 1650), отсюда и название - «декартово произведение».

Степенью множества А называется его прямое произведение самого на себя.

Aⁿ =

Соответственно,

A¹ = A, A² = AA

и вообще

Aⁿ = AA^n-1.

Теорема:

|AB| = |A| |B|.

Доказательство: первый компонент упорядоченной пары можно выбрать |А| способами, второй - |B| способами. Таким образом, всего имеется |A| |B| различных упорядоченных пар.

Следствие:

|Aⁿ| = |A|ⁿ.



2. Комбинаторика

Введение

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

Рассмотрим элементарный жизненный пример.

Пусть некоторое агентство недвижимости располагает базой данных из n записей, каждая запись содержит одно предложение (что имеется) и один запрос (что требуется). Требуется найти все такие пары записей, в которых предложение первой записи совпадает с запросом второй (осуществить подбор вариантов обмена). Допустим, что используемая СУБД позволяет проверить вариант за одну миллисекунду. При «лобовом» алгоритме поиска вариантов (каждая запись сравнивается с каждой) потребуется n(n-1)/2 сравнений. Если n=100, то ответ будет получен через 4,95 секунд; но если n=100000, то ответ будет получен за 4 999 950 секунд, что составляет почти 1389 часов и вряд ли это может считаться приемлемым. При этом мы оценили только трудоемкость прямых вариантов, но есть варианты, когда число участников сделки больше двух …

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

2.1 Основные законы комбинаторики

2.1.1 Правило суммы

Задача: на блюде лежат 5 яблок и 2 груши. Сколькими способами можно выбрать один плод?

Решение: плод можно выбрать семью способами (5+2=7).

Если некоторый элемент a может быть выбран из множества элементов m способами, а другой элемент b может быть выбран n способами, причем любой выбор элемента b отличен от любого выбора элемента a, то выбрать либо a, либо b можно m + n способами.

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

Теорема 1: если пересечение конечных множеств пусто, то число элементов в их объединении равно сумме чисел элементов множеств А и В.

АВ = | АВ | = |A| + |B|

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

Теорема 2: для любых конечных множеств верно равенство:

| АВ | = |A| + |B| - | АВ |.

Задача: среди студентов первого курса 30 человек имеют дома компьютер, 35 - учебник по информатике; оказалось, что 10 студентов имеют и компьютер, и учебник по информатике. Сколько студентов на первом курсе?

Решение: пусть множество А составляют студенты, имеющие компьютер, множество В - студенты, имеющие учебник по информатике; по условию задачи:

|A| = 30 |B| = 35 | АВ | = 10 | АВ | =?

| АВ | = |A| + |B| - | АВ | = 30 + 35 - 10 = 55.



2.1.2 Правило произведения

Вторым основным правилом комбинаторики является правило произведения.

Задача: определить количество клеток в игре «морской бой», если номер клетки состоит из буквы (букв 10) и цифры (цифр тоже 10).

Решение: количество клеток равно

10*10=100.

Если элемент a можно выбрать из множества элементов m способами и после каждого такого выбора элемент b можно выбрать n способами, то два элемента (упорядоченную пару) a и b можно выбрать m*n способами.

На языке множеств это правило выражается в виде следующей теоремы.

Теорема3: если множества А и В конечны, то

|AB| = |A| * |B|.

Следствие: если множества А₁, А₂, …, А_n - конечны, то

|A₁…А_n| = |A₁|* … *|A_n|.

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

Решение: обозначим множество букв А, множество цифр - В; каждый номер требуемого вида является набором длины n из декартова произведения ААВВВ; по условию |А| = 29, |В| = 10, тогда по следствию из теоремы3 имеем:

| ААВВВ | = 29*29*10*10*10 = 841 000.

2.2 Формулы комбинаторики

2.2.1 Перестановки

1) Перестановки без повторений.

Перестановки - это комбинации, состоящие из одних и тех же элементов и отличающиеся только порядком расположения этих элементов. Возьмем n различных элементов a₁, a₂, a₃, … a_n; будем переставлять эти элементы всевозможными способами, оставляя без изменения число элементов и меняя только порядок их расположения. Обозначим общее число полученных таким образом перестановок P(n). P - первая буква французского слова permutation - перестановка.

Составив таблицу перестановок для n элементов и применив (n - 1) раз правило произведения, получим число всех возможных перестановок:

P(n) = n * (n -1) * (n - 2) * … * 3 * 2 * 1 = n!

Такие перестановки называются перестановками без повторений (один и тот же элемент не может повториться в комбинации, все элементы различны).

Задача: шесть человек могут в разном порядке сесть за круглый стол, сколько существует способов разместить эти шесть человек за столом?

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

Р(6) = 6! = 1 * 2 * 3 * 4 * 5 * 6 = 720.

2) Перестановки с повторениями

Рассматривая различные перестановки, мы предполагали, что все n элементов различны. Если же некоторые элементы повторяются, то в этом случае комбинации с повторениями вычисляют по другим формулам.

Если среди n элементов есть n₁ элементов одного вида, n₂ элементов другого вида и т.д., n_k элементов к-го вида, то имеем перестановки с повторениями, их число:

,

Где

n₁+…+n_k = n.

Задача: сколько различных «слов» можно составить из букв слова ДЕД, МАТЕМАТИКА.

Решение: имеем перестановки с повторениями.

А) ДЕД n=3, k=2, n₁=2, n₂=1

P₃(2, 1) = 3!/(2! * 1!) = 6 / 2 = 3;

Б) МАТЕМАТИКА n=10, k=6, n₁=2, n₂=3, n₃=2, n₄=n₅=n₆=1

P₁₀(2,3,2,1,1,1)=10!/(2! * 3! * 2!)=2*4*5*6*7*9*10 = 134 400.

2.2.2 Размещения

1) Размещения без повторений.

Размещениями называют комбинации, составленные из n данных элементов по k элементов (k<=n, k>0), которые отличаются либо составом элементов, либо порядком расположения элементов. Обозначаются размещения A_n^k . А - первая буква французского слова arrangement, что в переводе означает "размещение", "приведение в порядок". Число всех возможных размещений находится по формуле:

.

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

Решение: имеем размещения без повторений из пяти элементов по два, из число:

.

2) Размещения с повторениями.

Пусть существуют n различных элементов. Выберем из них m штук, действуя по следующему принципу: возьмем любой элемент, но не будем устанавливать его в какой-либо ряд, а просто запишем под номером 1 его название, сам же элемент вернем к остальным элементам. Затем опять из всех n элементов выберем один, запишем его название под номером 2 и снова вернем элемент обратно. Будем выполнять эти операции, пока не получим m названий. Размещения с повторениями вычисляются по формуле:

.

Задача: сколько четырехзначных номеров можно составить из 10 цифр?

Решение: имеем размещения с повторениями из 10 элементов по 4, их число:

.

множество комбинаторика логика

2.2.3 Сочетания

1) Сочетания без повторений.

Сочетаниями называют комбинации, составленные из n различных элементов по k (k =< n) элементов, которые отличаются хотя бы одним элементом. Сочетания обозначаются: C_n^k C - первая буква французского слова combinasion - сочетание.

Составим из n элементов всевозможные сочетания по k элементов в каждом. Их будет C_n^k . Внутри каждого сочетания, состоящего из k элементов, образуем всевозможные комбинации, учитывающие порядок следования в них элементов. Таких комбинаций будет P_k, т.к. мы в нашем сочетании образовываем перестановки. Всего различных комбинаций из n элементов по k в каждой, отличающихся друг от друга либо составом (элементами), либо порядком их следования, будет C_n^k * P_k . Но такие комбинации называются размещениями. Таким образом,

A_n^k = C_n^k * P_k,

тогда:

.

Задача: в шахматном турнире участвует 7 человек; сколько партий будет сыграно, если между любыми двумя участниками должна быть сыграна партия?

Решение: имеем сочетания без повторений из 7 элементов по 2; их число:

.

2) Сочетания с повторениями.

Если в сочетаниях некоторые элементы (или все) могут оказаться одинаковыми, то такие сочетания называются сочетаниями с повторениями. Их число определяется по формуле:

.

Задача: сколько наборов из 7 пирожных можно составить, если в продаже имеется 4 сорта пирожных?

Решение: имеем сочетания с повторениями из четырех по 7 по, их число:

.



3. Логика высказываний

3.1 Введение

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

Алгебра логики возникла в середине 19 в. в трудах Дж. Буля и развивалась затем в работах Ч. Пирса, П. С. Порецкого, Б. Рассела, Д. Гильберта и др. Создание алгебры логики представляло собой попытку решать традиционные логические задачи алгебраическими методами.

С появлением теории множеств (70-е гг. 19 в.), поглотившей часть первоначального предмета алгебры логики, и дальнейшим развитием математической логики (последняя четверть 19 в. - 1-я половина 20 в.) предмет алгебры логики значительно изменился. Основным предметом алгебры логики стали высказывания.

3.2 Основные понятия

В формально-логических выводах используются истинные и ложные предложения.

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

Примеры высказываний: "кит - животное", "все углы - прямые" и т. п. Первое из этих высказываний является, очевидно, истинным, а второе - ложным. Предложение "реши задачу", также как и "2+2", не является высказываем.

Определения математических понятий не являются высказываниями, т.к. это принятые соглашения.

Будем обозначать высказывания большими латинскими буквами: A, B, C,….

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

3.3 Логические операции

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

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

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

Рассмотрим определения логических операций, соответствующих логическим связкам.

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

Истинностное значение сложных высказываний зависит от истинностных значений высказываний, составлявших слоеное высказывание.

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

Пусть A, В - произвольные высказывания, относительно которых не предполагается, что известно их истинностные значения.

Связке "НЕ" соответствует логическая операция отрицания, обозначение операции - знак щ или .

Определение. Отрицанием высказывания A называется высказывание (щA), которое истинно, если A - ложно, и ложно, если A - истинно.

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

A
И	Л
Л	И

Пример:

A: 2*2=4

- истинное высказывание;

:

Или

2*24

- ложное высказывание.

Связке "И" соответствует операция конъюнкция, обозначение операции - знак (или &).

Определение. Конъюнкцией высказываний A и B называется высказывание AB (читается "A и B"), которое истинно тогда и только тогда, когда A, B - истинно.

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

A	B	AB
И	И	И
И	Л	Л
Л	И	Л
Л	Л	Л

Пример: A: 5 - нечетное число; B: Пушкин родился в 1799 г - истинные высказывания; поэтому высказывание AB: 5 - нечетное число Пушкин родился в1799 г. - истинное высказывание.

Связке "ИЛИ" соответствует операция дизъюнкция, обозначение операции - знак .

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

Определение. Дизъюнкцией высказываний A и B называется высказывание AB (читается "A или B"), которое ложно тогда и только тогда, когда A, B - ложны.

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

A	B	AB
И	И	И
И	Л	И
Л	И	И
Л	Л	Л

Пример. A: 7<10, и.в. В: 3 - число четное, л.в. AB: 7<10 3 - число четное, и.в.

Связке "ЕСЛИ....ТО" соответствует логическая операция импликация, обозначение операции знак >.

Определение. Импликацией высказываний A и B называется высказывание A>B (читается "если A, то B"), которое ложно тогда и только тогда, когда A - истинно, а B - ложно.



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

A	B	A>B
И	И	И
И	Л	Л
Л	И	И
Л	Л	И

Пример.

A: 2*2=5, л. в.

В: 2=2, и. в.

A>B: 2*2=5> 2=2. и. в.

Высказывание A называется условием или посылкой, высказывание В - заключением или следствием импликации.

Связке "ТОГДА И ТОЛЬКО ТОГДА, КОГДА" соответствует операция эквиваленция, обозначение операция - знак «.

Определение. Эквиваленцией высказываний A и В навивается высказывание, обозначаемое A«B (читается :"A тогда и только тогда, когда В" или короче: "A эквивалентно В"), которое считается истинным только тогда, когда оба высказывания A и В имеют одинаковое истинностное значение.

Эквивалентность А«В читается также следующим образом: "Для того, чтобы A, необходимо и достаточно, чтобы В".

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

A	B	A«B
И	И	И
И	Л	Л
Л	И	Л
Л	Л	И

Пример. A: 7 - число простое; и.в. В: в равнобедренном треугольнике при основании углы равны, и.в. A«В - и.в.

3.4 Составные высказывания

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

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

Пример

.

A	B	C
И	И	И	И	Л	И
И	И	Л	И	Л	Л
И	Л	И	Л	И	И
И	Л	Л	Л	И	И
Л	И	И	Л	И	И
Л	И	Л	Л	И	И
Л	Л	И	Л	И	И
Л	Л	Л	Л	И	И

3.5 Формулы логики высказываний

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

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

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

1. Элементарные формулы - атомы - являются формулами логики высказываний.

2. Если A, B - формулы, то , (AB), (AB), (A>B), (A«В) также являются формулами логики высказываний.

3. только те выражения являются формулами логики высказываний, для которых это следует из 1, 2.

Согласно определения, всякая формула либо атом, либо образуется из атомов в результате применения 2.

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

Знак « имеет самую большую область действия, знак самую маленькую.

Определение. Формулы логики, принимающие значение "истина" при любых значениях атомов, входящих в формулу, называется тождественно истинными (или законами логики, или тавтологиями).

Например, формула всегда тождественно истинна.

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

Например, формула - противоречие.

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

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

Определение. Формулы Р и Q называются равносильными, если их истинностные значения совпадают при любом выборе истинностных значений атомов, входящих в эти формулы.

Запись

множество комбинаторика логика

РQ

означает, что формулы Р и Q равносильны.

3.6 Законы логики (свойства логических операций)

Следующие формулы являются законами логики.

1.

- закон двойного отрицания.

2.

- закон коммутативности конъюнкции.

3.

- закон коммутативности дизъюнкции.

4.

- закон ассоциативности конъюнкции.

5.

- закон ассоциативности дизъюнкции.

6.

- закон дистрибутивности конъюнкции относительно дизъюнкции.

7.

- закон дистрибутивности дизъюнкции относительно конъюнкции.

8.

- закон отрицания дизъюнкции.

9.

- закон отрицания конъюнкции.

10.

- закон отрицания импликации.

11.

- закон выражения эквивалентности через конъюнкцию и импликацию.

12.

- закон контрапозиции.

13.

- закон силлогизма.

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

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

2. Построить значение всей формулы и убедится, что формула является тавтологией.

A	B	A®B		A®
И	И	И	Л	Л	Л
И	Л	Л	И	И	Л
Л	И	И	Л	И	И
Л	Л	И	И	И	И

Пример. Докажем закон отрицания конъюнкции () этими способами:

1. Найдем значения для и и сравним их.

A	B
И	И	И	Л	Л	Л	Л
И	Л	Л	И	Л	И	И
Л	И	Л	И	И	Л	И
Л	Л	Л	И	И	И	И

2. Найдем значение и убедимся, что при всех значениях A и B - это истинное значение

A	B
И	И	И	Л	Л	Л	Л	И
И	Л	Л	И	Л	И	И	И
Л	И	Л	И	И	Л	И	И
Л	Л	Л	И	И	И	И	И



Заключение

В XXI веке дискретная математика является бурно развивающейся ветвью математики. Ее роль и место определяются в основном тремя факторами:

1) дискретную математику можно рассматривать как теоретические основы компьютерной математики

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

3) язык дискретной математики чрезвычайно удобен и стал фактически метаязыком всей современной математики.

В настоящее время знание дискретной математики необходимо специалистам в различных областях деятельности и элементы дискретной математики все чаще вводят в программы подготовки не только математиков, инженеров, программистов, но даже юристов. Интерес к этой дисциплине не случаен, т.к. потребность в знаниях этой области математики объясняется широким кругом ее применения: электроника и информатика, вопросы оптимизации и принятия решений. XXI в. называют веком информатизации, когда основной объем информации хранится в памяти ЭВМ. Применение ЭВМ для комплексной автоматизации информационной деятельности принципиально изменило характер взаимоотношений человека и машины. Если раньше компьютер осваивали только те, кто непосредственно его обслуживал: программисты, электронщики, операторы, то в XXI в. без машинной обработки информации не обойдется ни одна отрасль деятельности.



Список использованной литературы

1. Курс «Дискретная математика» http://any-book.org/download/11058.html

2. Мельников О.И. Обучение дискретной математике. - М. : Издательство ЛКИ, 2008. - 224с.

3. Фирсова Е. В. История развития дискретной математики и ее роль в обучении информатиков - экономистов [Текст] / Е. В. Фирсова // Молодой ученый. -- 2012. -- №2. -- С. 304-311.

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

...