Главная 
Математика, химия, физика Дискретная математика. Сборник задач
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
МАТЕМАТИЧЕСКАЯ ЛОГИКААлгебра высказываний Теоретические сведенияПростое высказывание представляет собой некоторое повествовательное предложение, которое может быть либо истинно, либо ложно, но не то и другое одновременно. Простое высказывание обозначается маленькими латинскими буквами а, Ь, с и т.д. Высказывания, которые получаются из простых с помощью грамматических связок «и», «или», «не», «тогда и только тогда», «либо... либо...», «если... то...», называются составными или формулами алгебры высказываний. Формулы алгебры высказываний обозначаются большими латинскими буквами А, В, С и т.д. Всегда истинная формула А называется тождественно истинной формулой или тавтологией, А - 1. Всегда ложная формула В называется тождественно ложной формулой или противоречием, В= 0. Рассматривая высказывания, мы абстрагируемся от их смысла, нас интересует их истинность или ложность. Мы пишем а = 1, если а — истинно, и а = 0, если а — ложно. Рассмотрим основные операции над высказываниями:
Значение истинности для каждой логической операции в зависимости от истинности ее операндов описывается таблицей истинности. Таблица истинности представляет собой таблицу, устанавливающую соответствие между возможными значениями наборов переменных и значениями операций [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. Полученная конъюнкция истинна тогда и только тогда, когда все ее сомножители истинны, т.е. каждый сомножитель должен быть равен единице:
Таким образом, получаем, что А — без прибыли, В — с прибылью, С — с прибылью. Задача 3.4. Даны три высказывания: А — «Идет дождь»; В — «Ветрено»; С — «Ясно». Формализовать следующее сложное высказывание: «Неверно, что ясно бывает тогда и только тогда, когда дует ветер или идет дождь». Задача 3.5. Даны три высказывания: А — «Идет дождь»; В — «Ветрено»; С — «Ясно». Формализовать следующее сложное высказывание: «Ясная погода является необходимым условием для отсутствия дождя или отсутствия ветра». Задача 3.6. Даны три высказывания: А — «Идет дождь»; В — «Ветрено»; С — «Ясно». Формализовать следующее сложное высказывание: «Ясная погода является необходимым и достаточным условием для отсутствия дождя или отсутствия ветра». Задача 3.7. Даны три высказывания: А — «Идет дождь»; В — «Ветрено»; С — «Ясно». Формализовать следующее сложное высказывание: «Ясная погода является достаточным условием для отсутствия дождя или отсутствия ветра». Задача 3.8. Определить, какие высказывания являются ложными:
Задача 3.9. Для того чтобы логическое выражение (а & а)/(Ь & Ь) при любых значениях логических переменных а и Ь всегда принимало значение «ложь», вместо / нужно поставить следующую функцию алгебры высказываний .... Задача 3.10. Для того чтобы логическое выражение (а & а)/(Ь V Ь) при любых значениях логических переменных а и Ь всегда принимало значение «ложь», вместо / нужно поставить следующую функцию алгебры высказываний .... Задача 3.11. Записать в символическом виде и вычислить, кто из трех предпринимателей — А, В, С — закончил 2016 год с прибылью, если известно, что:
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| << | СОДЕРЖАНИЕ | >> |
|---|
