Работа с учащимися по подготовке к ЕГЭ
Применение таблиц истинности при решении логических задач
Скачать:
| Вложение | Размер |
|---|---|
 primenenie_tablits_istinnosti_dlya_resheniya_zadach_ege_no.pptx | 1.71 МБ |
 Теория к заданию №5 | 25.59 КБ |
Предварительный просмотр:
Подписи к слайдам:
Алгебра логики — это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними. Алгебра логики рассматривает любое высказывание только с одной точки зрения — является ли оно истинным или ложным. Употребляемые в обычной речи слова и словосочетания "не", "и", "или", "если... , то", "тогда и только тогда" и другие позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками.
Истинность или ложность получаемых таким образом составных высказываний зависит от истинности или ложности элементарных высказываний, имеют значения — "истина" или "ложь", обозначаемые, соответственно, "1" и "0". Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение: Операция, выражаемая словом "не", называется инверсией (отрицанием) и обозначается чертой над высказыванием (или знаком ┐ ).
Операция, выражаемая связкой "и", называется конъюнкцией (лат. conjunctio — соединение) или логическим умножением и обозначается *( может также обозначаться знаками ∩ или &). Высказывание А * В истинно тогда и только тогда, когда оба высказывания А и В истинны. Например, высказывание "10 делится на 2 и 5 больше 3" истинно, а высказывания "10 делится на 2 и 5 не больше 3", "10 не делится на 2 и 5 больше 3", "10 не делится на 2 и 5 не больше 3" — ложны. Операция , выражаемая связкой "или" называется дизъюнкцией (лат. disjunctio — разделение) или логическим сложением и обозначается знаком v (или плюсом). Высказывание А v В ложно тогда и только тогда, когда оба высказывания А и В ложны. Например, высказывание "10 не делится на 2 или 5 не больше 3" ложно, а высказывания "10 делится на 2 или 5 больше 3", "10 делится на 2 или 5 не больше 3", "10 не делится на 2 или 5 больше 3" — истинны.
Операция, выражаемая связками "если ..., то", "из ... следует", "... влечет ...", называется импликацией (лат. implico — тесно связаны) и обозначается знаком → . Высказывание ложно тогда и только тогда, когда А истинно, а В ложно. x y x→ y 0 0 1 0 1 1 1 0 0 1 1 1 Импликацию можно выразить через дизъюнкцию и отрицание:
Операция, выражаемая связками "тогда и только тогда", "необходимо и достаточно", "... равносильно ...", называется эквиваленцией или двойной импликацией и обозначается знаком ↔ или ~. Высказывание истинно тогда и только тогда, когда значения А и В совпадают. Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию: x y x↔ y 0 0 1 0 1 0 1 0 0 1 1 1
Таким образом, операций отрицания, дизъюнкции и конъюнкции обладают функциональной достаточностью, чтобы описывать и обрабатывать логические высказывания. Порядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок договорились считать, что сначала выполняется операция отрицания ("не"), затем конъюнкция ("и"), после конъюнкции — дизъюнкция ("или") и в последнюю очередь — импликация.
В алгебре логики выполняются следующие основные законы, позволяющие производить тождественные преобразования логических выражений: Основные законы алгебры логики
Пример построения таблицы истинности:
Применение таблиц истинности при решении задач. Босова Л.Л. Рабочая тетрадь 7 класс
Применение таблиц истинности при решении задач. Босова Л.Л. Рабочая тетрадь 8 класс
Применение таблиц истинности при решении задач. Босова Л.Л. Рабочая тетрадь 8 класс
Применение логических формул при решении задач ГИА по информатике
Применение логических формул для решения задач Информатика 10-11 класс. Шауцукова 5.29 . При составлении расписания на пятницу были высказаны пожелания, чтобы информатика была первым или вторым уроком, физика — первым или третьим, история — вторым или третьим. Можно ли удовлетворить одновременно все высказанные пожелания?
Применение таблиц истинности для решения задач ЕГЭ № 2 Сайт К. Полякова
Применение таблиц истинности для решения задач ЕГЭ №2 Сайт К. Полякова
СКНФ - совершенно конъюнктивная нормальная форма СДНФ - совершенная дизъюнктивная нормальная форма Существует два вида нормальной формы: конъюнктивная нормальная форма, т. е. конъюнкция нескольких дизъюнкций (КНФ) и дизъюнктивная нормальная форма, т. е. дизъюнкция нескольких конъюнкций (ДНФ), пример:
Совершенно конъюнктивная НФ - конъюнкция дизъюнкций, причём в каждой дизъюнкции (в каждой скобке) присутствуют все переменные, входящие в формулу, либо их отрицание, нет одинаковых дизъюнкций, в каждой дизъюнкции нет одинаковых слагаемых, пример : Совершенно дизьюнктивная НФ - дизьюнкция коньюнкций , причём в каждой коньюнкции (в каждой скобке) присутствуют все переменные, входящие в формулу, либо их отрицание, нет одинаковых коньюнкций , в каждой коньюнкции нет одинаковых слагаемых, пример :
Правила построения СДНФ и СКНФ по таблице истинности Пример: Восстановите логическую функцию по ее таблице истинности:
РЕШЕНИЕ: СДНФ составляется на основе таблицы истинности по следующему правилу: для каждого набора переменных, при котором функция равна 1, записывается произведение, в котором с отрицанием берутся переменные, имеющие значение «0». x y z F 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1
СКНФ составляется на основе таблицы истинности по правилу: для каждого набора переменных, при котором функция равна 0, записывается сумма, в которой с отрицанием берутся переменные, имеющие значение 1.
Применение таблиц истинности для решения задач ЕГЭ №2 Задание 1 (М.В. Кузнецова) Логическая функция F задаётся выражением (a b ) (¬a c ) . Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных a , b , c . Таблица 1 В ответе напишите буквы a, b, c в том порядке, в котором идут соответствующие им столбцы.
2 способ (применение СКНФ и СДНФ) (a b ) (¬a c ) . Приведем функцию к совершенному виду, используя формулы алгебры логики . ( ) (¬a c ) = (¬a c ) =a (¬a c ) =a + c= a (c+ )+ c(b+ )= a c+ a + cb + c Выделим те строки, у которых функция равна 1.В формуле видно, что b принимает 3 значения 0 и один раз 1 , это соответствует 3му столбцу. C принимает 3 раза значения 1 и один раз 0. Это соответствует 2 столбцу. Ответ: acb
Задание 2. Логическая функция F задаётся выражением (¬ z) ˄ x ˅ x ˄ y . Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z. В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая 1-му столбцу; затем – буква, соответствующая 2-му столбцу; затем – буква, соответствующая 3-му столбцу). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Способ 1. Обозначим : Перем 1. => А; Перем 2. => B; Перем 3. => C Используя алгоритм образования СДНФ построим её по заданной таблице истинности. Выделяем те строки, в которых функция принимает значение 1: (¬ A)·(¬B)·C + (¬A)·B·C + A·B·C = C·((¬A)·(¬B) + (¬A)·B + A·B) = C·((¬A)·((¬B) + B) + A·B) = C·((¬A) + A·B) = C·((¬A) + B) Из 2 и 3 видно, что С => x; A => z; B => y Ответ: zyx .
Способ 2. Построим полную таблицу истинности функции (¬z ) ˄ x ˅ x ˄ y. Ответ: zyx x y z ¬z (¬z) ˄ x x ˄ y (¬z) ˄ x ˅ x ˄ y. 0 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 1 1 1 1 1 1 0 0 1 1
Задание 3 . Логическая функция F задается выражением (x /\ y /\¬z) \/ (x /\ y /\ z) \/ (x /\¬y /\¬z). На рисунке приведен фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z. Решение: Данная функция является функцией СДНФ. Рассмотрим каждую скобку. ( x /\ y /\¬z) ( x /\ y /\ z ) ( x /\¬y /\¬z) Сравниваем их со строками таблицы: Видно, что переменная х в формуле везде без отрицания, поэтому ей соответствует второй столбец таблицы. Переменная у имеет одно отрицание, поэтому ей соответствует первый столбец таблицы. Переменная z имеет два отрицания, поэтому соответствует третий столбец таблицы. Ответ: yxz .
Задание 4 (М.В. Кузнецова) Логическая функция F задаётся выражением (x y) (¬x y ¬z) . Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных Решение : Функция задана в виде КНФ. Приведем ее к совершенному виду, используя формулы алгебры логики. В первую скобку (x y) добавим недостающую переменную z , но, чтобы функция не изменилась, добавим z *¬z. Тогда получим F = (x y) (¬x y ¬z)= (x y z *¬z ) (¬x y ¬z)= (x y ¬ z ) (x y z ) (¬x y ¬z). Анализируя переменные и столбцы таблицы, имеющие нулевые значения, составим таблицу : Ответ: yxz . ? ? ? F 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 y x z F 0 0 0 0 0 0 1 0 0 1 1 0
145 .(К. Поляков) Логическая функция F задаётся выражением x ( y z y ¬ w ¬ z ¬ w ) . На рисунке приведён фрагмент таблицы истинности функции F , содержащий все наборы аргументов , при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x , y , z , w . ? ? ? ? F 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1
144. (Поляков К.Ю.)Логическая функция F задаётся выражением x ( z ¬ w y ¬ w y ¬ z ) . На рисунке приведён фрагмент таблицы истинности функции F , содержащий все наборы аргументов , при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x , y , z , w . ? ? ? ? F 0 1 1 0 1 1 0 1 0 1 1 0 1 1 1 1 1 1 0 1
143)Поляков К.Ю. Логическая функция F задаётся выражением x ( y z z w y ¬ w ) . На рисунке приведён фрагмент таблицы истинности функции F , содержащий все наборы аргументов , при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x , y , z , w . ? ? ? ? F 1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1
Предварительный просмотр:
Умение кодировать и декодировать информацию
Задание № 5
Умение кодировать и декодировать информацию
Код контролируемого элемента: 1.1.2 - Процесс передачи информации, источник и приемник информации. Сигнал, кодирование и декодирование. Искажение информации.
Код требуемых умений или способов действия: 1.2.2 - Интерпретировать результаты, получаемые в ходе моделирования реальных процессов
Уровень сложности задания – базовый.
Примерное время выполнения задания – 2 минуты.
Что нужно знать (очень краткая теория):
- Язык
Под языком прежде всего имеют в виду естественный человеческий язык, возникновение и существование которого неразрывно связано с возникновением и существованием человека — homo sapiens [1].
Язык – это знаковая система для представления и передачи информации [2, с. 15].
Языки, используемые для общения людей, называются естественными языками. Их насчитывается несколько тысяч. Естественные языки характеризуются: широкой сферой применения, наличием большого количества явных и неявных правил, гибкостью, открытостью, динамичностью. [3, с. 33];
Формальные языки применяются специалистами в профессиональной деятельности.
Формальный язык – это такой язык, в котором одинаковые сочетания знаков всегда имеют одинаковый смысл. Особенностью формальных языков является то, что все правила в них задаются в явной форме; это обеспечивает однозначность записи и восприятия сообщений на этих языках.
- Кодирование
- это перевод информации с одного языка на другой (запись в другой системе символов, в другом алфавите) [4, с. 1];
- это представление информации в той или иной форме [3, с. 33];
- это процесс представления информации, удобный для ее хранения и/или передачи [2, с. 15].
Обычно кодированием называют перевод информации с «человеческого» языка на формальный, например, в двоичный код, а декодированием – обратный переход.
Один символ исходного сообщения может заменяться одним символом нового кода или несколькими символами, а может быть и наоборот – несколько символов исходного сообщения заменяются одним символом в новом коде (китайские иероглифы обозначают целые слова и понятия) [4, с. 1].
- Способы кодирования
Кодирование может быть равномерное и неравномерное.
При равномерном кодировании все символы кодируются кодами равной длины (пример – равномерный телеграфный код Бодо) [2, с. 19].
При неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование (пример – азбука Морзе). Принцип кодирования азбуки Морзе исходит из того, что буквы, которые чаше употребляются, кодируются более короткими сочетаниями точек и
тире. Это делает передачи компактнее [5, с. 3].
- Условие Фано
- никакое кодовое слово не является началом другого кодового слова, тогда закодированное сообщение можно однозначно декодировать с начала.
Обратное условие Фано
- никакое кодовое слово не является окончанием другого кодового слова, тогда закодированное сообщение можно однозначно декодировать с конца.
Условие Фано – это достаточное, но не необходимое условие однозначного декодирования [4, с. 1].
- Префиксный код
Неравномерные коды, для которых выполняется условие Фано, называются префиксными.
Префиксный код - такой неравномерный код, в котором ни одно кодовое слово не является началом другого, более длинного слова. В таком случае кодовые слова можно записывать друг за другом без разделительного символа между ними [6].
- Алгоритм Хаффмана.
Сжатием информации в памяти компьютера называют такое ее преобразование, которое ведет к сокращению объема занимаемой памяти при сохранении закодированного содержания.
С помощью алгоритма Хаффмана строится двоичное дерево, которое позволяет однозначно декодировать двоичный код, состоящий из символьных кодов различной длины. Двоичным называется дерево, из каждой вершины которого выходят две ветви [2, с. 207]. Корень дерева – пустая строка. В узлах дерева двоичные коды. Левые ветви дерева соответствует команде «приписать 0 справа», правые ветви – команде «приписать 1 справа» [5, с. 4].
Источники
- http://tapemark.narod.ru/les/604c.html
- Информатика. Базовый уровень учебник для 10 класса / И. Г. Семакин, Е. К. Хеннер, Т. Ю. Шеина. – 4-е изд. – М. : БИНОМ. Лаборатория знаний, 2015. – 264 с. : ил. ISBN 978-5-9963-1930-5
- Информатика : учебник для 7 класса / Л. Л. Босова, А. Ю. Босова. - М. : БИНОМ. Лаборатория знаний, 2013. – 224 с. : ил. ISBN 978-5-9963-1165-1
- http://kpolyakov.spb.ru/download/ege5.doc
- ЦОР ЦФО Повышение квалификации учителей информатики НИУ ВШЭ Р.З. Ахметсафина, О.В. Максименкова.
- http://www.intuit.ru/studies/courses/3481/723/lecture/14228?page=4