НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ

ИНСТИТУТ МЕНЕДЖМЕНТА И ЭКОНОМИКИ В ЭНЕРГЕТИКЕ И ПРОМЫШЛЕННОСТИ

Лукьянова Т.В.

ИНФОРМАТИКА

КОНСПЕКТ ЛЕКЦИЙ

Москва - 2013

ОГЛАВЛЕНИЕ

Страница 2 из 47

Страница 3 из 47

1. ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ ЛОГИКИ. ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМ

1.1.Логика высказываний. Алгебра логики

1.1.1.История развития и общие понятия

Логика – наука о принципах правильного мышления.

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

I этап.

Принято считать, что с работ Аристотеля (384–322 до н.э.) началось систематическое изучение логики и ее законов. Он подверг анализу человеческое мышление, его формы – понятие, суждение, умозаключение и рассмотрел мышление со стороны строения, структуры, то есть с формальной стороны. Так возникла формальная логика. Аристотель исследовал различные формы рассуждений и их комбинаций, ввел понятие силлогизма, т.е. рассуждения, в котором из заданных двух суждений выводится третье.

Например: "Все млекопитающие имеют скелет. Все киты – млекопитающие. Следовательно, все киты имеют скелет."

II этап.

Основы математической или символической логики заложил немецкий ученый и философ Готфрид Вильгельм Лейбниц (1646-1716). Он попытался построить первые логические исчисления, считал, что можно заменить простые рассуждения действиями со знаками и привел правила. Но Лейбниц высказал только идею, а развил ее окончательно англичанин Джордж Буль (1815-1864). Буль считается основоположником математической логики как самостоятельной дисциплины.

Страница 4 из 47

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

Алгебра логики рассматривает любое высказывание только с одной точки зрения – является ли оно истинным или ложным. Заметим, что зачастую трудно установить истинность высказывания. Так, например, высказывание "площадь поверхности Индийского океана равна 75 млн кв. км" в одной ситуации можно посчитать ложным, а в другой – истинным. Ложным – так как указанное значение неточное и вообще не является постоянным. Истинным – если рассматривать его как некоторое приближение, приемлемое на практике.

Употребляемые в обычной речи слова и словосочетания "не", "и", "или",

"неверно, что ... ", "если ... , то ... ", "тогда и только тогда ... , когда ... " и

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

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

Так, например, из элементарных высказываний "Петров – врач", "Петров

– шахматист" при помощи связки "и" можно получить составное высказывание "Петров – врач и шахматист", понимаемое как "Петров – врач, хорошо играющий в шахматы".

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

Истинность или ложность получаемых таким образом составных высказываний зависит от истинности или ложности элементарных высказываний.

Простые высказывания называют логическими переменными (значением которой может быть только 0 или 1. Если высказывание истинно, то его

Страница 6 из 47

значение равно 1, если ложно – 0), а сложные высказывания логическими функциями (значения логической функции также только 0 или 1).

Чтобы обращаться к логическим высказываниям, им назначают имена. Пусть через А обозначено высказывание "Тимур поедет летом на море", а через В – высказывание "Тимур летом отправится в горы". Тогда составное высказывание "Тимур летом побывает и на море, и в горах" можно кратко записать как А и В. Здесь "и" – логическая связка, А, В – логические переменные, которые могут принимать только два значения – "истина" или "ложь", обозначаемые, соответственно, "1" и "0".

1.1.2. Операции над высказываниями

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

1. ОТРИЦАНИЕ (логическое "НЕ"). Операция, выражаемая словом "не", называется отрицанием и обозначается чертой над высказыванием (или знаком ). Запись А или читается как "не А". Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна, т.е. высказывание истинно, когда A ложно, и ложно, когда A истинно. Пример. "Луна – спутник Земли" (А); "Луна – не спутник Земли" ( ). В программировании операцию отрицания обозначают "NOT" (от английского "не").

2. КОНЪЮНКЦИЯ (логическое "И", логическое умножение). Операция,

выражаемая связкой "и", называется конъюнкцией (лат. conjunctio – соединение) или логическим умножением и обозначается точкой " . " (может также обозначаться знаками , & или *). Запись А ^ В читается как "А и В". Высказывание А . В истинно тогда и только тогда, когда оба высказывания А и В истинны. Например, высказывание "10 делится на 2 и 5 больше 3" истинно, а

высказывания "10 делится на 2 и 5 не больше 3", "10 не делится на 2 и 5 больше

3", "10 не делится на 2 и 5 не больше 3" – ложны. В программировании эту операцию обозначают "AND" (от английского "И").

Страница 7 из 47

3. ДИЗЪЮНКЦИЯ (логическое "ИЛИ", логическое сложение).

Операция, выражаемая связкой "или" (в неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio – разделение) или логическим сложением и обозначается знаком (или +). Дизъюнкция двух высказываний А и В соответствует союзу "ИЛИ". Запись А В читается как "А или В".

Высказывание А В ложно тогда и только тогда, когда оба высказывания А и В ложны. Например, высказывание "10 не делится на 2 или 5 не больше 3"

ложно, а высказывания "10 делится на 2 или 5 больше 3", "10 делится на 2 или 5 не больше 3", "10 не делится на 2 или 5 больше 3" – истинны. В

программировании эту операцию обозначают "OR" (от английского "ИЛИ").

4.ИМПЛИКАЦИЯ (логическое "если ..., то ..."). Операция, выражаемая связками "если ..., то", "из ... следует", "... влечет ...", называется

импликацией (лат. implico – тесно связаны) и обозначается знаком . Запись

А→ В читается как "из А следует В". Импликация двух высказываний истинна всегда, кроме случая, если первое высказывание истинно, а второе ложно, т.е. высказывание ложно тогда и только тогда, когда А истинно, а В ложно. Пример: пусть высказывание А = "Завтра будет хорошая погода", а высказывание В = "Я выйду на прогулку", тогда импликация А → В есть суждение: Х = "Если завтра будет хорошая погода, то я выйду на прогулку". В

программировании эту операцию обозначают "IMP".

5.ЭКВИВАЛЕНТНОСТЬ (логическое "тогда и только тогда").

Операция, выражаемая связками "тогда и только тогда", "необходимо и достаточно", "... равносильно ...", называется эквивалентностью или двойной импликацией и обозначается знаками , ≡ или ~ . Эквивалентность – это

функция тождества. Запись читается как "А эквивалентно В". Эквивалентность двух высказываний истинна только в тех случаях, когда оба высказывания ложны или оба истинны, т.е. высказывание истинно тогда и только тогда, когда значения А и В совпадают. Например,

высказывания "24 делится на 6 тогда и только тогда, когда 24 делится на 3", "23 делится на 6 тогда и только тогда, когда 23 делится на 3" истинны, а

Страница 8 из 47