Игошин Математическая логика и теория алгоритмов (1019110), страница 22
Текст из файла (страница 22)
Аналогично не могут быть истинными высказывания Ан ..., А . Итак, все высказывания Аь Аь ..., А ложны. Но по условию, по меньшей мере одна из посылок А,, А,, ..., А истинна. Следовательно, истинной должна быть посылка Аь Итак, высказывания Вн Си А, истинны. Тогда истинна конъюнкция В, л Си истинна импликация (В, л С) — » А„являющаяся обратной по отношению к первой данной импликации (А, л С) — » Вь Совершенно аналогично устанавливается истинность и остальных обратных импликаций (Вз л С) » Аг, ..., (В л С) — » А . П Пример 7.21. Примером применения данной общелогической теоремы могут служить следующие три утверждения а), б), е), выражающие свойство монотонности операции умножения в кольце целых чисел или в поле рациональных чисел (в правом столбце помещены обратные для них теоремы а'), б'), е'), справедливые на основании доказанной теоремы 7.20): а) х < у, г > 0 =» хг< уг; а') хг < уг, г > 0 ~ х < у б) х > у, г > 0 =» хг > уг; б') хг > уг, г > 0 =» х > у; е) х = у, г > 0 =» хг = уг; е') хг = уа, г > 0 ~ х = у.
Аналогично для следующих трех утверждений г), д), е) относительно целых чисел: г) х < у, г < 0 =» хг > уг; д) х > у, г < 0 =» хг < уе; е) х = у, г< 0 ~ хг = уг; Глава 11 БУЛЕВЫ ФУНКЦИИ Различные области математики имеют дело с разнообразными функциями. Это и действительные функции действительного аргумента, изучающиеся в курсе математического анализа, и комплексные функции комплексного аргумента, известные из теории функций комплексного переменного, и вектор-функции скалярного аргумента, играющие важную роль в дифференциальной геометрии, и скалярные функции векторных аргументов (например, скалярное и смешанное произведения векторов), и вектор-функции векторных аргументов (векторное произведение двух векторов), и функции, заданные и принимающие значения в множестве натуральных чисел (например, функция Эйлера, известная из теории чисел), и многие другие.
В настоящей главе познакомимся с еще одним видом функций — булевыми функциями. Они возникли при математической постановке задач логики. Их называют также функциями алгебры логики. и 8. Множества, отношения, функции Напомним некоторые необходимые в дальнейшем понятия так называемой наивной или интуитивной теории множеств. Понятие множества.
Понятие множества — одно из основных математических понятий. Оно первично, исходно, неопределяемо, т.е. не может быть сведено к другим понятиям. Под множеством понимается совокупность объектов (предметов), которая Рассматривается, мыслится как одно целое, как нечто единое. Объекты, составляющие множество, называются его элементами. Множества обозначают заглавными буквами латинского алфавита: А, В, С, ..., а элементы множеств — малыми латинскими буквами: а, Ь, с, ..., ан аъ а,, ... Если некоторый объект а является элементом множества А, т.е. объект а принадлежит множеству А, то пишут а е А. Если же элемент а не принадлежит множеству А, то пишут а е А. Символ е называется знаком принадлежности.
Множество, состоящее из элементов ан а„ ..., а„ обозначаетсл (аь а„..., а„). Символ (х: Я(х)) применяется для обозначения множества всех таких объектов х, которые удовлетворяют некоторому свойству 5(х). Если объекты берутся из некоторого множества А, то множество всех таких объектов, удовлетворяющих свойству Х(х), обозначается (х «А: В(х)).
Например, (х «В: х2 — х — 6 < О)— множество всех действительных чисел х, удовлетворяющих соотношению х' — х — 6 < 0 (нетрудно проверить, что это множество есть замкнутый интервал [-2, 3) числовой прямой). Включение и равенство множеств. Множество А называется подмножеством множества В, или говорят, что А включается в В, если каждый элемент множества А принадлежит множеству В. Запись: А ~ В. Множества А и В называются равными, если А состоит из тех и только тех элементов, которые принадлежат В, т.е.
если х«Атогдаитолькотогда, когдах«В. Запись: А= В. Ясно, чтоА=В тогда и только тогда, когда А с В и В с А. Множество А называется собственным подмножеством множества В, если А ~ В и А ~ В. Обозначение: А с В. Символ с называется знаком включения. Множество называется пустым, если оно не содержит ни одного элемента.
Существует единственное пустое множество, оно обозначается символом О. Значит, И <- А для любого множества А. Операции иад множествами. Обьединением множеств А и В называется множество, обозначаемое А () В, состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из множеств А и В. Таким образом, по определению А () В = (х: х «А или х «В).
Пересечением множеств А и В называется множество, обозначаемое А П В, состоящее из тех и только тех элементов, которые принадлежат как множеству А, так и множеству В. Следовательно, по определению А П В= (х: х «А и х«В). Разностью множеств А и В называется множество, обозначаемое А'~ В, элементами которого являются все те элементы множества А, которые не принадлежат множеству В, и только они. Таким образом, по определению А~ В= (х: х«А и х«В).
Если А ~ У (где У вЂ” некоторое универсальное множество, которое содержит в качестве подмножеств все рассматриваемые нами множества), то дополнением множества А в множестве У называется множество, обозначаемое А, состоящее из всех тех элементов множества У, которые не принадлежат множеству А. Итак, А = У~А= (х: х«Уи х«А) = (х«У: х«А). Перечислим некоторые наиболее важные свойства операций над множествами и отношения включения множеств: 1) А () А = А (идемпотентность объединения); 2) А П А = А (идемпотентность пересечения); 3) А () В= В() А (коммутативность объединения); 4) А П В= ВП А (коммугативность пересечения); 5) (А () В) () С = А 0 (В () С) (ассоциативность объединения); 6) (А П В) П С = А П (В П С) (ассоциативность пересечения); 7) А () (В П С) = (А () В) П (А () С) (дистрибугивность объединения относительно пересечения); 90 8) А П (В () С) = (А П В) 0 (А П С) (дистрибутивность пересечения относительно объединения); 9) А () (В П А) = А (1-й закон поглощения); 10) А П(В () А) = А (2-й закон поглощения); 11) А0 В = А П В (1-й закон де Моргана); !2) АПВ = А () В (2-й закон де Моргана); !3)А() У= У,АП У=А; 14) А () О = А, А П О = Я; 15)А0 А = У,АП А =И; 16) Й=У, У =О; 17) А = А (закон инволюции); 18)А~В=АП В; 19) АаАОВ, ВаАОВ; 20) А П В а А, А П В а В; 21) А ~ В е» А П В = А; 22)АаВ«=»А() В=В; 23) А ~ В «=» А 0 В = У; 24)А~Ве»АП В =И.
Покажем, как эти свойства доказываются с применением тавтологий алгебры высказываний, на которых они все базируются. Эти рассмотрения будут служить продолжением темы предыдущего параграфа: 1) хе АОА«»ха Архе А«»хе А. На последнем шаге применена тавтология из теоремы 3.2, ьс (Р ~ Р) <-» Р. Итак, множество А О А состоит из тех и только тех элементов, из которых состоит множество А. Следовательно, по определению равенства множеств, А () А = А; 6)хе (АПВ) П С<»ха АПВлхе Се»(хе Архе В) лхе е Се»хе Ал(хе Влхе С) «»хе Архе ВП С«»хе А П(ВП С). Использована тавтология из теоремы 3.2, г: ((Р л Ц) л Я) «-» (Р л л(Дл Я)); 9) хе АО(ВПА) е»хе А ~хе ВПА <»хе А~(хе Влхе А) «» «» х е А.
Использована тавтология из теоремы 3 2, сс (Р ч (О л Р)) «+ «-» Р; 11) хе А О В «:» хи А() В«=»-(хе А() В) «=»-(хе Архе В) «:» «=» (хе А)л (хе В) е»хя Алхан Ве»хе А лхе В «=»хе А П В. Использована тавтология из теоремы 3.2, лс: — (Р ~~ Д) «-» ( — Р л о -~Д)' 20) хе АП В«=»хе А лхе В~хе А. Использована тавтология из теоремы 3.2, ж: (Р л Д) -» Р; 21) А П В= А «» А П В а А л А а А П Ве» «=» (х е А П В -> х е А) л (х е А — » х е А П В) «=» «=» ((х е А л х е В) » х е А) л (х е А » (х я А л х е В)) «=» «=» 1 л (х е А — » (х е А л х е В)) «=» «-»хе А-»(хе Алхе В) с=»-(хе А) ~~(хе Алхе В) «=» 91 с=> ( — (х е А) ~ х е А) н ( -1(х а А)»~ х е В) с=» «:»1н(-,(хв А) ~хе В)<=»(хв А»хе В) е:»А~В.
Проанализируйте приведенную цепочку рассуждений и выявите использованные тавтологии. Бинарные отношения и функции. Пусть даны два (не обязательно различных) множества А и В. Выберем элементы а е А и Ь е В. Упорядоченной парой, составленной из элементов а и Ь, называется пара (а, Ь), в которой указано, какой элемент является первым, а какой — вторым.
Таким образом, упорядоченная пара (Ь, а) отлична от упорядоченной пары (а, Ь), если ни Ь. Упорядоченные пары (а, Ь) и (е, е() называются равными, если и только если а = с и Ь = Ы. Прямым (или декартов»ям) произведением двух множеств А и В называется множество А х В всевозможных упорядоченных пар (а, Ь), таких, что а в А и Ь е В: А х В = ((а, Ь): а в А и Ь в В). Бинарным отношением между элементами множеств А и В называется любое множество упорядоченных пар (а, Ь), таких, что а е А и Ь е В, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
