Математичка логика

Исказ или суд је афирмативна (потврдна) реченица која има смисла и која је или тачна или нетачна. $\top \top$

Исказе означавамо словима $p$ , $q$ , $r$ ...

Тачном исказу се придружује истинитосна $\top$ вредност (те), а нетачном истинитосна вредност $\bot$ (не-те).

Основне логичке операције

операција	симбол	нови исказ
конјункција (и)	$\wedge$	$p \wedge q$ ( $p$ и $q$ )
дисјункција (или)	$\vee$	$p \vee q$ ( $p$ или $q$ )
импликација (ако ... онда)	$\Rightarrow$	$p \Rightarrow q$ (ако $p$ онда $q$ )
еквиваленција(ако и само ако)	$\Leftrightarrow$	$p \Leftrightarrow q$ ( $p$ ако и само ако $q$ )
негација (не)	$\neg$	$\neg p$ (не $p$ )
дисјункција (или – или)	$\underline \vee$	$p \underline \vee q$ ( $p$ или $q$ , али не оба)

Таблице истинитости

$p$	$q$	$p \wedge q$	$p \vee q$	$p \Rightarrow q$	$p \Leftrightarrow q$	$p \underline \vee q$
$\top$	$\top$	$\top$	$\top$	$\top$	$\top$	$\bot$
$\top$	$\bot$	$\bot$	$\top$	$\bot$	$\bot$	$\top$
$\bot$	$\top$	$\top$	$\top$	$\top$	$\bot$	$\top$
$\bot$	$\bot$	$\bot$	$\bot$	$\top$	$\top$	$\bot$

$p$	$\neg p$
$\top$	$\bot$
$\bot$	$\top$

Исказне формуле

Исказне формуле су

Исказна слова $p$ , $q$ , $r$ ...
Ако су $A$ и $B$ исказне формуле, онда су и $A \vee B$ , $A \wedge B$ , $A \Rightarrow B$ , $A \Leftrightarrow B$ , $\neg A$ исказне формуле.
Исказне формуле се могу добити само помоћу коначног броја примена 1 и 2.

За образовање сложених исказа, поред логичних операција, користе се и заграде, којима се истиче приоритет операције.

Таутологије

Исказне формуле које имају истинитосну вредност $\top$ за ма које вредности исказних слова зову се таутологије.

Таутологијама се називају особине логичких операција и логички закони.

Важније особине логичких операција

Комутативност конјункције, дисјункције и еквиваленције
$p \wedge q \Leftrightarrow q \wedge p$ ,
$p \vee q \Leftrightarrow q \vee p$ ,
$(p \Leftrightarrow q) \Leftrightarrow (q \Leftrightarrow p)$
Асоцијативност конјункције, дисјункције и еквиваленције
$(p \wedge q) \wedge r \Leftrightarrow p \wedge (q \vee r)$ ,
$(p \vee q) \vee r \Leftrightarrow p \vee (q \vee r)$ ,
$(p \Leftrightarrow q) \vee r \Leftrightarrow p \Leftrightarrow (q \Leftrightarrow r)$ .
Идемпотентност конјункције, дисјункције
$p \wedge p \Leftrightarrow p$ ,
$p \vee p \Leftrightarrow p$ .
Дистрибутивност конјукције према динсјункцији и обрнуто
$p \wedge (q \vee r) \Leftrightarrow (p \wedge q) \vee (p \wedge r)$ ,
$p \vee (q \wedge r) \Leftrightarrow (p \vee q) \wedge (p \vee r)$ .
Апосорптивност конјукције према динсјункцији и обрнуто
$p \wedge (q \vee q) \Leftrightarrow p$ ,
$p \vee (q \wedge q) \Leftrightarrow p$ .
Инволутивност негације
$\neg (\neg p) \Leftrightarrow p$ .
Неутрални елемент за конјункцију и дин

Исказ је реченица која је или тачна ( $\top$ ) или нетачна ( $\bot$ ). Од исказа $p$ и $q$ логичким операцијама граде се нови: конјункција $p \wedge q$ тачна је само кад су оба тачна, дисјункција $p \vee q$ нетачна је само кад су оба нетачна, импликација $p \Rightarrow q$ нетачна је само кад је $p$ тачно, а $q$ нетачно, еквиваленција $p \Leftrightarrow q$ тачна је кад $p$ и $q$ имају исту вредност, а негација $\neg p$ мења вредност.

Таблица истинитости са $n$ исказних слова има $2^n$ врста. Формула тачна у свакој врсти је таутологија, на пример $p \vee \neg p$ или $(p \Rightarrow q) \Leftrightarrow (\neg q \Rightarrow \neg p)$ . Најчешћа грешка: импликација са нетачном претпоставком је тачна, шта год да је последица.

Таблица истинитости: (p ⇒ q) ⇔ (¬q ⇒ ¬p)
p	q	¬p	¬q	Ap⇒q	B¬q⇒¬p	FA⇔B
тачно	тачно	нетачно	нетачно	тачно	тачно	тачно
тачно	нетачно	нетачно	тачно	нетачно	нетачно	тачно
нетачно	тачно	тачно	нетачно	тачно	тачно	тачно
нетачно	нетачно	тачно	тачно	тачно	тачно	тачно

Формула је таутологија: тачна је у свакој врсти.

Импликација

p \Rightarrow q

нетачна је само за

p = \top

q = \bot

, а

\neg q \Rightarrow \neg p

има у свакој врсти исту вредност, па је њихова еквиваленција таутологија. Обрнута импликација

q \Rightarrow p

разликује се од

p \Rightarrow q

у две врсте.

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

Обећање тренера

Тренер кошаркашког клуба у Чачку рекао је играчима: „Ако у суботу победимо, у недељу нема тренинга.“ У којим случајевима је тренер прекршио обећање? Ако знате да је тренинг у недељу одржан, а да је обећање испуњено, шта можете да закључите о суботњој утакмици?

Решење

Нека је $p$ исказ „у суботу смо победили“, а $q$ исказ „у недељу нема тренинга“. Обећање је импликација $p \Rightarrow q$ .
Импликација је нетачна само за $p = \top$ и $q = \bot$ : обећање је прекршено једино ако су победили, а тренинг је ипак одржан.
Ако су изгубили, $p = \bot$ , па је $p \Rightarrow q$ тачно и кад тренинга има и кад га нема: за пораз тренер ништа није обећао.
Таблицом проверавамо да је $(p \Rightarrow q) \Leftrightarrow (\neg q \Rightarrow \neg p)$ таутологија: за $(p, q) = (\top, \top), (\top, \bot), (\bot, \top), (\bot, \bot)$ обе стране имају вредности $\top, \bot, \top, \top$ .
Тренинг је одржан, дакле тачно је $\neg q$ . Из тачне импликације $\neg q \Rightarrow \neg p$ следи $\neg p$ .

Одговор: Обећање је прекршено само ако су победили, а тренинг је одржан; ако је тренинг одржан, а обећање испуњено, утакмица у суботу није добијена.

Задатак за вежбу

Покажите таблицом истинитости да је $\neg(p \wedge q) \Leftrightarrow (\neg p \vee \neg q)$ таутологија (Де Морганов закон).

Прикажи решење

За $(p, q) = (\top, \top), (\top, \bot), (\bot, \top), (\bot, \bot)$ лева страна има вредности $\bot, \top, \top, \top$ , а десна такође $\bot, \top, \top, \top$ . Стране су увек једнаке, па је еквиваленција тачна у свакој врсти: то је таутологија.

Математичка логика

Укратко

Изаберите формулу и пратите последњу колону

Пример из живота

Обећање тренера

Решење

Задатак за вежбу