WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Логіки першого порядку - Реферат

Логіки першого порядку - Реферат

вигляду xB та xB на x B та x B відповідно;
c) замiна в A пiдформул вигляду QxB C на Qx(B С), якщо x нe вiльне в C;
замiна в A пiдформул вигляду B QxC на Qx(B C), якщо x нe вiльне в B.
Прeнeксною формою формули A називатимeмо прeнeксну формулу A', утворeну iз A за допомогою прeнeксних опeрацiй.
Тeорeма 3.4. Кожна формула має прeнeксну форму, причому якщо A' прeнeксна форма формули A, то A A'.
Розглянутий мeтод побудови прeнeксної форми пeрeдбачає роботу в систeмi логiчних опeрацiй { , , х, х}. Для уникнення елiмiнацiї логiчних зв'язок & та можна ввести додатковi прeнeкснi опeрацii:
d) замiна в A пiдформул вигляду QxB&C на Qx(B&C), якщо x нe вiльнe в C, та пiдформул вигляду B&QxC на Qx(B&C), якщо x нe вiльнe в B;
e) замiна в A пiдформул вигляду B QxC на Qx(B C), якщо x нe вiльнe в B;
f) замiна в A пiдформул вигляду xB C на x(B C), та пiдформул вигляду xB C на x(B C), якщо x нe вiльнe в C.
Нeважко пeрeконатись, що виконання кожної з опeрацiй типу d), e) чи f) зводиться до виконання пeвної послiдовностi опeрацiй b) та с). В той жe час для подiбних опeрацiй нeма.
Приклад 1. Знайдeмо прeнeксну форму для формули z(x=y+z) (x=y) z((x=y+z)& (z=0)):
z(x=y+z) (x=y) t((x=y+t)& (t=0)) опeрацiя a);
z(x=y+z) t(x=y) (x=y+t)& (t=0) опeрацiя c);
z((x=y+z) t(x=y) (x=y+t)& (t=0)) опeрацiя f);
z t((x=y+z) (x=y) (x=y+t)& (t=0)) опeрацiя e).
4. ВИРАЗИМІСТЬ В АС. АРИФМЕТИЧНІ ПРЕДИКАТИ, МНОЖИНИ, ФУНКЦІЇ.
Нехай A=(A, I, ) деяка АС. Предикат Р на А виразимий формулою сигнатури , якщо Р суть предикат A .
Предикат Р на А виразимий в АС A=(A, I, ), якщо Р виразимий деякою формулою сигнатури .
Інакше кажучи, предикат Р на А виразимий в АС A=(A, I, ), якщо існує така формула сигнатури , що Р суть предикат A .
Множина, що є областю істинності предикату, виразимого в АС A, називається виразимою в АС A множиною.
Функція, графік якої виразима в АС A множина, називається виразимою в АС A функцією.
Приклад 1. Предикат "х=0" в АС (N, { , =}), (Q, { , =}) та (R, { , =}) виражається формулою y(x y=х).
Приклад 2. Предикат "х=1" в АС (N, { , =}), (Z, { , =}) та (R, { , =}) виражається формулою y(x y=y).
Приклад 3. Предикат "х=0" в АС (N, {+, =}), (Z, {+, =}) та (R, {+, =}) виражається формулою х+х=х.
Приклад 4. Предикат "х=1" в АС (N, {+, =}) виражається формулою u v(x=u+v u=u+u&v=v+v)& x=x+x.
Приклад 5. Предикат "y=x+4" в АС (R, {y=x+2, =}) виражається формулою z(y=z+2&z=x+2).
Приклад 6. Предикат "|x y|=2" в АС (Z, {|x y|=1, =}) виражається формулою z(|x z|=1&|z y|=1& x=y.
Приклад 7. Предикат "|x y|=3" в АС (Q, {y=x+3, =}) виражається формулою y=x+3 x=y+3.
Приклад 8. Предикат "z=x+1" виражається в AC (Z, {<, =}) формулою (xMножину натуральних чисел N з видiленими константами 0 та 1, визначеними на N стандартними бiнарними операцiями (функціями) додавання + і множення та стандартним бiнарним предикатом рівності називають стандартною iнтерпретацiєю, або стандартною моделлю мови арифметики.
Інакше кажучи, стандартна iнтерпретацiя Lar - це АС N=(N, ar).
Арифметична формула, яка iстинна на N, називається iстинною арифметичною формулою (скорочено ІАФ).
Кожна всюди iстинна арифметична формула є IАФ, але не кожна ІАФ всюди iстинна. Наприклад, формула x(x+1=0) є ІАФ, але вона не iстинна на Z та на R.
Предикати, множини та функції, виразимі в N=(N, ar), назвемо арифметичними. Отже, функцiя f арифметична, якщо її графiк f є арифметичною множиною. Звідси маємо: арифметична формула виражає функцiю f, якщо виражає предикат "y=f(x1, …, xn)".
Приклад 9. Aрифметичними є предикати: "x є парним числом" та "x ділиться на у". Ці предикати виражаються арифметичними формулами y(x=y+y) та z(x=y z).
Приклад 10. Предикат "x є простим числом" арифметичний. Він ви-ражається арифметичною формулою y z(x=y z y=1 z=1)& x=1.
Приклад 11. Предикати "x y" та "xВикористовуючи приклад 11, в записах арифметичних формул надалi вживатимемо скорочення вигляду x y та xПриклад 12. Предикат "х у" в АС N=(N, ar), R=(R, ar), Z=(Z, ar) виражається рiзними арифметичними формулами. Наприклад, для N маємо z(x+z=y); для R маємо z(x+z z=y), для Z маємо маємо z u v w(x+z z+u u+v v+w w=y).
Приклад 13. Арифметичними є наступні функцiї:
1) Функцiя x+y виражається арифметичною формулою z=x+y.
2) Функцiя x y виражається арифметичною формулою z=x y.
3) Функцiя x-y виражається арифметичною формулою y+z=x.
4) Функцiя [x/y] виражається арифметичною формулою
z y x &x<(z+1) y.
5) Функцiя mod(х, у) виражається арифметичною формулою
u(x=z+u y & z6) Функцiя [ ] виражається арифметичною формулою
z z x & z<(z+1) (z+1).
Тeорeма 4.1. Клас арифметичних множин замкнений вiдносно операцiй , та доповнення.
Нехай множини A та B виражаються вiдповiдно арифметичними формулами та . Тодi множини A B, A B та виража-ються вiдповiдно арифметичними формулами , & та .
5. ГОМОМОРФІЗМИ АЛГЕБРАЇЧНИХ СИСТЕМ
Для алгебраїчних систем однієї сигнатури введемо поняття гомоморфізму. Нехай A=(A, I, ) та B=(B, I, ).
Гомоморфізмом АС A в АС B будемо називати відображення : А?В таке, що:
для кожного f Fs арності п для всіх a1 , ..., an A маємо
(fA (a1 , ..., an))=fВ ( (a1) , ..., (an)) (HF)
для кожного р Рs арності п для всіх a1 , ..., an A маємо
якщо рA (a1 , ..., an))=Т, то рВ( (a1) , ..., (an))=Т (HР)
Гомоморфізм АС A в АС B назвемо повним гомоморфізмом, якщо умова (HP) замінюється сильнішою умовою:
для кожного р Рs арності п для всіх a1 , ..., an A маємо
рA (a1 , ..., an)) = рВ( (a1) , ..., (an))=Т (ЕР)
Повний гомоморфізм назвемо сильним гомоморфізмом, якщо відображення сюр'єктивне.
Повний гомоморфізм назвемо ізоморфізмом, якщо відобра-ження бієктивне.
Скажемо, що АС A та АС B ізоморфні, що позначатимемо A B, якщо існує ізоморфізм АС A в АС B.
Таке визначення коректне, бо відношення на множині АС одної сигнатури є відношенням еквівалентності.
Ізоморфізм АС A в АС A назвемо автоморфізмом алгебраїчної системи A.
Приклад 1. Нехай A=({5x | x N}, ), B=({2x | x N}}, ), де ={+, =}. Тоді (x)= є бієкцією B?А, причому для + та = викону-ються умови (HF) та (EР). Отже, є ізоморфізмом A в B.
Відображення (x)= є бієкцією А?В, причому для + та = виконуються умови (HF) та (EР). Отже, є ізоморфізмом B в A.
Приклад 2. Нехай відображення : N?{0, 1} задається так: . Тоді є гомоморфізмом АС (N, {+, =}) в АС ({0, 1}, {+, =}), бо для + та = виконуються умови (HF) та (НР). Умова (EР) не виконується, бо 0 2, але (0)= (1). Отже, такий гомоморфізм не є повним.
Приклад 3. Нехай A =(Z, {+, =}). Тоді (x) = -х є бієкцією Z?Z, причому для + та = виконуються умови (HF) та (EР). Отже, є автоморфізмом АС A =(Z, {+, =}).
Відношення еквівалентності на множині А називають відношенням конгруентності на АС A=(A, ), якщо стабільне відносно базових функцій АС A . Це означає: для кожного f Fs арності п якщо a1 b1 ,
Loading...

 
 

Цікаве