Логические операции над высказываниями. Значения истинности

Тема программы: Высказывания и операции над ними.

Цели урока:

1) Обобщить теоретические знания по теме: «Высказывания и операции над ними».

2) Рассмотреть алгоритмы решений заданий теме «Высказывания и операции над ними», решить задачи.

3) Формировать умение прогнозировать собственную деятельность, умение организовать свою деятельность и анализировать ее.

Время выполнения: 1 час.

Теоретические основы

Основным понятием математической логики является понятие «простого высказывания». Под высказыванием обычно понимают всякое повествовательное предложение, утверждающее что-либо о чем-либо, и при этом мы можем сказать, истинно оно или ложно в данных условиях места и времени. Логическими значениями высказываний являются «истина» и «ложь».

Примеры высказываний.
1) Москва стоит на Неве.
2) Лондон - столица Англии.
3) Сокол не рыба.
4) Число 6 делится на 2 и на 3.
Высказывания 2), 3), 4) истинны, а высказывание 1) ложно.
Очевидно, предложение «Да здравствует Россия!» не является высказыванием.
Различают два вида высказываний.
Высказывание, представляющее собой одно утверждение, принято называть простым или элементарным. Примерами элементарных высказываний могут служить высказывания 1) и 2).
Высказывания, которые получаются из элементарных с помощью грамматических связок «не», «и», «или», «если.... то...», «тогда и только тогда», принято называть сложными или составными.
Так, высказывание 3) получается из простого высказывания «Сокол - рыба» с помощью отрицания «не», высказывание 4) образовано из элементарных высказываний «Число 6 делится на 2», «Число 6 делится на З», соединенных союзом «и».
Аналогично сложные высказывания могут быть получены из простых высказываний с помощью грамматических связок «или», «тогда и только тогда».
В алгебре логики все высказывания рассматриваются только с точки зрения их логического значения, а от их житейского содержания отвлекаются. Считается, что каждое высказывание либо истинно, либо ложно и ни одно высказывание не может быть одновременно истинным и ложным.
Элементарные высказывания обозначаются малыми буквами латинского алфавита: х, у, z, ..., а, b, с, ...; истинное значение высказывания цифрой 1, а ложное значение - буквой цифрой 0.
Если высказывание а истинно, то будем писать а = 1 , а если а ложно, то а = 0 .

Логические операции над высказываниями

Отрицание.

Отрицанием высказывания х называется новое высказывание , которое является истинным, если высказывание х ложно, и ложным, если высказывание х истинно.

Отрицание высказывания х обозначается и читается «не х» или «неверно, что х» .

Логические значения высказывания можно описать с помощью таблицы.

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

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

Конъюнкция.

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

Например, для высказываний «6 делится на 2», «6 делится на 3» их конъюнкцией будет высказывание «6 делится на 2 и 6 делится на 3», которое, очевидно, истинно.

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

Дизъюнкция

Дизъюнкцией (логическим сложением) двух высказываний х и у называется новое высказывание, которое считается истинным, если хотя бы одно из высказываний х, у истинно, и ложным, если они оба ложны. Дизъюнкция высказываний х, у обозначается символом «x V у» , читается «х или у» . Высказывания х, у называются членами дизъюнкции.
Логические значения дизъюнкции описываются следующей таблицей истинности:

В повседневной речи союз «или» употребляется в различном смысле: исключающем и не исключающем. В алгебре логики союз «или» всегда употребляется в не исключающем смысле.

Импликация.

Импликацией двух высказываний х и у называется новое высказывание, которое считается ложным, если х истинно, а у - ложно, и истинным во всех остальных случаях.
Импликация высказываний х, у обозначается символом , читается«если х, то у» или «из х следует у». Высказывание х называют условием или посылкой, высказывание у - следствием или заключением, высказывание следованием или импликацией.

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

Употребление слов «если.... то...» в алгебре логики отличается от употребления их в обыденной речи, где мы, как правило, считаем, что, если высказывание х ложно, то высказывание «Если х, то у» вообще не имеет смысла. Кроме того, строя предложение вида «если х, то у» в обыденной речи, мы всегда подразумеваем, что предложение у вытекает из предложения х . Употребление слов «если..., то...» в математической логике не требует этого, поскольку в ней смысл высказываний не рассматривается.
Импликация играет важную роль в математических доказательствах, так как многие теоремы формулируются в условной форме «Если х, то у». Если при этом известно, что х истинно и доказана истинность импликации , то мы вправе сделать вывод об истинности заключения у .

Эквивалентность.

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

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

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

Практические задания

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

• Если металл нагревается, он плавится.
• Неправда, что философские споры неразрешимы.
• Деньги - продукт стихийного развития товарных отношений, а не результат договоренности или какого-либо иного сознательного акта.

2. Записать логической формулой следующие высказывания:

а) если на улице дождь, то нужно взять с собой зонт или остаться дома;

Б) если - прямоугольный и стороны - равны, то

3. Проверить истинность высказывания:

а) , если, .

б) , если, .

в) , если, .

4. Проверить истинность высказывания:

а) Чтобы завтра пойти на занятия, я должен встать рано. Если я сегодня пойду в кино, то лягу спать поздно. Если я лягу спать поздно, то встану поздно. Следовательно, либо я не пойду в кино, либо не пойду на занятия.

б) Я пойду либо в кино, либо в бассейн. Если я пойду в кино, то получу эстетическое удовольствие. Если я пойду в бассейн, то получу физическое удовольствие. Следовательно, если я получу физическое удовольствие, то не получу эстетического удовольствия.

5 . На вопрос: «Кто из трех студентов изучал дискретную математику?» получен верный ответ: «Если изучал первый, то изучал и третий, но неверно, что если изучал второй, то изучал и третий». Кто изучал дискретную математику?

6. Определите, кто из четырех студентов сдал экзамен, если известно:

если первый сдал, то и второй сдал;

если второй сдал, то третий сдал или первый не сдал;

если четвертый не сдал, то первый сдал, а третий не сдал;

если четвертый сдал, то и первый сдал.

Контрольные вопросы

1. Какие элементы входят язык логики?

2. Какие способы установления общезначимости формулы логики вы знаете?

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

Практические занятия № 10-11

Тема программы: Формулы алгебры высказываний.

Понятие «высказывание» первично. Под высказыванием в логике понимают повествовательное предложение, о котором можно говорить, что оно истинно или ложно. Любое высказывание либо истинно, либо ложно, и никакое высказывание не является одновременно истинным и ложным.

Примеры высказываний: есть четное число», «1 есть простое число». Истинностное значение первых двух высказываний - «истина», истинностное значение последних двух

Вопросительные и восклицательные предложения не являются высказываниями. Определения не являются высказываниями. Например, определение «целое число называется четным, если оно делится на 2» не является высказыванием. Однако повествовательное предложение «если целое число делится на 2, то оно четное» есть высказывание, и притом истинное. В логике высказываний отвлекаются от смыслового содержания высказывания, ограничиваясь рассмотрением его с той позиции, что оно либо истинно, либо ложно.

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

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

Логические операции над высказываниями.

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

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

Пример. Высказывание «неверно, что 5 - четное число», имеющее значение И, есть отрицание ложного высказывания «5 - четное число».

С помощью операции конъюнкции из двух высказываний получается одно сложное высказывание, обозначаемое А Д В. По определению, высказывание А Д В истинно тогда и только тогда, когда оба высказывания истинны. Высказывания А и В называются соответственно первым и вторым членами конъюнкции А Д В. Запись «А Д В» читается как «Л и В». Истинностная таблица для конъюнкции имеет вид

Пример. Высказывание «7 - простое число и 6 - нечетное число» ложно, как конъюнкция двух высказываний, одно из которых ложно.

Дизъюнкцией двух высказываний А и В называется высказывание, обозначаемое , истинное в том и только в том случае, когда хотя бы одно из высказываний А и В истинно.

Соответственно этому высказывание А V В ложно в том и только том случае, когда и А и В оба ложны. Высказывания А и В называются соответственно первым и вторым членами дизъюнкции А V В. Читается запись А V В как «A или В». Союз «или» в данном случае носит неразделительный смысл, поскольку высказывание А V В истинно и при истинности обоих членов. Дизъюнкция имеет следующую истинностную таблицу:

Пример. Высказывание «3 Высказывание, обозначаемое , ложное в том и только в том случае, когда А истинно, а В ложно, называется импликацией с посылкой А и заключением В. Высказывание А-+ В читается как «если А, то 5», или «A влечет В», или «из A следует В». Истинностная таблица для импликации такова:

Отметим, что между посылкой и заключением могут отсутствовать причинно-следственные связи, но это не может повлиять на истинность или ложность импликации. Например, высказывание «если 5 - простое число, то биссектриса равностороннего треугольника является медианой» будет истинным, хотя в обычном понимании второе не следует из первого. Истинным также будет высказывание «если 2 + 2 = 5, то 6 + 3 = 9», поскольку истинно его заключение. При данном определении, если заключение истинно, импликация будет истинной независимо от истинностного значения посылки. В том случае, когда ложна посылка, импликация будет истинна независимо от истинностного значения заключения. Эти обстоятельства кратко формулируют так: «истина следует из чего угодно», «из ложного следует все, что угодно».

Среди возможных значений истинности лингвистической переменной Истинность два значения привлекают особое внимание, а именно пустое множество и единичный интервал , которые соответствуют наименьшему и наибольшему элементам (по отношению включения) решетки нечетких подмножеств интервала . Важность именно этих значений истинности обусловлена тем, что их можно интерпретировать как значения истинности не определено и неизвестно соответственно. Для удобства будем обозначать эти значения истинности символами и , понимая при этом, что и определяются выражениями

Значения неизвестно и не определено , интерпретируемые как степени принадлежности, используются также в представлении нечетких множеств типа 1. В этом случае имеются три возможности выражения степени принадлежности точки в : 1) число из интервала ; 2) (не определено ); 3) (неизвестно ).

Рассмотрим простой пример. Пусть

Возьмем нечеткое подмножество множества вида

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

где имеется в виду, что степень принадлежности элемента множеству частично неизвестна, причем член интерпретируется следующим образом:

. (6.56)

Важно четко понимать разницу между и . Когда мы говорим, что степень принадлежности точки множеству есть , мы имеем в виду, что функция принадлежности не определена в точке . Предположим, например, что - множество действительных чисел, а - функция, определенная на множестве целых чисел, причем , если - четное, и , если - нечетное. Тогда степень принадлежности числа множеству есть , а не 0. С другой стороны, если бы была определена на множестве действительных чисел и тогда и только тогда, когда - четное число, то степень принадлежности числа множеству была бы равна 0.

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

, (6.57)

. (6.58)

Применяя принцип обобщения, как в (6.25), получим

, (6.59)

После упрощения (6.59) сводится к выражению

. (6.61)

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

Рис. 6.4. Конъюнкция и дизъюнкция значений истинности высказывания со значением истинности неизвестно ().

Аналогично находим, что значение истинности высказывания или выражается в виде

. (6.62)

Следует отметить, что выражения (6.61) и (6.62) легко получить с помощью описанной выше графической процедуры (см. (6.38) и далее). Пример, иллюстрирующий это, показан на рис. 6.4.

Обращаясь к случаю , находим

(6.63)

и аналогично для .

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

или в более привычном виде

где означает истинный , а - ложный . Поскольку есть , мы можем отождествить значение истинности неизвестно со значением истинный или ложный , т. е.

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

Поскольку универсальное множество значений истинности состоит лишь из двух элементов, целесообразно построить таблицы истинности для операций , и в этой четырехзначной логике непосредственно, т. е. без использования общих формул (6.25), (6.29) и (6.31). Так, применяя принцип обобщения к операции , сразу получаем

откуда с необходимостью следует, что

На этом пути мы приходим к обычному определению связки ⟹ в двузначной логике в виде следующей таблицы истинности:

Как показывает рассмотренный выше пример, понятие значения истинности неизвестно в сочетании с принципом обобщения помогает уяснить некоторые из понятий и соотношений обычных двузначной и трехзначной логик. Эти логики, конечно, можно рассматривать как вырожденные случаи нечеткой логики, в которой значением истинности неизвестно является весь единичный интервал, а не множество 0 + 1.

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

Высказыванием называется любое повествовательное предложение, которое может быть либо истинным, либо ложным.

Пример . Следующие предложения являются высказываниями:

1) Все студенты МГПУ – отличники (ложное высказывание),

2) На Кольском полуострове водятся крокодилы (ложное высказывание),

3) Диагонали прямоугольника равны (истинное высказывание),

4) Уравнение не имеет действительных корней (истинное высказывание),

5) Число 21 – четное (ложное высказывание).

Следующие предложения не являются высказываниями:

Какая погода будет завтра?

х – натуральное число,

745 + 231 – 64.

Высказывания принято обозначать большими буквами латинского алфавита: А, В, С,…, Z .

«Истина» и «ложь» называются значениями истинности высказывания . Каждое высказывание либо истинно, либо ложно, одновременно быть и тем, и другим, оно не может.

Запись [ А ] = 1 означает, что высказываниеА – истинно .

А запись [ А ] = 0 означает, что высказываниеА – ложно .

Предложение
не является высказыванием, так как о нем невозможно сказать: истинно оно или ложно. При подстановке конкретных значений переменнойх оно обращается в высказывание: истинное или ложное.

Пример . Если
, то
– ложное высказывание, а если
, то
– истинное высказывание.

Предложение
называетсяпредикатом или высказывательной формой . Оно порождает множество высказываний одной и той же формы.

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

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

Пример . 1)
– одноместный предикат,

2) «Прямая х перпендикулярна прямой у » – двухместный предикат.

Также в предикатах переменные могут содержаться неявно. В предложениях: «Число четное», «две прямые пересекаются» переменных нет, но они подразумеваются: «Число х – четное», «две прямые х и у пересекаются».

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

Пример . Неравенство
можно рассматривать на множестве натуральных чисел, а можно считать, что значение переменной выбирается из множества действительных чисел. В первом случае областью определения неравенства
будет множество натуральных чисел, а во втором – множество действительных чисел.

Одноместным предикатом , заданным на множестве Х , называется предложение с переменной, которое обращается в высказывание при подстановке в него переменной из множества Х .

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

Пример . Множеством истинности предиката
, заданном на множестве действительных чисел, будет промежуток
. Множество истинности предиката
, заданном на множестве целых неотрицательных чисел, состоит из одного числа 2.

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

Пример . Пара
принадлежит множеству истинности предиката
, т.к.
– истинное высказывание, а пара
не принадлежит, т.к.
– ложное высказывание.

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

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

Число 42 – четное и делится на 7. Образовано из двух элементарных предложений: Число 42 четное, число 42 делится на 7 и составлено с помощью логической связки «и ».

Число х больше или равно 5. Образовано из двух элементарных предложений: Число х больше 5 и число х равно 5 и составлено с помощью логической связки «или ».

Число 42 не делится на 5. Образовано из предложения: Число 42 делится на 5 с помощью частицы «не ».

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

Пример . Выявим логическую структуру предложения: «Если углы вертикальны, то они равны». Оно состоит из двух элементарных предложений: А – углы вертикальные, В – углы равны. Соединены они в одно составное предложение с помощью логической связки «если…, то… ». Данное составное предложение имеет логическую структуру (форму): «если А, то В ».

Выражение «для любого х » или «для всех х » или «для каждого х » называется квантором общности и обозначается
.

при помощи квантора общности, обозначается:
и читается: «Для любого значениях из множества Х имеет место
».

Выражение «существует х » или «для некоторых х » или «найдется такое х » называется квантором существования и обозначается
.

Высказывание, полученное из высказывания или предиката
при помощи квантора существования, обозначается:
и читается: «Для некоторыхх из множества Х имеет место
» или «Существует (найдется) такое значениех из Х , что имеет место
».

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

Пример . Следующие высказывания содержат квантор общности:

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

Следующие высказывания содержат квантор существования:

а) Существуют числа, кратные 5; б) Найдется такое натуральное число , что
; в) В некоторых студенческих группах учатся кандидаты в мастера спорта; г) Хотя бы один угол в треугольнике острый.

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

Пример . Высказывание
истинно.

Высказывание
ложно , если при некотором значении переменной х предикат

Пример . Высказывание
ложно, т.к. при
предикат
превращается в ложное высказывание.

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

Пример . Высказывание
истинно, т.к. при
предикат
превращается в истинное высказывание.

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

Пример . Высказывание
ложно, т.к. предикат
является тождественно ложным.

Пусть предложение А – высказывание. Если перед сказуемым данно­го предложения поставить частицу «не » либо перед всем предложением поставить слова «неверно, что », то получится новое предложение, кото­рое называется отрицанием данного и обозначается:  А или (читают: «не А» или «неверно, что А »).

Пример . Если высказывание А : «Вертикальные углы равны», то отрицание этого высказывания  А : «Вертикальные углы не равны». Первое из этих высказываний истинное, а второе – ложное.

Для построения отрицания высказываний с кванторами надо:

квантор общности заменить квантором существования или наоборот;

высказывание заменить его отрицанием (поставить перед глаголом частицу «не »).

На языке математических символов это запишется так.

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

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

Рисунок сверху - иллюстрация явления, известного как "Парадокс лжеца". При этом, на взгляд автора проекта, такие парадоксы возможны только в средах, несвободных от политических заморочек, где на ком-то могут априори поставить клеймо лжеца. В естественном многослойном мире на предмет "истины" или "лжи" оцениваются только отдельно взятые высказывания . И далее на этом уроке вам представится возможность самим оценить на этот предмет немало высказываний (а затем посмотреть правильные ответы). В том числе сложных высказываний, в которых более простые связаны между собой знаками логических операций. Но прежде рассмотрим сами эти операции над высказываниями.

Логика высказываний применяется в информатике и программировании в виде объявления логических переменных и присвоения им логических значений "ложь" или "истина", от которых зависит ход дальнейшего исполнения программы. В небольших программах, где задействована лишь одна логическая переменная, этой логической переменной часто даётся имя, например, "флаг" ("flag") и подразумевается, что "флаг поднят", когда значение этой переменной - "истина" и "флаг опущен", когда значение этой переменной - "ложь". В программах большого объёма, в которых несколько или даже очень много логических переменных, от профессионалов требуется придумывать имена логических переменных, имеющих форму высказываний и смысловую нагрузку, отличающую их от других логических переменных и понятных другим профессионалам, которые будут читать текст этой программы.

Так, может быть объявлена логическая переменная с именем "ПользовательЗарегистрирован" (или его англоязычный аналог), имеющая форму высказывания, которой может быть присвоено логическое значение "истина" при выполнении условий, что данные для регистрации отправлены пользователем и эти данные программой признаны годными. В дальнейших вычислениях значения переменных могут меняться в зависимости от того, какое логическое значение ("истина" или "ложь") имеет переменная "ПользовательЗарегистрирован". В других случах переменной, например, с именем "ДоДняХОсталосьБолееТрёхДней", может быть присвоено значение "Истина" до некоторого блока вычислений, а в ходе дальнейшего исполнения программы это значение может сохраняться или меняться на "ложь" и от значения этой переменной зависит ход дальнейшего исполнения программы.

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

Логические операции над высказываниями

Для математических высказываний всегда можно сделать выбор между двумя различными альтернативами "истина" и "ложь", а для высказываний, сделанных на "словесном" языке, понятия "истинности" и "ложности" несколько более расплывчаты. Однако, например, такие словесные формы, как "Иди домой" и "Идёт ли дождь?", не являются высказываниями. Поэтому понятно, что высказываниями являются такие словесные формы, в которых что-либо утверждается . Не являются высказываниями вопросительные или восклицательные предложения, обращения, а также пожелания или требования. Их невозможно оценить значениями "истина" и "ложь".

Высказывания же, напротив, можно рассмотривать как величину, которая может принимать два значения: "истина" и "ложь".

Например, даны суждения: "собака - животное", "Париж - столица Италии", "3

Первое из этих высказываний может быть оценено символом "истина", второе - "ложь", третье - "истина" и четвёртое - "ложь". Такая трактовка высказываний составляет предмет алгебры высказываний. Будем обозначать высказывания большими латинскими буквами A , B , ..., а их значения, то есть истину и ложь, соответственно И и Л . В обычной речи употребляются связи между высказываниями "и", "или" и другие.

Эти связи позволяют, соединяя между собой различные высказывания, образовывать новые высказывания - сложные высказывания . Например, связка "и". Пусть даны высказывания: "π больше 3" и высказывание "π меньше 4". Можно организовывать новое - сложное высказывание "π больше 3 и π меньше 4". Высказывание "если π иррационально, то π ² тоже иррационально" получается связыванием двух высказываний связкой "если - то". Наконец, мы можем получить из какого-либо высказывания новое - сложное высказывание - отрицая первоначальное высказывание.

Рассматривая высказывания как величины, принимающие значения И и Л , мы определим далее логические операции над высказываниями , которые позволяют из данных высказываний получать новые - сложные высказывания.

Пусть даны два произвольных высказывания A и B .

1 . Первая логическая операция над этими высказываниями - конъюнкция - представляет собой образование нового высказывания, которое будем обозначать A ∧ B и которое истинно тогда и только тогда, когда A и B истинны. В обычной речи этой операции соответствует соединение высказываний связкой "и".

Таблица истинности для конъюнкции:

2 . Вторая логическая операция над высказываниями A и B - дизъюнкция, выражаемая в виде A ∨ B , определяется следующим образом: оно истинно тогда и только тогда, когда хотя бы одно из первоначальных высказываний истинно. В обычной речи эта операция соответствует соединению высказываний связкой "или". Однако здесь мы имеем не разделительное "или", которое понимается в смысле "либо-либо", когда A и B не могут быть оба истинны. В определении логики высказываний A ∨ B истинно и при истинности лишь одного из высказываний, и при истинности обоих высказываний A и B .

Таблица истинности для дизъюнкции:

3 . Третья логическая операция над высказываниями A и B , выражаемая в виде A → B ; полученное таким образом высказывание ложно тогда и только тогда, когда A истинно, а B ложно. A называется посылкой , B - следствием , а высказывание A → B - следованием , называемая также импликацией. В обычной речи эта операция соответствует связке "если - то": "если A , то B ". Но в определении логики высказываний это высказывание всегда истинно независимо от того, истинно или ложно высказывание B . Это обстоятельство можно кратко сформулировать так: "из ложного следует всё, что угодно". В свою очередь, если A истинно, а B ложно, то всё высказывание A → B ложно. Оно будет истинным тогда и только тогда, когда и A , и B истинны. Кратко это можно сформулировать так: "из истинного не может следовать ложное".

Таблица истинности для следования (импликации):

4 . Четвёртая логическая операция над высказываниями, точнее над одним высказыванием, называется отрицанием высказывания A и обозначается ~ A (можно встретить также употребление не символа ~, а символа ¬, а также верхнего надчёркивания над A ). ~ A есть высказывание, которое ложно, когда A истинно, и истинно, когда A ложно.

Таблица истинности для отрицания:

5 . И, наконец, пятая логическая операция над высказываниями называется эквивалентностью и обозначается A ↔ B . Полученное таким образом высказывание A ↔ B есть высказывание истинное тогда и только тогда, когда A и B оба истинны или оба ложны.

Таблица истинности для эквивалентности:

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

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

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

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

Пример 1.

1) (2 = 2) И (7 = 7) ;

2) Не(15 ;

3) ("Сосна" = "Дуб") ИЛИ ("Вишня" = "Клён") ;

4) Не("Сосна" = "Дуб") ;

5) (Не(15 20) ;

6) ("Глаза даны, чтобы видеть") И ("Под третьим этажом находится второй этаж") ;

7) (6/2 = 3) ИЛИ (7*5 = 20) .

1) Значение высказывания в первых скобках равно "истина", значение выражения во вторых скобках - также истина. Оба высказывания соединены логической операцией "И" (смотрим правила для этой операции выше), поэтому логическое значение всего данного высказывания - "истина".

2) Значение высказывания в скобках - "ложь". Перед этим зтим высказыванием стоит логическая операция отрицания, поэтому логическое значение всего данного высказывания - "истина".

3) Значение высказывания в первых скобках - "ложь", значение высказывания во вторых скобках - также "ложь". Высказывания соединены логической операцией "ИЛИ" и ни одно из высказываний не имеет значения "истина". Поэтому логическое значение всего данного высказывания - "ложь".

4) Значение высказывания в скобках - "ложь". Перед этим высказыванием стоит логическая операция отрицания. Поэтому логическое значение всего данного высказывания - "истина".

5) В первых скобках отрицается высказывание во внутренних скобках. Это высказывание во внутренних скобках имеет значение "ложь", следовательно, его отрицание будет иметь логическое значение "истина". Высказывание во вторых скобках имеет значение "ложь". Два этих высказывания соединены логической операцией "И", то есть получается "истина И ложь". Следовательно, логическое значение всего данного высказывания - "ложь".

6) Значение высказывания в первых скобках - "истина", значение высказывания во вторых скобках - также "истина". Два этих высказывания соединены логической операцией "И", то есть получается "истина И истина". Следовательно, логическое значение всего данного высказывания - "истина".

7) Значение высказывания в первых скобках - "истина". Значение высказывания во вторых скобках - "ложь". Два этих высказывания соединены логической операцией "ИЛИ", то есть получается "истина ИЛИ ложь". Следовательно, логическое значение всего данного высказывания - "истина".

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

1) "Пользователь не зарегистрирован";

2) "Сегодня воскресенье и некоторые сотрудники находятся на работе";

3) "Пользователь зарегистрирован тогда и только тогда, когда отправленные пользователем данные признаны годными".

1) p - одиночное высказывание "Пользователь зарегистрирован", логическая операция: ;

2) p - одиночное высказывание "Сегодня воскресенье", q - "Некоторые сотрудники находятся на работе", логическая операция: ;

3) p - одиночное высказывание "Пользователь зарегистрирован", q - "Отправленные пользователем данные признаны годными", логическая операция: .

Решить примеры на логику высказываний самостоятельно, а затем посмотреть решения

Пример 3. Вычислите логические значения следующих высказываний:

1) ("В минуте 70 секунд") ИЛИ ("Работающие часы показывают время") ;

2) (28 > 7) И (300/5 = 60) ;

3) ("Телевизор - электрический прибор") И ("Стекло - дерево") ;

4) Не((300 > 100) ИЛИ ("Жажду можно утолить водой")) ;

5) (75 < 81) → (88 = 88) .

Пример 4. Запишите с помощью логических операций следующие сложные высказывания и вычислите их логические значения:

1) "Если часы неправильно показывают время, то можно невовремя прийти на занятия";

2) "В зеркале можно увидеть своё отражение и Париж - столица США";

Пример 5. Определите логическое значение выражения

(p → q ) ↔ (r → s ) ,

p = "278 > 5" ,

q = "Яблоко = Апельсин" ,

p = "0 = 9" ,

s = "Шапка покрывает голову" .

Формулы логики высказываний

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

В примерах 1 и 2 мы учились записывать с помощью логических операций сложные высказывания. Вообще-то они называются формулами логики высказываний.

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

p , q , r , ..., p 1 , q 1 , r 1 , ...

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

Для построения формул логики высказываний кроме указанных выше букв используются знаки логических операций

~, ∧, ∨, →, ↔,

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

Понятие формулы логики высказываний определим следуюшим образом:

1) элементарные формулы (атомы) являются формулами логики высказываний;

2) если A и B - формулы логики высказываний, то ~A , (A ∧ B ) , (A ∨ B ) , (A → B ) , (A ↔ B ) тоже являются формулами логики высказываний;

3) только те выражения являются формулами логики высказываний, для которых это следует из 1) и 2).

Определение формулы логики высказываний содержит перечисление правил образования этих формул. Согласно определению, всякая формула логики высказываний либо есть атом, либо образуется из атомов в результате последовательного применения правила 2).

Пример 6. Пусть p - одиночное высказывание (атом) "Все рациональные числа являются действительными", q - "Некоторые действительные числа - рациональные числа", r - "некоторые рациональные числа являются действительными". Переведите в форму словесных высказываний следующие формулы логики высказываний:

6) .

1) "нет действительных чисел, которые являются рациональными";

2) "если не все рациональные числа являются действительными, то нет рациональных чисел, являющихся действительными";

3) "если все рациональные числа являются действительными, то некоторые действительные числа - рациональные числа и некоторые рациональные числа являются действительными";

4) "все действительные числа - рациональные числа и некоторые действительные числа - рациональные числа и некоторые рациональные числа являются действительными числами";

5) "все рациональные числа являются действительными тогда и только тогда, когда не имеет место быть, что не все рациональные числа являются действительными";

6) "не имеет места быть, что не имеет место быть, что не все рациональные числа являются действительными и нет действительных чисел, которые являются рациональными или нет рациональных чисел, которые являются действительными".

Пример 7. Составьте таблицу истинности для формулы логики высказываний , которую в таблице можно обозначить f .

Решение. Составление таблицы истинности начинаем с записи значений ("истина" или "ложь") для одиночных высказываний (атомов) p , q и r . Все возможные значения записываются в восемь строк таблицы. Далее, определяя значения операции импликации, и продвигаясь вправо по таблице, помним, что значение равно "лжи" тогда, когда из "истины" следует "ложь".

Заметим, что никакой атом не имеет вида ~A , (A ∧ B ) , (A ∨ B ) , (A → B ) , (A ↔ B ) . Такой вид имеют сложные формулы.

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

1) в сложной формуле будем опускать внешнюю пару скобок;

2) упорядочим знаки логических операций "по старшинству":

↔, →, ∨, ∧, ~ .

В этом списке знак ↔ имеет самую большую область действия, а знак ~ - самую маленькую. Под областью действия знака операции понимаются те части формулы логики высказываний, к которым применяется (на которые действует) рассматриваемое вхождение этого знака. Таким образом, можно опускать во всякой формуле те пары скобок, которые можно восстановить, учитывая "порядок старшинства". А при восстановлении скобок сначала расставляются все скобки, относящиеся ко всем вхождениям знака ~ (при этом мы продвигаемся слева направо), затем ко всем вхождениям знака ∧ и так далее.

Пример 8. Восстановите скобки в формуле логики высказываний B ↔ ~ C ∨ D ∧ A .

Решение. Скобки восстанавливаются пошагово следующим образом:

B ↔ (~ C ) ∨ D ∧ A

B ↔ (~ C ) ∨ (D ∧ A )

B ↔ ((~ C ) ∨ (D ∧ A ))

(B ↔ ((~ C ) ∨ (D ∧ A )))

Не всякая формула логики высказываний может быть записана без скобок. Например, в формулах А → (B → C ) и ~ (A → B ) дальнейшее исключение скобок невозможно.

Тавтологии и противоречия

Логические тавтологии (или просто тавтологии) - это такие формулы логики высказываний, что если буквы произвольным образом заменить высказываниями (истинными или ложными), то в результате всегда получится истинное высказывание.

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

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

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

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

Кроме тавтологий и логических противоречий существуют такие формулы логики высказываний, которые не являются ни тавтологиями, ни противоречиями.

Пример 9. Составьте таблицу истинности для формулы логики высказываний и определите, является ли она тавтологией, противоречием или ни тем, ни другим.

Решение. Составляем таблицу истинности:

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