Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Топ:
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
Интересное:
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Дисциплины:
2018-01-29 | 536 |
5.00
из
|
Заказать работу |
|
|
Дадим индуктивное определение истинности формулы φ(x1,…,xn) сигнатуры Σ на элементах a1,…,an А в алгебраической системе = .
Запись ╞φ(a1,…,an) будет означать, что формула φистинна на элементах a1,…,an А в системе .
1) ╞t1(a1,…,an)=t2(a1,…,an), где t1,t2 T(Σ), значения термов t1,t2 в системе Ã на элементах a1,…,an А совпадают;
2) ╞P(t1(a1,…,an),….,tk(a1,…,an)), где P(k) Σ,t1,…,tk T(Σ),↔(t1(a1,…,an),…, tk(a1,…,an)) P;
3) ╞ψ(a1,…,an)∧χ(a1,…,an) ╞ψ(a1,…,an) и ╞χ(a1,…,an);
4) ╞ψ(a1,…,an)∨χ(a1,…,an) ╞ψ(a1,…,an) или ╞χ(a1,…,an);
5) ╞ ψ(a1,…,an) → χ(a1,…,an) если ╞ ψ(a1,…,an), то ╞ χ(a1,…,an);
6) ╞ψ(a1,…,an) неверно, что ╞ψ(a1,…,an);
7) ╞ xψ(x,a1,…,an) ╞ψ(a,a1,…,an) длялюбого а A;
8) ╞ xψ(x,a1,…,an) ╞ψ(a,a1,…,an) для некоторого а А.
Если не выполняется ╞φ(a1,…,an), то будем говорить, что формула φ(a1,…,an)ложна в системе .
Пример 1.
Записать формулу φ(x), истинную в тогда и только тогда, когда х четно.
Решение.
φ(x)= y(x=y+y).
Пример 2.
Записать формулу φ'(x,y,z), истинную в тогда и только тогда, когда z‑ наименьшее общее кратное чисел х и y.
Решение.
φ'(x,y,z)=ψ(x,y,z)∧χ(x,y,z), где формула ψ «говорит» о том, что z делится на x и на y, а формула χ "говорит"о том, что z делит все общие кратные х и у, т. е. является наименьшим из всех общих кратных:
ψ= u,∨(z=u∙x∧z=∨х∙y),
χ= w( u,∨(w=u∙x∧w=∨х∙y)→ w1(w=w1∙z)). Итак,
φ'(х,у,z)= u,∨(z=u∙x∧z=х∙y)∧ w( u,∨(w=ux∧w=хy)→ w1(w=w1z)).
Логическое следствие в ЛП
Через обозначим кортеж переменных ; через ‑ .
Определение. Пусть φ1(),…,φn(), ψ() – формулы сигнатуры ∑. Формула ψ называется логическим следствием формул φ1,…,φn (обозначается φ1,…,φn╞ ψ), если для любой алгебраической системы сигнатуры ∑
|
╞ (φ1() … φn()→ψ()).
Пример 1.
Доказать, что φ1()→φ2(),φ2()→φ3()╞φ1()→φ3() (1)
где φ1(),φ2(),φ3() – формулы сигнатуры ∑.
Пусть =‹А, ∑› ‑ произвольная система сигнатуры ∑. Необходимо указать, что ╞ ((φ1()→φ2()) ((φ2()→φ3())→(φ1()→φ3())).
Пусть и ╞ ((φ1()→φ2()) ((φ2()→φ3()).
Покажем, что ╞(φ1()→φ3() (2)
Предположим, что ╞φ1(). Так как ╞(φ1()→φ2(), то ╞φ2().
Так как ╞φ2()→φ3(), то ╞φ3().
Таким образом (2), а, следовательно, и (1), доказано.
Исчисление предикатов
Зафиксируем некоторую произвольную сигнатуру Σ и определим исчисление предикатов сигнатуры Σ (ИПΣ).
Формулами ИПΣ будут формулы сигнатуры Σ.
Примем следующие соглашения. Пусть x1,…,xn ‑ переменные, t1,…,tn ‑ термы сигнатуры Σ и φ ‑ формула сигнатуры Σ. Запись будет обозначать результат подстановки термов t1,…,tn вместо всех свободных вхождений в φ переменных x1,…,xn соответственно, причем, если в тексте встречается запись , то предполагается, что для всех i={1,...,n} ни одно свободное вхождение в φ переменной xi не входит в подформулу φвида y или y , где у - переменная, входящая в ti.
Аксиомами ИПΣ являются аксиомы вида 1-10 ИВ, а также аксиомы
11) xφ→(φ)tx;
12) (φ)tx→ xφ;
13) x=x;
14) x=y→((φ)xz→(φ)yz).
Формулы 1-14 называются схемами аксиом ИПΣ.
Правила вывода ИПΣ:
1. φ, φ → ψ,
ψ
2. ψ →φ,
ψ→ xφ
3. φ → ψ,
xφ → ψ
где в правилах 2 и 3 переменная x не входит свободно в ψ.
Доказательством в ИПΣ формулы φ называется такая последовательность φ0,…,φn формул ИПΣ, что φn φ и для каждого i≤n формула φi удовлетворяет одному из следующих условий:
1) φi ‑аксиома ИПΣ;
2) φi получается из некоторых φ1,…, φi-1, по одному из правил вывода 1-3.
Если существует доказательство в ИПΣ формулы φ, то φ называется доказуемой в ИПΣ или теоремой ИПΣ (обозначаем ├φ).
|
Выводом в ИПΣформулы φ из множества формул φ1,…, φm называется такая последовательность ψ1,…,ψk формул ИПΣ, что φn φ и для каждого i≤n формула φi удовлетворяет одному из следующих условий:
1) φi ‑аксиома ИПΣ;
2) φi принадлежит Г;
3) φi получается из некоторых ψ1,…, ψi-1 j<i, по одному из правил вывода 1-3, причем при применении правил 2 и 3 переменная х не должна входить ни в одну формулу из Г свободно.
Если существует вывод в ИПΣ формулы φ из множества формул φ1,…, φn, то φ называется выводимой в ИПΣ из Г (обозначаем Г├φ). При этом Г называется множеством гипотез. Очевидно, что доказуемость формулы эквивалентна ее выводимости из пустого множества гипотез. Так же, как в исчислении высказываний, определяется понятие квазивывода. Если Г = {ψ1,…,ψn}, то вместо Г├φ пишем ψ1,…,ψn├φ.
Формула ψ сигнатуры Σ называется тавтологией, если она получается из формулы φ исчисления высказываний, доказуемой в исчислении высказываний, путем замены всех ее пропозициональных переменных x1,…,xn на формулы ψ1,…,ψn сигнатуры Σ соответственно. Формулу φ при этом называют основой тавтологии.
Утверждение 1. Любая тавтология φ сигнатуры Σ доказуема в ИПΣ.
Следствие 1. Если φ и ψ ‑ пропозиционально эквивалентные формулы сигнатуры Σ, то φ и ψ‑ эквивалентные формулы сигнатуры Σ.
В исчислении предикатов ИПΣ справедлива теорема о дедукции.
Теорема 1. (о дедукции).Пусть Г – множество формул ИПΣ, φ, ψ – формулы ИПΣ. Тогда Г,φ├ψ, Г├φ→ψ.
Эквивалентные формулыИП
Определение эквивалентных формул, утверждения 3,4 при замене формул φ, ψ, χ ИВ на формулы ИПΣ имеют место.
Утверждение 1. В ИПΣ выполнимы все эквивалентности ИВ из теоремы 5.
Доказательство. Выполнимость в ИПΣ всех эквивалентностей исчисления высказываний следует из следствия 3.
Утверждение 2. В ИПΣ выполнимы следующие эквивалентности, в которых предполагается, что переменная ж не входит свободно в формулу ψ, а переменная у не входит в формулу φ:
1) xφ≡ xφ,1\) xφ≡ xφ,
2) x(φ∧ψ)≡ xφ∧ψ, 2\) x(φ∨ψ)≡ xφ∨ψ
|
3) x(φ∧ψ)≡ xφ∧ψ, 3\) x(φ∨ψ)≡ xφ∨ψ,
4) xφ≡ . 4\) xφ≡
Пример. 1. Докажем эквивалентность а). Построим квазивывод формулы xφ→ xφ из Ø:
1. φ→ xφ ‑ аксиома 12;
2. xφ→φ ‑ к п.1 применили утверждение 3:
3. xφ→ xφ ‑ к п.2 применили правило вывода 2.
Построим квазивывод формулы xφ→ xφ из Ø:
1. xφ→φ ‑ аксиома 11;
2. φ→ xφ ‑ к п.1 применили утверждение 3;
3. xφ→ xφ ‑ к п. 2 применили правило вывода 3;
4. xφ→ xφ ‑ к п.З применили утверждение 3.
Пример. 2. Докажем эквивалентность г). Построим квазивывод формулы x(φ∧ψ)→ xφ∧ψ из Ø:
1. x(φ∧ψ)→φ∧ψ ‑ аксиома 11;
2. φ∧ψ→φ ‑ утверждение 1;
3. x(φ∧ψ)→φ ‑ к пп.1,2 применили утверждение 1;
4. x(φ∧ψ)→ xφ ‑ к п.4 применили правило вывода 2;
5. φ∧ψ→ψ ‑ утверждение 1;
6. x(φ∧ψ)→ψ ‑ к пп.1,5 применили утверждение 1;
7. ( x(φ∧ψ)→ xφ)→(( x(φ∧ψ)→ψ)→( x(φ∧ψ)→ xφ∧ψ)) ‑ аксиома 5;
8. x(φ∧ψ)→ xφ∧ψ ‑ к пп.4.6.7 применили правило вывода 1.
Построим квазивывод формулы xφ∧ψ → x (φ∧ψ) из Ø:
1. xφ∧ψ→ xφ ‑ аксиома 3;
2. xφ→φ‑ аксиома 11;
3. xφ∧ψ→φ ‑ к пп.1,2 применили утверждение 1;
4. xφ∧ψ→ψ‑ аксиома 4;
5. ( xφ∧ψ→φ)→(( xφ∧ψ→ψ)→( xφ∧ψ→φ∧ψ)) ‑ аксиома 5;
6. xφ∧ψ→φ∧ψ ‑ к пп.3,4,5 применили правило вывода 1;
7. xφ∧ψ→ x(φ∧ψ)‑ к п.6 применили правило вывода 2.
Теорема 1. (теорема о замене). Если формула φ сигнатуры Σ получается из формулы ψ сигнатуры Σ заменой некоторого вхождения подформулы ψ' на формулу φ' сигнатуры Σ и φ'≡ψ', то φ≡ψ.
|
|
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!