Материал: discrete_mathematics

− символи логiчних операцiй (композицій) ¬, та ;

– символ рівності = предметних значень.

У множиніFs може виділятися підмножина константних символів Сп Fs. Символ рівності = завжди інтерпретуємо як предикат рівності, причому таку рівність трактуємо як тотожність.

Символи ¬, , , = і предметнi імена назвемо базовими логiчними символами. Функцiональнi та предикатнi символи, окрім =, назвемо нелогiчними символами. Множини Fs та Ps утворюють сигнатуру мови першого порядку.

Основними конструкціями мови першого порядку є терми та формули. Терми використовують для позначення, назви об'- єктів предметної області, формули − для запису тверджень про такі об'єкти.

Індуктивне означення терму таке:

1)кожне предметне ім'я та кожна константа є термом; такі терми назвемо атомарними;

2)якщо t1,..., tn − терми, F − n-арний функцiональний сим-

вол, то F(t1...tn) − терм.

Атомарною формулою називають вираз вигляду P(t1...tn), де P − n-арний предикатний символ, t1,..., tn − терми.

Індуктивне визначення формули таке:

1)кожна атомарна формула є формулою;

2)якщо Φ та Ψ − формули, то (¬ Φ) та (Φ Ψ) − формули;

3)якщо Φ − формула, x − предметне iм'я, то ( xΦ) − формула. Дужки можна опускати, ураховуючи пріоритет операцій та їх

асоціативність. Пріоритет символів логічних зв'язок вважаємо нижчим за пріоритет предикатних символів, а пріоритет предикатних символів – нижчим за пріоритет функціональних символів. Квантори мають вищий пріоритет ніж бінарні логічні зв'язки. Для бінарних функціональних і предикатних символів зазвичай застосовуємо інфіксну форму запису. Те саме – для атомарних формул. Для формул вигляду ¬ (t1= t2) уживатимемо скоро-

чення t1 ≠ t2.

Вирази Φ&Ψ, Φ → Ψ та Φ ~ Ψ вважаємо вiдповiдно скороченнями формул

¬ (¬ Φ ¬ Ψ), ¬ Φ Ψ та ¬ (¬ (¬ Φ Ψ) ¬ (¬ Ψ Φ)).

231

Користуємося також символом , вважаючи вираз xΦ скороченням формули ¬ x ¬ Φ.

Скорочення термiв і формул називатимемо просто термами та формулами. Множини термів і формул мови першого порядку позначатимемо вiдповiдно Тr та Fr. Формули й терми визначають мову логіки L.

У формулi вигляду xΦ або xΦ формулу Φ називаютьобла

стю дiї квантора за x. Вираз вигляду x або x називають кван

торним префiксом.

Входження імені (змінної) x до формули Φ зв'язане, якщо воно міститься в області дії деякого квантора за x, інакше таке входження x у Φ вільне. Якщо існує вільне входження імені x до формули Φ, то x − вільне ім'я (вільна змінна) формули Φ.

Формулу Φ із вільнимиіменами x1,.., xn позначаємоΦ(x1,.., xn). Формула замкнена, якщо вона не має вільних імен.

Терм, який не містить входжень предметних імен, називають замкненимтермом. Зокрема, такимєкожнийконстантнийсимвол.

Наведемо приклади мов першого порядку.

Приклад 6.3.

1. Мова арифметики Lar визначається сигнатурою

0, 1, +, ×, =,

де 0 та 1 − константні символи, + та × − бiнарнi функцiональнi символи, = − бiнарний предикатний символ.

Терм мови арифметики назвемо арифметичним термом, а формулу мови арифметики – арифметичною формулою.

Наприклад,

1 + 1 − замкнений арифметичний терм; x × (y + z) − арифметичний терм;

z(x + z = y) − арифметичнa формула.

2.Мова теорiї множин Lset визначається сигнатурою , =, де

та = − бiнарнi предикатнi символи.

Наприклад,

z x − атомарна формула;z(z x→z y) − формула;

x¬ y(y x) − замкнена формула мови Lset.

Зауважимо, що останні дві формули відповідно означають x y та існує .

232

3. Мова теорiї впорядкованих множин Lord визначається сиг-

натурою <, =, де < та = − бiнарнi предикатнi символи. Наприклад,

x < y − атомарна формула;

z < x → x < y → z y −

x y(y < x) − Lord. ◄

Зв'язані імена у формулах можна замiнювати iншими предметними іменами, але при цьому може виникнути колiзiя − ситуацiя, за якої вiльнi імена стали зв'язаними. Наприклад, iз формули

z(x + z = y)

можна отримати формулу

t(x + t = y),

коли колiзiї немає, і формулу

x(x + x = y),

коли колізія змінила смисл формули.

Вільні входження предметних імен до формули або терму можна замінювати термами. Позначимо

Фх1,…,хn[t1,..., tn]

формулу, отриману із формули Φ заміною всіх вільних входжень імен x1,.., xn на терми t1,..., tn, відповідно. Для термів аналогічно вводимо позначення

tx1 ,...,xn [t1,..., tn].

У загальному випадку формули

Φx,y[a, b] та (Φx[a])y[b]

– різні. Наприклад, якщо Φ − це формула x y, то Φx,y[y, z] − фор-

мула y z, (Φx[y])y[z] − формула z z.

При заміні вільних входжень предметних імен термами можливі колізії, за яких вільне ім'я стає зв'язаним. Наприклад, нехай

Φ− це формула z(x + z = y). Тоді Φx[u] − це формула z(u + z = y);

Φx[z] − це формула z(z + z = y). Отже, маємо колiзiю.

Звідси терм t допустимий для замiни вiльного імені x у фор мулi Φ, якщо за такої заміни не виникають колізії.

Інтерпретацiєю, або моделлю мови L, називатимемо АС із доданою сигнатурою вигляду A = (M, I Fs, IPs).

233

Множину A називають областю iнтерпретацiї.

Значення символів і виразів мови L задамо на A таким чином. Предметні імена інтерпретуємо як імена елементів (змінні) на M. Символи логічних операцій інтерпретуємо як відповідні логічні операції (композиції). Константні символи інтерпретуємо як конкретні елементи множини M, тобто як функції-константи на M. Предикатні та функціональні символи інтерпретуємо як предикати та функцiї вiдповідної арностi, визначені на M, причому бінарний предикатний символ = завжди інтерпретувати-

мемо як предикат рівності на M.

Для інтерпретації термів і формул мови L задамо відображення

J Tr: Tr → FnQM та J Fr: Fr → PrQM,

яке індуктивно визначають за допомогою I Fs та IPs.

Для термiв маємо:

J Tr (х) ='x;

J Tr(F(t1,..,tn)) = I Fs(F)(J Tr(t1),..., J Tr(tn)) = FA (J Tr(t1),..., J Tr(tn)).

Для атомарних формул маємо:

J Fr(P(t1...tn)) =IPs(P)(J Fr (t1),..., J Fr(tn)) = PA (J F (t1),..., J F(tn)).

Для формул маємо:

Нехай J Fr (Φ) = p. Тодi J Fr (¬ Φ) = ¬ p, J Fr ( xΦ) = xp.

Нехай J Fr (Φ) = p та J Fr (Ψ) = q. Тодi J Fr (Φ Ψ) = p q. Зауважимо, тут ми неявно використовуємо введені раніше

композиції суперпозиції:

FA(g1,..., gn), по суті, означає SFn (FA, g1,..., gn),

PA(g1,..., gn) означає SPn (PA, g1,..., gn).

Терми та формули за заданої інтерпретації визначають спеціальні підкласи квазіарних функцій і предикатів, які називають Х-арними функціями та предикатами. Тут Х – множина імен (змінних) {v1,..., vn}. Значення Х-арних функцій і предикатів визначаються лише значеннями змінних із Х, інші змінні не впливають на значення функцій і предикатів. Клас Х-арних даних позначаємо M X.

Уведені визначення дають змогу стверджувати, що кожний терм із вільними іменами v1,..., vn інтерпретується як {v1,..., vn}- арна функція на M, кожна формула з вільними іменами v1,..., vn

234

– як {v1,..., vn}-арна функція на M. Зокрема, кожний замкнений терм інтерпретується як функція-константа на M, кожна замкнена формула – як предикат-константа на M.

Функцію, що є значенням терму t на АС A = (M, I Fs, IPs), позначаємо tA; предикат, що є значенням формули Φ на АС A = (M, I Fs, IPs), позначаємо ΦA. Це означає, що

J Tr(t) = tA, JFr (Φ) = ΦA.

Формулу Φ назвемо істинною за інтерпретації A, або істин ною на A, або A істинною, якщо предикат ΦA є істинним.

Останнє означає: Х-арний предикат ΦA такий, що для всіх d M X маємо ΦA(d) = 1.

Те, що формула Φ істинна на AC A, позначатимемо A B Φ.

Формулу Φ називають всюди iстинною, якщо вона iстинна за кожної iнтерпретацiї.

Те, що Φ усюди істинна, позначатимемо B Φ.

Формулу Φ назвемо виконуваною за інтерпретації виконуваною на AC A, або A-виконуваною, якщо предикат ΦA є

виконуваним. Це означає: Х-арний предикат ΦA є таким, що для деякого d M X виконується ΦA(d) = 1.

Формулу Φ називають виконуваною, якщо вона виконувана за деякої iнтерпретацiї.

Приклад 6.4.

1. Формула x = x усюди істинна.

2. Формула x y(x = y) iстинна на всiх 1-елементних АС i тільки на них; формула ¬ x y(x = y) iстинна на всiх k-еле- ментних АС, де k > 1, i тiльки на них.

Замиканням формули Φ із вільними іменами x1,..., xn назвемо

замкнену формулу x1... xnΦ, яку позначатимемо Φ . Із наведених означень випливає

кання:

Для всіх інтерпретаційA та формули Φ

A B Φ A BΦ .

3. Кожна формула вигляду Φx[t] → xΦ усюди істинна. ◄

235