Доказать что формула в логическое следствие посылок

Рассмотрим понятие логического вывода в логике высказываний и процедуры логического вывода.

Необходимо усвоить следующие основные понятия. В математике, как и в обычной жизни, часто нужно решить, следует ли одно утверждение из нескольких других. Это приводит к понятию “логический вывод”. Пусть даны формулы F₁,F₂. F_n и формула G. Товорят, что G есть логическое следствие формул F₁,F₂. F_n (или G логически следует из F₁,F₂. F_n) тогда и только тогда, когда для всякой интерпретации I, в которой F₁ÙF₂Ù. ÙF_n истинна, G также истинна. F₁,F₂. F_n называются аксиомами (или постулатами или посылками) G.

Следует знать и уметь пользоваться следующими теоремами о выводе логического следствия:

Теорема 1. Пусть даны формулы F₁,F₂. F_n и формула G. Тогда G есть логическое следствие F₁,F₂. F_n тогда и только тогда, когда ((F₁ÙF₂Ù. ÙF_n)G)общезначима.

Теорема 2. Пусть даны формулы F₁,F₂. F_n и формула G. Тогда G есть логическое следствие F₁,F₂. F_n тогда и только тогда, когда (F₁ÙF₂Ù. ÙF_nÙØG) противоречива.

Теоремы 1 и 2 очень важны. Из них вытекает: доказательство того, что отдельная формула есть логическое следствие конечного множества формул, эквивалентное доказательству того, что некоторая связанная с ними формула общезначима или противоречива. Если G есть логическое следствие формул F₁,F₂. F_n , то формула ((F₁ÙF₂Ù. ÙF_n)G) называется теоремой, а G называется также заключением теоремы. В математике, так же, как и в других областях, многие проблемы могут быть сформулированы как проблемы доказательства теорем.

Рассмотрим примеры решения типичных упражнений и задач

1. Даны формулы логики высказываний: F₁(PQ), F2ØQ, GØP.

Показать, что G есть логическое следствие F₁ и F₂.

Решение. Метод 1. Используем метод истинностных таблиц, чтобы показать, что G истинна в каждой модели формулы (PQ)ÙØQ. (Когда интерпретация I удовлетворяет формуле F, I называется моделью F). Из табл.3.4 мы видим, что есть только одна модель для (PQ)ÙØQ, а именно <ØP, ØQ>.

Таблица9.4 – Истинностная таблица (PQ)ÙØQ и ØP.

P Q	PQ	ØQ	(PQ)ÙØQ	ØP
0 0 0 1 1 0 1 1

Формула ØP истинна в этой модели. Таким образом, по определению логического следствия заключаем, что ØР есть логическое следствие (PQ) и ØQ.

Метод 2. Используем теорему 1. Это может быть сделано просто путем расширения истинностной таблицы в табл.9.4, т.е. путем вычисления истинностных значений формулы ((PQ)ÙØQ)ØP. Табл.3.5 показывает, что ((PQ)ÙØQ)ØP истинна при всех интерпретациях.

Таблица 9.5 – Истинностная таблица для ((PQ)ÙØQ)ØP

P Q	PQ	ØQ	(PQ)ÙØQ)	ØP	((PQ)ÙØQ)ØP
0 0 0 1 1 0 1 1

Следовательно, ((PQ)ÙØQ)ØP общезначима и, согласно теореме 1, ØP есть логическое следствие (PQ) и ØQ.

Мы можем также доказать общезначимость формулы путем преобразования ее в конъюнктивную нормальную форму:

((PQ)ÙØQ)ØP=Ø((PQ)ÙØQ)ÚØP=

Таким образом, ((PQ)ÙØQ)ØP общезначима.

Метод 3. Используем теорему 2. В этом случае мы докажем, что формула ((PQ)ÙØQ)Ù(Ø(ØP))=(PQ)ÙØQÙP противоречива. Как и в методе 2, можно использовать метод истинностных таблиц, чтобы показать, что (PQ)ÙØQÙP ложна в каждой интерпретации. Из табл.11.6 мы заключаем, что (PQ)ÙØQÙP противоречива и, согласно теореме 2, ØP есть логическое следствие формул (PQ) и ØQ.

Таблица 9.6 – Истинностная таблица для (PQ)ÙØQÙP

P Q	PQ	ØQ	(PQ)ÙØQÙP
0 0 0 1 1 0 1 1

Мы можем также доказать противоречивость формулы (PQ)ÙØQÙP путем ее преобразования в дизъюнктивную нормальную форму:

(PQ)ÙØQÙP=(ØPÚQ)ÙØQÙP=(ØPÙØQÙP)Ú(QÙØQÙP)=

=(ЛÙØQ)Ú(ЛÙP)=ЛÚЛ=Л. Таким образом, (PQ)ÙØQÙP противоречива.

2. Покажем применение логики высказываний при решении задач в словесной формулировке. Допустим, что если конгресс отказывается принять новые законы, то забастовка не будет окончена, если только она не длится более года и президент фирмы не уходит в отставку. Закончится ли забастовка, если конгрес отказывается действовать и забастовка только что началась?

Решение. Сперва преобразуем утверждения в символы:

Р: Конгресс отказывается действовать.

Q: Забастовка оканчивается.

R: Президент фирмы уходит в отставку.

S: Забастовка длится более года.

Тогда факты, данные в примере, могут быть представлены следующими формулами:

F₁: (P(ØQÚ(RÙS))) Если конгресс отказывается принять новые законы, то забастовка не будет окончена, если она не длится более года и президент фирмы не уходит в отставку.

F₂: P Конгресс отказывается действовать.

F₃: ØS Забастовка только что началась.

Можно ли заключить из фактов F₁, F₂ и F₃, что забастовка не будет окончена, т.е. можно ли показать, что ØQ есть логическое следствие F₁, F₂ и F₃? По теореме 1 это эквивалентно тому, что ((P(ØQÚ(RÙS)))ÙPÙØS)ØQ ¾ общезначимая формула. Истинностные значения указанной формулы при всех интерпретациях приведены в табл. 9.7.

Таблица 9.7 – Истинностная таблица для (F₁ Ù F₂ Ù F₃)ØQ,

где F₁(P(ØQÚ(RÙS))), F₂Р, F₃ØS

P

Q

R

S

F1

F2

F3

ØQ

(F1ÙF2ÙF3)ØQ

Из табл 9.7 видно, что не существует интерпретации, при которой данная формула ложна. Следовательно, формула ((P(ØQÚ(RÙS)))ÙPÙØS)ØQ общезначима. Поэтому ØQ есть логическое следствие F₁,F₂ и F₃, т.е. мы можем получить заключение ØQ из F₁,F₂ и F₃. Следовательно, забастовка не будет окончена.

Из приведенных примеров видно, что логика высказываний может применяться ко многим задачам. Метод состоит в том, чтобы сначала записать задачи формулами, а затем доказать, что формулы общезначимы или противоречивы. Процедуру доказательства противоречивости формулы путем ее преобразования в ДНФ и получение противоречивой формулы (Л) иногда называют методом умножения, потому что процесс преобразования очень похож на раскрытие скобок в произведении сумм.

Мы показали использование метода истинностных таблиц и метода умножения для доказательства общезначимости (или противоречивости).

Контрольные вопросы и задания по теме:

1. Логическое следствие в ЛВ.

2. Теоремы 1 и 2 об установлении логического следствия.

3. Методы установления истинности или противоречивости формул ЛВ.

4. Докажите, что (ØQØP) есть логическое следствие(PQ).

5. Если конгресс отказывается принять новые законы, то забастовка не будет окончена, кроме случая, когда она длится более года и президент фирмы уйдет в отставку. Допустим, что конгресс отказывается действовать, забастовка оканчивается и президент фирмы не уходит. Длилась ли забастовка более года?

6. Даны утверждения

F₁: PS,

F₂: SU,

Является ли G логическим следствием F₁,F₂ и F₃?

7. Покажите, что Q есть логическое следствие (PQ) и P. Это так называемое правило модус поненс (modus ponens).

# Формализация высказываний средствами логики первого порядка.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Студент – человек, постоянно откладывающий неизбежность. 10580 – | 7333 – или читать все.

78.85.5.224 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)
очень нужно

Говорят, что формула ψ(х₁,. х_п) АВ является логическим следствием формул φ₁(х₁,. х_п),…,φ_m(х₁,. х_п) АВ (обозначается ), если для любыхиз соотношенийследует. Формулыназываются гипотезами.

Пример 3. Доказать, что φ, φ→ψ, ψ→χ

Построим таблицы истинности для каждой формулы:

Из таблицы истинности видно, что когда все гипотезы принимают значение равное 1, формула χ тоже принимает значение 1, значит, χ является логическим следствием, что и требовалось доказать.

Формула φ(x₁,x₂,…,x_n) называется выполнимой (опровержимой), если существует такой набор значений переменных, на котором формула принимает значение 1 (соответственно 0) .

Пример 4. Формула х∧ у является одновременно выполнимой и опровержимой, поскольку ∧0=0, а 1∧1=1.

Формула φ(x₁,…,x_n) называется тождественно истинной, общезначимой или тавтологией (тождественно ложной или противоречием), если эта формула принимает значение 1 (соответственно ) на всех наборах значений переменных.

Пример 5. Формула x∨¬x является тождественно истинной, а формула x∧¬x — тождественно ложной:

;

– тождественно истинная формула;

2.1.3. Эквивалентные формулы алгебры высказываний

Как показано в примере 1, различные формулы могут иметь одинаковые таблицы истинности. Так возникает понятие эквивалентности формул.

Формулы φ и ψ АВ называются эквивалентными (обозначается φ ≡ ψ), если φψ или ψ, т.е. совпадают их таблицы истинности.

Легко видеть, что отношение ≡ является отношением эк­вивалентности на множестве формул АВ, т. е. оно рефлексивно (φ≡φ), симметрично (если φ≡ψ, то ψ≡φ), транзитивно (если φ≡ψ и ψ≡χ, то φ≡ χ), где φ,ψ,χ – произвольные формулы АВ.

Отметим основные эквивалентности между формулами АВ:

Читайте также:

1. A. Сообщения, касающиеся безопасности плавания, или важное метеорологическое предупреждение.
2. B. Графическое описание алгоритма.
3. BF (Best Fit – наилучший остаток) алгоритм
4. I. Обследование до наступления беременности.
5. I. Организационно-правовые аспекты приема и проверки подписных листов
6. I. Порядок проверки и оценки физической подготовленности
7. I.3.2. Изучение практического запроса и формулировка психологической проблемы.
8. I.4.3. Психологическое консультирование.
9. I.Исследование общей моторики
10. II. Исследование сенсорного развития детей.
11. II. Исследование сенсорного развития детей.
12. II. Равносильные формулы, выражающие одни логические операции через другие.

Санитарно-гигиенические показатели.

Химические показатели.

Вода характеризуется ионным составом:

– карбонаты, бикарбонаты (они все вместе обусловливают щелочность воды);

– кальций, магний (влияют на жесткость воды);

– железо и марганец (в зависимости от рН могут находиться либо в окислительной, либо в восстановительной форме в виде комплексов, коллоидов, дисперсных частиц);

– силикаты могут присутствовать в органических и неорганических формах;

– фтор, необходимый в биологическом питании для предотвращения таких заболеваний, как кариес и флюороз, в концентрации 0,7 – 1,5 мг / л, содержится в виде аниона;

– азотсодержащие вещества (ионы аммония, нитриты и нитраты), внесенные с бытовыми, промышленными и дренажными сточными водами и кислотными дождями.

Токсические вещества (стронций, свинец, ртуть, бериллий и др.), а также радионуклиды.

В основном это антропогенные продукты. Растворенные в воде газы – кислород, углекислый газ, сероводород, метан, аммиак (обусловливают запахи и коррозионную активность воды по отношению к трубопроводам и оборудованию).

В настоящее время существуют две главных проблемы водных ресурсов:

1) уменьшаются запасы пресной воды, пригодной для хозяйственно-питьевых нужд, по причинам нерационального их использования и загрязнения;

2) происходит загрязнение Мирового океана нефтепродуктами и отходами других производств.

Алгоритм действует следующим образом. Он просматривает последовательно по строкам таблицы значений формул F1, F2, F3, H. Если хотя бы один элемент нулевой строки α, β, γ равен 0, то без просмотра значения формулы H в этой строке (т. е. числа ξ) происходит переход к просмотру следующей строки α₁, β₁, γ₁. Если все элементы α, β, γ нулевой строки равны 1, то просматривается значение ξ формулы H в этой строке. При ξ = 0 выдается результат: формула H не является логическим следствием формул F1, F2, F3. При ξ = 1 происходит переход к просмотру следующей строки α₁, β₁, γ₁. И так далее. Если после просмотра последней строки α₇, β₇, γ₇, ξ₇ должен произойти переход к просмотру следующей строки, то это означает, что определение логического следования выполнено и формула H является логическим следствием формул F1, F2, F3.

Пример 1. По таблице истинности нескольких формул попытаемся определить, какие из них следуют из каких:

Рассмотрим формулы Х, Z, (X _^ Y) → Z, Y. Из таблицы видно, что имеется только одна строка (6-я), в которой первые три формулы принимают значение 1. В этой строке и формула Y также принимает значение 1. Следовательно, X, Z, (X _^ Y) → Z ╞ Y

Теперь рассматриваем формулы (Х _^ Y) → Z, Х→ Z, (Х _^ Y). Из таблицы видно, что имеется точно пять строк, в которых первые две формулы принимают значение 1, а именно 1-я, 2-я, 3-я, 4-я и 6-я. В этих строках третья формула также принимает значение 1. Следовательно, (X _^ Y) → Z, X → Z ╞ (Х _^ Y).

Признаки логического следствия.

То, что некоторая формула является логическим следствием каких-то формул, можно выразить так же, сказав, что подходящая формула является тавтологией. В этом существо признаков, о которых пойдет речь в настоящем пункте, чем еще раз подчеркивается важное значение тавтологий.

Теорема 6.3 (признак логического следствия). Формула Н будет логическим следствием формулы F тогда и только тогда, когда формула F → Н является тавтологией: F ╞ H ↔ ╞ F → H.

Следующая теорема дает признаки того, что формула является логическим следствием двух или большего количества формул.

Теорема 6.4. Для любых формул F₁, F₂, . F_m,╞ H (m ≥ 2) следующие утверждения равносильны:

Доказательство. Утверждения б) и в) равносильны на основании предыдущей теоремы. Докажем равносильность утверждений а) и б).

Тогда по равенству (1.2)

Отсюда по определению 1.3

б) => а). Дано: F_{1 ^} F_{2 ^} . _^ F_m ╞ H. Покажем, что F₁, F₂, . F_m ╞ H. Предположим, что справедливы все соотношения (6.3) для некоторых A₁, …, A_n. Тогда имеет место соотношение (6.2), из которого на основании равенства (1.2) приходим к соотношению (6.1). Из последнего на основании условия F_{1 ^} F_{2 ^} . _^ F_m ╞ H заключаем: λ(H(A₁, …, A_n)) = 1. Но это и означает, что F₁, F₂, . F_m ╞ H.

Два свойства логического следования.

Свойства, формулируемые в теореме 6.5, используются для доказательства того, что какая-то формула является логическим следствием некоторых формул (см. пример 6.2).

Теорема 6.5. Отношение логического следования между формулами алгебры высказываний обладает следующими свойствами:

а) F1, Ръ . Fm *= Fh для / = 1, 2. т

б) если Fu F2, . Fm *= Gjjumj = 1, 2. p и Gh G2, . Gp t= H,

то Fu F2, . Fm i= Я.

Доказательство. а) Фактически это свойство состоит в следующем: F/ •= Fh Оно непосредственно вытекает из определения 6.1 логического следования и означает, что отношение логического следования рефлексивно.

б) В частном случае при т-р- данное свойство утверждает: если F i= G и G »= Я, то F »= Я. Другими словами, отношение логического следования транзитивно. Докажем исходное утверждение. Строим таблицу истинности для всех формул, указанных в утверждении б), перечислив все пропозициональные переменные Хь Х2. Хт входящие хотя бы в одну из этих формул. Рассмотрим какую-нибудь строку этой таблицы, в которой каждая формула Fb F2. Fm получает истинностное значение, равное 1. Тогда на основании условий каждая из формул Gu G2, . Gp также принимает истинностное значение, равное 1. Следовательно, и Я имеет значение 1. Таким образом, для всякого набора истинностных значений переменных Хи Хъ . Хп, для которого каждая формула Fu F2, . Fm принимает значение 1, формула Я также принимает значение 1. Это означает, что Fu F2, . Fm t= Я. □

Следование и равносильность формул.

Если говорить о следовании из одной формулы другой, то получаем бинарное отношение на совокупности всех формул алгебры высказываний. Две формулы Fw Я (в указанном порядке) находятся в данном отношении, если F*= Я.

В § 4 рассмотрены бинарные отношения равносильности на совокупности всех формул алгебры высказываний. Две формулы Fw Я (в указанном порядке) находятся в этом отношении, если F = Я. Там же (следствие 4.3) установлено, что отношение равносильности формул есть отношение эквивалентности. Установим взаимосвязь между отношением равносильности и отношением следования.

Теорема 6.6. Две формулы алгебры высказываний равносильны тогда и только тогда, когда каждая из них является логическим следствием другой: F=H Ft=HnH*=F.

Доказательство. Необходимость. Дано: F= Я. По определению равносильности обе формулы F(XU . Хп) и Н(Хи . Хп) для любых конкретных высказываний Аи . Ап превращаются в высказывания F(AU . Ап) и Н(Аи . Ап), которые одновременно либо оба истинны, либо оба ложны. А раз так, то каждое из высказываний F(AU . Ап) -* Н(Аи . Ап) и Н(Аи . Ап) -» -> F(AU . Ап) истинно для любых конкретных высказываний А, . Ап. Это означает, что t=F->Hnt=H->F, откуда, по теореме 6.3, F t= Я и Я t= F.

Достаточность. Дано: Ft= Ни Н*= F. Тогда, по теореме 6.3, *= F-> -> Ни *= Я-» F. Поскольку формула /*-> Я всегда превращается в истинное высказывание и формула Н -^ F всегда превращается в истинное высказывание, то и их конъюнкция (F -» Я) л (Я -> F) является формулой, которая превращается в истинное высказывание всегда, т.е. »= (F-^> Я) л (Я-> F). Но на основании теоремы 4.4, ч, (F -» Я) л (Я -» i7) = F Я. Тогда по замечанию 4.7 t= i7^-» Я, а по теореме 4.2 F= Я.

Замечание 6.7. Если некоторая формула является тавтологией, то и всякое ее логическое следствие также является тавтологией. Символически это можно записать так: t=FHFt=H=$t=H

Правила логических умозаключений.

Теперь можем рассмотреть примеры структур правильного мышления, т.е. ответить на вопрос, что из чего следует.

Начнем с тавтологии из теоремы 3.1,/с: t= (Fa(F-> G)) -> G. (На основании замечания 3.7 пропозициональные переменные Р и Q заменены произвольными формулами Fn G алгебры высказываний.) На основании теоремы 6.4 заключаем, что F, /*-> G*= G. Полученную схему, или правило вывода (умозаключения), также называют правилом modus ponens.

Это правило означает, что от утверждения об истинности посылки F с помощью другой посылки F -» G переходят к утверждению об истинности следствия G. Данное правило называют также правилом заключения или отделения (от посылки F -> G с помощью посылки Fотделяется заключение G). По теореме 3.5 правилу 6.8 можно придать несколько иной смысл: если формулы, стоящие в числителе, являются тавтологиями, то и формула в знаменателе — также тавтология.

Не менее важное и широко применяемое в рассуждениях правило умозаключения получается на основе тавтологии теоремы 3.1, л.

Правило 6.9 (modus tollens): ‘

Оно называется правилом modus tollens: от отрицания истинности посылки G с помощью посылки F -» G переходят к отрицанию истинности F.

Таким образом, рассмотренные правила вывода 6.8 и 6.9 позволяют в истинной импликации F-> Сиз истинности посылки F делать вывод об истинности следствия G, а из ложности следствия G — о ложности посылки F.

Укажем еще некоторые правила вывода, применяемые в рассуждениях. Путь их получения состоит в том, что сначала заменяем в соответствующей тавтологии каждую пропозициональную переменную произвольной формулой алгебры высказываний, в результате чего на основании теоремы 3.6 снова получаем тавтологию, а затем от нее по теореме 6.3 переходим к соответствующему правилу вывода (умозаключения), которое и записываем в принятой форме. Так, тавтология теоремы 3.3, б дает следующее правило вывода:

Правило 6.10 (введения конъюнкции): ‘ ■

Из тавтологий теоремы 3.2, б приходим к таким правилам вывода:

Правило 6.11 (удаления конъюнкции):

Правило 6.12 (введения дизъюнкции):

Смысл названий этих правил виден из характера их действия.

Из тавтологии теоремы 3.1, д получаем правило контрапозиции.

Правило 6.13 (контрапозиции): — -.

Из тавтологии теоремы 3.1, е вытекает правило цепного заключения (или правило силлогизма).

Правило 6.14 (цепного заключения): .

Из тавтологии теоремы 3.1, м следует правило перестановки посылок.

Правило 6.15 (перестановки посылок): -.

Наконец, из тавтологии теоремы 3.1, н получаем следующие правила:

Правила 6.16 (объединения и разъединения посылок):

Правило 6.17 (расширенной контрапозиции):

Аналогично формулируются другие правила вывода тавтологий, что рекомендуется проделать самостоятельно.

На правила 6.8 — 6.17 можно смотреть с двух точек зрения. Во-первых, каждое из них представляет собой утверждение следующего типа: формула, записанная в знаменателе, является логическим следствием всех формул, записанных в числителе данного правила. Во-вторых, каждое из этих правил можно рассматривать как правило получения новой тавтологии из уже имеющихся: если все формулы, записанные в числителе, являются тавтологиями, то тавтологией будет и формула, записанная в знаменателе правила (для доказательства этого утверждения примените замечание 6.7).

Еще один способ проверки логического следования. Требуется выяснить, является ли формула Н(Хи . Х„) логическим следствием формул FX(XU . Х„), . Fm(Xu . Хп), т.е. Fu Ръ . Fm *= Я. Предположим, что Яне есть логическое следствие формул Fu F2. Fm. Значит, существуют такие конкретные высказывания Аъ . Ап, что высказывание Н(АЪ . Ап) ложно, в то время как все высказывания Fx(Ab . Ап), . Fm(Au . Ап) истинны. Если при этом удается найти распределение нулей и единиц между значениями переменных Хь . Хт соответствующее сделанному предположению, то предположение верно. Если же возникает противоречие, то предположение неверно. Посмотрим на примерах, как это делается.

Пример 6.18. Выясните, выполняется ли логическое следование

Допустим, что существуют такие конкретные высказывания А, В, С, что Х(А -> (-.В v С)) = 1, Х(гА) = 1, ЦВ -> С) = 1, но Х(А v С) = 0. Тогда из последнего соотношения получаем Х(А) = 0, ЦС) = 0, что не противоречит соотношению Ц-Л) = 1. Далее, соотношение Х(В -» С) = 1 дает ЦВ) = 0 (так как ЦС) = 0). Наконец, вычислив при данных значениях А, Ви С значение Х(А -> -»(-ii? v С)), убеждаемся что оно равно 1, а это находится в полном соответствии с допущением. Следовательно, приходим к выводу: если высказывания А, В, С таковы, что Х(А) = Х(В) = ЦС) = 0, то при подстановке X = A, Y= В, Z = С формулы-посылки примут значение 1, а формула Xv Z примет значение 0. Значит, формула Xv Zne выводима из формул X-» (-iKv Z), -лХ, Y-> Z

Нахождение следствий из данных посылок.

Мы научились определять, является ли данная формула логическим следствием некоторых других данных формул. Теперь возникает вопрос, как можно находить все формулы, являющиеся логическим следствием данной совокупности формул. Следующая теорема дает ключ к решению этой задачи.

Теорема 6.19. Формула Н(ХХ, . Хп), не являющаяся тавтологией, тогда и только тогда будет логическим следствием формул FX(XX, . Хп), . Fm(Xx, . Хп), не все из которых являются тавтологиями, когда все совершенные дизъюнктивные одночлены из разложения формулы Не совершенную конъюнктивную нормальную форму входят в совершенную конъюнктивную нормальную форму формулы ад, -, хп) а . л Fm

Доказательство. Необходимость. Дано: Fb. Fm*= HТогда, по теореме 6.4, Fx л . л Fm *= Н Найдем для формул Fx л . л Fm и Яих совершенные конъюнктивные нормальные формы. Такая форма для каждой не тождественно истинной формулы существует и единственна с точностью до порядка совершенных дизъюнктивных одночленов в конъюнкции (см. теорему 5.5). Пусть Dx л . л Dk — СКН-форма для формулы Fx л . л Fm9 а Нх л . л Я7— СКН-форма для формулы Н Тогда: Fx л . л Fm = Д л . л Dk, Н= Нх л . л Ht.

Допустим, что заключение теоремы не выполняется, т. е. среди совершенных дизъюнктивных одночленов Нъ . Я/ имеется такой, которого нет среди совершенных дизъюнктивных одночленов Du . Dk. He нарушая общности (ввиду несущественности порядка вхождения одночленов Яь . Я/ в СКН-форму Нх л . л Я/), можем считать, что таким одночленом является, например, Нх. Итак, ВД, . Хп) Z DX(XX, . Хп), . НХ(ХЬ . Хп) 2 Dk(Xx, . Хп). Тогда существует единственный (с точки зрения логических значений) набор Аи . Ап, на котором совершенный дизъюнктивный одночлен Нх<Хи . Хп) принимает значение 0: Х(НХ(АХ, . Ап)) = 0, откуда

Этот набор выбирается следующим образом. Если переменная Х < входит в Нх без знака отрицания, то А,- таково, что X(Aj) = 0; если X,- входит в Нх со знаком отрицания, то А,- таково, что (Aj) = 1 (1

|	следующая лекция ==>
Обеззараживание воды	|	Стандартный алгоритм вычисления 1 страница

Дата добавления: 2015-06-27 ; Просмотров: 4097 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет