Таутологије – пример 2

Видео лекција школе Рајак посвећена таутологијама. Садржи сложенији пример.

Задаци

Текст задатака објашњених у видео лекцији.

Пр.2) Испитати да ли је следећа формула таутологија:

$((p \Rightarrow q) \Rightarrow (r \Rightarrow \neg p)) \Rightarrow (\neg q \Rightarrow \neg r)$

((p⇒q)⇒(r⇒¬p))⇒(¬q⇒¬r)

Проверимо уз помоћ истинитосне таблице те формуле.

Са A означимо $p⇒q$ , са B означимо $r⇒¬p$ и са С означимо $¬q⇒¬r$

$p$	$q$	$r$	$¬p$	$¬q$	$¬r$	$A$	$B$	$С$	$A⇒B$	$(А⇒В)⇒С$
$\top$	$\top$	$\top$	$\bot$	$\bot$	$\bot$	$\top$	$\bot$	$\top$	$\bot$	$\top$
$\top$	$\top$	$\bot$	$\bot$	$\bot$	$\top$	$\top$	$\top$	$\top$	$\top$	$\top$
$\top$	$\bot$	$\top$	$\bot$	$\top$	$\bot$	$\bot$	$\bot$	$\bot$	$\top$	$\bot$
$\top$	$\bot$	$\bot$	$\bot$	$\top$	$\top$	$\bot$	$\top$	$\top$	$\top$	$\top$
$\bot$	$\top$	$\top$	$\top$	$\bot$	$\bot$	$\top$	$\top$	$\top$	$\top$	$\top$
$\bot$	$\top$	$\bot$	$\top$	$\bot$	$\top$	$\top$	$\top$	$\top$	$\top$	$\top$
$\bot$	$\bot$	$\top$	$\top$	$\top$	$\bot$	$\top$	$\top$	$\bot$	$\top$	$\bot$
$\bot$	$\bot$	$\bot$	$\top$	$\top$	$\top$	$\top$	$\top$	$\top$	$\top$	$\top$

Кад формула има три исказна слова $p$ , $q$ и $r$ , таблица истинитости има $2^3 = 8$ врста. Врсте пишете по реду: $p$ мења вредност на сваке четири врсте, $q$ на сваке две, а $r$ у свакој врсти. Дугачку формулу разложите на делове и сваки означите новим словом, на пример $A = p \Rightarrow q$ и $B = r \Rightarrow \neg p$ , па израчунајте колону сваког дела пре колоне целе формуле.

Да бисте показали да формула није таутологија, довољна је једна врста у којој је нетачна. За $((p \Rightarrow q) \Rightarrow (r \Rightarrow \neg p)) \Rightarrow (\neg q \Rightarrow \neg r)$ то је, на пример, $p = \top$ , $q = \bot$ , $r = \top$ . А да бисте показали да јесте, морате проверити свих осам врста. Пазите на импликацију: нетачна је само кад је претпоставка тачна, а последица нетачна.

Таблица истинитости: ((p ⇒ q) ∧ (q ⇒ r)) ⇒ (¬p ⇒ ¬r)
p	q	r	¬p	¬r	Ap⇒q	Bq⇒r	CA∧B	D¬p⇒¬r	FC⇒D
тачно	тачно	тачно	нетачно	нетачно	тачно	тачно	тачно	тачно	тачно
тачно	тачно	нетачно	нетачно	тачно	тачно	нетачно	нетачно	тачно	тачно
тачно	нетачно	тачно	нетачно	нетачно	нетачно	тачно	нетачно	тачно	тачно
тачно	нетачно	нетачно	нетачно	тачно	нетачно	тачно	нетачно	тачно	тачно
нетачно	тачно	тачно	тачно	нетачно	тачно	тачно	тачно	нетачно	нетачно
нетачно	тачно	нетачно	тачно	тачно	тачно	нетачно	нетачно	тачно	тачно
нетачно	нетачно	тачно	тачно	нетачно	тачно	тачно	тачно	нетачно	нетачно
нетачно	нетачно	нетачно	тачно	тачно	тачно	тачно	тачно	тачно	тачно

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

Марково закључивање нетачно је у две врсте,

(p, q, r) = (\bot, \top, \top)

и

(\bot, \bot, \top)

: у њима су обе премисе тачне, а закључак нетачан. Са закључком

p \Rightarrow r

формула је тачна у свих осам врста, па је то таутологија.

Тестери софтвера и инжењери аутоматике испробавају сва стања улаза као врсте таблице: три прекидача дају 8 комбинација, а довољна је једна погрешна да уређај не прође проверу.

Петица и екскурзија

Марко из Ниша размишља: „Ако научим градиво, добићу петицу. Ако добијем петицу, родитељи ће ме пустити на екскурзију. Дакле, ако не научим градиво, неће ме пустити на екскурзију.“ Испитајте таблицом истинитости да ли је ово закључивање исправно.

Решење

Означимо: $p$ је „Марко научи градиво“, $q$ је „Марко добије петицу“, а $r$ је „родитељи пусте Марка на екскурзију“. Закључивање је формула $((p \Rightarrow q) \wedge (q \Rightarrow r)) \Rightarrow (\neg p \Rightarrow \neg r)$ .
Нека је $A = (p \Rightarrow q) \wedge (q \Rightarrow r)$ и $B = \neg p \Rightarrow \neg r$ . Таблица има $2^3 = 8$ врста.
$B$ је нетачно само кад је $\neg p = \top$ и $\neg r = \bot$ , тј. у врстама $(p, q, r) = (\bot, \top, \top)$ и $(\bot, \bot, \top)$ . У обе је $p \Rightarrow q = \top$ и $q \Rightarrow r = \top$ , па је $A = \top$ .
У те две врсте је $A \Rightarrow B$ једнако $\top \Rightarrow \bot = \bot$ , а у осталих шест је $\top$ . Формула није таутологија.
Исправан закључак био би $p \Rightarrow r$ : формула $((p \Rightarrow q) \wedge (q \Rightarrow r)) \Rightarrow (p \Rightarrow r)$ тачна је у свих осам врста.

Одговор: Закључивање није исправно: Марко може да не научи градиво, а да га ипак пусте на екскурзију, и тада су обе премисе тачне, а закључак нетачан.

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

Испитајте да ли је формула $(p \Rightarrow (q \vee r)) \Rightarrow (p \Rightarrow q)$ таутологија.

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

Није. За $p = \top$ , $q = \bot$ , $r = \top$ претпоставка $p \Rightarrow (q \vee r)$ је $\top \Rightarrow \top = \top$ , а последица $p \Rightarrow q$ је $\top \Rightarrow \bot = \bot$ , па је цела формула нетачна.