Лекции по дискретной математике
скачать (389.4 kb.)
Доступные файлы (8):
desktop.ini | |||
Folder.htt | |||
Раздел 1 Логика.doc | 601kb. | 18.08.2002 15:14 | ![]() |
Раздел 2 теория множеств.doc | 384kb. | 03.09.2001 22:42 | ![]() |
Раздел 3 Теория графов.doc | 272kb. | 28.02.2002 20:24 | ![]() |
Раздел 4 Логика предикатов.doc | 156kb. | 10.06.2002 21:25 | ![]() |
Раздел 5 Теория простейших автоматов.doc | 313kb. | 28.03.2002 21:18 | ![]() |
Раздел 6 Комбинаторика.doc | 141kb. | 15.05.2002 22:05 | ![]() |
содержание
Загрузка...
- Смотрите также:
- по дискретной математике [ лекция ]
- по дискретной математике [ лекция ]
- по дискретной математике [ лекция ]
- по дискретной математике [ лекция ]
- по дискретной математике часть2 [ лекция ]
- по дискретной математике [ лекция ]
- по дискретной математике. Часть 1 [ лекция ]
- по дискретной математике [ лекция ]
- по дискретной математике [ лекция ]
- по дискретной математике [ лекция ]
- по дискретной математике [ лекция ]
- по дискретной математике [ лекция ]
Раздел 1 Логика.doc
Реклама MarketGid:
Загрузка...
Раздел 1. Булева алгебра
Тема 1.1. Понятие системы исчисления по любому основанию, двоичная система.
Под системой счисления будем понимать правила записи натуральных чисел. Для записи чисел мы пользуемся десятичной позиционной системой. В каждой системе счисления некоторые символы служат для обозначения некоторых чисел, эти знаки называются узловыми. В нашей системе счисления узловыми являются цифры от 0 до 9. В древнеримской системе счисления узловыми являются числа 1, 5, 10, 50, 100, 500, 1000: I, V, Х, L, C, D, M.
Если значение числового знака зависит от его расположения в записи числа, то система называется позиционной. Из истории математики известны системы счисления основанием, которых были числа, отличные от десяти. Например, у древних вавилонян узловыми являлись числа 1, 10, 60. У мойри (коренные жители Новой Зеландии) была принята 11-ричная система счисления. С применением некоторых этих систем счисления мы встречаемся и по сей день. Например, календарь – 12-ричная система счисления. Сутки делятся на 24 часа.
Введем понятие n-ричной системы счисления. Это система счисления, в которой любое число представимо в виде:

и для всех чисел от 0 до n-1 ставится в соответствие n различных знаков – цифр.
В ЭВМ применяется двоичная система счисления ее цифры {0,1}. Это связано с особенностями хранения данных в ЭВМ. Для кодирования часто применяется 16-ричная система счисления, ее цифры 0-9, A,B,C,D,E,F.
Способ перекодирования рассмотрим на примере двоичной системы.

2710 = 110112
Обратный переход:
1*16+1*8+0*4+1*2+1=16+8+2+1=2710
В дальнейшем, рассматривая двоичную систему счисления, мы будем пользоваться несколькими обозначениями, в зависимости от удобства в контексте. Возможные значения {0; 1}, {И, Л}, {TRUE, FALSE}, {Да, Нет}, {«Включено», «Выключено»} говоря об истинном или ложном значении выражения.
^
Каждая математическая дисциплина имеет свою собственную область объектов, которую она изучает. Например, геометрия изучает геометрические фигуры, математический анализ изучает функции, арифметика – числа. Основным объектом изучения алгебры высказываний, алгебры логики или Булевой алгебры являются высказывания.
Мы будем понимать под высказыванием такое утверждение, о котором можно сказать истинно оно или ложно. Когда суждение, являющееся содержанием какого-либо высказывания, истинно, то и высказывание истинно, и наоборот, если суждение ложно, то и высказывание ложно. В традиционном исчислении высказываний исследуются высказывания, которые или истинно или ложно, и ни одно высказывание не может быть истинным и ложным одновременно.
Например: 20 > 5
Москва – столица России
Берлин – один из крупнейших городов Франции
Сколько Вам лет? – это не высказывание.
Любое высказывание будем рассматривать с точки зрения их истинности или ложности (их логического значения, пренебрегая их житейским смыслом, всеми нюансами мысли, характерными для обычной устно или письменной речи).
В логике высказываний применяется искусственный язык, с помощью которого обозначаются высказывания, формулируются законы логики данной дисциплины и частные правила действий с высказываниями. Каждое высказывание мы будем обозначать заглавными латинскими буквами, и определим формальные правила обращения с высказываниями. Считая, что если А = 0 , то высказывание ложно и наоборот. Однозначность построения формул и определения порядка действий будем достигать использованием скобок () – это технические знаки.
Высказывание, обозначенное с помощью одной какой-либо буквой латинского алфавита, будем называть элементарным или атомарным высказыванием. Оно рассматривается как неразложимая единица, т.е. никакое другое высказывание не входит в него в качестве его части.
Единственное свойство элементарного высказывания, изучаемое в алгебре логики, является его истинностное значение. Никакого другого, конкретного содержания элементарное высказывание не имеет.
Заметим, что выражения типа «В том году был хороший урожай хлебов» и «Целое число n является простым» не могут считаться высказываниями, поскольку о них нельзя сказать истинны они или ложны. Дело в том, что такие выражения включают в свой состав переменную («том» и «n») и лишь в зависимости от значения этой переменной они превратятся в истинное или ложное утверждение, и только после этого станут высказываниями. Такие выражения называются пропозициональными переменными.
Основоположником формальной логики считается древнегреческий философ Аристотель, впервые разработавший теорию дедукции. Ему принадлежит открытие формального характера логического вывода, состоящего в том, что в наших рассуждениях одни предложения выводятся из других в силу определенной связи между их формой и структурой, независимо от конкретного содержания. Вторым витком развития логики стали работы ирландского математика Джорджа Буля (1815 – 1864), работавшего в университете города Корк, отца писательницы Этель Лилиан Войнич. С именем Буля связана революция в логике, она приобрела письменность, появился новый тип алгебры. Другие имена, связанные с этой теорией: Раймундо Луллий (испанский философ, монах–отшельник 12–13 вв), Б. Спиноза, Н. Винер.
^
Из элементарных высказываний можно составлять сложные высказывания с помощью логических операций. Чтобы уметь однозначно выявить истинное значение сложных высказываний, строго определим логические операции. Единственное свойство сложного высказывания, которое нас интересует, это его истинностное значение. Никакого другого, конкретного содержания сложное высказывание не имеет. Элементарные высказывания, входящие в состав сложного высказывания, связываются логическими операторами не по смысловому описанию, а только по их истинностным значениям. Следовательно, сложные высказывания являются функциями от входящих в них элементарных высказываний. Все операции в логике высказываний описываются только таблицей истинности. Все языковые конструкции, которые мы будем использовать для описания той или иной операции, не более чем средство запоминания. Дадим более строгое определение
Функция

1. Отрицание.
Определим унарную логическую операцию – отрицание. Для этой операции таблица истинности выглядит следующим образом:
-
Иллюстрацией отрицания в естественном языке служит частица "не", или слова "неверно, что".
Например: если мы хотим отрицать, что
Точка М принадлежит прямой а (1)
Мы скажем
Точка М не принадлежит прямой а (2)
Если (1) – это высказывание


Обратите внимание, что истинностные значения высказываний (1) и (2) находятся в определенной зависимости: если (1) – истинно, то (2) – ложно.
Если (1) – ложно, то (2) – истинно.
Например, покажем, что

-
Это одно из свойств Булевой алгебры. Следует отметить, что отрицание составных формул не такая уж тривиальная операция. Чуть позднее мы проиллюстрируем это утверждение.
2. Конъюнкция
Введем еще одну логическую операцию, определив её словесно следующим образом. Конъюнкция двух высказываний истинна тогда и только тогда, когда оба высказывания истинны. Эту логическую операцию называется еще логическим умножением, или логическим минимумом. Выпишем таблицу истинности для конъюнкции
-
Свойства конъюнкции:




В естественном языке эта операция чаще всего интерпретируется союзом "и"
Пример: Выведем формулу счастливой любви по Шекспиру. Для этого проанализируем следующие строки:
Увы, я никогда не слышал
И не читал – в истории ли, в сказке
Чтоб гладким был пут истинной любви.
Но или разница в происхождении
О горе, высшему – плениться низшей.
Или различье в летах
О, насмешка!
Быть слишком старым для невесты юной
Иль выбор близких и друзей
О, мука! Но как любить по выбору чужому?
А если выбор всем хорош – война,
Болезнь иль смерть всегда грозят любви.
Выделим в этом примере следующие элементарные высказывания:






Тогда формула будет выглядеть следующим образом

П

ример: Всякая система уравнений
Представляет собой конъюнкцию решений:

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

-
Укажем свойства этой операции




В качестве примера рассмотрим логический анализ решения неравенства

Обычно рассуждают так:
Дробь больше 0 тогда и только тогда, когда и числитель, и знаменатель >0, или числитель и знаменатель <0. В результате этих рассуждений получаем 2 системы неравенств:

получаем логическую формулировку

Вспомнив пример из Шекспира, напишем логическую формулу несчастной любви

При желании можно показать, что

О

пределение конъюнкции и дизъюнкции распространяется на любое число высказываний. Так

^
Операция "исключающего или" задается следующей таблицей истинности, она истинна, когда истинен только один из операндов. Эту операцию еще называют строгой дизъюнкцией или логическим неравенством.
-
Эту операцию можно выразить через &,,.

В языковом эквиваленте чаще всего эта операция выражается сложным союзом "либо, либо".
Пример: возьмем из изумительной сказки Леонида Филатова "Про Федота –стрельца"
Или леший нынче рьян,
Или воздух нынче пьян,
Или в ухе приключился
У меня какой изъян.
Иль из царских, из окон,
Оглашен такой закон,
Чтобы птицы говорили
Человечьим языком.
Разобьем на элементарные высказывания:




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

Пример: Еще один пример из армейского юмора:
Носки должны быть или черными или синими.



5. Импликация
Следующая логическая операция, которую мы рассмотрим – это операция импликации. Импликация ложна тогда и только тогда, когда


-
Это выражение читается так: если


Пример: Теорема: «Вертикальные углы – конгруэнтны», будет выглядеть так: «Если углы вертикальны, то они конгруэнтны». В такой формулировке выявлены посылка –







В математических терминах импликация еще обозначается фразами:




Импликацию тоже можно выразить через &,,

6. Эквивалентность
Она истинна только тогда, когда значения


-
В математических терминах эта операция интерпретируется в качестве фраз "тогда и только тогда", "необходимо и достаточно". Такая форма тоже очень часто используется в формулировке теорем. Эквивалентность представляется в виде:

Т.е. из




Например: Признак сходимости бесконечного ряда. Ряд сходится тогда и только тогда

^
Эта операция обозначается знаком / и определяет несовместимость высказываний. Эта операция ложна тогда и только тогда, когда оба операнда истинны. Выражение «А/В» читается так: «

-
Например: «2 * 2 = 4» и «2 * 2 = 5» несовместны – это истинное высказывание
«2 * 3 = 6» и «3 * 2 = 6» несовместны – это ложное высказывание, т.к. вот эти то высказывания как раз совместны.
Через базовые операции Штрих Шеффера выражается так:

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


Упражнение: Выразите через Штрих Шеффера оставшиеся логические операции (дизъюнкцию, импликацию, эквивалентность, исключающее или).
Ограничимся этим набором логических операций. Существует всего 16 двуместных операций. Выпишем их
А | В | 0 | А&В | А В | В А | А В | А В | А В | А y | В | В А | А | А В | А/В | 1 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Все эти функции называют элементарными. Символы операций часто называют логическими связками.
Теорема. Число всех различных


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












Будем считать, что






Для

![]() | ![]() | ![]() | ![]() |
0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
Теперь приведем несколько парадоксальных примеров, и подчеркнем, что истинность или ложность сложного высказывания зависит только от истинности или ложности элементарных высказываний, входящих в него.
Например: «Если треугольник имеет четыре стороны, то 2 +2 = 4». Такое высказывание в обыденной речи будет встречено с легким недоумением, но вы должны хорошо понимать, что это пример операции импликации. По определению, из ложной посылки «Если треугольник имеет четыре стороны», может следовать какое угодно заключение, и сложное высказывание будет истинным.
Поскольку любое истинное высказывание ничем не отличается от другого истинного высказывания, т.к. никаких других свойств высказываний математическая логика не рассматривает, то все истинные высказывания между собой эквивалентны. Это в равной мере относится и ко всем ложным высказываниям.
Рассматривая с такой точки зрения любые два истинных высказывания, например «Дважды два четыре» и «Наполеон умер 5 мая 1821 года», равно как и любые два ложных высказывания вроде «Дважды два пять» и «Снег черен», трактуются как эквивалентные друг другу.
^
Определение: Алфавитом называется любой непустой набор символов. Элементы этого набора называются символами алфавита.
Определение: Словом в алфавите



Определение: Формула алгебры логики определяется следующим образом (индуктивное определение):
Любая логическая переменная есть формула.
Если- формула, то
- формула (допустимы технические символы)
Еслии
– формулы, то
– тоже формулы (допустимы все логические связки).
Других формул нет.
Определение: Подформулой формулы


Для сокращения записи формул обычно принимаются следующие соглашения:
если часть формулы заключена в скобки, то сначала производится действие в скобках,
если над частью формулы стоит знак отрицания, то он заменяет собой скобки, в которые заключена эта часть формулы.
Принят следующий порядок выполнения операций:
Отрицание
конъюнкция,
дизъюнкция,
импликация и эквивалентность в порядке их записи,
Определение: Формула называется тождественно истинной или тавтологией, если она реализует функцию «тождественная единица», и тождественно ложной, если 0.
Упражнения
Являются ли формулы тождественно истинными:



^
Определение: Пусть логические формулы составлены из простейших высказываний. Если на любом наборе значений простых высказываний значения А и В совпадают, то А и В называются тождественными.
Возвращаясь к Шекспировскому примеру, и построив Таблицы истинности, мы легко покажем, что R=G.
| ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
Пример: Составим таблицу истинности следующей формулы:

| ![]() | ![]() | ![]() | ![]() | ![]() |
0 | 0 | 0 | 1 | 1 | 1 |
0 | 0 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 | 0 | 0 |
1 | 1 | 1 | 1 | 1 | 1 |
Скачать файл (389.4 kb.)