Логические связки и высказывания

Логические связки и высказывания

Элементами логических рассуждений являются утверждения, которые либо истинны, либо ложны, но не то и другое вместе. Такие утверждения называются (простыми) высказываниями. Простые высказывания обозначаются пропозициональными переменными, принимающими истинностные значения «И» и «Л». Из простых высказываний с помощью логических связок могут быть по­строены составные высказывания. Обычно рассматривают следующие логические связки:

Название	Прочтение	Обозначение
1. Отрицание	не	┐,`
2. Конъ­юнкция	и	&,Ù
3. Дизъюнк­ция	или	Ú
4. Импликация	если... то	®,É,Þ
5. Эквиваленция	…эквивалентно…	Û,~

 

Можно заметить, что в разговорной речи отрицание высказывания А лучше формулировать как «неверно, что А», а импликацию высказываний А и В – «А влечет В» или «из А следует В».

Далее, для удобства обозначений логических связок в отличие от алгебраических операций в алгебре Буля будем использовать везде для отрицания символ ┐, а для конъюнкции - &.

Правильно построенные составные высказывания называются (пропозициональными) формулами. Формулы имеют следующий синтаксис:

(формула) = И | Л |

‹пропозициональная переменная› |

(┐ (формула) › |

(‹фор­мула› & ‹ формула›) |

(‹ формула› ‹ формула›)|

(‹формула › →;‹формула›)|

(‹формула ›~‹формула›)|

(‹формула ›Å‹формула›)|

Для упрощения записи вводится старшинство связок (┐,&, , →;), и лишние скобки опускаются. Истинностное значение формулы определяется через истинностные значения ее составляющих в соответствии со следующей таблицей истинности:

А	В	┐ А	А&В	A В	А®В	А~В	АÅВ
Л	Л	И	Л	Л	И	И	Л
Л	И	И	Л	И	И	Л	И
И	Л	Л	Л	И	Л	Л	И
И	И	Л	И	И	И	И	Л

 

Следует отметить, что логические связки мы будем рассматривать таким образом, что истинностные значения составных высказываний определяются только истинностными значениями составляющих высказываний, а не их смыслом. Так, не математик может признать утверждение «если 2´2=5, то Киев –столица Украины» ложным, поскольку для него истинность высказывания «из А следует В» означает, что А по смыслу должно влечь за собой В. Но тогда связка «из А следует В» зависит от смысла самих этих высказываний. Однако практика показывает, что можно обороты типа «из А следует В» использовать таким образом, чтобы под ними каждый раз подразумевалась некоторая операция, не зависящая от смысла высказывания:

1) если 0=0, то 1=1;

2) если 0=1, то 0=0;

3) если 0=0, то 0=1;

4) если 0=1, то 1=2.

Первое утверждение естественно считать истинным, поскольку из равенства 0=0, используя другие свойства чисел, можно вывести равенство 1=1 (например, прибавив по 1 к обеим частям равенства 0=0).

Второе утверждение также естественно считать истинным: умножая на 0 обе части равенства 0=1, получаем равенство 0=0.

Третье утверждение считаем ложным, так как, исходя из истинного равенства, невозможно с помощью никаких умозаключений прийти к ложному.

Четвертое утверждение естественно считать истинным: прибавляя 1 к обеим частям равенства 0=1, получаем равенство 1=2.

Рассмотренная связка определяет импликацию, которая ложна тогда и только тогда, когда А истинно, а В – ложно. При этом А есть посылка импликации, а В – заключение.

Эквиваленция высказываний А и В – это высказывание, которое истинно тогда и только тогда, когда истинностные значения А и В совпадают («А эквивалентно В»).

Еще раз рассмотрим понятие формулы логики высказываний.

Алфавитом называется любое непустое множество. Элементы этого множества называются символами данного алфавита. Словом в данном алфавите называется произвольная конечная последовательность символов (возможно, пустая). Слово а называется подсловом слова в, если в=в₁ а в₂ для некоторых слов в₁ и в_{2 .}

Алфавит логики высказывания содержит следующие символы: высказывательные переменные Х ₁, Х ₂, Х _3, …; логические символы &,Ú, ┐,®,~; символы скобок (,).

Слово в алфавите логики высказываний называется формулой, если оно удовлетворяет следующему определению:

1) любая высказывательная переменная – формула;

2) если А и В - формулы, то (┐А), (А&В), (АÚВ), (А®В), (А~В), (АÅВ) - формулы;

3) только те слова являются формулами, для которых это следует из 1) и 2).

Подформулой формулы А называется любое подслово А, само являющееся формулой.

 

Пример 4.1. Слово (Х ₁ & Х ₂)® Х ₃ ┐ Х ₁ не является формулой, а слова (┐ Х ₁® Х ₂)Ú Х ₁, (Х ₁~ Х ₂)®┐ Х ₂ – формулы. Слова Х ₁ ~ Х ₂, ┐ Х ₂, Х ₁, Х ₂ - подформулы последней формулы.

Очевидно, что каждая формула имеет таблицу истинности.

 

Пример 4.2. Запишем формулами логики высказываний определение равенства множеств, исходя из формулы 1.12. Для этого обозначим простые высказывания:

А - «элемент х из множества F, т.е. х Î F»

В - «элемент х из множества G, т.е. х Î G»

С - «множества F и G равны».

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

((А®В)&(В®А))®С.

Пусть А (х₁,...,х₂) — пропозициональная формула, где х₁,...,х₂ — входящие в нее пропозицио­нальные переменные. Конкретный набор истинностных значений, приписанных переменным х₁,...,х_{2 ,} называется интерпретацией формулы А. Формула может быть истинной (иметь значение И) при одной интерпретации и ложной (иметь значение Л) при другой интерпретации. Значение формулы А в интерпретации I будем обозначать I(А). Формула, истинная при некоторой интер­претации, называется выполнимой. Формула, истинная при всех возможных интерпретациях, на­зывается общезначимой (или тавтологией). Формула, ложная при всех возможных интерпрета­циях, называется невыполнимой (или противоречием). Формула, ложная при некоторой интерпретации, называется опровержимой.