Најважније из лекције
- Квантификатори се користе за прецизно изражавање тврђења: \( \forall \) (сваки) и \( \exists \) (постоји/неки).
- Ограничени квантификатори (\( \forall x \in A \) и \( \exists x \in A \)) везују променљиву за одређени скуп вредности.
- Де Морганови закони омогућавају негирање квантификатора: негација „сваки” даје „постоји неки који не”, док негација „постоји” даје „за сваког није”.
- Логичко закључивање се може представити језиком скупова и Веновим дијаграмима како би се проверила формална исправност закључка.
Квантификатори, заједно са логичким везницима, служе за прецизно формулисање тврђења, посебно када се ради са бесконачним скуповима. Постоје два основна квантификатора.
Универзални квантификатор (\( \forall \)) – чита се као „сваки”, „било који” или „произвољан”.
Егзистенцијални квантификатор (\( \exists \)) – чита се као „постоји”, „неки” или „бар један”.
Ако релација \( V(x, y) \) значи „\( x \) воли \( y \)”:
- Свако воли некога: \( (\forall x)(\exists y) V(x, y) \)
- Неко воли свакога: \( (\exists x)(\forall y) V(x, y) \)
Како бисте математичким симболима записали реченицу: „Неко не воли никога”?
Одговор: \( (\exists x)(\forall y) \neg V(x, y) \)
Објашњење: „Постоји особа \( x \)” (\( \exists x \)), таква да „за сваку особу \( y \)” (\( \forall y \)) важи да „\( x \) не воли \( y \)” (\( \neg V(x, y) \)).
Објашњење: „Постоји особа \( x \)” (\( \exists x \)), таква да „за сваку особу \( y \)” (\( \forall y \)) важи да „\( x \) не воли \( y \)” (\( \neg V(x, y) \)).
Иза квантификатора обавезно следи променљива која узима вредности из унапред задатог скупа. Када се тај скуп истиче у формули, користимо ограничене квантификаторе.
\( \forall x \in A \) – „за сваки елемент \( x \) скупа \( A \)”
\( \exists x \in A \) – „постоји елемент \( x \) скупа \( A \)”
Ограничени квантификатори се могу елиминисати следећим еквиваленцијама (где је \( F \) произвољна формула):
\[ (\forall x \in A)F \Leftrightarrow \forall x(x \in A \Rightarrow F) \]
\[ (\exists x \in A)F \Leftrightarrow \exists x(x \in A \land F) \]
Збир било ког природног броја и нуле једнак је том броју:
\[ (\forall x \in \mathbb{N})(x + 0 = x) \]
Једначина \( x^2 - 6x + 5 = 0 \) има решења у скупу целих бројева:
\[ (\exists x \in \mathbb{Z})(x^2 - 6x + 5 = 0) \]
Преведите реченицу на језик формула: „Једначина \( x^2 = 2 \) нема решења у скупу рационалних бројева.”
Одговор: \( \neg(\exists x \in \mathbb{Q})(x^2 = 2) \)
Де Морганови закони показују везу приликом негирања исказа са квантификаторима. Негацијом универзалног квантификатора добија се егзистенцијални (и обрнуто), уз негацију саме формуле.
\[ \neg(\forall x)F \Leftrightarrow (\exists x)\neg F \]
\[ \neg(\exists x)F \Leftrightarrow (\forall x)\neg F \]
Негација реченице „Свако воли некога” је „Неко не воли никога”:
\[ \neg(\forall x)(\exists y)V(x, y) \Leftrightarrow (\exists x)(\forall y)\neg V(x, y) \]
Примените Де Морганове законе на формулу: \( \neg(\exists x \in \mathbb{Q})(x^2 = 2) \). Како гласи еквивалентна тврдња?
Одговор: \( (\forall x \in \mathbb{Q})(x^2 \neq 2) \)
Чита се: „За сваки рационалан број \( x \), његов квадрат је различит од 2.”
Чита се: „За сваки рационалан број \( x \), његов квадрат је различит од 2.”
Основне особине скупова и логички закони су тесно повезани. Венови дијаграми се често користе за проверу логичке исправности закључивања на основу датих претпоставки (премиса). Приликом закључивања проверава се формална логичка исправност, а не нужно истинитост самих претпоставки.
Претпоставке:
Закључак: Неки професори су добри људи (\( P \cap D \neq \emptyset \)).
- Неки професори (\( P \)) су математичари (\( M \)). \( \Rightarrow P \cap M \neq \emptyset \)
- Сви математичари (\( M \)) су добри људи (\( D \)). \( \Rightarrow M \subseteq D \)
Задаци за вежбање
Лак: Запишите математичким симболима следећу реченицу користећи ограничене квантификаторе: „Квадрат сваког реалног броја је већи или једнак нули.”
Одговор: \( (\forall x \in \mathbb{R})(x^2 \ge 0) \)
Средњи: Користећи Де Морганове законе за квантификаторе, пронађите еквивалентан исказ за следећу формулу и преведите га на српски језик:
\[ \neg(\forall x \in \mathbb{R})(\exists y \in \mathbb{R})(x > y) \]
Одговор: Применом правила мењамо \( \forall \) у \( \exists \), и \( \exists \) у \( \forall \), а исказ негирамо (негација од \( x > y \) је \( x \le y \)):
\[ (\exists x \in \mathbb{R})(\forall y \in \mathbb{R})(x \le y) \]
Превод: „Постоји реалан број \( x \) који је мањи или једнак од сваког реалног броја \( y \).”
Тежак: Дате су следеће претпоставке:
- Неки паралелограми су квадрати.
- Сви квадрати имају једнаке дијагонале.
Решење:
Нека је \( P \) скуп паралелограма, \( K \) скуп квадрата и \( D \) скуп фигура са једнаким дијагоналама.
Закључак: Неки паралелограми имају једнаке дијагонале.
- Претпоставка 1: \( P \cap K \neq \emptyset \)
- Претпоставка 2: \( K \subseteq D \)
Закључак: Неки паралелограми имају једнаке дијагонале.
