Најважније из лекције
- Таутологије су увек тачне исказне формуле и основа су логичког закључивања.
- Modus ponens омогућава да из \( p \) и \( p \Rightarrow q \) закључимо \( q \).
- Modus tollens омогућава да из \( \neg q \) и \( p \Rightarrow q \) закључимо \( \neg p \).
- Контрапозиција мења места и негира исказе у импликацији: \( (p \Rightarrow q) \Leftrightarrow (\neg q \Rightarrow \neg p) \).
- Свођење на апсурд доказује \( p \) тако што покаже да претпоставка \( \neg p \) води у логичку контрадикцију.
- Транзитивност омогућава ланчано повезивање импликација (\( p \Rightarrow q \Rightarrow r \)) или еквиваленција (\( p \Leftrightarrow q \Leftrightarrow r \)).
Таутологије су исказне формуле којима се описују важни закони мишљења и које су увек тачне, без обзира на истинитост исказа од којих су састављене.
Закон искључења трећег
\[ p \lor \neg p \]
Сваки сложен исказ овог облика је увек тачан. На пример: Троугао ABC је правоугли или троугао ABC није правоугли.
Де Морганови закони
Ови закони описују негацију конјункције и дисјункције:
- \( \neg(p \land q) \Leftrightarrow \neg p \lor \neg q \)
- \( \neg(p \lor q) \Leftrightarrow \neg p \land \neg q \)
Ова два закона су најчешће коришћена правила за директно извођење закључака из датих претпоставки.
Modus ponens
\[ (p \land (p \Rightarrow q)) \Rightarrow q \]
Шема закључивања:
\[ \frac{p \quad p \Rightarrow q}{q} \]
Из претпоставки "Ана живи у Београду" (\(p\)) и "Ако Ана живи у Београду, онда Ана живи у Србији" (\(p \Rightarrow q\)), изводимо закључак "Ана живи у Србији" (\(q\)).
Modus tollens
\[ ((p \Rightarrow q) \land \neg q) \Rightarrow \neg p \]
Шема закључивања:
\[ \frac{p \Rightarrow q \quad \neg q}{\neg p} \]
Из импликације "Ако је четвороугао квадрат, онда се у њега може уписати круг" (\(p \Rightarrow q\)) и тврђења "У четвороугао се не може уписати круг" (\( \neg q \)), закључујемо "Четвороугао није квадрат" (\( \neg p \)).
Транзитивност импликације
\[ ((p \Rightarrow q) \land (q \Rightarrow r)) \Rightarrow (p \Rightarrow r) \]
Шема закључивања:
\[ \frac{p \Rightarrow q \quad q \Rightarrow r}{p \Rightarrow r} \]
Ако из \(p\) следи \(q\), а из \(q\) следи \(r\), онда директно из \(p\) следи \(r\).
Транзитивност еквиваленције
\[ ((p \Leftrightarrow q) \land (q \Leftrightarrow r)) \Rightarrow (p \Leftrightarrow r) \]
Шема закључивања:
\[ \frac{p \Leftrightarrow q \quad q \Leftrightarrow r}{p \Leftrightarrow r} \]
Ова таутологија омогућава формирање "ланца еквиваленција". Уколико су еквивалентне сваке две суседне формуле у ланцу, еквивалентне су и прва и последња.
Закони контрапозиције
\[ (\neg q \Rightarrow \neg p) \Leftrightarrow (p \Rightarrow q) \]
Уместо да доказујемо импликацију \( p \Rightarrow q \), често је лакше доказати њој еквивалентну импликацију \( \neg q \Rightarrow \neg p \).
Свођење на апсурд (reductio ad absurdum)
\[ (\neg p \Rightarrow (q \land \neg q)) \Rightarrow p \]
Ако из претпоставке \( \neg p \) следе нека два противречна тврђења (\( q \) и \( \neg q \)), онда наша претпоставка није тачна, те изводимо закључак \( p \).
Закон набрајања (доказ по случајевима)
\[ ((p \Rightarrow r) \land (q \Rightarrow r)) \Rightarrow ((p \lor q) \Rightarrow r) \]
Ако закључак \( r \) следи из претпоставке \( p \), а такође следи и из претпоставке \( q \), онда он сигурно следи из њихове дисјункције (\( p \lor q \)).
Задаци за вежбање
Лак: Користећи Де Морганове законе, запиши исказ који је еквивалентан негацији исказа \( \neg(A \land B) \).
Према Де Моргановом закону за негацију конјункције: \( \neg(A \land B) \Leftrightarrow \neg A \lor \neg B \).
Средњи: Дате су претпоставке:
1. "Ако пада киша, улице су мокре." (\( p \Rightarrow q \))
2. "Улице нису мокре." (\( \neg q \))
Који закључак можемо извући и које правило закључивања користимо?
Извлачимо закључак: "Не пада киша" (\( \neg p \)).
Правило које смо користили је Modus tollens: \( \frac{p \Rightarrow q \quad \neg q}{\neg p} \).
Тежак: Желимо да докажемо тврђење: "Ако је број \( n^2 \) паран, онда је и број \( n \) паран." (\( p \Rightarrow q \)). Како би гласио еквивалентан исказ који можемо да докажемо користећи закон контрапозиције?
Закон контрапозиције гласи: \( (p \Rightarrow q) \Leftrightarrow (\neg q \Rightarrow \neg p) \).
Негација од \( q \) ("број \( n \) је паран") је "број \( n \) је непаран" (\( \neg q \)).
Негација од \( p \) ("број \( n^2 \) је паран") је "број \( n^2 \) је непаран" (\( \neg p \)).
Еквивалентан исказ за доказивање је: "Ако је број \( n \) непаран, онда је и број \( n^2 \) непаран."
