Најважније из лекције
- Исказне формуле настају повезивањем исказних слова и константи помоћу логичких операција (\( \neg, \lor, \land, \Rightarrow, \Leftrightarrow \)).
- Приоритет операција: Негација (\( \neg \)) се прва извршава, затим \( \lor \) и \( \land \), а на крају \( \Rightarrow \) и \( \Leftrightarrow \).
- Таутологија је формула чија је истинитосна вредност увек тачна (\( \top \)), без обзира на вредности појединачних исказних слова.
- Доказивање таутологија се може вршити исписивањем свих \( 2^n \) комбинација у истинитосној таблици или помоћу методе свођења на апсурд (претпоставком да је формула нетачна, што доводи до логичке контрадикције).
Исказне формуле су логички изрази којима се описују структуре (облици) исказа.
Исказне формуле се граде од:
- исказних слова: \( a, b, c, \dots, p, q, r, \dots \)
- логичких константи: \( \top \) (тачно) и \( \perp \) (нетачно)
- логичких операција: \( \lor, \land, \neg, \Rightarrow, \Leftrightarrow \)
Приоритет логичких везника:
Приликом записивања исказних формула без заграда, примењује се следећи редослед извршавања операција:
- \( \neg \) (негација) – највећи приоритет
- \( \lor \) (дисјункција) и \( \land \) (конјункција) – подједнак приоритет
- \( \Rightarrow \) (импликација) и \( \Leftrightarrow \) (еквиваленција) – најмањи приоритет, међусобно подједнаки
Истинитосна вредност формуле у којој се појављују исказна слова зависи од истинитосних вредности које су додељене тим словима. Приказује се помоћу истинитосне таблице.
Број редова у таблици (могућих комбинација истинитосних вредности) израчунава се формулом:
\[ 2^n \]
где је \( n \) број различитих исказних слова у формули. (нпр. за 2 слова постоје 4 комбинације, за 3 слова постоји 8 комбинација).
Пример формирања истинитосне таблице за формулу \( \neg(p \Rightarrow q) \land p \):
\[
\begin{array}{|c|c|c|c|c|}
\hline
p & q & p \Rightarrow q & \neg(p \Rightarrow q) & \neg(p \Rightarrow q) \land p \\ \hline
\top & \top & \top & \perp & \perp \\ \hline
\top & \perp & \perp & \top & \top \\ \hline
\perp & \top & \top & \perp & \perp \\ \hline
\perp & \perp & \top & \perp & \perp \\ \hline
\end{array}
\]
Таутологија је исказна формула која је увек тачна (\( \top \)), за било које истинитосне вредности исказних слова која се у њој појављују.
Формула \( \neg(p \lor q) \Leftrightarrow \neg p \land \neg q \) је таутологија, што се види из њене истинитосне таблице јер су у последњој колони све вредности \( \top \):
\[
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
p & q & p \lor q & \neg(p \lor q) & \neg p & \neg q & \neg p \land \neg q & \neg(p \lor q) \Leftrightarrow \neg p \land \neg q \\ \hline
\top & \top & \top & \perp & \perp & \perp & \perp & \top \\ \hline
\top & \perp & \top & \perp & \perp & \top & \perp & \top \\ \hline
\perp & \top & \top & \perp & \top & \perp & \perp & \top \\ \hline
\perp & \perp & \perp & \top & \top & \top & \top & \top \\ \hline
\end{array}
\]
Када формула има много исказних слова, цртање таблице је заморно. Зато се за доказивање таутологија користи метода свођења на апсурд.
Претпоставимо да дата формула није таутологија, односно да је њена истинитосна вредност нетачна (\( \perp \)).
На основу те претпоставке, анализирамо истинитосне вредности њених подформула користећи позната правила за логичке операције.
Долазимо до контрадикције (апсурда) – ситуације у којој једна иста формула или слово истовремено има вредности и \( \top \) и \( \perp \).
Закључујемо да је почетна претпоставка погрешна, те да формула јесте таутологија.
Доказ да је формула \( p \land (p \Rightarrow q) \Rightarrow q \) таутологија:
1. Претпоставимо да је вредност целе формуле \( \perp \).
2. Да би импликација била \( \perp \), мора бити \( \tau(p \land (p \Rightarrow q)) = \top \) и \( \tau(q) = \perp \).
3. Из \( \tau(p \land (p \Rightarrow q)) = \top \) следи да је \( \tau(p) = \top \) и \( \tau(p \Rightarrow q) = \top \).
4. Међутим, ако је \( \tau(p) = \top \) и \( \tau(q) = \perp \), тада би морало бити \( \tau(p \Rightarrow q) = \perp \).
5. Добили смо апсурд: \( \tau(p \Rightarrow q) \) је истовремено и \( \top \) и \( \perp \). Закључујемо да је формула таутологија.
1. Претпоставимо да је вредност целе формуле \( \perp \).
2. Да би импликација била \( \perp \), мора бити \( \tau(p \land (p \Rightarrow q)) = \top \) и \( \tau(q) = \perp \).
3. Из \( \tau(p \land (p \Rightarrow q)) = \top \) следи да је \( \tau(p) = \top \) и \( \tau(p \Rightarrow q) = \top \).
4. Међутим, ако је \( \tau(p) = \top \) и \( \tau(q) = \perp \), тада би морало бити \( \tau(p \Rightarrow q) = \perp \).
5. Добили смо апсурд: \( \tau(p \Rightarrow q) \) је истовремено и \( \top \) и \( \perp \). Закључујемо да је формула таутологија.
Задаци за вежбање
Лакши задатак: Колико редова има истинитосна таблица за исказну формулу у којој се појављују три исказна слова (\( p, q, r \))?
Број редова израчунава се по формули \( 2^n \), где је \( n \) број исказних слова.
\( 2^3 = 2 \cdot 2 \cdot 2 = 8 \)
Одговор: Истинитосна таблица ће имати 8 редова.
\( 2^3 = 2 \cdot 2 \cdot 2 = 8 \)
Одговор: Истинитосна таблица ће имати 8 редова.
Средњи задатак: Конструкцијом истинитосне таблице провери да ли је формула \( p \lor \neg p \) таутологија.
Формула има само једно исказно слово, па таблица има \( 2^1 = 2 \) реда.
\[
\begin{array}{|c|c|c|}
\hline
p & \neg p & p \lor \neg p \\ \hline
\top & \perp & \top \\ \hline
\perp & \top & \top \\ \hline
\end{array}
\]
Одговор: Пошто су све вредности у последњој колони \( \top \), дата формула јесте таутологија.
Тежи задатак: Методом свођења на апсурд докажи да је формула \( p \Rightarrow (p \lor q) \) таутологија.
1. Претпоставимо супротно: нека дата формула није таутологија, тј. \( \tau(p \Rightarrow (p \lor q)) = \perp \).
2. Да би импликација била нетачна, мора да важи: \( \tau(p) = \top \) и \( \tau(p \lor q) = \perp \).
3. Из \( \tau(p \lor q) = \perp \) (дисјункција је нетачна само ако су оба исказа нетачна) следи да је \( \tau(p) = \perp \) и \( \tau(q) = \perp \).
4. Овим смо добили апсурд: у кораку 2 смо добили \( \tau(p) = \top \), а у кораку 3 смо добили \( \tau(p) = \perp \). Ово није могуће.
Одговор: Због добијене контрадикције, закључујемо да претпоставка није тачна и да формула јесте таутологија.
2. Да би импликација била нетачна, мора да важи: \( \tau(p) = \top \) и \( \tau(p \lor q) = \perp \).
3. Из \( \tau(p \lor q) = \perp \) (дисјункција је нетачна само ако су оба исказа нетачна) следи да је \( \tau(p) = \perp \) и \( \tau(q) = \perp \).
4. Овим смо добили апсурд: у кораку 2 смо добили \( \tau(p) = \top \), а у кораку 3 смо добили \( \tau(p) = \perp \). Ово није могуће.
Одговор: Због добијене контрадикције, закључујемо да претпоставка није тачна и да формула јесте таутологија.
