Понятие высказывания. Понятие операции

М.А.Евдокимов, В.Г.Саркисов, Г.А.Саркисов

Элементы

математической логики

Учебно-методическое пособие

Самара 2004

УДК 51

Элементы математической логики: Учеб.-метод.пособ. / М.А.Евдокимов, В.Г.Саркисов, Г.А.Саркисов; Самар. гос. техн. ун-т. Самара 2004, с.33.

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

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

ISBN 5-7964-0625-6.

Ил. 27. Табл. 23. Библиогр.: 5 назв.

Печатается по решению редакционно-издательского совета

Самарского государственного технического университета

Рецензент: д-р. техн. наук Н. Н. С т о л я р о в

ISBN 5-7964-0625-6

Оглавление

1. Введение. 4

2. Понятие высказывания. Понятие операции. 4

3. Основные логические операции. 6

3.1. Инверсия (отрицание) 6

3.2. Конъюнкция (логическое умножение) 7

3.3. Дизъюнкция (логическое сложение) 7

3.4. Импликация (логическое следование) 8

3.5. Эквиваленция (двойная импликация) 10

3.6. Принципы доказательства тождеств. Таблица операций с двумя логическими
переменными. 11

4. Примеры практического приложения булевой алгебры. Переключательные схемы.. 13

5. Тождественные преобразования. 14

6. Дизъюнктивная и конъюнктивная нормальные формы булевой функции (дизъюнкция
конъюнкций и конъюнкция дизъюнкций) 17

7. Построение аналитического выражения булевой функции по таблице ее значений. 18

8. Минимизация логических функций, оптимизация технической реализации функций
алгебры логики. 21

9. Автоматизация процедуры считывания и минимизации логических функций с
помощью метода карт Карно. 23

Ответы.. 27

Библиографический список. 32

1. Введение

Логика как искусство рассуждений зародилась в глубокой древности. Начало науки о законах и формах рассуждений связывают с именем Аристотеля. Прошло два тысячелетия, прежде чем Лейбниц предложил ввести в логику математическую символику и использовать ее для общих логических построений. Эту идею последовательно реализовал в позапрошлом столетии Джордж Буль и тем самым заложил основы математической (символической) логики.

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

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

Во второй половине ХХ века логика получила широкое применение в технике при исследовании и разработке релейно-контактных схем, вычислительных машин, дискретных автоматов. Ее методы используются в теории преобразования и передачи информации, теории вероятностей и комбинаторном анализе. Математическая логика внедряется в такие области как экономика, биология, медицина, психология, языкознание, право.

Столь интенсивный выход математической логики за пределы математики объясняется тем, что ее аппарат легко распространяется на объекты самой общей природы, лишь бы они только характеризовались конечным числом состояний.

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

Понятие высказывания. Понятие операции

Основным объектом, изучаемым математической логикой является высказывание.

Высказывание – любое предложение, относительно которого известно, является оно истинным (И) или ложным (Л).

Примеры

1. "Наталья – мужское имя" – ложное высказывание.

2. "Сопротивление и ёмкость – параметры электрических цепей" – истинное высказывание.

3. "Среднее расстояние от Земли до Солнца составляет 150 000 000 км." – можно рассматривать как истинное или ложное высказывание в зависимости от величины допустимых погрешностей.

4. "Соблюдайте технику безопасности" – не является высказыванием.

Математическая логика не изучает содержание высказываний. Для нее существенна лишь их истинность или ложность.

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

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

Объекты с двумя возможными состояниями (в том числе и высказывания) характеризуются булевыми переменными, которые способны принимать лишь два различных значения. Для обозначения этих значений используют цифры 0 и 1 или буквы Л (ложь) и И (истина).

Отношения между булевыми переменными представляются булевыми функциями, которые (подобно числовым функциям) могут зависеть от одного, двух и более аргументов. Далее будем обозначать аргументы буквами x_i (i=1,2,…), а булевы функции буквами y_j (j=1,2,…). Булевы функции можно рассматривать как логические операции.

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

Выполняя над простыми высказываниями те или иные действия (в терминах математической логики – операции), можно образовывать сложные высказывания. Их истинность или ложность можно установить, опираясь на сведения о простых высказываниях. В разговорном языке операциям над высказываниями соответствуют логические связки "если …, то …", "… и …", "… или …", "не …" и др.

Примеры

1. "a<b", "b<c", "a<c" – простые высказывания; "Если a<b и b<c, то a<c" – сложное высказывание (подчеркнуты логические связки).

2. "Напряжение в сети 220 В", "частота 50 Гц" – простые высказывания; "напряжение в сети 220 В и частота 50 Гц" – сложное высказывание.

3. "Если начальная скорость равна нулю и ускорение а – постоянная величина, то пройденный за время t путь S вычисляется по формуле S=at²/2" – сложное высказывание. Выделим простые высказывания, составляющие данное сложное высказывание: "начальная скорость равна нулю", "ускорение а – постоянная величина", "пройденный за время t путь S вычисляется по формуле S=at²/2".

Вопросы и задания

2.1. Как определить, является ли предложение высказыванием?

2.2. Сформулируйте самостоятельно примеры истинных и ложных высказываний, а также предложений, не являющихся высказываниями.

2.3. Приведите примеры сложных высказываний. Выделите в каждом из них простые высказывания.