Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 29
Текст из файла (страница 29)
2.83. Введено следующее исчисление (исчисление Лукасеаича): множество парнов состоит ив бесконечного числа букв и аналое —, -+. Правила образования формул: все буквы есть суть формулы; если ~р — фор- мула, то 1э — такие формула; если ~р и ф — формулы: то у -э ф — такие формула. Система аксиом слецуюшзя: (А -э В) -+ ((В -э С) -+ (А -+ С)); (А -э э+А -+А;А-+(Аэв). праведлнвы правило подстановки и правило ааключепия.
Докавать, что в исчислении Лукасевнча выводима формула А -+ А. 2.84. Исчисление задано следующим абрааом (исчисление Паеикаэа): мно- Люстио термов состоит иа бесконечного числа букв и аваков ч, Л, -+, Правила образования формул: а) все буквы суть формулами б) если я — формула, то я — такие формула; в) если я и д — формулы, то а ч ~3, а Л33, сг -+ 33 — такие формулы.
Система аксиом состоит иэ следующих одиннадцати аксиом: 1) А э (В -э А); 2) (А-э (В -+ С)) -+ ((А-+ В) -+ (А-+ С)); 3) Алв- А; 4) Алв-эв; 6)(А-+в)-+ ((А- с)-+А-э(влс>); б) А -+ А ч в; 7> в э А ч в; 8> (А -+ с> - ((в -+ с> - (А ч в) с); 9)(А-+В)-+(А-эВ); 10)А-+А; 11)А-+А.
В качестве правила вывода испольауются правило подстановки и правило йкключеиия. Доваэвть, что система звеном является непротиворечивой, 3.68. Доказать, что авсиама 9) в исчислении Новикова является независимой по отношению ко всем остальным этого исчясления. 2.86. Пусть предиваты >Ч(х), С(х), Р(х), П(х), г1(х), Д(х, у) имеют са- (ВЬстсгвенно смысл: х — натуральное число, х — целое число, х — простое Кисло, х — полаяительное число, х — этнос числа, х делит у. Сформулировать Вмысл следующих формул узкого исчисления предикатов (и укааать, какие иа эйгх являются таидественно истнннымн): ц (ч >(>ч( ) -+ с( )); 2) (Чх)(С(х) э (х) ч (х)); 3) (Чх)(ху) (С(х) л С(у) -+ Д(х, у)); 4) (Эх)(Р(х) л (х)); б) (Чх)(с(х) л П(х) -э >Ч(х)). З.ВТ.
Описать мнояество истинности следующих двуместных предикатов, определенных на мноиестве дейстюпельиых чисел: хз — уз=0; (х>0)Л(у<0); (х>0)-+(у<0). 3.86. На мноиестве М определены однамесп|ые предикаты Р(х) и С(х). ЗВкаим условишг удовлетворяют области нх истинности, если истинны: 1) (Ч >(Р(х) +а( >) л(Зх)(Р(х) лс(х)); 2) (У )(Р( ) л С(*)) л(Бх)(Р( ) -+ а( ))т 3.88. Доказать эквивалентность следующих формул: а) з(х)Р(х) и Ч(х)Е(х); 156 Гл. 2. Машемашическал логика б) Ч(х)(Р(х) -+ А) и 3(х)(р(х) -ь А); в) Ч(х)(А -+ Р(х)) и А -+ Ч(х)г(х).
9.90. Докааать эквивалентность формул: а) В(х) (А А Е'(х)) и А л В(х)Р(х); б) В(х)(г (х) ч С(х)) и В(х)(г(х) -+ А); з) Ачч(х)Р(х) и Ч(х)(А ч Г(х)). 9.91. Установить, как монна построить теорию нормальных форм в исчислении предикзтоа, В 2.12. Комментарии Математическая логика — это аналпв методом рассуидений, при этом в первую очередь исследуются формы рзссуидений, в не их содериание.
Формалиаапия рассуидений восходит к Аристателю. Современный зид аристотелеза (формальная) логика приобрела з середине Х1Х века в работах профессора Казанского университета Платона Порепкого (1844 г.), Диордиа Буля и Августа де Моргана (1847 г.). Математическую логику иногда называют логистикой (школе Рассела). В становление логики внесли большой аплод и другие ученые того временин: Эрнст Шредер, Диуаепве Пеано, Дион Вени, Александр Макфарлейи. Интенсивно математяческая логика развивалась з 80-годы нашего столетия в связи с бурным развитием пнфровой техники.
В 1910 г. русский физик П. Эренфест указал иа возмоиность применения логики аыскааызапий для описания переквючательных делей в телефонной связи. В 1938-1940 гг. почти одновременно поаанлись рабаты советского ученого В,И. Шестакова, американского ученого Шеннона и яюшских ученых Накашнмы и Ханаевы о применеяии математической логики в пифрозой технике.
В 1981 г. в СССР была принята в эксплуатапию первая з Европе вычислительная машина — МЭСМ (малая электронная счетная машина), разработанная под руководством С.А. Лебедева. Первая монография, посвященная использованию математической логики при проектировании пифровой аппаратуры, была опубликована з СССР советским ученым М.А. Гавриловым в 1950 г. Пля углубления знаний по математической логике рекомендуем [8, П, г4, зо).
Прирола говорит языком математики: буквы этого яаыка — круги, треугольники и яные математические фигуры. Г. Галилей Глава 3 ТЕОРИЯ ГРАФОВ И МОГРАФОВ В 3.1. Взвешенный граф и его матричное задание Выше понятие графа было определено как совокупность множества вершин У н дуг Уг С Уг.
Дуга и, соединенная с вершиной и, называется икцидекшкой вершике а, а вершина а — коикцидекгякой дуге и. В дуге (о<, о ) вершины и; и о. называются гракичкыми, причем и; — начало, иу — конец дуги. Для учета изолированных вершин, т. е. вершин, не коиицидентиых ии одной дуге, расширим понятие грчфа С до совокупности вида С = (У, сггг, сггг), сггг С У, (Уг С У, где уиарное отношение Уг определяет изолированные вершины, (/г — дуги. При удалении дуг из графа С = (У, (У1, (Уг) получаем частич,ный грауу С' С С, С' = (У, туг, суг), туг С (уг, графа С; при удалении вершин и инцидентных им дуг получаем иодграф Сл = (Уо, (У1", сУг), Уа С У, Ц' С сУ1, (Угл С (Уг, графа С; при дальнейшем удалении дуг из подграфа Са графа С получаем часгяичкый иодграф С = (У, (У1, (Уг) графа С.
Две дуги, и и ид, называются смежными, если они инци::деитны одной и той же вершине. Две вершины, о, и оь, называются смежными, если они соединены дугой. Множество вершин, смежных с вершиной о„называются ее .окресогкосатью и обозначается 0(о ) или Г(о„). Используя по'нятие окрестности, граф определяют как совокупность множества 'вершин и множества их окрестностей: С = (У, Г). Определим понятие взвешенного графа. Сопоставим каждой вершине од б У (У = (о;/ у = 1,2,...,и~) графа С = (У, (гг, (уг) вес иц из множества весов )У = (иц/ з = 1,2,...1. В результате получим множество взвешенных вершин ((о;, шг)/ т = 1, 2,..., иу; Ври атом ие обязательна, чтобы все веса были различными. Сопоставим каждому злементу множества (Уг — — (и;/ т = 1, ...
°, тлу вес р; из множества весов Р = (р;/ т = 1, 2, ...). В результате получим множество взвешеккых дуг ((и;, р;)/ 1 = 1, 2, ... 13.1. Взвешенныа граф и его мвнеричное задание 189 Гл. 3. Теория графов и могрвфов 158 Рассмотрим логическую схему, реалнзуюшую сложение по модулю 2 Дх1, хт) = хг 9 хз в базисе Шеффера Р (а,,д) = а1~ д (рис. 3.1, а), и соответствующий ей взвешенный граф С = ((К И~), У), вершины которого и1, ит, о;, е = 3, 4, 5, 6, н ит взвешены переменными хг, гт, функциональной переменной 1о элемента кв к«1 Фш к| «2 А =[аф Рис. 3.1 11, где а+= ( "='10 Шеффера и функциональной переменной у соответственно. Начало дуги соответствует переменной х1, хт или выходу элемента Шеффера, конец дуги — входу элемента Шеффера или функциональной переменной у. Тогда граф С = ((1к, И'), У) (рис. 3.1, б), Определяющий эту логическую схему, задается матрицами рассмотренного класса как А(С) = ИГ(С)— И'(С) = Класс матриц смглености.
Матрица смежности Я = [г;Д„к„ ~евзвешенного графа определяется следующим образом". 1, если(оми)сУ, О, еслн (ом о ) 1с еУ. 3 ~~ | ! | | ~ ~ | ~ 1 1 ~~ |~ р, О О ... О 0 рт 0 ... 0 Р(С) = 0 0 0 ... р ..., т); при этом не обязательно, чтобы все веса были различными. Множества взвешенных вершин и дуг определяют в совокупности взвешенный граф С = ((Р, И~), (У, Р)), Р = У 11 Уг, который, строго говоря, является уже не графом, а функцией, определенной на вершинах н дугах графа. Для задания графов существует несколько классов матриц, основные из которых — класс матриц инцнденций и класс матриц смежности.
Рассмотрим этн классы матриц. Класс матриц инциденций, Если граф С содержит я вершин и т дуг, то матрица ннцнденцнй А(С) = [а;1) „„определяется как 3 1, если вершина о — начало дуги и;, а; = -1, если вершина о — конец дуги и;, О, если вершина о не коннцидентна дуге иен Иногда граф содержит петли, т. е. дуги вида (о;, тц).
В этом случае некоторые элементы матрицы А одновременно равны н 1, и -1, что приводит к неоднозначности элементов матрицы А. Для задания графа с петлями нрасщепнмн матрицу А на две матрицы, А+ и А (А+ — начальная, А — конечная матрица ннцнденций): если вершина и является началом дуги и;, в противном случае; А =[а,,) 1, если вершина о является концом дуги и;, где ~11 0 в противном случае. "" =(' Если граф без петель, то А = А+-А . Матрицы А+ и А описывают граф без учета весов вершин и дуг. Зададим веса вершин графа С в виде столбцовой матрицы а веса дуг — в виде диагональной матрицы порядка т Матрицы А+, А, И', Р полностью описывают взвешенный граф. 1 0 0 -1 1 0 -1 0 0 1 -1 О 0 1 0 0 0 0 1 — 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 -1 0 0 0 -1 0 1 -1 0 0 1 -1 Х1 йг 'Рш 'Рш 'Рш Уш У Э 3.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
