Скачать

Логика высказываний

ЛОГИКА ВЫСКАЗЫВАНИЙ


План

1 ОПРЕДЕЛЕНИЕ ФОРМУЛЫ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ

2 АЛГЕБРА ВЫСКАЗЫВАНИЙ

3 РАВНОСИЛЬНОСТЬ ФОРМУЛ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ. КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА

4 ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА. ПРОБЛЕМА РАЗРЕШИМОСТИ

5 СОВЕРШЕННАЯ ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА. СОВЕРШЕННАЯ КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА

Литература


1 ОПРЕДЕЛЕНИЕ ФОРМУЛЫ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ

Математическая логика стремится к возможно большей точности. Эта цель достигается с помощью точного языка, построенного из устойчивых, наглядно воспринимаемых знаков. В исчислении высказываний используются символы трех сортов:

1. Пропозициональные переменные. Их будем обозначать малыми буквами латинского алфавита с индексами или без них: x, у, х,..., p, q, .. . Различные буквы обозначают разные суждения, внутренняя структура суждений нас интересовать не будет. Суждения, обозначенные пропозициональными переменными, будут называться высказываниями. Будем полагать, что высказывания удовлетворяют закону исключенного третьего и закону непротиворечия, т.е. каждое высказывание либо истинно, либо ложно. Так что каждая переменная у нас будет принимать два значения: значения «истина» будем обозначать «1», а значение «ложь» – «0».

2. Константы или логические связи – «―», «Ù», «Ú», «®», «º».

3. Скобки: «(» - левая скобка и «)» - правая скобка.

С помощью констант (связок) атомарные высказывания соединяются в более сложные высказывания. Так из двух высказываний p и q с помощью констант образуются высказывания

`p - читается «не-р»

`q - читается «не-q»

pÙq – читается «р и q»

pÚq – читается «р или q»

р®q - читается «если р, то q»

рºq - читается «р тогда и только тогда, когда q»

Сложное высказывание, образованное с помощью знака «¯» называется отрицанием, знака - «Ù» - конъюнкцией, знака «Ú» - дизъюнкцией, знака «®» - импликацией, знака «º» - эквивалентностью. Переменные и сложные высказывания, образованные из них посредствам многократного применения логических связок и скобок называются формулами исчисления высказываний, если они удовлетворяют трем условиям:

1) Пропозициональная переменная есть формула

2) Если φ и ψ – формулы, то (