30. Відношення логічного слідування.

Між певними формулами логіки висловлювань існує відношення логічного слідування. Це означає: якщо із формули виду слідує формула виду то кожен раз, коли формула Р є істинною, то й формула Р2 є істинною. Формальний вираз відношення логічного слідування: Р, -" Р2. Наприклад, із формули виду А слідує формула виду А v В; із формули виду -> -o А слідує формула виду А; із формули виду А v А слідує формула виду А.

На підставі встановлення відношення рівносильності та слідування здійснюють операцію доведення певних формул на істинність за правилами виведення. Операція доведення - невід'ємна частина будь-якого числення висловлювань.

Правила логічного слідування

(А -> В, А) -" В (правило модус поненс);

(А -" В, -і В) -" -" А (правило модус толленс);

(А, В) -> А л В (правило ВК - введення кон'юнкції);

(А л В) -> А; (А л В) -> В (правило УК - усунення кон'юнкції);

А-> (А v В); В -" (А v В) (правило ВД - введення диз'юнкції);

(А 1 В, А) -" -і В; (А 1 В, - В) -" А (правило УД - усунення диз'юнкції);

((А -> В, В -> А)) -" (А = В) (правило ВЕ - введення еквівалентності);

(А = В) -> (А -> В); (А = В) -"(В -> А) (правило УЕ - усунення еквівалентності));

А -> -і -і А (правило (В32) - введення подвійного заперечення);

-" -і А -> А (правило У32 - усунення подвійного заперечення).

. Правила побудови прямого доведення. Пряме доведення формули А1 -> (А2 ... (Ая -> С) будується в такий спосіб. На будь-якому кроці доведення можна визначити:

1. Одну із формул А., А2,... Ап як припущення.

2. Формулу, що випливає з раніше невизначених формул за правилами логічного слідування.

3. Раніше доведену формулу.

Пряме доведення формули вважають побудованим, якщо відповідно до 1-3 ми отримуємо послідовність формул, котрі завершуються формулою С

31. Таблиці істинності пропозиційних зв’язок.

Серед групи логічних зв'язок виділяють зв'язку "є" і так звані пропозиційні зв'язки "і", "або", "якщо, то", "ні", "якщо і тільки якщо, то".

Окрім цих способів перевірки правила висновку (ми наголошуємо саме на перевірці правила висновку, а не на висновку, саме тому, що будь-який висновок це є по суті втілення конкретного правила висновку, тому перевірка коректності висновку зводиться до перевірки коректності правила висновку) існує ще перевірка шляхом застосування методу аналітичних таблиць.

Основу методу аналітичних таблиць складає звичайне визначення таблиць істинності для пропозиційних зв'язок, а сама аналітична таблиця будується навпаки. Виходимо із того, що значення істинності усього виразу нам відомо, залишається знайти лише значення істинності для елементарних висловлювань, з яких складається цей вираз.

Іншими словами, таблиці називаються аналітичними тому, що розкладаючи вихідне висловлювання на елементарні висловлювання (на атоми), ми намагаємося знайти набір значень атомів, при яких би вихідне висловлювання було хибне.

32. Поняття формули-тавтології.

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

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

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

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

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

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

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

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