Дискретная математика
Покупка
Основная коллекция
Тематика:
Дискретная математика
Издательство:
РИОР
Год издания: 2017
Кол-во страниц: 151
Дополнительно
Вид издания:
Учебно-методическая литература
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-369-00289-6
Артикул: 092200.02.01
В шпаргалке в краткой и удобной форме приведены ответы на все основные вопросы, предусмотренные государственным образовательным стандартом и учебной программой по дисциплине «Дискретная математика».
Книга позволит быстро получить основные знания по предмету, повторить пройденный материал, а также качественно подготовиться и успешно сдать зачет и экзамен.
Рекомендуется всем изучающим и сдающим дисциплину «Дискретная математика» в высших и средних учебных заведениях.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 01.03.01: Математика
- 01.03.02: Прикладная математика и информатика
- 02.03.01: Математика и компьютерные науки
- 02.03.02: Фундаментальная информатика и информационные технологии
- 02.03.03: Механика и математическое моделирование
- 03.03.02: Прикладная математика и информатика
- 04.03.02: Химия, физика и механика материалов
- 09.03.03: Прикладная информатика
- 09.03.04: Программная инженерия
- 11.03.02: Инфокоммуникационные технологии и системы связи
- 45.03.04: Интеллектуальные системы в гуманитарной сфере
- ВО - Магистратура
- 02.04.03: Математическое обеспечение и администрирование информационных систем
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
ДИСКРЕТНАЯ МАТЕМАТИКА Шпаргалка Москва РИОР
УДК 519.1(075.8) ББК 22.176я73 Д48 Дискретная математика: Шпаргалка. — М.: РИОР. — 151 с. ISBN 978-5-369-00289-6 В шпаргалке в краткой и удобной форме приведены ответы на все основные вопросы, предусмотренные государственным образовательным стандартом и учебной программой по дисциплине «Дискретная математика». Книга позволит быстро получить основные знания по предмету, повторить пройденный материал, а также качественно подготовиться и успешно сдать зачет и экзамен. Рекомендуется всем изучающим и сдающим дисциплину «Дискретная математика» в высших и средних учебных заведениях. УДК 519.1(075.8) ББК 22.176я73 Д48 ISBN 978-5-369-00289-6 © РИОР ФЗ № 436-ФЗ Издание не подлежит маркировке в соответствии с п. 1 ч. 2 ст. 1
1. Логика высказываний Логика — это наука о рассуждениях, которая позволяет определить и с т и н н о с т ь или л о ж н о с т ь того или иного математического утверждения, исходя из совокупности первичных предположений, называемых аксиомами. Высказывание — это утверждение или повествовательное предложение, о котором можно сказать, истинно оно или ложно. Будем обозначать высказывания буквами латинского алфавита р, q, r, ... . Истинность или ложность, приписываемые некоторому утверждению, называются его значением истинности или истинностным значением. Значение истинности может обозначаться либо латинскими буквами Т (true) и F ( false), либо русскими буквами И (истина) и Л (ложь), либо цифрами 1 и 0. Предложения, представляющие вопрос (Кто вы?), приказ или восклицание (Прочтите эту главу до следующего занятия) либо внутренне противоречивое утверждение (Это утверждение ложно), не являются высказываниями. В обыденной речи для образования сложного предложения из простых используются связки — особые части речи, соединяющие отдельные предложения. В логике
смысл таких связок должен быть определен однозначно. Истинность сложного высказывания однозначно опре деляется истинностью или ложностью составляющих его частей. Если связка применяется только к о д н о м у высказыванию, то ее называют унарной. Если связка применяется к д в у м высказываниям, то ее называют бинарной. Любое сложное высказывание, содержащее связки, представляет собой логическую функцию, которую можно отразить таблицей истинности. Таблица истинности перечисляет все возможные комбинации истинности и ложности сложного высказывания.
2. Унарные связки Поскольку для унарной связки используется только один аргумент, он может принимать два различных значения (Т или F ), а для каждого из двух значений аргумента может быть два значения истинности сложного высказывания (Т или F ), следовательно, для унарной операции возможны четыре вида связок. Они представлены в табл. Таблица Случай р ∼р T F p 1 2 3 4 5 6 1 T F T F T 2 F T T F F Для каждой унарной связки столбцы 1 и 2 в табл. являются общими. Совокупность общих столбцов и столбца для соответствующего вида связки представляет таблицу истинности конкретной связки. Столбец 2 является аргументом. Столбцы 3–6 характеризуют различные логические функции (связки). Одна из них называется опровержением или отрицанием высказывания р (столбец 3 табл.), обозначается символом «∼» перед высказыванием (∼р) или чертой сверху (р–), а иногда символом «¬»
перед высказыванием (¬р) или символом «′» после него (p′). Истинностное значение ∼р всегда противоположно истинностному значению р. В таблицах истинности отрицание всегда оценивается первым, если только за знаком отрицания не следует высказывание, заключенное в скобки. Высказывание, истинное во всех случаях (независимо от аргумента), называется логически истинным или тавтологией (столбец 4 табл.); высказывание, построенное так, что оно ложно в каждом случае (независимо от аргумента), называется логически ложным или противоречием (столбец 5 табл.). Четвертый случай (столбец 6 табл.) соответствует значению функции, которая повторяет значения аргумента.
3. бинарные связки Истинностные значения бинарных связок показаны в табл., в которой столбцы 2, 3 являются аргументами. Таблица Случай р q p ∧ q p ∨ q p ∨ q p → q q → p p ↔ q pq p ↓ q 1 2 3 4 5 6 7 8 9 1 0 1 1 1 T T T T F T T T F F 2 T F F T T F T F T F 3 F T F T T T F F T F 4 F F F F F T T T T T В конъюнкции высказываний р и q (обозначается р ∧ q или р&q) символ «∧» или «&» соответствует союзу и на языке символических выражений (столбец 4 табл.). В дизъюнкции высказываний р и q (обозначается р ∨ q) символ «∨» соответствует союзу или (столбец 5 табл.). Еще одна бинарная связка — исключающее или, обозначаемое «∨» (столбец 6 табл.). Когда говорят, что р и q либо истинно, либо ложно, то предполагают, что это не выполняется одновременно. Символ «→» называется импликацией высказываний р и q или условной связкой, обозначается p → q (столбец 7 табл.). В переводе на символический язык имп
ликация может обозначать фразу: если р, то q. С импликацией p → q связаны еще три типа высказываний, которые определяются следующим образом: p → q — импликация высказываний р и q; q → p — конверсия высказывания p → q; ∼p → ∼q — инверсия высказывания p → q; ∼q → ∼p — контрапозиция высказывания p → q. Истинность конверсии показана в столб це 8 табл. Высказывание вида (p → q) ∧ (q → p) обозначается p ↔ q. Символ «↔» называется эквиваленцией высказываний р и q. Штрих Шеффера (столбец 10 табл.) можно определить как двойную не-и. Стрелку Пирса (столбец 11 табл.) можно определить как двойную не-или. Может возникнуть вопрос, как интерпретировать выра жения, в которых отсутствуют скобки. Во избежание неоднозначности лучше всегда использовать скобки. Однако здесь, как и в алгебре, имеется следующий порядок выполнения операций: ∼; ∧ , ∨ ; →; ↔. Поэтому такие выражения, как ∼р ∨ q, р ∧ q ∨ r, р ∧ q → r и р ∧ q ↔ q → r, можно интерпретировать как (∼р) ∨ q, (р ∧ q) ∨ r, (р ∧ q) → r и (р ∧ q) ↔ (q → r).
4. ЭквиваЛентность высказываний Особый интерес представляют сложные высказывания, имеющие различное строение, но являющиеся истинными в одних и тех же случаях. Такие высказывания называются логически эквивалентными. Эквивалентность обозначается символом «≡». Используются и другие символы, например «=». Эквивалентность двух высказываний легко установить, сравнивая их таблицы истинности. С помощью таблиц истинности можно доказать следующие логические эквивалентности: Законы идемпотентности: р ∨ p ≡ p; р ∧ p ≡ p. Закон двойного отрицания: ∼(∼р) ≡ p. Законы де Моргана: ∼(р ∨ q) ≡ ∼p ∧ ∼q; ∼(р ∧ q) ≡ ∼p ∨ ∼q. Свойства коммутативности: р ∨ q ≡ q ∨ p; р ∧ q ≡ q ∧ p. Свойства ассоциативности: p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r; p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r. Свойства дистрибутивности: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r); p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r). Закон контрапозиции: р → q ≡ ∼q → ∼p.
Другие полезные свойства: р → q ≡ ∼p ∨ q; (р → q) ∧ (q → p) ≡ р ↔ q. Операции с логически истинными и логически ложными высказываниями: р ∧ T ≡ p; р ∨ T ≡ T; р ∨ ∼p ≡ T; р ∧ F ≡ F; р ∨ F ≡ p; р ∧ ∼p ≡ F; р → p ≡ T. Отметим, что благодаря свойству ассоциативности высказывания p ∧ (q ∧ r) и (p ∧ q) ∧ r могут быть записаны в виде p ∧ q ∧ r. Аналогично p ∨ (q ∨ r) и (p ∨ q) ∨ r можно записать просто как p ∨ q ∨ r. В каждом высказывании можно заменить любую его компоненту на логически эквивалентное ей высказывание. Полученное в результате такой замены высказывание будет логически эквивалент но исходному, поскольку истинностное значение высказывания зависит исключительно от истинностных значений составляющих его компонент (но не от их формы или сложности).