Дискретная математика. Краткий курс. Учебное пособие

Казанский А.А.

Возрастное ограничение: 0+ Жанр: Наука Издательство: Проспект Дата размещения: 15.09.2015 ISBN: 9785392196043 Язык: Объем текста: 163 стр. Формат: epub

Оглавление

Глава 1. Теория множеств

Глава 2. Отношения

Глава 3. Теория графов

Глава 4. Логика и исчисление высказываний

Для бесплатного чтения доступна только часть главы! Для чтения полной версии необходимо приобрести книгу

Глава 4.
Логика и исчисление высказываний

4.1. Введение

Логика занимается построением правильных выводов, и со времен Аристотеля (384–322 до н.э.) она развивалась как одно из направлений философии, но в середине XIX в. Д. Буль начал рассматривать логику как алгебраическую систему и эти идеи оказались крайне полезными в последние годы при проектировании компьютерных схем и автоматов.

Льюис Кэрролл в 1897 г. дал следующий пример:

Все утки в деревне, которые помечены клеймом «B», принадлежат мистеру Бонду.

Утки в деревне не носят кружевных ошейников, если они не имеют клейма «B».

Мистер Бонд не имеет серых уток в этой деревне.

Будет ли правильным заключение, что «в этой деревне нет серых уток, которые носят кружевные ошейники»?

Аристотель ввел понятие логических пропозиций, которые также называют утверждениями, или высказываниями, а также рассмотрел способы образования выводов, или заключений, из этих высказываний, которые он назвал силлогизмами.

Любое грамматическое предложение содержит подлежащее и сказуемое. Чтобы получить логическое высказывание, необходимо преобразовать такое предложение к виду, когда оно будет иметь объект и предикат. Объект соответствует подлежащему, а предикат в общем случае определяет свойства данного объекта.

Например, рассмотрим следующие высказывания:

Все пеликаны являются птицами.

Нет ни одной модной вещи, которая не устаревает.

Некоторые учебники являются электронными.

Некоторые люди не являются студентами.

В каждом из этих предложений имеется объект S (например, пеликаны), который связан с предикатом P (в данном примере это птицы). Количество объектов определяется словами «все» и «некоторые», которые называют кванторами. Утверждения называются универсальными («все» или «нет ни одного»), частными («некоторые»), а также утвердительными или отрицательными.

Тогда в символическом виде можно записать:

Все S являются P (универсальное утверждение).

Нет ни одного S, которое является P (универсальное отрицание).

Некоторые S являются P (частное утверждение).

Некоторые S не являются P (частное отрицание).

Аристотель описал вывод путем связывания вместе трех утверждений: два из них он назвал посылками, а третье заключением, основанном на посылках.

Рассмотрим пример вывода (обычно посылки отделяются от заключения горизонтальной чертой).

Если птицы имеют крылья

и пеликаны являются птицами,

тогда пеликаны имеют крылья.

В этом примере силлогизма заключение вывода имеет объект S (пеликаны) и предикат P (крылья). Первая посылка включает в себя P, вторая — S, и обе они включают в себя свойство «являются птицами». Такой свойство принято называть средним свойством M. С этими обозначениями силлогизм можно записать

Если M является P

и S является M,

тогда S является P.

Если убрать все слова, то можно получить сокращенную запись силлогизма:

M P

S M

S P.

С учетом условий, что первая посылка должна содержать P, вторая посылка должна содержать S, обе они должны содержать M и заключением вывода должно быть SP, можно получить еще три схемы вывода:

Все они известны как четыре фигуры силлогизма.

Каждая из этих фигур может быть универсальной или частной, утвердительной или отрицательной, но все они приводят к правильным выводам. При этом имеется в виду, что если вместо S, M и P подставлять такие предложения, что посылки, полученные в результате замены, будут истинными, то и окончательный вывод будет истинным. Важным условием является и то, что предложения, используемые для замены, должны быть такими, чтобы их истинность и ложность может быть определена однозначно.

Если схема вывода нарушается, то вывод оказывается неверным. Например, рассмотрим следующую фигуру:

Нет ни одного M, которое является P

Все S являются M

Некоторые S являются P.

Рассмотрим такой пример для этого силлогизма:

Нет ни одного положительного целого числа, которое меньше нуля

Все натуральные числа являются положительными целыми числами

Некоторые натуральные числа меньше нуля.

Нетрудно видеть, что такая подстановка приводит к неверному выводу.

4.2. Высказывания и составные высказывания

Современную логику иногда называют пропозиционной логикой. Такое название означает, что каждое рассматриваемое высказывание либо истинно, либо ложно (и оно не может быть одновременно и истинным и ложным). Рассмотрим, например такое предложение: «На улице светло». Для того чтобы это предложение было высказыванием, необходимо определить случаи, когда оно истинно и когда ложно. Если речь идет о ясном солнечном дне, то, вероятно, такое высказывание истинно. Если имеется в виду ночь, то оно ложно. Однако совершенно непонятно, какое оно примет значение, если дело происходит в пасмурный туманный день, при очень плохой видимости, или когда наступают сумерки. Крайне затруднительно ответить на вопрос светло ли на улице, если дело происходит ночью, но улица ярко освещена. Поэтому такое предложение нельзя считать высказыванием и, чтобы оно им стало, его надо дополнять какими-то условиями. Однако неясно, сколько должно быть условий и какими они должны быть. Из этого примера можно видеть, что построить высказывание для реальной действительности едва ли возможно. Обычно высказывания используются в рамках некоторой модели, которая абстрагирована от реальности и предназначена для изучения вполне определенных ее свойств. Поэтому логика не занимается внутренней структурой высказываний, предполагая, что она уже определена. Она занимается вопросами построения составных высказываний, образованных из исходных. Эта задача вполне разрешима и хорошо разработана.

Другая проблема, связанная с высказыванием, состоит в том, что надо заранее определять множество логических возможностей, с которыми оно связано. Необходимо для каждой из этих возможностей уметь определять, истинно высказывание или ложно, а также знать, не приводит ли данный случай к противоречию. Рассмотрим, например, задачу, которая предложена профессором Рэймондом Смаллианом из университета в Принстоне: «Под всесокрушающим пушечным ядром мы понимаем ядро, сметающее на своем пути все, что попадается, а под несокрушимым столбом — столб, который нельзя ни повалить, ни сломать. Что произойдет, если всесокрушающее ядро попадет в несокрушимый столб?»

При первом рассмотрении эта интересная задача вызывает затруднения. Часто возникает даже сомнение в существовании ее решения. Однако это происходит в том случае, если не учитывать имеющиеся логические возможности. При формулировке высказывания о пушечном ядре утверждается, что оно сметает на своем пути все, что попадается. В то же время в высказывании о несокрушимом столбе утверждается, что его нельзя ни повалить, ни сломать. С точки зрения логических возможностей такие объекты не могут существовать одновременно. Если есть всесокрушающее ядро, то тогда не может быть ничего, что бы оно не могло сокрушить, и поэтому не может быть и несокрушимого столба. Обратное тоже справедливо. Поэтому при формулировании высказывания всегда необходимо определять, не приводит ли оно к случаям, которые логически невозможны. При решении практической задачи сначала необходимо составить полный список всех логических возможностей для данной задачи, а затем уже создавать различные высказывания, связанные с этими возможностями.

Поскольку многие высказывания (или пропозиции) являются составными, то возникает вопрос: при каких условиях можно связывать исходные (простые) высказывания и какое высказывание является простым? Высказывание называется простым (или примитивным), если оно не может быть разбито на более простые высказывания, т.е. если оно не является комбинацией более простых высказываний.

Например, высказывание «Университет выпускает специалистов по информатике и математике» является составным, поскольку оно может быть разбито на два простых: «Университет выпускает специалистов по информатике» и «Университет выпускает специалистов по математике». Высказывание «Этот человек является музыкантом, но он не играет на гитаре» также составное и разбивается на простые: «Этот человек является музыкантом» и «Этот человек не играет на гитаре». Если имеется высказывание «Эти сведения можно найти в книге или в Интернете», то оно также состоит из двух простых: «Эти сведения можно найти в книге» и «Эти сведения можно найти в Интернете».

Основным свойством составного высказывания является то, что его истинность или ложность полностью определяется истинностью или ложностью тех простых высказываний, из которых оно образовано.

Под термином «исчисление высказываний» понимается метод, с помощью которого из одного или нескольких простых высказываний можно получить составное высказывание, истинность или ложность которого однозначно задается высказываниями, из которых оно построено. Образование составных высказываний осуществляется при помощи логических операций.

Для выражения логических значений будем рассматривать логические переменные, которые будем обозначать строчными буквами p, q, r, s, t, u, … Логические переменные могут принимать два значения: «истина» или «ложь», которые будем обозначать «1» и «0» соответственно.

4.3. Логические операции

Всего имеется 16 логических операций, однако далее рассмотрим некоторые из них.

Отрицание, ¬ p

Для данного высказывания p, новое высказывание, называемое отрицанием p, образуется при помощи записи слова «Неверно» перед р, или же добавлением в р слова «не».

Определение 4.1. Если р истинно, тогда ¬ p ложно; и если р ложно, тогда ¬ p истинно.

Рассмотрим пример: пусть имеется высказывание «На луне не видны звезды», тогда его отрицанием будет «Неверно, что на луне не видны звезды», или в более коротком виде «На луне видны звезды».

Если имеется высказывание р «Некоторые студенты отсутствовали на лекции», то высказывание «Некоторые студенты присутствовали на лекции» не будет его отрицанием. Это нетрудно доказать. Пусть, например, высказывание р истинно. Тогда имеется некоторое количество студентов, которых не было на лекции. Слово «некоторые» позволяет считать, что имеются и такие студенты, которые на данной лекции присутствовали. Но тогда высказывание «Некоторые студенты присутствовали на лекции» будет также истинным, что, в соответствии с определением, невозможно для отрицания. Следовательно, отрицанием будет высказывание «Все студенты присутствовали на лекции».

Конъюнкция, p ˄ q

Любые два высказывания можно связать при помощи слова «и», для того чтобы образовать составное высказывание, называемое конъюнкцией исходных высказываний. Конъюнкция символически обозначается p ˄ q и читается как «p и q». Высказывание p ˄ q является истинным только в случае истинности и p и q.

Определение 4.2. Если p и q истинны, тогда p ˄ q также истинно, иначе p ˄ q ложно.

Имеется ровно 4 возможности для определения значений истинности p ˄ q. Конъюнкция p ˄ q истинна, когда истинны p и q и ложна в оставшихся трех случаях: когда p ложно, а q истинно, когда p истинно, а q ложно и когда ложны и p и q.

Рассмотрим следующие высказывания:

1) «Москва столица Англии и Лондон столица России»;

2) «Москва столица Германии и Лондон столица Англии»;

3) «Москва столица России и Лондон столица Германии»;

4) «Москва столица России и Лондон столица Англии».

Здесь истинно только последнее высказывание, все остальные ложны.

Дизъюнкция, p ˅ q

Любые два высказывания можно связать при помощи слова «или», для того чтобы образовать составное высказывание, называемое дизъюнкцией исходных высказываний. Дизъюнкция символически обозначается p ˅ q и читается как «p или q». Высказывание p ˄ q является истинным только в случае истинности и p и q.

Определение 4.3. Если p и q ложны, тогда p ˅ q также ложно, иначе p ˅ q истинно:

1) «Москва столица Англии или Лондон столица России»;

2) «Москва столица Германии или Лондон столица Англии»;

3) «Москва столица России или Лондон столица Германии»;

4) «Москва столица России или Лондон столица Англии».

Здесь ложно только первое высказывание, все остальные истинны.

Следует помнить, что слово «или» не вполне ясно определяет тот смысл, который имеет логическая операция «или». Когда образовано составное высказывание при помощи конъюнкции, тогда оно истинно не только, когда истинно одно из высказываний (либо p, либо q), но и когда они оба истинны.

Все три операции представлены в таблицах на рис. 4.1.

Рис. 4.1

Обозначения логических операций не вполне стандартизированы, и часто для них используются другие символы, например:

для отрицания ¬ p используются p’, или p, или pc;

для конъюнкции p ˄ q используются p & q, или p · q, или pq;

для дизъюнкции p ˅ q используется p + q.

4.4. Таблицы истинности для высказываний

Обозначим через P(p, q, r, …) выражение, образованное из логических переменных p, q, r, …, каждая из которых может принимать одно из двух значений 1, 0 (истина, ложь), и соединенное знаками логический операций ¬, ˄, ˅ (или какими либо другими логическими операциями). Выражение P(p, q, r, …) является высказыванием.

Высказывание P(p, q, r, …) также принимает значение 1 или 0 (истина или ложь), и это значение зависит только от значений истинности переменных, из которых оно образовано. Иными словами, его значение определяется тем отношением, в котором находятся составляющие его переменные. Самый удобный способ увидеть это отношение дают так называемые таблицы истинности. Эти таблицы при двух переменных имеют 4 строки, при трех переменных — 8 строк и при n переменных — 2n строк.

Наука Казанский А.А. Дискретная математика. Краткий курс. Учебное пособие

Наука Казанский А.А. Дискретная математика. Краткий курс. Учебное пособие

В пособии изложены основные разделы современной дискретной математики. Рассматриваются вопросы, связанные с теорией множеств, теорией отношений, теорией графов и логикой. Материал построен на основе курса лекций, читаемого автором в технических вузах.<br /> В каждой главе рассмотрено большое число задач с подробными решениями и примерами, что позволяет эффективно и быстро осваивать изучаемую тему.<br /> Для студентов, обучающихся по специальности «Прикладная математика», а также для студентов технических и экономических факультетов, изучающих курс «Дискретная математика» и компьютерные технологии. Представляет интерес для тех, кто связан с использованием методов дискретной математики.

Внимание! Авторские права на книгу "Дискретная математика. Краткий курс. Учебное пособие" (Казанский А.А.) охраняются законодательством!