Программа по учебному курсу «Элементы математической логики» 8 класс

Пояснительная записка

Программа по учебному курсу «Элементы математической логики» для 8 класса составлена на основе:

Примерной Основной Образовательной Программы Основного Общего Образования одобренной решением федерального учебно-методического объединения по общему образованию (протокол от 8 апреля 2015 г. № 1/15)

Основной образовательной программы основного общего образования МБОУ Мурыгинской СШ и в соответствии с требованиями ФГОС основного образования.

Программа рассчитана на 16 часов. Контрольных работ – 3, практических – 7, промежуточная аттестация – 1.

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

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

• Наличие представлений об информации как важнейшем стратегическом ресурсе развития личности, государства, общества;

• Готовность и способность обучающихся к саморазвитию и самообразованию на основе мотивации к обучению и познанию; готовность и способность осознанному выбору и построению дальнейшей индивидуальной траектории образования на базе ориентировки в мире профессий и профессиональных предпочтений, с учетом устойчивых познавательных интересов; способность увязать учебное содержание с собственным жизненным опытом, понять значимость подготовки в области информатики и ИКТ в условиях развития информационного общества; готовность к повышению своего образовательного уровня и продолжению обучения с использованием средств и методов информатики и ИКТ.

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

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

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

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

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

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

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

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

• владение основами самоконтроля, самооценки, принятия решений и осуществления осознанного выбора в учебной и познавательной деятельности;

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

• ИКТ-компетентность – широкий спектр умений и навыков использования средств информационных и коммуникационных технологий для сбора, хранения, преобразования и передачи различных видов информации, навыки создания личного информационного пространства (обращение с устройствами ИКТ; коммуникация и социальное взаимодействие; поиск и организация хранения информации; анализ информации).

Регулятивные УУД

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

• анализировать существующие и планировать будущие образовательные результаты;

• идентифицировать собственные проблемы и определять главную проблему;

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

• ставить цель деятельности на основе определенной проблемы и существующих возможностей;

• формулировать учебные задачи как шаги достижения поставленной цели деятельности;

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

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

• определять необходимые действие(я) в соответствии с учебной и познавательной задачей и составлять алгоритм их выполнения;

• обосновывать и осуществлять выбор наиболее эффективных способов решения учебных и познавательных задач;

• определять/находить, в том числе из предложенных вариантов, условия для выполнения учебной и познавательной задачи;

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

• выбирать из предложенных вариантов и самостоятельно искать средства/ресурсы для решения задачи/достижения цели;

• составлять план решения проблемы (выполнения проекта, проведения исследования);

• определять потенциальные затруднения при решении учебной и познавательной задачи и находить средства для их устранения;

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

• планировать и корректировать свою индивидуальную образовательную траекторию.

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

• определять совместно с педагогом и сверстниками критерии планируемых результатов и критерии оценки своей учебной деятельности;

• систематизировать (в том числе выбирать приоритетные) критерии планируемых результатов и оценки своей деятельности;

• отбирать инструменты для оценивания своей деятельности, осуществлять самоконтроль своей деятельности в рамках предложенных условий и требований;

• оценивать свою деятельность, аргументируя причины достижения или отсутствия планируемого результата;

• находить достаточные средства для выполнения учебных действий в изменяющейся ситуации и/или при отсутствии планируемого результата;

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

• сверять свои действия с целью и, при необходимости, исправлять ошибки самостоятельно.

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

• определять критерии правильности (корректности) выполнения учебной задачи;

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

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

• оценивать продукт своей деятельности по заданным и/или самостоятельно определенным критериям в соответствии с целью деятельности;

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

• фиксировать и анализировать динамику собственных образовательных результатов.

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

• наблюдать и анализировать собственную учебную и познавательную деятельность и деятельность других обучающихся в процессе взаимопроверки;

• соотносить реальные и планируемые результаты индивидуальной образовательной деятельности и делать выводы;

• принимать решение в учебной ситуации и нести за него ответственность;

• самостоятельно определять причины своего успеха или неуспеха и находить способы выхода из ситуации неуспеха;

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

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

Познавательные УУД

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

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

• строить рассуждение от общих закономерностей к частным явлениям и от частных явлений к общим закономерностям;

• строить рассуждение на основе сравнения предметов и явлений, выделяя при этом общие признаки;

• излагать полученную информацию, интерпретируя ее в контексте решаемой задачи;

• самостоятельно указывать на информацию, нуждающуюся в проверке, предлагать и применять способ проверки достоверности информации;

• вербализовать эмоциональное впечатление, оказанное на него источником;

• объяснять явления, процессы, связи и отношения, выявляемые в ходе познавательной и исследовательской деятельности (приводить объяснение с изменением формы представления; объяснять, детализируя или обобщая; объяснять с заданной точки зрения);

• выявлять и называть причины события, явления, в том числе возможные / наиболее вероятные причины, возможные последствия заданной причины, самостоятельно осуществляя причинно-следственный анализ;

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

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

• обозначать символом и знаком предмет и/или явление;

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

• создавать абстрактный или реальный образ предмета и/или явления;

• строить модель/схему на основе условий задачи и/или способа ее решения;

• создавать вербальные, вещественные и информационные модели с выделением существенных характеристик объекта для определения способа решения задачи в соответствии с ситуацией;

• преобразовывать модели с целью выявления общих законов, определяющих данную предметную область;

• переводить сложную по составу (многоаспектную) информацию из графического или формализованного (символьного) представления в текстовое, и наоборот;

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

1. Смысловое чтение. Обучающийся сможет:

• находить в тексте требуемую информацию (в соответствии с целями своей деятельности);

• ориентироваться в содержании текста, понимать целостный смысл текста, структурировать текст;

• устанавливать взаимосвязь описанных в тексте событий, явлений, процессов;

• резюмировать главную идею текста;

• критически оценивать содержание и форму текста.

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

• определять необходимые ключевые поисковые слова и запросы;

• осуществлять взаимодействие с электронными поисковыми системами, словарями;

• формировать множественную выборку из поисковых источников для объективизации результатов поиска;

• соотносить полученные результаты поиска со своей деятельностью.

Коммуникативные УУД

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

• определять возможные роли в совместной деятельности;

• играть определенную роль в совместной деятельности;

• принимать позицию собеседника, понимая позицию другого, различать в его речи: мнение (точку зрения), доказательство (аргументы), факты; гипотезы, аксиомы, теории;

• определять свои действия и действия партнера, которые способствовали или препятствовали продуктивной коммуникации;

• строить позитивные отношения в процессе учебной и познавательной деятельности;

• корректно и аргументированно отстаивать свою точку зрения, в дискуссии уметь выдвигать контраргументы, перефразировать свою мысль (владение механизмом эквивалентных замен);

• критически относиться к собственному мнению, с достоинством признавать ошибочность своего мнения (если оно таково) и корректировать его;

• предлагать альтернативное решение в конфликтной ситуации;

• выделять общую точку зрения в дискуссии;

• договариваться о правилах и вопросах для обсуждения в соответствии с поставленной перед группой задачей;

• организовывать учебное взаимодействие в группе (определять общие цели, распределять роли, договариваться друг с другом и т. д.);

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

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

• определять задачу коммуникации и в соответствии с ней отбирать речевые средства;

• отбирать и использовать речевые средства в процессе коммуникации с другими людьми (диалог в паре, в малой группе и т. д.);

• представлять в устной или письменной форме развернутый план собственной деятельности;

• соблюдать нормы публичной речи, регламент в монологе и дискуссии в соответствии с коммуникативной задачей;

• высказывать и обосновывать мнение (суждение) и запрашивать мнение партнера в рамках диалога;

• принимать решение в ходе диалога и согласовывать его с собеседником;

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

• использовать невербальные средства или наглядные материалы, подготовленные/отобранные под руководством учителя;

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

1. Формирование и развитие компетентности в области использования информационно-коммуникационных технологий (далее – ИКТ). Обучающийся сможет:

• целенаправленно искать и использовать информационные ресурсы, необходимые для решения учебных и практических задач с помощью средств ИКТ;

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

• выделять информационный аспект задачи, оперировать данными, использовать модель решения задачи;

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

• использовать информацию с учетом этических и правовых норм;

• создавать информационные ресурсы разного типа и для разных аудиторий, соблюдать информационную гигиену и правила информационной безопасности.

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

• формирование информационной культуры; формирование представления о компьютере как универсальном устройстве обработки информации; развитие основных навыков и умений использования компьютерных устройств;

• формирование знаний о логических значениях и операциях

Математические основы информатики

Обучающийся научится:

• записывать в различных системах целые числа от 0 до 1024; переводить заданное натуральное число из десятичной записи в различные системы счисления и наоборот; сравнивать числа в позиционных системах счисления; складывать, вычитать и умножать числа, записанные в различных системах счисления;

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

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

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

Обучающийся получит возможность:

• узнать о том, что любые дискретные данные можно описать, используя алфавит, содержащий только два символа, например, 0 и 1;

• познакомиться с тем, как информация (данные) представляется в современных компьютерах и робототехнических системах;

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

Основное содержание изучаемого предмета

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

Математические основы информатики

Системы счисления

Запись в различных системах счисления целых чисел от 0 до 1024; перевод заданного натурального числа из десятичной записи в различные системы счисления и наоборот; сравнение чисел в позиционных системах счисления.

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

Арифметические действия в системах счисления.

Элементы комбинаторики, теории множеств и математической логики

Высказывания. Простые и сложные высказывания. Диаграммы Эйлера-Венна. Логические значения высказываний. Логические выражения. Логические операции: «и» (конъюнкция, логическое умножение), «или» (дизъюнкция, логическое сложение), «не» (логическое отрицание). Правила записи логических выражений. Приоритеты логических операций.

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

Логические операции следования (импликация) и равносильности (эквивалентность). Свойства логических операций. Законы алгебры логики. Использование таблиц истинности для доказательства законов алгебры логики. Логические элементы. Схемы логических элементов и их физическая (электронная) реализация. Знакомство с логическими основами компьютера.

Формы организации образовательного процесса

Единицей учебного процесса является урок. В первой части урока проводиться объяснение нового материала, а на конец урока планируется компьютерный практикум (практические работы). Работа учеников за компьютером в 8 классах 10-15 минут. В ходе обучения учащимся предлагаются короткие (5-10 минут) проверочные работы (в форме тестирования). Очень важно, чтобы каждый ученик имел доступ к компьютеру и пытался выполнять практические работы по описанию самостоятельно, без посторонней помощи учителя или товарищей.

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

Формы обучения:

- учебно-плановые (урок, лекция, семинар, домашняя работа) фронтальные, коллективные, групповые, парные, индивидуальные, а также со сменным составом учеников,

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

- вспомогательные (групповые и индивидуальные занятия).

Формы итогового контроля:

• контрольная работа;

• творческая практическая работа;

• проект.

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

Тема	Кол-во часов	Элементы содержания	Виды учебной деятельности
Системы счисления	7	Техника безопасности и организация рабочего места. Позиционные и непозиционные системы счисления. Примеры представления чисел в позиционных системах счисления. Основание системы счисления. Алфавит (множество цифр) системы счисления. Количество цифр, используемых в системе счисления с заданным основанием. Краткая и развернутая формы записи чисел в позиционных системах счисления. Перевод натуральных чисел из десятичной системы счисления в другие системы счисления и обратно. Перевод натуральных чисел из двоичной системы счисления в восьмеричную и шестнадцатеричную и обратно. Арифметические действия в системах счисления. Операции умножения и деления.	Аналитическая деятельность: - выявлять различие в унарных, позиционных и непозиционных системах счисления; - выявлять общее и отличия в разных позиционных системах счисления; - анализировать логическую структуру высказываний. Практическая деятельность: - переводить небольшие (от 0 до 1024) целые числа из десятичной системы счисления в двоичную (восьмеричную, шестнадцатеричную) и обратно; - выполнять операции сложения и умножения над небольшими двоичными числами; - записывать вещественные числа в естественной и нормальной форме; - строить таблицы истинности для логических выражений; - вычислять истинностное значение логического выражения.
Элементы комбинаторики, теории множеств и математической логики	8	Расчет количества вариантов: формулы перемножения и сложения количества вариантов. Множество. Определение количества элементов во множествах, полученных из двух или трех базовых множеств с помощью операций объединения, пересечения и дополнения. Высказывания. Простые и сложные высказывания. Диаграммы Эйлера-Венна. Логические значения высказываний. Логические выражения. Логические операции: «и» (конъюнкция, логическое умножение), «или» (дизъюнкция, логическое сложение), «не» (логическое отрицание). Логическое следование или импликация. Логическая равнозначность или эквивалентность. Правила записи логических выражений. Приоритеты логических операций. Таблицы истинности. Построение таблиц истинности для логических выражений.
Промежуточная аттестация	1
Всего	16

Календарно-тематическое планирование

№ урока	№ урока в теме	Тема урока	Домашнее задание	Дата
	Системы счисления
1	1	Техника безопасности и организация рабочего места. Примеры представления чисел в позиционных системах счисления.	Рабочая тетрадь 15, 20, 21	06.09
2	2	Краткая и развернутая формы записи чисел в позиционных системах счисления.	РТ 35, 36	13.09
3	3	Перевод натуральных чисел из десятичной системы счисления в другие системы счисления и обратно.	РТ 41, 42	20.09
4	4	Перевод натуральных чисел из двоичной системы счисления в восьмеричную и шестнадцатеричную и обратно.	РТ 46, 47	27.09
5	5	Арифметические действия в системах счисления. Операции умножения и деления.	Карточка №1-№3	04.10
6	6	Решение задач	РТ 57, 58, 59	11.10
7	7	Контрольная работа	Повторить основные понятия и правила	18.10
	Элементы комбинаторики, теории множеств и математической логики
8	1	Формулы перемножения и сложения количества вариантов. Определение количества элементов во множествах.	Записи в тетради. Карточка №1-№3	25.10
9	2	Высказывания о множествах. Простые и сложные высказывания. Диаграммы Эйлера-Венна.	Записи в тетради. Карточка №4-№6	08.11
10	3	Логические значения высказываний. Примеры эквивалентных преобразований. Законы алгебры логики.	Записи в тетради. Карточка №7-№9	15.11
11	4	Логическое следование (импликация) и логическая равнозначность (эквивалентность).	Записи в тетради. Карточка №10-№12	22.11
12	5	Правила записи логических выражений. Приоритеты логических операций. Графическое решение выражений по координатной прямой.	Записи в тетради. Карточка №1-№3	29.11
13	6	Построение логического выражения по таблице истинности. Построение таблиц истинности для логических выражений.	Записи в тетради. Карточка №4-№6	06.12
14	7	Решение текстовых задач	Карточка №1-№3	13.12
15	8	Контрольная работа	Повторить основные понятия курса	20.12
16	1	Промежуточная аттестация		27.12
17	1	Повторение. Системы счисления
18	1	Повторение. Элементы комбинаторики, теории множеств и математической логики

Перевод чисел из двоичной системы счисления в восьмеричную и шестнадцатеричную и обратно

Перевод чисел между системами счисления, основания которых являются степенями числа 2 (q = 2ⁿ), может производиться по более простым алгоритмам. Такие алгоритмы могут применяться для перевода чисел между двоичной (q = 2¹), восьмеричной (q = 2³) и шестнадцатеричной (q = 2⁴) системами счисления.

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

2 = 2ⁱ . Так как 2 = 2¹, то i = 1 бит.

Каждый разряд двоичного числа содержит 1 бит информации.

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

8 = 2ⁱ. Так как 8 = 2³, то i = 3 бита.

Каждый разряд восьмеричного числа содержит 3 бита информации.

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

Переведем таким способом двоичное число 101001₂ в восьмеричное:

101 001₂ = 1 × 2² + 0 × 2¹ + 1 × 2⁰ 0 × 2² + 0 × 2¹ + 1 × 2⁰ = 51₈.

Для упрощения перевода можно заранее подготовить таблицу преобразования двоичных триад (групп по 3 цифры) в восьмеричные цифры:

Двоичные триады	000	001	010	011	100	101	110	111
Восьмеричные цифры	0	1	2	3	4	5	6	7

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

Например, преобразуем дробное двоичное число А₂ = 0,110101₂ в восьмеричную систему счисления.

Получаем: А₂ = 0,110101₂ = 0,110 101₂ = 0,65₈. А₈ = 0,65₈

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

16 = 2ⁱ . Так как 16 = 2⁴, то i = 4 бита.

Каждый разряд шестнадцатеричного числа содержит 4 бита информации.

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

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

Двоичные тетрады	0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
Шестнадцатеричные цифры	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F

Переведем целое двоичное число А₂ = 101001₂ в шестнадцатеричное:

10 1001₂ = 1   2¹ + 0  2⁰        1  2³ + 0  2² + 0  2¹ + 1  2⁰ = 29₁₆.

В результате имеем: А₁₆ = 29₁₆.

Переведем дробное двоичное число А₂ =0,110101₂ в шестнадцатеричную систему счисления:

Получаем: А₁₆ = 0,110101₂ = 0,1101 0100₂ = 0,D4₁₆.

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

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

Например, преобразуем дробное восьмеричное число А₈ = 0,47₈ в двоичную систему счисления:

Получаем: А₂ = 0,100111₂.

Переведем целое шестнадцатеричное число А₁₆ = АВ₁₆ в двоичную систему счисления:

В результате имеем: А₂ = 10101011₂

3адания

1 Составить таблицу соответствия двоичных тетрад и шестнадцатеричных цифр.

2. Перевести в восьмеричную и шестнадцатеричную системы счисления следующие целые числа: 1111₂, 1010101₂.

3. Перевести в восьмеричную и шестнадцатеричную системы счисления следующие дробные числа: 0,01111₂, 0,10101011₂.

4. Перевести в восьмеричную и шестнадцатеричную системы счисления следующие числа: 11,01₂, 110,101₂.

5. Перевести в двоичную систему счисления следующие числа: 46,27₈, ЕF,12₁₆.

6. Сравнить числа, выраженные в различных системах счисления: 1101₂ и D₁₆; 0,11111₂ и 0,22₈; 35,63₈ и 16,С₁₆.

1 Составить таблицу соответствия двоичных тетрад и шестнадцатеричных цифр.

2. Перевести в восьмеричную и шестнадцатеричную системы счисления следующие целые числа: 1111₂, 1010101₂.

3. Перевести в восьмеричную и шестнадцатеричную системы счисления следующие дробные числа: 0,01111₂, 0,10101011₂.

4. Перевести в восьмеричную и шестнадцатеричную системы счисления следующие числа: 11,01₂, 110,101₂.

5. Перевести в двоичную систему счисления следующие числа: 46,27₈, ЕF,12₁₆.

6. Сравнить числа, выраженные в различных системах счисления: 1101₂ и D₁₆; 0,11111₂ и 0,22₈; 35,63₈ и 16,С₁₆.

1 Составить таблицу соответствия двоичных тетрад и шестнадцатеричных цифр.

2. Перевести в восьмеричную и шестнадцатеричную системы счисления следующие целые числа: 1111₂, 1010101₂.

3. Перевести в восьмеричную и шестнадцатеричную системы счисления следующие дробные числа: 0,01111₂, 0,10101011₂.

4. Перевести в восьмеричную и шестнадцатеричную системы счисления следующие числа: 11,01₂, 110,101₂.

5. Перевести в двоичную систему счисления следующие числа: 46,27₈, ЕF,12₁₆.

6. Сравнить числа, выраженные в различных системах счисления: 1101₂ и D₁₆; 0,11111₂ и 0,22₈; 35,63₈ и 16,С₁₆.

1 Составить таблицу соответствия двоичных тетрад и шестнадцатеричных цифр.

2. Перевести в восьмеричную и шестнадцатеричную системы счисления следующие целые числа: 1111₂, 1010101₂.

3. Перевести в восьмеричную и шестнадцатеричную системы счисления следующие дробные числа: 0,01111₂, 0,10101011₂.

4. Перевести в восьмеричную и шестнадцатеричную системы счисления следующие числа: 11,01₂, 110,101₂.

5. Перевести в двоичную систему счисления следующие числа: 46,27₈, ЕF,12₁₆.

6. Сравнить числа, выраженные в различных системах счисления: 1101₂ и D₁₆; 0,11111₂ и 0,22₈; 35,63₈ и 16,С₁₆.

Основы логики. Логические операции и таблицы истинности

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

Глоссарий, определения логики

Высказывание – это повествовательное предложение, про которое можно определенно сказать истинно оно или ложно (истина (логическая 1), ложь (логический 0)).

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

Логическое выражение – устное утверждение или запись, в которое, наряду с постоянными величинами, обязательно входят переменные величины (объекты). В зависимости от значений этих переменных величин (объектов) логическое выражение может принимать одно из двух возможных значений: истина (логическая 1) или ложь (логический 0).

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

Логические операции и таблицы истинности

1) Логическое умножение или конъюнкция:

Конъюнкция - это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное сложное выражение ложно.
Обозначение: F = A & B.

2) Логическое сложение или дизъюнкция:

Дизъюнкция - это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно тогда и только тогда, когда оба простых логических выраженныя ложны.
Обозначение: F = A + B.

Таблица истинности для дизъюнкции

3) Логическое отрицание или инверсия:

Инверсия - это сложное логическое выражение, если исходное логическое выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное логическое выражение ложно, то результат отрицания будет истинным. Другими простыми слова, данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО.

Таблица истинности для инверсии

Основы логики. Логические операции и таблицы истинности

4) Логическое следование или импликация:

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

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

Логическая операция импликации «если А, то В», обозначается А → В.

Таблица истинности для импликации

A	B	F
1	1	1
1	0	0
0	1	1
0	0	1

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

Докажем методом сравнения таблиц истинности, что операция импликации А → В равносильна логическому выражению ¬A ∨ B.

A	B	C
0	0	1
0	1	1
1	0	0
1	1	1

5) Логическая равнозначность или эквивалентность:

Эквивалентность - это сложное логическое выражение, которое является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность.

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

Логическая операция эквивалентности «А тогда и только тогда, когда В» обозначается А~В (или А ≡ В).

Таблица истинности для эквивалентности

A	B	F
1	1	1
1	0	0
0	1	0
0	0	1

Докажем, используя таблицы истинности, что операция эквивалентности А~В равносильна логическому выражению: (A ∨ ¬B) ∧ (¬A ∨ B).

A	B	C = A~ B
0	0	1
0	1	0
1	0	0
1	1	1

Порядок выполнения логических операций в сложном логическом выражении

1. Инверсия;
2. Конъюнкция;
3. Дизъюнкция;
4. Импликация;
5. Эквивалентность.

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

4.3. Основные логические тождества.

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

В таблице 1 приведен набор логических тождеств (пар эквивалентных логических выражений), которые полезно знать, сдавая ЕГЭ. Это не значит, что другие элементарные тождества вам не понадобится. Мы просто надеемся, что вы сможете при необходимости вывести другие понадобившиеся тождества. Желательно уметь пользоваться этими формулами так же свободно, как, например, алгебраическими формулами сокращенного умножения. Деление формул в таблице на группы – условное и приведено лишь для удобства восприятия.

Примечание. В таблицах использована «алгебро-подобная» система обозначений логических операций. Конъюнкция (логическое умножение) и дизъюнкция (логическое сложение) обозначаются символами «·» и «+» соответственно, а отрицание – чертой сверху. Эти обозначения общеприняты среди инженеров (но не специалистов по математической логике :)) и используются в некоторых школьных учебниках, в частности, в учебниках К.Ю.Полякова и Е.А.Еремина

Таблица 1.

А. Свойства 0, 1 и отрицания			С. Импликация и эквивалентность
Свойства 0 и 1	а · 0 = 0	а + 0 = 0	Определение импликации
	а · 1 = 1	а + 1 = 1	Полезные свойства
Свойства отрицания	а · = 0	а + = 1
	= а		Эквивалентность

5. Высказывания о множествах

Логические выражения над элементарными высказываниями о множествах (высказывания вида "A=∅", "x∈A" "A⊆B" ) можно преобразовывать, используя не только общие правила преобразования логических выражений, но и свои правила, связанные со свойствами операций над множествами. Ниже U - это универсальное множество; x - его произвольный элемент, A, B, X - множества. Верны следующие утверждения.

1. Следующие высказывания эквивалентны, т.е. имеют одинаковые логические значения при любых x, A, B (это обозначено знаком ⇔)

а) (x∈A)∧(x∈B) ⇔ x∈A∩B; б) (x∈A)∨(x∈B) ⇔ x∈A∪B; в) ¬(x∈A) ⇔ x∈U\A; г) (x∈A)∧ (¬(x∈B)) ⇔ x∈A\B.

2. Следующие высказывания эквивалентны, т.е. имеют одинаковые логические значения при любых X, A, B (это обозначено знаком ⇔)

а) (X ∩ A ≠ 0) ∨ ( X∩ B ≠ 0) ⇔ (X ∩ (A∪B) ≠ 0); б) (X∩A = 0) ∧ (X∩B = 0)⇔(X∩ (A∪B) = 0).

3. а) Пусть A ⊆ B, т.е. A — подмножество B; x - элемент универсального множества U. Тогда истинно высказывание: (x ∈ A) → (x∈ B);

б) Пусть высказывание (x ∈ A) → (x∈ B) истинно при любом x ∈ U. Тогда A ⊆ B.

4. а) Пусть A ⊆B, т.е. A — подмножество B; X ⊆ U произвольное множества. Тогда истинно высказывание:

(X∩A ≠ 0) → (X∩B ≠ 0)

б) Пусть высказывание (X∩A ≠ 0) → (X∩B ≠ 0) истинно для любого множества X ⊆ U. Тогда A ⊆В.

5. Следующее высказывания истинны для любых множеств A, B, X

((X∩A ≠ 0) ∧ (X∩B = 0) ) → (X∩ (A\B) ≠ 0)

6. Примеры эквивалентных преобразований

1. Первые два примера содержат доказательства свойств импликации из таблицы 1С (см. п.4).

Пример 1. Преобразуем выражение (¬y)→ (¬x) в выражение x→ y. Имеем :(¬y) ∨(¬(¬x)) = (¬y)∨x = x → y.

1) (¬y) ∨(¬(¬x) ) - замена импликации дизъюнкцией

2) (¬y)∨x -снятие двух отрицаний

3) x → y -замена дизъюнкции импликацией

Пример 2. Преобразуем выражение (x∧y)→ z в выражение x → (y→ z). Имеем: (x∧y)→ z = ¬(x∧y)∨z = ((¬x)∨(¬y))∨z =(¬x)∨((¬y)∨z) = (¬x)∨(y → z) = x → (y → z)

1) ¬(x∧y) ∨ z - замена импликации дизъюнкцией

2) ((¬x) ∨ (¬y) )∨ z -правило де Моргана

3) (¬x) ∨ ((¬y) ∨ z) - сочетательный закон для дизъюнкции

4) (¬x) ∨ (y → z) - замена дизъюнкции импликацией

5) x → (y → z) -замена дизъюнкции импликацией

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

Пример 3. Рассмотри выражение (x→y)∨z. Имеем: (x→y)∨z = ((¬x) ∨ y)∨ z = ) (¬x) ∨ (y∨ z) = x → (y∨z)

1) ((¬x) ∨ y)∨ z - замена импликации дизъюнкцией

2) (¬x) ∨ (y∨ z) - сочетательный закон для дизъюнкции

3) x → (y∨ z) - замена дизъюнкции импликацией

Пример 4. Рассмотри выражение (x→ z)∨(y→z). Имеем: (x→ z)∨(y→z)=((¬x)∨z)∨((¬y)∨z)=(¬x)∨z∨(¬y)∨z =(¬x)∨(¬y)∨z∨z=(¬x)∨(¬y)∨z=¬(x∧y)∨z = (x ∧ y) → z

1) ((¬x)∨ z) ∨ ((¬y) ∨ z) - две замены импликации дизъюнкцией

2) (¬x)∨ z∨ (¬y) ∨ z -раскрытие скобок (сочетательный закон для дизъюнкции)

3) (¬x) ∨ (¬y) ∨ z ∨ z - переместительный закон для дизъюнкции

4) (¬x) ∨ (¬y) ∨ z - закон поглощения для дизъюнкции

5) ¬(x ∧ y) ∨ z - правило де Моргана

6) (x ∧ y) → z - замена дизъюнкции импликацией

Алгебра логики

Алгебра логики – раздел математики, изучающий высказывания с точки зрения их логических значений (истинности или ложности) и логических операций над ними.
Иногда её называют двоичной логикой или булевой алгеброй по имени английского математика Джорджа Буля.

Для удобства записи, используют обозначение результата через F, а логические высказывания через A(X) и B(Y). Так как возможных вариантов значений всего два, их можно обозначить через 0 (ложь, нет, false, no) и 1 (истина, да, true, yes).

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

Логическое высказывание

Логическое высказывание – любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

Примеры

Тождественно истинные высказывания (тавтология)

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

Таким образом, такое высказывание всегда равно 1.

В качестве примеров можно привести высказывания, являющиеся разъяснением термина на основе его словообразования (авиабаза – место базирования авиационной техники). Или любое сложное высказывание, смысл которого сводится к формуле А\/¬A.

Тождественно ложные высказывания

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

Таким образом, такое высказывание всегда равно 0. Важно, что большинство высказываний сводится к формуле А/\¬A.

Эквивалентные высказывания

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

Логические операции

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

1. логическое умножение (конъюнкция или логическое И) [AND, &, /\];

2. логическое сложение (дизъюнкция или логическое ИЛИ) [OR, |, \/];

3. логическое отрицание (инверсия или логическое НЕ) [NOT, ¬, ];

4. логическое следование (импликация) [→];

5. логическое равенство (эквивалентность) [↔, ~].

Логическое умножение (конъюнкция)

Представляет собой объединение нескольких логических выражений с помощью союза И. При практическом наборе на компьютере часто используют знаки прямого и обратного деления без пробела: /\

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

A	B	F=A&B
0	0	0
0	1	0
1	0	0
1	1	1

Отсюда вытекает обратное следствие, упрощающее вычисления для конъюнкции:
Если хотя бы одно значение ложно, то ложно и всё выражение.

Логическое сложение (дизъюнкция)

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

A	B	F=A\/B
0	0	0
0	1	1
1	0	1
1	1	1

Отсюда вытекает обратное следствие, упрощающее вычисления для дизъюнкции: Если хотя бы одно значение истинно, то истинно и всё выражение.

Логическое отрицание (инверсия)

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

A	F= ¬A
0	1
1	0

Логическое следование (импликация)

Связывает два логических выражения с помощью оборота ЕСЛИ..., ТО. Дополнительная операция, так как A → B = ¬A \/ B
Кроме того, при построении высказывания могут использоваться выражения «из... следует», «... влечет».

A	B	F=A→B
0	0	1
0	1	1
1	0	0
1	1	1

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

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

Логическое равенство (эквивалентность)

Образуется соединением двух логических выражений с помощью оборотов «тогда и только тогда», «необходимо и достаточно», «...равносильно...». Поскольку мы видим здесь двойное следование (и вправо и влево), операцию иногда называют двойной импликацией. Дополнительная операция, так как A ↔ B = (A \/ ¬B) & (¬A\/B)

A	B	F=A↔B
0	0	1
0	1	0
1	0	0
1	1	1

Суть: эквивалентность ложна только тогда, когда выражения разные.

Законы алгебры логики

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

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

Замечание. Знаки алгебры логики намеренно заменены на сложение и умножение.

№	Для ИЛИ	Для И	Примечание
1	A+0 = A	A • 1 = A	Ничего не меняется при действии, константы удаляются
2	A + 1 = 1	A • 0 = 0	Удаляются переменные, так как их оценивание не имеет смысла
3	A+B=B+A	AB=BA	Переместительный (коммутативности)
4	A+¬A= 1		Один из операторов всегда 1 (закон исключения третьего)
5		A•¬A= 0	Один из операторов всегда 0 (закон непротиворечия)
6	A+A=A	A•A=A	Идемпотентности (NB! Вместо A можно подставить составное выражение!)
7	¬¬A=A		Двойное отрицание
8	(A+B)+C=A+(B+C)	(A•B)•C=A•(B•C)	Ассоциативный
9	(A+B)•C=(A•C)+(B•C)	(A•B)+C=(A+C)•(B+C)	Дистрибутивный
10	(A+B)•(¬A+B)=B	(A•B)+(¬A•B)=B	Склеивания
11	¬(A+B) = ¬A•¬B	¬(A•B) = ¬A+ ¬B	Правило де Моргана
12	A+(A•C)=A	A•(A+C)=A	Поглощение
13	A→B=¬A+B и A→B = ¬B→¬A		Снятие (замена) импликации
14	1) A↔B = (A•B)+(¬A•¬B) 2) A↔B = (A + ¬B)•(¬A + B)		Снятие (замена) эквивалентности

Порядок решения логического выражения

В первую очередь надо учитывать, что порядок задается скобками.

Далее выполняются операции отрицания, конъюнкции, дизъюнкции, импликации, эквивалентности.

Построение таблиц истинности

Чтобы решить логическое выражение, необходимо построить таблицу истинности, описывающую ВСЕ возможные варианты значений переменных величин. В связи с тем, что мы используем булевы переменные (то есть имеющие только два значения: 0 и 1), количество вариантов легко сосчитать по формуле M = 2ⁿ,

где n – число переменных, а M – число строк в результирующей таблице.

Заполнение же значений фактически является последовательным вписыванием в каждой строке двоичных чисел. Для первой строки это будет 0 (00, 000...), для второй – 1 (01, 001...), а для последней – числа, состоящего из всех единиц. Выполнение этого несложного правила позволит не только избежать ошибок, но и облегчит решение, так как значения 0/1 будут подчиняться определенному порядку для каждой переменной.

Графическое решение числовых выражений по координатной прямой

Ряд заданий в алгебре логики основывается в использовании в качестве высказывания числового выражения. Например, (X 2) /\ ¬(X 5).

Хорошо видно, что выражение берется в скобки для однозначного восприятия. Прежде чем наносить значения на рисунок, следует избавиться от отрицания. В этом случае происходит замена знаков отношения на противоположные по схеме: ↔ ≤, = ↔ ≠.

В нашем примере мы получим (X 2) /\ (X ≤ 5).

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

Возможные целочисленные ответы – 3, 4, 5.

Построение логического выражения по таблице истинности

Задача является противоположной стандартной.

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

Решение текстовых задач

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

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

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

Каждое высказывание оформляется в виде логической переменной. Чаще всего удобно вводить переменные, обозначенные русскими буквами и связанные с объектами, описанными в задаче: Иван – И, красный – К (или Кр, если переменная К уже введена для Коли) и т.п.

Соотношение переменных определяется связывающими высказываниями.

• И, ИЛИ, НЕ.

• «из... следует»; «... влечет»; ЕСЛИ..., ТО (импликация)

• «тогда и только тогда», «необходимо и достаточно», «...равносильно...» (эквивалентность).

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

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

Логическое значение категорически рекомендуется записывать как 0 (ложь) или 1 (истина). Это поможет дифференцировать записи, а не спотыкаться о глупейшие варианты Л/И.

Решение

Введем обозначения для логических высказываний:
Л - победит Ласточка; С - победит Стрела; Т — победит Тормоз.
Запишем высказывания (высказывание Петра "Тормоз готовился очень тщательно" не содержит информации о месте и не может быть учтено):

1) ¬Л /\ С, 2) Л /\ ¬Т, 3) ¬С.

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

[(¬Л /\ С) /\ (Л /\ ¬Т) /\ ¬¬С] \/ [¬(¬Л /\ С) /\ ¬(Л /\ ¬Т) /\ ¬С] \/ [¬(¬Л /\ С) /\ (Л /\ ¬Т) /\ ¬С] = 1

Затем упростим его за счет двойного отрицания, правила Моргана и убрав ненужные для первого члена скобки:

[¬Л /\ С /\ Л /\ ¬Т /\ С] \/ [(Л \/ ¬С) /\ (¬Л \/ Т) /\ ¬С] \/ [(Л \/ ¬С) /\ (Л /\ ¬Т) /\ ¬С] = 1

Выражение по-прежнему немаленькое. Далее, по закону поглощения можно сократить показанное красным

[¬Л /\ С /\ Л /\ ¬Т /\ С] \/ [(Л \/ ¬С) /\ (¬Л \/ Т) /\ ¬С] \/ [(Л \/ ¬С) /\ (Л /\ ¬Т) /\ ¬С] = 1

[(¬Л \/ Т) /\ ¬С] \/ [(Л /\ ¬Т) /\ ¬С] = 1

{(¬Л \/ Т) \/ (Л /\ ¬Т)} /\ ¬С = 1

{¬Л \/ Т \/ (Л /\ ¬Т)} /\ ¬С = 1

Здесь {(Л \/ ¬Л \/ Т) /\ (¬Т \/ ¬Л \/ Т)} /\ ¬С = 1

В оставшейся части сократим противоположные слагаемые (по закону исключения третьего) Т /\ ¬Л /\ ¬С = 1

Конечно, можно сразу сказать, что в произведении все три множителя должны быть равны единице, то есть: Л = 1, Т = 0, С = 0. Ответ: победителем скачек стала Ласточка.

Но можно сделать то же, построив таблицу истинности:

Л	Т	С	F
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	0

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

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

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

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

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

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

3)
(повторяется второй сомножитель, что разрешено законом идемпотенции; затем комбинируются два первых и два последних сомножителя и используется закон склеивания);

4)

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

5)
(сначала добиваемся, чтобы знак отрицания стоял только перед отдельными переменными, а не перед их комбинациями, для этого дважды применяем правило де Моргана; затем используем закон двойного отрицания);

6)
(выносятся за скобки общие множители; применяется правило операций с константами);

7)
(к отрицаниям неэлементарных формул применяется правило де Моргана; используются законы двойного отрицания и склеивания);

8)
(общий множитель x выносится за скобки, комбинируются слагаемые в скобках — первое с третьим и второе с четвертым, к дизъюнкции применяется правило операции переменной с её инверсией);

9)
(используются распределительный закон для дизъюнкции, правило операции переменной с ее инверсией, правило операций с константами, переместительный закон и распределительный закон для конъюнкции);

10)
(используются правило де Моргана, закон двойного отрицания и закон поглощения).

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

Построение логического выражения по таблице истинности

Правила построения логического выражения по таблице истинности:

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

2. Объединить все минтермы операцией дизъюнкции.

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