Тавтологија (логика)

Од Википедија — слободната енциклопедија
Прејди на: содржини, барај

Во логиката, тавтологија е исказ кој содржи повеќе од еден подисказ, кој е вистинит без разлика на вистинитоста на неговите делови. На пример, исказот „Или сите гаврани се црни или не сите од нив се црни“ е тавтологија, бидејќи е вистинит без разлика на тоа која боја се гавраните. Формално изразено, како исказ со X кој стои за „Сите гаврани се црни“ би било

X \lor \lnot X,

што е тавтологија, обележана како \top, бидејќи без разлика на вистинитоста на X, еден од дисјунктите е вистинит, а со тоа и целиот исказ. Знакот \top значи „генеричка“ тавтологија таму каде било каква тавтологија би завршила работа, без конкретно да укаже на тоа каде лежи тавтологијата.

Исказ како

X \land \lnot X

кој е секогаш невистинит без разлика на вистинитоста на неговите делови се нарекува контрадикција на недоследост и се бележи како \bot.

Кај исказната логика, знакот \vDash or \vdash може да се постави пред реченица или формули за да означи дека тоа е тавтологија. Празниот простор лево од знакот \vdash значи дека не се потребни никакви претпоставки за логично дедуцирање на материјал десно од знакот. Така можеме да се изразиме:

\lbrace X \lor \lnot X \rbrace \vdash \top, \lbrace\rbrace \vdash \top, \top \vdash X \lor \lnot X

Клучните вистини за тавтологија се 1)  \lnot\top \vdash \bot и 2)  \lnot\bot \vdash \top . Значи, не тавтологија е недолседност и не недоследност е тавтологија.

Тавтологии наспроти валидности[уреди]

Предикатната логика, често разликува помеѓу тавтологии и валидности (или логики вистини). Вака гледан, еден исказ се смета за тавтологија ако и само ако истиот претставува валидност во исказната логика (т.е. кога сè во опсегот на еден квантификатор се гледа како црна кутија). Така на пример исказот

(\forall x)(x=5)\lor\lnot(\forall x)(x=5)

е тавтологија бидејќи може да се напише и како

X \lor \lnot X

а ова е тавтологија. Наспроти тоа, исказот

(\forall x)\big((x=5)\lor\lnot(x=5)\big)

би бил валидност, но не тавтологија, иако е вистинит во било која интерпретација, бидејќи не постои начин истиот да се изрази како тавтологија во исказната логика. Оваа разлика не секогаш се прави.

Откривање на тавтологии[уреди]

Ефективна процедура за проверка дали една исказна формула е тавтологија или не е по пат на таблици на вистинитост. Меѓутоа како ефективна процедура, таблиците на вистинитост се ограничени од се ограничени од фактот што бројот на логички интерпретации (или припишувања на вистинитости) кои се проверени се зголемува како 2k, каде k е бројот на променливи во формулата. Алгебарски, симболички или трансформациони методи за упростување на едан формула набрзо стануваат решенија за овие сложени пребарувања со таблици.