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

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

Суждения в математической логике называют высказываниями или логическими выражениями. Для обработки логических выражений в математической логике была создана алгебра высказываний или алгебра логики.

Помимо алгебры высказываний, мы предлагаем также алгебру Буля и совершенные формы представления логических функций [1-6, 11].

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

Основным понятием математической логики является «простое высказывание».

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

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

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

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

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

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

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

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

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

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

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

Таблица 3.1

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

а

ь

о V Ь

а & Ь

а

а —> Ь

а® Ь

а <=> 6

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). Соответствует «а либо Ь», «либо а, либо Ь», «или а, или Ь».

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

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

Рассмотрев высказывания и основные операции над ними, мы можем определить алгебру высказываний. Под алгеброй понимается совокупность = <М, 0>, где М представляет собой множество элементов, на котором задан конечный набор операций О = {Ох, 02, ..., Оп}. В этом случае говорят, что М — носитель алгебры и О = = {0, 02,..., Оп} — сигнатура алгебры.

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

$ = <{0, 1}, {&, V, ,—>,<=>}>,

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

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

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

внимание, как они похожи на законы алгебры Кантора!

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

1

Х&Х = Х,ХУХ = Х

Законы идемпотентности

2

X & 1 = X, X V 1 = 1,

х&0 = 0,ху0 = х

Законы работы с 0 и 1

3

х & х = 0

Закон противоречия

4

X V X = 1

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

5

X = *

Закон снятия двойного отрицания

6

X & (х V у) = X ,

X V X & у = X

Законы поглощения

7

х <=> у = (х —» у) & (у —> х)

Эквивалентность через импликацию и конъюнкцию

8

х —> у = х V у

Эквивалентность через импликацию и конъюнкцию

9

X © у = (х —> у) V (у —> х)

Жегалкинское сложение через импликацию, отрицание и дизъюнкцию

10

X V у = X & у

Отрицание дизъюнкции через конъюнкцию отрицаний

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)

Дистрибутивность дизъюнкции относительно конъюнкции

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

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

Рассмотрим несколько примеров.

Союзы и частицы

естественного языка

Операции алгебры высказываний

Примеры

«а» и «Ь»

а & Ь

Погода ясная и дождливая

«о» или «Ь»

а V Ь

Ясная или дождливая погода

«с» либо «Ь»

с © Ь

Будет ветрено либо дождливо

Не «а»

а

Неверно, что погода ясная, погода пасмурная

«а» достаточное условие для «Ь»

а^>Ь

Ясная погода является достаточным условием дождливой погоды

Если «а», то «Ь»

а —»Ь

Если погода ясная, то будет дождь

«а» необходимое условие для «Ь»

Ь —> а

Ясная погода является необходимым условием дождливой

погоды

«а» тогда и только тогда, когда «Ь»

а <=> 6

Ясная погода бывает тогда и только тогда, когда идет

дождь

«а» либо «Ь»

а ®Ь

Погода будет ясной, либо дождливой, либо ясная погода

Или «а», или «Ь», но не оба

а® Ь

Или сегодня погода будет ясной, или дождливой, но не ясной с дождем

Задача 3.1. Формализовать следующее высказывание: «Неверно, что идет дождь либо ветрено и холодно».

Решение.

Выделяем простые высказывания и заменяем их буквами: «Идет дождь» — Л «Ветрено» — В; «Холодно» — С.

Наше высказывание приобретает вид: «Неверно, что А либо В и С».

«Неверно» соответствует отрицанию и должно применяться ко всей формуле; «либо» соответствует жегалкинскому сложению между И и «В и С», «и» — конъюнкции между В и С. Для правильного порядка применения операций конъюнкцию нужно заключить в скобки.

Таким образом, правильно построенная формула имеет вид А ®(В & С).

Задача 3.2. Формализовать следующее высказывание: «Отсутствие дождя есть необходимое условие для безветренной или холодной погоды». Решение.

Выделяем простые высказывания и заменяем их латинскими буквами: «Отсутствие дождя» — А; «Безветренная погода» — В; «Холодная погода» — С.

Наше высказывание приобретает вид: «А достаточное условие для В или С».

Самой старшей операцией будет «достаточное условие», т.е. импликация из А в «В или С». Таким образом, правильно построенная

формула для данной задачи имеет вид А —> V С).

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

Для решения логических уравнений или систем логических уравнений рекомендуем порядок действий:

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

Задача 3.3. Записать в символическом виде и вычислить, кто из трех предпринимателей: А, В, С — закончил 2016 год с прибылью, если известно, что:

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

Решение.

Выделяем простые высказывания и заменяем их буквами: «А с прибылью» — А; «В с прибылью» — В «С с прибылью» — С.

Формализуем первое сложное высказывание: В —> А.

Формализуем второе сложное высказывание: А V С —> В. Построим конъюнкцию высказываний и приравняем ее единице, так как должны быть истинными одновременно оба логических высказывания: —> А) & V С —> В) = 1.

А) & (А V СВ) = (В V А) & (А V С V 5) =

= Я&Л&(ЛмСуД) = 1.

Полученная конъюнкция истинна тогда и только тогда, когда все ее сомножители истинны, т.е. каждый сомножитель должен быть равен единице:

  • В = 1;
  • А = 1;
  • • ЛмСм? = 0мСм0 = С=1.

Таким образом, получаем, что Л — без прибыли, В — с прибылью, С — с прибылью.

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

 
< Пред   СОДЕРЖАНИЕ     След >