Игошин Математическая логика и теория алгоритмов (1019110), страница 43
Текст из файла (страница 43)
14 (законы коммугативности для кванторов). Следуюи1ие формулы логики предикатов являются тавтологиями: а) (~х)(Му)(Р(х, у)) <-э ('бу)('гх)(Р(х, у)); б) (ЗхНЗуНР(х, у)) с-+ (ЗуНЗхНР(х, у)); в) (ЗуНЧхНР(х, у)) -+ (»хНЗуНР(х, у)). Доказательство. Тождественная истинность первых двух формул достаточно очевидна (проверьте самостоятельно). Предположим, что формула в) — не тавтология. Тогда существует такой предикат А(х, у), определенный на множествах М, и Мг, что высказывание (ЗуНЧхНА(х, у)) -э ('ФхНЗуНА(х, у)) ложно.
Импликация ложна, если и только если 2.[(ЗуН'ФхНА(х, у))] = 1; Х[('ФхНЗуНА(х, у))] = О. 17б Из соотношения (1) по определению квантора существования следует, что предикат (от у) (чх)(А(х, у)) выполним, т.е. ),1(чх)(А(х, Ь))) = 1 для некоторого Ь е Мь Последнее, по определению 20.1 квантора общности, означает, что предикат А(х, Ь) тождественно истинен на Мь Следовательно, тождественно истинным на М, будет и одноместный (от х) предикат (Эу)(А(х, у)). Но тогда, по определению квантора общности„Х(('Фх)(Бу)(А(х, у))) = 1, что противоречит соотношению (2). Следовательно, данная формула — тавтология.
Теорема доказана. П Во всех доказанных тавтологиях предикатные переменные нульместны, одноместны или (в последней теореме) двухместны. Сохранится ли тождественная истинность этих формул, если считать, что входящие в них предикатные переменные зависят от произвольного числа предметных переменных? Положительный ответ содержится в следующей теореме. Теорема 21.15. Если в тавтологиях теорем 21.9 — 21.14 считать, что предикатные переменные зависят от произвольного конечного числа предметных переменных, то полученные 4юрмулы будут также тавтологиями логики предикатов.
Доказательство. Придоказательстветеоремы 21.12ужебыла предпринята попытка к расширению смысла приведенных там тавтологий: под предикатной переменной Ц понималась и-местная предикатная переменная Д(ун уп ..., у„). Можно было бы и под одноместной предикатной переменной Р(х) понимать т-местную предикатную переменную Р(х„хп ..., х ), а квантор общности рассматривать по хп считая, что х, не входит в число предметных переменных предикатной переменной 0(уп у„ ..., у„). Докажем, например, тождественную истинность формулы из теоремы 21.11, в, считая Р т-местной предикатной переменной Р(х„ х,, ...,х„), а Π— и-местной предикатной переменной О(уп у„..., у,).
Причем пусть х, не содержится среди предметных переменных у„уп ..., у„, хотя некоторые (или все) из переменных хп ..., х могут содержаться среди переменных у„уп ..., у„. Итак, требуется доказать тождественную истинность формулы (чх!)(Р(хп хп ..., хщ) ч Ц(уп Рп ...> уд)) <-» с-+ ('Фх,)(Р(хн х,, ..., х )) ч Ц(уп уп ..., у„). (1) Подставим вместо предикатных переменных Р и Ц конкретные предикаты А(х„хп ..., х ) и В(уь уп ..., у„), определенные на множествах М,, М„..., М и Жп Фп ..., Ф„соответственно.
Получим (т — 1 + и)-местный предикат (Ъх,)(А(хп х,, ..., х„) ч В(у„у,, ..., у„)) с-» +-» (»Ух,)(А(хн хь ..., х„)) ч В(у„уп ..., у,), (2) определенный на множествах М„..., М, 1чь Ф„..., 1ч'„(в случае, если некоторые переменные х,, ..., х„встречаются среди пере- 177 менных уь ун ..., у„, «местность» полученного предиката будет меньше). Докажем тождественную истинность данного предиката, Для этого проверим, что он превратится в истинное высказывание для произвольных элементов ан ..., а, Ьь Ь,, ..., Ь„множеств М„..., М, ЬГь Фь ..., У„соответственно.
Действительно, Рассмотрим одноместный (от х,) предикат А(хь аь ..., а„), определенный на множестве М, и полученный из предиката А(х~, хь ..., х ) в результате подстановки вместо предметных переменных хь ..., х элементов аь ..., а соответственно, и высказывание В(Ь„Ьь ..., Ь„). Подставим их в тавтологию теоремы 21.11, в вместо одноместной предикатной переменной Р(х) и нульместной предикатной переменной Д соответственно. Получим истинное высказывание ('Фх~НА(хн ан ..., а ) «В(Ь„Ьн ..., Ь„)) <-> +-э (Чх,НА(хн аь ..., а )) ~~ В(Ь„Ьн ..., Ь„). Это же высказывание получится, если в предикат (2) подставить вместо его предметных переменных х,, ..., х, у„уь ..., у„ элементы аь ..., а, Ьн Ьь ..., Ь„соответственно.
Итак, любые предикаты превращают формулу (1) в тождественно истинный предикат. Следовательно, эта формула — тавтология. П Замечание 21.1б. В распространении взгляда на тавтологии, выраженного в теоремах 21.9 — 2!.14, можно пойти еще дальше: считать, что буквы Р и (З представляют собой произвольные формулы логики предикатов, а не просто и-местные предикатные переменные (представляющие собой на основании определения 21.1 так называемые элементарные или атомарные формулы). Получаемые формулы также будут тавтологиями логики предикатов. Рекомендуется самостоятельно проделать пропущенные доказательства тождественной истинности формул логики предикатов в теоремах настоящего параграфа.
Такая работа позволит глубже проникнуть в сущность понятий «для всех» и «существует», научит различать их и выделять в математической практике. Эти знания и навыки будут способствовать более отчетливому осознанию будущими учителями математики природы математических понятий, строения доказательств математических теорем, образованию значительного пласта логической и общематематической культуры. 5 22. Равносильные преобразования формул и логическое следование формул логики предикатов Понятие равносильности формул. Оиределение 22.1. Две формулы, Ги Нлогики предикатов называются равносильными на множестве М, если при любой подстановке в эти формулы вместо 178 предикатных переменных любых конкретных предикатов, определенных на М, формулы превращаются в равносильные предикаты. Если две формулы равносильны на любых множествах, то их будем называть просто равносильными.
Равносильность формул будем обозначать так: Р и Н. Приведем пример двух неравносильных формул логики предикатов. Покажем, что (ЧхНР(х) г 0(х)) Ф (ФхНР(х)) г('с~хН (г(х)). В самом деле, подставим вместо предикатных переменных Р(х) и 0(х) конкретные предикаты А(х) и В(х), определенные на множестве Ф соответственно, где А(х) есть «х — четно», а В(х) есть «х — нечетно».
Тогда левая формула превратится в высказывание (нульместный предикат) «каждое натуральное число либо нечетно, либо четно», которое истинно. Правая формула превращается в высказывание (нульместный предикат) «либо каждое натуральное число четно, либо каждое натуральное число нечет- но», которое ложно. Нетрудно понять на основании определений 22.1 и 21.6, что формулы Г и Н равносильны тогда и только тогда, когда формула Р «-э Н является тавтологией: Г =- Н «» ~ Г <-> Н. Это замечание вместе с теоремами 21.9 — 21.!4 позволяет указать наиболее важные примеры равносильных формул (см.
Задачник, М 9.49). Как и в алгебре высказываний, можно заменять одну равносильную формулу другой. Переход от одной равносильной формулы к другой называется равносильным преобразованием исходной формулы. В процессе равносильных преобразований формул логики предикатов могут использоваться равносильности, известные из алгебры высказываний. Приведенная форма для формул логики предикатов. Равносильные преобразования позволяют приводить формулы к тому или иному более удобному виду. Один из таких'видов носит название приведенной формы. Определение 22.2. Приведенной формой для формулы логики предикатов называется такая равносильная ей формула, в которой из операций алгебры высказываний имеются только операции —, и, », причем знаки отрицания относятся лишь к предикатным переменным и к высказываниям.
Теорема 22.3. Для каждой формулы логики предикатов существует приведенная форма. До к а за те л ьс т в о. Проведем доказательство методом математической индукции по числу логических связок в формуле (включая кванторы общности и существования). Если формула не имеет логических связок, т.е. является атомарной, то она сама имеет приведенную форму.
Предположим, что всякая формула, содержащая не больше lс-1 логических связок, обладает приведенной формой. Покажем теперь, что приведенной 179 формой обладает также и всякая формула, содержащая 1г логических связок. Пусть à — такая формула. Тогда, на основании определения 21.1, она имеет олин из следующих видов: —,Гь (Г, л Гг), (Г~ ч Гг) (Гг -+ Г,), (Г, с-э Гг) (гчНГ,), (ЗОНГ,). Каждая из формул Г„Г, содержит логических связок не более гг — 1, а поэтому, по предположению индукции, обладает приведенной формой. Пусть Г,* и Г* — приведенные формы для формул Г, и Гг соответственно. Отсюда формулы (Гг* л Гг'), (Гг* ч Гг"), ('ФРНГг*), (ЗгНГг*) являются приведенными формами для формул (Г, л Гг), (Гг ~~ Гг), (1гсНГ,), (ЗРНГ,) соответственно.
Остается рассмотреть случаи, когда Г имеет один из следующих видов: Гь (Гг -з Гг) или (Г, с-~ Г,). Пусть Гесть — Гь Тогда формула — Гг* может не быть приведенной формой для формулы Уь Строго говоря, для этого случая следует провести доказательство также методом математической инлукции по числу логических связок формулы Г,*. Если Г,* атомарна, т.е. Г,* — предикатная переменная Р, то ( Г,)* есть Р— приведенная форма. Если же Гг* — составная формула, то задача сводится к пронесению знака — через кванторы и операции л и ~~ (другие логические операции не входят в приведенную форму Г,*). Это пронесение осуществляется на основании равносильностей из логики предикатов и алгебры высказываний, называемых законами де Моргана (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
