- •Введение
- •Программа курса математическая логика и терия алгоритмов
- •Логическое следствие в алгебре высказываний
- •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. Дополнительная литература
- •Содержание
Пример 3. Построить подсистему алгебраической системы , порожденную множествомХ:
=X={1/2};
=X={1/2};
=X={22;-36}.
Решение.1) Так какТ(Σ)={x1, x1x2, (x1x2)x3, x1(x2x3),…}, то теореме 2 имеемA(X)={1/2, 1/2∙1/2, 1/2∙1/2∙1/2,…}={1/2, 1/8, 1/16,…}={1/2n| n≥1}.
Из предыдущего примера следует, что {1/2n| n≥1}A(X). Так как операция деления является сигнатурной, то1/2n1/2m=2m-nA(X) для любых m, n≥1. ТогдаC={2n| nZ}A(X). Так как множествоС замкнуто относительно операций умножения и деления. т.е. является подсистемой алгебраической системы и содержит множествоX, тоA(Х)С. Следовательно,A(Х)=С.
Так как 2=22-8(-36)-1422и любое число, получаемое из чисел22, -36с помощью операции вычитания четное, тоA(X)=2
Формулы логики предикатов
Большинство определений этого параграфа будут индуктивными.
Введем понятие атомарной формулы сигнатурыΣ:
если t1, t2,T(Σ), то t1=t2‑ атомарная формула;
если P(n)Σ ‑ предикатный символ,t1,t2,…,tnT(Σ), то Р(t1,t2,…,tn)‑ атомарная формула;
никаких атомарных формул, кроме построенных по пп. 1, 2, нет.
Формула сигнатуры Σопределяется следующим образом:
1) атомарная формула сигнатуры Σесть формула сигнатурыΣ;
если φ, ψ – формулы сигнатурыΣ, то¬φ, (φ∧ψ), (φ∨ψ), (φ→ψ), xφ, xφ –формулы сигнатурыΣ;
никаких формул сигнатуры Σ, кроме построенных по пп. 1, 2, нет.
Символы ,, использованные в определении, называются соответственноквантором всеобщности иквантором существования и читаются "для любого" и "существует". Все соглашения относительно расстановок скобок, принятые в алгебре высказываний, остаются в силе и для формул логики предикатов. Кроме того, вместо записейx1…xnφ и x1…xnφ будем часто использовать записиx1,…,xnφ иx1,…,xnφ.
Определим подформулы формулыφ сигнатурыΣ:
если φ ‑ атомарная формула, тоφ ‑ ее единственная подформула;
если φ имеет вид¬φ1, илиxφ1, илиxφ1, то подформула формулыφ – это либоφ, либо подформула формулыφ1;
если φ имеет видφ1∧φ2, илиφ1∨φ2, илиφ1→φ2, то подформула формулыφ ‑это либоφ, либо подформула формулыφ1, либо подформула формулыφ2;
других подформул формулы φ, кроме построенных по пп. 1, 2, 3, нет.
Пример 4.Пусть Σ={F(2),P(1)}, φ=x(y(x=F(z,y))∨P(z))‑ формула сигнатурыΣ. Тогдаx(y(x=F(z,y))∨P(z)), y(x=F(z,y))∨P(z),
y(x=F(z,y)), x=F(z,y)), P(z) ‑ все подформулы формулыφ.
Говорят, что вхождение переменной хв формулуφ связано вφ, если оно находится в терме или предикате подформулы формулыφ видаxψ илиxψ; в противном случае это вхождение называетсясвободным вφ. Переменнаях называетсясвободной (связанной), если некоторое вхождениехвφ свободно (связано).
Пример 5.ПустьS={P1(1),P2(2)}. Рассмотрим формулы:
P1(x);
Р2(x,y)→xP1(x); 3)x(P2(x,y)→P1(x)).
Переменная хв первой формуле является свободной, во второй – и свободной, и связанной, в третьей – связанной; переменнаяу во всех формулах свободна.
Пример 6. Выписать все подформулы формулыφ, определить все свободные и связанные переменные этой формулы:
φxzy(x<y+z)((z∙2=u)→u(u=x+z)).
Решение. Выпишем подформулы формулы φ:
x<y+z,
y(x<y+z),
zy(x<y+z),
xzy(x<y+z),
z2=u,
u=x+z,
u(u=x+z),
(z2=u)→u(u=x+z),
φ.
Поскольку существуют связанные и свободные вхождения переменных х, u и z в формулу φ, то х, u и z являются связанными и свободными переменными. Переменная y связанная.
Предложением илизамкнутой формулой сигнатуры Σ называется формула сигнатуры Σ, не имеющая свободных переменных.
Запись φ(x1,…,xn) будет означать, что все свободные переменные формулыφ содержатся в множестве{x1,…, xn}.