Кодификатор элементов содержания по информатике для составления КИМ для ЕГЭ - 2009. - презентация

1 Кодификатор элементов содержания по информатике для составления КИМ для ЕГЭ

2 Логические операции 1. Логическое отрицание (инверсия) 2. Логическое умножение (конъюнкция) 3. Логическое сложение (дизъюнкция)

3 ABA&B AB A B A¬А¬А Конъюнкция (умножение) Дизъюнкция (сложение) Инверсия (отрицание)

4 Схематическое изображение логических операций

5 Логические функции Логические следования (импликация) А В Логическое равенство (эквивалентность) А ~ В

6 Импликация ABAB назад

7 Эквивалентность ABA~B

8 Для вычисления логического выражения 1 или 0 и 1 нарисовать схему, отражающую последовательность выполнения логических операций. По схеме вычислить значение логического выражения. Решение: Здесь наглядно отражено то, что первой выполняется операция И, затем ИЛИ. Теперь в порядке слева – направо припишем к выходящим стрелкам результаты операций: В результате получилась 1, т.е. истина

9 Задания для самостоятельной работы: Задание 1. Дано выражение: не (1 и (0 или 1) и 1). Вычислить значение выражения с помощью логической схемы. РешениеРешение Задание 2. Выполните вычисления по логическим схемам. Запишите соответствующие логические выражения:

10 Задача 1. Логическая схема с результатами вычислений выглядит так: Задача 2. 1) A ^ b (b a) Ответ: истина 2) ¬a (a ^ b) Ответ: ложь

11 Задания для самостоятельной работы: Задание 3. Дана логическая схема. Построить логическое выражение, соответствующее этой схеме. Вычислить значение выражения для а) х 1 =0, х 2 = 1; б) х 1 =1, х 2 = 0; в) х 1 =1, х 2 = 1; г) х 1 =0, х 2 = 0; Задание 4. Дана логическая схема. Построить логическое выражение, соответствующее этой схеме. Вычислить значение выражения для А) х 1 = х 2 =1, х 3 = х 4 =0 Б) х 4 =1, и любых значениях х1, х2, х3 В) х 1 =0, х 4 =0 и любых значениях х 2, х 3 Задание 5. Дана логическая схема. Построить соответствующие ей логическое выражение. Вычислить значение выражения для а)х1=х2=х3=1; Б) х1=х2=х3=0; В)х1=0, х3=1 и любых значениях х2

12 Задание 3. ¬х 2 ^(х 1 (¬х 1 ^х 2 )) 1) ложь, 2) истина, 3) ложь, 4) ложь Задание 4. Х 4 (¬х 2 ¬х 3 ^(х 1 ^х 2 ^х 3 )) А) ложь Б) истина В) ложь Задание 5. ¬ х 1 ^х 3 ¬(х 1 ^х 2 х 2 ^х 3 ) А) ложь Б) истина В) истина

13 Логические законы и правила преобразования логических выражений Закон тождества: Всякое высказывание тождественно самому себе А=А Закон противоречия: Высказывание не может быть одновременно истинным и ложным. Если высказывание А истинно, то его отрицание не А должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно А^¯А=0 Закон исключенного третьего: Высказывание может быть либо истинным, либо ложным, третьего не дано. Это означает, что результат логического сложения высказывания и его отрицания всегда принимает значение истина. А ¯А=1

14 Закон двойного отрицания. Если дважды отрицать некоторое высказывание, то в результате мы получим исходное высказывание. ¬¬А=А Законы де Моргана. Закон коммутативности Закон коммутативности В обычной алгебре слагаемые и множители можно менять местами. В алгебре высказываний можно менять местами логические переменные при операциях логического умножения и логического сложения. Закон ассоциативности. Закон ассоциативности. Если в логическом выражении используются только операция логического умножения или только операция логического сложения, то можно пренебрегать скобками или произвольно расставлять их.

15 Закон дистрибутивностиЗакон дистрибутивности. В отличие от обычной алгебры, где за скобки можно выносить только общие множители, в алгебре высказываний можно выносить за скобки как общие множители, так и общие слагаемые. Дистрибутивность умножения относительно сложения Дистрибутивность сложения относительно умножения ab+ac = a(b+c) – в алгебре (A^B) (A^C) =A^(B C) (A B) ^(A C) =A (B^C)

16 Логические законы и правила преобразования логических выражений ЗаконДля ИЛИДля И Переместительный x y=y x x*y=y*x Сочетательный x (y z)=(x y) z (x*y)*z=x*(y*z) Распределительный x*(y z)=x*y x*zx y*z=(x y)*(x z) Правила де Моргана x y=x*yx*y= x y Идемпотенции x x=x x*x=x Поглощения x x*y=xx*(x y)=x Склеивания (x*y) (x*y)=y(x y)*(x y)=y Операции переменной с ее инверсией x x=1 x*x=0 Операции с константами x 0=x; x 1=1 x*1=x;x*0=0 Двойное отрицание x=x назад

17 Примеры решения логических задач 1.Для какого числа Х истинно высказывание : (( Х > 3 ) ( Х > 4 ))? 1 ) 1 ; 2 ) 2 ; 3 ) 3 ; 4 ) 4 Решение: Используем таблицы истинности импликации и отрицания импликацииотрицания 1. ((1>3) (1>4)) = (л л) = и = л 2. ((2>3) (2>4)) = (л л) = и = л 3. ((3>3) (3>4)) = (л л) = и = л 4. ((4>3) (4>4)) = (и л) = л = и Ответ: 4

18 2. Укажите, какое логическое выражение равносильно выражению ( A B) C. 1 А В С 2 А В С 3 А В С 4 А В С Решение По закону де МорганаПо закону де Моргана ( A B) C= А В С =А В С Ответ: 3

19 Задачи для самостоятельно решения Постройте таблицы истинности для высказываний: ¬(А^В ¬С) С ПОСТРОЙТЕ ЭЛЕКТРИЧЕСКУЮ СХЕМУ ДЛЯ ДАННОГО ВЫРАЖЕНИЯ ¬(А^С В) ¬В ПОСТРОЙТЕ ЭЛЕКТРИЧЕСКУЮ СХЕМУ ДЛЯ ДАННОГО ВЫРАЖЕНИЯ ¬А^С ¬( В А) ПОСТРОЙТЕ ЭЛЕКТРИЧЕСКУЮ СХЕМУ ДЛЯ ДАННОГО ВЫРАЖЕНИЯ

20

21 Семинар НИТ Задачи для самостоятельно решения 3. Восемь школьников оставшихся в классе на перемене были вызваны к директору. Один из них разбил окно в кабинете. На вопрос директора кто это сделал были получены следующие ответы Егор Разбил Андрей Света Вика разбила. Оля Разбила Света. Миша Это кто-то из улицы Надя Да Оля права… Коля Это либо Вика либо Света Андрей Ни Вика ни Света этого не делали. Вика Андрей не бил Кто разбил окно если известно что из этих восьми высказываний истинно ровно три Ответ запишите в виде первой буквы имени.

22 3. Восемь школьников оставшихся в классе на перемене были вызваны к директору. Один из них разбил окно в кабинете. На вопрос директора кто это сделал были получены следующие ответы Егор Разбил Андрей Света Вика разбила. Оля Разбила Света. Миша Это кто-то из улицы Надя Да Оля права… Коля Это либо Вика либо Света Андрей Ни Вика ни Света этого не делали. Вика Андрей не бил Кто разбил окно если известно что из этих восьми высказываний истинно ровно три Ответ запишите в виде первой буквы имени. Решение Метод логического рассуждения. ЕСОМНКАВ Из таблицы видно, что Света права, разбила Вика, т.к. из этих восьми высказываний истинно ровно три. Ответ: В

23 Семинар НИТ 4. Символом F обозначено одно из указанных ниже логических выражений от трёх аргументов X Y Z. Дан фрагмент таблицы истинности выражения F Какое выражение соответствует F 1. X Y Z 2. X Y Z 3. X Y Z 4. X Y Z XYZF

24 4. Символом F обозначено одно из указанных ниже логических выражений от трёх аргументов X Y Z. Дан фрагмент таблицы истинности выражения F XYZF Какое выражение соответствует F 1. X Y Z 2. X Y Z 3. X Y Z 4. X Y Z Решение: Используем таблицу истинности функцийтаблицу истинности функций X Y Z F1F1 F2F2 F3F3 F4F Так как F 2 =F, отсюда следует, что выражение X Y Z соответствует F. Ответ: 2

25 5. А, В, С – целые числа, для которых истинно высказывание: (А = В) ((А В) (В С) ((В А) (С В)). Чему равно В если А= 45 С= 43 Решение:Чтобы высказывание было верным, необходимо, чтобы каждый множитель был истинным. Из (А = В) следует, что А В. Из (А В) (В С) следует, что В находится между А и С т.е. В = 44. (В А) (С В) истинно, т.к. 0 0 истинно. Ответ: 44.

26 Пример: Для какого из указанных значений числа Х истинно высказывание ((Х

27 Тестовые задания

28 Задачи на повторение: Для кодирования букв А, Б, В, Г, решили использовать двухразрядные последовательные двоичные числа (от 00 до 11 соответственно). Если таким способом закодировать последовательность символов ГБАВ и записать результат шестнадцатеричным кодом, то получиться: 1) D2 2)132 3) ) DBAC А Цепочка из трех бусин, помеченных латинскими буквами, формируется по следующему правилу. В конце цепочки стоит одна из бусин А, В, С. На первом месте – одна из бусин B, D, C, которой нет на третьем месте. В середине – одна из бусин A,C,E,B, не стоящая на первом месте. Какая из перечисленных цепочек создана по этому правилу? Какая из перечисленных цепочек создана по этому правилу? 1) СВВ 2) ЕАС 3) BCD 4) BCB

29 А Для групповых операций используются маски имен файлов. Маска представляет собой последовательность букв, цифр и прочих допустимых в именах файлов символов, в которых также могут встречаться следующие символы: Символ «?» (вопросительный знак) означает равно один произвольный символ. Символ «*» (звездочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность. Определите, какое из указанных имен файлов удовлетворяет маске: b*a*c?.c?* 1) bacc.cpp 2) bac.cpp 3) bacc.c 4) blarc.cpp

30 Задачи для самостоятельного решения В Строчки (цепочки символов латинских букв) создаются по следующему правилу. Первая строка состоит из одного символа – латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется «i»–я буква алфавита), к ней справа дважды подряд приписывается предыдущая строка. Вот первые четыре строки, созданные по этому правилу: (1) A (2) BAA (3) CBAABAA (4) DCBAABAACBAABAA Латинский алфавит (для справки) A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Запишите семь символов подряд, стоящие в восьмой строке со 128-го по 134 – е место (считая слева направо).