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

ДИСКРЕТНАЯ  МАТЕМАТИКА

Шпаргалка

Москва
РИОР

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

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