Алгебра висловлень

.....................

f (1,1,...,1,0)

f (1,1,...,1,1)

Серед формул алгебри висловлень особливе місце займають ті формули A(p1,p2,...,pn), які на всіх наборах (a1,a2,...,an) значень своїх змінних набувають значення 1.

Формула алгебри висловлень A(p1,p2,...,pn) називається тавтологією тоді і тільки тоді, коли їй відповідає функція істинності, яка тотожно дорівнює 1.

Тавтології ще називають тотожно істинними формулами, або законами алгебри висловлень. Аналогом тавтології у природній мові є поняття істинного твердження.

Наведемо приклади деяких важливих тавтологій:

(p(p)) (закон виключення третього),

((p(p))) (закон виключення суперечності),

(pp) (закон тотожності).

Довести, що ці формули є тавтологіями можна за допомогою відповідних таблиць істинності. Той факт, що формула A алгебри висловлень є тавтологією позначають так =A. Символ =, як і A належать метамові.

Формула алгебри висловлень A(p1,p2,...,pn), яка набуває значення 0 на всіх наборах (a1,a2,...,an) значень своїх пропозиційних змінних, називається суперечністю, або тотожно хибною формулою.

Формулу, яка не є ні тавтологією, ні суперечністю, називають нейтральною.

Множина всіх формул алгебри висловлень розбивається на тавтології, суперечності та нейтральні формули.

Формула, яка не є суперечністю, називається виконуваною.

Наведемо ряд тверджень, справедливість яких очевидна.

1. Заперечення тавтології є суперечністю і навпаки.

2. Кожна тавтологія є виконуваною формулою (навпаки, взагалі кажучи, ні).

3. Кожна нейтральна формула є виконуваною, але не навпаки.

4. Заперечення виконуваної формули може бути, як виконуваною формулою, так і невиконуваною формулою.

Дві формули A і B алгебри висловлень називаються рівносильними, якщо їм відповідає та сама функція істинності. Рівносильність формул A і B позначають за допомогою знака = ( або ): записують A=B (AB або AB).

Очевидно, що відношення рівносильності на множині формул є відношенням еквівалентності, тому часто це відношення називають еквівалентністю.