Скачать 0.71 Mb.
|
Пример 12. Формула x1∧¬x2∧x3 есть конституента единицы K1(1,0,1), формула x∨y∨¬z есть конституента нуля K0(0,0,1), формула (x1∧¬x2)∨(¬x1∧x2) – СДНФ, формула (x∨y∨¬z)∧(¬x∨¬y∨z)∧(¬x∨y∨z) – СКНФ, а формула (x1∧¬x2∧x3)∨(¬x1∧x2∧x3)∨(x1∧¬x2∧x3) не является СДНФ. Теорема 3. Для любой не тождественно ложной (не тождественно истинной) формулы φ АВ существует единственая СДНФ (СКНФ) ψ АВ такая, что φ≡ψ. Заметим, что единственность формулы в формулировке теоремы понимается с точностью до порядка следования конъюнктивных сомножителей и дизъюнктивных слагаемых в этой формуле. Опишем алгоритм приведения формулы к СДНФ.
а) если в конъюнкт входит некоторая переменная вместе со своим отрицанием, то мы удаляем этот конъюнкт из ДНФ; б) если в конъюнкт одна и та же литера xδ входит несколько раз, то удаляем все литеры хδ, кроме одной; в) если в конъюнкт x1δ1∧…∧xkδk не входит переменная у, то этот конъюнкт заменяем на эквивалентную формулу (x1δ1∧…∧xkδk∧y)∨(x1δ1∧…∧xkδk∧¬y); г) если в полученной ДНФ имеется несколько одинаковых конституент единицы, то оставляем только одну из них. В результате получается СДНФ. Пример 13. Найти СДНФ для ДНФ φ(x∧¬x)∨x∨(y∧z∧y). Решение. Имеем φ≡x∨(y∧z)≡(x∧y)∨(x∧¬y)∨(x∧y∧z)∨(¬x∧y∧z)≡ ≡(x∧y∧z)∨(x∧y∧¬z)∨(x∧¬y∧z)∨(x∧¬y∧¬z)∨(x∧y∧z)∨(¬x∧y∧z)≡ ≡(x∧y∧z)∨(x∧y∧¬z)∨(x∧¬y∧z)∨(x∧¬y∧¬z)∨(¬x∧y∧z). Описание алгоритма приведения формулы к СКНФ аналогично вышеизложенному описанию алгоритма приведения формулы к СДНФ и оставляется читателю в качестве упражнения.
Введем общее понятие формального исчисления. Будем говорить, что формальное исчисление I определено, если выполняются четыре условия.
Итак, исчисление I есть четверка (А,F,Ах,K). Выводом в исчислении I называется последовательность формул φ1,φ2,…,φn такая, что для любого i (1≤i≤n) формула φi есть либо аксиома исчисления I, либо непосредственное следствие каких-либо предыдущих формул. Формула φ называется теоремой исчисления I, выводимой в I, или доказуемой в I, если существует вывод φ1,…,φn,φ, который называется выводом формулы φ или доказательством теоремы φ. Вообще говоря, может не существовать алгоритма, с помощью которого для произвольной формулы φ через конечное число шагов можно определить, является ли φ выводимой в исчислении I или нет. Если такой алгоритм существует, то исчисление называется разрешимым. Исчисление называется непротиворечивым, если не все его формулы доказуемы. Используя понятие формального исчисления, определим исчисление высказываний (ИВ). Алфавит ИВ состоит из букв x,y,z,u,v, возможно с индексами (которые называются пропозициональными переменными), логических символов (связок) ¬, ∧, ∨, →, а также вспомогательных символов (, ). Множество формул ИВ определяется индуктивно: а) все пропозициональные переменные являются формулами ИВ; б) если φ, ψ формулы ИВ, то ¬φ, (φ∧ψ), (φ∨ψ), (φ → ψ) – формулы ИВ; в) выражение является формулой ИВ тогда и только тогда, когда это может быть установлено с помощью пунктов "а" и "б". Таким образом, любая формула ИВ строится из пропозициональных переменных с помощью связок ¬, ∧, ∨, →. В дальнейшем при записи формул будем опускать некоторые скобки, используя те же соглашения, что и в предыдущей главе. Подформулой ψ формулы φ ИВ называется подслово φ, являющееся формулой ИВ. Под длиной формулы будем понимать число символов, входящих в слово φ. Аксиомами ИВ являются следующие формулы для любых формул φ, ψ, χ ИВ: 1) φ→(ψ→φ); 2) (φ→ψ)→((φ→(ψ→χ))→(φ→χ));
Указанные формулы называются схемами аксиом ИВ. При подстановке конкретных формул в какую-либо схему получается частный случай схемы аксиом. Единственным правилом вывода в ИВ является правило заключения (modus ponens): если φ и φ→ψ выводимые формулы, то ψ также выводимая формула. Символически это записывается так: Говорят, что формула φ выводима в ИВ из формул φ1,…,φm (обозначается φ1,…,φm⊢φ), если существует последовательность формул ψ1,…,ψk,φ, в которой любая формула либо является аксиомой, либо принадлежит множеству формул {φ1,…,φm}, называемых гипотезами, либо получается из предыдущих по правилу вывода. Выводимость формулы φ из (⊢φ) равносильна тому, что φ теорема ИВ или доказуемая формула ИПΣ. Пример 1. Покажем, что ⊢φ→φ. Решение. Построим вывод данной формулы: 1) (φ→(φ→φ))→((φ→((φ→φ)→φ)→(φ→φ)) (схема аксиом 2); 2) φ→(φ→φ) (схема аксиом 1); 3) (φ→((φ→φ)→φ))→(φ→φ) (к пп. 2 и 1 применили правило вывода); 4) φ→((φ→φ)→φ) (схема аксиом 1); 5) φ→φ (к пп. 4 и 3 применили правило вывода). Квазивыводом в ИВ формулы φ из формул φ1,…,φm называется последовательность формул ψ1,…,ψk,φ, в которой любая формула , либо принадлежит множеству формул {φ1,…,φm}, либо выводима из предыдущих. Замечание 1. Если существует квазивывод в ИВ формулы φ из формул φ1,…,φm, то φ выводима в ИВ из формул φ1,…,φm. Пример 2. Покажем, что φ,ψ⊢φψ. Решение: Построим квазивывод формул φψ из φ и ψ: 1) φ (гипотеза); 2) ψ (гипотеза); 3) (φ→φ)→((φ→φ)→(φ→φψ)) (схема аксиом 5); 4) φ→φ (теорема ИВ по примеру 1); 5) ((φ→ψ)→(φ→φψ)) (к пп. 4 и 3 применили правило вывода); 6) ψ→(φ→ψ) (схема аксиом); 7) φ→ψ (к пп. 2 и 6 применили правило вывода); 8) φ→φψ (к пп. 7 и 5 применили правило вывода); 9) φψ (к пп. 1 и 8 применили правило вывода). Пример 3. Покажем, что φ⊢¬¬φ. Решение. Построим квазивывод формулы ¬¬φ из формулы φ:
Теорема 1 (о дедукции). Пусть φ1,…,φm,φ,ψ – формулы ИВ. Тогда φ1,…,φm,φ⊢ψ φ1,…,φm,⊢φ→ψ. Пример 4. Покажем, что φ→ψ⊢¬ψ→¬φ; Решение. По теореме о дедукции φ→ψ⊢¬ψ→¬φ φ→ψ, ¬ψ⊢¬φ. Строим вывод формулы ¬φ из формул φ→ψ,¬ψ: 1) φ→ψ (гипотеза); 2) ¬ψ (гипотеза);
Пример 5. Покажем, что φ→(ψ→χ)⊢ψ→(φ→χ) Решение. По теореме о дедукции φ→(ψ→χ)⊢ψ→(φ→χ)φ→(ψ→χ),ψ⊢(φ→χ)φ→(ψ→χ),ψ,φ⊢χ. Строим вывод формулы χ из формул φ→(ψ→χ),ψ,φ: 1) φ→(ψ→χ) (гипотеза); 2) φ (гипотеза); 3) ψ (гипотеза); 4) ψ→χ (к пп. 2 и 1 применили правило вывода); 5) χ (к пп. 3 и 4 применили правило вывода).
Формулы φ и ψ назовем эквивалентными (обозначим φ≡ψ), если φ⊢ψ и ψ⊢φ. Замечание 2. Для любых формул φ и ψ ИВ φ≡ψ⊢φ→ψ и ⊢ ψ→φ. Утверждение 1. Отношение ≡ является отношением эквивалентности на множестве формул ИВ, т.е. для любых формул φ, ψ, χ ИВ: а) φ≡φ; b) φ≡ψψ≡φ; с) φ≡ψ, ψ≡xφ≡x. Утверждение 2. Для любых формул φ, ψ, φ1, ψ1, φ2, ψ2 ИВ таких, что φ1≡ψ1 и φ2≡ψ2, имеют место эквивалентности: φ1∧φ2≡ψ1∧ψ2, φ1∨φ2≡ψ1∨ψ2, φ1→φ2≡ψ1→ψ2, ¬φ1≡¬ψ1. Теорема 2 (о замене). Пусть φ формула ИВ, ψ ее подформула, φ' получается из φ заменой некоторого вхождения ψ на формулу ψ' ИВ и ψ≡ψ'. Тогда φ≡φ'.
Утверждение 3. Пусть φ,ψ, χ – формулы ИВ. Тогда
Доказательство. Пункты 1, 4, 6, 8 доказаны в примерах 13, 14, 16, 17. Докажем пункт 7. Покажем, что φ→(ψ→χ)⊢φψ→χ. По теореме о дедукции φ→(ψ→χ)⊢φψ→χφ→(ψ→χ), φψ⊢χ. Строим вывод формулы χ из формул φ→(ψ→χ), φψ:
Покажем, что φψ→χ⊢φ→(ψ→χ). По теореме о дедукции φψ→χ⊢φ→(ψ→χ)φψ→χ, φ⊢φ→χφψ→χ, φ, ψ⊢χ. Строим квазивывод формулы χ из формул φψ→χ, φ, ψ:
высказываний Теорема 3. Пусть φ, ψ, χ формулы ИВ. Тогда имеют место следующие эквивалентности:
Доказательство. В примере 3 показано, что φ⊢¬¬φ. Покажем, что ¬¬φ⊢ φ. По теореме о дедукции ¬¬φ⊢ φ⊢¬¬φ→ φ, что выполняется, т.к. ¬¬φ→ φ – частный случай схемы аксиом 10. Докажем закон де Моргана ¬(φ∧ψ)≡¬φ∨¬ψ. Строим квазивыводформулы ¬(φ∧ψ)→¬φ∨¬ψ: 1) (¬(¬φ∨¬ψ)→φ)→((¬(¬φ∨¬ψ)→ψ)→(¬(¬φ∨¬ψ)→φ∧ψ)) (схема аксиом 5);
7) (¬φ∨ψ)→¬(φ∧ψ) (к пп. 5 и 6 применили правило вывода). Таким образом, закон де Моргана ¬(φ∧ψ)≡¬φ∨¬ψ доказан. Формула ИВ, получаемая из ДНФ (КНФ) АВ заменой логических переменных на переменные ИВ, называется ДНФ (КНФ) ИВ. Теорема 2. Для любой формулы φ ИВ существует ДНФ (КНФ) ψ ИВ такая, что φ≡ψ.
высказываний Формула φ(x1,…,xn) ИВ называется тождественно истинной (обозначается ⊨φ), если φ(x1,…,xn) – тождественно истинная формула как формула алгебры высказываний. Теорема 4 (о полноте). Формула φ ИВ доказуема тогда и только тогда, когда φ тождественно истинна: φ⊨φ. Таким образом, для того чтобы установить, доказуема ли формула ИВ, достаточно составить ее таблицу истинности. Как известно, существует эффективный алгоритм построения таблицы истинности, и, значит, ИВ разрешимо. Кроме того, из теоремы о дедукции и теоремы о полноте легко следует, что отношение эквивалентности ≡ в АВ и ИВ совпадают. Теорема 5 (о непротиворечивости). ИВ непротиворечиво. Доказательство. По теореме о полноте любая формула, не являющаяся тождественно истинной, не доказуема в ИВ. Например, такой формулой является формула х∧¬х. Следовательно, ИВ непротиворечиво. Схема аксиом называется независимой в исчислении, если хотя бы один ее частный случай не доказуем в исчислении без этой схемы. Теорема 6. Схемы аксиом ИВ независимы.
Часто объектом изучения в математике служит множество вместе с определенной на нем структурой. Например, поля, формирующие основу обычной арифметики, линейные пространства, обеспечивающие связь геометрических объектов с операциями над числами, множества с выделенными на них бинарными отношениями. Все эти структуры образуют алгебраические системы, представляющие собой некоторые миры с определенными на них законами. Перейдем к точному определению алгебраической системы. Напомним, что п-местным предикатом (отношением) на множестве А называется любое подмножество множества Аn; п-местной алгебраической операцией на множестве А называется функция F:An→A, где – n-я декартова степень множества А. Отметим, что поскольку операция F является функцией, для любого набора (x1,…,xn)An результат применения операции F(x1,…,xn) однозначно определен. Так как область значений операции F лежит в множестве А, то будем говорить, что операция F замкнута на множестве А. Сигнатурой Σ называется совокупность предикатных и функциональных символов с указанием их местности. Константным символом или просто константой называется 0-местный функциональный символ. Если α функциональный или предикатный символ, то его местность обозначается через μ(α). Часто п-местные предикатные и функциональные символы будем обозначать соответственно через Р(n) и F(n), возможно с индексами. Если в рассматриваемой сигнатуре используются стандартные символы, такие, например, как + для операции сложения, ≤ для отношения порядка, | для отношения делимости, 0 для константного символа и другие, то мы просто пишем Σ={≤}, Σ={≤,+, ... , 0} и т.д. Алгебраической системой сигнатуры Σ называется пара = где А – непустое множество и каждому n-местному предикатному (функциональному) символу из Σ поставлен в соответствие n-местный предикат (соответственно операция) на А. Множество А называется носителем, или универсумом алгебраической системы . Предикаты и функции, соответствующие символам из Σ, называются их интерпретациями. Обозначать интерпретации будем теми же буквами, что и соответствующие символы сигнатуры, возможно с индексом A. Заметим, что интерпретацией любого константного символа является некоторый элемент из А. Если Σ={α1,…, αn} – конечная сигнатура, то в записи фигурные скобки будем опускать. Пример 1. 1) Набор является алгебраической системой с двумя двухместными операциями.
Алгебраическая система = называется подсистемой системы = (обозначается), если выполняются следующие условия: а) АВ; б) для любого функционального символа F (n)Σ и любых элементов a1,a2,…,anA выполняется равенство FA(a1,a2,…,an)=FB(a1,a2,…,an), т.е. интерпретации символа F действуют одинаково на элементах из А; в) для любого предикатного символа Р(n)Σ справедливо равенство P=∩An, т.е. предикат содержит в точности те кортежи предиката , которые состоят из элементов множества А. Теорема 1. Если алгебраическая система, XВ, X≠Ø, то существует единственная подсистема (Х)= алгебраической системы такая, что XВ(Х) и (Х) для любой подсистемы алгебраической системы , для которой XА. Подсистема (Х) из теоремы 1 называется подсистемой алгебраической системы , порожденной множеством X. Для описания элементов подсистемы (Х) определим индукцией по построению понятие терма сигнатуры Σ:
Под сложностью терма будем понимать число символов, входящих в терм. Пример 2. 1) Термами сигнатуры Σ={+,∙,≤,0} будут, например, 0, x, x+y, z∙(x+z)+0∙y, а x+y≤(0+х) x термом не является. 2) Если Σ={ƒ(3), g(1), h(2)} функциональная сигнатура, то выражения h(ƒ(x1, x2, x3), g(x2)), g(ƒ(h(x1, x2), x1, g(x2)) – термы, а h(x1, ƒ(x1, x3)) термом не является. Пусть t(x1,…,xk) терм из T(Σ), все переменные которого содержатся в множестве {x1,…,xk}, = алгебраическая система. Значение терма t на элементах a1,…,akA (t(a1,…,ak)) определяется по индукции:
Теорема 2. Если = алгебраическая система, Ø≠XB, то B(Х)={t(a1,…,an) | tT(Σ), a1,…,anX}. |
Теория алгоритмов Нормальные алгоритмы Маркова и ассоциативные исчисления в исследованиях по искусственному интеллекту | Программа по формированию навыков безопасного поведения на дорогах... История появления, развития и запись чисел: в Древней Греции, Египте, на Руси; Фигурные числа, совершенные числа, дружественные числа,... | ||
Ответы на вопросы к экзамену "Физиология высшей нервной деятельности" Высшая нервная деятельность- условно-рефлекторная деятельность ведущих отделов головного мозга (у человека и животных- больших полушарий... | Министерство общего и профессионального образования Ростовской области... «Ребенок, развитие которого осложнено дефектом, не есть менее развитой, чем его нормальные сверстники, но иначе развитой» | ||
Преступления, совершённые за два с половиной года великой чистки... Общественная атмосфера, которая была порождена попытками обуздать, стереть историческую память народа, ярко передана в поэме А. Твардовского... | 2. Нормальные и экстремальные ситуации в жизни человека Соотношение понятий «среда» и «ситуация»; соотношение объективного и субъективного в ситуации. Эмпирические исследования влияний... | ||
Урок: кейс-метод Практическая часть В россии сейчас 1 млн беспризорных детей. И у многих из них нормальные семьи, мама и папа. В библии можно найти много заповедей о... | Проблемы исполнения обязательств в гражданском праве Охватывают как нормальные отношения между субъектами гражданского права, связанные с производством продукции, реализацией работ,... | ||
Урок №47. Формы мышления. Алгебра высказываний. Цели урока Правомерно ли считать, что религия, искусство, наука – духовные истоки философии? Обоснуйте свой ответ | Учебно-методическое пособие для самостоятельной работы по дисциплине... Полноценное кормление животных обеспечивает хорошее состояние здоровья, получение высокой продуктивности, нормальные воспроизводительные... | ||
И. Б. Ничипоров И. А. Бунин. Очерк творчества Художественное наследие... Золотого века до психологической прозы второй половины ХIХ столетия и в то же время аккумулировало новейшие эстетические открытия,... | Программа по формированию навыков безопасного поведения на дорогах... Как построить нормальные отношения с ребенком? Как заставить его слушаться? Можно ли поправить отношения, если они зашли в тупик?... | ||
Программа по формированию навыков безопасного поведения на дорогах... Как построить нормальные отношения с ребенком? Как заставить его слушаться? Можно ли поправить отношения, если они зашли в тупик?... | Программа по формированию навыков безопасного поведения на дорогах... Как построить нормальные отношения с ребенком? Как заставить его слушаться? Можно ли поправить отношения, если они зашли в тупик?... | ||
Для того чтобы правильно выполнить задание 2, необходимо усвоить... Видо-временные формы глагола: а) активный залог – формы Indefinite (Present, Past, Future); формы Continuous (Present, Past, Future);... | Программа по формированию навыков безопасного поведения на дорогах... Ага, как же, полюбому есть, только крысит. Мысля! У лоточников зарешать они всегда добавят, пофиг, что хачи, зато выручают по мелочи.... |