Квалификации и переподготовки работников образования предпрофильная подготовка

ТОМСКИЙ ОБЛАСТНОЙ ИНСТИТУТ ПОВЫШЕНИЯ

КВАЛИФИКАЦИИ И ПЕРЕПОДГОТОВКИ

РАБОТНИКОВ ОБРАЗОВАНИЯ

ПРЕДПРОФИЛЬНАЯ ПОДГОТОВКА

УЧАЩИХСЯ 9-Х КЛАССОВ
Учебно-методические пособия к спецкурсам

предпрофильной подготовки

по информатике

Томск 2011

Предпрофильная подготовка учащихся 9 классов. Учебные программы курсов по информатике. – Томск, ТОИПКРО. - 2011. - 54 с.

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

Научный редактор

Дозморова Е.В., к.п.н., ТОИПКРО

©ТОИПКРО,2011

СОДЕРЖАНИЕ

А.В. Розина. Логика в задачах………………………………………………………….3

А.Ф. Мещеряков. Основы компьютерной живописи………………………………28

Логика в задачах

(Учебно-методическое пособие к спецкурсу предпрофильной подготовки)

А.В. Розина
Пояснительная записка

В программе школьного курса по информатике, отраженной в обязательном минимуме содержания среднего (полного) общего образования, особое место уделяется теме «Основы математической логики». Знание данной темы является основой для формирования у школьников особого алгоритмического мышления, развития способностей решать нестандартные задачи по любому из школьных предметов.

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

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

Тематический план

№	Наименование разделов и дисциплин	Всего часов
№	Наименование разделов и дисциплин	Всего часов
1.	Общие сведения о науке «Математическая логика» Становление науки Высказывания	1
2. 2.1 2.2.	Основные логические операции Конъюнкция, дизъюнкция, отрицание, импликация, эквиваленция, таблицы истинности Перевод высказываний на язык алгебры логики	2 1
3. 3.1. 3.2.	Тождественность логических формул Тождественно-истинные формулы Тождественно-ложные формулы Доказательство тождественности 2-х формул	1 2
4. 4.1. 4.2.	Законы математической логики Основные законы математической логики Равносильные преобразования формул	2 2
5.	Решение текстовых логических задач	7
ИТОГО:		18

Описание тем и разделов

Общие сведения о науке Математическая логика.

Зарождение формальной логики. Основные формы мышления: Понятия, Суждения, Умозаключения. Появление математической (символьной) логики. Высказывания.

Занятие – 1 час
2. Основные логические операции

2.1. Конъюнкция, дизъюнкция, отрицание, импликация, эквиваленция., построение таблиц истинности.

2.2. Перевод высказываний на язык алгебры логики - для решения логических содержательных задач необходимо перевести все высказывания в символику алгебры логики.

Занятие – 3 часа
3. Тождественность логических формул

Тождественно-истинные формулы Тождественно-ложные формулы.
Доказательство тождественности 2-х формул - через построение таблиц истинности.

Занятие – 3 часа

4. Законы математической логики

4.1. Основные законы математической логики – переместительный, сочетательный, распределительный, де Моргана. Формулы склеивания и поглощения.

4.2 Равносильные преобразования формул – решение задач.

Занятие – 4 часа
5. Решение текстовых логических задач

На занятиях решаются содержательные задачи при помощи составления выражений по таблице истинности и с помощью преобразования формул.

Занятие – 7 часов

Решение логических задач (методические рекомендации)

Содержание

Логические операции……………………………………………………………………..9

1.1. Операция логического отрицания (инверсия)……………………………………….9

Операция логического сложения (дизъюнкция)……………………………………..9
Операция логического умножения (конъюнкция)………………………………… .10
Импликация…………………………………………………………………………...11
Эквиваленция…………………………………………………………………………11

2. Законы логики……………………………………………………………………………...12

3. Как решать логические задачи…………………………………………………………...13

Решение логических задач средствами алгебры логики…………………………...13
Решение логических задач табличным способом…………………………………..18

3.3. Решение логических задач с помощью рассуждений………………………………20

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

5. Литература…………………………………………………………………………………..27

1. Логические операции

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

1. 1. Операция логического отрицания (инверсия)

А: “Сегодня в 12 часов дня я был на катке.”
В: “Сегодня Миша был на катке в 12 часов дня.”
С: “Я был на катке в 12 часов не сегодня.”
D: “Сегодня в 12 часов дня я был в кино.”
E: “Сегодня я был на катке в 3 часа дня.”
F: “Сегодня в 12 часов дня я не был на катке.”

Рассмотрим высказывания A и F. Высказывание F истинно, если А - ложно и наоборот. Его называют отрицанием высказывания А.

Остальные высказывания не являются инверсией, так как об отрицании высказывания может идти речь, если имеем высказывания об одном и том же субъекте, времени, месте и отношении.

Высказывания С, E не являются инверсией, т.к. разное время действия.

Высказывание В не является инверсией, т.к. разный субъект

Высказывание D не является инверсией, т.к. разное место действия

Присоединение частицы “не” к сказуемому данного простого высказывания А называется логическим отрицанием.

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

или NOT A- указание выполнить логическое отрицание над высказыванием А.
Иногда используют другое определение: присоединение слов “неверно что...” ко всему данному высказыванию есть логическое отрицание.
Пример: А: “5 является делителем числа 30”

: “Неверно, что число 5 является делителем числа 30.”

Логическая операция ИНВЕРСИЯ

соответствует частице НЕ;
обозначается черточкой над именем переменной;
иначе называется ОТРИЦАНИЕ.

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

Таблица истинности инверсии имеет вид:

A
0	1
1	0

1.2. Операция логического сложения (дизъюнкция)

Соединение двух высказываний А и В в одно с помощью союза “ИЛИ”, употреб-яемого в неисключающем смысле, называется логическим сложением (дизъюнкцией), а полученное составное высказывание - логической суммой.

Пример высказывания, употребляемого в исключающем смысле: ”Председателем кооператива “Аметист” будет избран Иванов, или председателем кооператива “Аметист” будет избран Петров”.

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

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

Дизъюнкция обозначается знаком “+”, или знаком “ “, или союзом OR

А + В АВ A OR B

Пример: А: “6 - число кратное 3” В: “19> 37”
Логической суммой или дизъюнкцией этих высказываний будет
“6 - число кратное 3 19>37”

Логическая операция дизъюнкция

соответствует союзу ИЛИ;
обозначается знаками  , + , OR,
иначе называется ЛОГИЧЕСКОЕ СЛОЖЕНИЕ.

Дизъюнкция двух логических переменных ложна тогда и только тогда, когда оба высказывания ложны.
Это определение можно обобщить для любого количества логических переменных, объединенных дизъюнкцией.
А  В  С =0, только если А=0, В=0, С=0.
Таблица истинности дизъюнкции имеет следующий вид:

A	B	АВ
0	0	0
0	1	1
1	0	1
1	1	1

1.3. Операция логического умножения (конъюнкция)

Соединение двух высказываний А и В в одно с помощью союза “И” называется логическим умножением (конъюнкцией).
Результат умножения (составное высказывание) называется логическим произведением.
Конъюнкция обозначается знаком “· ”, или знаком “  “, или союзом AND

А· В А  В A AND B
Пример: Пусть даны два простых высказывания:
А: “Вильнюс - столица Литвы.”
В: “В Вильнюсе проживает 1 млн. жителей.”
Получим конъюнкцию:
Вильнюс - столица Литвы  в Вильнюсе проживает 1млн. жителей.

Логическая операция КОНЪЮНКЦИЯ

соответствует союзу И;
обозначается знаком  или  или AND;
иначе называется ЛОГИЧЕСКОЕ УМНОЖЕНИЕ.

Конъюнкция двух логических переменных истинна тогда и только тогда, когда оба высказывания истинны.
Это определение можно обобщить для любого количества логических переменных, объединенных конъюнкцией.
А  В  С=1, только если А=1, В=1, С=1.

Таблица истинности конъюнкции имеет следующий вид:

A	B	А  В
0	0	0
0	1	0
1	0	0
1	1	1

1.4. Импликация

Логическая операция, соответствующая союзу “если ..., то ...” называется импликацией.
Будем обозначать эту операцию символом  . Запись А В читается так: “если А, то В”, либо “А имплицирует В”.
С - “Если число n делится на 4 , то оно делится на 2”
D - “Если Иванов увлечен математикой, то Петров ничем, кроме хоккея, не интересуется.”

Логическая операция ИМПЛИКАЦИЯ

соответствует союзу ЕСЛИ..., ТО...;
обозначается знаком  .

Импликация высказываний ложна лишь в случае, когда А истинно, а В ложно.
Обещание приятеля: “Если будет хорошая погода, то я приду к тебе в гости”, - вы расцените как ложь в том и только в том случае, когда погода будет хорошая, а приятель к вам не придет.
Таблица истинности импликации:

А	В	А В
1	1	1
1	0	0
0	1	1
0	0	1

1.5. Эквиваленция

Логическая операция, соответствующая союзу “тогда и только тогда, когда” называется эквиваленцией.
Введем для обозначения эквиваленции символ  .
Запись А  В читается так: “А тогда и только тогда, когда В”.
Когда мы говорим “А тогда и только тогда, когда В”, то имеем в виду, что оба предложения А и В одновременно истинны, либо одновременно ложны.
Например, “Я поеду в Ленинград тогда и только тогда, когда ты поедешь в Киев.”

Логическая операция ЭКВИВАЛЕНЦИЯ

соответствует союзу ТОГДА И ТОЛЬКО ТОГДА, КОГДА...;
обозначается знаком  .

Эквиваленция двух высказываний истинна в том и только в том случае, когда оба эти высказывания истинны или оба ложны.

А	В	А В
0	0	1
0	1	0
1	0	0
1	1	1

Пример.
sin 30 = 1/2  2· 2=4 истина
sin 30 = 1/2  2· 2=5 ложь
sin 30 = 1  2· 2=4 ложь
sin 30 = 1  2· 2=5 истина
2. Законы логики

Равносильности формул логики высказываний часто называют законами логики.

Знание законов логики позволяет проверять правильность рассуждений и доказательств.
Нарушения этих законов приводят к логическим ошибкам и вытекающим из них противоречиям.
Перечислим наиболее важные из них:
1. X X Закон тождества
2.

Закон противоречия
3.

Закон исключенного третьего
4.

Закон двойного отрицания
5. X X X , X X  Законы идемпотентности
6        ,        Законы коммутативности (переместительности)
                ,                - Законы ассоциативности (сочетательности)
8.                   ,                    - Законы дистрибутивности (распределительности)
9. , Законы де Моргана
10. X 1  ,     
11.      ,     
12.          ,          ,         ,           Законы поглощения
13.            ,             Законы склеивания

1-й закон сформулирован древнегреческим философом Аристотелем. Закон тождества утверждает, что мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует.

Закон противоречия говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием.
“Это яблоко спелое” и “Это яблоко не спелое”.

Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно либо ложно. Третьего не дано. “Сегодня я получу 5 либо не получу”. Истинно либо суждение, либо его отрицание.

Закон двойного отрицания. Отрицать отрицание какого-нибудь высказывания - то же, что утверждать это высказывание.
“ Неверно, что 2 2 4”

Законы идемпотентности. В алгебре логики нет показателей степеней и коэффициентов. Конъюнкция одинаковых “сомножителей” равносильна одному из них.

Законы коммутативности и ассоциативности. Конъюнкция и дизъюнкция аналогичны одноименным знакам умножения и сложения чисел.
В отличие от сложения и умножения чисел логическое сложение и умножение равноправны по отношению к дистрибутивности: не только конъюнкция дистрибутивна относительно дизъюнкции, но и дизъюнкция дистрибутивна относительно конъюнкции.

Смысл законов де Моргана (Август де Морган (1806-1871) - шотландский математик и логик) можно выразить в кратких словесных формулировках:

- отрицание логического произведения эквивалентно логической сумме отрицаний множителей.

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

следующая страница >>