Логика высказываний
ЛОГИКА ВЫСКАЗЫВАНИЙ
План
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) Если φ и ψ – формулы, то (