Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Дискретная математика

Покупка
Основная коллекция
Артикул: 092200.02.01
Доступ онлайн
от 28 ₽
В корзину
В шпаргалке в краткой и удобной форме приведены ответы на все основные вопросы, предусмотренные государственным образовательным стандартом и учебной программой по дисциплине «Дискретная математика». Книга позволит быстро получить основные знания по предмету, повторить пройденный материал, а также качественно подготовиться и успешно сдать зачет и экзамен. Рекомендуется всем изучающим и сдающим дисциплину «Дискретная математика» в высших и средних учебных заведениях.
Тематика:
ББК:
УДК:
ОКСО:
ГРНТИ:
Дискретная математика: шпаргалка. — Москва : РИОР. — 151 с. - ISBN 978-5-369-00289-6. - Текст : электронный. - URL: https://znanium.com/catalog/product/614868 (дата обращения: 29.03.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
ДИСКРЕТНАЯ  МАТЕМАТИКА

Шпаргалка

Москва
РИОР

УДК 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
pq
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 табл.).  
В переводе на символический язык имп8

ликация может обозначать фразу: если  р, 
то  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.
В каждом высказывании можно заменить 
любую его компоненту на логически эквивалентное ей высказывание. Полученное 
в результате такой замены высказывание 
будет логически эквивалент но исходному, 
поскольку истинностное значение высказывания зависит исключительно от истинностных значений составляющих его компонент 
(но не от их формы или сложности).

5. нормаЛьные формы  
дЛя Логических фУнкций
Любое высказывание можно выразить через 
пару связок  «∼  и  ∧»  или «∼  и  ∨»,  причем 
в любом случае применяются обе связки. Однако две связки — штрих Шеффера  
и стрелка Пирса — объединяют эти пары: 
рq  ≡  ∼(р  ∧  q);  р ↓ q  ≡  ∼(р ∨ q).  Следовательно, 
любое высказывание можно выразить с использованием только одной из них.
Таким образом, если показать, что «∼  
и ∧» или «∼ и ∨» можно выразить, используя 
только ↓, тогда и любую связку можно выразить, используя лишь ↓.
Будем считать в качестве ограничения, что 
операция отрицания может быть применена 
только к простому высказыванию. Построим логические функции с использованием 
связок   ∼,  ∧    и  ∨.
Пусть  р1, р2, …, рn  — простые высказывания. Состояния простого высказывания  р 
в прямой  (р)  или инверсной  (∼р)  форме 
часто называют термами. Любой вариант 
связки (∧  или  ∨) полного набора термов 
называют конституентой.
Назовем выражение  x1  ∧  x2  ∧  …  ∧  xn, в 
котором  xi = pi   или xi = ∼pi,  элементарной 
конъюнкцией или конъюнктой. Выражение, 
представляющее собой дизъюнкцию эле12

ментарных конъюнкций, называется дизъюнктивной нормальной формой или совершенной 
дизьюнктивной нормальной формой (СДНФ). 
Так что если m1, m2, …, mn — элементарные 
конъюнкции, то  m1 ∨ m2 ∨ … ∨ mn — дизъюнктивная нормальная форма.
Если требуется построить высказывание, 
соответствующее конкретной таблице истинности, необходимо выбрать выражения, 
соответствующие случаям (строкам), где 
высказывание истинно, и соединить их связкой  ∨.
Назовем выражение x1  ∨  x2  ∨  … ∨  xn, в 
котором  xi = pi  или xi = ∼pi,  элементарной 
дизъюнкцией или дизъюнктой. Вы ражение, 
представляющее собой конъюнкцию элементарных дизъюнкций, называется конъюнктивной нормальной формой или совершенной 
конъюнктивной нормальной формой (СКНФ). 
Так что если  m1, m2, …, mn  — элементарные 
дизъюнкции, то  m1 ∧ m2 ∧ … ∧  mn  — конъюнктивная нормальная форма.
Если требуется найти высказывание, обладающее данной таблицей истинности, зная 
все случаи (строки), где в таблице истинности стоит ложное значение, то используются высказывания, каждое из которых ложно 
только в соответствующей строке, и все 
эти высказывания объединяются связкой  ∧.

Доступ онлайн
от 28 ₽
В корзину