- •Введение
- •Программа курса математическая логика и терия алгоритмов
- •Логическое следствие в алгебре высказываний
- •2.1.3. Эквивалентные формулы алгебры высказываний
- •2.1.4. Дизъюнктивные и конъюнктивные нормальные формы в алгебре высказываний
- •2.1.5. Совершенные дизъюнктивные и конъюнктивные нормальные формы
- •Исчисление высказываний
- •Определение формального исчисления
- •Система аксиом и правил вывода
- •Теорема о дедукции в исчислении высказываний
- •Теорема о замене в исчисления высказываний
- •Свойства выводимых и эквивалентных формул исчисления высказываний
- •Основные эквивалентности исчисления высказываний
- •Полнота и непротиворечивость исчисления высказываний
- •Логика предикатов
- •Алгебраические системы
- •Пример 3. Построить подсистему алгебраической системы , порожденную множествомХ:
- •Формулы логики предикатов
- •Истинность формулы логики предикатов в алгебраической системе
- •2.3.4. Логическое следствие в логике предикатов
- •2.3.5. Эквивалентные формулы логики предикатов
- •2.3.6. Пренексная нормальная форма в логике предикатов
- •X(φ∧ψ)≡xφ∧ψ, X(φ∨ψ)≡xφ∨ψ,
- •X(φ∧ψ)≡xφ∧ψ, X(φ∨ψ)≡xφ∨ψ,
- •Xφ≡X(φ)xφ≡X(φ)
- •2.4. Исчисление предикатов
- •2.4.1. Система аксиом и правил вывода
- •2.4.2. Эквивалентные формулы исчисления предикатов
- •2.4.3. Теорема Геделя о полноте. Непротиворечивость исчисления предикатов
- •Элементы теории алгоритмов
- •2.5.1. Машины Тьюринга
- •2.5.2. Примитивно рекурсивные функции
- •2.5.3. Частично рекурсивные функции
- •Задания для домашних и контрольных работ
- •3.1. Совершенные дизъюнктивные нормальные формы, совершенные конъюнктивные нормальные формы
- •3.2. Логическое следствие в алгебре высказываний
- •Логическое следствие в логике предикатов
- •Частично рекурсивные функции
- •Список литературы
- •Основная литература
- •4.2. Дополнительная литература
- •Содержание
Истинность формулы логики предикатов в алгебраической системе
Дадим индуктивное определение истинности формулы φ(x1,…,xn) сигнатурыΣна элементахa1,…,anА в алгебраической системе=(обозначаемφ(a1,…,an)).
1) ⊨t1(a1,…,an)=t2(a1,…,an), где t1,t2T(Σ), значения термовt1,t2в алгебраической системе на элементахa1,…,anА совпадают;
2) ⊨P(t1(a1,…,an),….,tk(a1,…,an)), где P(k)Σ, t1,…,tkT(Σ), (t1(a1,…,an),…, tk(a1,…,an))P;
3) ⊨ψ(a1,…,an)∧χ(a1,…,an)⊨ψ(a1,…,an) и ⊨χ(a1,…,an);
⊨ψ(a1,…,an)∨χ(a1,…,an)⊨ψ(a1,…,an) или ⊨χ(a1,…,an);
⊨ψ(a1,…,an)→χ(a1,…,an) если ⊨ψ(a1,…,an), то ⊨χ(a1,…,an);
⊨¬ψ(a1,…,an)неверно, что ⊨ψ(a1,…,an);
⊨xψ(x,a1,…,an)⊨ψ(a,a1,…,an) для любого аA;
⊨xψ(x,a1,…,an)⊨ψ(a,a1,…,an)для некоторогоаА.
Если не выполняется ⊨φ(a1,…,an),то будем говорить, что формулаφ(x1,…,xn) сигнатурыΣложна в системена элементахa1,…,anА.
Пример 7. Записать формулуφ(x),истинную вна элементеaтогда и только тогда, когдаa четно.
Решение. φ(x)y(x=y+y).
Пример 8. Записать формулуφ(x,y,z), истинную в на кортежеaтогда и только тогда, когдаc ‑ наименьшее общее кратное чиселaиb.
Решение. φ(x,y,z)ψ(x,y,z)∧χ(x,y,z),
где формула ψ«говорит» о том, чтоzделится наx и наy, а формулаχ«говорит» о том, чтоz делит все общие кратныехиу, т. е. является наименьшим из всех общих кратных:
ψ(x,y,z)uv(z=xu∧z=хy),
χ(x,y,z)w(uv(w=xu∧w=хy)→w1(w=w1z)).
Таким образом,
φ(х,у,z)uv(z=xu∧z=хy)∧w(uv(w=xu∧w=хy)→w1(w=w1z)).
2.3.4. Логическое следствие в логике предикатов
Через обозначим кортеж переменных; через‑.
Пусть φ1(),…,φn(), ψ()– формулы сигнатуры. Формулаψ называется логическим следствием формулφ1,…,φn(обозначаетсяφ1,…,φn⊨ψ), если для любой алгебраической системысигнатуры
⊨(φ1()…φn()→ψ()).
Пример 9. Доказать, что
φ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) сигнатуры называется тождественно истинной, если для любой алгебраической системысигнатуры
⊨φ(x1,…,xn). Формула φ(x1,…,xn) сигнатуры называется тождественно ложной, если формула ¬φ(x1,…,xn) тождественно истина. Множество формул φ1,…,φn сигнатуры называется противоречивым или несовместным, если формула φ1∧…∧φn тождественно ложна.
Теорема 3. Пусть φ1,..,φm,ψ – формулы сигнатуры Следующие условия эквивалентны:
;
{φ1,..,φm,¬ψ} – противоречивое множество формул;
– тождественно истинная формула;
φ1∧..∧φm∧¬ψ – тождественно ложная формула.
2.3.5. Эквивалентные формулы логики предикатов
Формулы φ и ψ сигнатурыназываются эквивалентными(обозначается φ ≡ ψ), если φψ или ψ.
Утверждение 1. В логике предикатов выполнимы все эквивалентности ИВ из теоремы 3.
Утверждение 2. Пусть φ, ψ – формулы сигнатуры переменная x не является свободной переменной формулы ψ, переменная у не является свободной переменной формулы φ. Тогда
1) ¬xφ≡x¬φ, 1΄) ¬xφ≡x¬φ,
2) x(φ∧ψ)≡xφ∧ψ, 2΄) x(φ∨ψ)≡xφ∨ψ,
3) x(φ∨ψ)≡xφ∨ψ, 3΄) x(φ∧ψ)≡xφ∧ψ,
4) xφ≡x(φ)4΄)xφ≡x(φ)
здесь запись (φ) обозначает результат подстановки y вместо всех свободных вхождений в φ переменной x.