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

Видео лекција у којој је објашњен сложенији задатак из ове области који се решава свођењем на контрадикцију.

Задаци

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

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

$\left( {\left( {p \Leftrightarrow q} \right) \Rightarrow \neg r} \right) \vee \left( {\left( {s \wedge \neg t} \right) \Rightarrow \left( {r \vee p} \right)} \right)$

$F:((p \Leftrightarrow q) \Rightarrow \neg r) \vee ((s \wedge \neg t) \Rightarrow (r \vee p))$

Да jе исказна формула $\left( {\left( {p \Leftrightarrow q} \right) \Rightarrow \neg r} \right) \vee \left( {\left( {s \wedge \neg t} \right) \Rightarrow \left( {r \vee p} \right)} \right)$ jедна таутологиjа можемо установити овако: ако посматрана формула не би била таутологиjа, требало би бити, за неке вредности елементарних исказа p, q, r, s и t коjи се у овоj формули поjављуjу,

$\tau \left[ F \right] = \bot$

То би се могло десити jедино у случаjу да jе

$\tau \left[ {(p \Leftrightarrow q) \Rightarrow \neg r} \right] = \bot$

и $\tau \left[ {(s \wedge \neg t) \Rightarrow (r \vee p)} \right] = \bot$ (диcjункциjа ова два исказа ниjе тачна уколико нису тачни ови искази).

Овде даље у првом делу видемо импликациjу два исказа коjи нису тачни.

За импликациjу знам да она ниjе тачна кад jе први исказ тачан а други ниjе тачан:

$\tau [p \Leftrightarrow q] = \top$

$\tau \left[ {\neg r} \right] = \bot$

Из другог исказа можемо закључити да

$\boxed{\tau [r] = \top }$

У другом делу задатка видемо импликациjу два исказа коjи нису тачни.

$\tau \left[ {(s \wedge \neg t) \Rightarrow (r \vee p)} \right] = \bot$

Импликациjа ниjе тачна кад jе први исказ тачан а други ниjе тачан:

$\tau \left[ {s \wedge \neg t} \right] = \top$

$\tau \left[ {r \vee p} \right] = \bot$

На исти начин добићемо да:

$\boxed{\tau [s] = \top }$

$\tau [\neg t] = \top$

$\boxed{\tau [t] = \bot }$

Имамо

$\tau \left[ {r \vee p} \right] = \bot$ онда

$\boxed{\tau [r] = \bot }$ и

$\boxed{\tau [p] = \bot }$

Враћамо се на први део овог задатка.

$\tau \left[ {(p \Leftrightarrow q) \Rightarrow \neg r} \right] = \bot$

Добили смо да

$\tau [p] = \bot$ онда је први исказ тачан

$\tau [p \Leftrightarrow q] = \top$ када

$\boxed{\tau [q] = \bot }$

Када смо добили истинитосне вредности свих исказних слова можемо да приметимо да на jедном месту $\tau \left[ {r} \right] = \bot$ а на другом $\tau \left[ {r} \right] = \top$

Ту смо дошли до контрадикциjе. Можемо да закључимо да посматрана формула jе таутологиjа.

Кад формула има много слова, таблица је предугачка: са пет слова има $2^5 = 32$ врсте. Тада се користи свођење на контрадикцију. Претпоставите да је формула $F$ нетачна, $\tau[F] = \bot$ , и пратите шта то намеће словима. Дисјункција је нетачна само кад су оба дела нетачна, импликација само кад је претпоставка тачна, а последица нетачна, а конјункција је тачна само кад су оба дела тачна.

Ако неко слово мора истовремено бити $\top$ и $\bot$ , претпоставка је немогућа и $F$ је таутологија. Ако добијете вредности без сукоба, нашли сте врсту у којој је $F$ нетачна, па $F$ није таутологија. Пазите: кад део формуле може бити тачан на више начина, као $p \Leftrightarrow q$ , проверите сваки случај.

Таблица истинитости: ((p ⇒ q) ∧ (q ⇒ r) ∧ (r ⇒ s)) ⇒ (p ⇒ s)
p	q	r	s	F
тачно	тачно	тачно	тачно	тачно
тачно	тачно	тачно	нетачно	тачно
тачно	тачно	нетачно	тачно	тачно
тачно	тачно	нетачно	нетачно	тачно
тачно	нетачно	тачно	тачно	тачно
тачно	нетачно	тачно	нетачно	тачно
тачно	нетачно	нетачно	тачно	тачно
тачно	нетачно	нетачно	нетачно	тачно
нетачно	тачно	тачно	тачно	тачно
нетачно	тачно	тачно	нетачно	тачно
нетачно	тачно	нетачно	тачно	тачно
нетачно	тачно	нетачно	нетачно	тачно
нетачно	нетачно	тачно	тачно	тачно
нетачно	нетачно	тачно	нетачно	тачно
нетачно	нетачно	нетачно	тачно	тачно
нетачно	нетачно	нетачно	нетачно	тачно

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

Свођење на контрадикцију показало је да

F

не може бити нетачна, а таблица од

2^4 = 16

врста то потврђује. Ако се закључак обрне у

s \Rightarrow p

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

p = \bot

и

q = r = s = \top

.

Програми који проверавају исправност процесора или правила распореда часова траже вредности исказа за које би неки услов био нарушен; ако наиђу на контрадикцију, услов важи увек.

Аларм у згради

Систем заштите од пожара у стамбеној згради у Крагујевцу повезан је овако: ако се активира детектор дима, укључује се сирена; ако се укључи сирена, откључавају се врата степеништа; ако се откључају врата, пале се светла за евакуацију. Инжењер тврди: ако се активира детектор, пале се светла за евакуацију. Докажите свођењем на контрадикцију да је тврдња увек тачна.

Решење

Нека су $p$ , $q$ , $r$ , $s$ искази „детектор се активирао“, „сирена се укључила“, „врата су откључана“ и „светла за евакуацију су упаљена“. Треба показати да је $F: ((p \Rightarrow q) \wedge (q \Rightarrow r) \wedge (r \Rightarrow s)) \Rightarrow (p \Rightarrow s)$ таутологија.
Претпоставимо $\tau[F] = \bot$ . Импликација је нетачна само кад је претпоставка тачна, а последица нетачна, па су $p \Rightarrow q$ , $q \Rightarrow r$ и $r \Rightarrow s$ тачне, а $\tau[p \Rightarrow s] = \bot$ .
Из $\tau[p \Rightarrow s] = \bot$ следи $\tau[p] = \top$ и $\tau[s] = \bot$ .
Пошто је $\tau[p] = \top$ , а $p \Rightarrow q$ тачно, мора бити $\tau[q] = \top$ . Затим из $q \Rightarrow r$ следи $\tau[r] = \top$ , а из $r \Rightarrow s$ следи $\tau[s] = \top$ .
За $s$ смо добили и $\bot$ и $\top$ , што је контрадикција. Дакле, $F$ не може бити нетачна.

Одговор: Тврдња инжењера важи увек: формула је таутологија, а уместо таблице од $2^4 = 16$ врста било је довољно неколико корака.

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

Свођењем на контрадикцију докажите да је формула $((p \Rightarrow q) \wedge (r \Rightarrow s) \wedge (p \vee r)) \Rightarrow (q \vee s)$ таутологија.

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

Ако би била нетачна, било би $\tau[q \vee s] = \bot$ , тј. $\tau[q] = \tau[s] = \bot$ , а све три претпоставке тачне. Из $p \Rightarrow q$ следи $\tau[p] = \bot$ , из $r \Rightarrow s$ следи $\tau[r] = \bot$ , па је $\tau[p \vee r] = \bot$ , а требало је $\top$ . То је контрадикција, па формула јесте таутологија.