Transcript
Page 1: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������������

MATEMATIKADISKRIT

Page 2: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ��� ���������

Page 3: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������������

MATEMATIKADISKRITSamuel Wibisono

2EdisiEdisi

Page 4: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ��� ���������

����������� �����

���� � ������ � ����

�� ��� � ��� � ���� ������������

�� � ������������� �����!�"##$

%���� &���©�"##'!�"##$�&����&��� �!%���� &���� � ���� ������(�����)�* ��������&������������� ������������� ������������� � ���� � �������������&��&�!��������������� ���&������ �!���������+�����& !������!��������������� ��&���������� ����!����&�� � ������� ����� �&����� �)

���� �,������ ��� �-�����./0����������'''112��&) �� #"34($$""/"5� #"34(44/"16'7�8) �� #"34(44/"16/

����������� ��

������������������� ����������

� �������� ��������� !�"# �$���� �%&&'(��)*+,$���*-��./%01�.

�23/+4'�+4+�45,�6*0�*

*.��!���!��� �.- � �

�(� � �� �+�9����� �)��) �

Page 5: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������������

������� ��� � ��� ���� ������������ ������ ���������� ���� ��������� �� �� �������� ����������������������������������������� �������� ��� �������������������������������

������ ���� �� ����� �������� � ���� ��� ����������� ����������� �������� ����������� �� ����������������������� ������������������������ ������������ ������������������������������ !����� ������������"���������� ������������� ������������ ��������������������������������������������������������#������� ���� �� ������� ����� ���������� ����� ����#��������������� ���������������� ����� ������������������ ����������������������������������� ������� ������ ���������������������������������������� ����� ����� ������ ���� � ������ �� ������������� � ������������� ������� ��������� ������������

$�� ����������� �������������� ������������� ������������������������� ���

������������������������������������������������������������

Page 6: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� �� ��� ���������

� %������������� ����������� ��������������������� ����������

� %������������� ������ ����� ���� �������#���������������������������������������������� ������������� �������� ������

� %������ ����� ���������� ������� �� ������������ �������� ����� �� ��� �� �� ����������������������&'������������

%������������������ ���������������������������%��������(���)��������*��+�����������)�#�������'�������,��)���� ���������� �������������#���������������� ��������������������������������������� ���������������%������-����' �������� �������������������������������������.����������������

&������� ��� �������� ���� ����� ���� �����������#������������������������ ��������������������������� /���� (�� � (0� ���� ��������������������������������������������������������������������������������������������������#������������������������������������

������ �����������������

0��������������.112

(���� 3�����

Page 7: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ����� ���

������������ ��� ������ �������� �������������� �

4�4� %��������� 44�.� %���������-������� .

4�.�4 5������� .4�.�. ������� 64�.�7 +���� 84�.�6 0������� 9+��:;<+:;= >4�.�? +�����9+�+�= >4�.�8 ,@� ���� �� 9�@��= 24�.�> ,@� ����+:; 9,@+:;= A

4�7 &���� �� ������������ 414�7�4 &���� �� 414�7�. 5�������� 41

4�6 5���������B��� 444�? � �����%������ 4.4�8 '�� ��� ���*�� ��� 46

4�8�4 '�� ��� 46

������ � ������ � ������ � ������ � ������ �

Page 8: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

���� �� ��� ���������

4�8�. *�� ��� 424�> ���������� 42

4�>�4� 5��������<C� ����������� 4A4�>�. *�����#����������������� .4

4�2� 5������%��������� .?4�2�4 �����#�����5������ .84�2�. +����5������ .>

����� ������������� ��.�4 $������ 74

.�4�4 5����� ��� 7.

.�4�. $������*����������&��*������� 77

.�4�7 5����������$���������(��������� 76

.�4�6 �����#�����$������ 78.�. :�����$������ 78

.�.�4 )���<-����������.������� 78

.�.�. '����������<'������� .$������ 7>

.�.�7 ;� ��������� �����<(� ��������.$������ 7>

.�.�6 5��� �������$������ 7>

.�.�? (���������������<*���(�������� 72.�7 ������C��� 72.�6 $����#������ �����$������ 7A.�? %���������$������-������� 64

.�?�4� -����������.$������ 64

.�?�. -����������7$������ 6.

����� �������������� ���� ��7�4� /���� ����������� 6A7�. :������������ ��DD� ?4

7�.�4 5��� ���� ?47�.�. -�������<)���$������/�DD� ?.

Page 9: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ����� ��

7�.�7 '����<'���������$������/�DD� ?77�.�6 %���������<E��$������/�DD� ?67�.�? %�������� 9(������=$������/�DD� ?>7�.�8 (�� ��E����� �� ?A

7�7 5����������$������*���� 81

����� ������ ���� ��6�4 %�������� 8>6�.� B����������+ �5��������*������ 826�7 (�� #��� >.

���� ������������ � ?�4 %������ ��� >??�. %��������;� �� >>

?�.�4 %��������5������� >>?�.�. %������������� >2?�.�7 %������� >2?�.�6 -����*������ >A

?�7 :������� ��;� �� ����� 21?�7�4 '������;� �� 9;F4= 21?�7�. 5������ ;� �� 24

?�6 ,��� ���5������� ���:������;� �� 2.?�6�4 ;� ��,��� �� 2.?�6�. ;� ��5������� 2??�6�7 %���� 9%���� �:������(��= 28

����� ���� ��8�4 ����� /���� A78�. �����#�����/���� A6

8�.�4 /���� ����#���� A68�.�. /�������� A?8�.�7 /���� ������� A88�.�6 /���� '����� A8

8�7 5������ /���� A28�6 /����5���������� AA

Page 10: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

� �� ��� ���������

���� ��!��������� �"�>�4 �� ���� �����*�� ��� ��

0������("����� 417>�. �� ���� �����*�� �����

;�������B��� 9-���= 41>>�7 �� ���� �����*�� ��� ��:�����5� �����

%����������5�� 95%5=���/�����%����������*���� 9/%*= 444

>�6 ���� ��� 9���������+���� /���= 447>�6�4 ������&��� '�� ������5�������� 447>�6�. %���5������� 448

����# �������� �� 2�4 %������ ��� 4.?2�. �����#�����-���� 4.>2�7 5�������� 47.2�6 *�������������0���� 4762�? �������<������ ����� ��� 4782�8 &��%�����-���� 9E��%���= 47>2�> )����������������� 4722�2 �����-���� 47A2�A B��� �������� 4642�41 �������&������������� 4662�44 -����*���� 9% ����-����= 46?2�4. %�"����%��� 46>2�47 %����<&��� 4?A

2�47�4 (������&��� 4842�47�. %����*������ 9;�����&���= 4872�47�7 %����*������*������

9:�����;�����&���= 48>

����� ��������������� �� A�4 %������ ��� 4>?A�. /����������� 9/�= 4>>

Page 11: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ����� ��

A�.�4 �������������/������������� 4>2A�.�. �������������/�������

����/���� ?#&�� � 421A�.�7 �������������/�������

&��� (���� 424A�.�? +��#����������/���

�������� 9+/�= 424A�.�8 /���(����&���������� 42A

�� ���������� ����������������� ��

�������

Page 12: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ��� ���������

Page 13: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������������

���� ����������

B���� ������� ����� ���� ������ �������������������� ������������

B���� ������� ���� ����������#���������� 9����������� ��������������=�

%��������� ��� �� �� ��� ��� ���� ���� ��������������������#�������� ���� ����

��G����

%����������������� ���� ����� ��������� ���� ������9���������������=�������� ��� ��9������������ ��=������ ������������� � ���������#�������

5���������������� ����������������������������� ������������� ���������� ���������

�������4� * ����� ���� �������� �� �� ����� ���� ��� ��

��������������������

�� �������� � �� �������� � �� �������� � �� �������� � �� �������� �

Page 14: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ��� ���������

.� (������� �� ������������������������� ��� ������������������ ���

7� ����������� ���� ����� �������� �� ��� �� �� �����������������������������

6� (��� ��� �������� '�� ����� ������� ��� �� �������������������������� ���� � ��������������� ��� ���

?� E���D��� ��� ����� ��������� ��� ������� ��������� 'C������� ���� ����� ��� ����������������������

5� ���#�� ��������������������������������� ���

� 5� ��� �������� 5� �������������� 5� ������������� 5� ����������� 5� ���HH"� �����H��

��� �����������������

*������� ���������� ����� ������� ������ �������������� ���� ����� ����<������ ����� ���������� ������ �������� ������ ���������� �������� ���� �������������������������������� � ���

�����#������������������������

����� �������

5���������� ����������������������������������#����������������������$%&+����#��������������

� �� ��@G���G��G

*���������������������������� ���������������� 5����������� ������������������������� ���� ����

Page 15: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������������

* � ����*��� ����������������� �������������� � ��� ����� ����������� ����� ������ ������������� ������������� ��������*����� �<�����* � ����*������ ����������������� ������������� ���� ���� ���������� ������� ����� ������ �������������������� ��������*��������� �<�������������� � � ����� ���*���� ������ ������ ����� ����� ������"��������������� ���������������� ������ ���

&��� 5��������5�������

� �

��

� ��

����

����

����

����

����

����

����

�����I��������������#�������� ��

�������� J �������� �� ��� �� ����� ���������� ����� ���<

��������������������������������#��������� ������������������� �����������������

G J ��������� ��� �� ����� ���������� ����� ���<��������� ����� ����������������� � � ������� ������� ����������������������

Page 16: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ��� ���������

� J ������ ���������� ��� �������� ����������#��������� �� ��������� ��� ������������ ������ ��

� J � ����� ������� ��� ������������������������� ������� �������������� ���

��� �� ��� ��������������������������������G������G� ��� ���������������� ��������G��������� ������ ��� ���������������� ����������� ������ ���

����� ������

������� ��� �� ���������� �������� ��� ��� ���#���������������������������%'%(�

+����#����� ��������� ���� �� �

*����������������� ����� ���� �� �� ������ ������� ���������������� ������������������������� �������������� �

��

Page 17: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������������

* � �������� ����*������������ �����������������<����� ������������������������������������������������ ��������*����� ��

* � ������������ ����*���9�������� ����=��������� ������������������ ������������������������������������������������ ��������������������� �������������������� ��

* � ��������*������������ ������������������ ���������������

������ ������ ����� ����� ��� ���"� ��������� ��� ������ ���������� ����������

&��� 5���������������

�����(��� ���� ��������������������������

*���� J&�*�I�4(� �� J/�(�F�1

�������� J ����������� ��� �� ����������������������

���� ���� ���� ���������� ��� �� ����������������

G J $������ ��� ��� �� ��������������������������������������� �������������� ���

� J %�������� �������������������������������������������� ������������������

����

����

� ��

����

����

����

����

����

Page 18: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ��� ���������

� J 3���"� K% ��� �� ������������� � ������� �������������� ���

��� �� ��� �������������������������������G�� ���� �� ��� ��������������������������������������

∨� � ��� ��������������� ��������G�� ������ ���

����� �����

+���� ��� �� ������ ���������� ����������������������������������������������������� ����� ���� �����"�H!����������������������������!�� �������������������

+����#����� ������

������� ′

�������� J $��������� ��� ������������������������������

����������� �������������� ��

�L� J ��� �� �� �����"����������� ��� �� ���������#

����� ��������� ����� �������� ��� �� ����������������

0������������������������� �� �"������������#����������������

&��� ���������������

��

��

Page 19: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������������

����� �������������������������

0������� ��� ���������������������������� ������������������������

+����+:;�

���������������� ∨↓

5����� �������� ��� �� ����� ��� ������� ���� ���������+:;��� ���������������

����� ������������ �

+�+���� ���������������������������� �������������������������

+����+�+��

���������� ′∧∧

5����� +�+� ����� ��� ��������� ���� ���� ���������+�+���� ���������������

����

����

� ��

����

����

����

� �

����

����

����

����

����� ∧ �

����

����

����

����

����

����

��������

����

∨� � �� � �� �

Page 20: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ��� ���������

����� !"���#���$���!�$�

,@�� ��� ������������ ������������� �� �� ���������G9���������#������=��� �������

+���� �@���

�� ���

�������� J �������� �� ��� �� ����� ���������� ����� ���<

��������������������������������#��������� �������������������� �����������������

G J ��������� ��� �� ����� ���������� ����� ���<��������� ����� ����������������� � � ������� ������� ����������������������

� J ����� � ����� ����� ��� �� ����� � ����� �������������� ������������ ��� ������������������ ���

� J � ����� ������� ��� ������������������������� ������� �������������� ���

���� ��� ��� ���@�������� ���������������G�������� ��� ��� ���@��������������������������� ����� ��� ��� ���@�����������������G��������� ����� ��� ��� ���@�������� ����������� ������ ���

������������ ���� ��������� �@�� ����� ��� � �������������

�� �� ���� ∨ � � �� � � ��

�� �� −� � �� −� ���� −� �� ���� �� �� −�−� �� �� � −� �� ��−� −� −� � −� −� −�

Page 21: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������������

����% !"���#������� !����

,K+:; ��� �� ���������� �������� �&)*%+%& ���,K:;������ ������������������� ��������������#���������������� ���

+����,K+:;�

)q p(~ ∨

�������� J �������� �� ��� �� ����� ���������� ����� ���<

��������������������������������#��������� �������������������� �����������������

G J ��������� ��� �� ����� ���������� ����� ���<��������� ����� ����������������� � � ������� ������� ����������������������

� J ����� � ����� ����� ��� �� ����� � ����� �������������� ����������� ��� ������������������ ��

� J � ����� ������� ��� ������������������������� ������� �������������� ���

���,K+:;G���� ����������������������,K+:;�� ��� ������������������ ���,K+:;G� ��� ������������������ ���,K+:;�� ��� ���������������������

������������ ���� ���������,K+:;�

����

����

����

������� ∨

Page 22: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ��� ���������

��� ����� ����������� ��

%������ �������� ��� � � ������������ �������� ������������.����

����� &������

&���� �� ��� �� ������� ���� �� � � ����� ��������������������

+���� ����� ���

��L�

�������� J $��������� ��� ������������������������������

����������� �������������� ��L� J ��� ���� �����"����������� ��� �������������#

���������������������������� ������������������

����∨ ��� ������������������

&��� ��������� ����� ���

����� ����$���'��

5�������� ��� �� ������� ���� �� � � �� �� �������������������

+���� �������������∧

��

��

��

��

��

��

����

��� ���∨ ��

��

Page 23: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������������

�������� J $��������� ��� ������������������������������

����������� �������������� ��L� J ��� �� �� �����"����������� ��� �� ���������#

����� ��������� ����� �������� ��� �� ����������������

����∧ ��� ��������������� ��

&��� �������������������

��

��

��

�� ���∧

��� ������������ �

������������������������������������������� �� �����������������

�������4� &������������"�� ����� ������� ��� �����������

�������������� ������� ������������������.� � �����*�� � ��� ��� �������������������������

������� ������������������

5���� ���������� � ������������ � � ������������������0����������������������������<���� ���

������������������ %9�� G� �� ���= ���M9�� G� �� ���=����� �������� ������ ������ � ���� ��������� �����������������������������������������������������%9��G������= ≡ M9��G������=�

��

Page 24: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ��� ���������

�������(� �����������������������"���������

4� &������������"������� ������������������� ����������� ������������� ������������������#����� �������� �����

.� (����� ��������� �������������� ���������#�� ���������������"���������� ��������������#��������� �������� �����

5������������������������ �������������������

4� ����� ∨.� L ���∧

������� ���� �������������������������

�� �� ��� ��� ���� ∨ � ����� ∨ � ������ ∨ �

�� �� −� −� �� −� −��� −� −� �� �� −� −�−� �� �� −� �� −� −�−� −� �� �� −� �� ��

0��������������� ������������������ ��������� ∧≡∨

�� �������������� �

� ����� ������������������������������#������ ����� �� �� ������������

$����#���������������� ���

4� '��������� � �� � �� �

� �

��

Page 25: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������������

.� �������

� � � �

� � � �

� � � � � �

� � � � � �

� � � � �

� � � � �

7� 5�������� � � �� � � �� � �

� � �

6� �������

� � � � � �

� � � � � �

� � � � � � �

� � � � � � �

� � � � � �

� � � � � �

?� '�������

� � ������������������� � �� � �������������������� � �� � � �

� � � �

8� 5��� ����

������������������������������������������

==∧==∨

>� '��� ����������� ≡

2� ��������N�

���������������

∧=∨∨=∧

A� �������

����������

≡∨∧≡∧∨

41� '�� �������� ∨=→

44� *�� ���

���������� →∧→=↔

��

Page 26: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ��� ���������

4.� 5��������������� →=→

(� �� ����������� �����#������ ����� ������� ��� �����������������������������������������

�������(����������� ������� � ��"�� 9������� ������

�������=�

� � � � � �

� �

� � � � � � �

� � �

� ��

� � � � � �

� � �

� �

��� ���� ��� ������ ��� ���

����� ()*��'���

%������������������������� �����������������3�������3���"���� �� ���������������

��������3������������ ������ ��������3���"�����������3���"���������� ������ ��� � ��� ��������3������������������3�������������������������"�#��"� �����3���"�������������� �������������3����

E������������������������������������������������� �������� ����������

+���� �� ����

� ��

��������������G

��

Page 27: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������������

� ��

����

����

����

��������������� ������

4� 0����������3�������3���"� ����� ������������ ���� ��������������������������������������

������������� �������������

.� 0�� �������� 3��� ���� ����� 3���"� ����������������� �������������� ����������������������������3��� ��� ��3���"�

7� 0�� ����� �������� 3��� ���� 3���"� ����������������� ������������������������� ��������3���"� �����������������3���

6� 0�� ������������� "������������"���"� �����������#������ �������������������������� ����� ����������3�����������������������������3���"��

&��� ��������� �� ��� ������ �������

���������� ����������������� ��������G��� ���� �����

���� �������� �������������������������������

� �� � �� �

!%,%-.

%���������������������������

� �� � �

� ��

� �

��

Page 28: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ��� ���������

0���������������� ��

*������������� �

������������

����

����

� ��

����

����

����

����

� ��

����

����

���� →�� �� ���� →

�����������#�$�+�(�#�$�+���������$�*�����

0���� ���� � ��

����� 5��������� � �� →'�������� � ���� →5������������� � ���� →

�������0����������3�������3���"������������������ ���� �������������������������� �������������

5����������� � 0��3���"� ����� ���������������������3��� �� ��������

'��������� � 0���������������3������������3���"� ����� ���������

5������������� � 0�� �����"���"� ����� ��������������������������3����� �������

&��� ���������

����

����

��

��

����

+

r r

��

Page 29: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������������

0�� ����� ����� ��� ���"� ������� ���� �� ��������#����� �������� � � ��������� ���� ����9 ������ �=�

*������������������������������������������������� �� �� �� ������ �� ����� � � � � ���������������#���������

�������*���������"��

0��@�� ���������������@����� ����������

�������� ��@���J����� → @J�����

�� �5���������� ��� �� ���� ������� ���

0��@������ ��������������@����������� �����������

�������� � �

0��@J���� ����@��J����

(����� ������� ��������������� ������ ��������@���� ��� �@J.�I4��� ������� ������������

� �

� �

��

� �� �

�� �� �

� �� �� �

� �

� � �

� � �

5����� � � ������� ��������� ����� ������� ��.� ����� ����������.��I.� ����� ����������

�������@�J� ��������� �������� �����������������4����������� ��������� �

0������������������������������� ����������������

��

Page 30: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ��� ���������

����� ��� ������

%�������������������������

��������3���������������������������������������� �����������3���"�

%��������� �������� ������ ��� ��� ���� ��������� ����������

+������� ���� � ��

���������������������G

������������������ ������

4� ��������3���������������������������������������� �����������3���"���� �����������������

*������������� ��� �����������

.� ��������3����������������������������������������������������3���"���� �������������� ��

7� *������������3��� ��� �������� ���������� ��#����������������������3���"���� �������������� ��

6� *������������3����������������������������������������������������3���"���� ����������#�������

&��� ������������ ����

� ��

����

����

����

��� �������� ���������� ��� �� ����� �� ����������#����������

��������� �������#�������������� �������������������������� �� 9���� ��=

��

Page 31: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������������

+�����

%�M�H �����#���������������������������������O%�M�HP �������#�����������������E ��� �� ���� ����<������ ��

�������0�������� �������� � ������

���� � ������

∴���������� ����

��%��� ��,���$���-����������$)��

C� ���� �������� ���������� ��� � � ��������������#������������������� ������

(���� �������� �������� �� � � ������#��������������������������� ���������������

���������0������������������ �������������������� ���������

0�������������� ����������������������������� ����

∴0������������������ ����������������������������

� �

� �

� �

� ����

� ����

� �����

��

Page 32: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ��� ���������

������� �������� ����� ��� ���� ������ ����� �������������

� �� �� �

� �

(���������������� ���� ����������

�/'/+%&)%&�.

B��������� �����4������� �����.����������������������������5��������������� ������ ����������95����� ������������������������4���.������ ��

� �����=� %�������� ����� ���� ��� � �� �� �� ����������������� �������

���������������� �������� � ���� �� �� ������ ������ �����

�������������������� ��������������������

��

� ��

��������

��������

��������

��������

�→���

��������

� ��

��������

Page 33: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�������������� �

���������������������� ����������������������������� ������ ����������������� ������ ��

∴���������� ���������

����������������������������������������

� ���

�������������������������������������������� �����������������

������������

�������������

����������������

� � ���

����

����

����

���������

����������������������������������������������� ���������������� ���� ���� ����������

����� ����� ���������������������������

�� �� �������������� �� �

Page 34: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� �����������������

!� ������������ �� �

"� ������ #���

� ���

$� ����������� �������

� � � �� � � �

� �� �

� � �

� �

%� &������������ ���������

� �� �� �

� �

'� (�����)������� ���

*� ��� ������� ���������

�+,---�+---

.� ������ /�����

+,-----�,-------�+---

Page 35: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�������������� ��

0� ����������� �������

�,+,------1,�,

123��23+

∨∴∨

→∧→

�4� � ������

� �

� �

� � �

� � �

��������� �� � �5������������������������������ �6�������������������� ��� �����

�� ����������������������������������������!� ����� ������� �������� ����� ������ ������

��� ����"� �����������������������������������������������

������ ��$� &����������

��7

������

��� ��� ��� ���

�������������� �

��������

�������

��������

��������

�����&������������(��������

� �� �� �

� �

� �� �� �

� �

Page 36: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� �����������������

(�����������������������������������

���� ����� ������

�����������#��

���� ������

���� ������

(�����������������������������������

��������

������� ������������������������������� � ��� �������������������� ���

��������� �� �

������������

Page 37: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�������������� ��

5���������� �� ����� ���

� �

�����������������

����������������

����������������

�����������������

�����������������

�����������������

�����������������

�����������������

�� → � → � → �� ∧

∴��������������������

���������������������

�������� #89:� ������� �������� ���� ������������ ���9����;���������� �����������������#��������)������������� ��������� ������� <= ∈ � ������#89:� ������� �� ������������

�������������� #89:� ������� �������� ����� 9� ������� �� ��� ����������� �����

����������>�������� ������ ������������

Page 38: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� �����������������

����� )��������������#89:��������������?

�����9 > �������������������������� ������ ����������8):

�����9 > !����������������!�������� ������ ����������8�:��� ���������

���������������� ������������ ������8��������:�������������� ���������������������������������� ��������������������� ����������������������� �������� ���������

����� �����������������

�������������������������������������������������?

�� ������������9��#89:���� ������������������� ��������������� �

!� ����� � �����8������������������:� � ��� � ����� ��� ������ �9����������� ��������������� �

�������������� 9� ������� 6���� ����� @�������� #� ���������� ������ ����������������� ���������

� � �� � ��� �� � �����? (����� 6���� ����� ����

������ ��!� � � � ��� � � �� � �����? ���� � ����� 6���� ����

��� ���� ����� ��� ����� ��

"� � � � ��� � � �� � � �����? (������6��������� �������� ���� ����� ����� ��� ����� ��

Page 39: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�������������� ��

$� � � � ��� � � �� � � �����? ���� 6���� ����� ��� �������� ��� ������ ��� ����� ��

����� ������������

������

∀=∃∃=∀

�����?

�������������

�������������

∀=∃

∃=∀

������������ →∀ > �3=223�3=2= →∃

> Q(x)xP(x) ∧∃

������������ →∃ > �3=223�3=2= →∀

> �3=2=�3=2 ∧∀

�������������� /��������� ����� �������������������� �6��?

8�: � �� � �� �

8 : �������� ∧∨∧8�: � � � �� � � �� � �

8�: �������� ↔∨∧

8�: ��������� ↔↔∨

8): ���������� ∧∨∨∧

8�: ��������������� ∧∨∧∨∧

!� (��������������������� ��� �6��?8�: � � � � � � � �� � � � � � � �� � � � � � �

8 : ����������� ∨∧∨∨∧

Page 40: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� �����������������

8�: �������������� ∧∨∨∨∧∨

8�: ���������������� ∧→↔∨→∨

8�: ������������� ↔∨∨→∧

"� 5���������� ��6����������� � ��

8�: +,+� ∨≡

������� ↔→∧≡

8 : ���� ∨→≡

������� ↔→∧≡

8�: ���� ∧≡

��������� ↓↓↓≡

8�: ���� ∨≡

��������� ↓↓↓≡

$� ���������������)� ������������ ���������������� �6��?8�: ����������������!� ��������������� ��������������

���������� ������������ ��8 : ����� 9� ���� ������ ����� ���������"�������9�

���� ���� ������ ��������������"

%� (������������������������������� �6��� ?8�: �� ����� ������)�� 6��� ����� 6���6�� ������

��������!� ����� �����������������)������� ����6��

��6�� ������� ��������"� A��9

� ����������)��6��

8 : 5���� ���������� ���� ������ ���� ���������� �� �6��?

Page 41: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�������������� ��

�� ����� �������� ������� �������� ����� ���������������� ������������� ������������������������� � ��5����

!� (��������������������� ���������"� /���������������� ������ � ��5����$� /����������

� 7

8�: �� ��B))����������������������� �������� �����������������

!� C������������������� �������� ���������� � ��

"� C������ � ��������������������$� D����� �������������

� ����������)��B))���

� �

���� ����� �

� � �

� � �

� ����� � �

���� �� �

� �

� �

'� /������������� ��������������� �6���� �������������� ��������������� ���������?

��� � �

� �

� �

� �

� ��� � � �

� ��� � � �

� ��� � � �

� ���� � � �

� � � �

� � � �

� � � �

� � � �

8�:

8�:

Page 42: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� �����������������

��� � � � �� �� � � �� �� � � �� �� � � �� �

� �

� �

� �

� �

� ��� � � � �

� ��� � � � �

� ��� � � � �

� ���� � � � �

� � � � �

� � � � �

� � � � �

� � � � �

���4���

Page 43: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������������ �

��� ������

(�������������������������������������������������������� ��� ������� ��������� ������� ��������� ������� ���������� �������������������������������������� ����� ��������� ���� ����� ��� ������ ������� �������� ������ ��� ����� ���������� ���������������������������� ����� �9���������

����� ������ ��������� ����� �������� ������������� ��� ������ ������ ���������� ����� �������������� �������� ���� ����� � ��� ���� ����)������������ ������ &������ ������ �������� �� ����� ������� ���� ���� ���� � ���� ������� ������ ����� ����� ��������������� �� ����� ������ ��������� B ���� ��� ��� ���� ���������������������������

D�����?

&����� ?����5��������

������������� ?���� ��������

���������� ����������� ����������� ����������� ����������� �

Page 44: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� �����������������

������C������)����������������)�6�������6���6������������������

��>�E��F������G9��������#�6�#����� ���H

����

5�>� E9I9���)�6�������6���6�H

�������������������������� ������������������ �������������������������5����� �������������������������

������������� ���������������������� �������������������������������������

�� ∈ ������9����������������

��∉ ������9� �������������������

����� �����������

���������������������������� �����������������������

D�����?��8�:������ --�

���������>�E���I����������� ����������������� �������������!4�H�

�������>�E!��"��%��*�������"���*���0H����� --� �>�.

��>�E������������������������� ��H������ -- �>�%

��>�E��EH��EEHH�H������ --� �>�"

����� ����������� ����������!������ �����

&������ ������� ������� ������� ������ ��������������� ������� ������ ���� ����� ��������� ������������ ���� � ���� ���� ������� ���� ����� ����� ��������������� ��������

Page 45: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������������ ��

5���������������������������������� �������

� > ���������)�6������������ > E9I9���)�6�����������H� > 8D��������)����#�����C���(����D���:

������5 > ������� ����������5 > 89I9� ����������H5 > E���!��"�������H

������� ������

����" ������������������������# ������

����������������5�������������������� ����������� ���� �������� ����������� ��������� ������� ��������

��������>� EF��#������F����F��#�)�����F(H5�>� EF��#�)�����F(����F����F��#��H

� � ��>�5

����������������5���������������������� �� ���� ��������� ������ ���� ��� ����� ���� ������ ������������������������� ��������������������5�

��������>�E��G9�����A������!"H5�>� E�������C�� ���H

� � �J5

Page 46: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� �����������������

&������������������� ��������5� ����������� ���������������������������������������������5�

������� > EF�"����F�"�����F�0%��F�0*H5 > EF�"����F�"�����F�0%��F�0*��F�0.��F�0.(G�

F��G��F�!444��F�K#H

� � �����

5��������������������������� ������ ��������

������� > EF�K#��A��9����9H5 > EF�"���� F�"����� F�0%�� F�0*�� F�0.�� F�0.(G�

F��G��F�!444��F�K#H� > E������� ������ ����H

� �

������ � �������� ������������� � �������� ������

⊄⊄

����$ �������������������

����$�����������������%&��'�#�

&������������������>�4����� ��������������������

D�����?� { }�∅

������� > ������� ��)�6������������ ���� ������������ ����

������ �������������

{ }� = ∅ =

Page 47: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������������ ��

����$���#��������#�

(������� ���� ������� ������� ���� ����� ��������� �������

������� > ��������������� ���� �)����� �� ����� ����� ���

������ ���������� ������� �������� > E������ ����H

����$�"���������#�����%(��)������#�

������ ������� ��� ������� �������� ����� ������������ ���� ���� ��� ������� �� ������� ���� �� ������������������������� ������������������

����������������������������������������������������� ������� � ����

D�����?��

������� > (���������� ����������������������������������

������)�� > EF��"���������F�K#�����H

����$�$�������������

������ �������������������������� ������ �������� ���������

&���������� ������ �� ������� ���������� �� ��������� ��������������� ����������������

5������� ������� ����� ���� �� ���� ������� �������

!���9�������� ������������

D�����?�!�

Page 48: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� �����������������

��������>�E���������� ���H

5�>� E������������� ����H

� �

� � � �� �

� � � � � � � ��

� � � � �

� �� ���� � ��� �� �

� �� ������� � ������ � �� ��� � �������������� �

���������� ��� � ��������� ��� �

� �

��� ���� �������

����� (����%*� ������������ ������

L� ����!�������������5�����������������������������������������������5��������������

D�����?

� �� �

∪+

��������>�E���������� ���H5�>� E������������� ����H��>�E���������� ������#��������H

� �

� �

� �

� � �������� �������������������������

� � �

� � ����������������������������� �������

� �

� �

� �

Page 49: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������������ ��

����� +���������%+��������������������

@�������� !�������������5������������������������������������ �����������������������5�

D�����?� � �∩

��������>� E���������� ������ ����������H5�>� E������� ������������������ ����H

� � 1��M-N��� -OPQ =∩

����"� ,����)��-��������%#����� �.��������������

(������������������������5���������������������������������� ���� ���������������� ������� ���������������������������5�

D�����?

��R�5

��������>�E(SA���������(SA���������H

5�>�E��(SA�����������B����H

� � � �� �� ���� �� �

����$ ����������������������

C������������ �� ��������������������������������������� �������������

����� ����� ���� ��������� �� ������� ������� ��������������������������������R���

Page 50: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� �����������������

D�����?�����′

������� > EF�"���� F�"����� F�0%�� F�0*�� F�0.�� F�0.(G�

F��G��F�!444��F�K#�����H� > EF�"����F�"�����F�0%��F�0*H

�� > EF�0.��F�0.(G��F��G��F�!444��F�K#�����H

����/ #'��������00������%�����#������

5���� ���������!�������������5���������������������������������������������������������������������5�������� ������������������������������������� �������

D�����?

�� ⊕

��������>�EF�"����F�"�����F�0%��F�0*H5�>�EF�0%��F�0*��F�0.��F�0.(G��F��G��F�!444H

� � �� ⊕ > EF�"���� F�"����� F�0.�� F�0.(G�� F��G�

F�!444H

��� ������� ���

�������������������������������������� ����� ���������������������������������������������� ������� ��������� ����� ������ ������ ���������� ������������� �����������

Page 51: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������������ ��

������

� �

��

� �

� �� �

� �

� ��� ��

� �� � ��

��� �������������������������

&����������� �� � �� ���� ������ ����� ��������� ������ ���� �����������������?

�� &����� @�������

� � �� � �

∪ =∩ =

!� &�������������)

( ) ( )( ) ( )� � � � � �

� � � � � �

∪ ∪ = ∪ ∪

∩ ∩ = ∩ ∩

Page 52: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� �����������������

"� &�������������)

� � � �� � � �

∪ = ∪∩ = ∩

$� &���������� ���

( ) ( ) ( )( ) ( ) ( )

� � � � � � �

� � � � � � �

∪ ∩ = ∪ ∩ ∪

∩ ∪ = ∩ ∪ ∩

%� &����� @�������

� ������������������� � �� � ��������������������

∪∅ = ∩ =∪ = ∩∅ = ∅

'� &����� @�������

( )��� �=

*� &����� C�������� �

� �

� � �������������������

� � ���������������� �

∪ = = ∅

∩ = ∅ ∅ =

.� &�����������

( )( )

� � �

� � �

� � � �

� � � �

∪ = ∩

∩ = ∪

0� &������������� 8� �����:?

������������

=∪∩=∩∪

������(��������

( )� � �∪ ∩

Page 53: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������������ �

� � �

( ) ( ) ( )( )

� � � � � �

� �

� �

∪ ∩ = ∩ ∪ ∩

= ∩ ∪= ∩=

��� ��������������������������

(����������������������������������������������������������������������� ���������������������� ������������������ �����������

5����������������������������� ������������������������� ����

��/��� *� �������������������

�����������������!���������������� ���������������� �� ����� �����?

� �� � �� � ��

� �

� � � � �

� � � � �

� � �� � �

� �

� �

� �

� �

� � � � � � � �� � � � ���

� � �� � � 8�:

� � � � � � � �� � � ��

� � � �� � 8!:

Page 54: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� �����������������

(� ��������8!:����8�:

� � � � � �� � � �

� �� � �

(������

� � � � � �� � � �

� �� � � 8":

��/�� *� ����������"��������

������������������"���������������� ���������������� �� ����� �����?

( ) ( )� � � � � � � ∪ ∪ = ∪ ∪ ��������)

(� ���������������8":������

� �� � � � � � � � �� � � �

� � � � �� � �

(� ���������������8":������ �

��

� �� � � � � � � � � � �� � � � � �

� � � � �� � � � � 8$:

&���������� ���� ?

� � � � � �� � � � � � � � �� � � � � �

&����� ����� ���� ��� ����� 8":� ������ �������� ����� ����

� �� � ��

� �������

� � � � � �

� � � �

� � � � � � �

� � � � � � � �

� � � � � � �

� �

� � �

� � �

� � � � �

� � � � �

� � � �

� � �

� � �

(� ��������������������� 8$:� ��������?

� � � � � � � � � � � � �� � � � � � � �

� ��� � � � � �� � � � � � � 8%:

Page 55: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������������ ��

����� ���

�� /������������� �������������� > E��� �� #���������� ���������� T��6����

#��(���#��L@�#�����H

5 >�E(SA�(�������(SA�������������B������(�#��5�#���L��(SA�� ���H

� >�E#&#���(#�������T���������H

� >�EF���6���A��9����9�����B(��B(U!�����H

G >�E��������������&������� ���H

T >�E���������� ����������������� ���H

!� �������� �������� ��� ������������� ��������������������� ������)�� ��� �������������� �������������� ����?

��>�EF�"����F�"�����F�0%��F�0*H

5�>�EF�0*��F�0.��F�0.(G��F��GH

��>�EF��G��F�!444��F�K#�����H

������?

�� ( )� � �∪ −

� ( )� � ��∩ ∪

�� ( )� � �⊕ −

�� ( )� � �− ⊕

�� ( ) ( )� � � � �∩ ∪ ∩

)� ( )� � ��− ∩

�� ���� ����

� �� ∪

�� �

� ∩

Page 56: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� �����������������

"� �����!44��������6��/@����������

%.!����������A��9'!*����������F���6�%$"������������9!!*����������A��9����F���6�"4*����������A��9������9!%4����������F���6�������9!!!�����������������������

5����������������������������������� ����������������� ��� ����7

5���������������������������A��9����������������������F���6�������97

$� ����"*��������������������������6�6��������� �� �������� ������������

!%����������#�����!.�����������VV!�����������������������

5�����������������������������7

%� &���������������������������������������������C��������� ���������

"!�����������������������!4����������������������������$%��������������������� ����%���������������������� ���*������������������������������4������������� �����������������%��������������������������

5����� �������������6�������������7

5����� �������������6����������� ����������������� ���� ������������7

Page 57: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������������ ��

5����� �������������6���������������������� ������������������������������������������������7

'� ������������������9������������ ��� �����������)��6����������������� �C����������������� ��� ������������!4��������6��!%W����������� ���� ��� ������� ����� ��������������� ������ ������ �������6�� ���� ��� �� ������������� ��������%�?�$������� ����� �������������6���� ������ 9� ���� ��7� 5����� ������ �������6�� �������� ��� �������7

*� ������������ 9� �� ������ �������������6�� �������� ��� ���������� ��)�6������������ ���#������������%?$?"�C����������������� ��� �?

� ����� ���� %4� �������6�X� �4W� ��� ������� ��� ��� �������#������ ���������X� !4W���� ������ ��� �������!4W������ ��� ��#������

� #������������������������ ��� ��������4�����5����� �������������6��������975����� �������������6����������� ��� ��#�������������������� ��� ��������������7

L�� ������������������Y

�.� �������� �� ������� �������6�� ����� �������� 5��������������6��������������������������������6�� ����� ������������ �� ������� �������6� ����� /����� @)��������� G� ������� �������6����� ����� ��� ������� ����������� �������� T��������������6������������������� �� ����������(����������L���������������6����� ��� �� ������� ��6��� ������ ������ ����� ���� (��������

Page 58: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� �����������������

D������� �������� ������� ������ ������ ����&������?

�� (����� �������6�� ����� ��� ���� ����� /����@)������������� ����������������������������

� &������������������� ��������������������������� ����� ����������������� �� �� �������� ��� �����������6�����������������������(���������

�� �������6�� ���� ����� ��� ������� ����������������� ������ ���� ����������������� �� ��������������������

�� (������������6�� �������� ���� ���� ������� ����� ����������� ������� ����� /����@)�������������������������� �� ��

0� ������� �44� �������6��� "!� ���� ������� �������������� !4� ���� ������� ��� T������� $%� ���������� ���5���������%������������ ���������������� 5�������� *� ���� ������� ��� ����������� ��T������� �4�� B��� ������� ��� T������ ��� 5�������� "4����������������� ������������������������ �������� ����� &����� ��������������6������������� �����

"� ��������� �� � &����� ������� �������6�� ���� ����� ����

���� �������������������� ��������� ���

�4� (�����!%��� ��� ��������� ������������� 8�:�����8�:������� 8F:�#�6��F���6���������� ��� �� ���� ������?��%�8�:���!�8�:�����8F:��%��8����F:��0�8�����:��$�8���F:��"�8����F:���������� �������?

�� &���� ��#�6��F���6 � &���� ����

Page 59: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������������ ��

�� &���� ��������� &���� �������F�������������� ������ &���� ���������������������� ��F�)� /���������������������������

���4���

Page 60: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� �����������������

Page 61: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������������� ! ��

/���� ������� )�ZZ�� �������� ����� ���� �����������8�� ������:���������� ������������ ���������������)�ZZ���������� ������ ����"�������������?

� #�����������������������0'%��0**� #����� ��)������� ��������0*.��0..� #�����)�ZZ�� ����������������������0.0

/���� ������� )�ZZ�� ����������� ����� #�)� A��)�� �������������������0'%����������������� ��������������� ��������������������

��� ���� ������������

5� ������������������������������������������������� �������������4��)����������������������)�ZZ��������������������4����������

������� > &������ ������� ������� ���� ����� �������

�����������������

���������� ����������������� ����������������� ����������������� ����������������� �������

Page 62: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� �����������������

������������������8��������:�����������������

��>�EA��9����9��F���6������B���B(!H

������� A��9����9�� F���6��� ���B��� B�!� ������������������������������ ������������� ������������������ ������� ���� ������� ������� ����� ����������������4�

������������������������������� ����������������������������� �)�������������������� ������ ������ ���������������������������������������������������������������� �������������������������������������� �������������������������)�ZZ������������������������?

� > E[A��9�4�*\��[��9�4�%\�[�F���6��4�0\�[���B��4�!\��[�B(!�4�$\H

����

� > 4�*UA��9�V�4�%U��9�V�4�0UF���6��V�4�!U���B��V4�$UB(!

������� 6���6�� ������ ����� �������� ����� ���������������������������������������������4�0���������A��94�*���� ��������� ������� �������������� ���������� �������������������������B�����������������4�!�D�����������������������)�ZZ�?

� �� � � ����

C������� �������������������)�ZZ�������������������� 4� ������� �����������������������������������)�ZZ����������������� �����)�����

������

⎪⎭

⎪⎬⎫

⎪⎩

⎪⎨⎧

><≤≤≤≤

=]-=--��-̂-=-�N��--_

]-=---̀�N��-=-a]-̀=---̂�N��--̂a=

2=3Q

Page 63: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������������� ! �

L�� ������)����������������89:����� ���������?

����

� � !

����

����

����������T�����������������89:���� � �89:

�������� ������������

"���� ���������

C��������������� )�ZZ����������� � � ����� )�������������?

( ) ( )� � � � �= −

A�������� ��"��

������

�������������������

���� ����

�������������������

≤≤+−=−−=

−=

≤≤−=

Page 64: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� �����������������

�����������������������������������)��������������

���� �������89:�>�.�9�

"���� *� ����%(�������������122'

L� �����������)�ZZ�������5���������������)�ZZ�� ��∪ ������)��������������

( )( ) ( ) ( )� � � ��� � � �� �∪ = ⎡ ⎤⎣ ⎦����������� � "� �

���������������89:� )���������������������)�ZZ���� ����� 8)�����:?

�89: > 4U%�*%�V�4U'�V�4�!%U'�!%�V�4�%U'�%�V�4�*%U'�*%�V��U*�V4�*%U*�!%�V�4�%U*�%�V�4�!%U*�*%�V�4U.�V�4U.�!%

��������������������?

���� > �U%�*%�V��U'�V�4�*%U'�!%�V�4�%U'�%�V�4�!%U'�*%�V�4�*�V4�!%U*�*%�V�4�%U*�%�V�4�*%U*�*%�V��U.�!%

� �

��������������������������������������������������������������������������������������������� � ����

++++++

++++=∪

Page 65: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������������� �� ��

������� ( )( )� � �∪ ������

( )( )� � �∪

� � � �

�������� ����������������� ( )( )� � �∪

����� ������� �� ����������������

��������������� ����� �������������������� ����� ����������� ����������������� �� ∩

���� �!��"#$%&���� "� =∩

�� ����� �� � �∈

�������'��������()*� � ������������������� ����� ������������� (��+����*�

�()* � ,-,./,01-201.3,-2.3,01.,-2.,01./,-2./,04-/01./,-/.3,01.,-/.,01.3,-/./,01.501.5.3,

���������������������

���� � 4-,6/,04-201./,-2.3,01.,-2.,01.3,-2./,01-/01.3,-/./,01.,-/.,01./,-/./,04-504-5.3,

Page 66: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ������������������

������� ∩ � 1-,./,01-201.3,-2.3,01.,-2.,01.3,-2./,01./01.3,-/.3,01.,-/.3,01.3,-/./,01.501-5.3,

������� ( )( )� � �∩ ������

( )( )� � �∩

��

���

�������� ����������������� ( )( )� � �∩

����� � ���������������������

����������� � ����� ��� �� ��� ���� � ���� ��������� ����������� ��7������� ����������� ����7����������������� ����� ���������� �6�8������������������ ����� ���� ���� ����� ��� ���� � ���� ����� �������� ����7��������������������������� ���������������������������

9������

��������� ∞≥∈=∞

Page 67: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������������� �� ��

�������8��� ���� � ���� ��������� ������� � �� �:� ��� ��� (;*

������������������1� �������4���<���������7�����������������=������ �� 352(41*.>52(31*.� ?52(>1*.������ ��4(,1*.������ �3(21*.������ ��>(/1*.������ ��?(51*����� =���3� �(411*.� � ������ �� �;���<������������������=���������� ����������������� ���������� � ������������������ ���

A (x) = 0/10 + 0,1/20 + 0,2/30 + 0,3/50 + 0,5/60 + 0,7/70 + 0,8/80 + 1/100

10 20 30 40 50 60 70 80 90 100

10

9

8

7

6

5

4

3

2

1

0

Page 68: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ������������������

��

������

������������

������������������

����������������������

��������������������������

��������������������������������

�������������������������������������� ����

���

���

���

���

���

���

=+=

++=+++=

++++=+++++=

++++++==

������������<��

�����������������

���

+==

������� ��� =∪

��������� 7 ��

��������� ��� =∪

���� ����� ����� ������������������� ���

���"""""""" �������������������� =∪∪∪∪∪∪∪

������������

� �= ∪ �

� [ ]���∈

Page 69: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������������� �� ��

������������������������� ����������������

������

������������

������������������

����������������������

��������������������������

��������������������������������

�������������������������������������� ����

���

���

���

���

���

���

=+=

++=+++=

++++=+++++=

++++++==

���������

�������

���

���

=∩=∩

������������������� ���

��� ��������������������� ��������� =∩∩∩∩∩∩∩

����� � ������� ������!������������

���� � ��� ��� ���� � ���� ��������� �� ����� ������������=������;� �������� ���� ����� �������� ����� ������;���������7���������������������������������16

9������

���������� ��� >∈=

��������()* � 1-,./,01-201.3,-2.3,01.,-2.,01./,-2./,04-/

01./,-/.3,01.,-/.,01.3,-/./,01-5@ ���(�*���A263,.�26,.�26/,.�/.�/63,.�/6,.�/6/,B

Page 70: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ������������������

������������ �����������������

�������� ����� ����������������������������������=�����;��������� ���� ����� �������� ����� ������;� ����� ����7����������������������������4

9������

( ) ( ){ }���� � � � � � = ∈ =

��������()* � 1-,./,�0�1-2�01.3,-2.3,01.,-2.,01./,-2./,04-/0

1./,-/.3,01.,-/.,01.3,-/./,01-501-5.3,C����(�*���A/B

����������������������������������

D������ ����� ��� ���� � ���������������� ����� ����� ���+������������7������������������ ����� ���������� �6

9������

�(�*

�����(�*���4.��������� ����� ������������������������(�*�E�4.��������� ����� ��������������� ������6

�������8��� ����� ������������������������=������;��������+

������������ ������������������������������ ��

( )

�� ������ � � �� �����������

�� ����������� �� � � �������������� ��

�� �������� ��

<⎧ ⎫⎪ ⎪− ≤ ≤⎪ ⎪⎪ ⎪= ≤ ≤⎨ ⎬⎪ ⎪− + ≤ ≤⎪ ⎪

>⎪ ⎪⎩ ⎭

Page 71: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������������� �� ��

���������� � ����� ������������ ������ �.� ��� �������� ����@ ��(�*�����(�*

������

����" �#������#���

��

� �� �

������

��

�������

����

( ) ( ){ }( ) ( ){ }

( )

���� � � � � � �

�� � � � � � � � �

� �

= ∈ < <

= ∈ ≤ ≤

=

@=���� =���������� ����� ��� ����� ���� � ������ �����������������=������;������7 ������ ������7������������+���������;��������� ����� �����

9������

( )� �

� � �∈

= ∑

Page 72: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ������������������

�������

������

������������

������������������

����������������������

��������������������������

��������������������������������

�������������������������������������� ����

���

���

���

���

���

���

=+=

++=+++=

++++=+++++=

++++++==

��F!GHI!JK!JL!JG!JM!JH!JNN"��� =++++++=

��� ��������������������������

8��� ����� ������������������������������� ����� ���

��(�����*�7�������������7���

�()*����()*

�� ��������� � �∈

8��� ���� � ���� �� ���������� ��� ���� ������� ������� ����� �����.�7�������������7���

� � � �� � � ��

�� ��������� � �∈

�������8��� ���� � ������ (����������� �������������� �����*.

��� ���� � ���� �� (����������� �������������� ������*.

Page 73: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������������� �� ��

��� ����� ����C�(������������������������������*���������+���������������������������������������<�6

���

���

���

���

���

���

���

���

���

� � � � � � �

��

������

'��������������������=������;�����

� �

� �� � � �

� � ! " # $ % & ''�(�)

� �* �+� �+� * � � �

'������������� ����������������������� ����� �����()*.��()*.����C()*.�������������� ��

Page 74: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ������������������

,�-././01- �� ��� ���

�����2 � � ������3, ��� � ������3 ��� ��� �����2� ���� ��� ��������� � ��� ��������� � � ��������� � � �

O����

��� ≠≠

������� ����7��� �������������� ������ ����� �� �� ������������)

��� ���P ⊂

�����������7��������������� ( ) ( )� � � �≤ � �� ����� ��������)6

��� ���

46 �6 �������������� ����� ���������� ����������+�������������������������

( )

� �� � � ��������� � � � �

� �

����� � ������

��������� � ��

⎧ ⎫−⎛ ⎞− − ≤ ≤ +⎪ ⎪⎜ ⎟

⎪ ⎪⎝ ⎠= ⎨ ⎬< −⎪ ⎪

⎪ ⎪> +⎩ ⎭

���������4Q

�6 D ���������� ����� �����=6 ������������ ���������� ����� ���� ��6 ��������������� ���������� ����� ����� ��

���� � ��

Page 75: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������������� �� ��

36 �6 ���7����� �������� ������ 4�� ���� � ����� ���������+����

� �

� �

� �

� �� ������ �

� � ����� � �

� � �

� ������ � ��� ������ � ���

�� �� �� ��� �� �� �

� � ��� �� �

� ��� � � �

��������1.,Q

�6 ���7����� �������� 4�=6 ���7����� �������� 4=�6 ���7����� �������� 4��6 D ������ ( )���� � �∪ .� ( )���� � �∪ .����� ( )� � �∪

�6 D �7 ������<�� ( )� � �∩ � ������������ ��������������1.,����� ( )� � �∪ ���� � ����

>6 '���������� ���� � �������������������������� ��� ����� �����������

� �� &

! )�()�'" � !�� � $

� '''''''' )�()�'� "'4��'� !�

�� �� � �� �

� � �� � � �

� �� 5

! )�()�'$ � !"6 � $

� '''''''' )�()�'� $'4��'� !"

�� �� � �� �

� � �� � � �

�6 ������������� ����� ������������6 D ��������� ����� �����������=6 ���������������������� ����� ���� � ����� ��6 ������������ ��������� ����� ���� � ���∪ � ���∩

� ���∪ ���� � �∩�6 D ������� �������� � ���� ���� ���� �∪ ∩ ∪ ∩

Page 76: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ������������������

�6 D ������=��������� � ���� ���� ���� �∪ ∩ ∪ ∩�6 D ���������������� � ���� ���� ���� �� � � �

?6 ���7�������������������>�����

� �� $

! )�()�'" � &� � "

� '''''''' )�()�'� "'4��'� &

�� �� � �� �

� � �� � � �

� �

� �� ����� � �� �� ������ �

� �� �� �� ����� � �

� ������ ���� �

� �� �� �� �� �

� � �� � �� �

� � ��

,6 8�� ����=����=���������� �� ����������+����������+� ����� ���������<�

(�* �����1.?-R�0�1.3-<�0�1.,-)�0�1.?-��0�4-�

(�* ������

�+

.� �� ��)�∈�;.�;���A�1.4.666.41�B

(=* C���4�+���.� �� ��)�∈ ;.�.�;���A4.666.41�B

26 S ���������.�������C���������������� ����������������

�����������

�+

�� ������ −= ��������� �M��HJHH

−+

���� ;� ��� ���� �������� T��� ������� �����R�;���U�1.�41�V

�* ���������������� �������������������()*.���()*����C�()*

�* ���������������� �������������������()*.���()*����C�()*

Page 77: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������������� �� ��

��� ����� � ������ ���� �����������������6

=* @�������������(�*� �� ��� P NP!N"! " ∪∪∪�* @�������������(�*� �� �� P NP!N"! " ∩∩∩�* @�������������(�*� �� �� W N"!P " ∩∩∪∪

/6 8��� ����S �����.�������C��������;���U1.51V��������+�������� ����������������

���7����������������2

+��1��+

⎪⎭

⎪⎬⎫

⎪⎩

⎪⎨⎧

>≤≤−

<=

GLN�NX%YX�NJNNNNNNNNNNGL�NNNMJX%YX�NHLZ��GL�

MJ�X%YX�NHNNNNNNNNNN���"

⎪⎪⎭

⎪⎪⎬

⎪⎪⎩

⎪⎪⎨

<<≤≤−≤≤−

><

=

������������������������� ����������������� ��������� ��������� ��

� ��������� ������� ����������

����

⎪⎭

⎪⎬⎫

⎪⎩

⎪⎨⎧

>≤≤−

<=

FJN�NX%YX�NHNNNNNNNNNNFJ�NNN[LX%YX�NHLZ�[L��

[L�X%YX�NJNNNNNNNNNN���"

Page 78: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ������������������

Page 79: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ���� ��� ��

�� ���������

������ \]������ � ���^� �������������� ������ �� ������+� ������������ �������������������������6�_������������������� ��.�������� ����������������������� �� ��������������.�������.� ����������� ����� � ����� ������� =����������������� ��������������� ����� ����������6�_������������������� ��������.� ���������� �������� ������ ������� ����������������������������������������R���������1�����46

_��������������� ��.�������� ���������� �� �<������������ ����� ������ ��� ���� � ���.� ������� ����� ����������.� �������� ����������� ����� ������������������ �������� ���� � ������� ������ �� ����� � �������������� ���+���� ��������������.� �������������� ��� � ���6� _���� � ������������������������������������������� ����� ��� �� �� ������������ ��� � ���.� ������� �������� �� ������������ � �� � � ����� ������� ����7��� �������������� ���� � ���� ���� ����7��� ���������� � ���� ���������68 � ����� ���� 7 ��� �������� �� ���������������� ������������������������ ����������� ���.���������` ������.�` ��+������������������������ � ���6

��������������������������������������������������

Page 80: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ������������������

� � ���������������� ��������������������

@����������� ���� ����� ���� �.� ��� �� ���������� ������������������������� ����� 3������ �������������� � �� �-�����-4���������-���-16

]�����������������������������������������������+������� ����� ������ ������ ������������������� ����� ��������������1�����4.���� ������������1�����a�������a�����4.�����+���������� �������� ������������� �������������������������6'��� ������� ���������������� ������ ���� ����� �� �����+�������������������������� �������������������������������+�������������������������� ������������.���������� \D�������� ���7���� ��������� ����<��� �������� ��� �������� @ �����+8����6^��������������������������� �������������a��������� �a����6

����� � � � ���� ��� ������������� ���������� ����������������������������>�������������������� �

�����-�� �-4@��-S���-1

@���������������� ���������������a

1 7 ∧ ∨ → ↔ ∧ ∨ → ↔ ∧ ∨ → ↔ ∧ ∨ → ↔ ∧ ∨ → ↔

� � � � � � � � � � � � � � � � � � � � � �� 8 � 8 � 8 8 8 8 8 � 8 � 8 � 8 � � � 8 � 8� � � � � � � � � � � � � � � � � � � � � �8 � � 8 8 8 8 8 8 8 � 8 8 8 � 8 � � � 8 8 88 8 8 8 � � 8 8 8 8 8 8 8 8 8 8 � � 8 8 � �8 � 8 � � 8 8 8 8 8 8 � � 8 8 � � 8 8 � � 8� � � � � � � � � � � � � � � � � � � � � �� 8 8 � 8 8 8 8 8 8 8 � 8 8 8 � 8 8 8 � 8 8� � � � � � � � � � � � � � � � � � � � � �

��������� � ���� ������ ������� ���������

Page 81: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ���� ��� ��

_���������������������������������a.���� �= ����,����������������������� ������������������ �] �����<�=�.��=R��.������.� 8������.� ���� T��=����=.� �������� ����������6

�������� ������ � ����] �����<�=��

b�� �������������������-���������������������������������

� � �= −

]������ � ���� �������������������������������������������� ��� ����� =��� ���� ���R�=�� ���� =��� ���� �����������.������ �� � 7 ��� �������� �� ��������� ���� ���� �������� ���� ����������� ��� � ���� ����� ������ ����� ������7�<��� ��������� ��� ������� �������� �����S ���� �������=�@�����.�S ����C �������.�S ����_�������.�S ����]���������+��������.� S ���� �������� D�������������� ������� �������������6

����� �� =����������S ���� �������=��@������

@�� ����� ��������������C�b����� ����� ����+��������������.� ������������������� ���� �����4�� ��� ��������������� ����� ��

c �����������������������=�����4111� �����������.������=����=���� 311� �����������6

����������������

���������

�������

������������������������

���������������������

→∧→=↔∨=∧

→→=∨−−=↔

−+=→−+=∧

=∨−=

Page 82: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ������������������

cc ��������������� ������������������=�����431� �����������.�����=�����=�����31� �����������6

ccc���� ���������� ��4?11� �����������.������ ��?11� ����������

�������C�b��� ��������������7 ��������������511� ������������������ ��� ���������� 21� ���.� ���� ������� ���� ��������� ����� ����� ����

O���������������� � ��������������������������������� �������������� ����6

�� �S ����� �����������

����������������� ����4111� �����������.�������������7��������������4���������������������(4111.4*6

���������������� �� 311� ���� ���� ���.��������� ����7��������������1���������������������(311.1*6

S ������������������ ���� �� �����������������������

:�+�:���������;�+�;�

:��+�:���������;��+�;�

:�+�1�������;�+�3114�+�1�������4111�+�311:������������;�+�311�����������������511������������������������������������������ � �.�� ����������������������

:���4�+�:���4�+�)�+�311������+�;�0�4111���������������������������511 ����������������511

_������=����������������������=����� ������������������ ��� �� �����������������6

Page 83: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ���� ��� ��

������ ��(431.4*���������� ��(31.1*

������

��������

����

−=

−−=

−−

������������������������� ���������������� � � �.� � ������������������

�������

������

����+−=−−=−=

_������=��������������� ������������������ ���� �� ������ �+����������������=����

������ ��(4?11.4*���������� ��(?11.1*

��������

�����������

����

−=

−−=

−−

������������� ������������������ ����� � �.��������� ����������������

���������

��������

����+−=−−=−=

7����������������������511� ���������������������� ��������21� ���.������� ����� �������� ����������� �������������� ��������� ������ ��� ������� ������ �����������

O���������������� � ��

������������ �� �����������

� ==+−=

Page 84: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ������������������

����������������������

������������������� ��

���� ==−=

�������������� ����������������������.��������������S ����������� �������������=��������� �����(�163,.�16?1�*���163,

'�������� ���� ���� �����

������������ ����

��

=+−=

+−=

O���.�C�b�������� �������� ����44,1� ���6

�� ��� ���

46 � ��� ����� ���������� �� ��� �� ∨≡∧ � ������� ��������������] �����<�=�.���=R��.������.�8������.����T��=����=6

36 9����������� ��������� �� �� �� ∧∧→ � ������� ��������������] �����<��=.���=R��.������.�����8������6

>6 D��� ���� ����� �������������������� ��� ��<�����������������������������������������������6�6 � ���6 � ��=6 � �� � �� �

�6 � �� � �� �

?6 D �7 �������<��6 � � �� � �7�������������7���� � ���6 � � �� � �7�������������7���� 9 ��

Page 85: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ���� ��� ��

����� � �� �� ������ ����� ���������� ����� ������������

,6 @�������R����������� ������������������������������������������� �������������6

26 ���7����� �������� =����� � ���� �������=�� ��� ����(������/1*6�� ���������� ����� � �� ���������������� � �� ��� ���������� � ����������(�*6 O���������������� � �����������������������������

���� ���� ����������� ����(�*6 O����������������������������������������������

���� ���� ���������������(=*6 O�����������������������������������������������

���� ���� ���������������

/6 @�� �� ��� ������ ���������� C�b��������� �������7 ����4�� ������������������������ ������������� ��������� ���=����� ,11� ���-���� ��������=�� 411� ���-���6����������� ���������� ���=����� 21� ���-���� ��������=�� 41� ���-���6���� ���� ������������=����� /11� ���-���� ���� �����=�311� ���-���6D��� ����������� ����C�b�������� �������� ����7������� ����������� ��������� ?11� ���� ���� ������������� ��������������>1� ����C�b.���������������� �������� ������ ������ � ����������������<���6 O���������������� � ����������������������������

���� ���� ���������� ����6�6 O���������������� � �����������������������������

���� ���� ����������� ����6=6 O����������������������������������������������

���� ���� ���������������6

Page 86: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ������������������

�6 O���� ����������� ����� ���� ����������� ���������������� ���� ���������������6

�6 8�� ������� ���� ����� +� ����� ��������� ����� ��� ?� �� ������� ���� ������6

C�������� � �������+���������������

Z = ( 1Z1 + 2Z2 + 3Z3 +� 4Z4 ) / ( 1 + 2 + 3 + 4)

:�����:

Page 87: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

!�"����#"���� ��

���������� ��

T����������� (��� � ��������*� �������������� ������������ ���������� ��� ��������� ������� �����+����������� 3��� �������� ��������� � ����������� 6

�������_ �� ������ ���� �T���� ����'�������������� � ����

�������� ����� �Q� \T���� ����� ������ ���� ���'�����^� 7����������������� � ����� �����6�������� ������ 7����� �����.������� ���� 3� ����� ���������� ������ ���� � �����Q� \���� ��������������� ���������^6

����� ������ ��������������� ��� �� ������ ��� ���������� ������ ����� ���������� =��������� ������� � �� � )��<�����R�������)������ �� �����<�����R��������6�'������R�������)����������������������������� �����R�� ���� � �U)�.�)�V�����U��.���V���� ������������ ����

;���A)4.)3B

:���A�4.�3B

������������ ������������ ������������ ������������ ������������

Page 88: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ������������������

��;�)�:���A()�.���*.�()�.���*.�()�.���*.�()�.���*B:�)�;���A(��.�)�*.�(��.�)�*.�(��.�)�*.�(��.�)�*B;�)�;���A()�.�)�*.�()�.�)�*.�()�.�)�*.�()�.�)�*B:�)�:���A(��.���*.�(��.���*.�(��.���*.�(��.���*B

� ;� ;� ;

<�

<�

<

'���� ������T�������� �����+�������������� ����;������� ����:������

� � �⊆ ×

��������+��������� �����������T��������������� �����.������� � ���� 3���� ���� ����� �������� ����� ������T.����������� �������������� �� ������ ������6

�������'������� ����� ������������ ��� �� ������ ;��� :� ������

������� T�.� ����� �� = >⊂ × � ������ ����� ���������� ����

���������� =��������� �������� ����� ��

Page 89: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

!�"����#"���� ��

T�������������������������� �������������� �������������������6�_����� � �����������������������������6

�� ����������� ���

����$ � ����%������

T������������������������� ������������������.��������=����� �����6

T���A('�=������.������<�*.�(��'.�1�-3*.�('�=�����.�'�=�@*B

[ ] [ ]� � � �� �� � ��×

� ;� ;� ;

<�

<�

<

�� � � �=

31?@�

��A�

/-

3/?�� B�3 31?

Page 90: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ������������������

D����� ������ ����� ������� ��� ��������7������� ��<���������� ������ �� ������ ������������6

����� � ����&����

T����� ������ �������������� �� ��� ��������.� ���� ������������ 4� ������� ���� ������ ������� 3� ����������������� � �.� ��� ��� ������� ������ ���� ������ ������� 3� �������������� ��� � �6

3/?�� B�3 31?

31?@� � � �@�� � � �/- � � �

3/?��

B�3

31?

31?@�

/-

@��

����� � � �

��������� ����� �������� R�� �� ������ �����������+ � ��������������� �� ���� ���������������������� �����������.���������=�����

Page 91: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

!�"����#"���� ��

_���� ��� �� �����.� ��� � �������� ����� ��� ������������������������������������������ ������������ ������ �6�T����� ������� ����� ������ ������� ������������������������� ������������������� � ������������� ����������� � �������� ����� ��� ���� ��� �6� T����� ������� ����� �� �������������������

� � �⊆ × ������� �� � �→

�������

3/?��A�C��D�?�E

3/?��A�C����.

3A�,�F���,�/-�

@��-�@CC/?�

2/1

G/H�

/-.�FA

I/-��

����� '��(�) ��(

��������������� ������ ��������� ����������� ����� �� �������� �� =� ���������� ���+�� ����������������� ��

�6 @����������������� ����;�����������������������������6 ������ ������� ������ ����������������������� ������

������ ������� ����������� ���.� 7���� ��������+������������������� ���������� �� ������ ������������6

Page 92: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ������������������

��������� ���������� �� ����� ������������������� ���������� �� �����������

�� � �������������� �� ����� �����������������6

1�

1�

1�

1�

1�

1�

��� ��������� ����� ����������

@�� ������������������ ����7 ����������������������������� �����.� ��� ������������������������ �������� ���������� ���� � �������� ������� �������� ����� ��� ���.�������� ��R����� ������ �������������� �����

����$ �* �� �+ #����+��!

��R�����������T��������������������� ������T.� ��R���������� T.� �������������� ���������� ���� � � ���� �������� ����� ������������������������������.�7���

O���� �� � ��→ ������� �� ��

������������������T��������������T���������.�����

� ��

�� ��

�� ����� ���������������T6

Page 93: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

!�"����#"���� ��

����� %���������+ #��

����������������������������������������������3�� �������������������=�=��-��� ��������������������� ���������������������� 6������� ��� ���������������������������������������������d�����������������������

����� ������ �

→→

��������:�������� ��������������:����d6

T����������d���� � � .�����������������������������

����� �→

_������ � ����� �� � 7���� ���� ����� 7���� �������� �� ������� ����:����� ���������������������4��������� ���������d6

�������

��

��

��

��

��

��

J�

J�

J�

J�

K�

K�

K�

K�

�, L

@����+����������������T����

�6 ���������(�� � �d*� � �T����� � �(d� � �T*

�6 D�������� �����

�� � �d�≠�d� � ��=6 (�� � �d*�����d�� � ����

Page 94: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ������������������

�� ����� ������������ ���������������� ���

��R���� �����.� ���������� ������ ���� ��������� ���������������7�����������������������6

����$ + #���,��*#

@�� �� ������ ����������������� ���R������������� ������� �������.� �������.���� ���������6

@�� �������������������������7�������������7���� ( )���� �∈

�� �����������������6

@�� ����������������� �������� 7������������� 7���� �� ���������������������������� ����;����������().��*������������������.������(�.�)*�7 ����������������6���� �7����( )���� �∈

����� ( )���� �∈ 6

@�� ���������������������������7�������������7���� �� �>� �������� ).�.�� �������� ����;Q� ( )���� �∈ .� ( )��� �∈ �����( )��� �∈ 6

�������'������� �����������<�.� ����� .������ � ��.� � �

���������� �������� ��� ��<�6

����� ���C�����T�������R���

M1H1 M/E1/ 31�1�0�E/1 NH��

E/ � 31�2/A ����-/ � 3���M�H ���/?1 � O1E0�E�A ��21-/ O1E0�E�A ��DP1 O1E0�E�A ���1-/ �/A/01 ��G1E/ � E/- ��Q1-/ � 31�2/A ��B-1 � 31�2/A ��R�-� � �/A/01 ��

� �∈

Page 95: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

!�"����#"���� ��

������� � ��������������+�����������<����������.�������� ����������<��������������������������������

;���A�.��.�C.�_.�.�S.��.�8.��.�OB

@������������� � ��� ��� �� ������T������;����;�����������������������<�

���� →T�� A(�.��*.�(�.��*.�(�.��*.�(�.�O*.�(�.��*.�(�.�C*.�(�.�8*.�(C.��*.

(C.�C*.�(C.�8*.�(_.�_*.(_.�*.�(_.�S*.�(.�_*.�(.�*.�(.�S*.(S.�_*.�(S.�*.�(S.�S*.�(�.��*.�(�.��*.�(�.�O*.�(��.��*.�(8.��*.(8.�C*.�(8.�8*.�(�.��*.�(�.��*.�(�.��*.�(�.�O*.�(O.��*.�(O.��*.�(O.��*.(O.�O*B

���������� ���� → ������������������������ ���������

� � � 2 D � G Q B R � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �2 � � � � � � � � � �D � � � � � � � � � �� � � � � � � � � � �G � � � � � � � � � �Q � � � � � � � � � �B � � � � � � � � � �R � � � � � � � � � �

��������T ��������������(�.�*.(�.�*.666.� (O.O*� �������� �����T ����������������(�.��*.�(�.��*.�666���� ���������������+

����������������TT �����������������(�.�*.�(�.O*�����(�.O*���������T

O���� ����� �→ � ������������ ����� ������<�� ����� ��������R���6

Page 96: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ������������������

�����������������R����������������������6

B

G R

M/E1/�� M/E1/��

� �

Q

M/E1/�

2

D �

��

����� ����� ��� ����� ������� ������������� ����� �������������������� �������� (�������*� ���� ������ ���� � ������������ ������� ���.� ����� �������� ������� ������ ���� � ������ ����� ���� ����+����6� T����� ���R���� ����� ����������������������������� ������������ �� �` �R���� =�����6

�������� ����� ��� ���� ������� ����� � �� � ��� ������������ ������������R����.������������� ����� ���� ���������6���������������` �R����=�������������������

Page 97: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

!�"����#"���� ��

@���� ����� ��� ���� ������� ����� ��� ���� ���������� �→ ��������������

@���� ����� ��� ���� ������� ����� ��� ���� ���������� �→ �������������C

@���� ����� ��� ���� ������� ����� ��� ���� ���������� �→ ��������������

����� + #���%�����- #

@�� �������������������������������������������� ��������������������������.���������������� �����������6�_����D���,64���������������� �������������������������������� ��

Q � �

B

D 2 � R G

0� 0�

0�

0�0� 0�

_����=������������������������������������<�������������� ���������.� ���� �

� ��.�8������������ 8������������� C�=����������������� �������� ��������O���

Page 98: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ������������������

� S��������O���� _��������R�

����� ��� �������##��.�� � �� �!

@�� ���������������T��������� ������������@�������+���������.� 7���� ������T� ������ �� ���������� �������.� ��������������� ���������6

@�� ������������������������������������� 7������������7���� �� ��)������������������ ����;.�����( )���� �∈ ������ ����� �������)����6

�������� �������� ���� ������� ����������� ������� \���+�� �^� ��� � \���� �^� �������

��E�� .�������� �������� .������� �������� �����e�� .������� �������� .������� ������� �����--�� .�������������������������������������

�������� �������� ���� ����������� ���������������������+�����8���� �������� =���������<�6

'��������������T������ � ������������� ��������A4.�3.>.�?.�,.�2B����������������������

������ ����!

�����T� ����� ��� �� ����� � ������� ������� ����� ��������������������������������8����������������� ��

" #

$ %&

Page 99: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

!�"����#"���� ��

' ����� �� ��(������� � ��� � ����� ���� ��� �) �

4�E�? .�4������ ��?4���3 .�4����� �������� ��33�--�> .��3���������������������������������>?�e�4 .��?����� ��43�����4 .��3����� ������� ��4

_���������� ��������� �����+������������������� ��������

� � ���������( �*������������������ ��� �� ������ ��� ���� ������� ��� �������������������������=������������������.���������������������������� ������������� ����������������������������� ���������������������

� ������ � ��� ������ ( �*��� � ���� ���� ������ ���������=����������������� ������� ����������������������� ���� ��� ���� �� ��� ���� ������� ����� ����� =�������������� �����=����

� ������������(�*�����������<������ ��� �� ��������� ������� ��<����� ���������� ����� ���������� =���� ������ ��<�����.� ������������� ������ ����� ��� ���� ������� �� � ���������������������������� ����������������<�����6

� ��������� ������ ������ (��*��� ����� ���� ������ ��<���������6�����������������<����� ����������������������� ���� �������� ����� ��������������������� =�����������<�������������6

Page 100: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ������������������

�������'���������� ��������A�.��.�=.��.��.��.��B������������ � �

��������8���������<�6

*

� �

� �

* �

� �

��������� ����� ���������� ���� ��������A=.��.��B

�� �������������������� ��(�*����.��.�=6���=������� �������

�������������=�������������������6���=������� ��������������������������=����� ������� ������������

� ��������<����������� �� (�*��� �.���� ������������<���������������������������� ���.��������������������������������

� ������ ����� �����=�� ������������ =� ������� =� ���� ������� ����������(=��������������������*

� ��������<�����������������������(�*����

��������������������������� �����������4�(������� ����*

�������'���������� ��������A�.��.�=.��.��.��.��B����������������

��������8���

Page 101: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������������ �

� ���� ��� � ���

� �� �� ��

� �� �� ��

� �� �� ��

� �� � �� �� ��

��������������� ��������������

������ ���������� �����������

����� ������ ���� ������ ������� ����� ������ ��������� �� ����� ���������� �������� ���������������������������� ������!�"��������������� �����������������������������#���������������������������������$�����������������������!

�������{ }� � �

� � �� ��= ����{ } { } { } { } { } { } { }{ }�

� � � � � � � � � � � �� � � � � � � � � �� � � �� � � �� � � �� ��= ∅

��%��%�����������%��&���

'��� ��%������� ���� ���(�� ������ #� ������ ����� ������������������������������������!

� ������%���)�����)�����������φ������%���)�����)������������)���)��

� ������%���)���)�����)������������)��������%���)���)�����)������������)���)��

Page 102: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ���������������

����

�! *��������������+��� ���� #�� ,�� ���� %����� ���������������� � � ��� �-���������������%����$%��������(��������� ����� %�������� ���%�� �%������ ����������%!

�� ( ){ }�� ���� � �= <

�� ( ){ }�� ���� � �= ≤

�� ( ){ }�� ���� � �= =

�� ( ){ }�� ���� �� �= =

�� ( ){ }�� ���� � � = = −

�� ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }�� ���� � ���� � ���� � ���� � ��� � �� � ��� � ��=

�� ( ){ }�� ���� � � ������� �= < >

�������������

�������������������������������������������������

=

� ( ){ }�� ���� � � ������� � ������ �= = = − − =

.� ( ) ( ) ( ) ( ){ }��� ���� � ��� � ��� � ��=

#! -��������/�����%�����$�����%�������������%��!,! 0�%���� ������� %����� �� ��(��� ���������$

�����%���������������%���������%�������#

��� �

� �� �� �

� �� ���

���

�� �−� �

� �� ��

��� �

� �� .�� �

� ����

�� �−� ��

� �� ��

��� �

� �� ��� �

� ����

� �� �� � �

� �� �−�

��� �

� �� ��� ��

� ��

Page 103: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������������ ��

1! *��������������+�������#��2��3����%��%����������$�%��&���

� �

� �

� �

�� -�����������$�����4��≥, 55��2�#

��2�6

3�2�6

7�2�1

7�2�6

�� �������� ������$������� ������ +� ����������� ����1��6��7���0����#��,��7������"����1��6��8�!-������������$��������� ����� ���� ���� ���� ��%������� ��0�����"!

� �� ������ ����������� �� ���� ��� ������ ��� ����� �� � �!�����!����"

� �

��

���������������������+������ �����#�,�1��

Page 104: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ���������������

-�������9

����������������������%�

7! "�%� -����� 6!�� ��������� ������� � � � �� � ������%�������������:����������������%����������������������������������������%��������%����%������������:�������!

8! ;��� ������� ;���� ���%� 7�� ��������� ��%� ��%�����(�!

3 /�����/��������%�������������������+��������#��,��1�7��3��<���#���7���3��#1��#8��,7��13��61��8#��3����=3���11���7#�#�7��,#1��1,#��713���#<7����������������������9�>�)��������>

���! ?���%��������������������������%��&���!���! 0�%�9�������������������������%�������$������9

�����3���#���3��#8��

0������#���3��,7��8#���=3��#�7��

"�����7���#���3��#1��,7��61��

@�����7���#��,7��8#��

$��=��$

Page 105: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������ ��

��� ������������

A�������������������%��������%�����������$������������������������+� �������������������� ������������������������� ���������!

������A����9

� � � �→

�����������������������%�+��������� ����������������+�������� !

B����������+��� ������ � � � �→ �����������%���%������%�����%��������+!

�������*������ �+ � �*�%������C�%���C�%�������*�%������@)$

����� ������#,�������;�����%���?��

� ���������� ������ ��������� ������ ������������%�

*������� � � � �→

������������������������������

Page 106: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ���������������

��

� �

������ ���

��� ���

������ �����

��� � � �

����� ��� ��

� ��

���!��� "���

���!��� ����

���!��� !�#$��

&������+��������%��������������%��������!&������ ����������$%����������������%��������!

��������������������������������%�*�%������C�%�����C�%���������������������9

�� �*�%������C�%��� ����� �C�%������

B����������%��������%��������������������������������������������������������%�!

�� ��� � ��� �����

����� ����� ��� ��

;������������ � � � �→ ��������������������$�����.������������ .��� ������ ������ ����� ������� +������������������������������������������������ !

Page 107: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������ ��

�������

� % ��#����� ���# ������ % &���'�( '�)�*� % ��#����� +#������ % & ��( �������*

� �

���'�

'�)�

��

�������

� � � ��

� �

� ���

'��� �����

� ����

� ��

����,

�����

����� ������ �

# $����%��! ������������������������&�����%��! �������'�����������(�'���� &���� � � �����������)����*��� $�!��� $�(��!��� ���� �����!+�����!�(�� �&�� � � ������������

�������� % ��#����� �,��� ����"��� % ��#����� ���# �����

� � � �→

Page 108: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ���������������

����� ��������� �

;����� ������ � � � �→ � ��������� �������������� .������������ .������������� ������������������ ��������.�������������%�����%����������������+!

�������+�������������(�%�������� ������������������%��

����� ����������

A������:�%�������������������������������������������������������������������������������������������������$������ +!� "������ ������ ������ ������ ����$����� �������� ������ �:�%�!

�������

� �,�� ����

� �����

� ��� �����

�������

'�)�

����,

� �

� ���

� ��

� �����

�����

����,

'�)�

� � � ��

��� � � �→� �∈

Page 109: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������ ��

�����������������$������������������������������:�%�� ���

� �

� ��

�����

����,

� � � ��

� �����

� �

�����

����, � ��

� �����

��� � � ��

�����������������$��������������������:�%�� ��� � � �→��������

,��&��������-

�� ���������������������������������������� ( )��� � �������

DE�

DEF

DEG

DGE

HDG�IJKF

��

+=∴

+=

+=

−=

−=

� � � �→

� � � �→

( ) ( )�� � ��� � �= −

Page 110: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

� ���������������

��� � ���������

'��������������%������������������������������ ( )� ��

����� ( )�� !

B��� � � � �→ ����� � � � �� �����

( )( )( ) ( )( )� � � � �

� � � � � �

�������� !

-��

$

.

/

*���� ( )� � � →� �������

( )( ) ( )( ) ( )( )( ) ( )( ) ( )( )( ) ( )( ) ( )

� � � � � � � � �

� � � � � � � �

� � � � � � �

= = =

= = =

= = =

*������� ( ) �� � � �= − ������ ( )� � � �= + !

( )( ) ( )( ) ( )( )( ) ( )( ) ( )� � � � � � � � ��

� � � � � � � � �

= = =

= = =

Page 111: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������ ��

��� ����� �����������

A�������%����%���������������������������������$����������������%����������������������=������������

( )�� � ��→

���� � ��

�������� �

�������� ��

� ���

��������� *������ L���������������������

��������*�� �

*���� ( )�� � � ��→ ��������������������������%�

����(��9

0

$

#� *��� L ����������������� ������ ����) ��� �������

��������� � � �

1 1 1∩ =

Page 112: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ���������������

.�/�$-

( )� � �∈ ∩ ����� �∈ ����� �∈

( ) ( ) ( )� � � �� � �� �� � ������ � ��∩∴ = = =

B��9

( ) ( )( )� � � �� � � � � � � �∩ = = ⋅ =

� � � �1 1 1∩∴ = ⋅

����

�! �������6�����������������������$�������������������$���������������(�%����������%�(�%�!

#! �������6������������� ���������������������������������� ����(�%����������%�(�%�!

,! *������������$������ ��������������������$�������%���/�� � ���������������

( )( )

�2 3 43 3 5

� 3 63 4

= + −

= −

�� 0�%����%���$%������%� � 2� ����� 2 �� !�� &����� ( )( )� � �� ����� ( )( )� � �� !

1! *������� � �� � � �→ ���������������� ( )� � �� �= − !�� �������������(�� ( )� � ������������������$��������

������������ 0�%����%�����������:�%�����!

6! *������ L�������#��,���!�!�!�����=���������������������)������������������0�

Page 113: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������ ���

������9

�!����

��� ⋅=∩

�!������

���� ∩∪ −+=

�!�����

��� ∩− −=

$��=��$

Page 114: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ���������������

Page 115: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�������� !!�� ���

+�.���%� ����� ������� ������� ����������� ����� ���%�����������������.�%� ����� ��������%� ������� ���������!�+�.���%� ����� ���������� �����?��%��� ����� ������318������������������%��������������������!

��� �������������������������� ������������������

B�%�����������������������%��������������������M�������%��%��������������$��%������%�������.�%����������%����������������%��5�����M� ����%��%������������������5������� ����%� ������� �����%���� ������� ��%�!;��������%�������.�%������������������%������������9�/���$����;(�������������*������)��!

-%����� ����5���%��� .�%��� .���� ����� ��������������.�%������(�������������%������������������%�� ��%������� ����� ������� �������� ����� ������ ��%���������%�� ��%����� ��������� ���!

;(����������� ������������������� ���� �������������������%��=��������=����������������.�����������������

����� ��������� ��������� ��������� ��������� ����

Page 116: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ���������������

����%��=������=�3�:����������������������.���������������������%��#�:���������6�:���!�B���=�����������������:�%������������

� �L�������������������������%������� .�%������(���$���������%�������������%����������������$�������.���% ��������������%���9� ����7 87 � 9� �� ��������� �������������������$����9

�! '������

� 8 8 �� 8 8 �

+ = +× = ×

#! "��%����

( ) ( ) ( )( ) ( ) ( )

� 8 � � 8 � �

� 8 � � 8 � �

+ × = + × +

× + = × + ×

,! ��������

� �� ����� ����� � ��� ����� � ��� � �

� � �

1! '������

� � : ;� � : <

+ =× =

6! ��������� � �� � �

+ =× =

7! ���������

� ; ;� < <

+ =× =

8! +���%��

( )( )

� � 8 �

� � 8 �

+ × =

× + =

Page 117: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�������� !!�� ���

3! ��:����

( )� : : �

<: ;;: <

===

<! +������

( ) ( )( ) ( )� 8 � � 8 �

� 8 � � 8 �

+ + = + +

× × = × ×

�=! "��*�%���

( )( )� 8 : � : 8 :

� 8 : � : 8 :

+ = ×

× = +

'�����%����������(�� ������������� ���������������%��������N��������)���)��������N��=��������������������=!�������.���������(������$�������.���%� �����������%���� �������� ����� ����� ������ ������%�����������.���!

B�%����� �(������ ����� ������ �������� ��%%������������%���%��+�"��������%�%����O/�!

�������������� ���

������������������������������� ∧

� )

Page 118: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ���������������

���������������������

�������������������� ∨+

)

�������?���%���� .�%����� �(����� ��������%���� ������������ ������ ( ) ( )( )� � � � � ∧ ∨ ∧ ∧ �������������%�����������.�%������%�����M� ������.�%�������%�����������������P

������

( ) ( )� � � � � �∧ ∨ ∧ ∧

( ) ( )� � � �� ��≡ ∧ ∨ ∧ ∨ ��"�*�%���

� .=

. �=

( ) ( )� � � �� ��≡ ∧ ∨ ∧ ∨ ������%��

� �� � � � �� � � �� ���%���

( ) ( )� � � � � �≡ ∧ ∨ ∧ �� �������

( ) � � �≡ ∨ ∧ �� �������

3 > :� �

Page 119: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�������� !!�� ���

B��� .�%����� �(������ � ��%������ ��� ���� )� ������� �� ���� ����.�%������������)�������� >: ���!

�� ������������������������������������������������

;������� ����%� %�������� ����� ��%�(�%�� ������������� ����� ������� %�������� ������ ����� ������ ����%.�������� ��������� ���������� ��%����� ������%�� ���.������������������ ��������� ���!

+��� ����%���� ����� ����� ��%��� ��������� ����%�������� ���������9

�! +�"

� � �≡ ×

1 (�

� .

��00

0�0�

.=

�0�0

3 >:�

�000

� ) � ��

0 0 00 � 0� 0 0� � �

� �

Page 120: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ���������������

#! O/

� � �≡ +

,! �O-

? @:≡

� 234��25�62�257

� ) ���8�)

0 0 00 � �� 0 �� � �

� �

� �9

0 �� 0

� �

( )� � �≡ ×

� �

� ) :

0 0 �0 � �� 0 �� � 0

� 234�3;�623;7

( )� � �≡ +

� �

� ) :

0 0 �0 � 0� 0 0� � 0

Page 121: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�������� !!�� ���

� :1�� �< �3;�6�:=3;�7

��� ��� � �≡ + ≡ ⊕

� :1*�� �< �23;�6�:=23;�7

? @9 @:9:≡ +

�������?���%����%���������������������������������9

( )( ) ( )( )� �� � � � �� �� �= ∨ ∧ ∧ ∧ ∨

'������ ����%�������!

� �

� ) :

0 0 00 � �� 0 �� � 0

� �

� ) :

0 0 �0 � 0� 0 0� � �

Page 122: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ���������������

�����

-

� �� � � �� �

� �� �

� �

� �

� � � � � �� �� �

� � � � � � �� �����������������

� � � � � �� �� �������������������

� � � �� �� ��������������������������

� �� ������������������������������������������

�� � � � � �

� � � �

� � � �

� � �

�� ��������

������� �

��������

� ��������

� � % �=

Page 123: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�������� !!�� ���

��� �������������������������� �������

������������������ ������ � �������������������������������

"������.���%� ��������%���N���������������%���'�'���� ���%��� )� ���� ������� ���%��� A� �� ������������������� ���%���'�'�����A� ���%������� ���������%���9

�������0�%����'�'�����A� ���%�16��13�����8#!

������A����%��%����%�16�������� �� �×A����%��%����%�13�������� �� �×A����%��%����%�8#�������� � �� �×

B���'�'���%�16��13�����8#�������� � �� � � ���� � �

B���A� ���%�16��13�����8#��������,!

��%������� ������'�'�� ����� �����%� �%�� ����� ������������ �����%� ����� ��������� �������� ��%����M� �����A� � ������ �����%� �%�� ����� ���� ����� 16�� 13� ���� 8#�������������� �����%��%����������������� ��%�����!

�������*���������������������� ����

�����

� �������#��,��1��6��7���=���#���6��#=��,=��7=�

������! 6�N��#

'�'���%�6������#��������7=#! 6����#

A� ���%�6������#���������,! @����� Q�%��P

��N�=����

�������

Page 124: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ���������������

��%�������������������%��������������N�=��������������.���������Q�%����%� ��

��A ���������!

1! @�����L�����P� � �× =

�������

123456789012345678901231234567890123456789012312345678901234567890123

123123123123123123123123123123123123123123123123123123123123123123123123

� � � � � � � �� �� �� �� �� ��

� � � � � � � �� �� �� �� �� ��

� � � � � �� � �� �� �� �� �� ��

� � � � �� �� � �� �� �� �� �� ��

� � � �� � �� �� �� �� �� �� �� ��

� � �� �� �� � �� �� �� �� �� �� ��

� � � � �� �� � �� �� �� �� �� ��

�� �� �� �� �� �� �� �� �� �� �� �� ��

�� �� �� �� �� �� �� �� �� �� �� �� ��

�� �� �� �� �� �� �� �� �� �� �� �� ��

�� �� �� �� �� �� �� �� �� �� �� �� ��

�� �� �� �� �� �� �� �� �� �� �� �� ��

�� �� �� �� �� �� �� �� �� �� �� �� ��

1212121212121212121212121212121212121212

1234567890123456789012312345678901234567890123

� � � � � � � �� �� �� �� �� ��

� � � � � � � � � � � � �

� � � � � � � � � � � � �

� � � � � � � � � � � � �

� � � � � � � � � � � � �

� � � � � � � � � � � � �

� � � � � � � � � � � � �

�� � � � � � � �� � � �� �� ��

�� � � � � � � � �� � � � ��

�� � � � � � � � � �� �� �� ��

�� � � � � � � �� � � �� �� ��

�� � � � � � � �� � �� �� �� ��

�� � � � � � � �� �� �� �� �� ��

��%�������� ����������� %���� �������� � �� )� �� �� ��������7=���.���������������%� ���"����������7=!

Page 125: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�������� !!�� ���

��� ��� ��������������������� ������ �

*�������������������%��� ������������������������������ ����� ����$�������� ����� ���� ������������������!�*�����������������%��������#���%�������9

�� "������ ���%� ����������� ���%� ���������!#� "�������������%�����!

����� ��� ����������������� ��������

;�����������.�%� ���%� ������� ���� ���������� �����������������������������%���������������9

�� A���������� �%������ ���%������ ����%�� ��������%��������������� ����� :�%����$:�%����� ����� �������������� :�%����� ����� ������ �������� �������!

��������R���SR���S��R ′′′ ������� ����������� �%�����

�SR���S��R�SR��� ′′ ������ ����������� �%�����

�� @���%��� ����� �@�+���������.����������������������������������%��$���!

�������� �� ����� ����= + +@���%��� ����� ����� ������� ����� .��� ����$�����@�����������������������������!

������������ ����������� � ������������� �� �������������� �� ���������

�� ��� �����������

�� ��� ��

�������

� �

� �

� �

� � ��

� � �

��������������������

�� ��������������������

� �������� � ����������������������������

��

Page 126: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ���������������

�������

��� � ��� �� ��� ������ �� �� �������������� �� ��

+=′+′′+=

����� ������

B���������������%�������

B ����%������������������$�����%�����������������N��������

����������N���������

�����B���������������%������ ����������������������������.������������������������������������������%�

�B ���

�� ������� ��%������ �����$������ ��� ���� ��� ���������$������ ����� ������ �������� ���������� �����������������������!

�������

⎭⎬⎫

=′=�

���������

�����������������%�������������������������

⎭⎬⎫

′=′=�

���������

����������

B�����������������%��������������

���� ����� +=++

�����������������������������#����������������� �������

Page 127: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�������� !!�� ���

�������

� �

� �

� ��������������� �� ��

� ���

� � � ���� ��� ��

������������� ��� � ��� � �� ��

������������� ��� � ��� ���� ���������������� ��� � ��� � ��� ���

����������������������

� ���

� �

� � � � �

� � � �

� � � �

� � � �

������������������������

� �

�������������� ��� � ����������������� � �

� �

� �

@���%��� ��������� ������� ����%��� ����� �@�� ��������� ������������%����������������������� ������������������������������!

�������

����� ��������� �� ���������� ��� �

′′+′+=′′=

�� ������������������������%��������������������%���9

�? �8 �8:� �:8�:= + +

�? �8 �� �8:� �:8�: 8�:= + + + +

�? �8 �� 8�:= + +

�? � �����������%��� ��������

��� � �

��� � � ��*���

��*���

Page 128: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ���������������

;���$����� ��%� ����%��� ��������� ������� �%�������� �

�B ����%�����%��� ����� � �����������������

�? � ?+ =

���� ����� ���� ����������� �%������ ���� ����� ��%������

�������� ����$����� ��%�����!

������������������ ��������������� ′

��

���������

���������������������

=′′+′+=

′+′′+′+=+′′+′+=

B��� ����%��� ��������� ����������� .�������%� �%����������!

����� �� �� �� �!

+������ ����� ��%� ����%��� ����� ����� ������ ������������������%� �%�� ����������� ����%��� ��������!

!����!���"�#������

���%������T�������������%��������T��T�������N��T��T�N���T�����N��T��T

�=�

.

.=

0

0 ��

.

Page 129: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�������� !!�� ���

!����!���$�#������

�������������� ����

�������0�%� ����%��� �����������%9

�����������������������������

′′+′′′+′+′+′′+′+=B�(��9�@�����������������

�����������������

′′+′+′+=B�(��9�@������������������

����������������

′′′+′′+′′′′+′′+′=

B�(��9� ���

′′+′= �����������

�.

/�

/=�

�=. �=.= �.=

/=�=

/�=

00

0�

00 0��.

/�

��

�0

�� �0

�.

/

/=

00

0�

0 ��./�=. �=.= �.=

��

�0

Page 130: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ���������������

00

0�

00 0��$��

��

�0

�� �0

√ √

√ √

�� %�� �� %��

00

0�

00 0��./�

��

�0

�� �0

�� % �/= C .=/= �� % �/= C .=/=

��

�=�

�$ �=$

�=�=

��=

�=$= �$=

/�

/=�

�. �=.

/=�=

/�=

�=.= �.=

√√

������

��

�=�

�$ �=$

�=�=

��=

�=$= �$=

00

0�

00 0�

��

�0

�� �0

�� % � �� % �

�$��

Page 131: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�������� !!�� ���

��������

�! ?���%������� .�%����� �(������ ����� ���������������� ��������� ����� �� ��(���� ����������%�������� ���� ����%���� ������� ����%��������������.�%�������%�����������������!�� ( ) ( ) ( )� � � � � � ∧ ∨ ∧ ∨

�� HHUVKHVUKWK ′∧∨′∨∧�� ( )( )( )� � � � �∨ ∧ ∨ ∧�� ( ) ( )( )� � � � � �∧ ∨ ∧ ∨ ∨

�� HUVWKUHVWK ′∨∨∧∧∨�� ( ) ( )� � � � � ∧ ∨ ∨ ∨

�� HUWKHHUWKVK ∨∨∨∧�� HVWKHHVWKHWVKWK ′∨′∧′∧∧∨∧

#! ?���%�������������� �������������������������������%��� ������� ��(����������� ����%���������������%����������� ����%�������!�� ( ) ( )( )� � � � �+ × × =�� ( ) ( )(( )( )@ 9: @ 9 9 9 @ ?× + × + × + =�� ( )( ) ( )( )( )� � � � � � � �+ × + + × × =�� ( ) ( )� � � � � �× + + + =�� ( ) ( )� � � � �× + × =�� � �� �� � � �� �� �� � � � � � � � �� � � � � � � �

�� XHUWKVWWVU =′′′′+������+T T0T�N�+T 0T�N�+ T0T�N�+ 0T���@�������+N N0��+N N0T��+TN N0T��+TN N0T��+TN TN0T����@.������+T 0T�N��+N T�0���@������ 0���+T�N+ �T�N��+ 0�T�TYT

Page 132: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ���������������

,! /���������� ������� .�%����� ������ ���.����� ����������� ,� ������� ���� #� ���������� ����� )�� ��� Q��������������������������������������������������#������,������������������������%����������������������������������������������������!

1! ����������� ���"�����%���9�� ������ Q�%��� ����������� � ��� �� ��� �

�� � �

6! ����������� ����

A ����%���9�� ������ Q�%��� ����������� ( )�� � ��× +

�� ���

7! 0�%� �%�� ���������%� �)�%��� ��������(��9

�������� ������� ������ ������������� ���� ������� ����� ������

������� ������ ������� ������������� ����� ������

�������� ������� ������ ���������������� ����� ���� ������

� � � � �

� � � �

� � � � �

� �

� � � � �

� � �

� ������ ����� ������ ����� ����������� ������� ����� ������

� ������� ������ ������� ������������� ������ ���� ����� ����� ������

� � � � � �

� � �

� � � � �

� � � � �

Page 133: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�������� !!�� ���

8! /������� ������� .�%����� ������ �����%���� �����������,���������)���������Q�����#������%���������!�����������������������������������������Q����������� ����� Q����!� ���� ���� ������ �������� ����� ������������������������!

3! /��������������.�%������������������������������������#��������+����� �����,���������������)����+�Z� ��������+��� �����Q�����+��4� !

<! '���������%���������.�%�����������������������!�3���������������#���!

�=! ;��%���������(�� �����%������� ������� .�%���������� ����� ���� �%����� �������� ���%� �����%��������.��� �������� ���%� ��%������ �������%�����%�� 9

���������������������������� ���������� ����������������������

�� ����� �����������������������������������������������

�� ������ ����������������������������������������������

���� �����(�� ��%������ ������� ������ ����������������%� 1� ��� ��������������� �������������%.���������(�����%�����!

Page 134: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ���������������

STOP

3

2

1

4

��!

?���%����������������%�����-O ���������������1���������

�! ;����%����������#! �)���%�����������������%�,! *���� ��%����1! ;����%������%����!

�%�������������M

�! B�������������%������������;����%� �)���=����������%�����%���=������������)��������%������%�������������-O

#! B��� �������� ������ ������� ��%��� ����� ��)������������%���)����������������������%��������=������%������%���=������������%������%����!

,! B������� ���������(��� �����%������%������������$��%��������=��������%���)���=����������%������%����������������%���� ��%�����������!

/����������%���������������������,��������[����������$��%������� \� ������ �����%� ��)��� ������ �����%� �����%����%��� ������� ������ ������%��!

Page 135: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�������� !!�� ���

�#!

A

B

C

?���%������������������������%��������������������.%������ ����� �������� ��%������ ,� ����� �����%� ����� ��%����������� ��������� �%!� ��%���� ������� ��.�� ������%�����M

�! ;��������������%��������������%���=!#! ;����,�������%���������������%�+������+������

�=�����0��=!,! ;����#�������%���������������%� ������+���� ���

����0��=!1! ;�������������%���������������%�0�����������

�����%����!

�������� %�������� ����������������� ��%������ �������������%������%��������������� ����� ������� ����#��������,!

�,! �����%�����������������%�,�������������8�����������.���������.�%������������������,������������1���������!

$��=��$

Page 136: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ���������������

Page 137: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� ��

���� �����������

������ ���� ��� ��������� ������� ��������� ������ ������ ������������� �������������������������������� ����� ���� ������ ������� ������� ������ ���� ����������������������������� ��������������������������������� �

��������������� ��������� ���� �������� ��������� �����

������������ ����������������� ���������� ��������������������������������� �������������� ���� ����������������������������� �������������������������

���������������������������������������������

Page 138: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

���� ���� �� ��� ���� ��� ��� ������ ��������������� ���������������� �������������������������������������� !� ������ ����� ����� ������ ������������� �����"��������#� ������� �������� ����� ����� $��� �� ��� ����� ���������� ���������������������������������������� ������� �������������������������������������������%�� ������� ����� �������� �������� &'��()�� ������'� ������ ����� *����+,���� ����(� ������ � ����� ����,������-����� � �������������� ���� ����������,������ ���� .��� �/� E� ��������� ����������� �������������������������������� ������*�����,�������� �� ��,����������������� �������������� ����������,������������������������������������

����������� ����������,������ ����,����0���� ���������(��1�����$���������������������,�0������������������������������

� � � �

���

�� ����

��

��

����

��� ���

���

��

���

��

���

������

���

Page 139: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� ���

��� ����������

�0�����0������ �������������������������2���0����� ������3

�� ��������

������ ���������� ��������� ������������������ �������� ������ ������ ������������������ 4� ����������

��������

��

��

����

��

��

��

� �

5���������6����������� ���� 4� ���� ������� ��� ���� ���������� ����� ������ ������ ���������� ���� ������ ��

�������

� ���������7�������� ������� ��� ������������ ���������� ��� ������������������������������������4�����������&������� )� ���������� ����� ����� ���� ��� � ����������

Page 140: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

��������

����

����

��

��

��

��

%�� ��� ����� ������������ ������������ �������������� ���� ��� � ������� ����(�� 8�� � ������ ������ ����������������������������������

�� ���������5�*����� ���������� ������������������������������

�� �����������%�� ������� ���������� ���������� �����������������������������������������������������������������

������� K5

Page 141: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� ���

�� ����������%�� ������������������ ���������� ����������� �������������0���������������������

�������

�� ������������ �������� � ������ ��� � ����� ����������� �� �������� ������������������������������������������ ������ ������������� � �������� ������ ����� ��� �������������� �

�������

Page 142: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

������������������������9���0������ ������3

�� ������ ������5��*�������� ��� � ������ ��� � ����� ������ ��������������� �� ��� ������������������ ������ ����� ��� ������� �������������� ������������� �����

� �

�������5����(����3

� ������ ��� � ��������� �������� ����� ���� ��������������������������*��������

� 5��*��������������������������������������������� ���������������� ��������������������

5�������������������������������������0����,������������������������������������������

�� �����������(���������� ���������� ����������������������� �������� ������������ ������ ���� ������ �������������� ��������������������������������������

Page 143: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� ���

�������

� �

��

��

��

��

����������

���� ������ ��� � ������ ������� ���� ������ ��� ������������ ����� �������� ������

������� ��� � ������ �� ��� �������� ��� �� ������� ������������������ ���������� ��������*����������� �

�� ���������������:������������� ���������� ������������������������ ���������������������������������� ������������������� ��������������������������������������

�������

� �

���

Page 144: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

��� � ��������

:������������� �������������� ������������������� �� ������������������������� ������������3

�� ���;������������������������������������������������

������� ������� ����������� ����� ���� ������������� ��������������� $�������������������� �� ����������� ����������������3

$�������<�$�������<������$�������<�5���������<������$�������<�6��� ���<���������<���������� ��������

� !������ ���6������;�����������������������������������������������

�������$�������<�6��� ���<�$������$�������<�$�������<�������<�5���������<�������<�$������<$���������� ��������

�� ����5������������������������������������������������������������ �������������������������

�������$�������������<�$���7���������<�$��� �����

$��� �������������<�$��� �:��5�����<�$����������

���� ��������

Page 145: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� ���

�� ����7�������������� ����� ������ ����������������� ��������������� ����������������

�������$�������<�6��� ���<�7���������$�������<�������<�6������<������������ ��������

�� !"���6�0��� ������ ��� ����� ������� �� ������� ���� ����� ����������� ��������

�������$�������<�5���������<�������<�$������$������� <� 6��� ��� <� 7���������� <� 6������ <� ������ <$��������������������

�� ����%���������0�0������ ����������0�0���0�0������������������������� �

�������� � �

� ��

%�� ����������� ������������0�0�������� ����������������� ������ ������������ ����� �����6%16�� ���������� 9&����������������������������0�0��)

Page 146: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

� !����������6�0�������0��������0�0������ �����������0�0���0�0������������ ���� ��������� �

����������� � 0����� ��� � &� �� )� �����������6�%�1�(����������0�0��������0��������� �������=�>��&������������������������������ 0�0��)

�� ��������������������

��������������� ������������������������������������������� ���������������������������������������������������� ������������� �������� �

$���������������������������������������������������������������� ����� �������� ��� ������

������������� ��������������������������������������������������������$�������<������������$�������<�$�������<������$�������<�5���������<������$�������<�6��� ���<�7����������<�7��0���<�������

����0�����������������������������������������������������������$�������<�$�������<����������������� ������

���������� ���������������������������������������

�� ������������������� ������ #�#���(������������������������������������ ���������������������� �������������������������� �

Page 147: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� ��

�������

� � �

� ��

$���� ��<���=�!

��<�6�=�4

��<���=�4

��<�(�=�!

��<�1�=�4

��<�:�=�9

��<�?�=�@

$���������������������=���&�)�=�@

� $���%�&�������##���$������� ������ ������������ ���� ����� �����0�� �������������� �

����������� 0����� ��� � ������� ������������ ������������������ ������3

��&�)�=�@��&�)�=�9��&6)�=�@��&�)�=�@��&()�=�9

Page 148: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

��&1)�=�4��&:)�=�9��&?)�=�@$�������������� �=���&%)�=�4

�� '�����������#�#����������� ��� � ������ ������������ ���� ����� ����������������������� �

�������������� ���������� ������ ���������������������� ��&%)�=�@�

�� ����������������5��� �������� ��� � ������ �������� �� ��� ����� ��������������������������������������������������0������������������������� �����������1�

�� ���������7����� ��� � ������ � ����� �������� ����� ��������������������������������������������������0����������� �������� �������.1/

��� ������������������������

�� ���� ���� ������ ������ ���� ������ ��� � �� ����� �����!����������������������0����� ������������������������ ���������������0����� �����������������������������������������������������0����� ������������������5����������������������������������������5������� ������������������������������ �

Page 149: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� ���

�������

� �

��

��

��

��

��

��

��

���

���

���

������������ ����������������3

� �

� �

� �

� �

� �

� �

� �

� �

���� �

���� �

���� �

���� �

���� �

���� �

���� �

���� �

$������������=�4@$�����������=�!4$������������=�4�����������������

��� ������ � ����������� ����

������ ��� � �� ��� � ������ ���� ������ ����� ���������������������������������������� ��������������������� ������������ ���� ��������� ���� ������ ������ ����� �0������ �������� ������������

Page 150: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

�������������������������6� ����0�������� � ����������A�B

�����������������0��� �������������������� �������� ���������3

� �

��� ������������������

������ ��� � �� ��� ���� ������� ������� ���������������� �������� ��3

� $����������� $��������� �������� ���� 5��� �����

����������� ��������� ������������������������������������ ?����� 0� ��� �

�������� �

� � �

��

�� �� ��

��

� � �

�� ��

Page 151: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� ���

%������%������� ������������������������������������ ��������!�<�!������������������������������������3

������� �����������

� �� �� �� �

� �

� �

� �

� �

� �

� �� �� �� �� �

��� ����������

������ ��� ��� ��� ���� ������������������������������3

�) ����� ���� &����0���� ���+)�) ����� ������ &(���� ���+)0) ����� ����<������� &?�0���0�� ���+)

�������C������������� ���������������������������������������������������

� � �

��

��

��

��

�� ��

��

���

���

���������������� ��������������������>�D�>����������� ����������� �����>��������

Page 152: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

� �� �� �� �� �� �� �� �� �� �� �

������ � � � �

� � � � � � � � � � � � � �� � � � � � � �� � � � � � � � � � � � � � �� � � � � � � �� � � � � � � �

!���������� ������%�������������

� �����!�������!�������������=�E� �����!�������4�������������=�!������������������������������������

� ����� @�������@�� �����������=�4�� ��������� �������

� �����B�������2������(����1�=�4������(�����1�������������4�������������������

� ����� >� ������!�� ���� ?� �����=� E�� ���� ?� ������ �����������������������������

����� ���������� ��� ��������������������!!�D�!!����������� ����������� �����!!�������

� � � � � � � � � ��

��

� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �

� � � � � � � � � � ������������

Page 153: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� ���

���������������� �������������

���� ������ ������ �������� ������� ������ ����� �����������������������������������=�!��������������������������������������������������=�E�

����� �������������� ��� ��������������������>�D!!������������ ����������������>���������!!�������

� � � � � � � � � ��

� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �

� � � � � � � � � � �

!���������� ������%�����������

��������������������������������������������������������������=�!����������������������������������������=�E�

��� ��������������

�������������������� ������ ������ �������� �������� � ������ ���� ����� �����,������� ��� � ������� ������8������� ���

� �

��

�� ��

��

��

Page 154: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

�������F������1���� ����� ������ !!�� �������:���� ����

������!@�������������������������������������������������������������� ��������0� ����������� �������������� ��������� �

F����� ������ ��� � �� ��� ���� ����� ���� ������������������� ������ ������ ������ ����� �������� ��� ������� ������� ���� �� ������ ����� ������� ������ ������������0��� &��0)�

� �

���������������� ����������� �������������� ������ ���� �� ���������������������9���0��������3

�� (����� #)����:�������� ������ ���� ������ ���� � ��������� ����� �������0����������������

!

"

!

"

Page 155: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� ���

������� � *��������:�������������� �������������� �������������������������0�����������

��������� +����#�����:�������������� ���� ���������� ��������������� �����0�����������������������

!

"

!

"

!

"

�������F����� ������ ��� � �� ��� ����� ������ ��������� ��������� ��� ��������������� ������������ �

�������������6����������������������

Page 156: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

���� �������������������������������������=����=�BEG���� �������������������������������������=����=�BEG6��� ����������������������������������6��=�6��=�BEG��������� ���������������6�������������6�=�!EEG

��0��������������� ���� ���������� ���������������� ������������������� ���������

���� ������������������������

�������� ������ ���� �������� ��� �����������������������

�) ?�� �������) ���� ������

?�������� ������ ���� ������ ������ ������ ������������������ ����

H���������������������������������������������������� ������ �����5�������� �����������=�E�������� ������,����,����0��

�#

� �

�#

�#�#

�#�# �##

Page 157: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� ��

5���������������������=�E��������������,����

�������

$

"

!

5���I�=������������������������I�=�E?��������7�=�4�������������4���������������������7H���������7�=�!�������������!�����������������������7?��������F�=�!H���������F�=�4

5�����=����������������������������=�E

���� ����������������������

������ ��� � ��������� ��� � ������ ���� ��������������� ��������� ���� ������ ������ ������ ����� �������� ������������������������%�� ��������� ��������������������� ���������&�� ��������� )���� �����������

Page 158: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

������������������� �������������������������7���������

%�� � ������ ������� ���� &�� )�� ������������ ��� ������������������ �����������������������,�����������,��������������������������������������������������������������� ��������� ������������������������������������������������������������&�������������)

�������

��

��

��

��

��

��

� �

� �

� �

F����������� ������� ��������� ������������ ��� ��������������������A������������������� ����������

Page 159: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� ���

�������������������������������������9��������������B�������������B

,����%���������-����� ������� ����������� � ��� �������������������

����������������������������������������������������� � ���� ��������������������������������� �

�� � � � �� � �

�� � � �� ���� %� �

�� � �� �� �

������� ������ ������ ������� ������!��"�������� � �����!�#�������������������!�#����������!� � � � � � �� � �� �� � �

4� � � � � � ���� & ' ( % %)

** ******** �+

** %) %,�+

� � � � �

� �

9� � �

�+ &,) '

***�+ �)

���� �����������

7��������� ������ ���� �� ��� ���������������9� 0��������3

�) �������� �����) �������� ������0) ��������������

Page 160: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

$����������������������������������� ������ �

� ���������������������������������������������������� ������������������� ������� ��������������� &D� &%))�

� ��������������������������������������������������������������������������������& ������������)�

� ������������������������������������ ���������������������������������������& �������������)�

� �������������� ���� ������ ������������ ��0���� ���������������������������������������������� ������� ����� �� ��� ��������� ����� �������������������� ������������,�������,���������������������

!������

� �

� �

-

� ��

�����������

!) 5�������������������!�4) 5����� ����1� ���� ���������� !� ������� ���� �������� ��� 1� ����� ������ ��������� ��������� �����������

9) 5������6�����(� ������ ��������� ��������� ����������� ����������� ����� ��������� ����������� 4�� 9�����@����������������%�� ���&�'()�!�"

Page 161: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� ���

�������������

����

�� ��

��

�� ��

� -

�-

��

-�

!) �����������������!�4) ��������������������������!������������������������������������������������������������������

9) ������������������4�@) ������������ ��������������4������������������������� �������������������������������������

B) �������������������92) ��������������@

$���������������������� ��������D�&%)�=�@

����������������� ������ ������ ��� � ������ � � �nK ��������������������� nK �������������3

� ��

� ���

��� ������������ � ��

� �������������

Page 162: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

� � ������������������

�������

� � �

� �

� �

� ��

� �

�� ����� ��������������� � ����� ������������� �� ����� ��������������� ����� ���������������� ����� ��������������

������ � �

� �� �� �� �� �

��./.�

��

��./.�

�./.�

�./.�

��./.�

��./.�

���./.�

��./.-

��./.�

��./.-

Page 163: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� � �

���������������%�� ���&�'*�)�!�+�

� � �

� � �

� �� ��

� � ��

�� ��

�,**** 0 **���* *����1�*2�1��*�%,*** 0 **���* *����1�*2�1��*%&,*** 0 *���* ����1�*2�1��*&+,*** 0 *���* ����1�*2�1��*+(,*** 0 *���* ����1�*2�1��*(

� � �� � �� � �� � �� � �

��

�� ��

��

��

��

��

��

���

���

���

���

���

-

���

� -

� � �

��

-

��

��

-

- ���

���-�

���

Page 164: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

� � ������������������

� ���� ��

!� ���������������������������&����*�������������������������)� ������� �������

� � � �

��

� �

� � �

� ��

� �

��

Page 165: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� � �

Page 166: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

� � ������������������

4� �������� �������������� ������������������������������� � ������ ���� ����� ������ ������ ������� �������������������������������������������������������� ����������������������������������*������������������0���������������������0���������������� ��� �� ������ 4� ���� ����� ��������� ����������� ����������������������������������������������� �����������0��������������

� � �

� 3

! $4

5 "

� �

� �

3

��

Page 167: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� �

9� %�������������� ������� � ���������������������������������������������������������������������� ���� �����

$ , - �$ . � . . �, � . � . �- . � � . � . . . . �� � � � � .

$ , - � /$ . . � . . �, . � . � � .- � . . . . � . � . . � .� . � . � . ./ � . � . . .

@� %�������������� ������� � �������������������J� ������ ������� �������� �������� ������� �����������������������

$ , - � /�� � . . � . .�� � . . . � .�� � . . . . ��� . � . � . .�� . � . . � .�� . � . . . ��� . . � � . .� . . � . � .� . . � . . �

Page 168: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

� � ������������������

B� 5������������ �����������������������������������<�������

� �

2� ;���������������������>� ������ ��� � ��� ������������ ���������� ���� ������3

A B C D E F G H I J K

A 1 1 2

B 1 1 1 1

C 1 1 1 1 1

D 1 1 1

E 1 1

F 1 1 1 1

G 1 1 1 1

H 2 1 1

I 1 1 1 1

J 1 1 1 1

K 1 1

�) 0������������������� �������������������� � ����������������%����� �� ���������������������������������%�� ������

) 1�� ������� �������� ���������

Page 169: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� � �

A� ������������������������ ������������������F;��C(5�������� ������ ��� �� ������� � ����� ���� �� ��� ��������������������������������� ���� �� �������������� ������ ��������� 4� ��� � ���� ���� ��� ������������ ������������������ ��������� �������������������������������K

A B C D E F G H I J K L M N O P Q R S T

A 1 1 1

B 1 1 1

C 1 1

D 1 1 1

E 1 1 1 1

F 1 1 1 1

G 1 1 1

H 1 1 1 1

I 1 1 1

J

K 1 1 1

L 1 1 1

M

N 1 1 1

O 1 1 1 1

P 1 1 1

Q 1 1 1 1

R 1 1

S 1 1 1

T 1 1 1

Page 170: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

� � ������������������

L� ��������� �����������������������������������3

A B C D E F G H I J K L M N O P

A 1 1

B 1 1 1 1

C 1 1 1

D 1 1 1

E 1 1 1

F 1 1 1 1 1

G 1 1 1 1 1 1

H 1 1 1 1

I 1 1 1

J 1 1 1 1 1

K 1 1 1 1 1

L 1 1

M 1 1 1

N 1 1 1 1

O 1 1 1

P 1 1

�) ;����� ��� ��� ����� ������� ��������� ����� ���������� ������� �������� �������� �������� ��������������������� ������������������

�) �������� ������� ������������ �������� ���������������������� �������� ���� ����������������� ����������� �������� ��������� �� ���������� ������� BE���������������� ��������� ������������������������������������������������������� ��������!EE������

Page 171: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� � �

!E�������������0��0�� ������������ �%���������������3

A B C D E F

A 0 1 1 1 1 1

B 1 0 1 1 1 1

C 1 1 0 1 1 1

D 1 1 1 0 1 1

E 1 1 1 1 0 1

F 1 1 1 1 1 0

�) %������������ �%�) ;������������������������ �%0) 5������������������������D&%)�����DM&%)

���� � � ������

������ ����� ���������� ������������� ������ ������ ���� �������� ����������������������������������������N� ���� �������������� ���� � ���� ������ ��� ������������� ������������������ ������� � ����� ������� �������������� ������������ ���� ���� �������� ��� �� ��� �������� ����� �������������

7������������������� ��������� �����������������<�!� ���������� �������� ����� ��������� &0�0��� ����)� ��������� �������� � ���������

Page 172: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

�������

6789:.;<=<:89>?:9.9@9ABAC?

;<=<:D.EF@[email protected]?G:./.�D../.H

������� ���� �� ��� ��������� ������� ����� ��������� ������������������ ��������������������������������������������� ���0�������

�������7������������������4�+�9�O�@�+�4�<�!�O�B��� ������������

�������������� ����������� 3

I I � �

- � � -

J

��-.�.�K..��.�.-KK.J.��..�K./.�

7��������� �������<� ���������������������� ������ ��������� ������� �� �������� ������� ���� 0������ �������������������������������� ����

:�������� ������� ����� ����� ���� ������ �� ��� ���������������3

�9:B98.>7L78./.�9:B98.EFEF8.J.�9:B98.;<=<:M

Page 173: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� ���

������

�� �� ��

����� ���������� ����� ���� �� ����� ��� ����� ����� ���������������

��������� ����������

���� �������������������������������������� ��������������� !��������������� ���� ��������������� ��������������� "���� �� ����������������� ������"

�� ����������������� �����!��� ������� ����

���� ���

!�����"�#��

����������� ���

$��������� ������� ����%� �������� �� � �� ����� ������������������������%������������������������� ��� &��������������������'

Page 174: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ������������������

�������

� ����

� ���

��

� ���

��

��

����

� ���

��� ��� �

� �

� �

� � ��

� �

%��� %��� '''� � ������� �� � �� ����� ����� �������� ���� ��%��� %�������� � �������� ����� �� �� ��� &���� ����� �����������'

���������������� ��

(������ � ���� ����� ��� ������ �����)������������� )������ �������� �������������� ������ ����� �� ����� ������� �� ��� � ���� �� � �� �� � �����*������������� ������ �� &� ��������� ��������������� ����� &����������� ����� &� �������� ����� ��� ��� ����� ��� ����������������������� �� ����� � �� ����'

������� &� �������������� ����� �� ����� �������� �� ����� ��� �+�����'

� �

� �

� ��

� �

�� ��

��

� ��

�� �

Page 175: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� ���

(� ���� �� � �� ������� �������� � ���� �� � ���� ������� ��� ����� ��� �+�������� � ��������� ������,

��������������������������� ����

$���������� ��������� ������������������ ���������&��� ����� ���� '

-���� ��� � ������� ������ �� �� � ������ ��� ��� .����������/'�$������������������� ����������������� �������������� �� ��� ���� �������� ����� ���� ���� �� �� � �� ����� � �� �� ������ ��� ������ ��������'

��� � ��� � ������� ������ ������ .���� � ����/� �� �� ������ ��� ��� ���������� ���"� .�� �/'

%� ������� ��������� �� ������������������������������� '

� �

� �

� ��

�� �

Page 176: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

-����������� 0��1�����2��3�����4��5���������&��� �������'''������������ %� ������� ���6�������������-�����

�/ 7�� ��������������������� �� ����� �� ���������������� � ����� � ������ ������� ���� �� )���� �� ���� �� ������� ��'

�/ �%� ���� �������� ��� ���������

$������ ��� � ����� ����� �� ���� ������ �� �����&��� � ���� ����� ���� ����� ������ ���� ��� � ������� �� �� �� ��� �������������������&��� ����������'

��

��

��

��

��

��

!

"�#����$%&'�'$%��#�(&�$�%��&')'$�%&���)�)��%����$�%�*%(���%���$)+����%�%#,�%&'�'$%��+,��+$�%)�)��%�%((&,$-���%+,#,�*%-��),.

Page 177: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� ���

��

��

����

����$��$%�%+,#,�����$��$%�%+,#,�����$��$% %+,#,�����$��$%�%+,#,�

$��� ������������� ���������%����������������������������� �� ������ ��� � ��� ������ ������ ������� ������ ���������������������&��� �������������������'

%�������������� ������������������ ����������� ������������������� ������������������������ ������ ������������������ ������������� � � ������ ������ ��������� �������� ���������'

�������

%�������������� ���������������� ������� �� ��������������� ��������������������� �����'

� ��

� � �

� � �

� �

� �

� �

Page 178: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

%�������������� ����������������6�����������������8��� �9��� ��������������� ���:8��9;'

8��� ��� ���� ������� �� ��� ��� ��������� �� ��� �� ���������������� ���� �������������� ������� <����������� ������� ����������������������� ������ ��� �� ���� �� ����� ��� ��������� ��� ���� ������ � ������ &��� ����� ������� ����

� ����� ���&��� ����������������� ���������� � '� ������ ���&��� �������� �������� ����� ���&��� �'

�������

/0

� � �

��

� �

��

� � �

%����� ���� � <��� ���� !� � ��&��� ��� ���������� � &��� ��������� ���&��� ���������������� ���������� ����� ���&��� �'

8��� � �� ���� �������� � <���� ����� ������ ����� ����)� ��������� ���&��� �������������� ���� ���&��� �'

�������� ��� �������� ��� �������)��������

� ������ � ��� ��� ������� ������ �� ���� ���� !� � ��&��� �

� ���������� ������������������ ���������� ����� ��&��� ��.��� /'

Page 179: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� ���

��������

0���� ���������� ��� ���� <������ ��� ���� �� ������ � )��� ������������������ �� ����������� ������=� ��� ���������������� ����������� ����!��=� '

��������

��

� �

� �

� � ( $ ' &

%������ ��� ����������������&��������<���� ��������������%��������� ������������������������ ������� ������������,��������= '������������������������ >������������!��=�

������������������������������ �� ���������� ���

8��� ��������������������������� ����������� ����������������&�������������� ����������������������������������������&�*�����*�����������������&��� ������������������� �������� ��!�����'''���������� �� ��� ��� ���&��� �'�?����� ����&��� �� ��������������������������� ���&��� ���� ���������� ���� ' �� '!�� '���'''���������� ��� ���� ���&��� �'������� ������� ��� ����� �������� ������ ��� ����� ������ ������ ��������� �@������ ������� �����'

Page 180: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

�������

�1

��1�

�1�1� �1�1

�1�1 1� �1�1 1

1� 1

1 1

�1� �1

�1 1

������ ��� � �������� �������� ��� ����� ��������A�B�&�)�����&� �����'� A�B�&������&� ������ ����� ���� ��� � � ���� �������� ��� ����� ���������������������������

(������ �.-�=�0/�B�1�#���*2�=3���� ������������������ ����A�B�&������&����������)����������������� ���� ����� ������ ����� �� �� � &����� ������� ����� � ����)����� ���� ����������� ������ B�� *�� =�� #�� ���� ���� �� ����� ������������������������������������������������������

..-�=0/�B�1/�#�..�*2/�=3/

$����� ��������������������������� �����������������#�� ��������������� ��������#��������&��� ��������� �������� � �������������#��������&��� ���� � '

A� ������������ �������� &���� ������ � ��� &��� ����� ���������� ��� ����� �������� B�� ��������� B�������� � .-�=�0/� �������������� �1����������� � '����������������������B������ ��&��� ��������������������������=��� ��������� �-��������������� �0����������� � ��&������ �������������� ������ ���&��� ������������ � '

Page 181: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� ���

%2

%%

%%�

%%�

%%�

%%�%!

3

%%4

%%4

$������� ����� ��� � �������� � �� ����� ����������������� ����A�B�&������&������ ��� ���������������� ������ � �� ����� � ���������� ��������� ����� ���� � A�������&C���������� ������<�B��� ����<�B'

0� ���� ��<�B� ������� &���� � ������ � �� ����� ��������� �� �� � �������� � ������ �������� ����������� �����������������������&��� �����������&��� ��������� ������� ���������������������� �������&��� ���� � '������� ������<�B������A�B�&������&����������������

#�B�=�-01�=*�23

0� �������<�B��������&����� ������� ����� ������������ �� � ��������� � ������ �������� �������� ����� � ������ �� � &���� ����� ����� ���������� � ��������� .������� ������ ����/�����������������������&��� ���� � �����&��� ���� � ��� ������� ��� ����� �������� ����� � ���� ��� &��� �� ����'� ������ �������� <�B������A�B�&������&����������������

-0�=�1�B��2*3=)

Page 182: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

���������

' 1������ �������� ��� � �������� ���������������������

�� � �

��

��

��

� �

� �

� �

��

��

�� ��

��

��

Page 183: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� ���

��

� �

� �

� �

��

��

��

��

���

!' ������� ���� A�B�&������&� ����� �� ����� � ����)���������������������� �������� ��� ������<�B��� ���<�B ��'�/ .#��=��/�B���#�.6*!/�=�>�#�!�/ .>�B�6�B���B�!/�#�.��=���B�>�#��/&/ .#��B�#>/�*�.>�#���=�.#��B�#,/�=�.��#�!�B�# �=��//�/ .-�B�0�#�1�*���=�2/�=�.-�#�0�#�1�#���B��/�*�.-�=�0

=�1�=��/

�' ������� �A�B�&������&� ����� ���<�B� <����������������� � ������� ��� ������<�B ��'

Page 184: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ������������������

�/ -0�=�1��B�23�*�#�#���B�/ -01�B�B�1�-�=�*�#&/ -0�#�1�=��01-�#�B�#�=�/ -01�2�=�B�#�*

6' ������� �A�B�&������&� ����� ��<�B� <������ ������������ � ������� ��� �������<�B ��'�� �������������������������� ��������������������������� � �������������� ����������������

>' ������������������������� ����� �� �+�.������ /��)���� ��� ����� �)��� ���� ����8���8���8���8���8��8���8��8���� �8�'�$��� ��� ������ ����� �� ����� �� ���� �������������������� �������� �� �� ��������������� � ���'�4����� ���@��� � �� �� ���� � ����� .�/�� ������������ �� ����&� ����������������������

���������������

���������������������������������������������������������������������������������

�������������������������������������������������������������������������������������

����������������������������������������������������������������������������������������������������

��������������������������������������������������

����������������������������������������

�������������������������������

������������������

��

��

��

��

��

��

��

��

��

��

��

��

��

��

���������������������

�������������� ������ ������������������������������������

Page 185: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��������� ���

�/ ����� ����� ��� ������ ��� �� � � ���� �� � � ���� �������� �� ���� �� �� �� ������ �������� ���� � ���� �� ������ �� ��� � �� ���� � ���� �� �� �� � ������� ��� ����� ������ ���� ����������� � ���� &��'

�/ %� ���� � � �� �� ���� � ����� ������ � ���� �����������'

�' $���� �� ����� ���� �� �� ����� ��������� �� ���� �� � � ��� ��� ��� ���� �� ���� ���� � !>� �� ����� �� � ������ �����'� 0���� �� &� �� � ���� �� � ������� ���������� ��� ������ ������ ����������� ��������� �� �� >��� ������ � �� �� ������� ����� ������� ������� � ����� �� &� �� � ���� �� � ���� �� ������������ � �� �� ������� ������ ��� ������� ��� ����� �������� ������ �������� �������� �����������'

A B C D E F G H I J K L M N

A 7 10 15 12

B 8 9 13 10

C 8 11 14 9

D 7 8 8 14 12 16

E 10 9 11 13 14 15

F 15 13 14 20 15 12

G 12 10 6 25 18 14

H 14 13 20 25 16 18 20 24

I 12 14 15 48 20 16 13 15

J 13 15 12 14 22 18 21 19

K 16 20 22

L 18 16 18

M 20 13 21

N 24 15 19

Page 186: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

�' ?������ � ������� �'��� ����� �� &� �� � ���� �� � ������� ��������������������������

A B C D E F G H I J K L M N O P

A 13 15

B 13 8 8 10 6

C 8 10 12

D 10 8 16

E 15 8 14 18

F 10 14 8 15 18

G 6 8 8 13 5 11

H 12 16 13 9

I 18 6 10

J 15 5 13 14 11

K 11 13 15 10 12

L 9 15 18

M 18 6 10

N 10 14 10 5

O 11 10 5

P 12 18

)��"��)

Page 187: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

���������������� ���

��� ��������

���������D55�������������������� �� ���� ����� ���������� ������� ����� �������� �� ������� �� ��������������������� �������������� ����� ����������������������'

���������� ����� ����������� �� ���� ����� ����� ����� ������� ����������� �������� �� ������� � ��������� ��������� �� ������� ������ *��������� ����������� � ��� ����'?����� *��������� � ������������ � ������������ ���� ����������� ����� ������ ������ �������� � ��������'���������� ���� ����� ����� ��������������������������� ����������� ��������'

E���1������ . +>"/�� &����� ���������������������� ���� �� � ����� ���������� � ������� ������ � ���� &����� ���������� ��� �)����� ��� ��

− ���������������&������F− ������ ��� ������ ���� ��� �������F− ������ ��� �����������������F− ��������� �)������� ��� ��������� ������ ��� ������� �

&��� ��F

�����������������������������������������������������������������

Page 188: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

− ������ ��� �������� �� � ������� )� ������� ���������� ������� ��� ����������������� ��F

E���1������� ������� ���� ����� <����� �� ���������������� ����������� ��������)����������������������������������������� ��� ��� ����<������� ������������ ���� ������� ������� � ����� ���� �� �� �� ����� ��������� �� �� �� ��� ��� ������ �)������ ������'

������ �� ���� ���� <���� ����� ���� � <�������� *������������ ���� �� ������������������ ���������� �� �� ��<� ����� ��� ������������������� ��� ��������)������� <����� ��� ������� &� ������������� � ��� � )� ��� ��� �� � �� ��� � ��� � �������� ������� �� ����� ��� ��������'

��<� ������� ����������

� (��� ���������� �����������)����� ���������&�����������'

� (��� ���������� ������������)������ ����� ���������� ��� �����<������ ����� ���� �� ������'

� (��� ���������������� ������ �������� �� ���������<� �������������&&������� ���� ��&�����������&&��������� ������������������� � ������� ���� ��� � ���������� ����������� ����'1� ����� ������ � �������� � � �� ������ ������� -%(��� ��������� �81���������������� ��������)� � ����85E*8�������'

$�������������&������� �������������������� ��������� � ������������ ������������� '

�������(��� �� �������� ��� ����������� �� ��� ������) ������������������� �� ���������G�@� �� ���&�� ��

Page 189: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

���������������� ���

� ��� ��� ��� � �� � ���� �� ����� �� ������ ������������ ������� ��� �� ��� ��� ��������� ��'

��� ������������� ������

���� ���� ����� �� ����� �������� ������ ����������������� ����������������������

� 3� ����-������� .3-/� 8������� �-������� .8�-/� %��� ��(�&�� �� .%(/

���������� � �� ����� �� ��� ��� �������� �� ��� �� ���� �������������3-'�3� ����$�����-������� ���� ���������3� ����-������� ���������� � �������� ��������������)������ �� �� ������ � �� � ������� � �������� ������ ����� �� ������������� ��������� ��.��������������/'�3� ����-�)������ � ������� ������ �� �� �� ��� ��� ����� ���� �� ������� <� ���� ��� ����� �� ��� ���������� � ��� ���� ����� ������� ������ ��� ������ �� �� ��� '� 3� ����-������� ������������ ����� � ��� � � ���� ���� ����� � �� ��� ��� ��������'

(��� ����������3� ����-��������� ��������������� ������� ����

− $����� ���@����− (��� � ����� .D� �� ��(�&�� �/− 8� ������ ���� ����� �� ���� .���<<�&� ���������������/− $������� � ������� .����&�� �/� ��� ������� ��

������� �����− 8�������� ��� �����− - �������A�������− E���� �E���− 8� ��&��������� .������ &��&�� �/

Page 190: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

3-��������������� ��������&�����������

� �������� E������3�����>�#������ %�����$����

����� ������������ !������"�����

$������ �����������������������,� �������������������� � � �������� � ������������ �������3-��� �� ���)����� ��������� �������� � 3-� �� �� � ������ �� � ������������

%����� � �������� � ������� ������ ������ � �������� ���� �� �� � �� ����� ��� ����� � ������� ��������� ����� �� � �� ����� � �� ����'

H�������������� �������� ���� ����*��� ���� ���������� ������ ����� ���� ����� � ��� ����� �������� ������������ �� �� ���� ���� ����� ����� ����� ������ �������'� A����� �������� � � ��� � �� ���������� ����� ������ ����� ������������������� ��������� � ����� ����������� �������)�����������������.� �����������/'

�������3-�� ����������&���� �'

����������� ��� �������� ������������������ ���������� � ����� ������ � ���� �� � �� ���� "� �� � � ����������� <���'�$������ <�����������������+���������� ��,������ �������� �����*����������� � ������������ ���������&��&����'

� � � � � � � � �

����%��)%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%��)�%��)#

5�,��%+�(%��+�%)�&%�$��$%�����%��)#

Page 191: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

���������������� ���

��������������<������������������"� �"�"� �"�"� ��� ����� ����� �� �"�B�!�=� �B�!��=�"�B�!��=�"�B�!��=� �B�!��=�"�B��!��=�"�B�!��=� B�!�����6�=�,�=� �����'1��&��������� �����"����������������I J�������������������������� ���'1��&��������� ����� ����������������I J�������������������������� �'

0������ �� �����������3-� �� �� � ������� ��������������������� ����������� �&��&������ � �F

��������������������� ������������������� �&��&������ �������!�����������������������I J��� ������ ��� �'����������!����� ������ ������ ������ �� ���� �� � �� �'� A� ��������������� ���� �������� ������� �������� ������� ��������� ����� �� � �� ����� � �� ��� �� � ������� ����� ���� ���� �� �� �� ����� ��� ����'�A� �������� ���������� ��<������� ��� ���� �� ���"��� � ����� ��� ������ ��������� �� ����� � ���"�� � �������� ������ ���"���� ������� �������� ���� ����������� ��� ������� �������� �'�?��� ������� ����� �������������� ������� ��� ��� ����������� ���������������� ����� ����������� ��� �� ����'

A� ����������������� �� ���� ������ ������ �� �������������������� ������� ������ �� .� ������ �����/� ���� ����� �� �� ����� �������'

�����3-�� ��������������������

%%%5� %%%%%5�

�6$ 7��

� �

5)�+

Page 192: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

K ����<����"�"� �"�"� �"�"�

���� ����� "��$� ��� ��������$����� ����� "��$� ��� ��������$����� ������ ��$� ��� ��������$ ���� ����� "��$ ��� ��������$ ���� ����� "��$ ��� ��������$ ���� ��� � ��$ ��� ��������$����� ������� "��$� ��� ��������$����� ������� "��$� ��� ��������$����� �������� ��$� ��� ��������$

���������� ���� �� �������������� ������� �� ����� ��� ������ ��� ���� �� �������������������� ������ ����� ���������� ".�� ��� ���������/'

����� ������������ !��������#$� ����%&' ��%�

�������<� ����<�����3-��� ������� ��� �� �>�����������$��$�����$���� �-����� �

$ ���������� � ������)������$ ���������� � � �����)������ � ��� ������� <� ���� ��� ������ &� ������ .$� /���$�� �� ���� ���$�

� ������ ��� ������� ��������$�

$� ������������������.� �����������/- ���������� � �������� ����� .�&&��� �� �����/

������������ ���� ������ ��� ����� � ����� �������� �� �� ��<� ���� <����� �������� ��������

� �

� �

� �

� �

� �

� � � �

�� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� � �� �

� � �� �

� � �� �

� � �� �

Page 193: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

���������������� ���

����� ������������ !������ ���%������

(� �������� �3-��� �� ������������������������������������3-�������������� ��������� �������� ���� ������������ �� �����&��� ����� ������� � ���� ���� ������������ �� ����������� ��'�$������ ������������� ��� �� ������� ������������������ �������������� ��L'������������������������������������������� ��� �� ����������������������������

� �

5� 5� 5�

5� 5� 5�

����& (�'"�����$��� ���!���������( !�

$��������� ��� ��������������������� �����&� <� � ������������������� ����������<� ������������������������������ � )������ ����&� <� ���� ��������� ���� ���E3-�������� ��� ��� � � ������������������� ������ ���������� � ����� ������������ �����������������'

���� �' ������� ����3-� ��� ������ �� �� � ������ ������ ��

��<� ���� <����' �' 0����� ���� �)��� �� ������� &� ���� ���� �� �� �

���������� ��������������3-� ��������'

%%%%%5� %%%%%5�

%%%%%5�

Page 194: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ������������������

%%%%5�%%%%%5�

%%%%5�

%%�

%%��

%%�

%%�

%%�

%%%%%5�%%%%%5�%%%%%5�

%%�

%%%%5�%%%%5�

%%%%5�%%%%5�

Page 195: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

���������������� ���

!�' ������� � ������� 3-� ����� �� ���� ������ ������ ���������� �� ���������� ���<� ���� <����

!�' 0����� ���� �)��� �� ������� &� ���� ���� �� �� ����������� ��������������3-� ��������'

� �

5� 5� 5�

5� 5� 5�

5� 5� 5�

� �

5� 5� 5�

5� 5� 5�

5� 5� 5�

� � �

5� 5� 5� 5�

5� 5� 5� 5�

5� 5� 5� 5�

5� 5� 5� 5�

��' ������� �����������3-�������� ������<� ���� <��)�������������� �� ���������� ������������

��' 0����� ������� �)��� �� ������� &� ���� ���� �� �� ����������� ��������������3-� ��������

� �

� �

� �

� � � � �

� �

� � � � � � � � � �

���

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� � �� �

� � �� �

� � �� �

� � �� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� � �� �

� � �� �

� � �� �

� � �� �

� � �� �

� � �� �

� �

� �

� �

� � �

� �

� � � � � �

���

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� � �� �

� � �� �

� � �� �

� � �� �

� �

� �� �

� �

� � �� �

� � �� �

Page 196: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

6' ������� ������������������ �� ���������<� ������)������$���� �� ������ � �� ������� ������� ����� ���������� ��� � ����� ��� ������� �� ����� ������������ ���� ����� ������� ������� � �� �� �������� ������������� ������������ ���� � ���������� �� ��� ������������������� ������������������ �������� �� ���� �� �� � ������� ������ ���� ��� � ������ �� ������������ ����������������������� ���������������� ��

>' $��������� �������� ��������� ������ ��� �>""�������� � """���������� ��� ��������������� ������ ����� ������� ���� �����!"""������'�������� <� ���� ������ �� �� � ������� ��� ��� � � � ��� ������ ����������������� �� ����������� ��������������� ���<� ���� <����'

�' $��������� � ����� � ��� � �� ��� ������ ����� ��� � ��� � >""� ������ �� � """� ������ �� � ���������������� ����������&���� �!�� ��������������� ��� """������>�� ��������������� ��� >""������ "�� ��������������� ���!"""������

������� ��� �� ���������� ������ ������� �� ���<� ���<�����<� ��������������������� ������ ���� ����������� �� � ���������� ��� � � � ��� �� ������� ������������� ����� � ��� � ��������� �� M����� ������� ��&���

� �

� �

� �

� � � � �

� �

� �

� � � � � � � � � �

���

� �

� � � �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� � �� �

� � �� �

� � �� �

� � �� �

� � �� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� � �� �

� � �� �

� � �� �

� � �� �

� � �� �

Page 197: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

���������������� ���

������ ������� ���� ������������������� ��������N� .�� �� ������������������������� ���<� ���� <����/

�' 2��@����� 1� ���������� ���� ������ ������ ��������������� �

�������������������� ������� ���������� ����������

����������������������� ������������������������������������������� ����� ������� ���������������������������������!���!���� ������� ���������������������������"���!���!������ ������� ����������������������������� ����������� ������� ��������"������������������������ ������� �����" ��������"��������

������� ����������� ���<� ���� <����� ����� ���@����&� �������� ��������'

����& (�'"�����$��� ���!���������( !�

$��������� ��� ��������������������� �����&� <� � ������������������� ����������<� ������������������������������ � )������ ����&� <� ���� ��������� ���� ���E3-�������� ��� ��� � � ������������������� ������ ���������� � ����� ������������ �����������������'

�������

%%%%%5�%%%%%5�

�%%%%%5�

�*%�

�*%�

� �

5� 5�*%5� 5�

5� 5� 5�

5� 5� 5�

Page 198: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

8�������� �3-��������2������� ��.�/� ��������$��� ���"� ���������$��� ���"� �"� ���������$��� ��"� �"� �"� ������������ �������� ��

�����A�.(/���:����"� ���"� �"� ���"� �"� �"� ���''''';

8�������� �E3-�������������������$�������� ����� � )���"������<� ������� ���� �����������$ ���������$!

0�����*�� ��������� ���������������E3-�����������������

A�.(/���:����"� ���"� �"� ���"� �"� �"� ���'''';

��� ������������������� �

��� 0����(� ������� �������E3-������ ���� ������� �����)

� ������<� �������������� ��� �����A.(/������E3-���������.���� ����@��� �/'

������ ����&� <� �������������� ��� �����A�.(/�����E3-����������������

5�5�

5�5�

��

�*%�

5�

Page 199: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

���������������� ���

���� ' $������E3-���������� ��� �� ����������� ������������

�������� �������

0 1 S0 S0,S1 S1

S1* S0,S1

� �

�*�%%%%%5�

%%%%%5�

������� ���� ������� 3-� �� �� ���@��� � .����� �������������� �����/��� �� �E3-�������'

!' ?������ �������� �' �� ���E3-

%%%%%5� %%%%%5�

%%�

�*�

%%%%%5� %%%%%5� %%%%%5�

�*�

%%%%%5� %%%%%5�

%%%%%5�%%%%%5�%%%%%5�

�� �

�' ?������ �������� �' �� ���E3-

6' %� ���� �A�.(/������E3-���������������� ���������������3-��� ��� �����A�.(/���������'

Page 200: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

>' ������� � �� �� � �������E3-� �� �� �� ������ �� �� � ������ ��� ������� ������ � ������� � �������� �� ���<� ���� <����

� �

5� φ 5�*%5�

5� 5� 5�*%5�

5� 5� φ

� �

5� φ 5�

5� 5�*%5� 5�

5� φ 5�*%5�*%5�

5� φ φ

� � �

5� 5� φ φ

5� 5� 5� 5�*%5�

5� 5�*%5�*%5� 5� 5�

� � �

5� 5� 5�*%5�*%5� φ

5� 5�*%5� φ φ5� φ 5�*%5� 5�*%5�

5� φ φ 5�

�' %� ���� �A.(/��������� �� )���� ��E3-� � ���� ����E�'>�������� ����������������3-��� ��� �����A.(/�����E3-� ��������'

�' %������ �E3-� ���� ����� ���� 6� � ������� �� �����<� ���� <������� ������������'

,' 0�������3-�� ����� �� ��� ���������� I@�������J� �����&��'

+' 0�������3-�� ����� �� ��� ��� ��<���������8��&��*1������G�%������$� ��$�!���� �������� ��'

Page 201: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

���������������� ���

����) ��������� ��$��*��$

$��������������������������������������������������������3-� �� ���� ���������� ������� ����� ������ ����� ���� ��������� ���� �� �� ������� � ��� ���������3-������ �������*�&)&����� ����� �������*����&���'� ����� ������ � 3-� �� ������� <���� �������� � ������ � ������ ������ �� ������������� �� ���������������� ��� �� ����� ������� ��������������� ����������������������������������� ����� '�$�����3-������������<���������� ������������<� ��������������� �)������� 3-� �� �� ������ � �������� � 3� ���� ��� ��&��� �����3-�� �� � �����'

3� ���� ������ ��� ��������������������� ��� �� �

� ������� ������ �����

������� ��������� ������������������ ������� ���������� ��

(������ ��������<� ������� ���&������ �� ��� ������� �������������������������� ����� �������� ���

��#�������$ ��#������ ����������� ��������������

���� ��� <� ���� ��� ���&��� ��������� ��� �� ������ I J� ����������� ���I J����������������� �������� ������������������������� �� �����������������

5� 5�

�3��

5�

�3���3��

�3�

�3�

�3�5)�+)

Page 202: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

8�������� ������� ��� ����� ���

$�����$�������� ��� ������� ��� � ����� ��������$�

$!������� ��� ������� ��� � ����� ��������$�

$!������� ���"������� ���"����� ��������$�

$ ������� ��� ������� ��� � ����� ��������$�

����� ���� �� � �"� ����������� �3-� ���������������� ������ � � � �"� � '

������� ��������� ������������������ ������� ������������

$������ ����� �� �� �������� �3-��� �� � ������� �������� � <� ���� ������ ��� ���&��� �� �� � ������ �� ��������� � �������� ������� ����� <� ���� ��� ����� �� �� ����<� ���� ������ ��� ���&��� <� ���� ��� ����� �������� �� �� ������� �� ������� �������'

%%%� %%%�

5� 5�*%� 5�*%��5�

5�*%� 5�*%��5�

5�*%� 5�*%��

���� ' 0������� ������� <� ���� ������ ��� ���&��� �� ��� )

��� ������� ����� �� �"� �"�"� � �� ��������� �� �"�"� �""�"�"� � �������� �������������� ������������

!' 0������� ������� <� ���� ������&��� �� ������)������ � ������������ � ������ ����� ��������� �� � ������>�. �"� /��� ���. � � /'

8�������� "� �"� "� � � �= � �"�"

Page 203: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

���������������� ���

��������� � �� ���� � ������ ������ � ��� �� �� �������� ������� � ��� ������ ���"��� ���������� ����������"� ����� �"��� ������ ���"��� ���������� ���������� � �� � ����� ��� �� � ��� ��������� ������� "� "� �� ����� ��� '

����� <� ���� ��� ���&�� ��� ����� ��������� ��� �� ������� �������� �������'

$����� $�������� ��� ��������"����� ��������$ $�������� ���" ��������"����� ��������$

$�������� ��� ������� ����� ��������$

$�������� ���""������� ����� ��������$"

����� ������ ������ ����� ������ � ������ � ��������������� ""

!�'�?������ ��� �� �&������ ������� ����,�=�+�����=�>���� ��=,

�' 0������� ������� <� ���� ��� ���&��� �� ������)������ � ������������ � ���� �� �������������� �� � �������%���&'��(���)������&�*�+

6' 0������� ������� <� ���� ������ ��� ���&��� �� ����� ��� ������ ���� �� � ��������� !� .�� ���/�� �������� �� ����������6'

)��"��)

%%%%%5�%%%%%5�

��3�

5)�+)

��3���3� ��3�

��*%��3���*%��3�

Page 204: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

�� ������������������

Page 205: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������������������ ���

3������K������������%�����0�������� �O�������������5���P�����������2�����!�!"">'

�� ��� �������H�&�������������������������'�8�� ��&��4����5 ��E�����������!"" '

?�� ������������� �%� ��-'�3����������������������������������������������8�� ��&��4����5 ���E����������� ++,'

?�� ������������K���4'�$��1������� �0��P�� ��������������������8�� ��&��4����5 ��� ++�'

$���?����������4����8�� ����-�������A������3�CC��������5���P�����������!""6'

$��� ���2������ �������������������5����P�����������!""�'

7�������$���� �-'���������� ������������ �� ������� ��������'(&������4����5 ���$� ������� +,�'

)��"��)

���� ���������� ���������� ���������� ���������� ������

Page 206: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������

Page 207: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

������������������ ���

�� ��� ��������� ��������� �� ������ �������� � � � ��� ��� ��� $��������'� 0������ � ��������� � ������ � ��� -������(����������� �� ����<������ �������������������������� �3������3��������(58-�K �@��������5 �� �)����� �� � � ��������� � 8������ 8��&�)$���� �� ���� �O��������� ������ �-�������A����� ���� � ++��� ���K �@����)���� 5 �� ����'

$��������� � +,���������� ���������0��� �(������������ � ���<������ �� � ��������� �������� ���� � ��� 8��������(������������� ����<�����'�0������������ ��������������(����������������� ������ ���� � ++����� ���������� �@�������� ����� ��� �K �@��������0� ��E��� ����� ���������K �@�������5 �� ����� 2���K ����� ��������� K �@�������� ?����� �?����7�&� ���-(5?�0?��%� ���� �'

�����������������������������������������������������������������

Page 208: MATEMATIKA DISKRIT - onemat.files.wordpress.com · 7ˇ.ˇ7 ’

��� ������������������


Top Related