МАТЕМАТИЧЕСКАЯ ЛОГИКА
Алгебра высказываний Теоретические сведения
Простое высказывание представляет собой некоторое повествовательное предложение, которое может быть либо истинно, либо ложно, но не то и другое одновременно. Простое высказывание обозначается маленькими латинскими буквами а, Ь, с и т.д.
Высказывания, которые получаются из простых с помощью грамматических связок «и», «или», «не», «тогда и только тогда», «либо... либо...», «если... то...», называются составными или формулами алгебры высказываний. Формулы алгебры высказываний обозначаются большими латинскими буквами А, В, С и т.д.
Всегда истинная формула А называется тождественно истинной формулой или тавтологией, А - 1.
Всегда ложная формула В называется тождественно ложной формулой или противоречием, В= 0.
Рассматривая высказывания, мы абстрагируемся от их смысла, нас интересует их истинность или ложность. Мы пишем а = 1, если а — истинно, и а = 0, если а — ложно.
Рассмотрим основные операции над высказываниями:
- • дизъюнкция V;
- • конъюнкция &;
- • отрицание а
- • импликация —
- • эквивалентность
- • сложение Жегалкина ©.
Значение истинности для каждой логической операции в зависимости от истинности ее операндов описывается таблицей истинности.
Таблица истинности представляет собой таблицу, устанавливающую соответствие между возможными значениями наборов переменных и значениями операций [2].
Таблицы истинности логических операций позволяют определить значение, которые они принимают при различных значениях переменных, сравнивать операции между собой, определять, удовлетворяют ли операции заданным свойствам.
Дизъюнкция а V Ь. Читается эта запись как «а дизъюнкция Ь».
Дизъюнкция ложна тогда и только тогда, когда ложны оба операнда. В русском языке дизъюнкция соответствует объединительному союзу «ИЛИ» (табл. 3.1).
Таблица 3.1
Таблица истинности высказывательных функций
а |
ь |
а/ Ь |
а & Ь |
а |
а —> Ь |
а © Ь |
а <=> Ь |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
Конъюнкция а & Ь. Запись читается как «а конъюнкция Ь».
Конъюнкция двух сомножителей истинна тогда и только тогда, когда истинны оба сомножителя. В русском языке соответствует союзу «И» (см. табл. 3.1).
Отрицание а. Запись читается как «не а».
Отрицание лжи есть истина, отрицание истины есть ложь. Соответствует частице «НЕ» (см. табл. 3.1).
Импликация а —> Ь. Запись а —> Ъ читается как «а импликация Ь» или «из а следует Ь».
Для функции импликации из лжи следует все что угодно, а из истины только истина (см. табл. 3.1). Соответствует «если а, то Ь», «а является достаточным условием для Ь». Запись а <— Ь соответствует «если Ь, то а», «а является необходимым условием для Ь».
Жегалкинское сложение а © Ь.Запись читается как «а сложение по Жегалкину Ь».
Операция истинна тогда и только тогда, когда значения переменных различны (см. табл. 3.1). Соответствует «а либо Ь», «либо а, либо Ь», «или а, или Ь».
Эквивалентность а <=> Ь. Запись читается как «а эквивалентно Ь». Операция истинна тогда и только тогда, когда значения переменных совпадают. В русском языке соответствует выражению «тогда и только тогда, когда».
Алгебра высказываний представляет собой совокупность
5= <{0, 1}, {&, V, ,—»,<=>}>,
где носитель алгебры представляет собой множество высказываний {О, 1}, в ее сигнатуру входят операции конъюнкция, дизъюнкция, отрицание, импликация и эквивалентность.
Основные законы алгебры высказываний можно разбить на три группы (табл. 3.2):
- • законы, выражающие свойства самих операций;
- • законы, выражающие одни операции через другие;
- • законы, выражающие основные законы алгебры высказываний. При работе с высказываниями мы отвлекаемся от их смысла, нас
интересует только истинность или ложность высказывания. Каждое
Таблица 3.2
Законы алгебры высказываний
1 |
X & X = X X V X - X |
Законы идемпотентности |
2 |
X & 1 = X X V 1 = 1 х & 0 = 0 х V 0 = х |
Законы работы с 0 и 1 |
3 |
х & х = 0 |
Закон противоречия |
4 |
X V X = 1 |
Закон исключения третьего |
5 |
к II II к |
Закон снятия двойного отрицания |
6 |
X & (х V у) = X xvx&y = x |
Законы поглощения |
7 |
х <=> у = (х —» у) & (у —> х) |
Эквивалентность через импликацию и конъюнкцию |
8 |
х —> у = X V у |
Эквивалентность через импликацию и конъюнкцию |
9 |
X © у - (х —> у) V (у —> х) |
Жегалкинское сложение через импликацию, отрицание и дизъюнкцию |
10 |
II > * |
Отрицание дизъюнкции через конъюнкцию отрицаний |
11 |
X & у = X V у |
Отрицание конъюнкции через дизъюнкцию отрицаний |
12 |
X & у = X V у |
Конъюнкция через дизъюнкцию и двойное отрицание |
13 |
X & у = у & X |
Коммутативность конъюнкции |
14 |
X V у = у V X |
Коммутативность дизъюнкции |
15 |
(х & у) & г = х & (у & 1) |
Ассоциативность конъюнкции |
16 |
(х V у) V ^ = X V (у V |
Ассоциативность дизъюнкции |
17 |
х&(уу^) = х& уух&^ |
Дистрибутивность конъюнкции относительно дизъюнкции |
18 |
X V у & г = (х V у) & (х V 1) |
Дистрибутивность дизъюнкции относительно конъюнкции |
высказывание — это повествовательное утверждение естественного языка. Несмотря на то что естественный язык гораздо богаче высказываний алгебры логики, в табл. 3.3 приведен один из способов формализации сложных высказываний, т.е. построения формул алгебры высказываний. В таблице рассмотрены примеры построения формул при условии что а — «погода ясная», Ь — «погода дождливая», с — «ветрено».
Таблица 3.3
Таблица формализации высказываний
Союзы и частицы естественного языка |
Операции алгебры высказываний |
Примеры |
«о» и «Ь» |
а & Ь |
Погода ясная и дождливая |
«а» или «Ь» |
д V Ь |
Ясная или дождливая погода |
«с» либо «Ь» |
с® Ь |
Будет ветрено либо дождливо |
Не «а» |
а |
Неверно, что погода ясная. Погода пасмурная |
«а» достаточное условие для «Ь» |
а —> Ь |
Ясная погода является достаточным условием дождливой погоды |
Если «а», то «Ь» |
а^>Ь |
Если погода ясная, то будет дождь |
«а» необходимое условие для «Ь» |
Ь —> а |
Ясная погода является необходимым условием дождливой погоды |
«а» тогда и только тогда, когда «Ь» |
а <=> Ь |
Ясная погода бывает тогда и только тогда, когда идет дождь |
«а» либо «Ь» |
а® Ь |
Погода будет ясной, либо дождливой, либо ясная погода |
Или «а», или «Ь», но не оба |
а® Ь |
Или сегодня погода будет ясной, или дождливой, но не ясной с дождем |
При формализации высказываний русского языка можно дать
несколько рекомендаций:
- • выделить из составного высказывания простые высказывания и обозначить их латинскими буквами;
- • определить, какие конструкции русского языка соответствуют операциям алгебры высказываний и их старшинство;
- • записать логическую формулу путем использования обозначений простых высказываний, операций и скобочных структур для правильного порядка применения операций.
Задачи
Задача 3.1. Формализовать следующее высказывание: «Неверно, что идет дождь либо ветрено и холодно».
Решение.
Выделяем простые высказывания и заменяем их буквами: «Идет дождь» — Л «Ветрено» — В; «Холодно» — С.
Наше высказывание приобретает вид: «Неверно, что А либо В и С».
«Неверно» соответствует отрицанию и должно применяться ко всей формуле; «либо» соответствует жегалкинскому сложению между А и «В и С», «и» — конъюнкции между В и С. Для правильного порядка применения операций конъюнкцию нужно заключить в скобки. Таким образом, правильно построенная формула имеет вид
А®(В&С).
Задача 3.2. Формализовать следующее высказывание: «Отсутствие дождя есть необходимое условие для безветренной или холодной погоды».
Решение.
Выделяем простые высказывания и заменяем их латинскими буквами: «Отсутствие дождя» — А; «Безветренная погода» — В; «Холодная погода» — С.
Наше высказывание приобретает вид: «А достаточное условие для В или С».
Самой старшей операцией будет «достаточное условие», т.е. импликация из А в «В или С». Таким образом, правильно построенная
формула для данной задачи имеет вид А —> (В V С).
Рассмотрим задачи на решение уравнений алгебры высказываний. Каждое такое уравнение решается при условии, что оно истинно, т.е. равно единице.
Для решения логических уравнений или систем логических уравнений рекомендуем порядок действий:
- • выделить из составного высказывания простые высказывания и обозначить их латинскими буквами;
- • формализовать каждое сложное высказывание с учетом выделенных простых и построить формулу алгебры высказываний, равную единице;
- • если рассматривается система уравнений, то нужно построить новую формулу алгебры высказываний в виде конъюнкции ранее построенных формул и приравнять ее единице;
- • определить все значения простых высказываний, при которых построенная формула истинна.
Задача 3.3. Записать в символическом виде и вычислить, кто из трех предпринимателей — А, В, С — закончил 2016 год с прибылью, если известно, что:
- • «Неверно, что если В с прибылью, то и А с прибылью»;
- • «В без прибыли, если остались без прибыли А или С».
Решение.
Выделяем простые высказывания и заменяем их буквами: «А с прибылью» — А; «В с прибылью» — В; «С с прибылью» — С.
Формализуем первое высказывание: В —> А.
Формализуем второе высказывание: А V С —> В.
Построим конъюнкцию высказываний и приравняем ее единице, так как должны быть истинными одновременно оба логических высказывания: (В —> А) & (А V С —> В) = 1.
Упрощаем формулу, применяя законы алгебры высказываний:
(В -» А) & (А V С -» В) = (В V А) & (А V С V В) =
= й&M(/lvCvfi) = 1.
Полученная конъюнкция истинна тогда и только тогда, когда все ее сомножители истинны, т.е. каждый сомножитель должен быть равен единице:
- • В = 1;
- • А = 1;
- • АчСчИ ==ЪчСчЪ = С = .
Таким образом, получаем, что А — без прибыли, В — с прибылью, С — с прибылью.
Задача 3.4. Даны три высказывания: А — «Идет дождь»; В — «Ветрено»; С — «Ясно». Формализовать следующее сложное высказывание: «Неверно, что ясно бывает тогда и только тогда, когда дует ветер или идет дождь».
Задача 3.5. Даны три высказывания: А — «Идет дождь»; В — «Ветрено»; С — «Ясно». Формализовать следующее сложное высказывание: «Ясная погода является необходимым условием для отсутствия дождя или отсутствия ветра».
Задача 3.6. Даны три высказывания: А — «Идет дождь»; В — «Ветрено»; С — «Ясно». Формализовать следующее сложное высказывание: «Ясная погода является необходимым и достаточным условием для отсутствия дождя или отсутствия ветра».
Задача 3.7. Даны три высказывания: А — «Идет дождь»; В — «Ветрено»; С — «Ясно». Формализовать следующее сложное высказывание: «Ясная погода является достаточным условием для отсутствия дождя или отсутствия ветра».
Задача 3.8. Определить, какие высказывания являются ложными:
- • «Ромб — частный случай параллелограмма»;
- • «Квадрат — частный случай ромба»;
- • «л/1200 < 34»;
- • «fl00 < 26»;
- • «Если натуральное число делится на 3 и 4, то оно делится и на 6».
Задача 3.9. Для того чтобы логическое выражение (а & а)/(Ь & Ь) при любых значениях логических переменных а и Ь всегда принимало значение «ложь», вместо / нужно поставить следующую функцию алгебры высказываний ....
Задача 3.10. Для того чтобы логическое выражение (а & а)/(Ь V Ь) при любых значениях логических переменных а и Ь всегда принимало значение «ложь», вместо / нужно поставить следующую функцию алгебры высказываний ....
Задача 3.11. Записать в символическом виде и вычислить, кто из трех предпринимателей — А, В, С — закончил 2016 год с прибылью, если известно, что:
- • «Если остались без прибыли А или С, то В — с прибылью»;
- • «Неверно, что А с прибылью, если В без прибыли».