1. Za pomocą diagramów Venna pokaż, że nie musi być spełniona równość A ^ (B v C)=(A ^ B) v C.

A ^ (B v C)=∅

A ^ B =∅

∅ v C = C

2. Czy relacja R jest relacją równoważności, gdzie xRy, gdy x - y jest liczbą całkowitą? To samo pytanie dla relacji S, gdzie xSy, gdy x - y jest liczbą naturalną.

Relacja R jest równoważna gdy x - y jest liczbą całkowitą, ponieważ spełnia 3 warunki równoważności. Relacja S nie jest równoważną, gdy x - y ma być liczbą naturalną, gdyż niespełnia warunku równoważności - warunku zwrotności.

Np. x =4 y=2 4-2=2 jest to liczba całkowita i naturalna, 2-4=-2 jest to tylko liczba całkowita.

3. Pokaż przykład funkcji f określonej na liczbach naturalnych, dla której f(A \ B) = f(A) \ F(B) dla dowolnych A oraz B.

A\B

y=x A i B to liczby naturalne A=4 B=2 f(A\B)=2 f(4) \ f(2) = 4-2 = 2

4. Jaka jest najmniejsza relacja przechodnia zawierająca relację R, gdzie xRy wtedy i tylko wtedy gdy 0<x-y<1?.

xRy yRz xRz 0<x-y<1 0<y-z<2 xRy x>y

5. Zdefiniuj indukcyjnie zbiór symboli działań zawartych w wyrażeniu arytmetycznym. (Zbiór ten dla 2 * x + x to {*,+}.)

Niech f(w) oznacza zbiór symboli zawartych w wyrażeniu. zał. f(liczb)= ∅ f(zmienna)=∅ op -operacja op ε {+,-,*,/}

1. f(W₁ op W₂) = f(W₁) v f(W₂) v {op} 2. f((W))=f(W)

6. Zapisać w normalnej postaci wyrażenie arytmetyczne zapisane następująco w odwrotnej notacji polskiej: 3a*2x-2++.

(3*a)+(2-x)+2

7. Udowodnij indukcyjnie, że dla każdej formuły rachunku zdań można znaleźć formułę równoważną, która zawiera jedynie spójniki logiczne i alternatywy.

p ^ q= ¬(¬p v ¬q) p=> q -> ¬p v q p q -> (p=>q) ^ (q=>p) -> (¬p v q) ^ (¬q v p) -> ¬(¬(¬p vq ) v ¬ (¬q v p )

8.Sprawdz czy następujące wyrażenie jest tautologią ((p v q) ^ r) => (p v q) ^ p v r).

p	q	r	(p v q)	((p v q) ۸ r)	(p v r)	(p v q) ۸ (p v r)	1 => 2
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	0 0 1 1 1 1 1 1	0 0 0 1 0 1 0 1	0 1 0 1 1 1 1 1	0 0 0 1 1 1 1 1	1 1 1 1 1 1 1 1

AvB - lub - alternatywa; A^B - i - koniunkcja; A\B - różnica; => implikacja; równoważność; ¬ negacja

Wartościowania

Gdy q jest niewiadoma

p	p^q	p v q	p=>q	p<=>q	q=>p
0	0	n	1	n	n
1	n	1	n	n	1

Inne wartościowania

p	q	r	q=>r	p=>q	p=>r	p=>(q=>r)	((p=>q)=>p=>r))
1	1	1	1	1	1	1	1
1	1	0	0	1	0	0	0
1	0	1	1	0	1	1	1
1	0	0	1	1	0	1	1
0	1	1	1	1	1	1	1
0	1	0	0	1	1	1	1
0	0	1	1	1	1	1	1
0	0	0	1	1	1	1	1

Odwrotna notacja polska

3a*2x-+2+ (3*a)+((2-x)+2); 345++2- (3+(4+5))-2

p	q	p ^ q	p v q	p => q	p <=> q
0	0	0	0	1	1
0	1	0	1	1	0
1	0	0	1	0	0
1	1	1	1	1	1

---