Алгебра в широком смысле этого слова - наука об общих операциях, аналогичных сложению и умножению, которые могут выполняться над разнообразными математическими объектами.
Многие математические объекты (целые и рациональные числа, многочлены, векторы, множества) вы изучаете в школьном курсе алгебры, где знакомитесь с такими разделами математики, как алгебра чисел, алгебра многочленов, алгебра множеств и т. д. Для информатики важен раздел математики, называемый алгеброй логики
; объектами алгебры логики являются высказывания
.
Высказывание
- это предложение на любом языке, содержание которого можно однозначно определить как истинное или ложное.
Пример:
Например, относительно предложений «Великий русский учёный М. В. Ломоносов родился в \(1711\) году» и «Two plus six is eight» можно однозначно сказать, что они истинны. Предложение «Зимой воробьи впадают в спячку» - ложно. Следовательно, эти предложения являются высказываниями.
В русском языке высказывания выражаются повествовательными предложениями.
Обрати внимание!
Но не всякое повествовательное предложение является высказыванием.
Пример:
Например, предложение «Это предложение является ложным» не является высказыванием, так как относительно него нельзя сказать, истинно оно или ложно, без того чтобы не получить противоречие. Действительно, если принять, что предложение истинно, то это противоречит сказанному. Если же принять, что предложение ложно, то отсюда следует, что оно истинно.
Побудительные и вопросительные предложения высказываниями не являются.
Например, не являются высказываниями такие предложения, как: «Запишите домашнее задание», «Как пройти в библиотеку?», «Кто к нам пришёл?».
Высказывания могут строиться с использованием знаков различных формальных языков - математики, физики, химии и т. п.
Примерами высказываний могут служить:
«Nа - металл» (истинное высказывание);
«Второй закон Ньютона выражается формулой \(F = ma\) (истинное высказывание);
«Периметр прямоугольника с длинами сторон \(а\) и \(b\) равен \(аb\)» (ложное высказывание).
Не являются высказываниями числовые выражения, но из двух числовых выражений можно составить высказывание, соединив их знаками равенства или неравенства. Например:
- 3 + 5 = 2 ⋅ 4 (истинное высказывание);
- «II + VI > VIII» (ложное высказывание).
Не являются высказываниями и равенства или неравенства, содержащие переменные.
Например, предложение \(«x < 12»\) становится высказыванием только при замене переменной каким-либо конкретным значением: \(«5 < 12»\) - истинное высказывание; \(«12 < 12»\) - ложное высказывание.
Обоснование истинности или ложности высказываний решается теми науками, к сфере которых они относятся. Алгебра логики отвлекается от смысловой содержательности высказываний. Её интересует только то, истинно или ложно данное высказывание. В алгебре логики высказывания обозначают буквами и называют логическими переменными . При этом, если высказывание истинно, то значение соответствующей ему логической переменной обозначают единицей \((А = 1)\), а если ложно - нулём \((В = 0)\).
\(0\) и \(1\), обозначающие значения логических переменных, называются логическими значениями .
Здесь: 1 - истина, 0 - ложь.
- 1. Х: треугольник АВС - остроугольный. Х: неверно, что треугольник АВС - остроугольный. Это все равно, что: Х: треугольник АВС - прямоугольный или тупоугольный
- 2. А: Иванова М. На экзамене по математике получила 4. : Неверно, что Иванова М. по математике получила 4.
Определение: Дизъюнкцией высказывания А и В называется высказывание АВ, истинное при условии, что хотя бы одно из высказываний А или В истинно.
Его читают «А или В».
Таблица истинности для АВ
Пример: 1. На этот раз ответчик явился и суд состоялся. - истина
2. В прямоугольном треугольнике сумма двух любых углов больше или равна третьего угла и гипотенуза меньше катета. - ложь
Определение: Импликацией высказываний А и В называется высказывание АВ, ложное лишь при условии, что А истинно, а В ложно.
Его читают: «Если А, то В».
Таблица истинности
Пример: 1. Если я сдам зачет, то пойду в кино.
2. Если треугольник равнобедренный, то углы при его основании равны. Определение: Эквиваленцией высказываний А и В называется высказывание АВ, истинное в том и только в том случае, когда А и В имеют одну и ту же истинность (т.е. либо оба истинны, либо оба ложны).
Читают: «А тогда и только тогда, когда В» или «А необходимо и достаточно для В»
Таблица истинности
Вторая задача, решаемая средствами алгебры высказываний, состоит в том, чтобы определить истинность конкретного высказывания на основе составления его формулы (процесс формализации) и составления таблицы истинности.
Пример: Если Саратов расположен на берегу Невы, то в Африке обитают белые медведи.
А: Саратов расположен на берегу реки Невы;
В: В Африке обитают белые медведи
Определение: Формула, которая истинна независимо от того, какие значения принимают входящие в нее высказывательные переменные, называется тавтологией или тождественно истинной формулой.
Определение: Формулы F 1 и F 2 называются равносильными, если их эквиваленция - тавтология.
Определение: Если формулы F 1 и F 2 равносильны, то предложения Р 1 и Р 2 , которые инициируют эти формулы, называются равносильными в логике высказываний.
Основные, наиболее часто встречающиеся равносильности, называют законами логики. Перечислим некоторые из них:
- 1. Х Х - закон тождества
- 2. Х Л - закон противоречия
- 3. Х И - закон исключения третьего
- 4. Х - закон двойного отрицания
- 5. законы коммутативности
- 6. Х (У Z) (Х У) Z закон ассоциативности
Х (У Z) (Х У) Z закон дистрибутивности
7. законы Де Моргана
8. законы сочленения переменной с константой
Используя законы логики, можно преобразовывать формулы.
4. Из множества формул, равносильных между собой, рассмотрим две. Это - совершенная конъюнктивная нормальная форма (СКНФ) и совершенная дизъюнктивная нормальная форма (СДНФ). Они строятся для данной формулы на основе ее таблицы истинности.
Построение СДНФ:
- -- выбираются строки, соответствующие значениям истинности (1) данной формулы;
- -- для каждой выделенной строки составляем конъюнкцию переменных или их отрицаний так, чтобы наборам значений переменных, представленных в строке, соответствовали истинные значения конъюнкции (для этого надо переменные, которые в этой строке принимали значения ложь (0) взять со знаком отрицания, а переменные, принимающие значения истинности (1) без отрицания);
- -- составляется дизъюнкция полученных конъюнкций.
Из алгоритма следует, что для любой формулы можно составить СДНФ, и притом единственную, если формула не является тождественно ложной, т.е. принимающей только ложные значения.
Составление СКНФ осуществляется по следующему алгоритму:
- -- выделить те строки таблицы, в которых формула принимает значение ложь (0);
- -- из переменных, стоящих в каждой такой строке, составить дизъюнкцию, которая должна принимать значения - ложь (0). Для этого все переменные должны войти в нее со значением ложь, следовательно те, которые истинны (1), надо заменить их отрицанием;
- -- из полученных дизъюнкций составить конъюнкцию.
Очевидно, что любая формула, не являющаяся тавтологией, имеет СКНФ.
СДНФ и СКНФ используются для получения следствий из данной формулы.
Пример: Составить таблицу истинности СДНФ и СКНФ для формулы: .
Таблица истинности СДНФ и СКНФ
5. Рассмотрим высказывательные форму «Река впадает в Черное море». Она содержит одну переменную и может быть представлена в виде «Река х впадает в Черное море».
В зависимости от значений переменной Х предложение является либо истинным, либо ложным, т.е. задается отображение множества рек на двух элементное множество. Обозначим это отображение, тогда:
Таким образом, имеем функцию, все значения которой принадлежат множеству.
Определение: Функция, все значения которой принадлежат множеству, называется предикатом.
Буквы, обозначающие предикаты, называют предикатными символами.
Предикаты могут задаваться:
a) высказывательной формулой,
b) формулой, т.е. задавая интерпретацию предикатного символа,
c) таблицей.
1) Р - «впадать в Черное море».
Эта формула означает, что «Река а впадает в Черное море».
- 2) Предикат Р задан высказывательной формулой: «быть простым числом на множестве первых 15 натуральных чисел».
- 3) В табличной форме предикат имеет вид:
Областью определения предикатов может быть любое множество.
Если предикат при каком-либо наборе входящих переменных теряет смысл, то принято считать, что этому набору соответствует значение Л.
Если предикат содержит одну переменную, то его называют одноместным, две переменные - двуместным, n переменных - n-местным предикатом.
Для перевода текстов на язык предикатов и определения их истинности необходимо ввести логические операции над предикаторами и кванторы.
Над предикатами выполняются так же операции: отрицания, конъюнкции, дизъюнкции, импликации, эквиваленции.
Определение: Подмножество множества М, на котором задан предикат Р, состоящий из тех и только тех элементов М, которым соответствует значение И предиката Р, называется множеством истинности предиката Р.
Множество истинности обозначается.
Определение: Отрицанием предиката Р называется предикат, ложный при тех наборах значений переменных, которые обращают Р в истинный, и истинный при тех наборах значений переменных, которые обращают Р в ложный предикат.
Обозначается отрицание.
Быть студентом АБиК.
Не быть студентом АБиК.
Если, то множество, где М - множество, на котором заданы предикаты Р и Q .
Определение: конъюнкцией предикатов и называется предикат истинный при тех и только тех значениях переменных, входящих в него, которые обращают оба предиката и в истинные.
Быть футболистом
Быть студентом
: быть футболистом и быть студентом.
Определение: дизъюнкцией предикатов и называется предикат ложный при тех наборах входящих в него переменных, которые обращают оба предиката в ложные
Быть четным натуральным числом
Быть нечетным натуральным числом
: быть натуральным числом.
Определение: Импликацией предикатов называется предикат, ложный при тех и только тех наборах входящих в него переменных, которые обращают в истинный предикат, а - в ложный.
Обозначается:
Быть простым числом на множестве N
Быть нечетным числом
Ложен при и истинным при других натуральных числах.
Определение: Эквиваленцией предикатов и называется предикат, который становится истинным, если оба предиката и истинны, или оба ложны.
Обозначается:
- «выигрывать», т.е. х выигрывает у
Лучше знать шахматную историю, х знает лучше у
обозначает, что х выигрывает у у в шахматы тогда и только тогда, когда он лучше знает теорию.
Определение: Предикат следует из предиката если импликация истинна при любых входящих в нее значениях переменных.
Обозначаются следования: .
Быть студентом
Ходить в институт
Для превращения предиката в высказывание существуют 2 пути:
1) придание переменной конкретного значения
; х - студент
Иванов - студент.
2) Навешивание кванторов - любой, всякий, каждый
Существует, имеется.
Запись, где обладает свойством Р означает, что всякий предмет х обладает свойством Р. Или по другому, «все х обладают свойством Р».
Запись означает, что существует предмет х, обладающий свойством Р.
Тема 2. Высказывания. Логические операции над ними
Простое высказывание – это утверждение (повествовательное предложение), в отношении которого можно сказать, истинно оно или ложно (но не то и другое вместе).
Всякое высказывание является предложением и может быть выражено словами, однако далеко не каждое предложение является высказыванием в математическом смысле.
Пример. Не являются высказываниями предложения:
1) число 0,00000001 очень мало;
2) существует ли число, квадрат которого равен 2?
4) 
.
Первое их этих предложений не является высказыванием потому, что не имеет точного смысла и мы не можем сказать, истинно оно или ложно; второе предложение содержит вопрос; третье и четвертое предложения содержат букву х. При одних значениях х получается истинное высказывание, при других ложное.
Предложение, о котором невозможно однозначно решить вопрос, истинно оно или ложно, высказыванием не является.
Всякое высказывание является либо истинным, либо ложным (закон исключенного третьего).
Никакое высказывание не может быть одновременно истинным и ложным (закон противоречия).
Неопределенные высказывания
Будем обозначать через N множество всех натуральных чисел. Через х обозначим произвольный элемент множества N. Рассмотрим следующие предложения:
,
.
Предложения A(x), B(x), C(x), D(x) высказываниями не являются, т.к. об истинности, например, A(x) мы ничего не можем сказать, пока нам не известно число х. Однако, подставляя в A(x) вместо х различные натуральные числа, мы будем получать высказывания о натуральных числах – иногда истинные, иногда ложные. Например:
Истинное высказывание;
Ложное высказывание.
Предложения A(x), B(x), C(x), D(x), содержащие переменную х , называют неопределенными высказываниями (предикатами). Если вместо х подставить число, то мы получим обычное высказывание.
Неопределенное высказывание может быть задано на любом множестве. Оно представляет собой высказывание о каком-то элементе х рассматриваемого множества.
Часто приходится рассматривать неопределенные высказывания, в которые входит не одно, а два или большее число переменных.
Пример. 
;
Мы ничего не можем сказать об истинности или ложности этих утверждений, т.к. нам неизвестны х и y. Но если точно указано, чему равны х и y , каждое из сформулированных утверждений превращается в высказывание – для одних пар х и y истинное, для других – ложное. Вот примеры высказываний, полученных из указанных предложений при конкретных значениях х и y:
-
истинное высказывание;
-
ложное высказывание;
-
ложное высказывание;
-
ложное высказывание;
- истинное высказывание.
Логические операции над высказываниями
Высказывания обозначают латинскими буквами A, B, C , …, их значения истина и ложь соответственно, через «И» и «Л». Сложные высказывания получают из простых при помощи логических операций, к которым относятся отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность (эквиваленция ) .
1. Если А – высказывание, то отрицание высказывания А определяется как такое высказывание, которое истинно тогда и только тогда, когда высказывание А ложно. Отрицание высказывания А обозначается (или ØА ) и читается «не А» .
Истинность-ложность операции отрицания выражает истинностная таблица 1.1.
Т а б л и ц а 1.1
| А | |
| И | Л |
| Л | И |
Пример. 1) ; .
2) 
; 
.
3) 
; 
.
4) ; .
Каково бы ни было высказывание А, из двух высказываний А, А одно является истинным, а другое – ложным.
Закон отрицания отрицания: Двойное отрицание А истинно в том и только в том случае, если истинно само высказывание А (т.е. если А истинно, то и А истинно, а если А ложно, то и А ложно).
2. Конъюнкцией двух высказываний называется такое высказывание, которое истинно тогда и только тогда, когда оба составляющие ее высказывания истинны.
Если А , В - высказывания, то их конъюнкция обозначается A Ù B (или А & B ) и читается «А и В ».
Конъюнкции соответствует истинностная таблица 1.2.
Т а б л и ц а 1.2
| А | В | А Ù В |
| И | И | И |
| И | Л | Л |
| Л | И | Л |
| Л | Л | Л |
Пример:
Высказывание 
- истинно, высказывание 
- истинно, поэтому истинна и их конъюнкция .
3. Дизъюнкцией двух высказываний называется такое высказывание, которое ложно тогда и только тогда, когда оба составляющие ее высказывания ложны.
Если А , В - два высказывания, то их дизъюнкция обозначается А Ú В и читается «А или В ». Союз «или» здесь употребляется в соединительном, а не в разделительном смысле, т. е. для истинности высказывания А Ú В допускается также случай истинности обоих высказываний А , В .
Операции дизъюнкции соответствует истинностная таблица 1.3.
Т а б л и ц а 1.3
| А | В | А Ú В |
| И | И | И |
| Л | И | И |
| И | Л | И |
| Л | Л | Л |
Пример:
Высказывание - истинно, высказывание 
- ложно. Тогда высказывание 
- истинно.
4. Импликация высказываний А, В определяется как такое высказывание, которое ложно тогда и только тогда, когда высказывание А истинно, а высказывание В ложно. Импликация двух высказываний А , В обозначается А Þ В и читается «если А , то В ». Высказывание А называется посылкой импликации , а В - заключением .
Импликации соответствует истинностная таблица 1.4.
Т а б л и ц а 1.4
| А | В | А Þ В |
| И | И | И |
| Л | И | И |
| И | Л | Л |
| Л | Л | И |
5. Эквивалентность двух высказываний А , В определяется как высказывание, которое истинно тогда и только тогда, когда высказывания А , В оба истинны или оба ложны. Обозначается А Û В и читается «А тогда и только тогда, когда В » («если А , то В , и, если В , то А », «А есть необходимое и достаточное условие для В »). Значения эквивалентности определены в истинностной таблице 1.5.
Т а б л и ц а 1.5
| А | В | А Û В |
| И | И | И |
| И | Л | Л |
| Л | И | Л |
| Л | Л | И |
Пример: Рассмотрим два высказывания, определенных на множестве натуральных чисел:
Тогда признак делимости на 3 можно записать как 
(число делится на 3 тогда и только тогда, когда сумма его цифр делится на три).
Если теорема сформулирована в виде A Þ B , то она называется признаком или достаточным условием дляB , где A, B – некоторые высказывания.
Теорема типа В Þ А называется обратной для теоремы A Þ B .
Если теорема имеет вид A Û B , то она называется критерием или необходимым и достаточным условиями для B .
Теорема такого типа объединяет прямую и обратную теоремы.
Теорема типа 
называется противоположной к обратной теореме
.
Высказывание A
Þ B
истинно тогда и только тогда, когда истинно высказывание 
. На этом факте основан метод доказательства от противного
.
Пример:
Пусть высказывание , а . Тогда 
.
Данную теорему принято выражать в следующем виде:
А является достаточным условием для В.
В является необходимым условием для А.
Необходимое условие можно сформулировать следующим образом: для делимости числа х на 4 необходимо, чтобы его последняя цифра была четной.
©2015-2019 сайт
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-10-25
Высказывание – это повествовательное предложение (утверждение), о котором можно говорить, что оно истинно или ложно.
Высказывания обозначают большими или маленькими латинскими буквами.
Пример 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).
Мы будем знакомиться с самым элементарным разделом логики - алгеброй высказываний.
Исходные объекты алгебры высказываний - это простые (элементарные) высказывания. Мы в дальнейшем будем их обозначать строчными латинскими буквами а, 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 &
а) = л, т. е. рассматриваемое высказывание ложно.
