Высказывания и предикаты.

Абрамсон Я.И. 14.09.2015

Конспект №1

Материалы III тура для отбора в углублённые группы по математике 5 и 6 классов ГОУ «школа-интернат Интеллектуал»

Элементы математической логики

Высказывания и предикаты.

Высказывания – это утвердительные предложения, которым можно придать значение «Истина (True)» или «Ложь (False). Они могут быть выражены на любом языке – русском, английском, китайском и т.д. Важно лишь, чтобы они обладали этим качеством – быть либо истинными, либо ложными. Переменная величина, которая принимает лишь два значения – Т (True) или F (False) называется логической переменной.

Функция[1] от нескольких логических переменных принимающая одно из двух значений - Т или F в зависимости от значений своих переменных называется логической функцией.

Упражнение №1.

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

a) сейчас на улице холодно.

b) 7 больше 5.

c) Который час?

d) Оставьте ваше сообщение после длинного гудка.

e) Перерыв продлится 8 минут.

f) На полдник опять дадут пирожки с капустой.

g) Убирайте за собой посуду!

h) Бутерброд всегда падает маслом вниз.

i) Миша иногда выполняет домашнее задание.

j) Если кошка перебежит дорогу, то тарелка упадёт и разобьётся.

k) Положи ластик на место.

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

Например: «целое число Х делится на 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, q существуют 4 возможности: оба истинны, оба ложны, первое истинно, второе ложно и наоборот, первое ложно, второе истинно. Поэтому таблицы для них будут содержать 4 строки.

Мы видим, что дизъюнкция ложна только тогда, когда оба высказывания ложны и верна, если хотя бы одно из них истинно. В языке это соответствует предлогу или с той лишь разницей, что мы часто, говоря «или» подразумеваем, что верно лишь одно из двух утверждений, но не оба вместе. Такое употребление назовём «разделительным или» и для его обозначения используем знак «!». Конъюнкция, наоборот, верна лишь тогда, когда оба высказывания истинны и ложна во всех остальных случаях. Ей в языке соответствует предлог «и».

Импликация читается как «если p, то q» или, иными словами, «из p следует q».

Считается, что из истины может следовать только истина, а вот из ложного утверждения может следовать всё что угодно, и мы не можем, поэтому, считать высказывание «изо лжи следует истина» ложным. В импликации первый операнд – p называется посылкой, а второй - q – заключением. В дизъюнкции и конъюнкции оба операнда можно поменять местами – результат от этого не изменится.

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

То же самое относится, например, к операциям вычитания и деления чисел.

Упражнение №2.

Пусть p означает предложение «завтра мы починим крышу» а q – предложение «сейчас пойдёт дождь». Как символически записать утверждения:

a) Если мы завтра не починим крышу, то сейчас пойдёт дождь,

b) Если сейчас не пойдёт дождь, то завтра мы починим крышу,

c) Или мы завтра не починим крышу, или сейчас пойдёт дождь.

d) И крышу мы завтра не починим, и дождя сейчас не будет.

Запишите словами утверждения, соответствующие формулам:

a) ØpÞ(qÚp)

b) (pÙq)ÞØq

c) (pÙØq)Þp

d) Ø(pÚØq)ÙØp