МАТЕМАТИЧЕСКАЯ ЛОГИКА

Алгебра высказываний Теоретические сведения

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

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

Всегда истинная формула А называется тождественно истинной формулой или тавтологией, А - 1.

Всегда ложная формула В называется тождественно ложной формулой или противоречием, В= 0.

Рассматривая высказывания, мы абстрагируемся от их смысла, нас интересует их истинность или ложность. Мы пишем а = 1, если а — истинно, и а = 0, если а — ложно.

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

• • дизъюнкция V;
• • конъюнкция &;
• • отрицание а
• • импликация —
• • эквивалентность
• • сложение Жегалкина ©.

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

Таблица истинности представляет собой таблицу, устанавливающую соответствие между возможными значениями наборов переменных и значениями операций [2].

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

Дизъюнкция а V Ь. Читается эта запись как «а дизъюнкция Ь».

Дизъюнкция ложна тогда и только тогда, когда ложны оба операнда. В русском языке дизъюнкция соответствует объединительному союзу «ИЛИ» (табл. 3.1).

Таблица 3.1

Таблица истинности высказывательных функций

Конъюнкция а & Ь. Запись читается как «а конъюнкция Ь».

Конъюнкция двух сомножителей истинна тогда и только тогда, когда истинны оба сомножителя. В русском языке соответствует союзу «И» (см. табл. 3.1).

Отрицание а. Запись читается как «не а».

Отрицание лжи есть истина, отрицание истины есть ложь. Соответствует частице «НЕ» (см. табл. 3.1).

Импликация а —> Ь. Запись а —> Ъ читается как «а импликация Ь» или «из а следует Ь».

Для функции импликации из лжи следует все что угодно, а из истины только истина (см. табл. 3.1). Соответствует «если а, то Ь», «а является достаточным условием для Ь». Запись а <— Ь соответствует «если Ь, то а», «а является необходимым условием для Ь».

Жегалкинское сложение а © Ь.Запись читается как «а сложение по Жегалкину Ь».

Операция истинна тогда и только тогда, когда значения переменных различны (см. табл. 3.1). Соответствует «а либо Ь», «либо а, либо Ь», «или а, или Ь».

Эквивалентность а <=> Ь. Запись читается как «а эквивалентно Ь». Операция истинна тогда и только тогда, когда значения переменных совпадают. В русском языке соответствует выражению «тогда и только тогда, когда».

Алгебра высказываний представляет собой совокупность

5= <{0, 1}, {&, V, ,—»,<=>}>,

где носитель алгебры представляет собой множество высказываний {О, 1}, в ее сигнатуру входят операции конъюнкция, дизъюнкция, отрицание, импликация и эквивалентность.

Основные законы алгебры высказываний можно разбить на три группы (табл. 3.2):

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

интересует только истинность или ложность высказывания. Каждое

Таблица 3.2

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

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

Таблица 3.3

Таблица формализации высказываний

При формализации высказываний русского языка можно дать

несколько рекомендаций:

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

Задачи

Задача 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 год с прибылью, если известно, что:

• • «Если остались без прибыли А или С, то В — с прибылью»;
• • «Неверно, что А с прибылью, если В без прибыли».