Что является высказыванием. Высказывание

Лабораторная работа № 7-8

Алгебра логики

Цель работы: Изучить основы алгебры логики.

Задачи лабораторной работы

В результате прохождения занятия студент должен:

      определения основных понятий (простое и сложное высказывания, логические операции, логические выражения, логическая функция);

      порядок выполнения логических операций;

      алгоритм построения таблиц истинности;

      схемы базовых логических элементов;

      законы логики и правила преобразования логических выражений;

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

      строить таблицы истинности;

      строить логические схемы сложных выражений.

Общие теоретические сведения

Основные понятия алгебры логики

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

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

Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

Пример. «3 – простое число» является высказыванием, поскольку оно истинно.

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

Пример. предложение «Давайте пойдем в кино» не является высказыванием. Вопросительные и побудительные предложения высказываниями не являются.

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

Пример. «x+2>5» - высказывательная форма, которая при x>3 является истинной, иначе ложной.

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

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

Пример. высказывание «Число 6 делится на 2» - простое высказывание. Высказывание «Число 6 делится на 2, и число 6 делится на 3» - составное высказывание, образованное из двух простых с помощью логической связки «и».

Истинность или ложность составных высказываний зависит от истинности или ложности элементарных высказываний, из которых они состоят.

Чтобы обращаться к логическим высказываниям, им назначают имена.

Пример. Обозначим через А простое высказывание «число 6 делится на 2», а через В простое высказывание «число 6 делится на 3». Тогда составное высказывание «Число 6 делится на 2, и число 6 делится на 3» можно записать как «А и В». Здесь «и» – логическая связка, А, В – логические переменные, которые могут принимать только два значения – «истина» или «ложь», обозначаемые, соответственно, «1» и «0».

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

Таблица 1. Основные логические операции

Обозначение операции

Читается

Название операции

Альтернативные обозначения

Отрицание (инверсия)

Черта сверху

Конъюнкция (логическое умножение)

Дизъюнкция (логическое сложение)

Если … то

Импликация

Тогда и только тогда

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

Либо …либо

Исключающее ИЛИ (сложение по модулю 2)

НЕ Операция, выражаемая словом «не», называется отрицанием и обозначается чертой над высказыванием (или знаком ¬). Высказывание ¬А истинно, когда A ложно, и ложно, когда A истинно.

Пример. Пусть А=«Сегодня пасмурно», тогда ¬А=«Сегодня не пасмурно».

И Операция, выражаемая связкой «и», называется конъюнкцией (лат. conjunctio – соединение) или логическим умножением и обозначается точкой « » (может также обозначаться знаками или &). Высказывание А В истинно тогда и только тогда, когда оба высказывания А и В истинны.

Пример. Высказывание «Число 6 делится на 2, и число 6 делится на 3» - истинно, а высказывание «Число 6 делится на 2, и число 6 больше 10» - ложно.

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

Пример: Высказывание «Число 6 делится на 2 или число 6 больше 10» - истинно, а высказывание «Число 6 делится на 5 или число 6 больше 10» - ложно.

ЕСЛИ … ТО Операция, выражаемая связками «если …, то», «из … следует», «... влечет …», называется импликацией (лат. implico – тесно связаны) и обозначается знаком → или  . Высказывание А→В ложно тогда и только тогда, когда А истинно, а В ложно.

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

РАВНОСИЛЬНО Операция, выражаемая связками «тогда и только тогда», «необходимо и достаточно», «... равносильно …», называется эквиваленцией или двойной импликацией и обозначается знаком ↔ или ~ или . Высказывание А↔В истинно тогда и только тогда, когда значения А и В совпадают.

Пример: Высказывание «Число является четным тогда и только тогда, когда оно делится без остатка на 2» является истинным, а высказывание «Число является нечетным тогда и только тогда, когда оно делится без остатка на 2» - ложно.

ЛИБО … ЛИБО Операция, выражаемая связками «Либо … либо», называется исключающее ИЛИ или сложением по модулю 2 и обозначается XOR или . Высказывание АВ истинно тогда и только тогда, когда значения А и В не совпадают.

Пример. Высказывание «Число 6 либо нечетно либо делится без остатка на 2» является истинным, а высказывание «Либо число 6 четно либо число 6 делится на 3» – ложно, так как истинны оба высказывания входящие в него.

Замечание. Импликацию можно выразить через дизъюнкцию и отрицание:

Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:

Исключающее ИЛИ можно выразить через отрицание, дизъюнкцию и конъюнкцию:

Вывод. Операций отрицания, дизъюнкции и конъюнкции достаточно, чтобы описывать и обрабатывать логические высказывания.

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

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

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

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

Пример . – логическая функция двух переменных A и B.

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

Приведем таблицу истинности основных логических операций (табл. 2)

Таблица 2

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

Алгоритм построения таблиц истинности для сложных выражений:

    количество строк = 2 n + строка для заголовка,

    n - количество простых высказываний.

    количество столбцов = количество переменных + количество логических операций;

    определить количество переменных (простых выражений);

    определить количество логических операций и последовательность их выполнения.

Пример 1. Составить таблицу истинности для формулы И–НЕ, которую можно записать так:.

1. Определить количество строк:

На входе два простых высказывания: А и В, поэтому n=2 и количество строк =2 2 +1=5.

2. Определить количество столбцов:

Выражение состоит из двух простых выражений (A и B) и двух логических операций (1 инверсия, 1 конъюнкция), т.е. количество столбцов таблицы истинности = 4.

3. Заполнить столбцы с учетом таблиц истинности логических операций (табл. 3).

Таблица 3. Таблица истинности для логической операции

Подобным образом можно составить таблицу истинности для формулы ИЛИ–НЕ, которую можно записать так:

Таблица 4. Таблица истинности для логической операции

Примечание: И–НЕ называют также «штрих Шеффера» (обозначают |)

или «антиконъюнкция» ; ИЛИ–НЕ называют также «стрелка Пирса» (обозначают ↓) или «антидизъюнкция» .

Пример 2. Составить таблицу истинности логического выражения .

Решение:

1. Определить количество строк:

На входе два простых высказывания: А и В, поэтому n=2 и количество строк=2 2 +1= 5.

2. Определить количество столбцов:

Выражение состоит из двух простых выражений (A и B) и пяти логических операций (2 инверсии, 2 конъюнкции, 1 дизъюнкция), т.е. количество столбцов таблицы истинности = 7.

Сначала выполняются операции инверсии, затем конъюнкции, в последнюю очередь операция дизъюнкции.

3. Заполнить столбцы с учетом таблиц истинности логических операций (табл. 5).

Таблица 5. Таблица истинности для логической операции

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

Существует три базовых логических элемента, которые реализуют три основные логические операции:

    логический элемент «И» – логическое умножение – конъюнктор;

    логический элемент «ИЛИ» – логическое сложение – дизъюнктор;

    логический элемент «НЕ» – инверсию – инвертор.

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

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

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

Алгоритм построения логических схем.

    Определить число логических переменных.

    Определить количество логических операций и их порядок.

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

    Соединить логические элементы в порядке выполнения логических операций.

Пример. По заданной логической функции построить логическую схему.

Решение.

    Число логических переменных = 2 (A и B).

    Количество операций = 5 (2 инверсии, 2 конъюнкции, 1 дизъюнкция). Сначала выполняются операции инверсии, затем конъюнкции, в последнюю очередь операция дизъюнкции.

    Схема будет содержать 2 инвертора, 2 конъюнктора и 1 дизъюнктор.

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

Логические законы и правила преобразования логических выражений

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

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

1. Закон двойного отрицания: ;

2. Переместительный (коммутативный) закон:

3. Сочетательный (ассоциативный) закон:

4. Распределительный (дистрибутивный) закон:

5. Законы де Моргана:

6. Закон идемпотентности:

7. Законы исключения констант:

8. Закон противоречия:;

9. Закон исключения третьего: ;

10. Закон поглощения:

11. Правило исключения импликации: ;

12. Правило исключения эквиваленции: .

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

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

Пример. Упростить логическое выражение .

Решение:

Согласно закону де Моргана:

Согласно сочетательному закону:

Согласно закону противоречия и закону идемпотентности:

Согласно закону исключения 0:

Окончательно получаем

/ Задания к лабораторной работе

Пример 1. Установите, какие из следующих предложений являются логическими высказываниями, а какие - нет (объясните почему):

    а) “Солнце есть спутник Земли ”;

    б) “2+3 =4 ”;

    в) “сегодня отличная погода ”;

    г) “в романе Л.Н. Толстого “Война и мир” 3 432 536 слов ”;

    д) “Санкт-Петербург расположен на Неве ”;

    е) “музыка Баха слишком сложна ”;

    ж) “первая космическая скорость равна 7.8 км/сек ”;

    з) “железо - металл ”;

    и) “если один угол в треугольнике прямой, то треугольник будет тупоугольным ”;

    к) “если сумма квадратов двух сторон треугольника равна квадрату третьей, то он прямоугольный ”.

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

Пример 3. Приведите примеры истинных и ложных высказываний:

    а) из арифметики; б) из физики;

    в) из биологии; г) из информатики;

    д) из геометрии; е) из жизни.

Пример 4. Сформулируйте отрицания следующих высказываний или высказывательных форм:

    а) “Эльбрус - высочайшая горная вершина Европы”;

    б) “2>=5”;

    в) “10<7”;

    г) “все натуральные числа целые”;

    д) “через любые три точки на плоскости можно провести окружность”;

    е) “теннисист Кафельников не проиграл финальную игру”;

    ж) “мишень поражена первым выстрелом”;

    з) “это утро ясное и теплое”;

    и) “число n делится на 2 или на 3”;

    к) “этот треугольник равнобедренный и прямоугольный”;

    л) "на контрольной работе каждый ученик писал своей ручкой".

Мы будем знакомиться с самым элементарным разделом логики - алгеброй высказываний.

Исходные объекты алгебры высказываний - это простые (элементарные) высказывания. Мы в дальнейшем будем их обозначать строчными латинскими буквами а, b, с, ..., х, у, z .

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

1. "Число 21 делится на 3";

2. "Тринадцать меньше пяти";

3. "Число 201 больше 180 на 21"

4. 1 это единственный корнь уравнения x 2 - 1 = 0";

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

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

1. "Аристотель - грек";

2. "Число 0,00001 очень мало";

3. "x больше 3";

4. "2x + 3 =17";

5. "Существует ли рациональное число квадрат которого равен 2?"

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

1. "Число 30221 157 + 5342 345623 + 1 является простым числом";

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

Вообще, многие математические утверждения можно считать простыми высказываниями при этом принято считать, что они либо истинны, либо ложны, даже если нам неизвестно, каким из двух свойств данное высказывание обладает. Так, например, «Всякое четное число является суммой двух простых чисел» - высказывание, хотя мы не знаем, каким из двух свойств оно в действительности обладает: это нерешенная проблема Гольдбаха.

Когда речь идет о высказывании нужно иметь в виду следующее:

1. Любое высказывание является либо истинным, либо ложным (закон исключенного третьего).

2. Никакое высказывание не может быть одновременно истинным и ложным (закон противоречия).

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

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

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

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

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

1. Отрицание. Эту логическую связку мы будем обозначать a . Если а - высказывание, то а (читается: «не а») также высказывание; оно истинно или ложно в зависимости от того, ложно или истинно высказывание а.

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

Мы видим, что операция в теории высказываний вполне соответствует понятию отрицания в обыденном смысле слова. Если, например, а - высказывание «Число три делит число шесть», то отрицанием a этого высказывания будет «Число три не делит число шесть». Высказывание а при этом истинно, высказывание a - ложно. Если же в качестве высказывания а взять какое-нибудь ложное высказывание, например «Число три делит число пять», то его отрицание a будет высказывание «Число три не делит число пять» - истинное высказывание.

2. Конъюнкция. В качестве знака для конъюнкции мы будем
употреблять знак -&

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

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

Как видно, определение операции конъюнкции вполне соответствует обыденному значению союза «и».

3. Дизъюнкция. В качестве знака для дизъюнкции мы будем употреблять знак V

Если а и b - высказывания, то а V b (читается: «а или b») - новое высказывание, оно ложное, если а и b ложны; во всех остальных случаях а V b истинно.

Таким образом, таблица истинности для операции дизъюнкции выглядит так:

Операция дизъюнкции довольно хорошо соответствует обыденному значению союза «или». Детальный анализ показывает, что в русском языке слово «или» употребляется в двух различных значениях: существуют исключающее «или» и неисключающее «или». Различие состоит в следующей: пусть а и b - два истинных высказывания, например а - «Число три делит число шесть», b - «Число шесть большее чем число три». Следует ли рассматривать сложное высказывание а V b - «Число три делит число шесть или число шесть больше, чем число три» как истинное или как ложное? В обыденной русской речи встречаются оба понимания: утверждение «а или b» может означать, что одно и только одно из предложений а и b истинно, тогда говорят, что слово «или» употребляется в исключающем смысле, или же «а или b» означает, что истинно по меньшей мере одно из предложений (но могут быть истинны оба), в этом случае говорят, что «или» употребляется в неисключающем смысле. Именно неисключающему «или» и соответствует дизъюнкция. Исключающему «или» соответствует, очевидно, таблица истинности

А в неисключающем смысле:
«Три делит пять или три больше шести» ложно;
«Три делит шесть или три больше шести» истинно;
«Три делит шесть или три меньше шести» истинно.

3. Импликация. В качестве знака для импликации будем употреблять знак,

Если а и b - два высказывания, то аb (читается: «а имплицирует b») - новое высказывание; оно всегда истинно, кроме того случая, когда а истинно, a b ложно. Таблица истинности операции импликации следующая:

В импликации аb первый член а называется антецедентом, второй b - консеквентом. Операция описывает в некоторой мере то, что в обыденной речи выражается словами «Если а, то b», «Из а следует b», «a - достаточное условие для b», но на этой аналогии не следует слишком настаивать. Действительно, учитывая определение импликации, данное выше, и интерпретируя выражение аb как «если а, то b», мы получаем: «Если дважды два - четыре, то трижды три - девять» - истинное высказывание; «Если дважды два - пять, то трижды три - восемь» - истинное высказывание и только высказывание типа «Если дважды два - четыре, то трижды, три - восемь» ложно.

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

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

4. Эквиваленция. Для. этой операции мы будем употреблять знак . Операция эквиваленции определяется так: если а и b - два высказывания, то аÛ b (читается: «а эквивалентно b»; соответствует словесному выражению «...тогда и только тогда, когда...» - новое высказывание, которое истинно, если либо оба высказывания истинны, либо оба - ложны. b (читается: «а меньше или равно b) представляет собой дизъюнкцию (а < b)V(a = b) оно истинно, если истинно по меньшей мере одно из входящих в него простых высказываний. Хорошими примерами сложных высказываний, встречающихся в школьной практике, являются так называемые двойные неравенства. Так, формула а < b < с означает
(а < b) & (b < с), а, например,

а < bс означает сложное высказывание (а < b)& ((b < c)V(b = с)).

Делается это аналогично тому, как в элементарной алгебре с помощью операций сложения, вычитания, умножения и деления строятся сколь угодно сложные рациональные выражения. А именно, предположим, что мы уже построили два каких-нибудь сложных высказывания, которые мы ради удобства сокращенно обозначим большими латинскими буквами А и В (при этом мы условимся, что элементарные высказывания следует рассматривать как частный случай сложных). Тогда новые высказывания можно получить, соединив А и В одрим из знаков & , V, , или же построив высказывание A и заключив результат в скобки. Сложными высказываниями будут, например, высказывания следующего вида:

((а b) & (с V а));

((аb) (с а )).

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

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

(a V с)(b& а))
и пусть входящие в него элементарные высказывания имеют следующие значения истинности: а = л, b = и, с = и. Тогда b V с = и, b & а = л, так что (a V с)(b & а) = л, т. е. рассматриваемое высказывание ложно.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A B A ∧ B
И И И
И Л Л
Л И Л
Л Л Л

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

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

A B A → B
И И И
И Л Л
Л И И
Л Л И

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

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

A ~ A
Л И
И Л

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

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

A B A → B B → A 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 . Все возможные значения записываются в восемь строк таблицы. Далее, определяя значения операции импликации, и продвигаясь вправо по таблице, помним, что значение равно "лжи" тогда, когда из "истины" следует "ложь".

p q r f
И И И И И И И И
И И Л И И И Л И
И Л И И Л Л Л Л
И Л Л И Л Л И И
Л И И Л И Л И И
Л И Л Л И Л И Л
Л Л И И И И И И
Л Л Л И И И Л И

Заметим, что никакой атом не имеет вида ~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. Составьте таблицу истинности для формулы логики высказываний и определите, является ли она тавтологией, противоречием или ни тем, ни другим.

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

И И И И И
И Л Л Л И
Л И Л И И
Л Л Л Л И

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

Высказывание – это повествовательное предложение (утверждение), о котором можно говорить, что оно истинно или ложно.

Высказывания обозначают большими или маленькими латинскими буквами.

Пример 1: А: «Москва – столица России» – истинное высказывание. b = «Волга впадает в Черное море» – ложное высказывание.

Значения истинности высказываний обозначаются буквами И – «истина» и Л – «ложь» или цифрами 1 – «истина» и 0 – «ложь». Т.е., А = 1(И), b = 0(Л).

Не всякое предложение является высказыванием. Так, к высказываниям не относятся вопросительные, и восклицательные предложения, поскольку говорить об их истинности или ложности нет смысла. Не являются высказываниями и такие предложения: «Каша – вкусное блюдо», «Математика – интересный предмет». Не может быть единого мнения о том, истинны эти предложения или ложны. Предложение «Существуют инопланетные цивилизации» следует считать высказыванием, так как объективно оно либо истинное, либо ложное, хотя пока никто не знает, какое именно.

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

Рассмотрим предложения: «Он рыжеволос» и «Число делится на 7». Эти предложения не содержат переменных в явном виде, но, тем не менее, являются высказывательными формами: первое из них становится высказыванием (истинным или ложным) только после замены местоимения «он» именем конкретного человека из некоторого множества людей мужского пола; второе становится высказыванием, если вместо слова «число» подставлять целые числа. Иначе эти предложения можно записать так: «Человек х рыжеволос», «Число у делится на 7».

Из высказывательных форм можно получать высказывания также с помощью специальных слов, так называемых кванторов . Их два: 1) квантор всеобщности – (любой, всякий, каждый); 2) квантор существования –(существует, найдется, имеется, некоторый, по меньшей мере, один). Например, из высказывательной формы «Площадь комнаты 20 м 2 » можно с помощью кванторов получить высказывания: «Площадь любой комнаты 20 м 2 » – ложное, «Существует комната, площадь которой 20 м 2 » – истинное. Предложения, образованные с помощью квантора всеобщности, называются общеутвердительными ; предложения, образованные с помощью квантора существования, называются частноутвердительными .

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

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

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

Пример 2 : Из предложений «Солнце всходит на востоке» и «Солнце заходит на западе» можно получить следующие составные высказывания: «Солнце всходит на востоке и заходит на западе»; «Солнце всходит на востоке или заходит на западе»; «Если солнце всходит на востоке, то оно заходит на западе»; «Солнце всходит на востоке тогда и только тогда, когда оно заходит на западе»; «Солнце не всходит на востоке» или «Неверно, что солнце заходит на западе».

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

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

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

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

1. Негация (отрицание) – единственная операция, которая может применяться к одному высказыванию.

Негацией высказывания называется новое высказывание, которое истинно тогда и только тогда, когда само высказывание ложно и ложно, когда само высказывание истинно.

Негация обозначается , или ¬b , читается: «не А» или «неверно, что А».

Например, высказывание А = «Луна – спутник Марса» – ложное, а высказывание = «Неверно, что Луна – спутник Марса» – истинное.

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

Пример 3: Сформулировать отрицание высказываний: А = «Курган – большой город»; В = «Сыр делают из молока»; С = «32 не делится на 4»; D = «Все псы попадают в рай».

Решение . = «Неверно, что Курган – большой город»; = «Сыр делаютне из молока»; = «32 делится на 4»;= «Не все псы попадают в рай» = «Некоторые псы не попадают в рай».

Отрицания сложных высказываний чаще всего формулируются с помощью словосочетания «неверно, что…». Например: Высказывание Е = «23 марта 1917 года в Москве утро было морозным и солнечным»; отрицание: = «Неверно, что 23 марта 1917 года в Москве утро было морозным и солнечным»

2. Конъюнкция (логическое умножение) – от латинского conjunctio – соединение.

Конъюнкцией двух высказываний называется новое высказывание, которое истинно тогда и только тогда, когда оба высказывания истинны.

Конъюнкция обозначается
илиА& B ; читается: «А и В ».

Таблица истинности для конъюнкции выглядит следующим образом:

Пример 4: Определить значение истинности высказываний «Париж расположен на Сене и 2 + 3 = 5»; «1 – простое число и 2 – простое число»; «Число 3 – четное и медведи живут в Африке».

Решение. Первое высказывание является конъюнкцией двух высказываний А = «Париж расположен на Сене» и В А В = 1. Следовательно,
= 1.

Второе высказывание является конъюнкцией высказываний А = «1 – простое число» (А = 0) и В = «2 – простое число» (В = 1). Следовательно,
= 0.

Третье высказывание является конъюнкцией двух ложных высказываний, следовательно,
=0.

3. Дизъюнкция (логическое сложение) – от латинского disjunction – разделение .

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

Дизъюнкция обозначается
и читается «А или В ».

Таблица истинности для дизъюнкции выглядит следующим образом:

Пример 5: Определить значение истинности высказываний «Париж расположен на Сене или 2 + 3 = 5»; «1 – простое число или 2 – простое число»; «Число 3 – четное или медведи живут в Африке».

Решение. Первое высказывание является дизъюнкцией двух высказываний А = «Париж расположен на Сене» и В = «2 + 3 = 5». Значение истинности высказывания А = 1 и значение истинности высказывания В = 1. Следовательно,
= 1.

Второе высказывание является дизъюнкцией высказываний А = «1 – простое число» (А = 0) и В = «2 – простое число» (В = 1). Следовательно,
= 1.

Третье высказывание является дизъюнкцией двух ложных высказываний, следовательно,
=0.

4. Импликация (логическое следствие).

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

Импликация обозначается
или
, читается «ЕслиА , то В » («Когда А , тогда В », «А , следовательно В »).

Таблица истинности импликации выглядит так:

Компоненты импликации имеют свои собственные «имена»: предложение А называется посылкой или антецедентом , предложение В – заключением или консеквентом .

Пример 6: Чтобы запомнить правило нахождения значения истинности импликации, удобно воспользоваться следующими высказываниями: «Дождь идет», «Асфальт мокрый», «Дождь не идет», «Асфальт сухой».

1)
= «Если дождь идет, то асфальт мокрый» = 1;

2)
= «Если дождь идет, то асфальт сухой» = 0;

3)
= «Если дождь не идет, то асфальт мокрый» = 1 (прошла поливальная машина или растаял снег);

4)
= «Если дождь не идет, то асфальт сухой» = 1.

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

Вместе с тем определение импликации вынуждает считать истинными высказываниями такие предложения, как «Если 2×2 = 4, то Москва – столица России» или «Если 2×2 = 5, то существуют ведьмы». Эти предложения, вероятно, кажутся бессмысленными. Дело в том, что мы привыкли соединять союзом «если…, то…» (так же, как и другими союзами) предложения, связанные по смыслу. Но определениями логических операций смысл составляющих высказываний никак не учитывается; они рассматриваются как объекты, обладающие единственным свойством – быть истинными либо ложными. Поэтому не стоит смущаться «бессмысленностью» некоторых составных высказываний, их смысл не входит в предмет нашего рассмотрения.

5. Эквиваленция (логическая равносильность).

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

Эквиваленция обозначается
или
, читается «А тогда и только тогда, когда В ».

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

В форме эквиваленции, как правило, формулируются определения (например, определения логических операций).

Пример 7: Пусть через А обозначено высказывание «9 делится на 3», а через В – высказывание «10 делится на 3». Составьте высказывания, имеющие логическую структуру: а)
; б)
; в)
; г)
; д)
; е)
и определите их значения истинности.

Решение. а)
= «Если 9 делится на 3, то 10 делится на 3» = 0, т.к.А = 1, а В = 0. б)
= «Если 10 делится на 3, то 9 делится на 3» = 1. в)
= «9 делится на 3 тогда и только тогда, когда 10 делится на 3» = 0. г)
= «10 делится на 3 тогда и только тогда, когда 9 делится на 3» = 0. д)
= «Если 9 не делится на 3, то 10 делится на 3» = 1 (т.к.А = 1, то = 0 иВ = 0, следовательно,
= 1). е)
= «9 делится на 3 тогда и только тогда, когда 10 не делится на 3» = 1 (А = 1 и = 1, тогда
= 1).

Урок №2

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

(урок комбинированный, включающий повторение предыдущей темы,

введение нового материала и закрепление)

Цель урока: Сформировать у учащихся понятия: логическое высказывание, логические операции.

Задачи урока :

Повторить основные материалы 1 урока (формы человеческого мышления: понятие, суждение, умозаключение);

Познакомить с определением алгебры высказываний;

Познакомить с основными логическими операциями.

Требования к знаниям и умениям:

Учащиеся должны знать:

Что изучает алгебра высказываний и что является объектом изучения алгебры высказываний;

Значения понятий: логическое высказывание, логические операции;

Таблицы истинности логических операций.

Учащиеся должны уметь:

Приводить примеры логических высказываний;

Определять значения логических высказываний;

Называть логические операции и строить для них таблицы истинности.

Этапы урока

I. Организационный момент. Постановка цели урока. 2 мин.

II. Повторение. 7мин.

III. Проверка домашнего задания. 5 мин.

IV. Введение нового материала. 20 мин.

V. Закрепление. 7 мин.

VI. Подведение итогов урока. 3 мин.

VII. Постановка домашнего задания. 1 мин.

Ход урока

II. Повторение .

1) Повторение основных определений и понятий 1 урока:

· Понятие – форма мышления, в которой отражены существенные признаки объектов.

o Объём понятия – множество предметов, каждому из которых принадлежат признаки, составляющие содержание понятия.

Привести примеры .

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

o Форма суждения – это его строение, способ связи его составных частей.

· Умозаключение - форма мышления, посредством которой из одного или нескольких суждений, называемых посылками, по определенным правилам вывода получаем суждение-заключение (вывод умозаключения)

- Определите, какие из перечисленных фраз являются высказываниями и почему?

1. Как хорошо быть генералом!

2.

3. Познай самого себя.

4. Все медведи живут на севере.

5. Революция не может быть мирной и бескровной.

6.

7.

(Примеры 1 и 3 не являются высказываниями, т. к. являются восклицательным и побудительным предложениями соответственно).

- Теперь определите, простые или составные суждения даны .

(В 5 примере можно разбить на два простых утверждения, значит, оно составное.)

- Определите значения высказываний (истина или ложь).

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

Русские пословицы как в примере 4 будут всегда истинны, т. к. опираются на жизненный опыт целых поколений людей.

В примере 7 значение высказывания решается в курсе геометрии, а в 5 утверждении в курсе истории.

Результаты оформляются в виде следующей таблицы:

Фразы

Высказывания

Истина или ложь

Простые высказывания

1. Как хорошо быть генералом!

2. Без труда не выловишь и рыбку из пруда.

3. Познай самого себя.

4. Все медведи живут на севере.

5. Революция не может быть мирной и бескровной.

6. Талант всегда пробьёт себе дорогу.

7. Сумма углов треугольника равна 1800.

На прошлом уроке мы говорили, что каждое высказывание состоит из трех элементов:
субъекта, предиката и связки . Субъект (S) - понятие о предмете. Предикат (P) - понятие о свойствах и отношениях предмета. Связка - отношение между субъектом и предикатом.

Определите, что в простых высказываниях является субъектом, предикатом и связкой.

Без труда не выловишь и рыбку из пруда.

Все медведи живут на севере.

Талант всегда пробьёт себе дорогу.

Сумма углов треугольника равна 1800.

III. Проверка домашнего задания:

Карточка для домашней работы

1.Из приведенных простых высказываний составьте и запишите не менее 3-ёх составных высказываний:

1) Поедем на дачу.

2) Хорошая погода.

3) Плохая погода.

4) Мы поедем на пляж.

5) Антон приглашает нас в театр .

2. Выведите, если это возможно, заключение из каждой пары посылок:

А) Все птицы – животные.

Все воробьи – птицы.

Б) Некоторые уроки трудны.

Всё, что трудно, требует внимания.

В) Ни один добрый поступок не является незаконным.

Всё, что законно, можно делать без страха.

А) Тем, кто лыс, расчёска не нужна.

Ни одна ящерица не имеет волос.

Следовательно, ящерицам расчёска не нужна.

Б) Всем, кто отлично закончит 3 четверть, подарят компьютер.

Ты закончил 3 четверть без троек.

Значит, готовься получить в подарок компьютер.

VI. Объяснение нового материала

Алгебра высказываний

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

Однако, подлинный прогресс этой науки был достигнут в середине XIX века прежде всего благодаря трудам Дж. Буля "Математический анализ логики". Он перенес на логику законы и правила алгебраических действий, ввёл логические операции, предложил способ записи высказываний в символической форме.

В развитии математической логики приняли участие многие выдающиеся математики и логики конца XIX и XX веков, в том числе К. Гедель (австр.), Д. Гильберт (нем.), С. Клини (амер.), Э. Пост (амер.), А. Тьюринг (анг.), А. Чёрч (амер.), и многие другие.

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

Таким образом, объектами изучения алгебры логики являются высказывания.

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

Обозначать высказывания будем большими латинскими буквами. Если высказывание А истинное, то будем писать "А = 1" и говорить: "А - истинно". Если высказывание Х ложно, то будем писать "Х = 0" и говорить "Х ложно".

Обоснование истинности или ложности простых высказываний решается вне алгебры логики. Например, истинность или ложность высказывания «Сумма углов треугольника равно 180о» устанавливается геометрией, причём в геометрии Евклида это высказывание является истинным, а в геометрии Лобачевского – ложным.

Алгебра логики отвлекается от смыслового содержания высказываний. Её интересует только один факт – истинно или ложно данное высказывание. Такое суждение интересов даёт возможность изучать высказывания алгебраическими методами.

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

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

    Дизъюнкция (логическое сложение) Импликация (логическое следование) Эквивалентность (логическое равенство)

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

Инверсия (логическое отрицание) – это логическая операция, которая каждому данному высказыванию ставит в соответствие новое высказывание, которое истинно, если данное высказывание – ложно, и ложно, если данное высказывание истинно.

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

Обозначение инверсии: ; неА ; А; NOT А

0 " style="border-collapse:collapse;border:none">

А

Образуется из простого высказывания с помощью добавления частицы НЕ к сказуемому или использованием оборота речи "НЕВЕРНО, ЧТО...".

Пример: А = "На улице дождь"

= "Неверно, что на улице дождь"

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

Определите истинность каждого.

Итак, инверсия высказывания истинна, когда высказывание ложно.

2) Конъюнкция (логическое умножение)

истинно тогда и только тогда, когда оба исходных высказывания истинны.

Обозначение конъюнкции: А &В , А andВ , А LВ , А В .

Таблица истинности:

А &В

Образуется соединением двух высказываний в одно с помощью союза «И»

Пример: А = "На улице дождь"

В= "Небо голубое"

А &В = "На улице дождь и небо голубое"

Задание 2. а) Приведите примеры двух высказываний и получите составное высказывание используя логическую связку "И".

Итак, конъюнкция двух высказываний истинна тогда и только тогда, когда оба исходных высказывания истинны.

3) Дизъюнкция (логическое сложение) – это логическая операция, ставящая в соответствие каждым двум высказываниям новое высказывание, которое

истинно тогда и только тогда, когда хотя бы одно из двух исходных высказываний истинно.

Обозначение дизъюнкции: А V В , А OR В , А +В .

0 " style="border-collapse:collapse;border:none">

А V В

Образуется соединением двух высказываний в одно с помощью союза «ИЛИ»

Пример: А = "На улице дождь"

В= "Небо голубое"

А V В = "На улице дождь или небо голубое"

Задание 3. а) Приведите примеры двух высказываний и получите составное высказывание используя связку "ИЛИ".

Итак, дизъюнкция двух высказываний истинна тогда и только тогда, когда хотя бы одно из двух исходных высказываний истинно.

4) Импликация (логическое следование) – это логическая операция, ставящая в соответствие каждым двум высказываниям новое высказывание, которое

ложно тогда и только тогда, когда первое высказывание (условие) истинно, а второе высказывание (следствие) ложно.

Обозначение дизъюнкции: А ® В .

Таблица истинности: Диаграмма Эйлера:

«ЕСЛИ …, ТО …»

Если клятва дана, то она должна выполняться.

Если число делится на 9, то оно делится и на 3.

Пример: А = " На улице дождь"

В= "Небо голубое"

А ® В = "Если на улице дождь, то небо голубое"

Задание 4 . а) Приведите примеры двух высказываний и получите составное высказывание, используя связку "ЕСЛИ, ТО...".

б) Определите истинность или ложность каждого из трех высказываний

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

5) Эквивалентность (логическое равенство) – это логическая операция, ставящая в соответствие каждым двум высказываниям новое высказывание, которое

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

Обозначение дизъюнкции: А « В, А = В, А≡В .

Таблица истинности: Диаграмма Эйлера:


Образуется соединением двух высказываний в одно с помощью оборота речи «…ТОГДА И ТОЛЬКО ТОГДА, КОГДА…»

Угол называется прямым тогда и только тогда, когда он равен 900

Все законы математики, физики, все определения – эквивалентность высказываний

Две прямые параллельны тогда и только тогда, когда они не пересекаются.

Пример: А = "На улице дождь"

В= "Небо голубое"

А « В = "На улице дождь тогда и только тогда, когда небо голубое"

Задание 5. а) Приведите примеры двух высказываний и получите составное высказывание используя связку речи «…ТОГДА И ТОЛЬКО ТОГДА, КОГДА…»

б) Определите истинность или ложность каждого из трех высказываний.

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

VI. Закрепление изученного.

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

· Какого цвета этот дом?

· Число Х не превосходит единицы.

· Посмотрите в окно.

· Пейте томатный сок!

· Эта тема скучна.

· Вы были в театре?

2. Объясните, почему формулировка любой теоремы является высказыванием.

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

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

    Коля спросил: «Как пройти к Большому театру?» Как пройти в библиотеку? Картины Пикассо слишком абстрактны. Решение задачи – информационный процесс. Число 2 является делителем числа 7 в некоторой системе счисления.

5. Выбрать истинные высказывания:

· “Число 28 является совершенным числом”

· “Без труда не выловишь и рыбку из пруда”

· “Талант всегда пробьёт себе дорогу”

· “Некоторые животные мыслят”

· “Информатика - наука об алгоритмах”

· “2+3*5=30”

· “Все ученики любят информатику”

6.

7. Какая логическая операция соответствует данной таблице истинности?

8. Какая логическая операция соответствует данной таблице истинности?

9. Какая логическая операция соответствует данной таблице истинности?

10. Какая логическая операция соответствует данной таблице истинности?

Итог урока:

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

2. Выучить все определения в тетради из конспекта урока .

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