Дать определение формальной арифметики. Сформулировать теорему Геделя о неполноте.

Формальная арифметика получается из теории с равенством добавлением константы 0, введением функциональных символов. f(x,y) = x + y, g(x,y) = xy, next(x) = x’ и добавлением следующих собственных аксиом: (Ar1) F(0) ( х (F(x) F(x’)) x F(x)), (Ar2) (t’₁ = t’₂) (t₁= t₂), (Ar3) (t₁ = t₂ ) (t’₁= t’₂), (Ar4) t’ 0, (Ar5) t + 0 = t’, (Ar6) t₁ + t’₂ = (t₁ + t₂)’, (Ar7) t·0 = 0, (Ar8) t₁· t’₂ = t₁ · t₂ + t₁. Аксиому Ar1 называют принципом математической индукции. Приведем другую формулировку этого принципа. Свойство 1. Если ⊢ F(0) и ⊢ F(x) F(x)’, то ⊢ х F(x). Доказательство состоит из следующих утверждений: 1) ⊢ F(x) F(x)’ – дано по условию; 2) ⊢ х(F(x) F(x’)) – из 1) по правилу обобщения; 3) ⊢F(0) – дано по условию; 4) ⊢F(0) ( F(x) F(x’)) x F(x)) – аксиома Ar1, 5) ⊢ x (F(x) F(x’)) x F(x) – из 3) и 4) по правилу MP, 6) ⊢ x F(x) – из 2) и 5) по правилу MP. Свойство 1 доказано. Моделью для формальной арифметики является множество N^u обычными операциями сложения и умножения, а next(x) = х + 1. В отличие от исчисления высказываний и исчисления предикатов формальная арифметика не является полной. Мы приведем без доказательства формулировки теоремы о ее неполноте. Теорема Геделя о неполноте. Существует замкнутая формула F такая, что в формальной арифметике не выводиться как формула F, так и ее отрицание .

1.19. дать определение дизьюнкции, коньюнкции и отрицания в нечеткой логике. доказать в нечеткой логике, что a v (b с) = (а V b) ∧ (a V c) и = V . В нечеткой логике рассматриваются функции у=f(x₁,…, x_n),где X_i [0;1] при i= 1,2, …., n и у [0;1]. Определение 1. Значения нечеткой дизьюнкции и коньюкции определяется по формуле у= х₁Vх₂=max(x₁,x₂) и у = x₁∧x₂= min(x₁,x₂). Следующие свойства нечеткой дизьюнкции и коньюнкции такие же, как и для двузначной логики: 1)a V 0 = a; 1’) a ∧ 0 = 0; 2) a V 1 = 1; 2’) a ∧ 1 = a; 3) a V a = a; 3’) a ∧ a = a; 4) a V b = b V a; 4’) a ∧ b = b ∧ a; 5) a V (b V c) = (a V b) V c; 5’) a∧ (b ∧ c) = (a ∧ b) ∧ c; 6) если a b, то a V c b V c; 6’) если a b, то a ∧ c b ∧ c; 7)a ∧ (b V c) = (a ∧ b) V (a ∧ c); 7’) a V (b ∧ c) = (a V b) ∧ (a ∧ c). Свойства 1 – 6 и 1’ – 6’ непосредственно вытекают из определения: приведем доказательство свойства 7. Пусть b c, тогда a ∧ (b V c) = a ∧ c и (a ∧ b) V (a ∧ c) = a ∧ c, т.к. a ∧ b a ∧ c по свойству 6’. Свойство 7’ доказывается аналогично. Определение 2. Значение нечеткого отрицания определяется по формуле у= =1- х. Следующие св-ва нечеткого отрицания совпадают со свойствами отрицания в двузначной логике: 1) = 1, 2) = 0, 3) = a, 4) a b, то , 5) = ∨ , 6) = ∧ Доказательство свойств 8 – 11 очевидно; докажем свойство 12. Пусть a b, тогда = , так как a ∧ b = a; a ∨ = потому, что b. Св-во 13 доказывается аналогично. Определение 3. Функция у = х ∧ называется противоречием, обозначается у = . Из этого определения вытекают следующие св-ва: = 15) Определение 4. Функция у = х ∨ называется тавтологией, обозначается у = . Из этого определения вытекает следующие св-ва: = 17) Заметим, что в двузначной логике х ∧ 0, а х V 1, что не имеет места в нечеткой логике. Определение 5. Функция у = f(х) называется противоречивой, если f(х) для всех х Примером противоречивой функции является у = . Определение 6. Функция у = f (х) называется общезначимой, если f (х) для всех х . В качестве примера общезначимой функции можно привести тавтологию у = .

1.20. Дать определение нечеткой импликации и эквивалентности. Доказать в нечеткой логике, что a b = (a ∧ b) V ( ∧ ). Определение 1. Нечеткая импликация определяется по формуле а b = V b. Из этого определения вытекают следующие свойства: 1) 0 a = 1, 2) a 1 = 1, 3) a a = ∨ a = Определение 2. Нечеткую эквиваленцию можно определить по формуле а b = (a b) ∧ ( a). Отметим следующие св-ва нечеткой эквиваленции: a b = ( ∨ b) ∧ ( ∨ a), a a = V a = , a b = (a ∧ b) ∨ ( ∧ ). Докажем свойство 6. Для этого разберем два случая. 1) Пусть a , тогда b, из них выводится, что ∧ b) ∧ (a ∨ ) = ∧ ⟹ a b = ∧ . С другой стороны, ∧ ⟹ (a ∧ b) ∨ ( ∧ ) = ∧ , следовательно, a = (a ∧ b) V ( ∧ ). 2) Случай a разбирается аналогично. Замечание. Можно ввести в нечеткой логике и остальные логические операции по формулам х ⊕ у = – “ исключающие или “, х ⎡у = ∨ - штрих Шеффера, х ↓у = ∧ - стрелка Пирса.

1.21. Дать определение нечеткого множества и операций дополнения, пересечения, объединения, возведения в степень, умножения и сложения нечетких множеств. Доказать, что A B ⊂ A + B.

Нечеткое значение высказывания Р будем обозначать µ(Р). Определение 1. Множество А называется нечетким, если задана функция принадлежности, которая по любому его элементу х определяет число µ_А(х) = µ(х [0;1], равное нечеткому значению предиката х U\ А, где U – универсум, считается по умолчанию, что µ_А(х) = 0. Пример 1. Зададим нечеткие множества А и В таким образом: А = /х₁, 1/х₂, 0.8/х₃, 0/х_{4 ,} В = ; из этой записи следует, что µ_А(х₁) = 0.3, µ_А(х₂) =1, µ_В(х₁) = 0 и т.д.. Определение 2. Для нечетких множеств можно определить отношения равенства и подмножества: А = В, если х(µ_А(х) = µ_В(х)); А ⊂ В, если х(µ_А(х) µ_В(х)). Заметим, что, если х(µ_А(х) = 0), то множество А считается пустым, А = ∅. Определение 3. Функции принадлежности для дополнения, пересечения и объединения нечетких множеств определяется так: (х)= 1- (х), = ∧ = min (, (x) = V (x) = max ( (x), (x)). Из определений 2, 3 и свойств отрицания, коньюнкции и дизьюнкции следует, что на нечеткие множества переносятся обычные свойства операций дополнения, пересечения и объединения. Отметим некоторые из этих свойств. 1) А А = А. 1’) A A = A. 2) А (В С) = (А В) (А С). 2’) A (B C) = (A ) (A C). 3) = . 3’) = . Определение 4. Введем операции возведения в степень, умножения и сложения нечетких множеств, задавая их функции принадлежности таким образом: (x) = (x) при n 0, (x) = (x) · (x), (x) = (x) + (x) - (x) · (x). Отметим некоторые свойства введенных операций. 1) ⊂ A при n 1. 1’) A ⊂ при n 1. 2) ·B ⊂ A B. 2’) A B ⊂ A + B. 3) = + . 3’) = · . Пример 2. Если А и В – множества, данные в примере 1, то А В = А В = , = А· В = ,А+В = Пример 3. Пусть нечеткие значения предикатов р = (х А), q= (x B) и r = (x C) следующие: р = 0,2, q = 0,4 и r = 0,7. Найти нечеткое значение предиката s = (x Решение. Поскольку s = ∧ (q V r), то подставляя значения p,q,r, получаем, что s = 0,8 ∧ (0,4V0,7) = 0,8 ∧ 0,7 = 0,7. Ответ. Нечеткое значение предиката s равно 0,7.

Дата добавления: 2015-08-21