Основы дискретной математики В.А. Осипова (552659), страница 5
Текст из файла (страница 5)
2. Будем употреблять следующую терминологию и символику: операцию называть умножением, а результат применения отгерацин к элементам а и 6 — произведением аЬ. Это мультипликативная терминология. Иногда естественнее и удобнее использовать вддитивную терминологию и символику: операцию называть сложением, а результат ее выполнения — суммой а+ 6 элементов а и 6. Если для любых элементов а и Ь множества М справедливо равенство а6 = Ьа, то операцию называют коммутативной,.
Коммутативны, например, сложение и умножение чисел, сложение матриц одного порядка и т. д. Некоммутативными операциями являются векторное произведение векторов, произведение матриц порядка и при и ) 2 и др. Если для любых элементов а, 6, с множества М справедливо равенство а(Ьс) = (аЬ)с, то операцию называют ассоциативной.
Ассоциативны, например, сложение и умножение целых чисел, умножение матриц, композиция отображений, а также операции, определенные таблицами Кэли табл. 1.1 и табл. 1.2. Неассоциативной операцией является векторное умножение векторов пространства. В ряде случаев множество М, на котором определена алгебраическая операция, обладает единичным элементом, т е. таким элементом е, что ае = еа = а для всех а из М. Единичный элемент единственен, так как если существует еще один элемент е' с этим же свойством, то ее' = е и ее' = е', откуда е = е'. При адцитивной записи единичный элемент называется нулевым и обозначается О.
На мнджестве квадратных матриц порядка н единичным элементом относительно операции умножения является единичная матрица, на множестве отображений множества Х в себя единичным элементом относительно композиции отображений является тождественное отображение. Число 1 есть единичный элемент множества целых чисел относительно операции умножения, а множество четньгх чисел не имеет единичного элемента относительно этой операции.
Если операция ассоциативна, то можно однозначно говорить о произведении любого конечного числа элементов, взятых в определенном порядке. Пусть дана упорядоченная система из и элементов множества М: а,1, а2, ..., а„, в которой некоторым 29 1.3. Алгебраические операции 28 1лава 1. МНОЖЕСТВА И ОТНОШЕНИЯ образом расставлены скобки, указывающие на порядок выпол- нения операции.
Теорема 1.1. Если операция, определенная на ЛХ, ассоциативна, то результат ее последовательного прилсенения к и элементам множества не зависит от расстановки скобок. Доказательство проведем индукцией по числу множителей п. Для и = 3 утверждение теоремы следует из закона ассоциативности. Докажем это для и множителей, предполагая, что для меньшего числа множителей утверждение верно. В этом случае достаточно доказать, что для любых й и 1, где 1 < й, 1 < и — 1, (а1аз ° аь)(аьч.1 ° ° о,„) = (агат ° ° а1)(а1+1 а„), так как внутри скобок расстановка их несущественна по индуктивному предположению. Для этого покажем, что обе части равенства совпадают с произведением элементов (а1аз -.а„), взятых в следующем фиксированном порядке: (.
"((а1аз)аз) а„1)а„(это произведение называется левонормированным произведением элементов а1, аз, ..., а„). Действительно, при Й = и — 1 имеем (а1а2 ап 1)а„= ( (агав) аа 1)а„, т. е. левонормированное произведение. При 1с < п — 1 ввиду ассоциативности получаем (а1аз аь)(аь+1 " а„) = = (а1ае ...аь)((аь+1 - а 1)а„) = = ((а1ат . аь)(аь1 1 . а„ 1))а„ = = ( И . (а1аз) аь)аь+1) .
. а„ 1)а„, т. е. снова имеем левонормированное произведение. К такому же виду приводится и правая часть доказываемого равенства. В силу теоремы 1.1 при записи и вычислении произведения агав. а„ скобки не ставят, а следят только за порядком множителей, и то лишь в случае, если операция некоммутативна. В частности, при а1 = аэ = . = а„= а произведение аа .а обозначают символом а" и называют и-й степенью элемента. Если множество М обладает единичным элементом, то полагают ао = е. Из теоремы 1.1 вытекают соотношения; а а"=а +"; (а"")"=а ", т,пеИ. (1.1) В адцитивной символике степеням соответствуют кратные па = а+ а+ + а и выполняются соотношения та+ па = (т+ п)а; п(та) = (пт,)а, т, и Е 1ч.
2.1, Логика высказываний Глава 2 ЭЛЕМЕНТЫ МАТЕМАТИ'ЧЕСКОЙ логики Формальная логика — это наука о формах и законах правильного мышления, аналитическая теория искусства рассуждения. Формальная логика изучает умозаключения с точки зрения их формалыиго с~роения. 1) «Все люди смертны. Сократ — человек. Следовательно, Сократ смертен»; 2) «Все граждане России имеют право на образование.
Иванов — гражданин России. Следовательно, Иванов имеет право на образование». Легко заметить, что эти умозаключения составлены, в сущности, по одной н той же формальной схеме: «Все М суть Р; Я есть М. Следовательно, Я есть Р». Содержание терминов Я, Р, Л~Х для их справедливости безразлично. Умозаключения, составленные по такой схеме, ученые-схоласты назвали силлогизмами первой фигуры по модусу Вагбага. Формальная логика просуществовала без серьезных изменений от времен Аристотеля до начала Х1Х века, практически не выходя за рамки изучения такого рода силлогических умозаключений. Но уже начиная с работ Дж.
Буля (1815-1864), можно говорить о превращении ее в математическую логику. Математическая логика (или символическая логика) — часть формальной логики, где формы мышления изучаются с помощью специального искусственного языка. Тем самым достигается большая точность формализации, систематизации принципов рассуждения, что позволяет представить логические теории в удобной форме и применить их для решения задач, труднодоступных для человеческого мышления. Математическая логика развивалась в связи с широким распространением аксиоматнческого метода в построении различных математических теорий.
Но уже с середины ХХ века аппарат математической логики стал усгешно использоваться в различных приложениях, в том числе связанных со средствами общения с ЭВМ. Формализм логического вывода взят за основу универсального языка программирования ПРОЛОГ (РНОбгаппшпб ш ЬОС1с), являющегося удобным инструментом при построении вычислительных моделей различных дискретных систем. 2.1. Логика высказываний 2.1.1. Высказывания. Логические операции. Формулы логики высказываний Под высказыванием принято понимать языковое предложение, о котором имеет смысл говорить, что оно истинно или ложно.
Высказываниями являются, например, следующие предложения: «2 х 2 = 4», «5 — простое число», «Волга впадает в Черное море». Первые два предложения истинны, а третье— ложно. Предложения «Вашингтон — столица США>, «НьюЙорк — столица США», «Царевич Дмитрий был убит по приказу Бориса Годунова» являются высказываниями, причем первое из них истинно, второе — ложно, а третье до сих пор обсуждается историками. Предложения «х + у = 4» и «Который часу» высказываниями не являются. Предложения «Город стоит на берегу реки» и «Сегодня хорошая погода> тоже не следует относить к высказываниям ввиду их недостаточной уточненности. В логике высказываний интересуются не содержанием, а истинностиью или ложностью высказываний (т.
е. их истинностным значением). Истинностные значения — истина и ложь — будем обозначать И и Л соответственно. Мнохсество 1И, Л) называется множестпвом исгпияностных значений. Грамматическими средствами в разговорном языке из нескольких простых высказываний можно составить сложное (составное) высказывание. Например, с помощью союзов «и>, «или» и отрицательной частицы «не» можно из простых высказываний «Москва стоит на берегу Невы» (ложного) и «Санкт-Петербург стоит на берегу Невы» (истинного) составить следующие сложные нысказывания: «Москва не стоит на берегу Невы», «Москва стоит на берегу Невы или Санкт-Петербург стоит на берегу Невы», «Москва стоит на берегу Невы и СанктПетербург стоит на берегу Невы».
Первые два высказывания 33 2.1. Логика высказываиий 1) еслиО=О,то1=1; 2) если0=1,то0=0; 3) если 0 = О, то 0 = 1; 4) если 0=1, то 1=2. 32 Глава 2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ истинны, а последнее — ложно. Определим логические операции над высказываниями, при которых истинностные значения составных высказываний определяются только истинностными значениями составляющих высказываний, а не их смыслом. Огарицанием высказываний Р называется высказывание, истинное тогда и только тогда, когда высказывание Р ложно.
Отрицание Р обозначается через — Р и читается как «не Р». Отрицание высказывания определяется также таблицей истинности (см. табл. 2.1). В разговорной речи отрицание соответствует составлению из высказывания Р нового высказывания, например: «неверно,что Р». Таблица 2.1. Таблица 2.2. Таблица 2.3. Конъюнкцией двух высказываний Р и Я называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания.
Конъюнкция высказываний Р и Я обозначается через РЫ~ и читается как «Р и Я». Конъюнкция определяется также таблицей истинности (см. табл, 2.2). В разговорной речи конъюнкции соответствует соединение высказываний союзом «и». Дизъюнкцией двух высказываний Р и Я называется высказывание, ложное тогда и только тогда, когда оба высказывания ложны. Дизъюнкция высказываний Р и Я обозначается через Р Ч с2 и читается как «Р или Я». Дизъюнкция определяется также таблицей истинности (см. табл.
2.3). В разговорной речи дизъюнкция соответствует соединению высказываний союзом «или» в неразделительном смысле. Из двух высказываний Р и Я можно составить высказывание «Р влечет с2» (или, иначе, «из Р следует Я», «еслн Р, то Я»). Не математик может признать утверждение типа «если 2 х 2 = 5, то Москва — столица России» ложным, поскольку для него истинность высказываний «Р влечет Я» означает, что Р по смыслу должно влечь за собой с,. Но тогда связка «влечет» зависит от смысла самих этих высказываний.
Однако практика показывает, что можно обороты типа «Р влечет с,» и «из Р следует Я» использовать таким образом, чтобы под ними каждый рез подразумевалась некоторая операция, не зависящая от смысла высказываний. Рассмотрим следующие высказывания; Первое утверждение естественно считать истинным, поскольку, используя равенство 0 = О, а также другие свойства чисел, можно вывести равенство 1 = 1 (например, прибавляя 1 к обеим частям равенства 0 = 0). Второе утверждение также естественно считать истинным: умножая на 0 обе части равенства 0 = 1, получаем равенство 0 = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
