Занимательная логика в математике

Содержание

Введение  3

1.   Из истории возникновения математической логики  5

2.   Основы теории множеств  8

3. Виды логических задач  12

4.   Логические задачи и круги эйлера  14

5. Элементы логики высказываний  19

6. Решение логических задач с помощью логики высказываний  25

7. Решение логических задач с помощью таблиц  26

8. Решение логических задач с помощью кругов эйлера  29

Заключение  31

Литература  32

Введение

Логика – это Бог мыслящих.

Л. Фейхтвангер

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

В какой-то момент математики задали вопрос: «В чем, собственно, состоит математика, математическая деятельность?» Простой ответ заключается в том, что математики доказывают теоремы, то есть выясняют некоторые истины о реальном мире и «идеальном математическом мире». Попытка ответить на вопрос что такое математическая теорема, математическая истина и что такое математическое утверждение истинно или доказуемо, это и сеть исходная точка математической логики. Мы должны в школе научиться анализировать, сравнивать, выделять главное, обобщать и систематизировать, доказывать и опровергать, определять и объяснять понятии, ставить и решать проблемы. Овладение этими методами и означает умение мыслить. В науке приходится путем рассуждений выводить разнообразные формулы, числовые закономерности, правила, доказывать теоремы. Например, в 1781 г. была открыта планета Уран.  Наблюдения показали, что движение этой планеты отличается от теоретически вычисленного движения.  Французский ученый Леверье (1811-1877гг.), логически рассуждая и выполнив довольно сложные вычисления, определил влияние на Уран другой планеты и указал место ее нахождения. В 1846 г. астроном Галле подтвердил существование планеты, которая была названа Нептун. При этом они использовали логику математических рассуждений и вычислений.

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

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

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

Задачи:

1. Проанализировать литературу о сущности и возникновении математической логики.

2. Изучить элементы математической логики.

3. Подобрать и решить задачи с элементами математической логики.

Методы: анализ  литературы, понятий, метод аналогий в решении задач, самонаблюдение.

1.      Из истории возникновения математической логики

Математическая логика тесно связана с логикой и обязана ей своим возникновением. Основы логики, науки о законах и формах человеческого мышления были заложены величайшим древнегреческим философом Аристотелем (384—322 гг. до н. э.), который в своих трактатах обстоятельно исследовал терминологию логики, подробно разобрал теорию умозаключений и доказательств, описал ряд логических операций, сформулировал основные законы мышления, в том числе законы противоречия и исключения третьего. Вклад Аристотеля в логику весьма велик, недаром другое ее название - аристотелева логика. Еще сам Аристотель заметил, что между созданной им наукой и математикой (тогда она именовалась арифметикой) много общего. Он пытался соединить две эти науки, а именно свести размышление, или, вернее, умозаключение, к вычислению на основании исходных положений. В одном из своих трактатов Аристотель вплотную приблизился к одному из разделов математической логики - теории доказательств.

В дальнейшем многие философы и математики развивали отдельные положения логики и иногда даже намечали контуры современного исчисления высказываний, но ближе всех к созданию математической логики подошел уже во второй половине XVII века выдающийся немецкий ученый Готфрид Вильгельм Лейбниц (1646 - 1716), указавший пути для перевода логики «из словесного царства, полного неопределенностей, в царство математики, где отношения между объектами или высказываниями определяются совершенно точно».  Лейбниц надеялся даже, что в будущем философы, вместо того чтобы бесплодно спорить, станут брать бумагу и вычислять, кто из них прав. При этом в своих работах Лейбниц затрагивал и двоичную систему счисления. Следует отметить, что идея использования  двух символов для кодирования  информации очень стара. Австралийские аборигены  считали двойками, некоторые племена охотников-сборщиков Новой Гвинеи и Южной Америки тоже пользовались двоичной системой счета. В некоторых африканских племенах передают сообщения с помощью барабанов в виде комбинаций звонких и глухих ударов. Знакомый всем пример двухсимвольного кодирования - азбука Морзе, где буквы алфавита представлены определенными сочетаниями точек и тире. После Лейбница исследования в этой области  вели многие выдающиеся ученые, однако настоящий успех пришел здесь к  английскому математику-самоучке Джорджу Булю (1815—1864), его целеустремленность не знала границ.

Материальное положение родителей Джорджа (отец которого был сапожным мастером) позволило ему окончить лишь начальную школу для бедняков. Спустя какое-то время Буль, сменив несколько профессий, открыл маленькую школу, где сам преподавал. Он много времени уделял самообразованию и вскоре увлекся идеями символической логики. В 1847 году Буль опубликовал статью «Математический анализ логики, или Опыт исчисления дедуктивных умозаключений», а в 1854 году появился главный его труд «Исследование законов мышления, на которых основаны математические теории логики и вероятностей». Буль изобрел своеобразную алгебру  - систему обозначений и правил, применимую ко всевозможным объектам, от чисел и букв до предложений. Пользуясь этой системой, он мог закодировать высказывания (утверждения, истинность или ложность которых требовалось доказать) с помощью символов своего языка, а затем манипулировать ими, подобно тому, как в математике манипулируют числами. Основными операциями булевой алгебры являются конъюнкция (И), дизъюнкция (ИЛИ) и отрицание (НЕ). Через некоторое время стало понятно, что система Буля хорошо подходит для  описания электрических переключательных схем. Ток в цепи может либо протекать, либо отсутствовать, подобно тому, как утверждение может быть либо истинным, либо ложным. А еще несколько десятилетий спустя, уже в XX столетии, ученые объединили созданный Джорджем Булем математический аппарат с двоичной системой счисления, заложив тем самым основы для разработки цифрового электронного компьютера.  Отдельные положения  работ Буля в той  или иной мере затрагивались и  до, и после него другими математиками и логиками. Однако сегодня в данной области именно труды Джорджа Буля причисляются к математической классике, а сам он по праву считается основателем математической логики и тем более важнейших ее разделов - алгебры логики (булевой алгебры) и алгебры  высказываний.

Большой вклад в развитие логики внесли и  русские ученые П.С. Порецкий (1846-1907), И.И. Жегалкин (1869-1947).

В XX веке огромную роль в развитии математической логики сыграл

Д. Гильберт (1862-1943), предложивший программу формализации математики, связанную с разработкой оснований  самой математики. Наконец, в последние  десятилетия XX века бурное развитие математической логики было обусловлено развитием теории алгоритмов и алгоритмических языков, теории автоматов, теории графов (С.К. Клини, А. Черч, А.А Марков, П.С. Новиков и многие другие).  

В середине XX века развитие вычислительной техники привело к появлению логических элементов, логических блоков и устройств вычислительной техники, что было связано с дополнительной разработкой таких областей логики, как проблемы логического синтеза, логическое проектирование и логического моделирования логических устройств и средств вычислительной техники. В 80-х годах XX века начались исследования в области искусственного интеллекта на базе языков и систем логического программирования. Началось и создание экспертных систем с использованием и развитием автоматического доказательства теорем, а также методов доказательного программирования для верификации алгоритмов и программ для ЭВМ. В 80-ые годы начались также изменения в образовании. Появление персональных компьютеров в средних школах привело к созданию учебников информатики с изучением элементов математической логики для объяснения логических принципов работы логических схем и устройств вычислительной техники, а также принципов логического программирования для компьютеров пятого поколения и разработка учебников информатики с изучением языка исчисления предикатов для проектирования баз знаний.

2. Основы теории множеств

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

Множеством называется совокупность определенных вполне различаемых объектов, рассматриваемых как единое целое. Создатель теории множеств Георг Кантор давал следующее определение множества — «множество есть многое, мыслимое нами как целое».

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

Множества принято обозначать большими буквами латинского алфавита, а элементы этих множеств — маленькими буквами латинского алфавита. Множества записываются в фигурных скобках { }.

Принято использовать следующие обозначения:

·      a ∈ X — «элемент a принадлежит множеству X»;

·      a ∉ X — «элемент a не принадлежит множеству X»;

·      ∀ — квантор произвольности, общности, обозначающий «любой», «какой бы не был», «для всех»;

·      ∃ — квантор существования: ∃y ∈ B — «существует (найдется) элемент y из множества B»;

·      ∃! — квантор существования и единственности: ∃!b ∈ C — «существует единственный элемент b из множества C»;

·      : — «такой, что; обладающий свойством»;

·      → — символ следствия, означает «влечет за собой»;

·      ⇔ — квантор эквивалентности, равносильности — «тогда и только тогда».

Множества бывают конечные и бесконечные. Множества называются конечным, если число его элементов конечно, т.е. если существует натуральное число n, являющееся числом элементов множества. А={a₁, a₂,a ₃, ..., a_n}. Множество называется бесконечным, если оно содержит бесконечное число элементов. B={b₁,b₂,b₃, ...}. Например, множество букв русского алфавита — конечное множество. Множество натуральных чисел — бесконечное множество.

Число элементов в конечном множестве M называется мощностью множества M и обозначается |M|.Пустоемножество — множество, не содержащее ни одного элемента — ∅. Два множества называются равными, если они состоят из одних и тех же элементов, т.е. представляют собой одно и тоже множество. Множества не равны X ≠ Y, если в Х есть элементы, не принадлежащие Y, или в Y есть элементы, не принадлежащие Х. Символ равенства множеств обладает свойствами:

·      Х=Х; — рефлексивность

·      если Х=Y, Y=X — симметричность

·      если X=Y,Y=Z, то X=Z — транзитивность.

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

Подмножества. Отношение включения.

Множество Х является подмножеством множества Y, если любой элемент множества Х ∈ и множеству Y. Обозначается X⊆Y.

Если необходимо подчеркнуть, что Y содержит и другие элементы, кроме элементов из Х, то используют символ строгого включения ⊂: X⊂Y. Связь между символами ⊂ и ⊆ дается выражением:

X⊂Y ⇔ X⊆Y и X≠Y

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

1.                        X⊆Х (рефлексивность);

2.                        [X⊆Y и Y⊆Z] → X⊆Z (транзитивность);

3.                        ∅ ⊆ M. Принято считать, что пустое множество является подмножеством любого множества.

Исходное множество А по отношению к его подмножествам называется полным множеством и обозначается I.

Любое подмножество А_i множества А называется собственным множеством А.

Множество, состоящие из всех подмножеств данного множества Х и пустого множества ∅, называется булеаном Х и обозначается β(Х). Мощность булеана |β(Х)|=2ⁿ.

Счетное множество — это такое множество А, все элементы которого могут быть занумерованы в последовательность (м.б. бесконечную) а₁, а₂, а₃, ..., а_n, ... так, чтобы при этом каждый элемент получил ишь один номер n и каждое натуральное число n было бы в качестве номера дано одному и лишь одному элементу нашего множества.

Множество, эквивалентное множеству натуральных чисел, называется счетным множеством.

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

Существует 2 основных способа задания множеств.

·      перечислением (X={a,b}, Y={1}, Z={1,2,...,8}, M={m₁,m₂,m₃,..,m_n});

·      описанием — указывается характерное свойства , которым обладают все элементы множества.

Множество полностью определено своими элементами.

Перечислением можно задать только конечные множества (например, множество месяцев в году). Бесконечные множества можно задать только описанием свойств его элементов (например, множество рациональных чисел можно задать описанием Q={n/m, m, n∈Z, m≠0}.

Способы задания множества описанием:

а) заданием порождающей процедуры с указанием множества (множеств), которое пробегает параметр (параметры) этой процедуры — рекурсивный, индуктивный.

X={x: x₁=1, x₂=1, x_k+2=x_k+x_k+1, k=1,2,3,...} — мн-во чисел Фибониччи.

{мн-во элементов х, таких, что х₁=1,х₂=1 и произвольное х_k+1 (при к=1,2,3,...) вычисляется по формуле х_k+2=х_k+х_k+1} или Х=[x: x₁=1, x₂=1, x₃=2, x₄=3, x₅=5, x₆=8, ...}

б) заданием вычислительной процедуры формульной зависимости:

X = {x: x=2sin(y)+1, y∈{0, p/2}} ⇔ {1, 3}

X = {x: x²-1=0 ⇔{+1,-1}

в) заданием характеристического свойства (высказывания), выделяющего элементы данного множества из элементов других множеств — предикатный.

А={x: x — четное число}; M={x: p(x)} — множество х, обладающих свойством p

N={n: n∈Z, n>0, Z={-..., -2, -1, 0, 1, 2, ...} — множество целых чисел

K={m: m=n², n∈N} — множество всех квадратов натуральных чисел, N={1, 2, 3, ...}

X={x: 0≤x≤1, x∈N} ⇔ 1, 2, 3, ..., где N-мн-во целых чисел.

г) заданием с помощью операций над множествами — аналитический.

Отметим некоторые свойства подмножества, вытекающие из его определения:

Если X⊆Y и Y⊆X → X=Y

Для любого множества само это множество и ∅ можно рассматривать как его подмножества, называемыенесобственными. Все другие подмножества — собственные.

3. Виды логических задач

Существует множество разных логических задач. В ходе знакомства с ними, выделим несколько основных видов задач:

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

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

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

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

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

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

Задачи типа «Кто есть кто?»     Смысл задач под кодовым названием «Кто есть кто?» довольно прост. Нам даются отношения между предметами и следуя по цепочке этих отношений, мы приходим к правильному результату. Задачи данного типа чаще всего решаются методом графов.  

4.     Логические задачи и круги Эйлера

Эйлеровы круги (круги Эйлера) — принятый в логике способ моделирования, наглядного изображения отношений между объемами понятий с помощью кругов, предложенный знаменитым математиком Л. Эйлером (1707–1783).

Обозначение отношений между объемами понятий посредством кругов было применено еще представителем афинской неоплатоновской школы — Филопоном (VI в.), написавшим комментарии на «Первую Аналитику» Аристотеля.

Условно принято, что круг наглядно изображает объем одного какого-нибудь понятия. Объем же понятия отображает совокупность предметов того или иного класса предметов. Поэтому каждый предмет класса предметов можно изобразить посредством точки, помещенной внутри круга, как это показано на рисунке:

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

Такое именно отношение существует между объемами понятий «небесное тело» (А) и «комета» (B). Объему понятия «небесное тело» соответствует больший круг, а объему понятия «комета» — меньший круг. Это означает, что все кометы являются небесными телами. Весь объем понятия «комета» входит в объем понятия «небесное тело».

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

Такое именно отношение существует между объемом понятий «учащийся» и «комсомолец». Некоторые (но не все) учащиеся являются комсомольцами; некоторые (но не все) комсомольцы являются учащимися. Незаштрихованная часть круга А отображает ту часть объема понятия «учащийся», которая не совпадает с объемом понятия «комсомолец»; незаштрихованная часть круга B отображает ту часть объема понятия «комсомолец», которая не совпадает с объемом понятия «учащийся». 3аштрихованиая часть, являющаяся общей для обоих кругов, обозначает учащихся, являющихся комсомольцами, и комсомольцев, являющихся учащимися.

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

Такое именно отношение существует, например, между понятиями «тупоугольный треугольник» и «остроугольный треугольник». В объеме понятия «тупоугольный треугольник» не отображается ни один остроугольный треугольник, а в объеме понятия «остроугольный треугольник» не отображается ни один тупоугольный треугольник.

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

Такое отношение существует, например, между понятиями «родоначальник английского материализма» и «автор „Нового Органона“». Объемы этих понятий одинаковы, в них отобразилось одно и то же историческое лицо — английский философ Ф. Бэкон.

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

Такое именно отношение существует между понятиями «скрипка», «флейта», «пианино», «рояль», «барабан». Эти понятия в равной мере подчинены одному общему родовому понятию «музыкальные инструменты».

Круги, изображающие соподчиненные понятия, не должны касаться друг друга и перекрещиваться, так как объемы соподчиненных понятий несовместимы; в содержании соподчиненных понятий имеются, наряду с общими, различающие признаки. Эта схема отображает общее, что характерно для отношения любых соподчиненных понятий, взятых из различных областей знания. Это применимо к понятиям: «дом», «сарай», «ангар», «театр», подчиненных понятию «постройка»; к понятиям: «муха», «комар», «бабочка», «жук», «пчела», подчиненных понятию «насекомое» и т. д.

В тех случаях, когда между понятиями имеется отношение противоположности, отношение между объемами таких понятий отображается посредством одного круга, обозначающего общее для обоих противоположных понятий родовое понятие, а отношение между противоположными понятиями обозначается так: А — родовое понятие, B и C — противоположные понятия. Противоположные понятия исключают друг друга, но входят в один и тот же род, что можно выразить такой схемой:

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

Когда же между понятиями существует противоречащее отношение, тогда отношение между объемами понятий изображается иначе: круг делится на две части так: А — родовое понятие, B и не-B (обозначается как ¬B) — противоречащие понятия. Противоречащие понятия, исключают друг друга и входят в один и тот же род, что можно выразить такой схемой:

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

Посредством Эйлеровых кругов изображаются также отношения между объемами субъекта и предиката в суждениях. Так, в общеутвердительном суждении, выражающем определение какого-либо понятия, объемы субъекта и предиката, как известно, равны. Наглядно такое отношение между объемами субъекта и предиката изображается посредством одного круга, подобно изображению отношений между объемами равнозначащих понятий. Разница только в том, что в данном случае всегда на поверхности круга надписываются две определенные буквы: S (субъект) и P (предикат), как это показано на рисунке:

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

5. Элементы логики высказываний

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

Высказывание - это термин математической логики, которым обозначается предложение какого-либо языка (естественного искусственного), рассматриваемого лишь в связи с его истинностью.

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

Рассмотрим некоторый класс объектов и установим свойства этих объектов, а также отношения и операции над ними. Простые высказывания являются простейшим объектом логики высказываний. Рассмотрим несколько примеров простых высказываний:  «Некоторые свойства мышления не моделируются средствами современной кибернетики», «Верста больше километра», «Число 100 больше числа 10». В двузначной логике единственный способ оценки сводится к утверждению или отрицанию истинности высказывания. В такой логике есть смысл абстрагироваться от различий между суждением и высказыванием и рассматривать их как синонимы.

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

1) Если идет дождь, то солнце не светит.    2) Если ветер дует, то нет дождя.

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

Логические операции часто называют логическими связками, и для них используется система символических обозначений. Простые высказывания будем обозначать большими буквами A, B, C и т.д., и, если высказывание истинно, будем писать A=1, а если ложно, то A=0. Для булевых переменных, то есть переменных, которые принимают только два значения, называемые «истиной» (TRUE) и «ложью» (FALSE) и обозначаемые соответственно 1 и 0, определены следующие логические операции (здесь приведены различные обозначения, встречающиеся в литературе):

1) ¬ - означает логическое НЕ

2) &, и, AND – означает логическое И

3) +, или, OR – означает логическое ИЛИ

4) → - импликация

5) ↔, = - двойная импликация или эквиваленция

Операция отрицания (иногда называют операцией инверсии) является простейшей операцией логики высказываний. Если  А – истинное высказывание, то ¬А является ложным высказыванием, и наоборот, если А – ложно, то ¬А – истинно. Операция отрицания выражается словосочетанием «неверно, что» и определяется следующей таблицей истинности:

А	¬А
1	0
0	1

Операция конъюнкции (логического умножения). Соединение двух простых высказываний A и B в одно составное с помощью союза «и» называют логическим умножением или конъюнкцией, а результат операции — логическим произведением.

Конъюнктивное (соединительное) высказывание АΛВ – это высказывание, в котором утверждается наличие двух ситуаций. Например, «солнце светит и нет дождя».  Операция конъюнкции определяется с помощью следующей таблицы истинности:

А	В	АΛВ
1	1	1
1	0	0
0	1	0
0	0	0

Таким образом, сложное высказывание АΛВ истинно в том и только в том случае, когда оба высказывания А и В являются истинными. Например, пусть высказывание А – число 100 делится на 5, а высказывание В – число 100 больше 5. Тогда сложное высказывание АΛВ будет истинным.

Операция дизъюнкции (логическое сложение), соответствующая союзу «или» имеет два различных значения. Следует различать исключающее «или» и неисключающее «или».  Логическая операция, соответствующая неисключающему «или» называется дизъюнкцией и обозначается  АVВ, а полученное составное высказывание — логической суммой.  Дизъюнкция определяется следующей таблицей истинности:

А	В	АVВ
1	1	1
1	0	1
0	1	1
0	0	0

Таким образом, дизъюнкция (логическая сумма) АVВ ложна тогда и только тогда, когда оба высказывания ложны.

Например, пусть высказывание А – число 20 делится на 7, а В – число 20 больше 7, тогда сложное высказывание АVВ «число 20 делится на 7 или число 20 больше  7» будет истинным. 

Для высказывания, соответствующего исключающему «или», часто используется словосочетание «или…, или…» («либо…, либо…»). Ниже приведена таблица для дизъюнкции, соответствующей исключающему «или»:

А	В	А В
1	1	0
1	0	1
0	1	1
0	0	0

Рассмотрим два примера дизъюнкции, соответствующей неисключающему «или» и исключающему «или»:     

1) «Володя вчера в шесть часов  вечера читал книгу или ехал  в автобусе на стадион». Союз  «или» использован в этом предложении  в неисключающем смысле — Володя мог читать и одновременное ехать в автобусе. Одно не исключает другого.

2) «Володя вчера наблюдал за ходом матча с западной или  восточной трибуны». Здесь союз  «или» имеет исключающий характер  — две описываемые ситуации исключают друг друга: нельзя наблюдать один и тот же матч одновременно с двух противоположных трибун.

Импликация (логическое следование) – это одна из самых важных операций логики высказываний. Эта операция соответствует обороту «если…, то…». По определению импликация   А→ В истинна всегда за исключением случая, когда А истинно, а В ложно. Таблица истинности для операции импликация имеет следующий вид:

А	В	А→ В
1	1	1
1	0	0
0	1	1
0	0	1

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

а) если 2+3=6, то 2*2=4

б) если 2+3=6, то 2*2=5

Очень часто высказывание после слова «если» называется основанием, а после слова «то» следствием. Например, «если идет дождь, то земля мокрая». Здесь простое суждение «идет дождь» - основание, а следствие – «земля мокрая».

Эквиваленция.  Высказывание «А тогда и только тогда, когда В»

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

А	В	А↔В
1	1	1
1	0	0
0	1	0
0	0	1

Таким образом, сложное высказывание А↔В – это высказывание, в котором утверждается одновременное наличие или отсутствие двух ситуаций.

Выражается, как правило, словосочетаниями «если и только если..., то…», «в том и только в том случае, когда…», «тогда и только тогда, когда…».

Ниже приведена таблица логических операций и их перевода на естественный язык.

№	Операция	Обозначение	Истолкование
1.	Отрицание	Ᾱ, ¬А, не А	Не А;  неверно, что А
2.	Конъюнкция (логическое произведение)	АВ, АΛВ, А и В, A and B	А и В; как А, так и В; А вместе с В;  А несмотря на В;  А, в то время как В
3.	Дизъюнкция (логическая сумма), соответствующая неисключающему «или»	А+В, АVВ, A OR B, А или В	А или В; А или В или оба
4.	Дизъюнкция, соответствующая исключающему «или»	А В, ẠВ	А либо В; А или В, но не оба
5.	Импликация	А→ В	Если А, то В; В если А; В необходимо для А; А достаточно для В; А только тогда, когда В; В тогда, когда А; все А есть В
6.	Эквиваленция (двойная импликация)	А↔В, А=В	А эквивалентно В; А необходимо и достаточно для В; А тогда и только тогда, когда В; А если и только если В

Используя основные логические операции, можно построить более сложные высказывания, например,

( АΛВ) V (АΛВ) V (¬АΛ¬С), (¬(АVВ) →С) = ¬А.

Указанные высказывания называются формулами алгебры высказываний А, В,…, знаков логических операций (¬,V, Λ, →, =), а также скобок.

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

6. Решение логических задач с помощью логики высказываний

Задача 1.

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

Андреев: «Я приехал из Тольятти, а Григорьев живет в Жигулевске».

Борисов: «В Жигулевске живет Васильев. Я же прибыл из Октябрьска».

Васильев:  «Я – из Тольятти, а Борисов – из Кинеля».

Григорьев: «Я приехал из Жигулевска, а Данилов из Чапаевска».

            Данилов: «Да, я действительно из Чапаевска, Андреев же живет в Октябрьске».

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

Решение.

Рассмотрим первый возможный вариант.  Пусть первое утверждение Андреева верное, то есть он из Тольятти. Тогда Григорьев живет не в Жигулевске. Поэтому второе утверждение Данилова – ложное, значит, он из Чапаевска. Тогда первое утверждение Григорьева – ложно. Так как Андреев из Тольятти, то первое утверждение Васильева ложно, поэтому Борисов – из Кинеля. Так как Григорьев не из Жигулевска, то остается, что он из Октябрьска, а Васильев – из Жигулевска.

Рассмотрим второй возможный вариант. Пусть у Андреева второе утверждение – правильное, тогда Григорьев приехал из Жигулевска. Значит, Данилов приехал не из Чапаевска, а Андреев не из Тольятти. Тогда у Борисова первое утверждение ложное (в Жигулевске живет Григорьев), следовательно, Борисов прибыл из Октябрьска. Поэтому Андреев не из Октябрьска и получается, что Данилов – из Чапаевска. Получили противоречие: Данилов из Чапаевска и не из Чапаевска. Значит, второй вариант невозможен.

Ответ.    Андреев – из Тольятти, Борисов – из Кинеля, Васильев – из Жигулевска, Григорьев – из Октябрьска, Данилов – из Чапаевска.

7. Решение логических задач с помощью таблиц

Задача 2.

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

Из четырех офицеров – Александрова, Борисова, Васильева и Григорьева – два лейтенанта, один капитан и один майор. Александров и один из лейтенантов – танкисты, Борисов и капитан - артиллеристы, Александров младше по званию, чем Васильев. Определите род войск и воинское звание каждого из них.

Решение.

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

Фамилия                         Звание	Александров	Борисов	Васильев	Григорьев
Лейтенант
Лейтенант
Капитан
Майор

Фамилия Род войск	Александров	Борисов	Васильев	Григорьев
Танкист
Артиллерист

Звание     Род войск	Лейтенант	Лейтенант	Капитан	Майор
Танкист
Артиллерист

-

Используя данные задачи, поставим 1 на пересечении Борисов – артиллерист, Александров – танкист,  лейтенант – танкист, капитан – артиллерист. Тогда Борисов – не танкист и не капитан. Капитан не танкист. Александров – не артиллерист и не капитан. Поставим соответственно 0 на пересечении данных слов в таблицах. Тогда получим:

Фамилия Звание	Александров	Борисов	Васильев	Григорьев
Лейтенант
Лейтенант
Капитан	0	0
Майор

Фамилия Род войск	Александров	Борисов	Васильев	Григорьев
Танкист	1	0
Артиллерист	0	1

Звание Род войск	Лейтенант	Лейтенант	Капитан	Майор
Танкист			0
Артиллерист			1

Александров не капитан и не майор (так как младше по званию, чем  Васильев), значит он лейтенант. Получается, что оба лейтенанта танкисты, а Борисов – артиллерист, значит он не лейтенант. Так как Борисов не лейтенант и не капитан, то он майор. Тогда Васильев – капитан, поэтому он – артиллерист. Григорьев, значит, лейтенант и танкист.

В результате постепенного заполнения получаем следующие таблицы:

Фамилия Звание	Александров	Борисов	Васильев	Григорьев
Лейтенант	1	0	0	0
Лейтенант	0	0	0	1
Капитан	0	0	1	0
Майор	0	1	0	0

Фамилия Род войск	Александров	Борисов	Васильев	Григорьев
Танкист	1	0	0	1
Артиллерист	0	1	1	0

Звание Род войск	Лейтенант	Лейтенант	Капитан	Майор
Танкист	1	1	0	0
Артиллерист	0	0	1	1

Ответ:  Васильев и Борисов -  капитан и майор артиллерии, Александров и Григорьев – лейтенанты танковых войск.

8. Решение логических задач с помощью кругов Эйлера

Задача 3

Из  90 туристов, отправляющихся в  путешествие, немецким языком владеют 30 человек, английским – 28, французским – 42. Английским и немецким одновременно владеют 8 человек, английским и французским -10 , немецким и французским – 5, всеми тремя языками – 3. Сколько туристов не владеют ни одним языком?

Решение:

  

Английским и французским языками владеют 10 человек, а 3 из них владеют ещё и немецким. Значит, английским и французским владеют 10 – 3 = 7 (человек)

В общую часть английского и французского кругов  вписываем число 7. Английским и немецким языками владеют 8 человек, а 3 из них владеют ещё и французским. Значит, английским и немецким владеют 8 – 3 = 5 (человек). В общую часть английского и немецкого кругов вписываем число 5

Немецким и французским языками владеют 5 человек, а 3 из них владеют ещё и английским. Значит, немецким и французским владеют 5 – 3 = 2 (человека). В общую часть немецкого и французского кругов  вписываем число 2

Известно, что немецким языком владеют 30 человек, но 5+3+2=10 из них владеют и другими языками, значит, только немецкий знают 20 человек.

Английский язык знают 28 человек, но 5+3+7=15 человек владеют и другими языками, значит, только английский знают 13 человек.

Французский язык знают 42 человека, но 2+3+7=12 человек владеют и другими языками, значит, только французский знают 30 человек.

По условию задачи всего 90 туристов. 20+30+13 +5+2+3+7 = 80 туристов знают хотя бы один язык, следовательно,  10 человек не владеют ни одним языком.

Ответ:    10 человек.

Заключение

•    Использование элементов математической логики позволяет учащимся гораздо быстрее найти нужные решения задач.

•    Класс логических задач является самым разнообразным, как по типам, так и по методам решения.

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

Литература

1. Виленкин Н.Я., В.В. Фирсов и др. Факультативный курс. Избранные вопросы математики. М.: Просвещение 1998 – 192 с.

2. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов / В.И. Игошин. – 3-е изд., стер. – М.: Издательский центр «Академия», 2007. – 304 с.

3. Математическая логика // Википедия / http://ru.wikipedia.org

4. Успенский В.А., Верещагин Н.К., Плиско В.Е. Вводный курс математической логики. 2-е изд. – М.: Физматлит, 2002. – 128 с.

5.  Фарков А.В.  Методы решения олимпиадных задач. 10-11 классы. – М.: ИЛЕКСА, 2011. – 110 с. (Серия «Математика: элективный курс»).