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

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

Задаци

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

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

$(p \Rightarrow q) \Leftrightarrow (\neg p \vee q)$

Нама jе потребно проверити да ли jе формула таутологиja наjjедноставниjе се може проверити помоћу истинитосне таблице те формуле.

$p$	$q$	${\neg p}$	${p \Rightarrow q}$	${\neg p \vee q}$	${(p \Rightarrow q) \Leftrightarrow (\neg p \vee q)}$
$\top$	$\top$	$\bot$	$\top$	$\top$	$\top$
$\top$	$\bot$	$\bot$	$\bot$	$\bot$	$\top$
$\bot$	$\top$	$\top$	$\top$	$\top$	$\top$
$\bot$	$\bot$	$\top$	$\top$	$\top$	$\top$

Исказна формула је таутологија ако је тачна за све могуће вредности својих исказних слова. Најсигурније се то проверава таблицом истинитости: са $n$ слова таблица има $2^n$ врста, а формула је таутологија ако у последњој колони стоји само $\top$ . Таблицу попуњавате колону по колону, од најмањих делова формуле ка целој формули.

Кључно правило: импликација $p \Rightarrow q$ нетачна је само кад је $p$ тачно, а $q$ нетачно. Зато $p \Rightarrow q$ у свакој врсти има исту вредност као $\neg p \vee q$ , па је $(p \Rightarrow q) \Leftrightarrow (\neg p \vee q)$ таутологија и импликацију увек можете заменити дисјункцијом. Честа грешка је да се импликација са нетачном претпоставком прогласи нетачном. Формула која је увек нетачна зове се контрадикција.

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

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

Колоне

p \Rightarrow q

и

\neg p \vee q

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

p = \top

,

q = \bot

, као код Миле, а са обрнутом импликацијом

q \Rightarrow p

не поклапа се у две врсте.

Програмери овако поједностављују услове у програмима, јер се провера „ако $p$ , онда $q$ “ може написати као „није $p$ или $q$ “, а пројектанти чипова таблицама истинитости проверавају да ли два логичка кола дају исти излаз за сваки улаз.

Правило на базену

На улазу градског базена у Новом Саду пише: „Ако је дете млађе од 10 година, мора да буде у пратњи одрасле особе.“ Чувар проверава другачије: пушта свакога ко има бар 10 година или је у пратњи. Покажите да чувар примењује исто правило и одредите ко од четворо деце крши правило: Ана (8 година, са мамом), Лука (12 година, сам), Мила (7 година, сама) и Петар (11 година, са татом).

Решење

Нека је $p$ исказ „дете је млађе од 10 година“, а $q$ исказ „дете је у пратњи“. Правило на табли је $p \Rightarrow q$ , а чувар проверава $\neg p \vee q$ .
За $(p, q) = (\top, \top), (\top, \bot), (\bot, \top), (\bot, \bot)$ импликација $p \Rightarrow q$ има вредности $\top, \bot, \top, \top$ , а $\neg p \vee q$ такође $\top, \bot, \top, \top$ .
Колоне су једнаке у свакој врсти, па је $(p \Rightarrow q) \Leftrightarrow (\neg p \vee q)$ таутологија: табла и чувар траже исто.
Правило крши само дете за које је $p = \top$ и $q = \bot$ . Ана има $(\top, \top)$ , Лука $(\bot, \bot)$ , Мила $(\top, \bot)$ , а Петар $(\bot, \top)$ .

Одговор: Чувар примењује исто правило, а крши га само Мила, јер је млађа од 10 година и дошла је сама.

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

Таблицом истинитости испитајте да ли је формула $\neg(p \Rightarrow q) \Leftrightarrow (p \wedge \neg q)$ таутологија.

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

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