ХКОИС
ХРРЦ
Регистрация
Забыли пароль?
Логин:
Пароль:
Поиск
Справочные сведения о системе образования Хабаровского края
Новости образования Хабаровского края
Информация и документы из министерства образования и науки Хабаровского края
Хабаровская краевая заочная физико-математическая школа
РЕГИОНАЛЬНАЯ ОЛИМПИАДА ШКОЛЬНИКОВ
Подготовка к олимпиадам по информатике
Подготовка к олимпиадам по информатикеТеоретические материалы > Элементы математической логики
Элементы математической логики
§ 1.Введение
Логика как наука сформировалась в IV веке до нашей эры. Ее создал древнегреческий ученый Аристотель, его ученики и последователи. Аристотель исследовал различные формы суждений и их комбинации и ввел понятие силлогизма – рассуждения, в котором из двух заданных рассуждений вида  «все a суть b», «некоторые a суть b», «все a не суть b», «не все a суть b» выводится третье. Силлогизмы бывают правильными и неправильными. Пример правильно силлогизма: «Все ноутбуки – компьютеры. Все компьютеры имеют процессор. Следовательно, все ноутбуки имеют процессор». Пример неправильного силлогизма: «Все компьютеры являются электрическими приборами. Некоторые электрические приборы являются утюгами. Значит – некоторые компьютеры являются утюгами». Доказано, что общее число силлогизмов, которые можно составить из суждений указанного вида, равно 256, из них правильных  всего 24. В XVIII веке  великий математик Эйлер предложил очень простой метод проверки правильности силлогизмов — геометрической иллюстрации логических рассуждений, который впоследствии был назван диаграммами Эйлера-Венна. Согласно этому методу, каждое суждение можно изобразить в виде геометрической фигуры. Так, суждение «все a суть b» изображено на рисунке 1, «некоторые a суть b» — на рисунке 2, «все a не суть b» — на рисунке 3, и «не все a  суть b» — на рисунке 4.
Логика, основанная на теории силлогизмов, называется классической логикой. В течение многих веков логика практически не развивалась, и лишь в XVII веке немецкий ученый Лейбниц задумал создать новую логику, в которой каждому понятию соответствовал бы символ, а рассуждения имели вид вычислений. Только в середине XIX века эти идеи воплотил в жизнь Дж. Буль, который создал алгебру логики. С этого времени начала развиваться новая наука – математическая логика, которая использует язык и методы математики.
§ 2. Логика высказываний
1.      Высказывания
Основным понятием математической логики является высказывание – любое повествовательное предложение, про которое известно, является оно истинным или ложным. Высказывания могут быть описаны либо с помощью слов, либо некоторых символов. Например, являются высказываниями:
а) «сумма чисел 2 и 5 равна 7» (истинное высказывание),
б) «2 + 5 = 7» — предыдущее высказывание, записанное с помощью математических символов,
в) «для всех значений x верно неравенство  » (ложное высказывание),
г) «завтра будет солнечный день» (может быть истинным или ложным).
Высказывания обозначаются заглавными буквами латинского алфавита – A, B и т.д.
Не всякое предложение является высказыванием, например, восклицательные или побудительные предложения не являются высказываниями. Также не являются высказываниями определения – они лишь дают название некоторому объекту, но не могут быть истинными или ложными. Кроме высказываний существуют еще высказывательные формы – предложения, содержащие переменную. Например, выражение «» является высказывательной формой, так как при некоторых значениях переменной эта форма становится истинным высказыванием, а при других значениях – ложным.
2.      Простые и сложные высказывания
Выше мы говорили, что высказывание имеет вид  повествовательного предложения. Из двух таких предложений можно получить новые с помощью логических связок – союзов «и», «или», « если…,то», «тогда и только тогда, когда»  и частицы «не». Такие предложения будем называть составными. Предложения, не являющиеся составными, называются элементарными. Соответственно, если можно судить об истинности или ложности таких предложений, то они будут называться простыми и составными высказываниями. Например, высказывание «число делится на три тогда и только тогда, когда сумма цифр этого числа делится на три» является составным высказыванием (оно является истинным и в математике известно как признак делимости числа на три).
С точки зрения грамматики различают простые и сложные предложения. Например, предложение «число 10 делится на 2 и на 5» является простым, хотя с точки зрения математической логики это – сложное высказывание, состоящее из двух простых высказываний «число 10 делится на 2», «число 10 делится на 5», полученное с помощью логической связки «и».
3.      Логические операции над высказываниями
Аналогично тому, как в алгебре чисел используются операции сложения, вычитания, умножения, деления, в алгебре высказываний вводятся специальные операции, которые имеют названия логического сложения (дизъюнкции), логического умножения (конъюнкции), отрицания, импликации и эквиваленции. Рассмотрим подробно.
а). Конъюнкция и дизъюнкция
Пусть А и В – произвольные высказывания. Введем символ  для обозначения логической связки «и». Сложное высказывание «А и В» считается истинным лишь в том случае, если оба исходных высказывания  истинны. Если же хотя бы одно из исходных высказываний ложно, то сложное высказывание «А и В» считают ложным.
Определение. Высказывание «А и В», истинное, если истинны оба высказывания А и В, и ложное, если хотя бы одно из них ложно, называется конъюнкцией этих высказываний и обозначается АВ.
Запишем это определение в специальной форме, которая называется таблицей истинности. В ней для каждого значения истинности «И» (истина) или «Л» (ложь) логических высказываний А и В определяется значение истинности высказывания АВ.
Введем символ  для обозначения логической связки «или». Сложное высказывание «А или В» условимся считать ложным в том и только в том случае, когда оба высказывания А и В ложны.
Определение. Высказывание «А или В», истинное, если истинно хотя бы одно из высказываний А или В, и ложное лишь в одном случае, когда оба высказывания А и В ложны, называется дизъюнкцией этих высказываний и обозначается АВ.
Таблица истинности для высказывания АВ выглядит следующим образом:
А
В
АВ
И
И
Л
Л
И
Л
И
Л
И
И
И
Л
в). Отрицание
 Логическая операция, соответствующая логической связке «не», называется отрицанием.
Определение. Высказывание «не А», истинное лишь в том случае, когда высказывание А ложно и ложное лишь в том случае, когда высказывание А истинно, называется отрицанием А и обозначается .
Таблица истинности для высказывания  выглядит следующим образом:
 А
И
Л
Л
И
с). Импликация и эквиваленция
Логические рассуждения чаще всего имеют форму цепочки высказываний. Эти высказывания имеют условный характер, то есть, утверждают, что некоторое высказывание истинно при условии, что истинно другое высказывание. Например, «если два угла одного треугольника соответственно равны двум углам другого треугольника, то эти треугольники подобны». В общем виде такого рода высказывания записываются следующим образом «если А, то В» и называются импликацией. Высказывание А в этом случае называют условием, а высказывание В заключением.
Определение. Импликацией высказываний А и В называют высказывание  (читается «если А, то В»), ложное лишь в случае, когда А истинно, а В – ложно.
Таблица истинности для высказывания  выглядит следующим образом:
 
А
В
И
И
Л
Л
И
Л
И
Л
И
Л
И
И
Определение. Эквиваленцией высказываний А и В называют высказывание  (читается «А тогда и только тогда, когда  В»), истинное, в том и только в том случае, когда оба эти высказывания истинны, или оба ложны.
Таблица истинности для высказывания  выглядит следующим образом:
 А
В
И
И
Л
Л
И
Л
И
Л
И
Л
Л
И
 
§ 3. Алгебра логики
1. Язык и формулы логики высказываний        
Из данных высказываний А, В, С можно с помощью логических операций составить новые высказывания, которые будут истинны или ложны.  Раздел математической логики, в котором изучают свойства выражений, составленных из высказываний с помощью логических операций, называется алгеброй высказываний.
Пусть X, Y, Z– переменные, обозначающие элементарные логические высказывания или их значения истинности. Такие переменные будем называть логическими (или высказывательными) переменными. С помощью логических переменных и символов логических операций можно формализовать любое логическое высказывание. Таким образом, логическое высказывание заменяется формулой, отражающей логическую структуру этого высказывания. Например, высказывание «Число а делится на 6 тогда и только тогда, когда а делится на 2, и а делится на 3» формализуется в виде .
Дадим теперь строгое математическое определение формулы логики высказываний. Это определение имеет вид конструктивного (или индуктивного) определения.
Определим алфавит, то есть, набор символов, которые употребляются в логике высказываний:
1.  (i – индекс, значения которого – натуральные числа) – символы для обозначения логических переменных,
2. И, Л – символы, обозначающие логические константы «истина», «ложь»,
3.  - символы логических операций,
4. (, ) – скобки, вспомогательные символы, служащие для указания порядка выполнения логических операций.
Дадим определение формулы  логики высказываний:
1.      Всякая логическая переменная  есть формула.
2.      Символы И, Л есть формулы.
3.      Если  есть формула, то  есть формула.
4.      Если  есть формулы, то , , ,  есть формулы.
5.      Никаких других формул в логике высказываний нет.
Для формализации высказываний используют следующий алгоритм.
Алгоритм формализации высказываний.
  1. Если высказывание – простое, то ему ставится в соответствие элементарная формула.
  2. Если высказывание – составное, то для составления формулы требуется:
а) выделить все элементарные высказывания и логические связки, образующие данное высказывание,
в) заменить их соответствующими символами,
с) расставить скобки в соответствии со смыслом данного высказывания.
Пример 1. Формализовать высказывания: а)  «Неверно, что число 500 делится на 3 или на 13», в) «тогда и только тогда, когда ».
Решение. а). Обозначим простые высказывания: X – « число 500 делится на 3», Y –  «число 500 делится на 13». Тогда данное сложное высказывание имеет вид ,
в). Обозначим простые высказывания: X– « », Y – «», Z – «». Тогда данное высказывание имеет вид .
2. Составление таблиц истинности для формул логики высказываний
 
 

Пусть  - некоторая формула логики высказываний. Если каждой переменной, входящей в эту формулу, приписать одно из значений истинности, то, пользуясь таблицами истинности логических операций, можно найти значение истинности и формулы  при заданном наборе значений ее переменных. Это можно сделать, построив граф вершинами которого будут логическая переменная или логическая формула, а над ребрами графа проставим значения истинности каждого высказывания. Например, найдем значения истинности формул примера 1 а). (рис. 5)
Наиболее удобной формой записи является таблица истинности.
Пример 2. Найдем значения истинности формул примера 1.
Решение.  а). Составим таблицу истинности для формулы 
X
Y
И
И
И
Л
И
Л
И
Л
Л
И
И
Л
Л
Л
Л
И
                        в). Составим таблицу истинности для формулы 
X
Y
Z
И
И
И
И
И
И
И
Л
Л
Л
И
Л
И
Л
Л
Л
И
И
И
Л
И
Л
Л
Л
Л
Л
И
Л
Л
И
Л
Л
И
Л
И
Л
Л
Л
Л
И
§ 4. Язык и метаязык. Искусственные языки
Формализацию высказываний можно рассматривать как перевод с естественного языка на искусственно сознанный язык формальной логики. Существует много искусственных языков, например, языки программирования. Они необходимы в тех случаях, где недопустима многозначность, синонимичность, присущая естественным языкам. Так обстоит дело при общении с ЭВМ – она не может выбрать нужное значения из множества слов-синонимов. Многозначность слов естественного языка несовместима с точностью и надежностью логического анализа.
Искусственные языки, создаваемые для нужд логики, называются формализованными языками. Формализованный язык строится следующим образом: задается алфавит языка – символы, которые используются в языке. Каждая последовательность символов называется словом. Затем вводится синтаксис, то есть набор правил, с помощью которых из всех слов языка выделяются специальные слова, называемые формулами. Например, построенный выше язык логики высказываний, является формализованным языком.
Когда мы строим формализованный язык, то употребляем слова естественного языка, а также некоторые символы, не входящие в алфавит формализованного языка. Так, например, при описании формул логики высказываний, мы пользовались словами русского языка, а также символами , F, не входящими в алфавит этого формализованного языка. Когда о некотором языке  говорят, используя язык , то язык  по отношению к  называется метаязыком, а  по отношению к  называется языком-объектом. Иногда слова метаязыка и языка-объекта звучат одинаково. Так, например, происходит, если учебник по языку «Паскаль» написан на английском языке. В этом случае, слова языка-объекта некоторым образом выделяются (например, берутся в кавычки). В логике такое разделение слов обоих языков необходимо.
Например, сравним два высказывания: 1). «Парабола является  графиком квадратичной функции. Парабола имеет уравнение , где . Значит, парабола является графиком квадратичной функции и имеет уравнение , где », 2). «Парабола является  графиком квадратичной функции. Парабола состоит из 8 букв. Значит, парабола является  графиком квадратичной функции и состоит из  8 букв». Эти высказывания одинаковы по форме, но в высказывании «Парабола состоит из 8 букв»  слова неравнозначны – первое принадлежит языку-объекту, а второе – метаязыку. Неразличение слов языка-объекта и метаязыка приводит к ряду парадоксов, известных еще ученым древности. Например, требуется выяснить, истинно или ложно высказывание «Ложь то, что я голоден». Если признать истинным факт, что я голоден, то высказывание- ложное и наоборот. Таким образом, при построении формализованных языков должна исключаться возможность смешивания языка-объекта и метаязыка.
Copyright © 2005–2017 ХабЦНИТ ТОГУ Отправить письмо
Создание сайтов в Хабаровске
Оптимальный тур в Доминикану из Киева предполагает проживание в уютной гостинице не высокого класса. . купоны ebay