Математическая логика



страница1/5
Дата30.01.2013
Размер0.52 Mb.
ТипДокументы
  1   2   3   4   5
Тамбовский государственный университет им. Г.Р.Державина

Академия непрерывного образования


С.Н.Петрунина
ПОСОБИЕ ПО ДИСЦИПЛИНЕ

МАТЕМАТИЧЕСКАЯ ЛОГИКА”

Тамбов 2004
Тамбовский государственный университет им. Г.Р.Державина

Академия непрерывного образования

С.Н.Петрунина
ПОСОБИЕ ПО ДИСЦИПЛИНЕ

МАТЕМАТИЧЕСКАЯ ЛОГИКА”

Тамбов 2004

УДК

ББК

П


Рецензенты:

проректор по инновациям ТГУ им. Г. Р. Державина,

доктор педагогических наук, профессор М. С. Чванова
зав. кафедрой алгебры и геометрии ТГУ им. Г. Р. Державина,

доктор физико-математических наук, профессор А. И. Булгаков

Петрунина С.Н.

Пособие по дисциплине “Математическая логика” / С. Н. Петрунина. – Тамбов: Изд-во ТГУ им. Г. Р. Державина, 2004. – 49 с.
Пособие содержит теоретический материал по дисциплине “Математическая логика”, типовые задачи с решениями, упражнения для самостоятельной работы, контрольные вопросы курса и задания контрольных работ.

Для студентов специальностей математика, прикладная информатика в гуманитарной области, организация и технология защиты информации, изучающих дисциплину “Математическая логика” и преподавателей.

УДК

ББК
© Тамбовский государственный университет

им. Г. Р. Державина, 2004

ОГЛАВЛЕНИЕ
Предисловие

Введение

Глава I. Алгебра высказываний.

§ 1. Высказывания и логические операции над ними




§ 2. Формулы алгебры высказываний и их истинностное значение




§ 3. Основные виды формул алгебры высказываний. Законы формул алгебры высказываний




§ 4. Равносильность формул алгебры высказываний и ее свойства




§ 5. Основные равносильности формул алгебры высказываний




§ 6. Конъюнктивные и дизъюнктивные нормальные формы формул алгебры высказываний




§ 7. Проблема установления вида формул алгебры высказываний




§ 8. Совершенные конъюнктивные и дизъюнктивные нормальные формы формул алгебры высказываний




§ 9.
Применение алгебры высказываний к анализу и синтезу электрических схем




§ 10. Приложение алгебры высказываний к вопросам школьной математики




Глава II. Алгебра предикатов.




§ 1. Определение n-местного предиката и его основных видов




§ 2. Логические операции над предикатами и их свойства




§ 3. Связанные и свободные переменные. Свойства операций навешивания кванторов




§ 4. Формулы алгебры предикатов и их основные виды




§ 5. Равносильность формул алгебры предикатов. Основные равносильности алгебры предикатов.




§ 6. Приведенные и предваренные формы предикатных формул.




Задачи.




Контрольные вопросы.




Задания контрольных работ.




Рекомендуемая литература.






ПРЕДИСЛОВИЕ
Предлагаемое вниманию читателей учебное пособие предназначено студентам специальностей математика, прикладная информатика в гуманитарной области, организация и технология защиты информации, изучающим дисциплину “Математическая логика”.

Пособие состоит из двух глав, разделенных на параграфы.

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

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

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

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

Контрольные вопросы, приведенные в конце пособия, позволят читателю проверить качество усвоения теоретического материала, задания контрольных работ соответствуют уровню требований, предъявляемых к умениям и навыкам обучающихся по курсу “Математическая логика”.

Условные обозначения разъясняются в теоретической части параграфов. Для множеств комплексных, действительных, рациональных, целых и натуральных чисел используются стандартные обозначения: C, R, Q, Z и N соответственно.
ВВЕДЕНИЕ

Термин “логика” происходит от греческого слова логос, что означает “мысль”, “разум”, “слово”, “понятие”. Логика (или формальная логика) как наука изучает мышление. Но мышление изучается не только логикой, а и различными другими науками: психологией, физиологией, кибернетикой, педагогикой и так далее. Каждая из них изучает какую-то одну из сторон сложного процесса мышления. Логика есть наука о законах и формах правильного мышления. Она изучает формы рассуждений, отвлекаясь от их конкретного содержания; устанавливает что из чего следует, ищет ответ на вопрос: как мы рассуждаем?

Математическая логика называемая также символической или теоретической логикой, выросла из логики традиционной. Эта наука, с одной стороны, применила математические методы для изучения общих структур (форм) правильного мышления и тем самым оформилась как раздел математики. С другой стороны математическая логика сделала предметом своего изучения процесс доказательста математических теорем, сами математические теории. Математическая логика явилась, таким образом, инструментом для исследований в области оснований математики.

Изучение курса математической логики способствует воспитанию культуры логического мышления. Широчайшее использование компьютеров во всех сферах нашей жизни требует массового внедрения компьютерной культуры, то есть понимания возможностей компьютера и умения взаимодействовать с ним. Важнейшей составной частью этой культуры является, в первую очередь, способность и умение мыслить алгоритмически, то есть весьма отчетливо и недвусмысленно определять последовательность своих действий при решении той или иной задачи. Мышление в области математических наук всегда было наиболее алгоритмичным в сравнении с мышлением в области прочих наук. Всеобщая компьютеризация наиболее отчетливо проявила именно эту сторону математического мышления. Будущий специалист должен отчетливо осознавать неразрывную связь методов математической логики и современных компьютеров. Эти методы используются как при создании самих компьютеров (алгебра высказываний и булевы функции - математический аппарат для конструирования переключательных схем), так и при создании математического обеспечения к ним (в основе многочисленных языков программирования лежат логика предикатов и теория алгоритмов). Кроме того, синтез логики и компьютеров привел к возникновению баз данных и экспертных систем - важнейших этапов на пути к созданию искусственного интеллекта - машинной модели человеческого разума. Понимать все эти взаимосвязи, чтобы быть квалифицированным специалистом - важная задача современного студента.
Глава I. АЛГЕБРА ВЫСКАЗЫВАНИЙ.
Алгебра высказываний изучает способы построения высказываний из имеющихся высказываний, закономерности таких способов сочетания высказываний. Алгебра высказываний является фундаментом математической логики.
§ 1. Высказывания и логические операции над ними.

Понятие высказывания - одно из основных понятий математической логики. Под высказыванием понимается такое предложение, которое либо истинно, либо ложно. Например, предложение “Котовск - город Пензенской области” - высказывание, причем, ложное. “Число 7 > 10” - высказывание (ложное).

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

Предложения, которые выражают субъективное (личное) мнение не являются высказываниями, например, “Овсяная каша - вкусное блюдо” не высказывание.

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

Таким образом, определения не могут быть истинными или ложными, они лишь фиксируют принятое использование терминов.

Условимся высказывания обозначать заглавными буквами латинского алфавита А, В, С, ... Если высказывание А истинно, то говорят значение высказывания А истинно и символически это записывают так (А) = u или А = u. Если высказывание В ложно, то говорят значение высказывания В ложно и символически записывают так (В) = ? или В = ?.

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

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


А

В



АВ

АВ

АВ

АВ

u

u



u

u

u

u

u







u







u

u



u

u







u





u

u

1

2

3

4

5

6

7



Определение 1. Отрицанием высказывания А называется высказывание, обозначаемое (читается “не А” или “неверно, что А”), которое истинно тогда, когда А ложно и ложно, когда А истинно.

С помощью таблицы это определение запишем так (см. столбцы 1 и 3).

Определение 2. Конъюнкцией высказываний А и В, называется высказывание, обозначаемое А  В (читается А и В), которое истинно в единственном случае, когда оба высказывания А и В истинны и ложно в остальных случаях ( см. столбцы 1, 2 и 4).

Конъюнкции двух высказываний в обычной речи соответствует союз “и”.

Определение 3. Дизъюнкцией двух высказываний А и В, называется высказывание, обозначаемое АВ (читается “А или В”), которое истинно в тех случаях, когда хотя бы одно из высказываний А или В истинно, и ложно в единственном случае, когда оба высказывания А и В ложны (см. столбцы 1, 2 и 5).

Заметим, что операции дизъюнкция соответствует союз “или”, но только не в разделительном смысле, так как дизъюнкция истинна и тогда, когда оба высказывания истинны.

Определение 4. Импликацией двух высказываний А и В, называется высказывание, обозначаемое АВ (читается “если А, то В”, “из А следует В”, “А достаточно для В”, “В необходимо для А”), которое ложно в единственном случае, когда высказывание А истинно, а В - ложно и истинно во всех остальных случаях (см. столбцы 1, 2 и 6).

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

В записи АВ высказывание А - условие (посылка), В - заключение (следствие).

Определение 5. Эквивалентностью высказываний А и В, называется высказывание, обозначаемое АВ (читается “А эквивалентно В”, “А необходимо и достаточно для В”, “В необходимо и достаточно для А”, “А тогда и только тогда, когда В”, “А равносильно В”), которое истинно тогда и только тогда, когда оба высказывания А и В одновременно истинны или одновременно ложны и ложно в остальных случаях ( см. столбцы 1, 2, 7).

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

§ 2. Формулы алгебры высказываний и их истинностное значение.

Пусть А,В,С, ... простые высказывания, принимающие одно из двух значений И или Л.

С помощью логических операций из них можно образовать более сложные высказывания: , АВ, ВС, АВ и так далее. Из этих высказываний с помощью тех же логических операций можно образовать еще более сложные высказывания, например, ((АВ) ВС)), (АВ)( ВС), ((ВС) ).

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

В любой формуле важную роль играют скобки, которые как и в обычной алгебре определяют порядок выполнения операций. Условились внешние скобки в формулах опускать, что не влияет на порядок выполнения операций. Например, в первой и третьей написанных выше формулах внешние скобки можно опустить.

Простые высказывания могут иметь постоянные значения, то есть быть истинными или ложными, но могут и не иметь определенного значения. Тогда такие высказывания называют переменными высказываниями. Например, высказывание X>10 является переменным, так как, например, при Х=11 оно истинно, а при Х=8 оно ложно. Условимся переменные высказывания обозначать X, Y, Z, ... или X1, Х2, ..., Xn, а формулу алгебры высказываний символически записывать так F(X, Y, Z, ...) или F(X1, Х2, ..., Xn,).

Так как каждое из высказываний принимает одно значение из {И, Л}, то и формула алгебры высказываний принимает значение из этого множества.

Чтобы найти значение истинности формулы F от n высказываний, надо составить для нее таблицу истинности и из последнего столбца таблицы узнать значение истинности.

Легко установить, что таблица формулы от n высказываний содержит 2n строк истинности +1 общая строка, а число столбцов в таблице равно числу высказываний n+число операций в формуле.

П
3
ример. Составить таблицу истинности для формулы


1

2

4

F(X, Y, Z) = ((XY) Z)  Y


X

Y

Z

XY







И

И

И

И

И

Л

И

И

И

Л

И

Л

Л

Л

И

Л

И

Л

Л

И

И

Л

И

И

И

И

Л

И

И

Л

Л

Л

Л

И

И

Л

И

Л

И

Л

Л

Л

Л

Л

И

И

И

И

И

Л

Л

Л

И

Л

И

И


Из последнего столбца таблицы следует, что данная формула при всех возможных значениях истинности высказываний X, Y, Z принимает 6 раз значение истины и 2 раза значение лжи.
  1   2   3   4   5

Похожие:

Математическая логика iconРабочей программы «Математическая логика» Дисциплина ( В. Од. 1) «Математическая логика»
В. од. 1 «Математическая логика» является вариативной частью Математического и естественнонаучного цикла подготовки студентов направления...
Математическая логика iconТехнологий В. П. Битюцкий Н. В. Папуловская Математическая логика. Исчисления высказываний и предикатов Методическое пособие по дисциплине "Математическая логика и теория алгоритмов" Екатеринбург 2005 удк

Математическая логика iconМосковская государственная академия приборостроения и информатики кафедра " Персональные компьютеры и сети"
Ульянов М. В., Шептунов М. В. Математическая логика и теория алгоритмов, часть 1: Математическая логика. – М.: Мгапи, 2003. – 47...
Математическая логика iconЭкзамен по спецкурсу и спецсеминару Математическая логика
Математическая логика. Высказывания. Таблицы истинности. Основные логические операции, их свойства. Упрощение логических выражений....
Математическая логика iconРабочая программа дисциплины Математическая логика и теория алгоритмов Направление подготовки 230700 Прикладная информатика
Целями освоения дисциплины «Математическая логика и теория алгоритмов» являются получение теоретических знаний по основам математическая...
Математическая логика iconМатематическая логика
Основными разделами математической логики является: логика высказываний, логика предикатов, металогика
Математическая логика icon3 Введение. Математическая логика в системе современного образования 6
Математическая логика и теория алгоритмов: Учеб посо­бие для студ высш учеб заведений / Владимир Иванович Игошин. — М.: Издательский...
Математическая логика iconУчебная программа Дисциплины р2 «Математическая логика и теория алгоритмов»
Фгос впо, содействует формированию мировоззрения и системного мышления. Целью преподавания дисциплины «Математическая логика и теория...
Математическая логика iconПрограмма-минимум кандидатского экзамена по специальности 01. 01. 06 «Математическая логика, алгебра и теория чисел» по физико-математическим наукам
В основу настоящей программы положены следующие дисциплины: математическая логика; алгебра; теория чисел
Математическая логика icon1. Организационно-методический раздел. 1 Название курса. Математическая логика и теория алгоритмов
Основной курс "Математическая логика и теория алгоритмов" предназначен для студентов первого курса отделения прикладной инфоматики...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org