Strona główna

Do użytku wewnętrznego zadania z logiki


Pobieranie 34.22 Kb.
Data18.06.2016
Rozmiar34.22 Kb.

Do użytku wewnętrznego

ZADANIA Z LOGIKI

LISTA nr 1

Dla danego zbioru A i każdego n > 0 , określamy operacje trywialne n – zmiennych następująco: E(x1 , ... , xn) = xi . Dla danej algebry A = j}j J , {ak }k K > , rodziną działań algebraicznych A(A) jest najmniejsza rodzina skończenie argumentowych funkcji z A w A zawierająca wszystkie funkcje trywialne, wszystkie funkcje {Sj}j J oraz zamknięta ze względu na składanie i podstawianie wyróżnionych elementów {ak }k K .



  1. Niech A =  K> , gdzie K jest ciałem, będzie przestrzenią liniową nad ciałem K. Uwaga,  jest unarnym działaniem oznaczającym mnożenie przez   K . Wykazać, że A(A) jest zbiorem wszystkich kombinacji liniowych, tj. jeśli F  A(A) jest działaniem n zmiennych, to istnieją 1 , ... , n  K takie, że F(x1 , ... , xn) = 1x1 + ... + nxn , dla każdych

x1 , ... , xn  A .

  1. Niech A = 0> będzie dowolną grupą abelową, gdzie – jest działaniem jednoargumentowym oznaczającym element przeciwny. Przyjmując standardowe oznaczenia

na = oraz –na =

dla dowolnego naturalnego n , udowodnić, że A(A) jest zbiorem wszystkich całkowitych kombinacji liniowych. Czyli jeśli F  A(A) jest działaniem n zmiennych, to istnieją całkowite



m1 , ... , mn takie, że F(x1 , ... , xn) = m1x1 + ... + mnxn , dla każdych x1 , ... , xn  A .

  1. Niech A = będzie kratą, tj. algebrą, w której działania binarne  i  spełniają następujące aksjomaty:

przemienność

ab = b a

ab = b a

łączność

a  (bc) = (ab)  c

a  (bc) = (ab)  c

idempotentność

aa = a

aa = a

dystrybutywność

a  (bc) = (ab)  (ab)

a  (bc) = (ab)  (ab)

Wykazać, że każda funkcja F  A(A) jest postaci

F(x1 1 , ... , x1 n , ... , xm 1 , ... , xm n) =  xi j .

  1. Przy założeniach Zadania 3 . Wykazać, że każda funkcja F  A(A) jest postaci

F(x1 1 , ... , x1 n , ... , xm 1 , ... , xm n) =  xi j .

  1. Niech 2 = <{0 , 1} ,  ,  ,  , 0 , 1> będzie algebrą, w której operacje  ,  i  są znanymi operacjami z rachunku zdań. Wykazać, że każda skończenie argumentowa funkcja

F : {0 , 1}n  {0 , 1} jest elementem A(2) .

  1. Niech A będzie zbiorem n elementowym. Obliczyć, ile jest algebr , gdzie F jest działaniem m argumentowym.

  2. Dwie algebry A1 = }j J , {a}k K > i A2 = }j J , {a}k K > są algebraicznie równoważne jeśli mają te same działania algebraiczne, tj. A(A1) = A(A1) . Wykazać, że algebry i , gdzie + jest dodawaniem a – jest odejmowaniem nie są algebraicznie równoważne.

  3. Niech B = c , 0 , 1> będzie dowolną algebrą Boole'a. Niech B1 = c > ,

B2 = c > oraz niech B3 = będzie algebrą, w której

xy = (xyc)  (yxc) . Udowodnić, że A(B) = A(B1) = A(B2) = A(B3)

  1. Niech  będzie relacją na Z określoną przez xy iff x i y mają ten sam znak. Czy  jest kongruencją w , a w . > ?

  2. Podać przykład dwóch systemów relacyjnych A i B oraz homomorfizmu

h : A  B , który nie jest silnym homomorfizmem.


©snauka.pl 2016
wyślij wiadomość