mathlogic-s1-v1-0-0-p1

21

Конспект лекций по математической логике (I семестр)

f ◦ g(Mi) = Mi+2 (док-ть!) — биективное (док-ть!)

Пусть M =

i A Ai.

, для a

Построим

A

A

A

h:& →

1

h(a) =

(

a

если a M

i M2i+1,

f

◦

g(a) если a

i

M2i.

&

&

Лемма 8.9. h: A → A1 биективна

! (Следует из определения функции h.) "

A = A1 , A1 = B A = B . "

Сл. 8.10. A ≤ B — частичный порядок.

Теорема 8.11. (Кантора) A < P(A) .

!(1) A ≤ P(A) , т. к. A P(A) по определению : f(a) = {a} (инъективна).

(2) A ̸= P(A) . От противного. Пусть g: A → P(A) (g биективна).

c

A g(c) =

!

= H

"

( ) =

c

g(c) — прот-е.

#

( )

прот-е; (б) c / g c

"

c / H

. Тогда

Рассмотрим H =

a

A

a

/ g(a). H

A

H P(A)

1

( )

2

"

H

. (а) c

g c

H

c

H

c / g c —

Сл. 8.12. Количество бесконечных мощностей бесконечно.

Континуум-гипотеза (КГ). Не существует мощностей, промежуточных

	между N и P(N).
Обобщённая КГ (ОКГ). c ¬ A c < A < P(c) .
	Парадокс Кантора. Не	1				2
		существует множества всех множеств.
	! От противного. Пусть A — множество всех множеств.
	A < P(A) , однако B P(A) (B A) (т. к. B —							множество),
	значит P(A) A, P(A) ≤ A — противоречие. "
	A / A A A.	!		"	#
Парадокс Рассела. Рассмотрим A =			a	"	a / a	. Тогда A A			A / A;

§9. Счётные множества

Опр. 9.1. A — счётное A = N = ω.

Предл. 9.3. (а) N2 счётно; (б) A счётно A2 счётно.

(в) A, B счётны A × B счётно.

! Через канторовскую нумерацию. "

Сл. 9.4. При n N (а) Nn счётно; (б) A счётно An счётно;

(в) A1, . . . , An счётны		A1 × . . . × An счётно.
! (в) по индукции, (а) и (б) частные случаи. "
Предл. 9.5. (а) N =		&	n N Nn счётно; (б) A счётно				n N An счётно.
! Канторовская				f: N → N	.	"	&
	нумерация, биективная

http://ccfit.nsu.ru/ tarancov/

Конспект лекций по математической логике (I семестр)

22

Сл. 9.6. Счётные множества: множества всех программ, вычислимых на машине Тьюринга функций, частично рекурсивных функций, многочленов с целыми коэффициентами, алгебраических чисел.

! Элементарно. "

Предл. 9.7. Множество конечных подмножеств счётного множества счётно:

! " # gf (A) = B A " B конечно .

! Инъективность f: A → P F (A), инъективность g: P F (A) → Aω. "

Предл. 9.8. (а) A, B — конечные A B, A ∩ B — конечные;

(б) P F (x), ≤ — РУМ с наименьшим элементом; (в) P F (x) — БА x конечно.

Предл. 9.9. В любом бесконечном множестве есть счётное подмножество.

! A ≠ a1 A;

A ≠ a1 (A \{a1}) ≠ a2 (A \{a1}) . . . "

Предл. 9.10. A — бесконечное & a A A = A \{a} . ! Указываем отображение. "

Сл. 9.11. A — бесконечное & B A — конечное A = A \ B .

!Индукция по B . "

§10. Континуум

Опр. 10.1. Множество A — континуально (имеет мощность континуум), если A = R .

Теорема 10.2. (О бессчётности континуума.) R > N .

!N R N ≤ R . Покажем N ≠ R от противного.

Лемма 10.3. R = (0, 1) .
Пусть	N		=		(0, 1) . Тогда f: N		→	(0, 1) биективна.
	n
Пусть αk		— k-й знак после запятой в десятичной записи f(n).
Определим βn = 1 при αnn ̸= 1, βn = 2 в противном случае.											, значит
					запятой, получим новое число					b (0, 1)
Взяв βi как знаки после n
n a(n) = b. Но тогда αn						= βn, чего быть не может. "
Сл. 10.4. Пусть A < C ,						B < C , тогда A B < C .
! Без доказательства. "
Сл. 10.5. (а) Трансцендентные числа (обозн. «множество T ») существуют.
	(б)		<!t R " t трансцендентно#< =						<R<.
			<		"			<	< <

!На основе того, что алебраических чисел (A) счётное количество, и R = = T A. "

Теорема 10.6. Прямая и плоскость равномощны: R = R2 .

!Строим биективную функцию. "

Версия 1.0.0

23	Конспект лекций по математической логике (I семестр)

Теорема 10.7. R = P(N) .

!По теореме Кантора-Берштейна, сопоставляя R десятичную дробь. "

§11. Конечная Булева алгебра

Опр. 11.1. Пусть A — БА. a A (a ≠ 0) — атом, если он минимальный среди ненулевых элементов.

Опр. b A — безатомный, если под ним (≤) нет атомов:

c A (c ≤ b c — не атом).

Опр. c A — атомный, если под ним нет ненулевых безатомных элемен-

тов.

!

""

≤

# !

"

≤ #

At(A) =

;

Опр. 11.2.

a

A

"

a — атом

"

A

A

— атом

A

при c

At(c) = !a

"

a c, a

= a

At(

) a

c .

#

Опр. 11.3. Булева алгебра называется атомной, если в ней нет ненулевых безатомных элементов.

Опр. Булева алгебра называется безатомной, если в ней нет атомов.

Зам. 11.4. (а) A — атомная 1A — атомный;

(б) A — безатомная

1A — безатомный;

(в) 0 — атомный и безатомный.

"

Предл. 11.5. At(P(X)) = A

X

"

A

= 1

=

a

a

X .

Сл. 11.6. P(X) — атомная!БА.

"

|

|

#

!{ }

"

#

Предл. 11.7.	Пусть A — БА; a, b A. Тогда a ∩ b = 0 a ≤		.
		b
Предл. 11.8.	Пусть A — БА; a, b A; a — атом. Тогда a ≤ b a ≤				.
				b

Зам. 11.9. При a1, . . . , an A в силу ассоциативности « » и «∩» можно записать без скобок: a1 . . . an = sup{a1, . . . , an}, аналогично для «∩».

	Предл. 11.10. Пусть A — конечная БА,		A, тогда	.
	Зам. 11.11. Пусть a, b, c A. Тогда:	a		a = &c At(a) c

(а) c ≤ (a ∩ b) c ≤ a & c ≤ b; (б) c ≥ (a b) c ≥ a & c ≥ b.

Теорема 11.12. (Стоуна для конечной БА) Пусть A — конечная БА. Тогда A изоморфна P(At(A)); , ∩, , , At(A) , то есть множеству всех подмножеств множества её атомов.

Опр. 11.13. Пусть A, B K(σ). Отображение f: |A| → |B| называется изоморфизмом алгебраических систем A и B, если:

(1)f биективна;

(2)f сохраняет отношение функции и константы,

т. е. pn, gk, C σ, a1, . . . , an A:

(а) A |= p(a1, . . . , an) B |= p(f(a1), . . . , f(an));

http://ccfit.nsu.ru/ tarancov/

Конспект лекций по математической логике (I семестр)		24
(б)	f(g(a1, . . . , an)) = g(f(a1), . . . , f(an));
(в)	CB = f(CA).

По существу, изоморфизм — это переозначивание.

§12. Секвенциальное исчисление высказываний

Опр. 12.1. Γ = (ϕ1, . . . , ϕn) либо Γ = (n = 0).

«|=» — знак секвенции.

Опр. 12.2. Исчисление секвенций (секвенц-е исчисление высказываний): а) ϕ |= ϕ (аксиома).

б) Правила вывода:

(1)	Γ |= ϕ; Γ |= ψ
	Γ |= (ϕ & ψ)
(3)	Γ |= (ϕ & ψ)
	Γ |= ψ

Γ|= ψ

(5)Γ |= (ϕ ψ)

(7)	Γ, ϕ |= ψ
	Γ |= (ϕ → ψ)
(9)	Γ, ¬ϕ |=
	Γ |= ϕ

(11)Γ1, ϕ, ψ, Γ2 |= ξ Γ1, ψ, ϕ, Γ2 |= ξ

Γ|= (ϕ & ψ)

(2)Γ |= ϕ

(4)	Γ |= ϕ
	Γ |= (ϕ ψ)
(6)	Γ, ϕ |= ξ; Γ, ψ |= ξ; Γ |= (ϕ ψ)
		Γ |= ξ
(8)	Γ |= ϕ; Γ |= (ϕ → ψ)
	Γ |= ψ
(10)	Γ |= ϕ; Γ |= ¬ϕ
	Γ |=

Γ|= ϕ

(12)Γ = .

, ψ | ϕ

§13. Семантика секвенциального исчисления высказываний

Опр. 13.1. ϕ1, . . . , ϕn |= ψ называется истинной при данных значениях пропозициональных переменных, если либо одна из формул ϕi ложна, либо ψ истинна.

Опр. ϕ1, . . . , ϕn |= называется истинной при данных значениях пропозициональных переменных, если хотя бы одна из формул ϕi ложна

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

Теорема 13.2. (О корректности исчисления секвенций) Если секвенция доказуема, то она тождественно истинна.

Опр. 13.3. ρ: F → F (F — множество формул) называется подстановкой, если она перестановочна с логическими связками: ρ(ϕ & ψ) = ρ(ϕ) & & ρ(ψ), аналогично для , →, ¬. Если S — секвенция, ρ — подстановка,

S = (ϕ1, . . . , ϕn |= ψ), ρ(S) = (ρ(ϕ1), . . . , ρ(ϕn) |= ρ(ψ)).

Версия 1.0.0

25	Конспект лекций по математической логике (I семестр)

Теорема 13.5. (О подстановке) Подстановка сохраняет доказуемость секвенции.

Опр. 13.6. Формула ϕ называется доказуемой, если |= ϕ — доказуемая секвенция.

Сл. 13.7. Если ϕ доказуема, ρ — подстановка, то ρ(ϕ) доказуема.

Опр. 13.8. ϕ ≡ ψ («равносильно»), если ϕ |= ψ и ψ |= ϕ доказуемы.

Предл. 13.9. «≡» является отношением эквивалентности.

Предл. 13.10. «≡» является конгруентной F; , &, →, ¬ , т. е. ϕ ≡ ϕ1 & & ψ ≡ ψ1 (ϕ ψ) ≡ (ϕ1 ψ1), аналогично для &, →, ¬.

Предл. 13.11. Если ϕ доказуема, ϕ ≡ ψ, то ψ доказуема.

Теорема 13.12. (О замене) ϕ ≡ ϕ′, ψ′ получена из ψ заменой некоторого вхождения формулы ϕ на ϕ′, тогда ψ ≡ ψ′.

Предл. 13.13. «≡» является отношением эквивалентности. (Ср. с (13.9) —

прим. ред. ;).

Предл. 13.14. Имеют место следующие эквивалентности:

1)¬(ϕ & ψ) ≡ ¬ϕ ¬ψ

2)¬(ϕ ψ) ≡ ¬ϕ & ¬ψ

3)¬¬ϕ ≡ ϕ

4)ϕ & ψ ≡ ψ & ϕ

5)ϕ ψ ≡ ψ ϕ

6)(ϕ & ψ) & ξ ≡ ϕ & (ψ & ξ)

7)(ϕ ψ) ξ ≡ ϕ (ψ ξ)

8)ϕ & (ψ ξ) ≡ (ϕ & ψ) (ϕ & ξ)

9)ϕ (ψ & ξ) ≡ (ϕ ψ) & (ϕ ξ)

10)ϕ → ψ ≡ ¬ϕ ψ

11)ϕ (ψ & ¬ψ) ξ ≡ ϕ ξ

12)ϕ & (ψ ¬ψ) & ξ ≡ ϕ & ξ

§14. Теорема о полноте исчисления секвенций

Теорема 14.1. ϕ КНФ ψ (ψ ≡ ϕ)

Теорема 14.2. КНФ ϕ тождественно истинна в каждой её элементарной дизъюнкции есть переменная, входящая в эту дизъюнкцию как сама, так и с отрицанием.

Предл. 14.3. (|= ϕ ¬ϕ) доказуема.

Теорема 14.4. КНФ доказуема в каждой её элементарной дизъюнкции есть переменная, входящая в эту дизъюнкцию как сама, так и с отрицанием.

Сл. 14.5. КНФ ϕ доказуема ϕ тождественно истинна.

http://ccfit.nsu.ru/ tarancov/

Конспект лекций по математической логике (I семестр)

26

Теорема 14.6. (О полноте СИВ) Если ϕ тождественно истинна, то ϕ доказуема.

Теорема 14.7. (а) ϕ тождественно истинна ϕ доказуема (формула);

(б) ξ тождественно истинна ξ доказуема (секвенция).

Сл. 14.8. ϕ, ψ (ϕ ψ ϕ ≡ ψ).

Опр. 14.9. Пусть Γ — множество формул.

Γ|= ϕ, если конечное Γ0 Γ такое, что Γ0 |= ϕ доказуемо.

Γ|= (противоречива), если конечное Γ0 Γ такое, что Γ0 |= доказуемо.

Теорема 14.10. (Об адекватности)

(а) Γ |= ϕ для любого набора значений переменных верно: если истинны все формулы из Γ, то истинна ϕ.

(б) Γ |= не существует набора значений переменных, на котором все формулы из Γ истинны.

§15. Исчисление секвенций Гильбертовского типа

Опр. 15.1. Аксиомы:

1) ϕ → (ψ → ϕ)

2) (ϕ → ψ) → ((ϕ → (ψ → ξ)) → (ϕ → ξ)) 3) (ϕ & ψ) → ϕ

4) (ϕ & ψ) → ψ 5) (ϕ → ψ) → ((ϕ → ξ) → (ϕ → (ψ & ξ)))

6) ϕ → (ϕ ψ)

7) ψ → (ϕ ψ)

8) (ϕ → ξ) → ((ψ → ξ) → ((ϕ ψ) → ξ)) 9) (ϕ → ψ) → ((ϕ → ¬ψ) → ¬ϕ)

10) ¬¬ϕ → ϕ

Правило вывода (modus ponens): ϕ; ϕψ→ ψ .

Опр. 15.2. Последовательность ϕ1, . . . , ϕn называется док-вом ИВ, если каждая ϕi либо является аксиомой, либо получена из предыдущих однократным применением правил вывода.

Если ϕ1, . . . , ϕn = ϕ — доказательство, то говорят, что ϕ1, . . . , ϕn — доказательство формулы ϕ.

Если у ϕ существует доказательство, то ϕ называется доказуемой и обозначается ϕ.

Пусть H — множество формул. Говорят, что ϕ1, . . . , ϕn — доказательство из множества формул H, если каждая ϕi либо является аксиомой, либо ϕi H, либо получена из предыдущих однократным применением правил вывода.

Если ϕ = ϕn, то ϕ1, . . . , ϕn — доказательство ϕ из H.

Если существует док-во ϕ из H, то говорят, что ϕ доказуемо в H (H ϕ). ! Без доказательства (см. Ершов-Палютин). "

Версия 1.0.0

27	Конспект лекций по математической логике (I семестр)

Теорема 15.3. (О дедукции) Если H {ϕ} ψ, то H (ϕ → ψ).

Теорема 15.4. (Об эквивалентности ИС и ИВ) (а) ϕ1, . . . , ϕn |= ψ доказуема в ИС {ϕ1, . . . , ϕn} ψ в ИВ.

(б) ϕ1, . . . , ϕn |= доказуема в ИС {ϕ1, . . . , ϕn} (ψ & ¬ψ) для некоторой ψ в ИВ.

§16. Гомоморфизмы. Эпиморфизмы. Изоморфизмы и конгруэнции алгебраических систем.

Опр. 16.1. Пусть σ — сигнатура. Kσ = K(σ) — класс алгебраических

систем сигнатуры σ. A, B Kσ . A = A; σA , B = B; σB . A = |A|, B = |B|. Тогда h: A → B называется гомоморфизмом, если:

(1)h: A → B — отображение

(2)pn, fn, C σ, a1, . . . , an A:

(а) A |= p(a1, . . . , an) B |= p(h(a1), . . . , h(an)); (б) fB(h(a1), . . . , h(an)) = h(fA(a1, . . . , an));

(в) h(CA) = CB.

Опр. h: A → B — эпиморфизм A → B, если

(1) h — гомоморфизм; (2) h сюрьективна.

Опр. h: A → B — строгий гомоморфизм, если

pn, fn, c σ; a1, . . . , an A:

(а) A |= P(a1, . . . , an) B |= P(h(a1), . . . , h(an)); (б) f(h(a1), . . . , h(an)) = h(f(a1, . . . , an));

(в) h(cA) = cB.

Свойство (а) сохраняет истинность и ложность P n.

Опр. h:nA →n B — сильный гомоморфизм, если
p , f , c σ; a1, . . . , an A;	b1, . . . , bn B:
(а) B |= P(b1, . . . , bn) c1, . . . , cn A:
h(c1) = b1, . . . , h(cn) = bn	и A |= P(c1, . . . , cn);

(б) fB(h(a1), . . . , h(an)) = h(fA(a1, . . . , an)); (в) h(cA) = cB.

Свойство (а) сохраняет ложность P n.

Опр. h: A → B — изоморфизм, если

(1)h биективно;

(2)h — строгий гомоморфизм.

Опр. h: A → B — изоморфное вложение, если

(1)h инъективно;

(2)h — строгий гомоморфизм.

Зам. 16.2. (В лекциях было следующее. Определения эпиморфизма, изоморфизма и изоморфного вложения даны не через гомоморфизмы, а непосредественно. В этом замечании же были записаны другие варианты определений, приведённые в этом конспекте.)

http://ccfit.nsu.ru/ tarancov/

Конспект лекций по математической логике (I семестр)	28
Зам. 16.3. (а) h — гомоморфизм	h: A → h(A) — эпиморфизм;

(б) h — изоморфное вложение h: A → h(A) — изоморфизм.

Опр. 16.4. Модель A Kσ является подмоделью B Kσ (A B), если:

(1)|A| |B|;

(2)pn, fn, c σ; a1, . . . , an A:

(а) A |= P(a1, . . . , an) B |= P(a1, . . . , an); (б) fA(a1, . . . , an) = fB(a1, . . . , an);

(в) cA = cB.

Зам. 16.5. A, B Kσ, |A| |B|, тогда

:A → B — изоморфное вложение.a

! (Упр.) "

Опр. 16.6. B Kσ, A B, тогда множество A замкнуто относительно

операций в модели B, если fn, c σ fB(a1, . . . , an) A,

a1, . . . , an A: cB A.

Предл. 16.8. B Kσ , A B, тогда A определяет некоторую подмодель A модели B тогда и только тогда, когда A замкнуто относительно операций в модели B.

! ( ) A Kσ , A B, A = |A|, fn, c σ, a1, . . . , an A. fB(a) = fA(a) A.

cB = cA A A — замкнуто.

( ) A замкнуто, тогда введём на A отношения, операции, константы, определённые на B. P n, fn, c σ, a A.

(а) A |= P(a), если B |= P(a). (б) fA(a) = fB(a) A.

(в) cA = cB A.

Тогда воспользуемся определением A Kσ , причём A B. (Кто мо-

жет объяснить эту фразу, напишите мне!) "

Сл!. 16.9." Пусть#A, B Kσ , K: A → B — гомоморфизм. Тогда C = = h(a) " a A B, т. е. C = h(A) замкнуто в модели B относительно

операций и, следовательно, определяет подмодель модели B: C = h(A)

B.

!fn, c σ, a A.

fB(h(a1), . . . , h(an)) = h(fA(a1, . . . , an))

fA(a) A h(fA(a)) C fB(h(a1), . . . , h(an)) C. cB = h(cA), cA |A| cB = h(cA) C

L Kσ , C = |L|, L B. "

Предл. 16.10. Пусть H Kσ ,	B Kσ , A H (A B). Тогда C =
A B , C закмнуто относительно операций в модели B.
= =A H | | | | L = A,	C = L .
	| |

>

A H

Версия 1.0.0

29	Конспект лекций по математической логике (I семестр)

!a C, fn, c σ.

A H a A fB(a) = fA(a) A

cB = cA |A|.

=

A H |A| = .fB(a)= C

cB A H |A| = C. "

Теорема 16.11. Пусть B Kσ , X B. Тогда наименьшая по включению подмодель C B такая, что X C. Эта подмодель называется

подмоделью B, порождённой множеством X: C = subB(X).
C =	!A H A	"	C	#B A H, X A X C C H, по
! H =	A B		X A		, B H H ̸=
	=			| | |		| "
определению A" H					C	A .

Предл. 16.12. Пусть A, C B, |C| |A|. Тогда C A.

!A, B, C Kσ ,

|C| = C C B C замкнуто относительно операций.

C |A| C A.

Pn, fn, c σ, a |C|.

C |= P(a) |A|

C |= P(a) B |= P(a) A |= P(a). fC(a) = fB(a) = fA(a).

cC = cB = cA

C A. "

Сл. 16.13. Пусть X B. Тогда C = subB(X) — подмодель модели B, порождённая множеством X, — является подмоделью любой другой под-

модели B, содержащей множество X. ( A B X A C A.)
	X	Kσ		!		; "	#
Предл. 16.14. (а) Пусть	B	Kσ , тогда			A		A B ; — ЧУМ;
(б) Пусть			, тогда X				— ЧУМ,
т. е. отношение «быть подмоделью				» является"частичным порядком.

! (1) A A;

(2) A B, B A |A| |B|, |B| |A| |A| = |B| A = = B;

(3) A B, B C |A| |B|, |B| |C| |A| |C|;

Pn, fn, c σ, a A:

A |= P(a) B |= P(a) C |= P(a) fA(a) = fB(a) = fC(a).

cA = cB = cC

A C. "

Теорема" 16.15. Пусть B K , X B, C = subB(X). Тогда |C| =

=!t(a) " a X, t T (σ)#. σ

!(1) |C| D, X D. Покажем, что D замкнуто относительно операций.

Пусть fn, c σ, d D, t T (σ).

http://ccfit.nsu.ru/ tarancov/

Конспект лекций по математической логике (I семестр)

30

1, . . . ,

n X | di = ti(

i), тогда f(

) = f(

)(

1, . . . ,

n).

d

t

a

a

a

a

a

f(

) T (σ) f(

) D.

t

d

c T (σ) cB D

|C| |A| =

D замкнуто A B | |A| = D X |A|

= D.

(2) D |C|, C — алгебраическая система. X C a X a

C, t T (σ) tB(a) = tC(a) C D |C|. "

Предл. 16.16. Пусть A B, A, B Kσ , t(x1, . . . , xn) T (σ). Тогда tA(a) = tB(a).

! Индукцией по построению терма (упр.) "

Зам. 16.17. (а) X Y |A|

subA(X) subA(Y ).

(т. к.

(б) C A, subA(|C|) = C.

( ) ="

A( )

A(

#)

Y ) t (a) a Y, t

!

! (а) σ

= σ(A)

|subA(X)| =

tA(

a

)

" |

a

X,

t

T (σ)

!

A

"

#

|

subA(Y ).

X

= | |

"заметим,

T σ

= |

sub

Y

sub

X

C, t T (σ)

A( )| = !

( )

"

(б) C

A,

C

C ;

что

D

sub

C

tA

a

a

t( #) =

( )

= ( )

" C

Определим

X

X

T σ

a

C

a

t a

D

D d = tA(

) D

C tA(

) = tC(

) = C D

a

a

a

a

C D = C C = subA(|A|). "

Сл. 16.18. Пусть A Kσ

. Тогда:

#

(б) subA( ) —

!

"

(т. е. FV (t) = ).

(а) |subA( )| = tA T (σ)

"

t замкнуто

наименьшая подмодель A по отношению «быть подмоделью».

!(а) По предложению 16.16.

(б) C A subA( ) subA(|C|) = C. "

Сл. 16.19. Пусть A Kσ , σ содержит только предикатные символы. X|A|. Тогда (а) X замкнуто в A; (б) X = |subA(X)|.

!(а) Из определения.

(б) t T (σ) t = X; a X t(a) = a X. "

Опр. 16.20. Пусть A Kσ , S: P(|A|) → P(|A|). Тогда S(X) = |subA(X)|.

Предл. 16.21. S — оператор замыкания, т. е.:

(а) S(S(X)) = X; (б) X Y S(X) S(Y ); (в) S(X) S(Y ) S(X Y ).

Предл. 16.22. Пусть A B, a A, ϕ(x) — без кванторов.

Тогда A |= ϕ(a) B |= ϕ(a).

!Индукция по построению ϕ. Схема доказательства: (а) (1) ϕ = (t = q)

(2)ϕ = P(t)

(б) ϕ = ϕ1 & ϕ2 или ϕ = ϕ1 ϕ2 или ϕ = ¬ϕ1

Версия 1.0.0