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

СРЕДНЕЕ
ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАНИЕ



В.В. КУЛИКОВ




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




УЧЕБНОЕ ПОСОБИЕ


  Рекомендовано Межрегиональным учебно-методическим советом профессионального образования в качестве учебного пособия для учебных заведений, реализующих программу среднего профессионального образования по укрупненной группе специальностей 09.00.00 «Информатика и вычислительная техника» (протокол № 11 от 10.06.2019 г.).




Москва РИОР ИНФРА-М

УДК 519.1(075.32)
ББК 22.176я73
      К90


   ФЗ    Издание не подлежит маркировке   
№ 436-ФЗ в соответствии с п. 1 ч. 4 ст. 11

      Рецензенты:
      В.В. Копытов — директор регионального центра информатизации, заведующий кафедрой организации и технологии защиты информации, д-р техн. наук, старший научный сотрудник;
      С.В. Сподынюк — заведующая кафедрой высшей математики, канд. техн. наук, доцент

      Куликов В.В.
К90 Дискретная математика: учебное пособие / В.В. Куликов. — Москва : РИОР : ИНФРА-М, 2020. — 303 с. — (Среднее профессиональное образование). — DOI: https://doi.org/10.12737/2686
          ISBN 978-5-369-01826-2 (РИОР)
          ISBN 978-5-16-015264-6 (ИНФРА-М, print)
          В пособии рассмотрены элементы математической логики, теории множеств и теории графов, приведены основные принципы комбинаторики. Описаны алгоритмы, позволяющие решать различные задачи с помощью компьютера. Изложены основные понятия теории конечных автоматов.
          Предназначено для студентов учебных заведений среднего профессионального образования. Может быть рекомендовано студентам высших учебных заведений, обучающихся по направлениям подготовки «Телекоммуникации», «Информационные системы», «Информатика и вычислительная техника».

                                                    УДК519.1(075.32)
                                                    ББК 22.176я73













ISBN 978-5-369-01826-2 (РИОР)
ISBN 978-5-16-015264-6 (ИНФРА-М, print)


© Куликов В.В.

Глава 1. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ



   1.1. ЛОГИКА ВЫСКАЗЫВАНИЙ
          Логика — это фундамент, на котором построено все здание математики [2]. По сути, логика — это наука о рассуждениях, которая позволяет определить истинность или ложность того или иного математического утверждения, исходя из совокупности первичных предположений, называемых аксиомами. Логика применяется также в информатике для построения компьютерных программ и доказательства их корректности. Понятия, методы и средства логики лежат в основе современных информационных технологий. Рассмотрим основы математической логики.
   Высказывание — это утверждение или повествовательное предложение, о котором можно сказать, истинно оно или ложно. Иными словами, утверждение об истинности или ложности высказывания должно иметь смысл. Будем обозначать высказывания буквами латинского алфавита р, q, г, ... . Например, р может обозначать утверждение «Завтра будет дождь», а q — утверждение «Квадрат целого числа есть число положительное».
   Истинность или ложность, приписываемые некоторому утверждению, называются его значением истинности или истинностным значением. Значение истинности может обозначаться либо латинскими буквами Т (true) и F (false) [2], либо русскими буквами И (истина) и Л (ложь) [1], либо цифрами 1и0[7].
   Предложения, представляющие вопрос (Кто вы?), приказ или восклицание (Прочтите эту главу до следующего занятия) либо внутренне противоречивое утверждение (Это утверждение ложно), не являются высказываниями.
   В обыденной речи для образования сложного предложения из простых используются связки — особые части речи, соединяющие отдельные предложения. Высказывание, не содержащее связок, называется простым, а высказывание, содержащее связки, — сложным. Наиболее часто употребляются связки и, или, нет, если... то, только если и тогда и только тогда. В отличие от обыденной речи, в логике смысл таких связок должен быть определен однозначно. Истинность сложного высказывания однозначно определяется истинностью или ложностью составляющих его частей.

3

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

Случай р ~р Т F Р
  1    2 3  4 5 6
  1    Т F  Т F Т
  2    F Т  Т F F

   Для каждой унарной связки столбцы 1 и 2 в табл. 1.1 являются общими. Совокупность общих столбцов и столбца для соответствующего вида связки представляет таблицу истинности конкретной связки. Столбец 2 является аргументом. Столбцы 3—6 характеризуют различные логические функции (связки). Одна из них называется опровержением или отрицанием высказывания р (столбец 3 табл. 1.1), обозначается символом «~» перед высказыванием (~р) [2] или чертой сверху (р ) [1], а иногда символом «—» перед высказыванием (—р) или символом «'» после него (р').
   Истинностное значение ~р всегда противоположно истинностному значению р. В таблицах истинности отрицание всегда оценивается первым, если только за знаком отрицания не следует высказывание, заключенное в скобки.
   Высказывание, истинное во всех случаях (независимо от аргумента), называется логически истинным или тавтологией (столбец 4 табл. 1.1); высказывание, построенное так, что оно ложно в каждом случае (независимо от аргумента), называется логически ложным или противоречием (столбец 5 табл. 1.1). Четвертый случай (столбец 6 табл. 1.1) соответствует значению функции, которая повторяет значения аргумента.

4

   У бинарных связок возможны четыре случая, которые необходимо рассмотреть. Высказывание р может быть истинным (Т) или ложным (F) и независимо от того, какое истинностное значение принимает р, высказывание q может также быть истинным (Т) или ложным (F). Для каждого случая значение связки может быть либо истинным (Т), либо ложным (F). Таким образом, возможное число связок составляет 4² = 16. Только 10из них имеют названия и условные обозначения.
   К бинарным связкам относят конъюнкцию (л), дизъюнкцию (v), исключающее или (v), импликацию (^), эквиваленцию (^), а также связанные с импликацией конверсию, инверсию и контрапозицию. Кроме того, две связки носят имена ученых: так называемые штрих Шеффера (I) и стрелка Нирса (^). Истинностные значения этих связок показаны в табл. 1.2, в которой столбцы 2, 3 являются аргументами.
Таблица 1.2

Случай р q Р л q Р v q Р v q р ^ q q ^ р р^ q р I q р4 q
  1    2 3 4     5       6   7     8     9     1 0  1 1 
  1    Т т Т     Т     F     Т     Т     Т    F     F   
  2    т F F     Т     Т     F     Т     F    Т     F   
  3    F Т F     т     Т     Т     F     F    Т     F   
  4    F F F     F     F     Т     Т     Т    Т     Т   

   В конъюнкции (conjunctio — лат. союз, связь) высказываний р и q (обозначается р л q) символ «л» соответствует союзу и на языке символических выражений. Высказывание р л q истинно (столбец 4 табл. 1.2), когда истинны оба простых высказывания. Иногда для обозначения конъюнкции используютсимвол «&» (р&q) [8].
   В дизъюнкции (disjunctio — лат. различие) высказываний р и q (обозначается р v q) символ «v» соответствует союзу или. Для того чтобы всё высказывание было истинным, достаточно, чтобы хотя бы одна из двух составляющих его компонент была истинной (столбец 5 табл. 1.2). Высказывание рv q ложно только в случае 4, когда р и q обаложны.
   Еще одна бинарная связка — исключающее или, обозначаемое «v» (столбец 6 табл. 1.2). Когда говорят, что р и q либо истинно, либо ложно, то предполагают, что это не выполняется одновременно. В логике исключающее или используется довольно редко.

5

   Символ «^» называется импликацией (implico — лат. тесно связаны) высказываний р и q или условной связкой, обозначается p ^ q (столбец 7 табл. 1.2). Иногда импликацию обозначают символом «с» (p с q) [7]. В переводе на символический язык импликация может выражаться в виде различных языковых конструкций (обозначать фразу):
   еслир, то q;
   р достаточно для q;
   р является достаточным условием для q;
   q необходимо дляр;
   q является необходимым условием дляр;
   р, только если q (или: только если q, тор).
   Может показаться, что p ^ q носит характер причинно-следственной связи, но это не является необходимым. Нужно помнить, что истинность или ложность бинарного сложного высказывания зависит только от истинности составляющих его частей и не зависит от наличия или отсутствия между ними какой-либо связи. Важен не порядок, в котором р и q присутствуют во фразе, а то, какая часть предложения является частью «если», а какая частью «то». При замене «если р, то q» на «q, если р» с логической точки зрения последнее высказывание совпадает с исходным.
   С условным высказыванием — импликацией p ^ q связаны еще три типа высказываний: конверсия, инверсия и контрапозиция высказывания p ^ q. Они определяются следующим образом:
   p ^ q — импликация высказыванийр и q;
   q ^p — конверсия высказыванияp ^ q;
   -p ^ ~q — инверсия высказыванияp ^ q;
   -q ^ ~p — контрапозиция высказыванияp ^ q.
   Истинность конверсии показана в столбце 8 табл. 1.2. Таблица истинности инверсии совпадает с конверсией, а контрапозиции — с импликацией. В то же время импликация и ее инверсия имеют различные таблицы истинности. Непонимание этого факта — источник распространенных ошибок.
   Высказывание вида (p ^ q) л (q^p) обозначается p ^ q. Символ «^» [2] называется эквиваленцией высказыванийр и q. В некоторых источниках используются другие символы [1, 7]. Очевидно, что таблица истинности для (p ^ q) л (q ^p) определяет таблицу истинности для p ^ q (столбец 9 табл. 1.2). Непосредственно из определения вытекает, что эквиваленция истинна только в случае, когда р и q имеют одинаковые истинностные значения.

6

   Следующие языковые конструкции, выражающие эквивален-циювысказываний р^q, равносильны:
   р тогда и только тогда, когда q;
   р необходимо и достаточно для q;
   р есть необходимое и достаточное условие для q.
   Штрих Шеффера (столбец 10 табл. 1.2) имеет значение истинности, противоположное операции конъюнкции, в связи с чем эту связку можно определить как двойную не-и. Стрелка Пирса (столбец 11 табл. 1.2) имеет значение истинности, противоположное операции дизъюнкции, в связи с чем эту связку можно определить как двойную не-или.
   Приведем примеры сложных высказываний. Для этого обозначим:
   р: Петров водит автомобиль;
   q: У Смирноварусые волосы.
   Сложное высказывание «Петров водит автомобиль и у Смирнова русые волосы» может быть символически записано в виде р л q.
   Рассмотрим выражение р л q. Если некто говорит: «Петров водит автомобиль, и у Смирнова русые волосы», то мы, естественно, представляем себе Петрова за рулем автомобиля и русоволосого Смирнова. В любой другой ситуации (например, если Смирнов не русоволос или Петров не водит автомобиль) мы скажем, что говорящий не прав.
   Точно так же высказывание «Петров водит автомобиль или у Смирноварусые волосы» символически выражается как р v q.
   Примером, который подтверждает таблицу истинности для импликации (см. столбец 7 табл. 1.2), является высказывание «Если целое числоравно 3, то его квадратравен 9».
   Конечно, желательно, чтобы это высказывание было истинным всегда. Пустьр — высказывание «Целое число равно 3», а q — высказывание «Квадрат целого числа равен 9». Еслир и q истинны, то целое число равно 3 и его квадрат равен 9. Это соответствует первой строке таблицы истинности. Если целое число равно -3, то его квадрат по-прежнему равен 9. В этом случае р ложно и q истинно, что совпадает со случаем 3 и подтверждает правильность третьей строки таблицы. Если целое число равно 4, то ложны и р и q, что соответствует случаю 4. Этим подтверждается правильность четвертой строки таблицы. Заметим, что случай 2 здесь не имеет места, но во всех других случаях эта таблица истинности обеспечила нам желаемый результат.

7

   Может возникнуть вопрос, как интерпретировать выражения, в которых отсутствуют скобки. Во избежание неоднозначности лучше всегда использовать скобки. Однако здесь, как и в алгебре, имеется следующий порядок выполнения операций: -; л , v ; ^; ^. Поэтому такие выражения, как -р v q, р л q v г, р л q ^ г и р л q ^ q ^ г, можно интерпретировать как (-р) v q, (р л q) v г, (р л q) ^ г и (рлq)^ (q^г).
   Рассмотрим пример построения таблицы истинности сложного высказывания, состоящего из трех простых (функция от трех аргументов): «Попов уплатит налог за машину или Попов останется без машины и будет ходить наработу пешком». Пустьр обозначает высказывание «Попов уплатит налог за машину», q — высказывание «Попов останется при своей машине», а г — высказывание «Попов будет ходить наработу пешком». Тогда наше сложное высказывание можно представить в виде р v ((-q) л г), где скобки использованы, чтобы показать, какие именно высказывания являются компонентами каждой связки.
   Таблица истинности дает возможность однозначно указать те ситуации, когда высказывание является истинным; при этом необходимо быть уверенным, что учтены все случаи. Поскольку сложное высказывание содержит три основных высказывания р, q и г, товозможнывосемьслучаев(табл. 1.3).
Таблица 1.3

Случай р q г - q (- q) л г р v ((- q) л г)
  1    2 3 4 5   6                7       
  1    Т Т Т F   F                Т       
  2    Т Т F F   F                Т       
  3    Т F Т Т   Т                Т       
  4    Т F F Т   F                Т       
  5    F Т Т F   F                F       
  6    F Т F F   F                F       
  7    F F Т Т   Т                Т       
  8    F F F Т   F                F       

   При нахождении значений истинности для столбца (-q) л г используем столбцы для (-q) иг, а также таблицу истинности для л . Таблица истинности для л (см. столбец 4 табл. 1.2) показывает, что высказывание (-q) л г истинно лишь в том случае, когда истинны оба высказывания (-q) и г. Это имеет место лишь в случаях 3и7 (см. табл. 1.3).

8

   Заметим, что при определении значений истинности для столбца р v ((~q) л г) играет роль только истинность высказываний р и (~q) л г. Таблица истинности для v (см. столбец 5 табл. 1.2) показывает, что единственный случай, когда высказывание, образованное с помощью связки или, ложно, — это случай, когда ложны обе части этого высказывания. Такая ситуация имеет место только в случаях 5, 6 и 8 (см. табл. 1.3). Если Попов не уплатит налог за машину (т.е.р ложно, или имеет значение F), останется без машины (q имеет значение F) и будет ходить на работу пешком (г имеет значение F), то будет иметь место случай 7. Тот, кто скажет: «Попов уплатит налог за машину или Попов останется без машины и будет ходить наработу пешком», будет абсолютно прав.
   Другой, эквивалентный способ построения таблицы истинности состоит в том, чтобы записывать истинностные значения выражения под связкой. Снова рассмотрим выражение р v ((~ q) л г). Сначала записываем истинностные значения под переменными р, q и г (табл. 1.4). Единицы под столбцами истинностных значений (см. строку «Очередность действий» в табл. 1.4) указывают на то, что этим столбцам истинностные значения присваиваются в первую очередь. В общем случае число под столбцом будет показывать номер шага, на котором выполняются вычисления соответствующих истинностных значений.
   Затем мы записываем под символом «~» (столбец 7) истинностные значения высказывания ~q. Далее записываем истинностные значения ~qл г под символом «л» (столбец 9). Наконец записываем значения высказыванияр v ((~q) л г) под символом «v» (столбец 6).

Таблица 1.4

Случай   р     q   г    Р v ((~ q) л г) 
  1    2      3    4    5 6 7   8  9 1 0
  1    Т      Т    Т    Т Т F   Т  F Т  
  2    Т      Т    F    Т Т F   Т  F F  
  3    Т      F    Т    Т Т Т   F  Т Т  
  4    Т      F    F    Т Т Т   F  F F  
  5    F      Т    Т    F F F   Т  F Т  
  6    F      Т    F    F F F   Т  F F  
  7    F      F    Т    F Т Т   F  Т Т  
  8    F      F    F    F F Т   F  F F  
Очередность действий    1 4 2   1  3 1  

9

  1.2. ЭКВИВАЛЕНТНОСТЬ ВЫСКАЗЫВАНИЙ
         Особый интерес представляют сложные высказывания, имеющие различное строение, но являющиеся истинными в одних и тех же случаях. Такие высказывания называются логически экви-вилентными. Эквивалентность обозначается символом «=» [2]. Используются и другие символы, например «=». Эквивалентность двух высказываний легко установить, сравнивая их таблицы истинности.
   Пример. Пусть р и q обозначают следующие высказывания: р: Сегодня шел дождь;
   q: Сегодня шел снег.
   Рассмотрим сложные высказывания: «Неверно, что сегодня шел дождь или снег», или символически ~(р v q), и «Сегодня не шел дождь и сегодня не шел снег», или символически -р л ~q.
   Построим таблицы истинности для обоих высказываний (табл. 1.5).
Таблица 1.5

Случай р  q  ~    (р    v    q)    (~   р) л    (~    q)     
  1    2  3  4 5         6   7     8 9       1 0   11   1 2 
  1    Т  Т  F Т         Т   Т     F Т      F     F    Т    
  2    Т  F  F Т         Т   F     F Т      F     Т    F    
  3    F  Т  F F         Т   Т     Т F      F     F    Т    
  4    F  F  Т F         F   F     Т F      Т     Т    F    
Номер шага   3 1         2   1     2 1      3     2    1    

   Итак, во всех четырех строках истинностные значения для ~(р v q) (действие 3, столбец 4) и для ~рл~q (действие 3, столбец 10) совпадают. Это означает, что два рассматриваемых выска-зываниялогическиэквивалентны,т.е. ~(рvq) = ~рл~q. о
   Используя это свойство, можно строить отрицание высказываний с «или», осуществляя отрицание каждой из его частей и меняя «или» на «и».
   С помощью таблиц истинности можно доказать следующие логические эквивалентности:
Законы идемпотентности:          р vр = р;
                                  р л р = р.
Закон двойного отрицания:        ~(~р) = р.

10