Законы логики на уроках информатики и ИКТ

Урок по информатике рассчитан на учащихся 10-х классов общеобразовательной школы, в учебном плане которой входит раздел «Алгебра логики». Учащимся очень нелегко дается эта тема, поэтому мне, как учителю, захотелось заинтересовать их в изучении законов логики, упрощении логических выражений и с интересом подойти к решению логических задач. В обычной форме давать уроки по этой теме нудно и хлопотно, да и ребятам не всегда понятны некоторые определения. В связи с предоставлением информационного пространства, у меня появилась возможность выкладывать свои уроки в оболочке «learning». Учащиеся, зарегистрировавшись в ней, могут в свое свободное время посещать этот курс и перечитывать то, что было непонятно на уроке. Некоторые учащиеся, пропустив уроки по болезни, наверстывают дома или в школе пропущенную тему и всегда готовы к следующему уроку. Такая форма преподавания очень устроила многих ребят и те законы, которые им были непонятны, теперь в компьютерном виде ими усваиваются гораздо легче и быстрее. Предлагаю один из таких уроков информатики, который проводится интегративно с ИКТ.

План урока

1. Объяснение нового материала, с привлечением компьютера – 25 минут.
2. Основные понятия и определения, выложенные в «learning» — 10 минут.
3. Материал для любознательных – 5 минут.
4. Домашнее задание – 5 минут.

1. Объяснение нового материала

Законы формальной логики

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

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

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

Закон непротиворечия: невозможно, чтобы одно и то оке в одно то же время было и не было присуще одному и тому же в одном и том же отношении. То есть невозможно что-либо одновременно утверждать и отрицать.

Закон исключенного третьего: из двух противоречащих суждений одно истинно, другое ложно, а третьего не дано.

Закон достаточного основания: всякая истинная мысль должна быть достаточно обоснована.

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

Законы алгебры высказываний

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

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

Законы алгебры высказываний (алгебры логики) — это тавтологии.

Иногда эти законы называются теоремами.

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

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

Закон тождества:

А=А

Всякое понятие и суждение тождественно самому себе.

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

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

В рассуждении: Движение вечно. Хождение в школу — движение. Следовательно, хождение в школу вечно слово «движение» используется в двух разных смыслах (первое — в философском смысле — как атрибут материи, второе — в обыденном смысле — как действие по перемещению в пространстве), что приводит к ложному выводу.

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

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

А — истинно, то его отрицание не А должно быть ложным (и наоборот). Тогда их произведение будет всегда ложным.

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

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

1. На Марсе есть жизнь и на Марсе жизни нет.

2. Оля окончила среднюю  школу и учится в X классе.

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

В один и тот же момент времени высказывание может быть либо истинным, либо ложным, третьего не дано. Истинно либо

А, либо не А. Примеры выполнения закона исключенного третьего:

1. Число 12345 либо четное, либо нечетное, третьего не дано.

2. Предприятие работает убыточно или безубыточно.

3. Эта жидкость является или не является кислотой.

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

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

Парадокс (греч. paradoxos — неожиданный, странный) в этом примере возникает из-за того, что предложение ссылается само на себя. Другим известным парадоксом является задача о парикмахере: В одном городе парикмахер стрижет волосы всем жителям, кроме тех, кто стрижет себя сам. Кто стрижет волосы парикмахеру?

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

Например, определим, чему эквивалентно (равносильно) А (двойное отрицание А, т. е. отрицание отрицания А). Для этого построим таблицу истинности:

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

А. Таким будет столбец А.

Таким образом, мы можем сформулировать закон двойного отрицания:

Если отрицать дважды некоторое высказывание, то в результате получается исходное высказывание. Например, высказывание А = Матроскин — кот эквивалентно высказыванию А = Неверно, что Матроскин не кот.

Аналогичным образом можно вывести и проверить следующие законы:

Свойства констант:

Законы идемпотентности:

Сколько бы раз мы ни повторяли: телевизор включен или телевизор включен или телевизор включен …

значение высказывания не изменится. Аналогично от повторения на улице тепло, на улице тепло,… ни на один градус теплее не станет.

Законы коммутативности:

A v B = B v A

А & В = В & А

Операнды А и В в операциях дизъюнкции и конъюнкции можно менять местами.

Законы ассоциативности:

A v(B v C) = (A v B) v C;

А & (В & C) = (A & В) & С.

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

Законы дистрибутивности:

A v (B & C) = (A v B) &(A v C)

(дистрибутивность дизъюнкции
относительно конъюнкции)

А & (B v C) = (A & B) v (А & C)

(дистрибутивность конъюнкции
относительно дизъюнкции)

Закон дистрибутивности конъюнкции относительно дизъюнкции ана­логичен дистрибутивному закону в алгебре, а закон дистрибутивности дизъюнкции относительно конъюнкции аналога не имеет, он справедлив только в логике. Поэтому необходимо его доказать. Доказательство удобнее всего провести с помощью таблицы истинности:

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

A v (A & B) = A

A & (A v B) = A

Проведите доказательство законов поглощения самостоятельно.

Законы де Моргана:

Словесные формулировки законов де Моргана:

1.

2.

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

Примеры выполнения закона де Моргана:

1) Высказывание Неверно, что я знаю арабский или китайский язык тождественно высказыванию Я не знаю арабского языка и не знаю китайского языка.

2) Высказывание Неверно, что я выучил урок и получил по нему двойку тождественно высказыванию Или я не выучил урок, или я не получил по нему двойку.

Замена операций импликации и эквивалентности

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

Так, заменить операцию импликации можно в соответствии со следующим правилом:

Для замены операции эквивалентности существует два правила:

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

Знание правил замены операций импликации и эквивалентности помогает, например, правильно построить отрицание импликации.

Рассмотрим следующий пример.

Пусть дано высказывание:

Е = Неверно, что если я выиграю конкурс, то получу приз.

Пусть А = Я выиграю конкурс,

В = Я получу приз.

Тогда

Отсюда, Е = Я выиграю конкурс, но приз не получу.

Интерес представляют и следующие правила:

Доказать их справедливость можно также с помощью таблиц истинности.

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

Например, фраза

Если Винни-Пух съел мед, то он сыт

тождественна фразе

Если Винни-Пух не сыт, то меда он не ел.

Задание: придумайте фразы-примеры на данные правила.

2. Основные понятия и определения в Приложении 1

3. Материал для любознательных в Приложении 2

4. Домашнее задание

1) Выучить законы логики, используя курс «Алгебры логики», размещенный в информационном пространстве (www.learning.9151394.ru).

2) Проверить на ПК доказательство законов де Моргана, построив таблицу истинности.

Приложения

1. Основные понятия и определения (Приложение 1).
2. Материал для любознательных (Приложение 2).

Логические выражения

Понятие логического выражения или логической формулы вводится индуктивно.

Логической формулой является

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

2) если A и B — формулы, то, А*В и (А*В) — тоже формулы, где знак “*” означает любую из логических бинарных операций (см. “Логические операции. Кванторы”).

Формулой является, например, следующее выражение (x & y) z. Каждой формуле при заданных значениях входящих в нее переменных можно приписать одно из двух значений — 0 или 1.

Формулы А и В, зависящие от одного и того же списка переменных x1, x2, x3, …, xn, называют равносильными, или эквивалентными, если на любом наборе значений переменных x1, x2, x3, …, xn они принимают одинаковые значения. Для обозначения равносильности формул используется знак равенства, например, А = В.

Любую формулу можно преобразовать к равносильной ей, в которой используются только операции &, и отрицание.

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

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

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

Для логических операций в одном логическом выражении установлен следующий порядок вычислений:

· отрицание — первый, наивысший приоритет;

· конъюнкция — второй приоритет;

· дизъюнкция, разделительная дизъюнкция — третий приоритет;

· импликация, эквивалентность — низший приоритет.

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

В алгебре логики дизъюнкция (логическое сложение) играет роль, аналогичную сложению в алгебре действительных чисел, конъюнкция (логическое умножение) — умножению, а отрицание (инверсия значения логической формулы) — унарному минусу (инверсия знака обычной формулы). Операция эквивалентность аналогична операции отношения “=”, а операция импликация — операции отношения “”.

Канонические формы

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

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

Формулу называют элементарной конъюнкцией, если она является конъюнкцией одной или нескольких переменных, взятых с отрицанием или без отрицания. Например, формулы x₂, x₂, x₁ & x₃, x₁ & x₃ & x₁ & x₃  являются элементарными конъюнкциями.

Формула называется дизъюнктивной нормальной формой (ДНФ), если она является дизъюнкцией элементарных конъюнкций. ДНФ записываются в виде A₁ A₂ … A_n, где каждое A_i — элементарная конъюнкция. Например, x₂x₁ & x₃, x₂ & x₂x₁ & x₂— дизъюнктивные нормальные формы.

Формула А от k переменных называется совершенной дизъюнктивной нормальной формой (СДНФ), если

1) А является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция k переменных x₁, x₂, …, x_k, причем на i-м месте этой конъюнкции стоит либо переменная x_i, либо ее отрицание;

2) все элементарные конъюнкции в такой ДНФ попарно различны.

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

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

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

Теорема. Пусть — f (x₁, x₂, …, x_n)булева функция от n переменных, не равная тождественно нулю. Тогда существует совершенная дизъюнктивная нормальная форма, выражающая функцию f, которую можно построить по следующему алгоритму:

1. В таблице истинности отмечаем наборы переменных, на которых значение функции f равно единице.

2. Записываем для каждого отмеченного набора конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае — ее отрицание.

3. Все полученные конъюнкции связываем операциями дизъюнкции.

Доказательство. Каждая элементарная конъюнкция, вошедшая в СДНФ, принимает значение 1 только на единственном наборе. Отсюда следует, что если функция на каком-то наборе равна 1, то и вся СДНФ равна 1 в силу того, что по построению соответствующая элементарная конъюнкция, вошедшая в СДНФ, равна 1. А если функция равна 0, то и СДНФ равна 0, т.к. на этом наборе равны 0 все вошедшие в СДНФ элементарные конъюнкции. Таким образом, СДНФ равносильна исходной функции.

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

Доказательство. Для всех функций, отличных от 0, это можно сделать с помощью СДНФ, а ноль можно выразить, например, как x &`x.

Методические рекомендации

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

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

2) Во многих языках программирования используется только несколько логических операций, как правило, операция логического сложения, логического умножения и отрицания, а также операция разделительной дизъюнкции. Поэтому, если полученная формула содержит не только операции &, и отрицание, то учащиеся должны уметь выполнять тождественные преобразования для построения ДНФ (дизъюнктивной нормальной формы). Умение выполнять тождественные преобразования основано на знании основных законов алгебры логики, но формируется это умение в результате выполнения большого числа заданий. На формирование этого умения времени практически не отводится, но практика показывает, что достаточно научить учащихся выражать операции импликации и эквивалентности через &, и отрицание. Большинство законов алгебры логики ученикам интуитивно понятны и не требуют запоминания. Исключение составляют законы поглощения и де Моргана. Последние особенно часто применяются в программировании. Знакомство с законами алгебры логики начинается в базовом курсе информатики и продолжается в старшей школе.

3) Для построения СДНФ учащиеся должны уметь без ошибок строить таблицу истинности для конкретной логической формулы. А для этого надо требовать, чтобы учащиеся строго соблюдали порядок перечисления набора значений переменных: если каждый набор значений переменных рассматривать как двоичное число, то все числа должны быть записаны в порядке возрастания. Например, для формулы от трех переменных перечисление набора значений в таблице истинности должно быть выполнено в следующем порядке:

4) Перед изложением формулировки теоремы о СДНФ надо пояснить, для чего используются нормальные формы (поиск аналитического вида булевой функции, заданной таблицей истинности; минимизация представления булевой функции с использованием только трех логических операций &, и отрицания: такая задача возникает при конструировании микросхем, в частности, для производства компьютеров, и т.д.). Учащимся на примерах надо показать, что проблема представления формул в виде СДНФ не надуманна, ее решение имеет важное практическое значение в информатике. Данная тема подлежит рассмотрению в старших профильных классах.

5) Если вы задаете своим ученикам задания на построение отрицания к сложному высказыванию (а проще всего это делать через построение отрицания к соответствующему логическому выражению), то им следует пояснить, почему в этом случае квантор общности заменяется на квантор существования и наоборот (см. “Логические операции. Кванторы”).

Очевидно, что высказывание, содержащее квантор общности (например, “Все мужчины старше 70 лет имеют длинную седую бороду”), можно заменить на следующее: “И Иванов А.П., и Кравцов И.Г., и Петухов С.П., и … старше 70 лет и имеют длинную седую бороду”. Это высказывание можно записать следующей формулой: И & К & П & …, где буквой И обозначено высказывание “Иванов А.П. (который старше 70 лет) носит длинную седую бороду”, буквой К обозначено высказывание “Кравцов И.Г. носит длинную седую бороду” и т.д. При построении отрицания к первоначальному сложному высказыванию, содержащему квантор общности, воспользуемся законом де Моргана. Тогда получим:

Этой формуле соответствует высказывание “Или Иванов А.П. не имеет длинной седой бороды, или Кравцов И.Г. не имеет длинной седой бороды, или Петухов С.П. … или … не имеет длинной седой бороды”, другими словами, “Существует мужчина старше 70 лет, который не имеет длинной седой бороды”.

---

⁶ От латинских слов idem — тот же самый и potens — сильный; дословно — равносильный.

Решение заданий ЕГЭ по информатике с использованим элементов алгебры логики

В настоящее время на вступительных экзаменах по информатике есть много заданий по теме “алгебра логики”. Цель данного урока – закрепление навыков решения заданий ЕГЭ по информатике с использованием элементов алгебры логики.

Цели урока:

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

Задачи урока:

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

Ход урока

Повторение логических операций и законов.

Применение логических операций и законов на практике.

Объяснение домашнего задания.

Сегодня мы с вами завершаем тему “Основы логики” и применим основные логические операции, законы преобразования для решения заданий ЕГЭ по информатике.

Урок идет параллельно с презентацией. <Приложение1>

1. Повторение логических операций и законов.

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

Вопросы:

1. Основоположник формальной логики?

Аристотель.

2. Основоположник алгебры логики?

Джордж Буль.

3. Перечислите логические операции:

¬ отрицание (инверсия)
&, /\ конъюнкция (“И”)
V дизъюнкция (“ИЛИ”)
логическое следование (импликация)
равнозначность (эквивалентность)

4. В чем смысл закона двойного отрицания?

Двойное отрицание исключает отрицание.

5. Законы де Моргана (законы общей инверсии).

Отрицание дизъюнкции является конъюнкцией отрицаний:

¬(A V B) = ¬A /\ ¬B

Отрицание конъюнкции является дизъюнкцией отрицаний:

¬(A /\B) = ¬A V ¬B

6. Закон идемпотентности (одинаковости).

A V A = A

A /\ A = A

7. В чём смысл закона исключения третьего?

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

A V ¬А= 1

8. О чём закон противоречия?

Не могут быть одновременно истинны утверждение и его отрицание:

A /\ ¬А= 0

9. Закон исключения констант.

Для логического сложения:

A V 1 = 1 A V 0 = A

Для логического умножения:

A /\ 1 = A A /\ 0 = 0

10. Как выразить импликацию через дизъюнкцию?

А В = ¬A V В

2. Примение логических операций и законов на практике.

Пример 1. (Задание А11 демоверсии 2004 г.)

Для какого имени истинно высказывание:

¬ (Первая буква имени гласная -> Четвертая буква имени согласная)?

1) ЕЛЕНА

2) ВАДИМ

3) АНТОН

4) ФЕДОР

Решение. Сложное высказывание состоит из двух простых высказываний:

А – первая буква имени гласная,

В – четвертая буква имени согласная.

¬ (А В) = ¬ (¬A V В) = (¬ (¬А) /\ ¬B) = A /\ ¬B

Применяемые формулы:

1. Импликация через дизъюнкцию А ? В = ¬A V В

2. Закон де Моргана ¬(A V B) = ¬A /\ ¬B

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

(Первая буква имени гласная /\ Четвертая буква имени гласная)

Ответ: 3

Пример 2. (Задание А12 демоверсии 2004 г.)

Какое логическое выражение равносильно выражению ¬ (А \/ ¬B)?

1) A \/ B

2) A /\ B

3) ¬A \/ ¬B

4) ¬A /\ B

Решение. ¬ (А \/ ¬B)= ¬ А \/ ¬ (¬B)= ¬ А \/ B

Ответ: 4

Пример 3.

Составить таблицу истинности для формулы

¬ (B /\ C) V (A/\C B)

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

¬ (B /\ C) V (A/\C B)

2   1   5   3   4

Составить таблицу истинности.

Сколько строк будет в вашей таблице? 3 переменных: А, В, С; 2³=8

Сколько столбцов? 5 операций + 3 переменных = 8

Решение:

A	B	C	(B /\ C)	¬ (B /\ C)	A/\C	(A/\C ? B)	¬ (B /\ C) V (A/\C B)
0	0	0	0	1	0	1	1
0	0	1	0	1	0	1	1
0	1	0	0	1	0	1	1
0	1	1	1	0	0	1	1
1	0	0	0	1	0	0	1
1	0	1	0	1	1	1	1
1	1	0	0	1	0	0	1
1	1	1	1	0	1	1	1

Какие ответы получились в последнем столбце?

Ответ: 1

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

Решим этот пример аналитическим методом:

упрощаем выражение

¬ (B /\ C) V (A/\C B)= (применим формулу для импликации)

¬ (B /\ C) V ¬ (A /\ C) V B = (применим 1 и 2 законы де Моргана)

(¬B V ¬C) V (¬A V ¬C) V B = (уберём скобки)

¬B V ¬C V ¬A V ¬C V B= (применим переместительный закон)

¬B V B V ¬C V ¬C V ¬A = (закон исключения третьего, закон идемпотентности)

1 V ¬С V ¬A = 1 V ¬A = 1 (закон исключения констант)

Ответ: 1, означает, что формула является тождественно-истинной или тавтологией.

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

(задание 3 домашнего задания)

Пример 4.

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

Для обозначения логической операции “ИЛИ” в запросе используется символ I, а для логической операции “И” – символ &.

А	Законы & Физика
Б	Законы I (Физика & Биология)
В	Законы & Физика & Биология & Химия
Г	Законы I Физика I Биология

Решение:

Первый способ основан на рассуждении. Рассуждая логически, мы видим, что больше всего будет найдено страниц по запросу Г, так как при его исполнении будут найдены и страницы со словом “законы”, и страницы, со словом “физика”, и страницы со словом “биология”. Меньше всего будет найдено страниц по запросу В, так как в нем присутствие всех четырех слов на искомой странице. Осталось сравнить запросы А и Б. По запросу Б будут найдены все страницы, соответствующие запросу А, (так как в последних обязательно присутствует слово “законы”), а также страницы, содержащие одновременно слова “физика” и “биология”. Следовательно по запросу Б будет найдено больше страниц, чем по запросу А. Итак, упорядочив запросы по возрастанию страниц, получаем ВАБГ.

Ответ: ВАБГ.

Второй способ предполагает использование графического представления операций над множествами. (Смотри презентацию)

Пример 5. (Задание А16 демоверсии 2006 г.)

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

Фамилия	Пол	Математика	Русский язык	Химия	Информатика	Биология
Аганян	ж	82	56	46	32	70
Воронин	м	43	62	45	74	23
Григорчук	м	54	74	68	75	83
Роднина	ж	71	63	56	82	79
Сергеенко	ж	33	25	74	38	46
Черепанова	ж	18	92	83	28	61

Сколько записей в данном фрагменте удовлетворяют условию

“Пол=’м’ ИЛИ Химия>Биология”?

1) 5

2) 2

3) 3

4) 4

Решение:

Выбираем записи: Мальчики (двое) и Химия>Биология (трое, но один мальчик, уже взялся 1 раз). В итоге 4 записи удовлетворяют условию.

Ответ: 4

Задание 6. (Задание В4 демоверсии 2007 г)

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

Один считает, что первой будет Наташа, а Маша будет второй.

Другой болельщик на второе место прочит Люду, а Рита, по его мнению, займет четвертое место.

Третий любитель тенниса с ними не согласился. Он считает, что Рита займет третье место, а Наташа будет второй.

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

Какое место на чемпионате заняли Наташа, Маша, Люда, Рита?

(В ответе перечислите подряд без пробелов числа, соответствующие местам девочек в указанном порядке имен.)

Решение:

Обозначим высказывания:

Н1 = “первой будет Наташа”;

М2 = “второй будет Маша”;

Л2 = “второй будет Люда”;

Р4 = “четвертой будет Рита”;

Р3 = “третьей будет Рита”;

Н2 = “второй будет Наташа”.

Согласно условию:

из высказываний 1 болельщика следует, что Н1VМ2 истинно;

из высказываний2 болельщика следует, что Л2VР4 истинно;

из высказываний 3 болельщика следует, что Р3VН2 истинно.

Следовательно, истинна и конъюнкция

(Н1VМ2) /\ (Л2VР4) /\ (Р3VН2) = 1.

Раскрыв скобки получим:

(Н1VМ2) /\ (Л2VР4) /\ (Р3VН2) = (Н1/\Л2V Н1/\Р4 V М2/\Л2 V М2/\Р4) /\ (Р3VН2)=

Н1/\ Л2/\Р3 V Н1/\Р4/\Р3 V М2/\Л2/\Р3 V М2/\Р4/\Р3 V Н1/\Л2/\Н2 V Н1/\Р4/\Н2 V М2/\Л2/\Н2 V М2/\Р4/\Н2 = Н1/\ Л2/\Р3 V 0 V 0 V 0 V 0 V 0 V 0 V= Н1/\ Л2/\Р3

Наташа-1, Люда-2, Рита-3, а Маша-4.

Ответ: 1423

3. Объяснение домашнего задания.

Задание 1. (Задание В8 демоверсии 2007г)

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

Для обозначения логической операции “ИЛИ” в запросе используется символ |, а для логической операции “И” – &.

А	волейбол | баскетбол | подача
Б	волейбол | баскетбол | подача | блок
В	волейбол | баскетбол
Г	волейбол & баскетбол & подача

Задание 2 (Задание В4 демоверсии 2008г)

Перед началом Турнира Четырех болельщики высказали следующие предположения по поводу своих кумиров:

A) Макс победит, Билл – второй;

B) Билл – третий. Ник – первый;

C) Макс – последний, а первый – Джон.

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

Какое место на турнире заняли Джон, Ник, Билл, Макс?

(В ответе перечислите подряд без пробелов места участников в указанном порядке имен.)

Оценки за урок.

Урок по информатике «Основы логики»

Цели:

1. Введение в предмет “Алгебра логики”.
2. Сформировать у учащихся понятия: формы мышления, алгебра высказываний, логическое высказывание, логические величины, логические операции.
3. Способствовать формированию логического мышления, интереса к разделу информатики - алгебре логики.
4. Закрепить полученные ЗУН.

Формы организации урока: объяснительно-иллюстративный, диалогический.

Ход урока.

I. Изложение нового материала.

1. Этапы развития логики.

Логика очень древняя наука.

1-й этап связан с работами ученого и философа Аристотеля (384-322 г.г. до н.э.). Он пытался найти ответ на вопрос “Как мы рассуждаем”, изучал правила мышления. Аристотель впервые дал систематическое изложение логики. Он подверг анализу человеческое мышление, его формы – понятие, суждение, умозаключение. Так возникла формальная логика.

2-й этап – появление математической, или символической, логики. Основы ее заложил немецкий ученый и философ Г.В. Лейбниц (1646-1716). Он сделал попытку построить первые логические исчисления, считал, что можно заменит простые рассуждения действиями со знаками, и привел соответствующие правила. Но он выдвинул только идею, а развил её окончательно англичанин Д. Буль (1815-1864). Буль считается основоположником математической логики как самостоятельной дисциплины. В его работах логика обрела свой алфавит, свою орфографию и грамматику.

2. Формы мышления.

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

Основными формами мышления являются понятие, суждение, умозаключение.

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

Например: компьютер, трапеция, портфель, ураганный ветер.

Упражнение 1 (устно). Приведите свои примеры.

Понятие имеет две стороны: содержание и объем.

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

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

Например:

1. Объем понятия город – это множество, состоящее из городов, носящих имя Москва, Одесса, Казань, Уфа, Нижнекамск и др.
2. Объем понятия персональный компьютер – совокупность существующих в мире персональных компьютеров.

Упражнение 2 (устно)

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

Опр.3 Суждение (высказывание, утверждение) – это форма мышления, в которой что-либо утверждается или отрицается о свойствах реальных предметов и отношениях между ними. Высказывание может быть либо истинным, либо ложным, и может быть либо простым, либо составным (сложным).

Например:

1. Истинное и простое высказывание: Буква “т” - согласная.
2. Ложное и сложное высказывание: Осень наступила, и грачи прилетели.

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

Например:

1. Уходя, гасите свет!
2. Кто хочет быть счастливым?

Высказывания могут выражаться с помощью математических, физических, химических и прочих знаков. Например: 5>3, H₂O+SO₂=H₂SO₄.

Упражнение 3 (устно). Объясните, почему следующие высказывания не являются высказываниями:

1. Какого цвета твой велосипед?
2. Число Х больше пяти?
3. 5Х-2
4. Посмотрите в окно.
5. Пейте томатный сок!
6. Вы были в музее?
7. Разность чисел 12 и Х равна 6.

Упражнение 4 (устно). Какие из следующих высказываний являются истинными, а какие ложными?

1. Город Москва – столица России.
2. Число 12 – простое.
3. 7*3=1.
4. 12<15.
5. Сканер – устройство, которое может напечатать на бумаге то, что изображено на экране компьютера.
6. Клавиатура – устройство ввода информации.

Упражнение 5 (устно). Приведите свои примеры истинных и ложных высказываний.

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

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

Например:

1. Все металлы – простые вещества. Литий – металл. Литий – простое вещество.

2. Все школьники – отличники. Вовочка – школьник. Вовочка – отличник.

Упражнение 6.

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

3. Алгебра высказываний.

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

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

Под высказыванием (суждением) будем понимать повествовательное предложение, относительно которого можно сказать, истинно или ложно.

В алгебре высказываний простым высказываниям ставятся в соответствии логические переменные, обозначаемые прописными буквами латинского алфавита.

Например:

А= “Листва на деревьях опадает осенью”.
В= “Земля прямоугольная”.

Высказывания, как говорилось уже ранее, могут быть истинными или ложными. Истинному высказыванию соответствует значение логической переменной 1, а ложному – значение 0 .

Например:

А=1
В=0

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

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

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

Рассмотрим три базовых логических операций – инверсию, конъюнкцию, дизъюнкцию и дополнительные – импликацию и эквивалентность.

Логическая операция	Название	Соответствует союзу	Обозначение знаками	Таблица истинности	Логическая операция
Инверсия (от лат. inversion – переворачиваю)	отрицание	не А		А 1 0 0 1	Опр. 8 Инверсия логической переменной истина, если переменная ложна, и, наоборот, инверсия ложна, если переменная истинна.
Конъюнкция (от лат. conjunction – связываю)	Логическое умножение	А и В		А В 1 1 1 1 0 0 0 1 0 0 0 0	Опр.9Конъюнкция двух логических переменных истинна тогда и только тогда, когда оба высказывания, истинны.
Дизъюнкция (от лат. disjunction – различаю)	Логическое сложение	А или В		А В 1 1 1 1 0 1 0 1 1 0 0 0	Опр. 10 Дизъюнкция двух логических переменных ложна тогда и только тогда, когда оба высказывания ложны.
Импликация (от лат. implication – тесно связывать)	Логическое следование	Если А, то В; Когда А, тогда В	А–условие В-следствие	А В 1 1 1 1 0 0 0 1 0 0 0 1	Опр. 11 Импликация двух логических переменных ложна тогда и только тогда, когда из истинного основания следует ложное следствие.
Эквивалентность (от лат. equivalents — равноценность)	Логическое равенство	А тогда и только тогда, когда В		А В 1 1 1 1 0 0 0 1 0 0 0 1	Опр. 12 Эквивалентность двух логических переменных истинна тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны

Упражнение 7. Даны два простых высказывания:

А= “Щука – рыба”;
В=“Ворона – певчая птица”.

Составьте из них все возможные составные (сложные) высказывания и определите их истинность.

При вычислении значения логического выражения (формулы) логические операции вычисляются в определенном порядке, согласно их приоритету:

1. инверсия,
2. конъюнкция,
3. дизъюнкция,
4. импликация и эквивалентность.

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

Например: дана формула

Порядок вычисления:

— инверсия
— конъюнкция
— дизъюнкция
— импликация
- эквивалентность.

Упражнение 8.

Дана формула . Определите порядок вычисления.

II. Закрепление изученного материала.

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

1. Число 456 трехзначное и четное.
2. Неверно, что Солнце движется вокруг Земли.
3. Число делится на 9 тогда и только тогда, когда сумма его цифр делится на 9.
4. Луна – спутник Земли.
5. На уроке химии ученики выполняли лабораторную работу, и результаты исследований записывали в тетрадь.
6. Если число оканчивается на 0, то оно делится на 10.
7. Чтобы погода была солнечной, достаточно, чтобы не было ни ветра, ни дождя.
8. Если у меня будет свободное время и не будет дождя, тоя не буду писать сочинения, а пойду на дискотеку.
9. Без Вас хочу сказать Вам много
   При Вас я слушать Вас хочу.
10. Если человек с детства и юности своей не давал нервам властвовать над собой, то они не привыкнут раздражаться и будут ему послушны.

2. Постройте отрицания следующих высказываний.

1. На улице сухо.
2. Сегодня выходной день.
3. Ваня не был готов сегодня к урокам.
4. Неверно, что число 3 не является делителем числа 198.
5. Некоторые млекопитающие не живут на суше.
6. Неверно, что число 17 – простое.

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

1. “Луна – спутник Земли”, “Неверно, что Луна спутник Земли”, “Неверно, что Луна не является спутником Земли”;
2. “2007 < 2008”, “2007 > 2008”, “2007 ? 2008”;
3. “Прямая а перпендикулярна прямой с”; “Прямая а не параллельна прямой с”; “Прямая а не пересекается с прямой с”.

4. По данным формам сложных высказываний запишите высказывания на русском языке.

1.
2.
3.
4.
5.

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

6. Даны два высказывания: А = “2 х 2 = 4”, В = “2 х 2 = 5”. Очевидно, что А=1, В=0. Какие из высказываний истинны?

а)
б)
в) А
г)
д)

5.2. Что такое логическая формула?

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

Определение логической формулы: 1. Всякая логическая переменная и символы «истина» («1») и «ложь» («0») — формулы. 2. Если А и В — формулы, то , (А · В), (А v В), (А ® B), (А « В) — формулы. 3. Никаких других формул в алгебре логики нет.

В п. 1 определены элементарные формулы; в п. 2 даны правила образования из любых данных формул новых формул.

В качестве примера рассмотрим высказывание «если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог«. Это высказывание формализуется в виде (A v B) ® C; такая же формула соответствует высказыванию «если Игорь знает английский или японский язык, то он получит место переводчика».

Как показывает анализ формулы (A v B) ® C , при определённых сочетаниях значений переменных A, B и C она принимает значение «истина», а при некоторых других сочетаниях - значение «ложь» (разберите самостоятельно эти случаи). Такие формулы называются выполнимыми.

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

В качестве другого примера рассмотрим формулу А •, которой соответствует, например, высказывание «Катя самая высокая девочка в классе, и в классе есть девочки выше Кати«. Очевидно, что эта формула ложна, так как либо А, либо обязательно ложно. Такие формулы называются тождественно ложными формулами или противоречиями. Высказывания, которые формализуются противоречиями, называются логически ложными высказываниями.

Если две формулы А и В «одновременно», то есть при одинаковых наборах значений входящих в них переменных, принимают одинаковые значения, то они называются равносильными.

Равносильность двух формул алгебры логики обозначается символом «=» или символом «є». Замена формулы другой, ей равносильной, называется равносильным преобразованием данной формулы.

Логические законы и правила преобразования логических выражений

Цели:

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

Тип урока: урок-игра.

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

План урока:

1. Организационный момент.
2. Первый этап игры: Логические операции.
3. Второй этап игры: Логические законы.
4. Третий этап игры: Минимизация логических выражений.
5. Итоги урока. Домашнее задание.

Ход урока

I. Знакомство с правилами игры.

Обучающимся предлагается учебная игра по типу телевизионной игры «СВОЯ ИГРА». Участвует весь класс на личное первенство. Каждый участник за правильный ответ получает определённое количество баллов. Игра проводится в три этапа, на каждом этапе предлагается для выбора по пять вопросов. Цена вопроса изменяется по возрастающей в пределах одного этапа, а также и по этапам.

II. Первый этап: Логические операции.

Проверка знаний логических операций.

1. Дать определение конъюнкции. Представить таблицу истинности. (3 балла)
2. Дать определение дизъюнкции. Представить таблицу истинности. (3 балла)
3. Дать определение инверсии. Представить таблицу истинности. (3 балла)
4. Дать определение импликации. Представить таблицу истинности. (5 баллов)
5. Дать определение эквивалентности. Представить таблицу истинности. (5 баллов)

III. Второй этап: Логические законы.

1. Записать закон двойного отрицания. (5 баллов)
2. Записать законы противоречия и исключающего третьего. (10 баллов)
3. Записать закон тавтологии и закон коммутативности. (15 баллов)
4. Записать законы ассоциативности и поглощения. (20 баллов)
5. Записать законы дистрибутивности и де Моргана. (25 баллов)

IV. Третий этап: Минимизация логических выражений.

1) Упростите формулу

Постройте исходную и упрощенную логические схемы. (30 баллов)

Ответ на данное задание:

2) Упростите формулу

Постройте исходную и упрощенную логические схемы. (35 баллов)

Ответ на данное задание

3) Упростите формулу

Постройте исходную и упрощенную логические схемы. (40 баллов)

Ответ на данное задание

4) Упростите формулу

Постройте исходную и упрощенную логические схемы. (45 баллов)

Ответ на данное задание

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

Ответ на данное задание:

V. Итоги урока.

По количеству баллов, набранному каждым участником, определяются три первых места (обучающиеся, получающие оценку «5»), следующие пять участников получают оценку «4», обучающиеся, набравшие минимальное количество баллов, получают оценку «3», обучающиеся, не набравшие ни одного балла, получают оценку «2».

Литература:

1. Шауцукова Л.З. Информатика: Учеб. пособие для 10-11 кл. общеобразоват. учреждений / Л.З. Шауцукова. – 4-е изд. – М. : Просвещение, 2004.
2. Угринович Н.Д. Информатика и информационные технологии. Учебник для 10-11 классов / Н.Д. Угринович. – 4-е изд. – М.: БИНОМ. Лаборатория знаний, 2007.