Дипломная работа

«Технологии повторения учебной темы. Логика высказываний»

СОДЕРЖАНИЕ

• Введение
• 1. Основные понятия и операции логики высказываний. Способы решения логических задач
• 1.1 Виды логических операций
• 1.1.1 Исторический аспект

1.1.2 Определение понятий логики высказываний

1.1.3 Логические операции над высказываниями

1.2 Формы записи высказываний. Алгоритмические способы решения логических задач

1.2.1 Формулы логики высказывания и их свойства

1.2.2 Нормальные формы. Совершенные нормальные формы

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

1.3 Эвристические методы решения логических задач

1.3.1 Прием конкретизации задачи

1.3.2 Прием переструктурирования задачи

1.3.3 Прием разбиения задачи на части

1.3.4 Приемы моделирования

2. Повторение, его виды и способы реализации в учебном процессе

2.1 Виды повторения

2.1.1 Обобщающее повторение

2.1.2 Методические рекомендации к проведению обобщающего повторения

2.2 Требования к повторению

2.2.1 Требования к организации повторения

2.2.2 Принцип непрерывного повторения

2.3 Методы, приемы и формы повторения

2.3.1 Формирование умений и навыков применения приемов мыслительной деятельности

2.3.2 Формы повторения

3. Безопасность жизнедеятельности

3.1 Анализ негативных факторов в учебном кабинете математики №207 школы №14

3.2 Микроклимат и его влияние на организм человека

3.3 Анализ возможных чрезвычайных ситуаций

Заключение

Список используемой литературы

Приложение А. Схема учебного материала темы «Логика высказываний»

Приложение Б. Схематическое содержание технологий повторения

Приложение В. Вопросы к теме «Логика высказываний»

Приложение Г. Тестовые задания к теме «Логика высказываний»

Приложение Д. Перечень задач по теме «Логика высказываний»

Приложение Е. Описание программы решения логических задач «Логика»

ВВЕДЕНИЕ

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

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

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

Поэтому целью дипломной работы является разработка технологий повторения темы «Логика высказываний».

Задачами данной дипломной работы являются анализ содержания учебной темы «Логика высказываний» и исследование технологии повторения при изучении темы «Логика высказываний».

В первой главе дипломной работы раскрывается содержание учебной темы «Логика высказываний». Описываются основные понятия и операции логики высказываний, а также способы решения логических задач (алгоритмические и эвристические).

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

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

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

1 ОСНОВНЫЕ ПОНЯТИЯ И ОПЕРАЦИИ ЛОГИКИ ВЫСКАЗЫВАНИЙ. СПОСОБЫ РЕШЕНИЯ ЛОГИЧЕСКИХ ЗАДАЧ

1.1 Виды логических операций

1.1.1 Исторический аспект

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

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

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

«Мы употребляем знаки не только для того, чтобы передать наши мысли другим людям, но и для того, чтобы облегчить сам процесс нашего мышления» (Лейбниц).

Первая реализация идеи Лейбница принадлежит английскому математику Дж.Булю (1815-1864 г.).

Буль создал алгебру, в которой буквами обозначены высказывания, и это привело к алгебре высказываний. Сочинение Дж.Буля, в котором подробно исследовалась эта алгебра, было опубликовано в 1854 г., то есть почти 150 лет тому назад. Оно называлось «Исследование законов мысли» («Investigation of the Laws of Thought»). Отсюда ясно, что Буль рассматривал свою алгебру как инструмент изучения законов человеческого мышления, то есть законов логики.

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

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

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

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

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

В этом отношении показательны работы немецкого математика Г.Фрёге (1846-1925 г.) и итальянского математика Д.Пеано (1858-1932 г.), которые применили математическую логику для обоснования арифметики и теории множеств.

Уже начиная с этих работ, стало ясно, что математическая логика изучает основания математики, принципы построения математических теорий. В этом ее главная роль. Коротко говоря - математическая логика - это наука о средствах и методах математических доказательств [3].

Математическая логика сама стала областью математики, поначалу казавшейся в высшей степени абстрактной и бесконечно далекой от практических приложений. Однако эта область недолго оставалась уделом «чистых» математиков. В начале нынешнего века П.С. Эренфест указал на возможность применения аппарата логики высказываний (раздела математической логики) в технике. В середине столетия была обнаружена теснейшая связь математической логики с новой наукой - кибернетикой. Эта связь открыла возможности многочисленных и разнообразных приложений математической логики. Достаточно сказать, что сегодня математическая логика используется в биологии, медицине, лингвистике, педагогике, психологии, экономике, технике. Чрезвычайно важна роль математической логики в развитии вычислительной техники: она используется в конструировании электронно-вычислительных машин (ЭВМ) и при разработке искусственных языков для общения с машинами.

Математическая логика уточнила и по-новому осветила понятия и методы традиционной формальной логики, существенно расширила ее возможности и сферу применимости [4].

1.1.2 Определение понятий логики высказываний

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

Среди осмысленных предложений в русском языке выделяют повествовательные предложения, как выражения, которые утверждают некоторый факт. Аналогом повествовательных предложений в логике высказываний является высказывание (формула) [2].

Высказыванием называется повествовательное предложение, о котором можно сказать в данный момент, что оно истинно или ложно, но не то и другое одновременно. Истинность или ложность предложения есть истинное значение высказывания [5].

Каждое высказывание можно однозначно классифицировать - истинно оно или ложно. Если мы введем в рассмотрение множество, состоящее из двух элементов - русских слов «истина» и «ложь» (или английских «true» и «false»), которые записывают сокращенно И, Л (или соответственно Т, F), - то элементы этого множества {И, Л} часто называют истинностными значениями. Вместо И и Л мы будем использовать обозначения 1 и 0 соответственно, не придавая этим символам никакого арифметического смысла [2].

Приведем примеры высказываний.

1) Москва - столица России.

2) Волга впадает в Черное море.

3) Новгород стоит на Волхове.

4) Курица не птица.

5) Число 8 делится на 2 и на 4.

Высказывания 1), 3) и 5) истинны, а высказывания 2) и 4) ложны.

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

Не являются высказываниями и такие предложения: «Каша - вкусное блюдо», «Математика - интересный предмет»; нет, и не может быть единого мнения о том, истинны эти предложения или ложны. Предложение «Существуют инопланетные цивилизации» следует считать высказыванием, так как объективно оно либо истинное, либо ложное, хотя никто пока не знает, какое именно. Предложения «Шел снег», «Площадь комнаты равна 20 м²», а²=4 не являются высказываниями; для того чтобы имело смысл говорить об их истинности или ложности, нужны дополнительные сведения: когда и где шел снег, о какой конкретной комнате идет речь, какое число обозначено буквой а.

В последнем примере а может не обозначать конкретного числа, а быть переменной, т.е. буквой, вместо которой можно подставлять элементы некоторого множества, называемые значениями переменной. Пусть например, {-2; 0; 2, 3, 4} - множество значений переменной а. Каждому значению переменной соответствует либо истинное, либо ложное высказывание; например, высказывания (-2)²=4, 2²=4 истинны, а высказывания 0²=4, 3²=4, 4²=4 ложны.

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

Высказывание, представляющее собой одно утверждение принято называть простым или элементарным. Примерами элементарных высказывании могут служить высказывания 1) и 3). Элементарные высказывания обозначаются буквами латинского алфавита: A,B,C… X,Y,Z или a,b,c…x,y,z. Если высказывание А истинно, то будем писать А=1; если ложно А=0.

Высказывания, которые получаются из элементарных с помощью логических связок «не», «и», «или», «если ..., то...», «тогда и только тогда, когда…», «не…и не…», «не…или не…» принято называть сложными или составными. Так, высказывание 4) получается из простого высказывания «Курица - птица» с помощью отрицания «не». Высказывание 5) образовано из элементарных «число 8 делится на 2», «число 8 делится на 4», соединенных союзом «и». Аналогично сложные высказывания «Я пойду в школу или в кино» получается из простых высказываний «Я пойду в кино», «Я пойду в школу» с помощью грамматической связки «или» [2, 4, 6].

1.1.3 Логические операции над высказываниями

Для написания этого раздела использовалась литература [2, 5, 7, 8].

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

1) Отрицание

Простейшей операцией логики высказываний является операция отрицания, соответствующая в русском языке частице «не».

Эту операцию обозначают символом «Ї» (или «»)

Определение: Если А - некоторое высказывание, то (читается «не А» или «неверно, что А») - новое, сложное высказывание, которое истинно тогда и только тогда, когда А ложно.

Пример: А - «идет дождь», - «не идет дождь».

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

1	0
0	1

Именно эту таблицу (ее надо читать по строкам: «если А=1, то =0», т.е. одновременно А истинно и ложно) мы и приняли в качестве определения операции отрицания. Подобными таблицами истинности мы будем пользоваться и при определении других логических операций.

2) Конъюнкция

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

Обозначается конъюнкция символом «» («» или «&»), который ставится между высказываниями.

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

Пример. А - «лиса - хищное животное», В - «медведь меньше лисы», С - «Лондон - столица Англии»; АВ - «лиса - хищное животное, и медведь меньше лисы» - ложное высказывание; АС - «лиса - хищное животное, и Лондон - столица Англии» - истинное высказывание.

Таблица истинности для операции конъюнкции выглядит следующим образом:

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

В этой таблице каждая строка показывает, истинна или ложна конъюнкция при данном наборе истинных или ложных конъюнктивных членов.

3) Дизъюнкция

Аналог в русском языке для следующей логической операции - союз «или». Но в русском языке этот союз имеет несколько довольно далеких друг от друга значений.

Примеры: «Здесь близко река или озеро» - союз «или» в соединительном (неисключающем) смысле; «Или он останется, или я» - «или» в разделительном (исключающем) смысле; «Самолет, или аэроплан, есть летательный аппарат тяжелее воздуха» - «или» в пояснительном смысле и т.д.

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

Определение: Если А и В - высказывания, то АВ - сложное высказывание (читается «А или В»), которое ложно тогда и только тогда, когда ложны оба высказывания А и В. Высказывания А и В называют при этом дизъюнктивными членами.

Пример: А - «3<6», В - «5>1», АВ - «3<6 или 5>1» - истинное высказывание.

Таблица истинности для операции дизъюнкции выглядит следующим образом:

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

4) Импликация

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

Одна из проблем, связанных с восприятием импликации - использование этого оборота в нескольких разных значениях.

Пример: а) «Если меня не обманывает зрение, то это Иван Иванович»; «Если треугольник - прямоугольный, то для него справедлива теорема Пифагора» - условное значение оборота « если..., то ...»;

б) «Если на севере промышляли больше охотой, то на юге основу хозяйства составляло земледелие» - противопоставительное значение;

в) «Если сэр Вальтер Скотт не написал ни одного романа, то не было гражданской войны в США» - контрафактическое условное значение и т.д.

Мы будем ориентироваться только на первое значение этого оборота - условное.

Но и в этом случае полной аналогии нет, поскольку в русском языке оборот «если..., то...» подразумевает наличие причинной связи.

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

В результате истинными могут оказаться сложные высказывания «Если в доме пять этажей, то в квартире номер три проживает Иванов» или «Если 1+12, то Рим есть столица Франции», а то и еще более «удивительные» высказывания.

Перейдем к точному определению и его обсуждению.

Определение: Если А и В - высказывания, то АВ (читается «если А, то В», «из А следует В», «А влечет В», «А имплицирует В») - сложное высказывание, которое ложно тогда и только тогда, когда А истинно, а В ложно.

Таблица истинности для операции импликации такова:

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

Пример: Пусть Р означает «22=4», Q - «снег бел», Р - «22=5», Q - «снег черен». Тогда высказывания PQ, РQ и QР истинны, а РQ - ложно.

Замечания:

Иногда вместо «» используют знак «».

Два главных момента в свойствах импликации: истина не может имплицировать ложь, но из лжи следует что угодно. Такое уточнение истинностного смысла связки «если А, то В» не противоречит обычной практике, скорее даже ее расширяет.

5) Эквивалентность

Еще одна логическая операция - эквивалентность (или эквиваленция) - соответствует оборотам русского языка типа «тогда и только тогда, когда...», «для того, чтобы..., необходимо и достаточно...» и др. и обозначается знаками «», «~».

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

Определение: Если А и В - высказывания, то АВ (читается: «А эквивалентно В») есть сложное высказывание, которое истинно тогда и только тогда, когда одновременно А и В истинны либо оба ложны.

Приведем таблицу истинности для эквивалентности:

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

Пример: Пусть А - «Хлеба уцелеют», В - «вырыты оросительные канавы» Тогда высказывание или «Хлеба уцелеют тогда и только тогда, когда будут вырыты оросительные канавы».

6) Штрих Шеффера

Следующая логическая операция называется штрих Шеффера и обозначается символом «|». Аналогом в русском языке служит оборот « не …или не …»

Определение: Если А и В - высказывания, то А (читается: «А штрих Шеффера В») - сложное высказывание, которое ложно тогда и только тогда, когда А и В истинны одновременно.

Таблица истинности для этой операции:

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

Пример: Пусть А - «Противоположные стороны трапеции не конгруэнтны», В - « Противоположные стороны трапеции не параллельны» Тогда высказывание или «Противоположные стороны трапеции не конгруэнтны или не параллельны» - истинное.

7) Стрелка Пирса

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

Определение: Если А и В - высказывания, то АВ (читается: «А стрелка Пирса В») - сложное высказывание, которое истинно тогда и только тогда, когда А и В ложны одновременно.

Таблица истинности для этой операции:

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

Пример: Пусть А - «Петр не едет на Урал», В - «Николай не едет в Сибирь» Тогда высказывание или « Петр не едет на Урал и Николай не едет в Сибирь « - истинное.

1.2 Формы записи высказываний. Алгоритмические способы решения логических задач

1.2.1 Формулы логики высказывания и их свойства

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

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

Например, высказывание: «Если 20 делится на 2 и на 5, то 20 делится на 10», формализуется в виде . Такая же формула соответствует предложению: «если в четырехугольнике две противоположные стороны равны и параллельны, то этот четырехугольник - параллелограмм».

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

1) А,В,С и т.д. - символы для обозначения высказываний;

2) 1 и 0 - символы, обозначающие логические константы «истина», «ложь»;

3) - символы, логические операции;

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

Дадим строгое определение формулы логики высказываний.

1) Всякое высказывание - это формула;

2) Символы 1, 0 - формулы;

3) Если А - формула, то - тоже формула;

4) Если А₁ и А₂ - формулы, то - формулы;

5) Никаких других формул в логике высказываний нет.

Алгоритм формализации высказывания

1) Простые высказывания заменяем переменными;

2) Логические связки заменяем соответствующими символами;

3) Расставляем вспомогательные символы, скобки: ( , ) в соответствии со смыслом данного высказывания.

Формула алгебры высказываний принимает одно из двух значений (0 или 1) в зависимости от простых высказываний и от связи между ними.

Истинность или ложность высказывания мы будем задавать таблицей истинности.

Составление истинностных таблиц происходит по следующему правилу:

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

При составлении таблиц необходимо следить за тем, чтобы не перепутать порядок действий. Заполняя таблицу, следует двигаться «изнутри наружу», то есть от элементарных формул к более и более сложным. Столбец, заполняемый последним, содержит значения исходной формулы [4].

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

Пример 1: :

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

Пример 2: Вычислить значение функции:

при .

1)

2)

3)

4)

5)

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

Две формулы А и В будем называть равносильными (А=В или ), если они имеют одинаковые таблицы истинности.

Будем считать две таблицы истинности одинаковыми, если у них одинаковые последние (результирующие) столбцы.

Пример:

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

x	y
0	0	1	1
0	1	1	1
1	0	0	0
1	1	1	1

Может оказаться, что в последнем столбце таблицы истинности стоят одни единицы или нули. Будем называть такое высказывание тождественно-истинным (тавтологией) соответственно тождественно-ложным (противоречием) и обозначать 1 и 0. Из определения следует, что для проверки равносильности формул нужно построить их таблицы истинности и сравнить [7].

Пример: Формулы и являются тождественно-истинными:

х
1	0	1
1	0	1
0	1	1
0	1	1

х	у
1	1	1	1
1	0	1	1
0	1	0	1
0	0	1	1

Для упрощения логических высказываний могут быть использованы следующие равносильности (свойства):

Свойства конъюнкции и дизъюнкции:

1. Коммутативные (переместительные) законы:

2. Ассоциативные (сочетательные) законы:

3. Дистрибутивные (распределительные) законы:

4. Законы поглощения:

5. Законы склеивания:

Свойства с отрицанием

1. Законы Де Моргана:

2. Закон двойного отрицания:

;

3. Закон противоречия:

;

4. Закон исключения третьего:

.

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

1. , ;

2.

3.

4.

Связь между логическими операциями

1. ;

2. , ;

3. , ;

4. ;

5. .

1.2.2 Нормальные формы. Совершенные нормальные формы

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

Примеры элементарных конъюнкций:

.

Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ) и выглядит следующим образом:

,

где и - различные элементарные конъюнкций.

Примеры ДНФ:

.

Алгоритм приведения к ДНФ может быть описан с привлечением приведенных выше равносильностей:

1. Используя закон двойного отрицания и законы Де Моргана все отрицания «спускаются» до переменных;

2. Раскрываются скобки по распределительному закону;

3. С помощью законов поглощения, противоречия и исключенного третьего удаляются лишние конъюнкции и повторение переменных;

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

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

Примеры элементарных дизъюнкций:

.

Всякая конъюнкция элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ) и выглядит следующим образом:

,

где и - различные элементарные дизъюнкции.

Примеры КНФ:

Алгоритм приведения к КНФ может быть описан с помощью тех же соотношений и законов, которые использовались и в алгоритме для ДНФ.

1. Используя закон двойного отрицания и законы Де Моргана все отрицания «спускаются» до переменных;

2. Раскрываются скобки по распределительному закону;

3. С помощью законов поглощения, противоречия и исключенного третьего удаляются лишние дизъюнкции и повторения переменных;

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

Совершенной дизъюнктивной нормальной формой формулы алгебры высказываний (СДНФ) называется ДНФ, в которой: 1) все слагаемые содержат сомножителем все переменные - без отрицания либо с отрицанием, но не вместе. 2) отсутствуют повторения слагаемых и сомножителей.

Совершенной конъюнктивной нормальной формой формулы алгебры высказываний (СКНФ) называется КНФ, в которой: 1) каждый сомножитель содержит слагаемым каждую переменную, без отрицания либо с отрицанием, но не вместе; 2) отсутствуют повторения сомножителей и слагаемых.

Замечание: Обратим внимание, что одно определение получается из другого заменой друг другом слов «слагаемое» и «сомножитель».

Примеры:

СДНФ некоторой формулы двух переменных:

СКНФ функции трех переменных:

.

Допустимыми для СДНФ (СКНФ) являются только некоторые полные конъюнкции (дизъюнкции): содержащие - без повторений - все переменные этой функции - с отрицаниями или без них.

Опишем два способа приведения к совершенным нормальным формам.

1-Й СПОСОБ - АНАЛИТИЧЕСКИЙ

Алгоритм приведение к СДНФ:

1.Приводят к ДНФ с помощью равносильных преобразований;

2. Умножают на единицы, представленные в виде дизъюнкций каждой недостающей переменной, с ее отрицанием;

3.Раскрывают скобки - по первому распределительному закону;

4.Исключают повторения слагаемых.

Пример:

.

Алгоритм приведение к СКНФ:

1.Формулу приводят к КНФ;

2.Прибавляют нули, представленные в виде конъюнкций каждой недостающей переменной с ее отрицанием;

3.С помощью второго распределительного закона приводят эти сомножители к суммам первой степени, т. е. не содержащим произведений;

4.Исключают повторения сомножителей.

Пример:

2-Й СПОСОБ - ТАБЛИЧНЫЙ

Составим таблицу истинности для функции :

x	y	z
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

Алгоритм приведение к СДНФ:

1.Строим таблицу истинности;

2.Рассматриваем только те строки таблицы, в которых формула принимает значение 1;

3.Каждой такой строке соответствует конъюнкция всех аргументов (без повторений). Аргумент, принимающий значение 0, входит в нее с отрицанием, значение 1 - без отрицания;

4.Образуем дизъюнкцию всех полученных конъюнкций.

Пример: В нашей таблице первую строку опускаем: функция принимает значение 0. Второй строке соответствует конъюнкция третью строку опускаем и т. д.

СДНФ:

Приведение к СКНФ:

1.Строим таблицу истинности;

2.Рассматриваем только те строки таблицы, где функция принимает значение 0;

3.Каждой такой строке соответствует дизъюнкция всех переменных (без повторений). Аргумент, принимающий значение 0, берется без отрицания, значение 1 - с отрицанием;

4.Образуют конъюнкцию полученных дизъюнкций.

В нашем примере первой строке таблицы соответствует дизъюнкция , вторую строку опускаем и т. д.

СКНФ:

Замечания:

Если условиться из двух совершенных форм, СДНФ и СКНФ, отдавать предпочтение той, которая содержит меньше букв, то СДНФ предпочтительнее, если в столбце значений функции таблицы истинности меньше единиц; СКНФ - если в этом столбце меньше нулей.

В обычной, школьной алгебре мы знаем, что нет общего метода перехода от табличного задания функции к аналитическому. В алгебре высказываний, как видим, такой метод существует [5, 7].

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

Алгоритм решения:

1) Кодирование: обозначение искомых с помощью булевых переменных (принимающих значения 0, 1) и описание содержания этих переменных.

2) Запись условия в виде системы логических уравнений, в правых частях которых - единицы.

Замечание. Если правая часть уравнения - нуль, то отрицанием левой части она приводится к единице.

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

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

Верно и обратное - каждое решение характеристического уравнения (обращающее конъюнкцию в единицу) обращает в единицу все сомножители конъюнкции, следовательно, удовлетворяет системе уравнений.

4) Приведение левой части характеристического уравнения к ДНФ (в частности, к СДНФ).

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

5) Приравнивание каждого слагаемого СДНФ, независимо от других, единице и извлечение из уравнений (левые части которых - конъюнкции переменных или их отрицаний) значений переменных. Каждый их набор является решением задачи.

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

Замечание. Если после упрощений в ДНФ осталось одно слагаемое, задача имеет единственное решение, если более одного - несколько решений. В случае, когда в левой части характеристического уравнения все слагаемые уничтожаются, задача не имеет решения (данные не совместны) /4/.

Применим этот алгоритм к решению задачи.

Задача. (Кто смотрит телевизор?)

Семья состоит из пяти человек: Алексей (А), Вера (В), Глеб (Г), Даша (Д), Евгений (Е).

Если телевизор смотрит А, то смотрит и В;

смотрят либо Д, либо Е, либо оба вместе;

смотрят либо В, либо Г, но не вместе;

Д и Г либо смотрят вместе, либо вовсе не смотрят;

если смотрит Е, то смотрят А и Д.

Кто смотрит телевизор?

Решение:

1) Записываем в виде системы логических уравнений:

2) Преобразуем в характеристическое уравнение:

3) Приведем левую часть характеристического уравнения к СДНФ:

4) Получили одно слагаемое, следовательно, задача имеет единственное решение. Приравнивание каждого слагаемого СДНФ единице и извлечение из уравнения значение переменных: .

Таким образом, получили ответ: телевизор смотрят Глеб и Даша.

1.3 Эвристические методы решения логических задач

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

1.3.1 Прием конкретизации задачи

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

Задача 1. Три ученицы - Галя, Лида и Наташа - в соревнованиях по гимнастике заняли три первых места. Когда же девочек спросили, кто из них занял первое место, они дали три разных ответа.

Галя: «Я заняла первое место»;

Лида: «Я заняла не первое место»;

Наташа: «Я заняла не третье место, однако, вы учтите, что один из ответов моих подруг правильный, а другой - неправильный».

Кто занял в соревнованиях первое место, если Наташин ответ во всем правдив?

Решение: Итак, Наташа заняла не третье место, а первое или второе. Проанализируем ответы других девочек. Галя сказала, что заняла первое место. Правдив ли ее ответ? Это неизвестно. Конкретизируем задачу. Пусть Галя сказала правду. Тогда она заняла первое место. В этом случае Лида сказала неправду, т.е. неверно, что она заняла не первое место. Но тогда получилось, что и Галя, и Лида заняли первое место, а это противоречит условию.

Выполним конкретизацию по-другому. Пусть Галя сказала неправду, тогда, значит, ответ Лиды правдив. Следовательно, Галя заняла второе или третье место, а Лида также заняла не первое место, а второе или третье. Тогда получим, что первое место заняла Наташа.

Используем прием конкретизации в более сложных задачах.

Задача 2. Четыре ученицы - Мария, Нина, Ольга и Поля - участвовали в лыжных соревнованиях и заняли четыре первых места. На вопрос, кто какое место занял, они дали три разных ответа:

«Ольга заняла первое место, Нина - второе»;

«Ольга - второе, Поля - третье»;

«Мария - второе, Поля четвертое».

Отвечавшие при этом признали, что одна часть каждого ответа верна, а другая - неверна. Какое место заняла каждая из учениц?

Решение: Проанализируем ответы девочек.

1) «Ольга заняла первое место, Нина - второе».

Что здесь истина? Неизвестно. Конкретизируем условие: пусть первая часть ответа - истина, а вторая часть - ложь. Исходя из этого, запишем предполагаемые истинные и ложные высказывания в таблице 1.1. Теперь легко видеть, что в правом столбце таблицы оказалось два противоречивых утверждения: Ольга и Нина не могут одновременно занимать второе место. Значит, хотя бы одно из этих высказываний действительно ложное.

Таблица 1.1

истина	ложь
Ольга - I место Поля - III место Мария - II место	Нина - II место Ольга - II место Поля - IV место

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

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

«Ольга заняла не первое место, а Нина - второе». Но тогда ложна первая часть ответа 2), а значит, то, что Поля на третьем месте - истина. Но тогда из ответа 3) получится, что Мария - на втором месте, как и Нина. А это противоречит условию задачи.

Других конкретизации рассматривать нет смысла, так как любая конкретизация предложения 2) или 3) диктует истинность или ложность первой или второй части в предложении 1), которые уже обеспечили получение ответа. Значит, найденный ранее ответ единственный.

1.3.2 Прием переструктурирования задачи

Переструктурирование заключается в изменении расположения уже имеющихся элементов задачи путем их перестановки или перегруппировки.

Задача 3.

Акробат и собачонка

Весят два пустых бочонка.

Шустрый пес без акробата

Весит два мотка шпагата.

А с одним мотком ягненок

Весит, видите, бочонок.

Сколько весит акробат

В пересчете на ягнят?

Решение: Изобразим условие задачи наглядно (рис. 1), обозначив акробата буквой А, собачонка буквой С, ягненка буквой Я, бочонки буквой Б и мотки буквой М.

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

А+С = Я + М + Я+М (2)

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

А+С = 2Я + С (3)

Итак, А =2Я, акробат весит столько же, сколько и два ягненка.

1.3.3 Прием разбиения задачи на части

Если в задаче можно выделить самостоятельные части, то целесообразно сформулировать их отдельно и решить по очереди.

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

Задумался судья, а потом и говорит: «Вот перед вами лежат 5 тюбетеек: 3 из красного бархата, а 2 - из черного. Сейчас вам завяжут глаза и наденут тюбетейки на головы. Когда повязки с ваших глаз снимут, самый мудрый из вас скажет, какая тюбетейка у него на голове»,

Так и сделали. Сняли повязки с глаз: видит каждый перед собой красные тюбетейки на головах товарищей, а какая на своей голове - не знает. Наконец, один мудрец сказан: «О справедливейший из судей! Ты велел надеть на меня красную тюбетейку».

«Вот ты и есть самый мудрый из вас троих» - решил судья.

Как мудрец догадался, что на нем красная тюбетейка?

Решение: Так как всего было 5 тюбетеек: 3 красные и 2 черные, то возможны три различных варианта:

а) на трех мудрецов надели 2 черные и 1 красную тюбетейку;

б) на трех мудрецов надели 1 черную и 2 красные тюбетейки;

в) на трех мудрецов надели 3 красные тюбетейки.

Каждый случай можно рассмотреть отдельно.

Причем любая предыдущая подзадача помогает разобраться в последующей подзадаче.

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

В случае б) любой из собратьев обладателя черной тюбетейки увидел бы ее. А это тоже противоречит условию.

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

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

1.3.4 Приемы моделирования

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

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

1. Прием моделирования на полупрямой

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

Задача 5. На вечеринку собрались четверо друзей: Аня. Вика. Миша и Коля. Коля пришел раньше Ани, но не был первым. Определите, в какой последовательности друзья приходили к месту встречи, если Вика пришла последней.

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

Рисунок 1.1

На рисунке 1.1, а) показано, что Коля пришел раньше Ани. По рисунку 1, б) мы видим, что кто-то из друзей опередил Колю, а следовательно, и Аню. Появление еще одной правой точки на рисунке 1, в) передает условие «Вика была последней». Тогда придется сделать вывод, что Миша пришел раньше всех. Последовательность явки друзей к месту встречи видна на рисунке 1, г).

2. Прием моделирования с помощью таблицы

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

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

Борис прошлую летнюю сессию сдал на отлично;

Виктор должен был летом ехать на практику в Омск;

Иванов собирался поехать домой в Челябинск;

Антон был курсом старше Петра:

Борис и Орлов коренные москвичи:

Крылов в прошлом учебном году окончил школу и поступил на тот же факультет, на котором учился Зуев;

Борис иногда пользовался прошлогодними конспектами Виктора.

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

Если теперь, в соответствии с условием, в таблицы 2 ставить знаки «минус» на заведомо невозможных парах элементов, то можно прийти к решению задачи.

Отметим в таблице данные из условия задачи.

Борис прошлую сессию сдал на отлично, следовательно, Борис не на I курсе - в клеточке (Борис; I) ставим знак «минус».

Виктор летом едет в Омск, а Иванов в Челябинск, значит, фамилия Виктора не Иванов - в клеточке (Виктор; Иванов) прочерк.

Антон курсом старше Петра, значит, Антон учится не на I курсе - в клеточке (Антон; I) появляется знак «минус».

Так как Борис и Орлов коренные москвичи, то фамилия Бориса не Орлов - в клеточке (Борис; Орлов) ставим прочерк.

Таблица 1.2

Имя, курс	Фамилия	Курс
	Зуев	Крылов	Иванов	Орлов	I	II	III	IV
Борис	+	-	-	-	-	-	+	+
Виктор	-	-	-	+	-	-	-	+
Антон	-	-	+	-	-	+	-	-
Петр	-	+	-	-	+	-	-	-
I	-	+	-	-
II	-	-	+	-
III	+	-	-	-
IV	-	-	-	+

Крылов в прошлом году окончил школу, т.е. сейчас он учится на I курсе - знак «+» в клеточке (Крылов; I). Ясно, что тогда ни Зуев, ни Иванов, ни Орлов не учатся на I курсе - в этих клеточках ставим прочерки.

Борис пользуется прошлогодними конспектами Виктора, значит, Виктор на один курс старше Бориса. Но мы знаем, что Борис уже не на I курсе, следовательно, Виктор учится не на I и не на II курсе - в клеточках (Виктор; I) и (Виктор; II) ставим прочерки.

По условию Иванов из Челябинска, а Борис коренной москвич, следовательно, Борис не Иванов - в клеточке (Борис; Иванов) прочерк.

Из таблицы видно, что на I курсе учится не Борис, не Виктор, не Антон. Следовательно, на I курсе учится Петр - в клеточке (Петр; I) появляется знак «+». В клеточках (Петр; II), (Петр; III) и (Петр; IV) прочерки.

Но на I курсе учится Крылов. Значит, Петр носит фамилию Крылов - в клеточке (Петр; Крылов) ставим знак «+». Ясно, что Петр не может быть ни Ивановым, ни Зуевым, ни Орловым, а также Крыловым не могут быть ни Борис, ни Виктор, ни Антон - во всех этих клеточках прочерки.

Обратим внимание на столбец «Иванов». Из него видно, что ни Борис, ни Виктор, ни Петр не носят фамилию Иванов. Следовательно, Ивановым может быть только Антон - в соответствующей клеточке ставим знак « + «. Тогда ясно, что ни Орлов, ни Зуев не носят имя Антон - в этих клеточках появляются знаки «минус».

Обратим внимание на столбец «Орлов»: ни Борис, ни Антон, ни Петр не носят фамилию Орлов. Значит, только Виктор может быть Орловым - клеточку (Виктор; Орлов) помечаем знаком «+». Но тогда Виктор не может быть Зуевым - ставим минус в клетке (Виктор; Зуев). Тогда из таблицы видно, что только Борис может быть Зуевым.

Итак, Петр Крылов учится на I курсе, но Антон Иванов курсом старше Петра, значит, Антон Иванов на II курсе - отметим соответствующие клеточки.

Мы знаем, что Виктор Орлов курсом старше Бориса Зуева, значит, Борис Зуев учится на III, a Виктор Орлов - на IV курсе.