Правильные и полные дизъюнкты и конъюнкты

1) Конъюнктивный одночлен (конъюнкт), а также дизъюнктивный одночлен (дизъюнкт) называют правильными, если они не содержат в своем составе более одного раза любую переменную x_j^σj. Это означает, что всякая переменная может входить в него ровно один раз, и одночлен не может содержать никакой переменной вместе с ее отрицанием.(правильный коньюнкт xКyКz)

Ясно, что любой одночлен можно преобразовать правильно на основе основных равносильностей.

 

2) Предположим, что задан набор пропозиционных переменных x₁,x₂, …, x_n. Одночлен называется полным относительно этого набора переменных, если он содержит каждое из x_j^σj (j=1, 2, …, n).

Если одночлен неполный, то его можно дополнить в следующем смысле:

а) Неполный дизъюнкт можно представить в равносильном ему виде конечной конъюнкции полных дизъюнктов.

Пусть дизъюнкт Д не содержит, например, ни у, ни ┐у. Тогда запишем его в равносильном виде Д≡Д\/(y/\┐y). Тем самым мы получили конъюнкцию двух неполных переменных у дизъюнктов, что и утверждалось.

Далее этим же способом можно вводить (дополнять) другие недостающие переменные.

Аналогично всякий неполный конъюнкт можно представить в виде конечной дизъюнкции полных конъюнктов. Действительно, пусть, например, К не содержит ни у, ни ┐у:

К≡К/\(y\/┐y);

К≡(К/\у) \/(К/\┐y).

 

Правильный и полный относительно заданного набора переменных одночлен называется совершенным.

(2)Одночлен назыв полным относительно на данных лог переменных(атомы)если он содержит их все хотябы и с отриц. Например если данны 3 атома x,y,z то дизьюнкция их будет полной (xДyДz),а такой xдz будет не полный правильнный и полный одночлены назыв совершенный.

Теор:Всякий неполный коньюнкт можно представить в виде конечной дизьюнкций полных коньюнктов.

Док-во:Рассмотрим некотрый коньюнкт “К” не содержащий коньюнкта “у”,а значит не полный.Пополним его следующим образом получая равносильные ему формулы KкE;

Кк(Уд(У)); тем самым введена в каждый коньюнкт переменная “y”.Онологичным образом можно вводить остальные логические операций.

Теор:Всякий неполный дизьюнкт может быть раносильным образом представлен в виде конечной коньюнкций полных дизьюнкций.

Док-во: (по аналогий пункта выше указаного)Д,Дд(Ук(У)).

 

Совершенные формы формул алгебры высказываний.

 

1) Среди всевозможных ДНФ данной формулы F выделим совершенную ДНФ (СДНФ), т.е. в которой все элементарные конъюнкции (одночлены) являются совершенными.

Теорема 1. Всякая формула F, отличная от противоречия имеет СДНФ, причем единственную.

Для доказательства существования достаточно установить алгоритм перехода от F к ее СДНФ. Он состоит из следующих шагов:

а) Получить любую ДНФ данной формулы F.

б) Устранить в ней ситуации повторения одних и тех же конъюнкций, что возможно на основании равносильности К\/К≡К.

в) Устранить повторение в составе каждого конъюнкта одной и той же переменной (переменная и ее отрицание в конъюнкции уже быть не может, т.к. F уже отлична от противоречия (по условию)): x_j^σj /\ x_j^σj ≡ x_j^σj.

г) Каждый неполный конъюнкт пополняем, превращая его в конечную дизъюнкцию полных конъюнктов.

Итак, для каждой F получена ДНФ, в которой каждый одночлен (конъюнкт) оказался полным и правильным, т.е. совершенным.

2) Теорема 2. Всякая формула F, отличная от тавтологии Е, имеет СКНФ, причем единственную.

Доказательство существования состоит из тех шагов, приведенных в 1 пункте.

Замечание. Приведенный алгоритм показывает практический способ построения СНФ.

Пример. Даны две переменные х и у. Получим совершенные формы для х\/у.

а) х\/у уже СКНФ, т.к. состоит из правильного и полного дизъюнкта.

б) х\/у это ДНФ, но не СДНФ, т.к. конъюнкты х и у (тривиальные) не полны. Значит, их необходимо пополнить:

х ≡х /\(у \/ ┐y);

х ≡(х /\у) \/(х /\ ┐y);

у ≡у /\(х \/ ┐х);

у ≡(у /\х) \/(у /\ ┐х);

х\/у ≡(х /\у) \/(х /\ ┐y) \/(у /\х) \/(у /\ ┐х);

Исключая одинаковые одночлены, приходим, наконец, к СДНФ:

х\/у ≡(х /\у) \/(х /\ ┐y) \/(у /\ ┐х).

Логическое следование из группы формул.

1) Рассмотрим набор формул Q₁, Q₂, …, Q_n и P, зависящих от одной и той же совокупности переменных.

Определение. Говорят, что имеет место логическое следование

(Q₁, Q₂, …, Q_n)├P,(1)

если λ(P)=1 на каждом наборе переменных, на котором λ(Q₁)= λ(Q₂)=…= λ(Q_n)=1. P следует из данного набора формул, если она принимает значение истины на всяком наборе переменных, на котором истинны все H_k.

2) Теорема. Логическое следование (H₁, H₂, …, H_n)├F имеет место тогда и только тогда, когда справедливо (H₁/\H_2/\ …/\H_n)├F. (2)

Таким образом, понятие логического следования из группы формул мы свели к следованию из одной формулы, которой является конъюнкция данных.

Доказательство. В самом деле, все λ(H_k) принимают значение истины на тех и только тех наборах переменных, на которых истинна их конъюнкция.

3) Логическое следование (1) имеет место тогда и только тогда, когда тавтологией является импликация ├((H₁/\H_2/\ …/\H_n)→F). В самом деле, логическое следование (1) равносильно логическому следованию (2). Но, согласно теореме предыдущего параграфа, (2) равносильно потому что указанная импликация есть тавтология.

Алгоритм получения всех логических следований из данной формулы:

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

а) Получить СКНФ для формулы F.

б) Взять все совершенные дизъюнкты и все возможные конъюнкты (различные) таких дизъюнктов.

в) Полученный набор формул исчерпывает все возможные формулы, логически следующие из F.

Основные понятия исчисления высказываний (ИВ). Выводимость из группы формул.

 

1) ИВ есть аксиоматическая теория, которая позволяет все вышеприведенные утверждения сформулировать и доказать на основе систем основных понятий, минимального количества аксиом и правил вывода (получения) новых утверждений.

Синтаксис:

а) Алфавит ИВ содержит пропозиционные переменные и две операции: операция ┐(относится к 1 переменной) и операция → (соединяющая 2 пропозиционные переменные).

б) Слово в ИВ есть любой упорядоченный конечный набор символов алфавита.

в) Понятие формулы:

1. Всякая пропозиционная переменная есть формула.

2. Если Р – формула, Q – формула. то ┐Р, P→Q также формулы.

3. Других формул в ИВ нет.

Замечание. Вспомогательные символы, т.е. запятые, скобки употребляются так же как в АВ.

 

2) Основным понятием в ИВ является понятие выводимой формулы (доказуемой формулы) ├Р.

 

3) Система аксиом - это система договоренности о том, какие формулы в данной теории заранее принимаются выводимыми. В ИВ утверждаются аксиомы:

1. ├P→(Q→P);

2. ├(P→(T→Q))→((P→T)→(P→Q));

3. ├(┐P→┐Q)→((┐P→Q) →P).

 

4) Единственным правилом вывода в ИВ является ПЗ (правило заключения):

если ├P и ├(P→Q), то ├Q.

 

5) Теорема 1. Если ├R, то ├(B→R), где В – любая формула.

Доказательство. Из первой аксиомы получаем ├R→(B→R); R выводима по условию, на основании ПЗ получаем ├(B→R).

Теорема 2. Для любой формулы В имеет место ├(В→В).

Теорема вытекает из второй аксиомы, записанной в более общем виде.

 

1) Это понятие обобщает понятие логического следования из группы формул, но оно уже не может использовать известные в АВ логические операции.

Пусть имеется группа формул {Г} в ИВ. Формула В – выводима из Г, если существует такая последовательность В₁, В₂, …, В_n-1, В_n, то:

а) В_n≡В (совпадение формул);

б) Каждая формула В_j в этой последовательности либо из набора {Г}, либо аксиома, либо получена из двух предыдущих по правилу заключения (ПЗ). Последнее надо понимать так: в указанной последовательности имеется последовательность В_j-1, В_j-1→В_j, В_j.

 

2) Набор {Г} вообще говоря бесконечен.

Теорема 1. Если множество {Г} является подмножеством {Δ} и ({Г}с{ Δ }). Если В выводим из {Г}, то В выводим из {Δ}.

Утверждение очевидно, поскольку те формулы последовательности В_j, которые были взяты из {Г} являются одновременно взятыми из {Δ}.

 

3) Обозначения выводимости из группы формул: {Г}├В.

В определении выводимости не исключалось также, что набор {Г} пуст; то, что тогда представляет собой определение выводимости из {Г} есть просто выводимость в исчислении, т.к. В получается тогда лишь из аксиом ПЗ. В этом случае ├В. Говорят также, что В доказуемо или теорема в ИВ. Все элементы множества {Г} называют гипотезами при выполнении которых выводима В. А последовательность В₁, В₂, …, В_n-1, В_n называют также выводом формулы В.

 

4) Нельзя ли свести определения выводимости к конечному набору гипотез? Утвердительный ответ содержится в следующей теореме.

Теорема. Соотношение {Г}├В (1)

имеет место тогда и только тогда, когда найдется конечный набор гипотез

H₁, H₂,…, H_m из {Г}, такой, что { H₁, H₂,…, H_m}├B. (2)

Доказательство. Если (2) имеет место, то (1) имеет место по теореме пункта 2, поскольку набор {Г} более широк, чем набор H_j.

Обратно. Если имеет место (1), то В является конечным звеном цепочки формул В₁, В₂, …, В_n-1, В. (3)

Среди формул, предшествующих В может быть только лишь конечное количество гипотез, взятых из {Г} (понятно, что и сама В может быть такой же гипотезой). Именно этот конечный набор, участвующий в выводе и представляет собой ту самую последовательность H₁, H₂,…, H_m о которой шла речь в выводе (2).

Суть теоремы в том, что можно без ограничения общности считать, что {Г} есть конечное множество.

Теорема дедукции в АВ.

 

Если (H, G)├F, (1)

то H├(G→F). (2)

Доказательство согласно критерию следования (H/\G)├F. В этом случае F не ложно, когда G и H истинны. Если предположить, что (2) не имеет места, то это означало бы, что λ(F)=0, тогда как λ(H)=1 и λ(G)=1 (только в этом случае импликация принимает значение лжи), однако одновременно выполнение последних соотношений в силу условия (1) невозможно, что и доказывает утверждение (2).

Теорема дедукции в общем случае. Если (H₁, H₂, …, H_n)├ F, (3)

то (H₁, H₂, …, H_n-1)├(H_n→F). (4)

Суть в том, что одну из посылок можно сделать посылкой импликации, которая будет логически следовать из остальных посылок.

Доказательство. Согласно критерию логического следования из группы формул соотношение (3) имеет место тогда и только тогда, когда (H₁/\H₂/\ …/\H_n)├ F. (5)

Согласно свойству ассоциативности, это означает, что ((H₁/\H₂/\ …/\H_n-1) /\H_n)├ F. (6)

 

В

Отношение (6) приняло вид (В/\H_n)├ F.

Согласно все тому же критерию, оно равносильно (В, H_n)├ F. (7)

По теореме 1 (и ситуации 1), тогда имеет место В├(H_n→F) или

(H₁/\H₂/\ …/\H_n-1) ├(H_n→F). (8)

Согласно критерию (8), это все равно, что (4).

Итак, логическое следование (3) означает, что верно (4), а это и следовало доказать.

Согласно теореме дедукции, которая записана в виде (4), можно проводить дальнейшее «отрывание» посылок. То есть, если дано (3), то в силу (4) справедливо следование (H₁, H₂, …, H_n-2)├(H_n-1→(H_n→F)). (9)

Процесс можно продолжать и далее, пока все посылки не закончатся.

Следствие. Если имеет место логическое следование (3), то следующая формула является тавтологией: ├(H₁→(H₂→ (H_n-1→(H_n→F)))).

На ИВ

1) Пусть {H₁, H₂,…, H_m-1, H_m} ├ P, тогда {H₁, H₂,…, H_m-1} ├ (H_m→ P).

 

2) Следствие. ├(H₁ →(H₂ →…→ (H_m-1→(H_m→ P))…)), если выполнено условие теоремы пункта 1. Следствие доказывается последовательным применением теоремы пункта 1 (последовательным отщеплением гипотез H₁, H₂,…, H_m-1, H_m.).

Выводимость (H₁, H₂,…, H_n-1, H_n) ├ P (1)

имеет место тогда и только тогда, когда справедлива выводимость

(H₁, H₂,…, H_n-1)├(H_n→ P). (2)

Тот факт, что из (1) следует (2), утверждается в пункте 1.

Установим обратное. Выводимость (2) означает, что нашелся набор формул (вывод) В₁, В₂,…,В_n-1 (H_m→ P), (3)

Причем, среди формул В_j возможно присутствуют какие-то из гипотез H_k (k=1 2,…,m-1) Поскольку множество гипотез можно расширять согласно предыдущему параграфу, то и последовательности (3) можно добавить гипотезу H_m: В₁, В₂,…,В_m-1 В_m, (H_m→ P). (4)

Теперь можно считать, что (4) есть вывод для Р, поскольку Р будет получаться по ПЗ.

В₁, В₂,…,В_m-1 В_m, (H_m→ P), Р. (5)

Итак, (5) есть вывод Р. Из чего? – из набора H₁, H₂,…, H_m-1, в который добавлено H_m (а остальные участники (5) могут быть аксиомы или результаты ПЗ).

Итак, получили выводимость Р из H₁, H₂,…, H_m-1, H_m, т.е. доказано (1)

 

4) Имеет место выводимость {P, P→Q,Q→T} ├ {P→T} (6) («транзитивность импликации»).

Доказательство. Мы в праве дополнить формулу P, P→Q,Q→T еще одной формулой, а именно Q, т.е. записать в качестве гипотез набор вида P, P→Q,Q, Q→T (7). Рассмотрим (7), как последовательность-вывод формулы Т, поскольку она (Т) есть результат ПЗ: P, P→Q,Q, Q→T, Т, т.к. Т - завершающая формула, то можно записать P, P→Q,Q, Q→T├Т. На основании теоремы дедукции любую гипотезу, в частности Р, можно «отщепить», кроме того в наборе посылов можно снова исключить Q, поскольку она не была самостоятельной посылкой, а результатом ПЗ.

{P→Q,Q→T} ├ (P→T) (8). Итак, установлено (8), а значит и (6) (поскольку Р можно добавить в перечень гипотез).