В.Н. Нефедов, В.А. Осипова - Курс дискретной математики, страница 5

Число ! есть единпчимй элемент множества цслык чисел относительно операции умножения, а множество четных чисел не имеет единичного элемею та относительно этой операции. Если операция ассоциативна, то можно однозначно говорить о произведении любого конечного числа элеммпоц взятык в определенном порядке. Пуси дана упорвдочеиная система нз л элементов множества М:аь аь..,, а„, в которой пекоторыи образом расставлены скобки, уяазываюшне иа порядок выпал- пения операции.

Теорема О.1. Если операция, определенная иа М, ассоциагиеиа, то рсэульгог ее лосладоеагельлсео иримелеиил к л элементам млотесгза яе зависит от расстановки скобок. Доказательства проведем индукцисй по числу множителей л. Для л = 3 утверждение теоремы следует нз закона ассоцн»- гивностн. Допажеы зто Лля и множителей, предполагая, по для менынего числа множителей утверждение верно. В этоы случае достаточно доказать, что для любых * н 1, где 1 ы;й, !(ю — 1. (аг...аь)(оь г...а )=(аг...аг)(агт ...а,], так нак внутри скобок расстановка их несущественна по индуктиввому предположению.

Для этого покажем, что обе части равенства совпадают с произведением элементов аь..., а„, елятых в сиедующем фиксированном порядкег (... ((агат)аэ) ... а ы)а„ (это произведение называется левовормироаанным пронзведе. пнем элементов аь..., а ). Действительно, при й и†1 имеем (аг... а ~)а (... (а,аа) ... а„,)а,. т. е. левонормнрованное произведение. Прн й < и†1 авилу ассоциативности получаем (аы ., аь) (иь+г ...

а„] (аг ... аь) ( (аэ+~ .. а -ч)и ) ((а, ... а,) (аь+г ... а„ ,)) а„ ( ... (( ... (а,от) ...ал)аьы) ... ... а„,)а„, т. е. снова имеем левонормировавпое произаедеине. К такому же виду приводится и ираваи часть доказываемого равенстеа. В силу теоремы 0.1 прн записи н вычислении произведения а,... а„ скобки не ставят, а следят только за порядком мно. жителей, н то лишь в случае, если операция иекоммугетивиа. В частности, прн а~ = аз ...

а а произведение аа... а обозначают символом а" н называют л-й степенью элемента. Если множество М обладаег единичным элементом, то полагают аз е Иэ теоремы 0.1 вытекают соогиогнения .а а" а '"; (а )" =а, лп лтД [0.1] В адднтнвной символике степеням соответствуют кратные тю а+а+... +а в выполняются сгютногпеиия та+па (т+л)а; л(та) = (кт)а, иь лтИ. 22 ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ ГЛДВД 1 Математическая логика — современной вид формальнорг логики, т.

е. науки, изучающей умоааключсння с точки зрения нх формального строения. Рассмотрим следующие два умозаключения: 1) «Все люди смертны. Сократ — человек. Следовательно, Сократ смертенэ; й) «Все граждане Россия имеют право на образование Иванов — гражданин России. Следовательно, Иванов имеет право иа образование». Легко заметить, что анн составлены, в сущности, по одной п той же формальной схеме: «Все М суть Р; 8 есть М.

Следовательно,а есть Р . Сопержание терминов 5. Р, М длк справедливости этик умозаключений безразлично. Умозаключения, саставлеынме по этой схеме, ученые-схоласты назвали силлогизмами первой фигуры по модусу Ба«бага. Вплоть до начала Х1Х в. формальна» логика практически вс выходила за рамки такого рода силлогических умозаключений. Однако, начиная с работ Дж. Буля, можно говорить о превращении ес и математическую логику. Особенности математической логики заключаются в ее матеыатическом аппарате, в преииРиесгвеннон внимании к умозаключениям, применяемым в самой математике. Математи нская логика — это обширная наука, которая кроме традндиоипай проблематики занимается вопрасамн оснований математики н теории алгоритмов н имеет келий ряд лриложений. 1Д.

ЛОГИКА ВЫСКАЗЫВАНИЙ 1.1.!. Высказывания. Логические связки. Жормулы летиня высказываний Под высказыванием принято понимать языковое пргдложе. нне, о котором имеет смысл говорить, что оно истинно или ложно. Высказываниями являются, например, следующие ггрекло жсиияг «дай=4», «б — простое число», «Волга впадает в Черное море». Первые два предложения истинны, а третье — ложно.

Предложения «Вашингтон — столица США», Нью-Йорк— столица США», «Царевич Дмитрий был убит яо приказу Бориса Годунова» являются высказываниями, причем первое из впх исгнвио, второе — ложно, а третье до сих пор обсуждается историками. Предложения «х-ь р 4» и «который часу» высказыванияии не являются. Предложения «Город стоит на берегу реки» и «Сегодня хорошая погода» тоже не следует относить к высказываниям ввиду ик недостаточной уточнен- кости. В логике вмсказываянй интересуются не содержанием, а лстиянасг»го или зожкосг»ю высказываний (т. е.

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

Рассмотрим также логичеспие операция (связки) вад высказываниями, прн которых стн понг ыс значения сост нных высказмваний опредслвются тмько нстнниостными значсниячи составляющих высказываний, а не их смыслом. Отрпкаиием высказываний Р называется выскаэмваниц истинное тогда н только тогда, когда высиазывание Р ложно. Отрицание Р обозначается через )Р н читается как «че Р».

Отрицание высказывания определяется тавже таблицей истинности (см. табл. 1.!). В разгоаориой речи отриканне соответствует составлению из высказывания Р нового высказывания, напрнмерг «неверно, что Р». Яз Табзв«з !.! Табзвва !.з Табаева !3 Рае О е РЧЕ И И Л Л И И Л Л И Л Л Л И Л И Л И И И Л И Л И Л И Каяъюя«Лией двух высказываний Р п Сг' называетсв выскаэыванне, нстннвое тогда н только тогда, когда нсткпны оба высказывання. Конъюнкция высказываний Р и 4«обозначается через Рй»Т н читается как «Р н ()». Канъюнкцня определяется также габлвцей истинности (см. табл. 1.2). В разговорной речи «опъюнкцнн соответствует соединение высказываннй союзом «п».

Днаъюлкцяей двух высказываний Р н !3 называется высказывание, ложное тогда н только тогда, «огда аба высказывания ложны. Днзъюнкцня высказываннй Р н 4« обозначается через Рта' й н чнтается «ак «Р ялн !«». Дязъюннцпя опрсделястгн также таблнцей нстнняостя (см. табл. 1.3). В разговорной речи днэыонкцня соответствует соединенк«» высказываний союзом «нлк» в неразделятельном смысле.

Из двух высказываняй Р и »б можно составить высказывание «Р влечет !4» (нлн, иначе, «нз Р следует !'»», «еслн Р, то !«»). Не математнк может признать утвержденне типа «если 2!!2=5, то Москва в сталнцв Рс«сян» ложным, поскольку для пега пстинвость высказываний Р влечет ()» означает, что Р по смыслу должно влечь за собой й. Но тогда связкт «влечет» зависят от смысла самих зтнх высказываннй. Однако практика показывает, что можно обороты типа Р влечет !)» н екз Р следует »;»» попользовать такнм образом, чтобы под ннмк каждый раэ подразумевалась некоторая опсрацпя, не завнсяшая ат смысла высказываний. Рассмотрям следующие высказывания! ! ) еслн О = О, то 1 = 1; 2) еслвО 1,то0=0; 3) еслпО О,таО 1; 4) еслн 0 = 1, то! = 2.

Первае утвержденне естественно с »итать истинным. паскальку, нспользуя равенство 0-0, а также другие свойства чисел, кожно вмвестн рамнство 1=1 (аапрнмер, прибавляя 1 к абмгм частям равенства 0 = О). Второе утвсржденке также естественно считать нстнннымг Умножая на О абе часты равенства 0 1, получаем рамнство 0 О. зэ Таблзкз 1.б б Р-Е И Л И И И Л И Л И Л Л И И И Л Л И Л И Л И И Л Л Определим понятие формулы логики амскаа»юаиид Алфавигои называется любое венус»ос множество. Элементы этого множества называются сьлаолали денного алфавита.

Словом в денном алфавите называется произвольная конечная последовательность символов (возможно, пустая). Слово а на. зывзется лодслоаол слове Ь, если Ь Ь,аЬ, для некоторых слов Ь~ и Ь» Алфавит логики высиэзываниб содержит слелующве символы; выскзэывзтельиые переменные Хг. Х» Хэ,. ° .; логические символы й, Т/, 1, ю,; символы скобок (,).

Слово в алфавите логики высквэывевнд называется форнблоа, если оно удовлетворяет следующему определеннюг 1) любав выскаэывательнзя переменная — формула; у) если А н  — формулы. то ( )А), (АЬВ), (АТ(В), (Аюб], (А В) — формулы; яб Третье утверждение приходится считать лажным, пбо, нсхо. дя из истинного ревенства, мы с помощью умозаключения никогда не придем н ложному.

Четвертое утверждение естественно считать нстиипымг прибавляя 1 к обеим частям равенства 0 1, получаем равенство 1 2. Таким образом, используя оборот «если Р, то М» квк логичес операцию (связку). онределим ес следующим обрезом. Имлликаяигй двух выскззывагиб Р и () называется высказывание, ложное тогдв н только тогда, ногда Р истинно, а Я ложно. Импликация высказываний Р н Ц обозначается через Рю() (илн Р=.Г)) н читается как «Р влечет ()» (илн, иначе, «если Р, то Г)», «из Р следует М»). Высказывание Р называется лосылкоб нмплнкации, а высказывание «г — эа лгочглиач имплнкации.

Импликзцив определяется гакжс таблицей истинности (см. табл. !.4). Экаивалеиииеб двух высказывания Р и () называется выскззывзвне, ястиннос тогда и тольно тогда, когда истинно«тиме значения Р н Ц совнккаюг. Эквнвзлснция высказывания Р н () обозначается через Р Гг и читается как Р эквивалентно мж Эквизалеицня определяется также таблицеб истинности (см. табл. 1.5). Таблипз !4 3) только те слова являются формуламн, для которых зто слелует нз 1) в 2). Подфорлулой формулы Л называется любое подслово А, само являющееся формулой.

Для упрощения записи будем в формуле опускать внешнее скобки н те пары скобок, без которых можно восстановнть эту формулу, сслн пользоваться следующим празвлом: каждое вхождение знака -1 относятся к наикратчайшей подформуле, следующей за ннм. Пример 1.1. Слово 1ХгйХз) юХ 1Хг нс является формулой, а слова ( (Хг~Хз))/Х» (Хг Хз) ю )Хз — формулы. Слова Хг — Хз, )Хь Хь Хь Хз — подфорыулы последней формулы.

Принцип математнческой нндукцнн, который будем использовать и рассужденнях, формулируется слелующвм образомг если какое-то зысказмванне РЯ, завнсящес от натурального параметра Г, доказано для 1 О в прн произвольном 1 удается нз пстннностн Р(1) обосновать истинность Р(Г + !), то Р(1) нстянно для всех Г, Будем применять также н другую формулнровну этого првнцнпаг еслн Р(Г) истинно прн Г = О н для юобого 1 нз нстзнносгнр(з) пря всех з (1 следует истинность Р(1+ 1). то Р(Г) нстпшю для всех б Применительно к высказывательпмм форыулач прнвцпп математической пндукцнн можно сформулировать следующим образом: еслн накое-го утверждение Р(ГИ завнсяшее от параметра Р, который пробегает вге множество высказывательнмх формул, нстянво для всек формул, не содержащих логвчссккх символов (т. е. формул вида Хг), я прн любам натуральном л «з тога, что Р(Р) нстннно для зсек формул Г с числом логнчссквх снмволов меньше л, следует, что Р(Р) нстннно лля всех формул с л логнческнмп символами, то Р(Р) нстннно для всек формул Р.