Н. В. Папуловская Математическая логика Методическое пособие

Вид материала

Методическое пособие

Содержание 1.3. Выполнимые и общезначимые формулы A–формула, то запись ú= А 1.4. Алгебраический подход Замечательные тождества

Подобный материал:

• Математическая логика, 1012.22kb.
• Рабочая программа по дисциплине в 2-Математическая логика и теория алгоритмов шифр, 316.78kb.
• Программы кандидатского экзамена по специальности 01. 01. 06 "Математическая логика,, 50.44kb.
• Рабочая учебная программа по дисциплине математическая логика, 72.41kb.
• Рабочей программы учебной дисциплины дв2 Математическая логика и теория алгоритмов, 50.1kb.
• Рабочая учебная программа по дисциплине «Математическая логика и теория алгоритмов», 69.99kb.
• Уакиев Валериан Савирович рекомендуемая литература, 334.04kb.
• Аннотация программы учебной дисциплины «Дискретная математика и математическая логика, 55.65kb.
• Пособие по латинскому языку для студентов-юристов. Рига: бри, 1997. 64с., 108.11kb.
• В. А. Жернов апитерапия учебно-методическое пособие, 443.6kb.

1.3. Выполнимые и общезначимые формулы

Формула семантически выполнима, или просто выполнима, если её можно интерпретировать со значением истина. Например (P & q)– выполнима.

Множество формул называют выполнимым (непротиворечи­вым), если найдется такая интерпретация, при которой все формулы истины. Если такой интерпретации не находится, то множество невыполнимо (противоречиво).

Существуют высказывания, которые истины в любой области. Примером может служить высказывание A v`A. Такие высказывания называются общезначимыми, тождественно-истинными или тавтологиями. Отрицание общезначимой формулы является невыполнимая формула или противоречие.

Иногда из вида высказывания не ясно, является ли оно тавтологией. Проверка состоит в вычислении значения истинности высказывания на всех наборах значений входящих в него элементарных высказываний. Если формула содержит K различных высказывания, тогда она допускает 2^K интерпретаций. Рассмотрев все эти 2^K интерпретаций, можно определить, какая это формула.

Если A–формула, то запись ú= А означает, что А – тавтология.

Необходимо уметь:

• Записывать в формальном виде любое сложное высказывание, сформулированное фразами естественного языка.
  
• Определять семантическую область составного высказывания.
  
• Определять, является ли данное высказывание тавтологией;
  

При переходе от высказываний на естественном языке некоторые связки могут иметь другой смысл. Так, связка И обозначает истинность формулы, только если истинны входящие в неё элементарные высказывания. Поэтому её значение (и смысл) не зависит от порядка элементарных высказываний в формуле (например, во фразе "холодно и идёт дождь"). Но рассмотрите предложения " он убил и ему стало страшно" или "ему стало страшно, и он убил". В первом варианте И по значению играет роль условного предложения ("Ему стало страшно, потому что он убил"). Во втором варианте причина и следствие меняются местами.

В логике истина-ложь не всякое предложение имеет смысл. Например, предложение "это предложение ложно" не может быть ни ложным, ни истинным. Существуют парадоксы, т.е. рассуждений, приводящих к противоречиям. Например, парадокс лжеца. Некто говорит «Я лгу». Если при этом он не лжёт, то произнесённое им есть ложь, и поэтому он не лжёт. Если же при этом он говорит правду, то произнесённое им есть истина, и поэтому он лжёт. В любом случае оказывается, что он лжёт и не лжёт одновременно.


Контрольные упражнения.

1. Определить, является ли выражения тавтологией?
   

1. r & (P®q) ®q.
   
2. P ÚØq & r Û P.
   
3. (P®q) Û ØP Ú q Ú r.
   
4. (ØP ® q) &(ØP ® Øq)) ® P.
   
5. (P ® q) & (q ® r) ® (P ® r).
   

2. Построить таблицы истинности для следующих выражений:

1. r &(S&P)  P.
   
2. P  q  r.
   
3. ((P  q)  (q  r)  P)  (P  r).
   
4. (P  q)  (S  P  S).
   
5. P  (¬(PS) (Sr).
   

1.4. Алгебраический подход

Семантика произвольной формулы исчисления высказываний полностью определяется её таблицей истинности. Разные формулы могут иметь одну и ту же семантику.

Для логических формул важно уметь обнаруживать эквивалентность двух различно представленных объектов.

Определение. Две формулы назовём равносильными, если для любых наборов значений переменных они принимают одинаковые значения.

А º В тогда и только тогда, когда ú= АÛ В.

Чтобы преобразовать логическую формулу в равносильную полезно знать «замечательные тождества», которые задают различные способы представления объекта.

Замечательные тождества.

I. Законы булевой алгебры. Математик Джордж Буль (1815 – 1864) описал алгебру, основанную на операторах И, ИЛИ и НЕ.

6. 
   Закон двойного отрицания (инволюция): ØØA º A;
   
7. Законы коммутативности: A & B º B & A,
   
8. A Ú B º B Ú A;
   
9. Законы ассоциативности: A & (B & C) º (A & B) & C,
   A Ú (B Ú C) º (A Ú B) Ú C;
   
10. Законы дистрибутивности: A & (B Ú C) º (A & B) Ú (A & C),
    A Ú (B & C) º (A Ú B) & (A Ú C);
    
11. Свойства констант: A &1= A, A & 0 = 0, A Ú 1 = 1, A Ú 0 = A.
    
12. Закон идемпотентности: A & A º A; AÚ A º A.
    

II. Законы де Моргана:

Ø (A & B) º ØA Ú ØB;

Ø (A Ú B) º ØA & ØB.

III. Другие замечательные тождества.

Связь операций:

A Þ B º ØA Ú B,

A Û B º (A Þ B) & (ВÞА),
A & В º Ø(A Þ ØB),

A Ú В º ØA Þ B,

A Þ ØB º В Þ ØА.

6. Закон контрапозиции: A Þ B º ØB ÞØA.
   
7. Закон противоположности: A Û B º ØA Û ØB
   

Используя эти равносильности, можно по данной формуле построить ей равносильные или эквивалентные.

Примеры.

1. (A Ú A) & B Ú A º A & B Ú A º A& B Ú A & 1 º A& (B Ú 1) º A & 1º A.
   
2. B(Ø A & B) º ØB Ú (Ø A & B) º (ØB Ú ØA)&(ØB v B) º(ØB Ú ØA) &1º º(ØB Ú ØA) º Ø (B & A).