II. Равносильные формулы, выражающие одни логические операции через другие

I. Основные равносильные формулы.

1. A Ù A º A;

2. A Ú A º A - законы идемпотентности;

3. A Ù истина º A;

4. A Ú истина º истина;

5. A Ù ложь º ложь; 6. A Ú ложь º A;

7. A Ù ù A º ложь - закон противоречия;

8. A Ú ù A º истина -закон исключения третьего;

9. ù ù A º A - закон снятия двойного отрицания;

10. A Ù (B Ú A) º A;

11. A Ú (B Ù A) º A - законы поглощения;

1. A «B º (A ® B) Ù (B ® A);

2. A ® B º ù A Ú B;

3. ù (A Ù B) º ù A Ú ù B;

4. ù (A Ú B) º ù A Ù ù B;

5. A Ù B º ù (ù A Ú ù B);

6. A Ú B º ù (ù A Ù ù B).

III. Равносильные формулы, выражающие основные законы алгебры логики высказываний.

1. A Ù B º B Ù A - коммутативность конъюнкции.

2. A Ú B º B Ú A - коммутативность дизъюнкции.

3. A Ù (B Ù N) º (A Ù B) Ù N - ассоциативность конъюнкции.

4. A Ú (B Ú N) º (A Ú B) Ú N - ассоциативность дизъюнкции.

5. A Ù (B Ú N) º (A Ù B) Ú (A Ù N) - дистрибутивность конъюнкции

относительно дизъюнкции.

6. A Ú (B Ù N) º (A Ú B) Ù (A Ú N) - дистрибутивность дизъюнкции относительно конъюнкции.

Форма, в которой записывается формула (иными словами, метод, которым она конструируется из простых высказываний и логических соединителей), называется синтаксисом формулы. Истинностное значение формулы называют семантикой формулы. Существуют некоторые формулы, имеющие определённые истинностные значения, обусловленные синтаксической формой этих формул, вне зависимости от значений истинности простых высказываний, из которых эти формулы состоят.

Например: Значением формулы A Ú ù A - всегда будет истина, неза-висимо от значения A. Про такую формулу говорят, что она тождественно -истинна, её называют тавталогией. С другой стороны, истинностным значением формулы B Ù ù B - всегда будет ложь, независимо от значения B. Про такую формулу говорят, что она тождественно-ложна и её назы-вают противоречием. Также существуют формулы, принимающие значе-ния истина или ложь в зависимости от значений входящих в неё перемен-ных (Например: A ® B). Такие формулы называют выполнимыми.

Таким образом все формулы алгебры логики делятся на три класса:

- тождественно-истинные;

- тождественно-ложные;

- выполнимые.

Исчисление высказываний - это аксиоматическая система на основе тавталогий (аксиом), используемых для дедуктивного вывода, где в качестве простых высказываний используются переменные. Описание ис-числения состоит из алфавита, правил описания формул и правил преобра-зования (создания, вывода) формул.

Алфавит состоит из символов 3-х категорий:

1. A, B, N, C, U, Z ¼ - переменные.

2. Ú - дизъюнкция; Ù -конъюнкция; ® - импликация; ù -отрицание - логические связки.

3. () - скобки.

Правила описания формул включают в себя:

1. Всякая переменная A, B, N, C, U, Z ¼ - является формулой.

2. Если A и B -формулы, то (A Ù B), (A Ú B), (A®B), ù A -также формулы.

3. Никакая другая строчка символов не является формулой. Процедура создания формул в исчислении высказываний происходит путём применения правил вывода к аксиомам исчисления, являющихся тождественно-истинными формулами или тавтологиями. Система аксиом исчисления высказываний состоит из IV групп.

I группа

1. C ® (U ® C).

2. (C ® (U ® Z)) ® ((C ® U) ® (C ® Z)).

II группа

1. C Ù U ® C.

2. C Ù U ® U.

3. (Z ® C) ® ((Z ® U) ® (Z ® C Ù U)).

III группа

1. C® C Ú U.

2. U ® C Ú U.

3. (C ® Z) ® ((U ® Z) ® (C Ú U ® Z)).

IV группа

1. (C ® U) ® (ù U ® ù C).

2. C ® ù ù C.

3. ù ù C ® C.

К правилам вывода формул относятся:

Правило подстановки. Если формула A доказуема в исчислении высказываний C - переменная, B - произвольная формула исчисления высказываний, то формула полученная в результате замены в формуле A переменной C всюду где она входит, формулой B, является также доказуемой формулой.

Обозначения:

B

ò (A) - в A подстановка B вместо C.

C

^ A - доказуемая в исчислении высказываний формула A.

Краткая формулировка правила подстановки.

^A, ^ B, то B

^ ò (A)

C

Правило заключения. Если формулы A и A ® B доказуемы в исчислении высказываний, то формула B также доказуема.

^ A и ^ A ® B

^B

Основная задача любого исчисления - доказательство доказуемости формул.

Доказуемой формулой является:

- аксиома;

- формула, полученная из доказуемой формулы путём подстановки вместо переменной C произвольной формулы B;

- формула B, полученная из доказуемых формул A и A ® B путём применения правила заключения;

- никакая другая формула исчисления высказываний не является доказуемой.

Дата добавления: 2015-06-27