Игошин Математическая логика и теория алгоритмов (1019110), страница 10
Текст из файла (страница 10)
Если в формулу Гвместо символа Х везде, где он входит в Г, вставить формулу Н, то получим но- 37 вую формулу. Она обозначается ЗлнГи называется формулой, полученной из Г в результате подстановки в нее формулы Н вместо пропозициональной переменной Х. Например, если в формулу ((Х г У) — » -» (Хп У)) вместо переменной Уподставить формулу (Х, к Хз), то получим ((Х ч (Х1 н Хз)) -» (Х п -(Х1 п Хз))). Если в ту же формулу вместо переменной Уподставить формулу У, то произойдет просто замена переменной, в результате которой получится формула ((Х г У) -+ (Х п -~.8')).
Если формула Гсодержит две пропозициональные переменные Хи У (а возможно, и еще несколько), то можно определить одновременную подстановку двух формул Н и 6 в формулу Г вместо пропозициональных переменных Хи Усоответственно как одновременную замену символа Х всюду, где он входит в Г, формулой Н и символа Увсюду, где он входит в Г, формулой б. Получающуюся формулу обозначают Зхн оГ. Например, подстановка в формулу (Х-» (Х г У)) вместо переменной Х формулы (Х, г Х,), а вместо переменной Уформулы — У приводит к формуле ((Х, г Хз) -» ЯХ, ~ Х) г)). Аналогично определяется одновременная подстановка в формулу Г и большего числа формул (трех, четырех и т.д.).
Теорема З.б (правило подстановки). Если формула Г, содержащая пропозициональную переменную Х является тавтологией, то подстановка в формулу Г вместо переменной Хлюбой формулы Нснова приводит к тавтологии. Другими словами, из Гследует и ЗхнГ. Доказательство. Так как ~ Г(Х У,...),то формула Г(Х У ...) превращается в истинное высказывание при подстановке вместо всех пропозициональных переменных Х, У ... любых конкретных высказываний.
Истинность получаемого высказывания не зависит от структуры подставляемых вместо Х, У, ... высказываний. В частности, вместо Х может быть подставлено высказывание, которое само является конкретизацией формулы Н(Хп ..., Хе) на некотором наборе конкретных высказываний. Но зто и означает, что тавтологией будет формула Г(Н(~п ..., Уе), У, ... ), т.е. ~ ЗхнГ, что и требовалось доказать. П Например, если в тавтологии (Х » ()' — » Х)) выполнить подстановку формулы (Х, п ~Х,) вместо переменной Х, то получим тавтологию ((Х, л Хз) — » (У вЂ” » (Х, л Хз))).
Замечание 3.7. Отметим„что правило подстановки позволяет рассматривать каждую из тавтологий, приведенных в теоремах ЗЗ вЂ” 3.4, не как отдельно взятую тавтологию, а как схему образования тавтологий. Значит, каждая из пропозициональных переменных в данных формулах может рассматриваться не как переменная, а как произвольная формула алгебры высказываний. Например, тавтология б) из теоремы 3.3 предоставляет бесконечное множество тавтологий вида ~ Г, — » (Гз — » (Г, л Гз)), где Гп Гз — произвольные формулы алгебры высказываний. 38 Два рассмотренных правила образования тавтологий — «модус поненс» и правило подстановки — будем называть основными.
Существуют и другие правила (см. 5 6), которые будем называть вторичными или производными правилами, й 4. Логическая равносильность формул Понятие равносильности формул. Онределение 4.1. Формулы Г(Хь Х,, ..., Х„) и Н(Х„Хп ..., Х„) алгебры высказываний называются равносильными (эквивалентными), если при любых значениях входящих в них пропозициональных переменных логические значения получающихся из формул г и Н высказываний совпадают. Для указания равносильности формул используют обозначение рн Н. Определение равносильности формул можно записать символически: г и Н«» Х(Г(Аь Ап ..., А„)) = Х(Н(Аь Аь ..., А„)) (4 () для любых конкретных высказываний А„Ап ..., А,. Не следует думать, что в обе формулы Г и Н непременно входят одни и те же переменные.
Некоторые из переменных Хп Хь ..., Х„ могут фактически отсутствовать в любой из них. Проверим, например, равносильность формул Л; и Хз л (Хз ~ Л;). Для этого составим таблицы истинности обеих формул и убедимся, что значения истинности получающихся из них высказываний одинаковы для любых одинаковых наборов значений пропозициональных переменных Х, и Х,: Проверьте самостоятельно справедливость равносильностей Х, ч ч.
Х, =- Х~ ч — Хь Х, н — Х, =- Хз л — Хь Выписывание в предыдущем определении в формулах Г и Н одних и тех же пропозициональных переменных обусловлено стремлением сделать записи и рассуждения более краткими и лаконичными. Это замечание следует иметь в виду и далее (например, при изучении 5 6). Для лучшего усвоения понятия равносильности формул алгоритм проверки на равносильность двух формул Г(Х У, У) и О(Х У, У) можно представить в виде условной схемы (приведена в тексте).
Формулы Г(Х, ); У) и 6(Х, У, У) заданы своими таблицами значений: 39 Алгоритм нроверки формул на равносильность Проанализируйте работу данного алгоритма и сопоставьте ее с определением понятия равносильности формул. Признак равносильности формул. Сущность признака состоит в выявлении тесной связи между понятием равносильности формул и понятием тавтологии.
Теорема 4.2 (признак равносильности формул). Две формулы Г и Н алгебры высказываний равносильны тогда и только тогда, когда формула г' <-> Н является тавтологией: Г = Н ~ ~ Г <-> Н. (4.2) Д о к а з а т е л ь с т в о. Если Гге Н, то по определению 4.1 ЦГ(Ан ..., А„)) = ).(Н(Ан ..., А„)) для любых высказываний Ан ..., А„. Тогда (по определению 1.9 операции эквивалентности) Х(Г(Ан ..., А„)) <-~ <-> Х(Н(Ан ..., А„)) = 1, откуда на основании соотношения (1.5) заключаем, что ).(Г(Ан ..., А„) <-+ Н(Ан ..., А,)) = 1 для любых Ан ..., А„.
40 Последнее означает по определению тавтологии, что Гс-> Н. Обратными рассуждениями доказывается утверждение: если ы Г<-~ Н, то Г в Н. Теорема доказана. П Отметим, что равносильность формул — это не (логическая) операция над формулами, а отношение между формулами логики высказываний.
Это означает, что если Ги 6 — формулы, то выражение Г:— 6 уже не является формулой алгебры высказываний; оно — угверждение о некотором взаимоотношении между формулами Ги Н, лишь сокращенная (символическая) запись утверждения (высказывания) «Гравносильна 6» об этих формулах. Это утверждение либо истинно, либо ложно, т. е. Г и 6 либо находятся в отношении равносильности, либо нет. В приведенном далее следствии из теоремы 4.2 устанавливаются некоторые свойства этого отношения между формулами алгебры высказываний, Следствие 4.3. Отношение равносильности между формулами алгебры высказываний: а) рефлексивно: Г ге Г; б) симметрично: если Г~ =- Гп то Г2 га Г~', в) транзитивно: если Г, =- Г2 и Г~ ге Гп то Г, я Гп т.
е. отношение равносильности является отношением эквивалентностии. Доказательство. Рефлексивностьследуетнепосредственно из тавтологии теоремы 3.3, о и теоремы 4.2. Для доказательства симметричности отношения я предположим, что Г1 га Гв т.е. на основании признака равносильности (теорема 4.2) ы Г, +-> Гь Тогда по тавтологии теоремы 3.3, п заключаем: формула Г2 «-» Г, принимает всегда те же самые значения, что и формула Г, <-~ Гз, т.е. только истинные значения.
Следовательно, ы Гз с-+ Г„или (по признаку равносильности) Г2 гв Гь Симметричность доказана. Наконец, если Г, =- Г2 и Гз =- Гы т.е. Ы Г, <-> Г2 и ы Гз ~-«Гм то на основании определения конъюнкции заключаем, что: ы (Р; <-> <-~ Г2) н (Гт ~-» Гз). Привлекая теперь тавтологию из теоремы 3.3, р и правило заключения для получения тавтологий (теорема 3.5), получаем ы Г, <-» Гм или (по теореме 4.2) Г, я Ги Следовательно, отношение ге транзитивно. Таким образом, отношение ге есть отношение эквивалентности, что и требовалось доказать.
П Как и всякое отношение эквивалентности, отношение гв разбивает множество, на котором оно задано, на непересекающиеся классы эквивалентных элементов. В данном случае множество всех Формул алгебры высказываний распадается на попарно непересекающиеся классы, в каждом из которых находятся равносильные М~жду собой формулы. Один класс, например, образуют все тавтологии, другой — все тождественно ложные формулы; имеется и много других классов. 41 Примеры равносильных формул. В теореме 4.4 перечисляются некоторые основные равносильности. Они получаются из тавтологий, приведенных в теоремах 3.1 — 3.4, на основании признака равносильности формул. 'Теорема 4.4.
Справедливы следующие равносильности: а) Рге Р; б) Р— » 0=--0-+ — Р; в) Рь» Ци — Р<-» — 0; г) Р -+ (Д вЂ” » А) ге (Р л О) -+ А; д) (Р— » А) л (Π— » А) =- (Р ч 0) -+ А; е) РлРгеР; зк) Р ч Р и Р; з)Рл0=цлР; и) Рч (2 и Д ч Р; к) Р л (0 л А) ге (Р л 0) л А; л) Рч(цчА) гг(Рч (2) ч А; м) Р л ((2 ч А) ге (Р л 0) ч (Р л А); и) Рч(цлА):-(Рч 0) л(РчА); о) Р л (Р ч 0) и Р; и) Р ч (Р л 0) ге Р; р) — (Р л 0) и — Р ч — 0 (1-й закон де Моргана); с) — (Р ч (г) и — Р л — Д (2-й закон де Моргана); т) Р +-» 0 га (2 <-» Р; у) Р-+ Цге — Рч 0; ф) Р— » ()»з -(Р л -0; х) Р л Д =- - (Р— » — 0); ц) Рч 0и- Р-+ 0; н) Р <-» 0 ге (Р— » 0) л (Д вЂ” » Р); »и) Рч — Ри1,Рл — РиО; щ) Р ч 1 ге 1, Р л 1 ге Р; ы) Р ч О ге Р, Р л О =- О. Сформулируем и докажем лемму о замене, которая служит основанием для равносильных преобразований и упрошения формул.
Лемма 4.5 (о замене). Если 6()п ..., 1;) и Н(уп ..., У), то длл любой формулы алгебры высказываний Г(Хь ..., Х и К Хчь ..., Х„) имеет место равносильность Г(Хп ..., Х и 6()ь ..., У), Хьь ..., Х„) ге Г(Хь ..., Х ь Н(уь ..., К), Х,ь ..., Х„). Другими словами, если в формуле некоторую ее подформулу заменить на равносильную ей формулу, то полученная формула будет равносильна исходной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
