8. Решение задач

Дополнительные материалы методиста Фрунзенского района Санкт-Петербурга Смирновой Т.М.. Перейдите по ссылке....

https://docs.google.com/present/edit?id=0AauJNWEHHyPVZGczNnFubmRfMGhrdmg3NmY3&hl=ru
или на сайт разработчика http://edu-frn.spb.ru/nmc_mdep.phtml?id=45

7. Множества и основы логики. Учимся решать задачи типа В12 демоверсии ЕГЭ 2012 по информатике

Два множества A и B могут вступать друг с другом в различные отношения, которые соответствуют ранее рассмотренным логическим операциям.
Например,

Логика_____________________Теория множеств
A&B - Конъюнкция___________Пересечение
AVB - Дизъюнкция___________Объединение
˥А-___Инверсия_____________Дополнение

Более подробно можно ознакомиться с материалом наhttp://www.grandars.ru/student/vysshaya-matematika/mnozhestvo.html.

Перейдем непосредственно к решению задач группы В12. Несмотря на то, что согласно СПЕЦИФИКАЦИИ контрольных измерительных материалов единого государственного экзамена 2012 года по информатике и ИКТ данное задание относится к умению осуществлять поиск информации в Интернет, мы поймем, связь решения этой задачи с теорией множеств и алгеброй логики.

Задание 1
В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ
«&».
В таблице приведены запросы и количество найденных по ним страниц
некоторого сегмента сети Интернет.
Запрос Найдено страниц
(в тысячах)
Шахматы | Теннис 7770
Теннис 5500
Шахматы & Теннис 1000
Какое количество страниц (в тысячах) будет найдено по запросу
Шахматы?
Считается, что все запросы выполнялись практически одновременно, так что
набор страниц, содержащих все искомые слова, не изменялся за время
выполнения запросов.
Решение:

[Шахматы]=[Шахматы V Теннис]+[Шахматы & Теннис]-[Теннис]= 7770+1000-5500=3270.

Ответ: 3270 тыс.запросов.

Задания для самостоятельного решения
1.
В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке убывания количества страниц, которые найдет поисковый сервер по данному запросу.
1. барокко V (классицизм & ампир)
2. барокко V классицизм
3. барокко V классицизм V ампир
4. (классицизм & ампир)

2.
В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ
«&».
В таблице приведены запросы и количество найденных по ним страниц
некоторого сегмента сети Интернет.
Запрос Найдено страниц
(в тысячах)
Чехов - 4100 тыс. стр.
Лермонтов - 4000 тыс. стр.
Лермонтов V Чехов - 6600 тыс. стр.
Какое количество страниц (в тысячах) будет найдено по запросу "Лермонтов & Чехов"?
3.
Множества А, В и С заданы кругами Эйлера. Для каждого из образовавшихся множеств определите выражение, которому оно соответствует.

6. Учимся решать задание В15 демоверсии ЕГЭ по информатике 2012.

Решение задач данного типа начнем с более простого примера, который присутствовал в ЕГЭ прошлых лет. Отличительной особенностью заданий такого типа являлось меньшее по сравнению с демоверсией ЕГЭ по информатике 2012 года количество переменных и меньшее количество уравнений следствий.
Поэтому представляется возможным показать два способа решения. Первый способ - построение таблиц истинности, второй - использование логический рассуждений.
Приступим,...

Сколько различных решений имеет уравнение ((KVL)=>(L&M&N))=0, где K, L, M, N - логические переменные?
В ответе не нужно перечислять все различные наборы значений K, L, M, N, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Задания для самостоятельной работы

1. Укажите значение логических переменных K, L, M, N, при которых логическое выражение: (KVM)=>(MV¬LVN) ложно.
Ответ запишите виде стоки из четырех символов: значений переменных K, L, M, N (в указанном порядке). Так, например, строка 0101 сответствует тому, что K=0, L=1, M=0, N=1

2. Сколько различных решений имеет уравнение ((KVL)&(MVN))=1, где K, L, M, N - логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M, N, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов.

3. Дано логическое выражение (MV¬LV¬N)=>(KV¬LV¬N).
Укажите значение переменных K, L, M, N, при которых логическое выражение ложно. Ответ запишите виде стоки из четырех символов: значений переменных K, L, M, N (в указанном порядке). Так, например, строка 0101 сответствует тому, что K=0, L=1, M=0, N=1.

5. Учимся решать задачи типа А10 демоверсии ЕГЭ 2012 по информатике

В этом пункте перейдем непосредственно к решению задач типа А10, представленных в демоверсии ЕГЭ 2012 по информатике.

Задание 1
Какое из приведённых имён удовлетворяет логическому условию:
(первая буква согласная → вторая буква согласная) & (предпоследняя буква
гласная → последняя буква гласная)?
1) Лилия
2) Валентин
3) Кристина
4) Владимир
Решение:

Введем следующие обозначения:
А - "первая буква согласная",
В - "вторая буква согласная",
С - "предпоследняя буква гласная",
D - "последняя буква гласная".

Формализуем условие задачи: (А=>B)&(C=>D).
Составим таблицу истинности для этого условия задачи. Если для имени высказывание - истина, будем ставить в соответствующую графу "1", если ложно - "0".
_________А______В______С_______D________A=>B______C=>D________(А=>B)&(C=>D)
Лилия____1______0_______1_______1_________0_________1___________0____-н/подходит
Валентин__1______0_______1_______0________0_________0___________0____-н/подходит
Кристина__1______1_______0_______1________1_________1___________1____-подходит
Владимир__1______1_______1_______0________1_________0___________0____-н/подходит

Ответ: Кристина

P.s. При решении удобнее заполнять сначала столбцы А-D, а затем строки 1-4.

Внимание!!! Не забывайте о приоритете выполнения действий!

Задания для самостоятельной работы
1.
Для какого из названий животного ложно высказывание:
Заканчивается на согласную букву & В слове 7 букв => ˥(Третья буква согласная)?
1) Вербдюд
2) Страус
3) Кенгуру
4) Леопард
2.
Какое из приведенных имен истинно высказыванию:
Третья буква гласная => ˥ (Первая буква согласная) V В слове 4 гласных буквы?
1) Римма
2) Анатолий
3) Светлана
4) Дмитрий
3.
Для какого символьного набора истинно высказывание:
Вторая буква согласная & (В слове три гласных буквы V Первая буква согласная)?
1) аббедг
2) маиодд
3) жабвеа
4) икррое

4. Учимся решать задачи типа А3 демоверсии ЕГЭ 2012 по информатике

В этом пункте перейдем непосредственно к решению задач типа А3, представленных в демоверсии ЕГЭ 2012 по информатике.

Задание 1
Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: Х, Y, Z.
Дан франмент таблицы истинности выражения F:
X___Y____Z____F
0___0____1____1
1___1____1____1
1___1____0____0
Какое выражение соответсвует F?
1) X&Y&Z
2) XVYV˥Z
3) ˥X&˥Y&Z
4) ˥XV˥YVZ

Решение:
Проверим правильность составления данной таблицы истинности (каждой строки) для каждого выражения. Для этого составим новую таблицу, в шапку которой поместим выражения 1-4:
X____Y_____Z_______X&Y&Z_______XVYV˥Z______˥X&˥Y&Z______˥XV˥YVZ_____F
0____0_____1_________ ? ____________ ? __________ ? ____________ ? _______ 1
1____1_____1_________ ? ____________ ? __________ ? ____________ ? _______ 1
1____1_____0_________ ? ____________ ? __________ ? ____________ ? _______ 0

Заполним пустые ячейки таблицы (по столбцам). Нахождение столбца соответствующего значению истинности выражения F позволяет дать ответ в данном задании.
Итак, приступим..
1.
X____Y_____Z_______X&Y&Z_______XVYV˥Z______˥X&˥Y&Z______˥XV˥YVZ_____F
0____0_____1_________ 0 ____________ ? __________ ? ____________ ? _______ 1
1____1_____1_________ 1 ____________ ? __________ ? ____________ ? _______ 1
1____1_____0_________ 0 ____________ ? __________ ? ____________ ? _______ 0
Выражение "1" не соответствует F.
Производим проверку дальше.
2.
X____Y_____Z_______X&Y&Z_______XVYV˥Z______˥X&˥Y&Z______˥XV˥YVZ_____F
0____0_____1_________ 0 ____________ 0 __________ ? ____________ ? _______ 1
1____1_____1_________ 1 ____________ 1 __________ ? ____________ ? _______ 1
1____1_____0_________ 0 ____________ 1 __________ ? ____________ ? _______ 0
Выражение "2" не соответствует F.
Производим проверку дальше.
3.

X____Y_____Z_______X&Y&Z_______XVYV˥Z______˥X&˥Y&Z______˥XV˥YVZ_____F
0____0_____1_________ 0 ____________ 0 __________ 1 ____________ ? _______ 1
1____1_____1_________ 1 ____________ 1 __________ 0 ____________ ? _______ 1
1____1_____0_________ 0 ____________ 1 __________ 0 ____________ ? _______ 0
Выражение "3" не соответствует F.
Производим проверку дальше.
4.

X____Y_____Z_______X&Y&Z_______XVYV˥Z______˥X&˥Y&Z______˥XV˥YVZ_____F
0____0_____1_________ 0 ____________ 0 __________ 1 ____________ 1 _______ 1
1____1_____1_________ 1 ____________ 1 __________ 0 ____________ 1 _______ 1
1____1_____0_________ 0 ____________ 1 __________ 0 ____________ 0 _______ 0
Выражение "4" соответствует F.
УРА!!!
Ответ: 4.

Задания для самостоятельной работы
1.Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: Х, Y, Z.
Дан франмент таблицы истинности выражения F:
X___Y____Z____F
0___1____0____1
1___0____1____0
1___1____0____0
Какое выражение соответсвует F?
1) ˥X&Y&˥Z
2) XV˥YVZ
3) X&˥Y&Z
4) ˥XVYV˥Z
2.Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: Х, Y, Z.
Дан франмент таблицы истинности выражения F:
X___Y____Z____F
0___0____0____0
0___1____0____1
1___1____1____1
Какое выражение соответсвует F?
1) XVYVZ
2) X&Y&˥Z
3) ˥X&Y&˥Z
4) XVYVZ
3.Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: Х, Y, Z.
Дан франмент таблицы истинности выражения F:
X___Y____Z____F
0___1____0____1
1___1____1____1
1___1____0____0
Какое выражение соответсвует F?
1) X=>(Y=>Z)
2) (X=>)=>Z
3) XVY&˥Z
4) ˥XVY=>Z

3. Учимся составлять таблицы истинности

Самостоятельно проверьте правильность выполнения заданий пункта "2. Таблицы истинности".
1.
A ˥A
1 0
0 1

2.
A__B__AVB__A*В___А=>B___A <=> B
0__0___0____0_____1________1
0__1___1____0_____1________0
1__0___1____0_____0________0
1__1___1____1______1________1

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

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

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


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

Истинность или ложность сложных суждений представляет собой функцию истинности или ложности простых. Эту функцию называют БУЛЕВОЙ ФУНКЦИЕЙ СУЖДЕНИЙ (F(A,B)). Рассмотрим примеры построения таблиц истинности для сложных суждений.

Задание 2.
¬¬А <=> А (закон "отрицания отрицания": Отрицание отрицания суждения тождественно самому суждению.)

А___¬А__¬¬А__¬¬A<=>A
1___0____1____1
0___1____0____1
Если значение истинности булевой функции всегда истина, то эта функция выражает ЗАКОН.

Задание 3
((А => В) & ¬В) => ¬A (доказательство "от противного": Если А влечет В, но В не верно, то не верно и А.)
переменные промежуточные логические формулы итоговая формула
A__B_______A=>B___¬B_____(A=>B)&¬B)____¬A________((A=>B)&¬B)=>¬A
1__1_________1_____0___________0________0_______________1
1__0_________0_____1___________0________0_______________1
0__1_________1_____0___________0________1_______________1
0__0_________1_____1___________1________1_______________1
Задание 4
Для формулы A&(BV¬B&¬C) построить таблицу истинности.
Количество логических переменных 3, следовательно, количество строк в таблице истинности должно быть 2^3 = 8. Количество логических операций в формуле 5, значит количество столбцов в таблице истинности должно быть 3 + 5 = 8.
п е р е м е н н ы е промежуточные логич. формулы итоговая формула
A__B__C__¬B__¬C___¬B&¬C_____BV¬B&¬C_____A&(BV¬B&¬C)
0__0__0___1___1______1__________1____________0
0__0__1___1___0______0__________0____________0
0__1__0___0___1______0__________1____________0
0__1__1___0___0______0__________1____________0
1__0__0___1___1______1__________1____________1
1__0__1___1___0______0__________0____________0
1__1__0___0___1______0__________1____________1
1__1__1___0___0______0__________1____________1

Задания для самостоятельной работы
Задание 1

Заполните таблицу истинности для формулы:¬(ХVY)&(X&¬Y)
переменные промежуточные логические формулы
Х___Y____XVY_____¬(XVY)_____¬Y______X&¬Y
0___0
0___1
1___0
1___1

Задание 2

Составьте таблицы истинности для следующих функций:

Ā => В
В & (А V В)
В & (Ā V В)
Ā => В) V (А & В)

Дополнительно:
Задание 3
Составьте логическую формулу и таблицу истинности для сложного высказывания:"В случае нарушения или оспаривания прав потребитель может обращаться в суд с иском о защите своих прав и охраняемых интересов".(Ст.16 Закона "О защите прав потребителей").

2. Таблицы истинности

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение:
1. Операция, выражаемая словом «не», называется отрицанием и обозначается чертой над высказыванием или знаком. Высказывание истинно, когда А ложно, и ложно, когда А истинно.
2. Операция, выражаемая связкой «и», называется конъюнкцией (от лат. Conjunctio - соединение) или логическим умножением и обозначается «●» или «&» или «^». Высказывание А●В истинно тогда и только тогда, когда оба высказывания А и В истинны.
3. Операция, выражаемая связкой «или», называется дизъюнкцией (от лат. dizjunctio - разделение) или логическим сложением и обозначается + или V. Высказывание АVB истинно тогда и только тогда, когда хотя бы одно истинно, а ложно, когда оба высказывания ложны.
4. Операция, выражаемая связками «если …, то», «из … следует», «… влечет …», называется импликацией (от лат. Implico – тесно связаны) и обозначается =>. Высказывание если А, то В ложно тогда и только тогда, когда А истинно, а В – ложно.
5.Операция, выражаемая связками «тогда и только тогда, когда», называется эквиваленцией и обозначается <=>. Высказывание "А тогда и только тогда, когда В" истинно, когда высказывания А и В одновременно истинны или одновременно ложны. Во всех остальных случаях А<=>B - ложно.
6. Операция, выражаемая связками "А либо В" называется строгая дизъюнкция и обозначается V'. Строгая дизъюнкция истинна, когда А и В принимают различные значения. Во всех остальных случаях она ложна.
Эти операции удобно графически представлять в виде таблиц истинности. Таблица истинности — это таблица, описывающая логическую функцию.

Алгоритм построения таблицы истинности:

подсчитать количество переменных n в логическом выражении;
определить число строк в таблице m = 2n;
подсчитать количество логических операций в формуле;
установить последовательность выполнения логических операций с учетом скобок и приоритетов;
определить количество столбцов в таблице: число переменных плюс число операций;
выписать наборы входных переменных ;
провести заполнение таблицы истинности по столбикам, выполняя логические операции в соответствии с установленной в п.4 последовательностью

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

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


Задание 1.
Заполните в тетради таблицы истинности, соответствующие отрицанию, конъюнкции, дизъюнкции, импликации, эквиваленции.

а)Операция - ..........
A ˥A
1
0

б)Операция - ..........
A B A => B
0 0
0 1
1 0
1 1

в)Операция - ..........
A B A V B
0 0
0 1
1 0
1 1

г)Операция - ..........
A B A&B
0 0
0 1
1 0
1 1

д)Операция - ..........
A B A <=> B
0 0
0 1
1 0
1 1

1. Введение

Алгебра логики – это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания.
Создателем алгебры логики является живший в XIX веке английский математик Джордж Буль, в честь которого эта алгебра названа булевой алгеброй высказываний.
Логическое высказывание – это любое повествовательное предложение, в отношении которого можно точно сказать, истинно оно или ложно.
!!!Не каждое предложение является логическим высказыванием (например, «ученик десятого класса»; Предложения типа «в городе А более миллиона жителей», «у него голубые глаза» не являются высказываниями, так как для выяснения их истинности или ложности нужны дополнительные сведения)
Высказывательная форма – это повествовательное предложение, которое прямо или косвенно содержит хотя бы одну переменную и становится высказыванием, когда все переменные замещаются своими значениями.
Заметим, что зачастую трудно установить истинность высказывания (например, «Площадь поверхности Индийского океана равна 75 млн. кВ. км»)
Употребляемые в обычной речи слова и словосочетания «не», «и», «или», «если …, то », «тогда и только тогда» и другие позволяют из уже заданных высказываний строить высказывательную форму.
Чтобы обращаться с логическими высказываниями, им назначают имена.
Обозначим А – «Тимур поедет летом на море»
В – «Тимур летом отправится в горы»
Составное высказывание «Тимур летом побывает и на море и в горах» можно кратко записать А и В {«и» - логическая связка, А, В – логические переменные, которые могут принимать только два значения: истина или ложь, обозначаемые, соответственно, «1» и «0»}.

Hello, мир!

Добро пожаловать на блог Козловой Татьяны Сергеевны, посвященный решению задач ЕГЭ по информатике, относящихся к теме "Алгебра логики".