Полная версия

Главная arrow Математика, химия, физика arrow Дискретная математика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Элементы математической логики

Моделирование высказываний

Согласно одному из самых распространенных определений, логика есть анализ методов рассуждений. Изучая эти методы, логика интересуется в первую очередь формой, а не содержанием доводов в том или ином рассуждении. Логику не интересует истинность или ложность отдельных посылок или заключений, она лишь желает знать, вытекает ли истинность заключения из истинности посылок. Одна из основных задач логики - систематическая формализация и каталогизация правильных способов рассуждений.

Математическая логика, как любая другая математическая дисциплина, предметом своего изучения имеет математическую модель, в данном случае - модель человеческих рассуждений и правил умозаключений. В содержательной логике под высказыванием понимается законченная мысль. Это может быть некоторое предложение, о котором имеет смысл говорить истинно оно или ложно, или несколько предложений, связанных между собой определенным образом. Следовательно, можно выделить элементарные высказывания (первокирпичики) и более сложные высказывания, которые по определенным правилам строятся из элементарных высказываний.

В математической логике элементарные высказывания моделируются элементами некоторого произвольного (непустого) множества М. Будем называть М множеством элементарных высказываний, а его элементы - элементарными высказываниями, и обозначать, как это принято в математической логике, большими латинскими буквами (иногда с индексами). При анализе способов построения сложных высказываний в разговорной речи можно выделить основные связки: «не», «и», «или», «если ..., то...», «тогда и только тогда,» и др. В математической модели им соответствует другое множество, элементы которого называются логическими (пропозициональными) связками. Множество логических связок включает в себя следующие связки:

«-1» - отрицание («не»),

«&» - конъюнкция («и»),

« V » - дизъюнкция («или »),

«—»» - импликация («если ..., то ...»),

«=» - эквивалентность («тогда и только тогда»).

Множество элементарных высказываний и множество логических связок никогда не пересекаются.

Заметим, что в литературе встречаются другие обозначения логических связок. Например, конъюнкцию обозначают «Л», импликацию О», а эквивалентность - «~».

Формализуем правила построения сложных высказываний из элементарных высказываний. Из множества элементарных высказываний М с помощью множества логических связок построим новое множество Ф, которое будем называть множеством логических формул. Правило построения множества Ф состоит из 3-х условий (такой способ определения называют индуктивным).

Определение 3.1. Множество Ф является множеством логических форм,у л, если выполняются следующие условия:

  • 1) всякое элементарное высказывание есть формула, т. е. МСф;
  • 2) если F и Fo - формулы (/д, /3 ? Ф), то (-иF)), (f&/3), (F V IF), (F] —? F)), (F] =F2) - формулы;
  • 3) других формул нет.

П р и м ер 3.1. Записать в виде логической формулы следующее предложение: «если целое число не делится на два, то оно нечетное».

Введем обозначения для элементарных высказываний: А - «целое число делится на два», В - «оно (целое число) нечетное». Тогда сложное предложение описывается формулой: ((-Д)—>.В). При составлении формулы мы точно следовали определению 3.1. Действительно, так как А и В - элементарные высказывания, то они формулы (условие 1 определения 3.1), следовательно по условию 2 формулами являются выражения (-ъ4) и ((-1 Л)—»/?). Однако записи (->Л—>В), (-|Д)—нельзя назвать формулами, согласно определению 3.1, так как в первой не заключено в скобки высказывание (-ь4), а во второй - целиком все высказывание ((-iA)—> В). Это противоречит условию 3 определения 3.1.

Данный пример показывает, что при записи логических формул нужно соблюдать формальные правила, сформулированные в определении 3.1. Для упрощения записи формул принят ряд соглашений. Скобки можно опускать, придерживаясь следующего порядка действий: конъюнкция выполняется раньше, чем все остальные операции, дизъюнкция выполняется раньше, чем импликация и эквивалентность. Кроме того, можно опускать внешние скобки и не заключать в скобки отрицание.

Например, формула F= (А —> (~i(CV (А&В)))), учитывая принятые соглашения, может быть записана следующим образом:

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>