1.2.5. Решавање проблеми од множества

За да ги погледнете задачите за вежбање притиснете тука.

1.2.4 Закони за операции со множества

За секој закон од математичката логика кореспондира по еден закон од теоријата на множества. Во продолжение ќе бидат дадени основните утврдени закони за множества:


Комутативни закон:

• за унијата    А∪В=В∪А
• за пресекот А∩В=В∩А

Асоцијативни закон:

• за унијата    А∪(В∪С)=(А∪В)∪С
• за пресекот А∩(В∩С)=(А∩В)∩С

Дистрибутивни закони:

• за унијата    А∩(В∪С)=(А∩В)∪(А∩С)
• за пресекот А∪(В∩С)=(А∪В)∩(А∪С)

Закони за идентитет

• за унијата     А∪∅=∅∪А=А
• за пресекот   А∩U=U∩А=А

Закони за комплементност

• за унијата    А∪А^c=U
• за пресекот А∩А^c=∅

Закони за идемпотентност

• за унијата    А∪А=А
• за пресекот  А∩А=А

Закони за абсорпција:

• А∪(А∩В)=А
• А∩(А∪В)=А

Закони на Де Морган:

• (А∪В)^c=А^c∩B^c    
• (А∩В)^c=А^c∪B^c

1.2.3 Дефинирање на операции со множества со помош на логички операции

Во овој дел ќе се задржиме да ги објасниме операциите:

• комплемент на множества
• пресен на множества
• унија на множества
• разлика множества

Овие операции нам ни се познати од основно образование, разликата е тоа што сега ќе ги објаснуваме со помош на логичките операции ¬, ∧, ∨ .
1. Нека А е множество, дефинираме:

A^c={x | x ∉ A}

На овој начин дефиниравме комплемент на множеството А со помош на логичката операција негација.

2. Нека ни се дадени две множества А и В дефинираме

А∩В={x|x∈А ∧ x∈В}

На овој начин ја дефинираме операцијата пресек на две множества со помош на логичката операција конјункција. 

3. Нека ни се дадени две множества А и В дефинираме

А∪В={x|x∈А ⋁ x∈В}

На овој начин ја дефинираме операцијата унијa на две множества со помош на логичката операција дисјункција. 

4. Нека ни се дадени две множества А и В дефинираме

А\В={x|x∈А ∧ x∉В}

На овој начин ја дефинираме операцијата разлика на две множества со помош на логичките операции конјункција и негација. 

1.2.2. Начини на задавање на множество

Кога го објаснувавме поимот множество рековме дека, доколку  се членови на множеството A кое е конечно или преброиво бесконечно, тогаш математички тоа се запишува на следниов начин:

Овој начин на задавање на множествата го нарекуваме табеларен начин.

Пример:
А={1,2,3,4,5}
Ако пак едно множество може да се опише ако се искористи и некое својство P(x) кое го исполнуваат сите елементи на тоа множество. Математички тоа се запишува вака:

Пример:

А={x|x∊N ⋀ 3<x<10}

Овој начин на задавање на множествата го нарекуваме описен начин.

Третиот начин на задавање на множеството е со Венов дијаграм како што е прикажано на следната слика.

Веновиот дијаграм се користи за прикажување / визуелизација на можните односи меѓу членовите на множествата. Инаку името на дијаграмот е добиено од името на Англискиот математичар, логичар и филозов John Venn,(4 August 1834 – 4 April 1923).

1.2.1 Поим за множество, подмножество и примери

Множеството претставува збир на предмети кои се нарекуваат елементи на даденото множество. Множеството кое не содржи ниту еден елемент се нарекува празно множество и се означува со ∅. Понекогаш, поимите множество, елемент и припадност кон дадено множество, се прифаќаат како основни, интуитивно јасни и не се дефинираат. Доколку  се членови на множеството A кое е конечно или преброиво бесконечно, тогаш математички тоа се запишува на следниов начин:

${\displaystyle A=\{x_{1},x_{2},\ldots ,x_{n}\}}$

Едно множество може да се опише ако се искористи и некое својство P(x) кое го исполнуваат сите елементи на тоа множество. Математички тоа се запишува вака:

${\displaystyle A=\{x\mid P(x)\}}$

Ако некој елемент ${\displaystyle x}$ му припаѓа на множеството A, тогаш тоа се означува со ${\displaystyle x\in A}$, а доколку ${\displaystyle x}$ не е елемент на множеството A тоа се запишува ${\displaystyle x\notin A}$. За две множества A и B велиме дека се еднакви ако и само ако секој елемент на множеството А е елемент и на множеството B или ако и двете множества се празни:

Во математиката од посебна важност се, множествата кои се составени од „математички објекти“ - точки, броеви, итн. Множествата, чии елементи се броеви се викаат бројни множества. Во продолжение ќе дадаеме некои од тие множества:

• множеството на природни броеви кое го означуваме со 𝐍.
• множеството на цели броеви кое го означуваме со 𝐙
• множеството на рационалните броеви кое го означуваме со 𝐐
• множеството на реалните броеви кое го означуваме со 𝐑

Во математиката, особено во делот од математиката наречен теоријата на множествата, множество A е подмножество на множество B ако A „се содржи“ во B. A и B може да се совпаѓаат. Ваквата релација се нарекува содржајна релација или инклузија. Така, множестово B е надмножество на A бидејќи сите елементи на A се воедно и елементи на B.

Дефиниција: Едно множество А велиме дека е подмножество на друго множество В, ако и само ако секој елемент на множеството А е елемент и на В.

Во иднина ќе ги разликуваме поимите: 

• подмножество (ќе го бележиме со „⊆“) Две множества се еднакви ако и само ако секое од нив е подмножество на другото
• вистинско подмножество (ќе го бележиме со „⊂“ и ќе значи А⊂в ⇔ (А⊆В и А≠В)

Примери за множества: 

• Напиши го множеството од месеци во годината.
• Напиши го множеството пролетни месеци во годината.
• Напиши го множеството месеци во годината кои во името ја содржат буквата р.

1.1.4. Решавање на проблеми од математичка логика

Задачи за домашна работа и вежбање можете да земете тука

1.1.3. Сложен исказ (тафтологија)

Забележуваме дека структурата на сложениот исказ     ..(p⇒q)∧(p⇒q).....  e изразена во вид на една конечна низа од буквите p и q и некои од знаците за операции и одреден број на загради, со кои се утврдува редоследот на извршувањето на операциите во него. Секоја таква конечна низа состевана „на дозволен начин“ се вика исказна формула.

Буквите p,q,r,… покрај тоа што означуваат некои појдовни искази, тие играат улога и на променливи – исказни променлови, бидејќи наместо нив во исказните формули можат да се постават произволни искази. Исказните променливи во исказните формули можат да примаат само две вредности:  Т, ⊥. Според тоа, областа на менување на вредностите на вистинитост на исказните променливи во исказите и исказните формули е множеството  {Т, ⊥}.

Знаците Т и ⊥ кои ни означуваат „вистинит исказ“ и „лажен исказ“ се исто симболи за искази, но за искази со постојана вредностна вистинитост, па затоа уште ги викаме и исказни константи.

Во зависност од крајната вредност што ја добиваме за сложениот исказ, разликуваме три вида исказни формули:

1.       Исказната формула Ф, за која за секој можен избор на вредности на нејзините променливи важи , се вика идентично вистинита формула или тафтологија.

2.       Исказната формула Ф, за која за секој можен избор на вредности на нејзините променливи важи ⊥, се вика идентично невистинита формула или контрадикција.

3.       Ако пак дадена исказна формула Ф, за некои избори на вредност на исказните променливи добива вредност на вистинитост Т, а за други избори – добива вредност ⊥, тогаш таа се вика неутрална исказна формула.

За нас од посебно значење се исказните формули од првиот вид  тафтологија.

Нека имаме две исказни формули А и В и нека вредностите на вистинитост на овие две формули се исти. Тоа значи, за секој можен исбор на вредности на исказните променливи во нив важи . За такви две исказни формули велиме дека се истовредносни и се викаат еквивалентни исказни формули. Еквивалентноста на исказните формули ќе ја запишуваме со знакот „ “.

Листа на тафтологии

1. ⅂⅂p ∼ p                                   Закон за двојна негација
2. p∨⅂p                                 Закон за исклучено трето
3. ⅂(p∨⅂p)                            Закон за непротивречност
4. p∧q ∼ q∧p                       Комутативен закон за конјункција
5. p∨q ∼ q∨p                       Комутативен закон за дисјункција
6. p⇔q ∼ q⇔p                    Комутативен закон за еквиваленција
7. (p∧q)∧r ∼ p∧(q∧r)         Асоцијативен закон за конјункција
8. (p∨q)∨r ∼ p∨(q∨r)         Асоцијативен закон за дисјункција
9. p∧(q∨r) ∼ (p∧q)∨(p∧r) Дистрибутивен закон на конјункција во однос на дисјункција
10. p∨(q∧r) ∼ (p∨q)∧(p∨r) Дистрибутивен закон на дисјункција во однос на конјункција
11. ⅂(p∧q) ∼ ⅂p∨⅂q                Закони на Де Морган
12. ⅂(p∨q) ∼ ⅂p∧⅂q                 Закони на Де Морган
13. p⇨q ∼ ⅂q⇨⅂p                      Закон за контрапозиција

Покрај овие логички закони, постојат и други логички закони кои често се употребуваат, и тие се следниве:

1. p∧p ∼ p
2. p∨p ∼ p         
3. p∧(p∨q) ∼ p 
4. p∨(p∧q) ∼ p
5.  (p⇔q)∼((p⇒q)∧(q⇒p))
6. (p⇒q)∼ ⅂p∨q
7. p∧⊤ ∼ p
8. p∧⊥ ∼ ⊥
9. p∨⊤ ∼ ⊤
10. p∨⊥ ∼ p
11. p⇒⊤∼ ⊤
12. ⊥⇒p∼ ⊤

Задачи:

Користејќи ги вистинитосните таблици, докажи дека следниве формули за тафтологии.

1. p⇨(q⇨p)
2. p⇨(p∨q)
3. (p∧(p⇨q))⇨q
4. (p⇨q)∨(q⇨p)
5. ⅂(⅂p∧q)⟺p∨⅂q
6. ⅂(⅂p∨q)⇔p∧⅂q
7. ((p⇒q)∧(q⇒r))⇒(⅂p∨r)
8. ((p⇒(q⇒r))⇔((p∧q)⇒r)
9. ((p⇒r)∧(q⇒r))⇔((p∨q)⇒r)

Решение:

1)

p	q	(q⇨p)	p⇨(q⇨p)
⊤	⊤	⊤	⊤
⊤	⊥	⊤	⊤
⊥	⊤	⊥	⊤
⊥	⊥	⊤	⊤

2)

p	q	(p∨q)	p⇨(p∨q)
⊤	⊤	⊤	⊤
⊤	⊥	⊤	⊤
⊥	⊤	⊤	⊤
⊥	⊥	⊥	⊤

3)

p	q	(p⇨q)	p∧(p⇨q)	(p∧(p⇨q))⇨q
⊤	⊤	⊤	⊤	⊤
⊤	⊥	⊥	⊥	⊤
⊥	⊤	⊤	⊥	⊤
⊥	⊥	⊤	⊥	⊤

4)

p	q	(p⇨q)	(q⇨p)	(p⇨q) ∨(q⇨p)
⊤	⊤	⊤	⊤	⊤
⊤	⊥	⊥	⊤	⊤
⊥	⊤	⊤	⊥	⊤
⊥	⊥	⊤	⊤	⊤

6)

p	q	r	⅂p	(p⇨q)	(q⇒r)	((p⇒q)∧ (q⇒r))	⅂p∨r	((p⇒q)∧ (q⇒r))⇒ ( ⅂p ∨r)
⊤	⊤	⊤	⊥	⊤	⊤	⊤	⊤	⊤
⊤	⊤	⊥	⊥	⊤	⊥	⊥	⊥	⊤
⊤	⊥	⊤	⊥	⊥	⊤	⊥	⊤	⊤
⊤	⊥	⊥	⊥	⊥	⊤	⊥	⊥	⊤
⊥	⊤	⊤	⊤	⊤	⊤	⊤	⊤	⊤
⊥	⊤	⊥	⊤	⊤	⊥	⊥	⊤	⊤
⊥	⊥	⊤	⊤	⊤	⊤	⊤	⊤	⊤
⊥	⊥	⊥	⊤	⊤	⊤	⊤	⊤	⊤