Книга-тренажер: «Базовая подготовка к ЕГЭ по информатике в компьютерной форме». Авторский курс

Евгений Леонидович Сидоркин

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

Глава 2. Алгебра логики и базы данных

Задание №2. Алгебра логики

Алгебра логики или булева алгебра — так их называют. Как вы думаете, для чего вообще нужна алгебра логики, кроме как мучить детей? Представьте, что по проводу течет ток. Если ток есть в проводе, то обозначим это действие за 1, т.е. истина. Если же тока нет, то ноль, т.е. ложь. Сборка различных схем на компьютере осуществляется как раз схемами, которые представлены на рис.1.

Рисунок №1

Причем можно усложнить схемы, сделать их большими и громоздкими. В компьютере, понятное дело, используются большие логические схемы взаимодействий. Учить это не хочется, но важно понять, как это работает. Для этого и придумали алгебру логики. Какая бы сложная схема ни получилась, ее всегда можно упростить до двух проводов, далее буду говорить до 2 переменных, на языке алгебры логики. Высказывание — повествовательное предложение, о котором можно сказать, истинно оно или ложно. В алгебре простым высказываниям ставятся в соответствии логические переменные (А, В, С и т.д.). Пример высказываний:

Рисунок №2

Логическая переменная — это простое высказывание.

Логические переменные обозначаются прописными и строчными латинскими буквами (a-z, A-Z) и могут принимать всего два значения — 1, если высказывание истинно, или 0, если высказывание ложно.

Логическая формула (логическое выражение) — формула, содержащая лишь логические переменные и знаки логических операций. Результатом вычисления логической формулы является ИСТИНА (1) или ЛОЖЬ (0).

Логическое умножение — конъюнкция. Принятые обозначения: /\, •, и, and. Этой операции соответствует знак умножения. Например, переменные А=0, B=0, то F=A*B=0*1=0. То же самое можно представить в виде примера А=«Немцы победили русских в Великой Отечественной войне»=0, ложь, т.к. русские выиграли, B=«Лимон кислый на вкус»=1, истина, т.к. это соответствует действительности. Тогда A*B=0*1=0, т.к. я настаиваю, чтобы и А, и B выполнялось (через действие умножение), поэтому значением выражения будет ложь. Остальные значения таблицы истинности вы можете посмотреть на Рисунке №3. Логическая формула истинна только в одном случае и ложна в трех других.

Рисунок №3

Логическое сложение (дизъюнкция). Объединение двух (или нескольких) высказываний в одно с помощью союза ИЛИ. Обозначение: \/, +, или, or.

Рисунок №4

На рисунке №4 функция истинна в трех случаях и ложна только в одном, когда ложь. Дизъюнкции соответствует знак сложения.

Отрицание (инверсия), от лат. InVersion — переворачиваю — Рисунок №5:

Соответствует частице НЕ, словосочетаниям НЕВЕРНО, ЧТО или НЕ. Обозначение: не А, ¬А, not. В данной функции значения функции меняются наоборот. Если А=0, то F= Не А=1.

Рисунок №5

Логическая функция импликация. Обозначается cтрелкой — >. В языке программирования соответствует операции меньше либо равно <=. Как из лжи А=0 получить ложь B=0? Рассмотрим на примере A=2> 3 — ложь, то прибавим к обоим частям неравенства +2 и получим тоже ложь B = 4> 5. Если из лжи А=0 и B=0 можно получить ложь, значит, истина A — > B=1. A= — 5> 3 — ложь, то обе части неравенства возведу в квадрат и получим уже истину B= 25> 9, тогда при A=0 и B=0 получаю, что А — > B=1. Из истины А=1 я не могу получить B=0, поэтому A — > B=0. Если вы поняли смысл, как мы получили логические высказывания, то вам не потребуется зубрить таблицы истинности.

Рисунок №6

Вы еще не устали от логики)?

Последняя функция эквиваленция. Обозначается как на рисунке №6.

Рисунок №6

Функция истинна A <-> B=1 только в двух случаях: либо когда обе логических переменных А и B истинны, или когда А и B — ложны.

В каком же приоритете выполняются данные операции, спросите Вы? Да все очень просто: сначала отрицание, затем конъюнкция (умножение), потом дизъюнкция (сложение), далее импликация и эквиваленция.

Рисунок №7

В ЕГЭ представлено две задачи на знания алгебры логики. Это задачи №2 и №15. Рассмотрим основные типы этих задач ниже.

Пример 2.1

Логическая функция F задается выражением (x ⟶ y) ∧ (x ∨ ¬z) ∧ (x ≣ ¬w). Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных w, x, y, z.

Решение:

Первый способ — это написание программы на языке программирования Python. Код представлен ниже.

print (’x’,’y’,’z’,’w’)

def f (x,y,z,w):

return (not x or y) and (x or not z) and (x == (not w)) # условие из задачи, преобразовали x ⟶ y= not x or y

for x in range (0,2): # изменение переменных от истины до лжи.

for y in range(0, 2):

for w in range(0, 2):

for z in range(0, 2):

if f (x,y,z,w) == 1: # условие истинности из задачи

print (x,y,z,w)

После запуска программы мы можем заметить строку, содержащую 0 0 0 1. Если сравнить эту строку со строками из таблицы (что в условии), то в данной таблице мы не найдем строку с тремя нулями, поэтому строку 0 0 0 1 можем смело исключить из решения. Рассмотрим оставшиеся три строки, которые необходимо сопоставить с таблицей, что в условии. Второй столбец с тремя единицами соответствует второму столбцу из таблицы, значит, второй столбец — Y. В первую ячейку третьего столбца однозначно можно поставить только ноль, и тогда образуется первая строка 1 1 1 0. Т.к. в последней строчке из рисунка №7 стоит такая же строка 1 1 1 0, что в условиях таблицы, то третий столбец — однозначно W. На рисунке №7 в первой и третьей ячейке третьей строки стоят нули, которые мы можем перенести в таблицу из условия на соответствующие места и однозначно определить, что Z — это первый столбец, а Z — третий.

Рисунок №7

x y z w

0 1 0 1

1 1 0 0

1 1 1 0

Решение:

Второй способ решения этой же задачи состоит в том, что мы составляем таблицу истинности без помощи компьютера. Заполняем первую строку, если w=0, то x=1, а y=1, а z — или ноль, или один. Итого получим почти две одинаковые строчки, за исключением значения z. 1 1 0 0 и 1 1 1 0. Теперь предположим, что W=1, тогда x=0. Т.к. в условии есть столбец с тремя единицами, то необходимо в ручном решении тоже получить такой столбец, поэтому y=1, а z=0. Ответ: ZYWX.

Пример 2.2

Логическая функция F задается выражением (¬z) ∧ x ∨ x ∧ y. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.

Решение:

Расставим скобки, выражение (¬z) ∧ x ∨ x ∧ y является дизъюнкцией двух конъюнкций: ((¬z) ∧ x) ∨ (x ∧ y). В обеих конъюнкциях присутствует x. То есть при x = 0 все выражение равно нулю. Только в третьем столбце напротив нулей стоят значения функции F=0, поэтому третий столбец — это x. Также можно заметить, что выражение ((¬z) ∧ x) ∨ (x ∧ y) =1, если x =1 и выполняется хотя бы одно из условий: y = 1 или z = 0. Из четвертой строки следует, что Перем.1 = z, а Перем.2 = y.

Ответ: zyx.

Пример 2.3

Дан фрагмент таблицы истинности для выражения F. Укажите максимально возможное число различных строк полной таблицы истинности этого выражения, в которых значения x4 не совпадает с F.

Решение:

Таблица истинности выражения с семью переменными (x1…x7) содержит 2⁷=128 строк. В приведенном фрагменте таблицы x4 не совпадает с F в 4-х строках, а совпадает только в последней нижней строке. Во всех остальных может не совпадать. Тогда максимально возможное количество строк, где значения x4 и F не совпадают, будет 128—1=127.

Ответ: 127.

Задачи для самостоятельного решения

Задача 2.4

Логическая функция F задаётся выражением: (x ∧ ¬ y) ∨ (y ≣ z) ∨ w. На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w. В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Задача 2.5

Для функции F известен фрагмент таблицы истинности, представленный ниже. Определите, какое максимальное количество единиц может быть в столбце F полной таблицы истинности, если известно, что при значении x4 = 1 значение функции равно 1.

Задача №3. Файловая система. Базы данных

Возможно, помните из школьного курса информатики, что файл представляет собой имя файла и расширение. Например, mama.doc. Где расширение? Слева от точки — это имя файла, а справа — расширение. Примеры некоторых типов файлов:

Текстовые файлы — расширения. txt,.doc;

Исполняемые файлы — расширения. exe,.com;

Звуковые файлы — расширения. mp3,.waf.

Звездочка «*» — заменяет любое количество (в том числе и нулевое) любых символов.

«?» — заменяет один и только один обязательно стоящий в указанном месте символ. Например, по маске «*.*» будут отобраны вообще все файлы с любыми именами и расширениями, по маске «*.txt» — файлы с расширением. txt, по маске «aл?.doc» — файлы, с расширением. doc, имена которых начинаются на «aл» и имеют обязательный непустой третий символ.

Для хранения и обработки большого объема информации организовывают Базы Данных. Под Базой Данных понимают организованную в соответствии с некоторыми правилами структурированную совокупность логически связанных данных. Эти данные предназначены для удобного совместного хранения и анализа.

Реляционная База Данных состоит из связанных между собой таблиц.

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

Пример 3.1

Для групповых операций с файлами используются маски имен файлов. Маска представляет собой последовательность букв, цифр и прочих допустимых в именах файлов символов, в которых также могут встречаться следующие символы: символ»?» (вопросительный знак) означает ровно один произвольный символ. Символ «*» (звездочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность. Определите, какое из указанных имен файлов удовлетворяет маске:?fi*r.?xt

1) dir. txt 2) ofir. txt 3) ofir. xt 4) firr. txt

Решение:

Рассмотрим все варианты ответов: 1) не подходит, т.к. в имени отсутствует буква f; 2) полностью удовлетворяет условию маски; 3) не подходит, т.к. на месте»?» после точки отсутствует лишний символ перед буквой x; 4) не подходит, т.к. перед буквой f нет никакого символа, а он должен быть по условию задачи.

Ответ: 2.

Пример 3.2

Каталог содержит файлы с именами

а) p5.pas г) pq. u

б) p4.ppt д) pq.pas

в) p12.pas е) p12.ppt

Определите, в каком порядке будут показаны файлы, если выбрана сортировка по типу (по возрастанию).

1) вадгеб 2) гавдбе

3) вадгбе 4) гвадеб

Решение:

Отсортируем файлы по типу (по возрастанию), а это значит, что сначала отсортируем по расширению, а потом по имени файла. Все расширения начинаются на одну букву p, тогда смотрим расширения. На первом месте будет стоять файл, в расширении которого вообще нет второй буквы — пустой символ всегда меньше непустого: pq. u (г).

Далее идут файлы с расширением. pas (а и д), но поскольку таких файлов несколько, то анализируем имена файлов. Известно, что цифра «меньше» буквы в кодировочной таблице.

p12.pas (в) — т.к. 1 <5

p5.pas (а) — т.к. 5 <q

pq.pas (д) —

Дальше идут файлы с расширением. ppt, т.к. в расширении ppt вторая буква p больше второй буквы а в расширении pas.

p12.ppt (е) — т.к. 1 <4

p4.ppt (б)

Ответ: 4. pq. u, p12.pas, p5.pas, pq.pas, p12.ppt, p4.ppt

Пример 3.3

Ниже представлены два фрагмента таблиц из базы данных о жителях микрорайона. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных ID женщины, ставшей матерью в наиболее молодом возрасте. При вычислении ответа учитывайте только информацию из приведённых фрагментов таблиц.

Решение:

Нарисуем 3 дерева ниже, где матерями будут выступать женщины со следующими ID: 44, 34, 64. По рисунку ниже мы видим, что мать с ID= 44 родила в 26 и 36 лет, мать с ID=34 родила в 26 и 29 лет, а мать с ID=64 родила в 22 и 28 лет. Из чего можем сделать вывод, что 22 года — это самый младший возраст женщины, которая родила ребенка. Поэтому это мать с ID=64.

Ответ: 64.

Задачи для самостоятельного решения

Задача 3.4

Ниже представлены два фрагмента таблиц из базы данных о жителях микрорайона. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных, у скольких детей на момент их рождения отцам было больше 25 полных лет. При вычислении ответа учитывайте только информацию из приведённых фрагментов таблиц.

Задача 3.5

Для групповых операций с файлами используются маски имен файлов. Маска представляет собой последовательность букв, цифр и прочих допустимых в именах файлов символов, в которых также могут встречаться следующие символы: символ»?» (вопросительный знак) означает ровно один произвольный символ. Символ «*» (звездочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность. Определите, какое из указанных имен файлов не удовлетворяет маске: bys??.*

1) byste. m 2) bys23.exe 3) bystem. dll 4) byszx.problem