Тема 3. Основы дискретной математики

 

Презентация-Основы логики и логические основы компьютера

 

Видеоурок 1.Базовые знания математической логики

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

Видеоурок 3.Решение логических выражений через построение таблиц истинности

Видеоурок 4.Основные законы математической логики

Видеоурок 5.Математическая логика.Пример решения задания

 

http://avt.miem.edu.ru/Dokuments/Eva/5lec.html (ссылка на развернутую лекцию)

http://www.studfiles.ru/dir/cat14/subj266/file9092/view94463.html (ссылка на развернутую лекцию)

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

1. Основные понятия теории множеств.

Определение. Множеством М называется объединение в единое целое определенных различимых однотипных объектов а, которые называются элементами множества.

а e М

Множество можно описать, указав какое-то свойство, присущее всем элементам этого множества.

Замечание. Вообще говоря, понятие множества считается первичным (исходным) понятием, и, как таковое, не определяется. Приведённое выше определение следует, скорее, считать уточнением понятия множества.

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

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

Мощностью конечного множества М называется количество его элементов. Обозначается n. Если, в каждом из множеств А и В содержится равное количество элементов, то множества А и В называются равномощными.

Определение. Если все элементы множества А являются также элементами множества В, то говорят, что множество А включается (содержится) в множестве В.

А

В

А e В

Определение. Если А e В, то множество А называется подмножеством множества В (также говорят, что В покрывает А).

Замечание. Не следует считать равносильными отношения принадлежности и вхождения одного множества в другое. Можно привести следующий пример. Пусть А — множество всех студентов данной группы, а В — множество всех учебных групп данного института. Здесь, но, поскольку элементы этих множеств разнородны. Этот пример показывает также, что элементами множеств могут являться другие множества.

Парадокс Рассела. Задание множеств характеристическим предикатом может привести к противоречиям. Рассмотрим множество всех множеств, не содержащих себя в качестве элемента:. Если такое множество существует, то можно ответить на следующий вопрос: принадлежит ли оно само себе. С одной стороны, если, то. С другой стороны, если, то! Это противоречие можно разрешить различными способами, в целом сводящимся к тому, что не является множеством.

Для трех множеств А, В, С справедливы следующие соотношения:

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

Здесь знак V либо & обозначает конъюнкцию (логическое “и”).

В заключение добавим, что Г. Кантор предложил использовать понятие “универсального множества” (универсум), как бы противоположного понятию пустого множества. По мысли Кантора, универсальное множество содержит все мыслимые множества, и при этом оно само содержится во множестве своих подмножеств в качестве элемента.

Функции, отношения и множества

Введем обозначения.

R – множество действительных чисел.

X e R – элемент X принадлежит множеству R.

Равные множества – множества, состоящие из одинаковых элементов.

A = B – множество А равно множеству B.

0 – пустое множество.

A<= C – Множество А является подмножеством множества С.

Если А не равно С и А <= C, то А < С. (строго).

Если A <= C и C <= А, то А = С.

Пустое множество 0 является подмножеством любого множества.

Существуют конечные и бесконечные множества. Пусть n – число элементов данного множества А. Это число называется мощностью данного множества.

У множества рациональных чисел мощность является счетной (т.е. все элементы можно пронумеровать).

У множества иррациональных чисел мощность – континиум. Обозначается (С).

Основное правило комбинаторики (показано на примере)

Пусть имеется палочка, разделенная на 3 части. Первую ее часть можно раскрасить n способами, вторую – m, третью – k. Всего способов раскраски палочки – n*m*k.

Аналогично с множествами U = {a1,a2… an-1, an}

Пусть U = {a1, a2, a3} Выпишем множество всех подмножеств множества U.

P(U) = {0, a1, a2, a3, a1a2, a1a3, a2a3, a1a2a3}. Мощность множества U равна 3, а мощность P(U) равна 8.

Методом математической индукции доказывается, что при произвольной мощности n множества U, мощность множества P(U) равна 2n.

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

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

Обозначается С = А U В.

Геометрическое изображение множеств в виде области на плоскости называется диаграммой Эйлера — Вэйна.

А

В

Геометрическое изображение множеств в виде области на плоскости называется диаграммой Эйлера — Вэйна.

 

 

Определение. Пересечением множеств А и В называется множество С, элементы которого принадлежат каждому из множеств А и В. Обозначение С = А ∩ В.

 

 

 

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

 

 

 

 

 

Дополнение множества А. (С = А) – не А. Все элементы, принадлежащие универсальному множеству, не принадлежат множеству А.

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

1. A U B = B U A – коммутативность. A n B = B n A

2. (A U B) U C = A U (B U C), A n (B n C) = (A n B) n C – ассоциативность.

3. (A U B) n C = (A n C) u (B n C), (AnB) U C = (A U C) n (B U C) – дистрибутивность.

4. Поглощение A U A = A, A n A = A.

5. Существование универсальных границ. А U 0 = A A n 0 = 0 A u U = U A n U = A

6. Двойное дополнение A = A

7. A U A = U A n A = 0

8. Законы двойственности или закон Де – Моргана (AUB) = A n B (AnB) = A U B

Логика

LOGOS ( греч.) - слово, понятие, рассуждение, разум.

Слово «логика» обозначает совокупность правил, которым подчиняется процесс мышления.

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

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

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

Умозаключение - прием мышления, посредством которого из исходного знания получается новое знание (все металлы - простые вещества).

Логика (формальная) - наука о законах и формах правильного мышления.

Математическая логика - изучает логические связи и отношения, лежащие в основе логического (дедуктивного) вывода.

Этапы развития логики

I. АРИСТОТЕЛЬ (384-322 гг. до н.э., древнегреческий философ) - основоположник логики.

Написал книги «Категории», «Первая аналитика», «Вторая аналитика».

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

Например:

1.Все млекопитающие имеют скелет. Все киты - млекопитающие. Следовательно, все киты имеют скелет.

2. Все квадраты - ромбы. Все ромбы - параллелограммы. Следовательно, все квадраты - параллелограммы.

Аристотель выделил все правильные формы силлогизмов, которые можно составить из рассуждений вида: «Все А суть В»; «Некоторые А суть В»; «Все А не суть В»; «Некоторые А не суть В».

Логика, основанная на теории силлогизмов называется классической.

II. Декарт Рене (1596-1650, французский философ, математик).Рекомендовал в логике использовать математические методы.

III. Лейбниц Г.В. (1646-1716, немецкий философ и математик) - предложил использовать в логике математическую символику и впервые высказал мысль о возможности применения в ней двоичной системы счисления. Ему принадлежит идея логического исчисления, то есть четко сформулированные правила действий со словами и предложениями, сродни арифметическим правилам действий с числами. В соответствии с этими правилами простые элементы логических рассуждений (понятия) обозначаются буквами, сложные элементы (предложения) – формулами, а умозаключения – уравнениями. «Единственное средство улучшить наши умозаключения – сделать их, как у математиков, наглядными, и если среди людей возникнет спор, нужно сказать «Посчитаем!»; тогда без особых формальностей можно будет увидеть, кто прав», - писал Лейбниц.

Лейбниц заложил идейный фундамент математической логики, а над практической реализацией этих идей работали и работают многие учёные.

IV. Джордж Буль (1815-1864, ирландский математик и логик) - основоположник математической логики. В 1847 г. Джордж Буль в работе «Математический анализ логики» изложил основы булевой алгебры. Разработал алфавит, орфографию и грамматику.

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

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