Игошин Математическая логика и теория алгоритмов (1019110), страница 4
Текст из файла (страница 4)
Важно также понимание сути необходимых и достаточных условий, прямой и обратной теорем и их различных видов. Кроме того, необходимо научиться определять, какие утверждения равносильны каким, т.е. научиться преобразовывать структуру математического утверждения равносильным образом. Чем больше усвоено логических равносильностей, тем выше логическая культура учителя. 2. Принцип обучения понятию доказательства математической теоремы. В этом случае важно уяснить, что доказательство теоремы — это последовательность (цепочка) утверждений, каждое из которых есть либо условие теоремы, либо аксиома, либо получено из двух предыдуших утверждений последовательности по правилу вывода: из утверждений А и А — > В следует утверждение В.
Построив такую цепочку, мы доказываем, что из А выводится В, в результате чего делаем вывод, что справедлива теорема А — ~ В. Обоснованием этому переходу служит логическая теорема о дедукции. Всякий раз при доказательстве теоремы нужно стремиться к тому, чтобы цепочка последовательных утверждений вырисовывалась в сознании учащегося как можно более отчетливо. 3. Принцип обучения методам доказательства математических теорем. В первую очередь необходимо, научиться методам построения цепочки утверждений А = А,, А,, ..., А„= В для доказательства теоремы А — > В. Синтетический (или прямой) метод— построение цепочки в прямом направлении, т.е. от А к В.
Аналитический метод (или метод восходящего анализа) — построение цепочки в обратном направлении, т.е. от В к А. Далее необходимо уяснить, что для доказательства теоремы А — > В достаточно доказать теорему - В + — А или (А л В) -~ А или (А л В) -+ В (варианты метода доказательства от противного), вместо теоремы А достаточно доказать теорему ( А — > (В л — В)) — > А (метод приведения к абсурду), а вместо теоремы А — ~ С вЂ” две теоремы А -+ В и  — > С (метод цепного заключения) и т.д. 4. Принцип обучения строению математических теорий.
Имеется в виду уяснение сути аксиоматического метода при построении математической теории и при ее преподавании, а также уяснение сути первоначальных (неопределяемых) понятий теории, ее аксиом и теорем, вплоть до метатеории (свойств этой теории)— !3 непротиворечивости, полноты, категоричности, независимости системы аксиом.
Важно также знание аксиоматических теорий, лежащих в основе школьных математических курсов: аксиоматических построений геометрии на основе систем аксиом Евклида, Гильберта, Вейля и т.д.; аксиоматической теории числовых систем как основания школьного курса алгебры и начал анализа. Математическая логика помогает обосновать и облегчает применение указанных логических принципов. Они должны органично войти в сознание всякого преподающего и изучающего математику, так как при несоблюдении данных принципов при обучении математике изучаемый предмет рискует утратить те качества и черты, которые, собственно, и выделяют его из системы прочих наук.
Математическая логика и современные ЭВМ. Широчайшее распространение компьютеров, проникших буквально во все сферы жизни, связано с насущной проблемой развития и поддержания массовой компьютерной культуры, начиная с самого раннего возраста. Важно, чтобы росло понимание возможностей компьютера и умение взаимодействия с ним, чтобы молодые люди развивали свои способности и умение мыслить алгоритмически, т. е. отчетливо и однозначно могли определять последовательность своих действий при решении той или иной задачи.
Развитие мышления в области математических наук всегда было в наибольшей степени алгоритмичным по сравнению с прочими науками, тем не менее всеобщая компьютеризация еще более отчетливо выявила эту сторону математического мышления. Математическая логика, в частности ее раздел, посвященный теории алгоритмов, являются важнейшими составляющими теоретических основ алгоритмического мышления. Не менее тесная связь методов математической логики и современных компьютеров прослеживается по следующим двум направлениям. Эти методы используются как при физическом конструировании и создании компьютеров (алгебра высказываний и булевы функции — математический аппарат для конструирования переключательных и функциональных схем, составляющих элементную базу компьютеров), так и при создании математического обеспечения к ним.
В основе многочисленных языков программирования лежат теория алгоритмов, теория формальных систем, логика предикатов. Например, название языка ПРОЛОГ означает сокращение от слов «ПРОграммирование ЛОГическоеж Кроме того, синтез логики и компьютеров привел к возникновению баз данных и экспертных систем, что явилось важнейшим этапом на пути к созданию искусственного интеллекта — машинной модели человеческого разума. Понимание всех этих взаимосвязей неотделимо от современного высшего математического, технического и педагогического образования. Глава 1 АЛГЕБРА ВЫСКАЗЫВАНИЙ Высказывание — первый важнейший объект изучения математической логики.
Алгебра высказываний изучает способы построения высказываний из уже имеющихся высказываний, закономерности таких способов сочетания высказываний. Алгебра высказываний является фундаментом математической логики. $1. Высказывания и операции над ними Понятие высказывания. Предметом исследования алгебры высказываний являются высказывания. Но алгебра высказываний не ставит целью их всестороннее изучение. Из многочисленных свойств высказывания алгебру высказываний интересует лишь одно: истинно оно или ложно.
Именно это и является определяющим свойством высказывания. Итак, под высказыванием понимается такое предложение, которое либо истинно, либо ложно. Высказывание не может быть одновременно и истинным, и ложным. В дальнейшем будем считать, что имеется первоначальная совокупность некоторых простейших высказываний, называемых элементарными или исходными, о каждом из которых точно известно, истинно оно или ложно. Причем в этой совокупности имеются как истинные высказывания, так и ложные.
Примеры предложений, являющихся высказываниями, и предложений, таковыми не являющимися, приведены в Задачнике', М 1.1. Договоримся обозначать конкретные высказывания начальными заглавными буквами латинского алфавита А, В, С, Р, ... или теми же буквами с индексами внизу. Приведем примеры высказываний, которые будут использованы в дальнейшем: А|. «Москва — столица России»; Ат'. «Саратов находится на берегу Невы»; Аз: «Все люди смертны»; А4-. «Сократ — человек»; Ат. '«7 < 4»; » В.И.З,, м ритмов.
— М., 2004. 15 Аа. '«Волга впадает в Каспийское море»; Ат; «А, С, Пушкин — великий русский математик»; А,: «Снег белый». Обозначив истинное высказывание символом 1, а ложное — О, введем функцию д, заданную на совокупности всех высказываний и принимающую значения в двухэлементном множестве (О, 1), по следующему правилу: !1, если высказывание Р истинно, '(О, если высказывание Р ложно.
Функция ) называется функцией истинности, а значение д(Р)— логическим значением или значением истинности высказывания Р. Для приведенных высказываний имеем логические значения ) (А!) = 1, з(Аз) = 0 )~(Аз) = 1 3.(А«) = 1, ЦАз) = О, т"(Аа) = 1~ ЦАг) = О, ~ (Аа) Отметим, что в литературе имеются следующие обозначения для истинных высказываний: 1, И, г (от англ. ! ие — истинный) и для ложных высказываний: О, Л, 1 (от англ.
1о!ле — ложный). Из этих обозначений будем использовать 1 и О. Это обусловлено рядом причин. Во-первых, таблицы истинности для формул алгебры высказываний принимают более лаконичный и стандартизированный вид, так как в этом случае наборы значений пропозициональных переменных (см. в 2) можно расположить в порядке возрастания чисел, которые этими наборами закодированы в двоичной системе счисления. Например, для случая трех пропозициональных переменных Х У, У набор значений этих переменных 000 означает двоичную запись десятичного числа О, набор 001— двоичную запись десятичного числа 1, набор 010 — двоичную запись десятичного числа 2, 011 — 3, 100 — 4, 101 — 5, 110 — 6, 111 — 7.
Во-вторых, более удобный и математически строгий вид принимают многие формулы и алгоритмы алгебры высказываний. В-третьих, обозначение 0 и ! принято и более целесообразно в приложениях математической логики к компьютерам и информатике. Из элементарных высказываний с помощью операций над высказываниями или логических связок строят сложные высказывания. Перейдем к точному описанию таких построений.
Отрицаиие высказывания. Определение 1.1.' Отрицанием высказывания Р называется новое высказывание, обозначаемое ~ Р(читается: «не Р» или «не верно, что Р»), которое истинно, если высказывание Рложно, и ложно, если высказывание Р истинно. Другими словами, логическое значение высказывания — Р связа- ' В книге принята нумерация всех элементов по параграфам. Так, в обозначении «Определение !.
!» первая цифра указывает на номер параграфа, в котором находится данный элемент, вторая — на порядковый номер элемента в данном параграфе. 16 но с логическим значением высказывания Р, как указано в следу- ющей таблице, называемой таблицей истинности операции отри- цания: Здесь может возникнуть вопрос, почему приписывание истинности или ложности высказыванию -Р осуществляется именно на основании приведенной таблицы. Конечно, можно ответить, что об определениях не спорят.
Но ведь мы желаем построить математическую теорию (алгебру выказываний), которая в какой-то мере отражала бы реально существующий в природе человеческого мышления процесс построения составных высказываний из элементарных и имела бы реальный смысл. Затем мы должны будем развить нашу математическую теорию, а полученные выводы применить в практике мышления и при этом не войти в противоречие с общеизвестными законами мышления. Определение отрицания с помощью приведенной таблицы (как, впрочем, и других логических связок с помощью соответствующих таблиц, о чем речь пойдет далее) появилось как результат длительного опыта, и оно полностью оправдало себя на практике.
Пример 1.2. Применим операцию отрицания к высказыванию Аъ.' «Волга впадает в Каспийское море». Данное отрицание можно читать так: «Неверно, что А,» т.е. «Неверно, что Волга впадает в Каспийское море». Или же частицу «не» переносят на такое место (чаще всего ставят перед сказуемым), чтобы получилось правильно составленное предложение: «Волга не впадает в Каспийское море». Таблица из определения 1.1 дает для данного высказывания следующее логическое значение: Х(- Аъ) = -А(А«) = 1 = О, т.е. высказывание — Аъ ложно.
Ложность высказывания — Аъ обусловлена только истинностью исходного высказывания Аъ и определением 1.1, но никак не соображениями смысла (содержания) высказывания -А«. Другое дело, что само определение 1.1 потому и имеет такую формулировку, что оно правильно (или, как говорят, адекватно) отражает факты, известные нам из практики. Конъюнкция двух высказываний. Определение 1 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
