- •Конспект №1
- •1Элементы математической логики
- •1.1Высказывания и предикаты.
- •1.2Операции с высказываниями.
- •1.3Составление таблиц истинности логических функций.
- •1.4Таблица основных логических тождеств. Двойственность. Вывод новых тождеств с помощью основных.
- •2Элементы теории множеств.
- •2.1Множества, элементы, подмножества. Пустое множество.
- •2.2Операции с подмножествами универсального множества.
- •2.3Диаграммы Венна. Формула включений-исключений.
- •2.4Доказательства теоретико-множественных тождеств.
- •2.5Кванторы.
- •2.6Декартово произведение множеств
- •2.7Бинарные отношения.
- •2.8Факторизация.
- •3Построение z.
- •4Позиционные системы счисления
- •4.1Степень целого числа с натуральным показателем.
- •4.2Системы счисления
- •5Конечные арифметики
- •5.1Деление с остатком.
- •5.2Признаки делимости.
- •5.2.1Делимость на составные делители.
Конспект №1
Материалы III тура для отбора в углублённые группы по математике 5 и 6 классов ГОУ «школа-интернат Интеллектуал»
1Элементы математической логики
1.1Высказывания и предикаты.
Высказывания – это утвердительные предложения, которым можно придать значение «Истина (True)» или «Ложь (False). Они могут быть выражены на любом языке – русском, английском, китайском и т.д. Важно лишь, чтобы они обладали этим качеством – быть либо истинными, либо ложными. Переменная величина, которая принимает лишь два значения – Т (True) или F (False) называется логической переменной.
Функция1 от нескольких логических переменных принимающая одно из двух значений - Т или F в зависимости от значений своих переменных называется логической функцией.
Упражнение №1.
Среди следующих предложений выберите те, которые являются высказываниями в силу данного определения (поставьте напротив них галочки):
сейчас на улице холодно.
7 больше 5.
Который час?
Оставьте ваше сообщение после длинного гудка.
Перерыв продлится 8 минут.
На полдник опять дадут пирожки с капустой.
Убирайте за собой посуду!
Бутерброд всегда падает маслом вниз.
Миша иногда выполняет домашнее задание.
Если кошка перебежит дорогу, то тарелка упадёт и разобьётся.
Положи ластик на место.
Если в некотором утвердительном предложении содержится переменные величины, которые могут принимать различные значения и при этих значениях переменных утверждение становится истинным или ложным, т.е. превращается в высказывание, то такое предложение будем называть предикатом.
Например: «целое число Х делится на 5». При подстановке вместо Х чисел 5, 10, 20, 30, 100 оно становится истинным, а при подстановке чисел 7, 12, 28, 93 – ложным. В этом предикате одна переменная – число Х. Предикат может содержать несколько переменных. Например, «Х<Y». При подстановке вместо пары переменных Х, Y чисел 3 и 6 получим истинное высказывание, а при подстановке тех же чисел в обратном порядке (6 и 3) – ложное. Чтобы получить высказывание из этого предиката мы должны заменить оба переменных числами.
1.2Операции с высказываниями.
Высказывания будем обозначать строчными латинскими буквами. Заглавными буквами соответственно Т (True) и F (False) будем обозначать соответственно истинное и ложное высказывания. Определим вначале операцию логического отрицания.
Она применяется к одному высказыванию и потому называется “унарной”.
Если обозначить высказывание буквой p, то его отрицание обозначается либо как p (уголок перед p), либо как p (черта сверху над p). Если высказывание p было истинным, то его отрицание считается ложным, и наоборот, если оно было ложным, то его отрицание является истинным. Это определение можно выразить таблицей:
p |
p |
Т |
F |
F |
T |
Следующие операции применяются к паре высказываний и поэтому они называются “бинарными”. Для пары высказываний p, q существуют 4 возможности: оба истинны, оба ложны, первое истинно, второе ложно и наоборот, первое ложно, второе истинно. Поэтому таблицы для них будут содержать 4 строки.
Значения высказываний
|
Название операции |
|||
Дизъюнкция |
Конъюнкция |
Импликация |
||
p |
q |
pq |
pq |
pq |
Результат операции |
||||
T |
T |
T |
T |
T |
T |
F |
T |
F |
F |
F |
T |
T |
F |
T |
F |
F |
F |
F |
T |
Мы видим, что дизъюнкция ложна только тогда, когда оба высказывания ложны и верна, если хотя бы одно из них истинно. В языке это соответствует предлогу или с той лишь разницей, что мы часто, говоря «или» подразумеваем, что верно лишь одно из двух утверждений, но не оба вместе. Такое употребление назовём «разделительным или» и для его обозначения используем знак «!». Конъюнкция, наоборот, верна лишь тогда, когда оба высказывания истинны и ложна во всех остальных случаях. Ей в языке соответствует предлог «и».
Импликация читается как «если p, то q» или, иными словами, «из p следует q».
Считается, что из истины может следовать только истина, а вот из ложного утверждения может следовать всё что угодно, и мы не можем, поэтому, считать высказывание «изо лжи следует истина» ложным. В импликации первый операнд – p называется посылкой, а второй - q – заключением. В дизъюнкции и конъюнкции оба операнда можно поменять местами – результат от этого не изменится.
Это свойство называется коммутативностью. Этим же свойством обладают, например, сложение и умножение чисел. А вот в импликации посылку и заключение поменять местами нельзя.
То же самое относится, например, к операциям вычитания и деления чисел.
Упражнение №2.
Пусть p означает предложение «завтра мы починим крышу» а q – предложение «сейчас пойдёт дождь». Как символически записать утверждения:
Если мы завтра не починим крышу, то сейчас пойдёт дождь,
Если сейчас не пойдёт дождь, то завтра мы починим крышу,
Или мы завтра не починим крышу, или сейчас пойдёт дождь.
И крышу мы завтра не починим, и дождя сейчас не будет.
Запишите словами утверждения, соответствующие формулам:
p(qp)
(pq)q
(pq)p
(pq)p