Информация и информационные процессы

Математические и логические основы информатики

1. Основные понятия математической логики

1. Основные понятия математической логики

Алгебра логики – это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности и ложности) и логических операций над ними [4].

Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно [4].

Для обозначения истины (истинного высказывания) используется символ 1, а для обозначения лжи (ложного высказывания) используется символ 0.

Рассмотрим примеры логических высказываний (см. Таблицу 1):

Таблица 1. Примеры логических выражений

Предложение	Характеристика с точки зрения алгебры логики
Иваново – Родина Первого Совета	Истинное логическое высказывание
За зимой наступит весна	Истинное логическое высказывание
В городе Иваново проживают только граждане России	Ложное логическое высказывание
После дождя всегда тепло	Ложное логическое высказывание
После вторника будет выходной	Не является логическим высказыванием, т.к. не известно, о каком человеке, каком месяце и дне идет речь (если у человека текущий график работы, возможно, что у него в среду будет выходной, в противном случае среда – рабочий день; если в среду будет праздничный день, например, 8 марта, то этот день также будет выходным)

Употребляемые в обычной речи слова и словосочетания «не», «и», «или», «если…то», «тогда и только тогда» и др. позволяют из уже заданных высказываний строить более сложные высказывания. Такие слова и словосочетания называют логическими связками. Высказывания, образованные с помощью логических связок – называют составными высказываниями. Высказывания, не являющиеся составными, называют элементарными.

Для обозначения логических высказываний, им назначают имена. Например, если А – высказывание «В четверг был дождь», В – высказывание «В пятницу было солнечно», то составное высказывание «В четверг был дождь, а в пятницу было солнечно», можно записать в виде:

А и В.

Здесь А, В – логические высказывания (могут быть либо истинными, либо ложными), и – логическая связка.

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение (см. Таблицу 2):

Таблица 2. Логические связки

№	Логическая связка	Название	Обозна-чение	Высказы-вание	Математическая запись
1	и	конъюнкция логическое умножение	Ù, & *, And	A и В	A Ù B, A & B A * B, A And B
2	или	дизъюнкция логическое сложение	Ú +, Or	A или В	A Ú B A + B, A Or B
3	не	инверсия, логическое отрицание	¬, , Not	не А	¬А, , Not A
4	Если…то	импликация, логическое следование	→, Þ	Если A, то В	A → B A Þ B
5	тогда и только тогда	эквивалентность, равносильность, логическое тождество	«, º Û, ~	А тогда и только тогда, когда В	А«В, АºВ АÛВ, А~В

Импликацию можно выразить через дизъюнкцию и отрицание:

A → B = ¬А Ú B

(1)

Эквивалентность можно выразить через отрицание, дизъюнкцию и конъюнкцию:

A « B = (¬А Ú B) Ù (¬B Ú А)

(2)

Вычисление значения логического выражения производится слева направо в соответствии с таблицей истинности (см. Таблицу 3) и приоритетом выполнения логических операций (см. Таблицу 4). Порядок выполнения операций можно менять, используя круглые скобки.

Таблица 3. Таблица истинности

A	B	A Ú B	A Ù B	¬A
0	0	0	0	1
0	1	1	0	1
1	0	1	0	0
1	1	1	1	0

Таблица 4. Приоритет выполнения логических операций

Приоритет операции	Логическая операция
Первый (высший)	Логическое отрицание
Второй	Конъюнкция (логическое умножение)
Третий	Дизъюнкция (логическое сложение)
Четвертый	Импликация (следование)
Пятый (низший)	Эквивалентность (равносильность)

2.Основные законы алгебры логики

В алгебре логики выполняются следующие основные законы, позволяющие производить тождественные преобразования логических выражений (см. Таблицу5.)

Таблица 5. Основные законы алгебры логики

Закон	Для ИЛИ	Для И
Переместительный	xÚy = yÚx	xÙy = yÙx	(3)
Сочетательный	xÚ(yÚz) = (xÚy)Úz	xÙ(yÙz) = (xÙy)Ùz	(4)
Распределительный	xÙ(yÚz) = xÙyÚ xÙz	xÚ yÙz = (xÚy) Ù (xÚz)	(5)
Правила Де Моргана	¬( xÚy)= ¬xÙ(¬y)	¬(xÙy)= ¬xÚ(¬y)	(6)
Идемпотенции	xÚx=x	xÙx=x	(7)
Поглощения	xÚxÙy=x	xÙ(xÚy)=x	(8)
Склеивания	xÙyÚ(¬x)Ùy=y	(xÚy)Ù (¬xÚy)=y	(9)
Операция с переменной с ее инверсией	xÚ(¬x)=1	xÙ(¬x)=0	(10)
Операция с константами	xÚ1=x; xÚ0=х	xÙ1=x; xÙ0=0	(11)
Операция двойного отрицания	¬(¬x)=x		(12)

Задание 1. (Задание А11 демоверсии 2004 г.)

Для какого имени истинно высказывание:

¬(Первая буква имени гласная → Четвертая буква имени согласная)

1) ЕЛЕНА

2) ВАДИМ

3) АНТОН

4) ФЕДОР

Решение.

Введем обозначения для высказываний:

А = «Первая буква имени гласная»	(13)
В = «Четвертая буква имени согласная»	(14)

тогда наше высказывание примет вид: ¬(A → B). Чтобы преобразовать высказывание, воспользуемся тождествами (1), (6), (12):

₍₁₎

₍₆₎

₍₁₂₎

¬(A → B) = ¬((¬A) Ú B) = ¬(¬A) Ù (¬B) = A Ù (¬B)

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

Первая буква гласная Ù ¬(Четвертая буква имени согласная), «

Первая буква гласная Ù Четвертая буква имени гласная.

Этому условию удовлетворяет только имя АНТОН (вариант ответа №3).

Ответ: 3

Задание 2. (Задание А12 демоверсии 2004 г.)

Какое логическое выражение равносильно выражению ¬(A Ú ¬B)

1) AÚB

2) AÙB

3) ¬AÚ¬B

4) ¬AÙB

Решение.

Чтобы преобразовать высказывание, воспользуемся законами (6), (12):

_{(6) (12)}

¬(A Ú ¬B) = ¬A Ù ¬(¬B) = ¬A Ù B, что соответствует ответу №4.

Ответ: 4

Задание 3. (Задание А13 демоверсии 2004г., А11 демоверсий 2005, 2006г.)

Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F:

X	Y	Z	F
0	0	0	1
0	0	1	0
0	1	0	1

Какое выражение соответствует F?

1) ¬XÙ¬YÙZ

2) ¬XÚ¬YÚZ

3) XÚYÚ¬Z

4) XÚYÚZ

Решение.

Способ 1. Наличие двух единиц в столбце F позволяет предположить использование дизъюнкции в логическом выражении. F принимает значение, равное 0, при X=0, Y=0, Z=1, что соответствует логической сумме XÚYÚ¬Z. При проверке этой формулы при значениях первой и третьей строки, получаем верные значения F.

Способ 2. Проверим предложенные ответы:

1) F=¬XÙ¬YÙZ=0 при X=0, Y=0, Z=0, что не соответствует первой строке таблицы.

2) F=¬XÚ¬YÚZ=1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы.

3) Выражение XÚYÚ¬Z соответствует F при всех предложенных комбинациях X,Y,Z.

4) F=XÚYÚZ=1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы.

Таким образом, верный вариант ответа №3.

Ответ: 3

Задание 4. (Задание А9 демоверсий 2005 г., 2006 г.)

Для какого числа X истинно высказывание

X>1 Ù ((X<5)→(X<3))

(15)

1) 1

2) 2

3) 3

4) 4

Решение.

Заменим импликацию, входящую в исходное выражение, воспользовавшись тождеством (1):

₍₁₎

(X>5)→(X<3) = ¬ (X<5) Ú (X<3)

Подставим получившееся выражение в (15):

(X>1)Ù((X<5)→(X<3)) = (X>1) Ù(¬ (X<5) Ú (X<3)) =

=(X>1) Ù ((X>=5) Ú (X<3))

(16)

Найдем значение выражения (16) при заданных значениях X (=1; 2; 3; 4)

X=1: (1>1) Ù((1>=5) Ú (1<3)) = 0Ù(1Ú1) = 0Ù1=0

X=2: (2>1) Ù((2>=5) Ú (2<3)) = 1Ù(0Ú1) = 1Ù1=1

X=3: (3>1) Ù((3>=5) Ú (3<3)) = 1Ù(0Ú0) = 1Ù0=0

X=4: (4>1) Ù((4>=5) Ú (4<3)) = 1Ù(0Ú0) = 1Ù0=0

Верный вариант ответа №2.

Ответ: 2.

Задание 5. (Задание А10 демоверсий 2005 г., 2006 г.)

Укажите, какое логическое выражение равносильно выражению ¬(¬AÙB)

1) A Ú ¬B

2) ¬A Ú B

3) B Ù¬A

4) A Ù¬B

Решение.

Воспользуемся равенствами (6) и (12):

_{(6) (12)}

¬(¬AÙB) = ¬(¬A)Ú¬B = AÚ¬B

Верный вариант ответа №1.

Ответ: 1.

Задание 6. (Задание А13 демоверсий 2005 г., 2006 г.)

Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех). Эти коды представлены в таблице:

A	B	C	D	E
000	01	100	10	011

Определить, какой набор букв закодирован двоичной строкой 0110100011000

1) EBCEA

2) BDDEA

3) BDCEA

4) EBAEA

Решение.

Заметим, что строка 0110100011000 может начинаться только с двух букв: 01(В) или 011(Е). При этом, если первая буква В, то для второй буквы имеется две возможности: 10(D) и 101(-) – нет соответствующей буквы (см. Схему 1) и т.д.

При этом результативным является только одна ветвь дерева (на Схеме 1 она выделена двойной рамкой) – BDCEA, что соответствует варианту ответа №3.

Верный вариант ответа №3.

Ответ: 3.

Задание 7. (Задание А14 демоверсий 2005 г., 2006 г.)

Для составления цепочек используются бусины, помеченные буквами: A, B, C, D, E. На первом месте в цепочке стоит одна из бусин А, С, Е. На втором – любая гласная, если первая буква согласная, и любая согласная, если первая гласная. На третьем месте – одна из бусин С, D, E, не стоящая в цепочке на первом месте. Какая из перечисленных цепочек создана по правилу?

1) CВE

2) АDD

3) EСЕ

4) EAD

Решение.

Введем обозначения для условий:

Условие 1 = «На первом месте в цепочке стоит одна из бусин А, С, Е».

Условие 2 = «На втором – любая гласная, если первая буква согласная, и любая согласная, если первая гласная».

Условие 3 = «На третьем месте – одна из бусин С, D, E, не стоящая в цепочке на первом месте».

Рассмотрим выполнимость Условий 1-3 для вариантов ответов 1) - 4). Поставим символ «1», если соответствующее условие выполнено, «0» - если условие не выполнено (см. Таблицу 6).

Таблица 6. Выполнимость условий 1-3 для вариантов ответов Задания 7.

№ ответа	Вариант ответа	Условие 1	Условие 2	Условие 3
1	CВE	1	0	1
2	АDD	1	1	1
3	EСЕ	1	1	0
4	EAD	1	0	1

Из таблицы 6 видно, что все три условия выполнены только для варианта ответа №2.

Ответ: 2.

Задание 8. (Задание В2 демоверсий 2005 г., 2006 г.)

Сколько различных решений имеет уравнение

(KÙLÙM) Ú (¬LÙ¬MÙN)=1

где K, L, M, N – логические переменные?

В ответе не нужно перечислять все различные наборы K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.

Решение.

Заметим, что поскольку исходное уравнение представляет собой объединение двух логических выражений, то оно равносильно совокупности (объединению) уравнений, состоящих из этих выражений:

KÙLÙM=1	(17)
¬LÙ¬MÙN=1	(18)

При этом уравнение (17) представляет собой пересечение трех логических выражений, и потому оно принимает значение, равное 1, тогда и только тогда, когда каждое из них истинно, т.е. К=L=M=1. На выражение N условий не накладывается, поэтому возможны два варианта решений: 1) К=L=M=1, N=1; 2) К=L=M=1, N=0.

Уравнение (18) также представляет собой пересечение трех логических выражений, и потому оно принимает значение, равное 1, тогда и только тогда, когда ¬L=¬M=N=1. Откуда: L=M=0, N=1. На выражение K условий не накладывается, поэтому у уравнения (18) – также два решения: 1) К=M=0, N=1, K=1; 2)К=M=0, N=1,k=0.

Таким образом, уравнение (17) имеет 2 решения и уравнение (18) имеет два решения. Поскольку исходное уравнение представляет собой объединение этих двух уравнений, то количество его решений равно сумме решений уравнений (17) и (18), т.е. равно 4.

Ответ: 4.

Задание 9. (Задание В2 демоверсии 2004 г.)

Укажите значения переменных K, L, M, N, при которых логическое выражение

(¬KÚ M) → (¬LÚ MÚ N)

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

Решение.

Преобразуем данное выражение, используя равенства (1), (6), (12):

_{(1) (6),
(12)}

(¬KÚ M) → (¬LÚ MÚ N) = ¬ (¬KÚ M) Ú (¬LÚ MÚ N) = (K Ù ¬M) Ú (¬LÚ MÚ N) = 0

Поскольку получившееся выражение представляет собой логическое сложение двух выражений (K Ù ¬M) и (¬LÚ MÚ N), то оно равно тогда и только тогда, когда

K Ù ¬M =0	(19)
¬LÚ MÚ N =0	(20)

Из (20) следует, что ¬L= M= N =0, значит L=1, M=0, N=0.

Подставим M=0 в уравнение (19):

K Ù 1 =0, откуда K=0.

В итоге получим: K=0, L=1, M=0, N=0.

Ответ: 0100.

Задание 10. (Задание В4 демоверсии 2006 г.)

Мама, прибежавшая на звон разбившейся вазы, застала всех трех своих сыновей в совершенно невинных позах: Саша, Ваня и Коля делали вид, что происшедшее к ним не относится. Однако футбольный мяч среди осколков явно говорил об обратном.

‑ Кто это сделал? ‑ спросила мама.

‑ Коля не бил по мячу, ‑ сказал Саша. ‑ Это сделал Ваня.

Ваня ответил: ‑ Разбил Коля, Саша не играл в футбол дома.
‑ Так я и знала, что вы друг на дружку сваливать будете, ‑ рассердилась мама. ‑ Ну, а ты что скажешь? ‑ спросила она Колю.

‑ Не сердись, мамочка! Я знаю, что Ваня не мог этого сделать. А я сегодня еще не сделал уроки, ‑ сказал Коля.

Оказалось, что один из мальчиков оба раза солгал, а двое в каждом из своих заявлений говорили правду.

Кто разбил вазу?

Решение.

Введем обозначения для высказываний:

А = «Коля не бил по мячу» = «¬Коля» = ¬C;

В = «Это сделал Ваня» = «Ваня»;

С = «Разбил Коля» = «Коля»;

D = «Саша не играл в футбол дома» = «¬Саша»;

E = «Ваня не мог этого сделать» = «¬Ваня» = ¬B;

F = «Я сегодня еще не сделал уроки» - не имеет отношения к вопросу «Кто разбил вазу?».

Из условия задачи известно, что один из мальчиков оба раза солгал, а двое в каждом из своих заявлений говорили правду.

Предположим, что солгал первый мальчик, тогда:

A=0 Ù B=0 Ù C=1 Ù D=1 Ù E=1 Ù F=1.

Поскольку A= ¬C и E=¬B, имеем:

¬C=0, B=0, C=1, D=1, ¬B=1, F=1, – противоречий не получили, этот вариант является решением задачи: ¬B=1, C=1, F=1, осталось лишь вспомнить обозначения:

В= «Ваня», значит: ¬B = не «Ваня»;

C=«Коля»;

F=1 – не имеет отношения к вопросу. Значит, вазу разбил Коля.

На всякий случай рассмотрим два других варианта (когда солгал второй или третий мальчики).

Если солгал второй мальчик, то:

С=0 Ù D=0 Ù A=1 Ù B=1 Ù E=1 Ù F=1.

Поскольку A= ¬C и E=¬B, имеем:

C=0, D=0, ¬C=1, B=1, ¬B=1, F=1 – получили противоречие: B=1 и ¬B=1, значит, этот вариант нам не подойдет.

Если солгал третий мальчик, то:

E=0 Ù F=0 Ù A=1 Ù B=1 Ù C=1 Ù D=1.

Заменим: A= ¬C и E=¬B, тогда:

E=0, F=0, ¬C=1, B=1, C=1, D=1– получили противоречие: C=1 и ¬C=1, значит, этот вариант нам не подойдет.

Ответ: Коля.

Задание 11. (Задание В8 демоверсии 2006 г.)

В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу.

Для обозначения логической операции “ИЛИ” в запросе используется символ |, а для логической операции “И” - &.

A		чемпионы \| (бег & плавание)
Б	чемпионы & плавание
В	чемпионы \| бег \| плавание
Г	чемпионы & Европа & бег & плавание

Решение.

Решение задачи сводится с тому, чтобы расположить множества, состоящие из результатов поиска А-Г в порядке возрастания количества элементов. Воспользуемся тем, что логическое умножение для двух множеств равносильно их пересечению, а логическое сложение – их объединению. При этом при пересечении несовпадающих множеств в результате всегда получается множество, меньшее, чем исходные множества, а при объединении – большие, чем исходные (см. Рис. 1 – Рис. 2).

Введем обозначения для множеств и запросов.

Пусть K = «чемпионы»;

L = «бег»;

M = «плавание»;

N = «Европа»,

тогда запрос А = K È L Ç M;

Б = K Ç M;

В = K È L È M;

Г = K Ç N Ç L Ç M.

Из обозначений запросов видно, что самым маленьким по количеству элементов будет множество Г (состоит из пересечений четырех множеств K, L, M, N). Самым большим множеством является множество В, т.к. оно состоит из объединений трех множеств K, L и M. Значит, ответ на Задание 11 будет выглядеть так: Г**В. Осталось определить, какие множества (из А и Б) будут стоять на 2 и 3 местах.

Заметим, что множество Б состоит из пересечений двух множеств K и M, поэтому оно является множеством, меньшим К). Множество А состоит из объединения множества К с пересечением множеств L и M, поэтому А - множество, большее К. Значит, при расположении их в порядке возрастания, получим, что на втором месте в ответе будет стоять Б, а на третьем – А.

Ответ: ГБАВ.

Список литературы

№	Название литературы
1.	Учебно-тренировочные материалы для подготовки к единому государственному экзамену. Информатика/ Крылов С.С., Лещинер В.Р., Супрун П.Г., Якушкин П.А.; под ред. Лещинера В.Р. – М. Интеллект-Центр, 2005 – 136 с.
2.	Информатика и информационные технологии. Учебник для 10-11 классов/ Н.Д. Угринович Н.Д. – М.: Бином. Лаборатория знаний, 2003. – 512 с.: ил.
3.	Практикум по информатике и информационным технологиям. Учебное пособие для общеобразовательных учреждений / Н.Д. Угринович Н.Д., Л. Л. Босова, Н.И. Михайлова. – М.: Бином. Лаборатория знаний, 2002. – 400 с.: ил.
4.	Информатика: Учеб. Пособие для 10-11 кл. общеобразовательных учреждений/ Л. З. Шауцукова. – 3-е изд. – М.: Просвещение, 2003. – 416 с.: ил.
5.	Информатика в школе: Приложение к журналу «Информатика и образование» №6 – 2005.- М.: Образование и информатика, 2005. – 104 с.: ил.
6.	Единый государственный экзамен по информатике. Демонстрационный вариант 2004 г.
7.	Единый государственный экзамен по информатике. Демонстрационный вариант 2005 г.
8.	Единый государственный экзамен по информатике. Демонстрационный вариант 2006 г.
9.	Методическая разработка учителя информатики высшей категории СОШ №4 г. Родники Кулигиной Г.К. «Алгебра логики»/ Отдел образования администрации МО «Родниковский район», 2005 г.

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

1. Для какого имени истинно высказывание:

Первая буква имени согласная Ù (¬Вторая буква имени согласная → Четвертая буква имени гласная):

1) ИВАН

2) ПЕТР

3) ПАВЕЛ

4) ЕЛЕНА

2. Какое логическое выражение равносильно ¬(¬X Ù ¬Y)?

3. Какое логическое выражение равносильно (¬X Ú Y) Ù X?

4. Какое логическое выражение F(A,B) соответствует таблице истинности:

A	B	F
0	0	1
0	1	1
1	0	0
1	1	1

5. В понедельник в одном из классов должно быть проведено 4 урока – по математике, физике, информатике и биологии. Учителя высказывали свои пожелания для составления расписания. Учитель математики хотел бы проводить первый или второй урок, учитель физики – второй или третий, учитель информатики не второй и не третий, учитель биологии – третий и четвертый. Какой вариант расписания устроит всех учителей? (Обозначения: М – математика, Ф – физика, И – информатика, Б – биология)

1) ИМБФ

2) МФБИ

3) МИФБ

4) МБФИ

6. X, Y, Z – целые числа, для которых истинно высказывание

(Z<X Ú Z<Y) Ù (¬Z+1< X) Ù ¬(Z+1< Y)

Чему равно Z, если X=20, Y=10?

7. Три свидетеля дорожного происшествия сообщили сведения о скрывшемся нарушителе. Боб утверждает, что тот был на синем «Рено». Джон сказал, что нарушитель ехал на черной «Тойоте», а Сэм сказал, что машина была точно не синяя, и, по всей видимости, это был «Форд». Когда удалось отыскать машину, выяснилось, что каждый из свидетелей точно определил только один из параметров автомобиля, а в другом ошибся. Машина какой марки и какого цвета была у нарушителя?

8. В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу.

A	законы & физика
Б	законы \| (физика & биология)
В	законы & физика & биология & химия
Г	законы \| физика \| биология

Ответы к заданиям для самостоятельного решения

Задание	1	2	3	4	5	6	7	8
Ответ	2	xÚy	xÙy	A→B или=¬AÚB	2	Z=19	Черный Рено	ВАБГ