====== Подготовка к ЕГЭ по информатике. Раздел логика ====== ----- Для того, чтобы правильно упрощать логические высказывания, нужно знать начальные определения, понятия, а так же таблицы истинности всех логических операций. ----- ====== Разделы для повторения ====== ----- * **Что такое алгебра логики?** ([[http://book.kbsu.ru/theory/chapter5/1_5_1.html|Учебник Л. З. Шауцуковой]],[[http://de.ifmo.ru/bk_netra/page.php?tutindex=19&index=11|Официальный сайт Института точной механики и оптики]]). * **Что такое логическая формула?** ([[http://book.kbsu.ru/theory/chapter5/1_5_2.html|Учебник Л. З. Шауцуковой]],[[http://de.ifmo.ru/bk_netra/page.php?dir=3&tutindex=19&index=12&layer=1 |Официальный сайт Института точной механики и оптики]]). * **Связь между алгеброй логики и двоичным кодированием?** ([[http://book.kbsu.ru/theory/chapter5/1_5_3.html|Учебник Л. З. Шауцуковой]],[[http://de.ifmo.ru/bk_netra/page.php?dir=3&tutindex=19&index=13&layer=1|Официальный сайт Института точной механики и оптики]]). * **Что такое логический элемент компьютера?** ([[http://book.kbsu.ru/theory/chapter5/1_5_5.html|Учебник Л. З. Шауцуковой]],[[http://de.ifmo.ru/bk_netra/page.php?dir=3&tutindex=19&index=14&layer=1|Официальный сайт Института точной механики и оптики]]). * **Что такое схемы И, ИЛИ, НЕ, И—НЕ, ИЛИ—НЕ?** ([[http://book.kbsu.ru/theory/chapter5/1_5_6.html|Учебник Л. З. Шауцуковой]],[[http://de.ifmo.ru/bk_netra/page.php?dir=3&tutindex=19&index=15&layer=1|Официальный сайт Института точной механики и оптики]]). * **Какие основные законы выполняются в алгебре логики?** ([[http://book.kbsu.ru/theory/chapter5/1_5_9.html|Учебник Л. З. Шауцуковой]],[[http://de.ifmo.ru/bk_netra/page.php?dir=3&tutindex=19&index=17&layer=1|Официальный сайт Института точной механики и оптики]]). * **Как составить таблицу истинности?** ([[http://book.kbsu.ru/theory/chapter5/1_5_10.html|Учебник Л. З. Шауцуковой]]). * **Как упростить логическую формулу?** ([[http://book.kbsu.ru/theory/chapter5/1_5_11.html|Учебник Л. З. Шауцуковой]],[[http://de.ifmo.ru/bk_netra/page.php?dir=3&tutindex=19&index=18&layer=1|Официальный сайт Института точной механики и оптики]]). * **Упражнения для самопроверки**([[http://book.kbsu.ru/theory/chapter5/1_5_14.html |Учебник Л. З. Шауцуковой]]). ===== Разбор заданий по упрощению логических выражений ===== === Задания из демонстрационного варианта ЕГЭ по информатике за 2004 год === ----- **А11** Для какого имени истинно высказывание: \\ **//¬ (Первая буква имени гласная -> Четвертая буква имени согласная)?// ** - Елена - Вадим - Антон - Федор **Решение:** \\ Исходя из того, что нам нужно узнать, для какого имени высказывание ИСТИННО, делаем вывод, что выражение, стоящее в скобках должно быть ложным. А при каких значениях в результате импликации выходит «ложь»? Только если первое высказывание истинно, а второе ложно. Остается всего лишь подобрать имя, в котором первая и четвертая буквы гласные. \\ **Ответ: 3)** \\ ----- **А12** Какое логическое выражение [[http://book.kbsu.ru/theory/chapter5/1_5_2.html|равносильно]] выражению **¬ (А or ¬B)** ? \\ - A or B - A and B - ¬A or ¬B - ¬A and B **Решение:** \\ Для этого необходимо воспользоваться [[http://book.kbsu.ru/theory/chapter5/1_5_9.html|законами алгебры]] логики и упростить исходное выражение. В данном случае нам подходит закон де Моргана, с помощью которого упрощаем выражение и получаем **ответ 4)** ----- **А13** Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент [[http://book.kbsu.ru/theory/chapter5/1_5_10.html|таблицы истинности ]] выражения F: \\ ^X ^Y ^Z ^F ^ |0 |0 |0 |1 | |0 |0 |1 |0 | |0 |1 |0 |1 | Какое выражение соответствует **F**? \\ - ¬X and ¬Y and Z - ¬X or ¬Y or Z - X or Y or ¬Z - X or Y or Z **Решение:** \\ Из исходной таблицы истинности мы можем получить совершенную конъюнктивную нормальную форму **(СКНФ)**, для этого: \\ * находим строки, в которых значение функции равно нулю (в данном случае она одна), \\ *выписываем элементарную дизъюнкцию, *объединяем элементарные дизъюнкции в элементарную конъюнкцию и получаем ответ 3). **Ответ: 3)** \\ ----- === Задания из демонстрационного варианта ЕГЭ по информатике за 2005 год === ----- **А9** \\ Для какого числа X истинно высказывание **X>1 and ( (X<5) → (X<3) )** - 1 - 2 - 3 - 4 **Решение:** \\ Подставляя каждое из значений, мы сможем определить, когда же может данное выражение быть истинным. \\ - при Х=1 1>1 and ( (1<5)->(1<3) ) «ложь» /\ («истина» -> («истина»)) – «ложь» \\ - при Х=2 \\ 2>1 and ( (2<5)->(2<3) ) \\ «истина» /\ («истина» -> («истина»)) – «истина» \\ **Ответ: 2)** ----- **В2** Сколько различных решений имеет уравнение **(K and L and M) or (¬L and ¬M and N) = 1**, где K, L, M, N - логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов. **Решение:** \\ Построим таблицу истинности для данного выражения, и количество итоговых «1» будет указывать на количество решений исходного уравнения. **Ответ: 4** ====== Раздел для самостоятельного решения ====== ----- [[http://www.egeinfo.ru/getready/egedemos/|www.egeinfo.ru]] - демоверсии вариантов ЕГЭ по информатике за 2006-2007 \\ [[http://ege.ru/demo-ege/demo-inf-2004.shtml|www.ege.ru/demo-ege]] - Интерактивный ознакомительный вариант ЕГЭ по информатике за 2004 \\